"""Build cell → nucleus → pathogen object trees from measurement tables.
Every object table in ``measurements.db`` is flat, and the relationships
between them are already stored: :mod:`spacr.schema` gives ``nucleus`` and
``pathogen`` a ``cell_id`` pointing at the cell they sit inside
(:data:`spacr.schema.CHILD_OBJECT_TABLES`). This module assembles those links
into a tree, so a question such as "cell 41 in field 3 has one nucleus and
four pathogens, and one of those pathogens has an area that would be
impossible inside that nucleus" can be answered by inspecting one cell.
It uses plain pandas with no Qt, so the tree can be built in a notebook and
tested without a display.
Why a tree and not a join
-------------------------
A join answers "give me every pathogen with its cell's area". A tree answers
"what is inside this cell", which is a different question and the one a person
looking at a crop actually has. The difference shows up in the failures: a
join silently drops a cell with no pathogens and silently drops a pathogen
whose ``cell_id`` names a cell that is not there. Both of those are findings —
the first is the negative control working, the second is a segmentation bug —
so :func:`build_forest` keeps childless parents and :func:`orphans` returns
the unattached children rather than discarding them.
Identity is the shared one
--------------------------
Nodes are keyed by :func:`spacr.selection.object_keys`, the same string the
UMAP, the plate view and the crop grid use, so selecting a node in the tree
publishes something every other view already understands. A child's parent is
resolved *within its own field*: ``cell_id`` is a label, not a key, and label
7 exists in every field on the plate.
The shared key carries the object type
--------------------------------------
:data:`spacr.selection.OBJECT_KEY_COLUMNS` used to be the field plus the
object label, with no table in it, so a nucleus labelled 1 and a pathogen
labelled 1 in the same field had **the same key**. A lineage tree is where
that became visible, because a cell's own children are exactly the objects
most likely to collide: four objects opened as three crops and which one you
got depended on the row order of ``png_list``.
:func:`spacr.selection.object_keys` now writes the object type into the key,
so a node's shared key already says which table it came from and
:attr:`LineageNode.node_id` is the same identity in a different spelling.
Both are kept. ``node_id`` is what the tree addresses its rows by and cannot
collide by construction; :meth:`LineageNode.key_collisions` compares the two
and is now a **regression test rather than a warning** — it finds nothing on a
correctly keyed forest, and :func:`build_forest` still takes ``typed=False``
so the collapse can be reproduced on demand rather than only remembered.
"""
from __future__ import annotations
import os
from dataclasses import dataclass
from dataclasses import field as _field
from typing import Any, Dict, Iterable, List, Mapping, Optional, Sequence, Tuple
import pandas as pd
from . import schema
from .active_learning import _object_label
__all__ = [
"LineageError",
"LineageNode",
"ROOT_TABLE",
"LINEAGE_TABLES",
"child_tables",
"field_key",
"node_key",
"build_forest",
"tree_for",
"orphans",
"lineage_frame",
"read_object_tables",
"describe_forest",
"forest_key_collisions",
"ID_SEPARATOR",
]
#: What separates the table from the object key in
#: :attr:`LineageNode.node_id`. A colon, because
#: :data:`spacr.schema.KEY_SEPARATOR` is ``'_'`` and is already inside the key
#: — joining on it again would make ``node_id`` as ambiguous as the thing it
#: exists to disambiguate.
ID_SEPARATOR = ":"
[docs]
class LineageError(ValueError):
"""Raised when a set of tables cannot be assembled into a lineage.
Raised rather than returning an empty forest: "this cell has no children"
and "the cell table has no object_label column so nothing could be
matched" render identically as a leaf node, and only one of them is a
result.
"""
#: The table whose rows are the roots of the tree. Cells contain nuclei and
#: pathogens; nothing contains a cell.
ROOT_TABLE = "cell"
#: The tables this module assembles, root first. ``cytoplasm`` is a parent
#: table in the schema but carries no ``cell_id``, so it has no place in a
#: containment tree — it is the cell minus its children, not a child.
LINEAGE_TABLES: Tuple[str, ...] = (ROOT_TABLE,) + schema.CHILD_OBJECT_TABLES
[docs]
def child_tables() -> Tuple[str, ...]:
"""The tables whose rows carry a parent link, from the schema itself.
Read off :data:`spacr.schema.OBJECT_TABLE_SCHEMAS` rather than written
out here, so a table that gains a ``parent_column`` joins the tree
without an edit in this file. ``organelle`` is in
:data:`spacr.schema.CHILD_OBJECT_TABLES` but has no declared schema
entry, so it is included by name — its per-object table is optional and
its rows carry ``cell_id`` when it exists.
"""
declared = tuple(
name for name, contract in schema.OBJECT_TABLE_SCHEMAS.items()
if contract.parent_column)
extra = tuple(name for name in schema.CHILD_OBJECT_TABLES
if name not in declared)
return declared + extra
[docs]
def field_key(row: Mapping[str, Any]) -> str:
"""The ``prcf`` of one row — the field a label is unique within.
``cell_id`` is an object *label*, and label 7 exists in every field of
every plate. Matching children to parents on the label alone attaches
every field's nuclei to every field's cell 7, which produces a tree that
looks plausible and is wrong everywhere.
:param row: an object-table row carrying every column of
:data:`spacr.schema.FIELD_KEY_COLUMNS`; their values are joined with
the schema key separator.
"""
return schema.KEY_SEPARATOR.join(
str(row[column]) for column in schema.FIELD_KEY_COLUMNS)
[docs]
def node_key(row: Mapping[str, Any],
object_type: Optional[str] = None) -> str:
"""The shared object key of one row: field, then the typed object id.
:param row: an object-table row.
:param object_type: which table it came from. ``None`` builds the untyped
key spaCR wrote before object types existed — the one that gives a
cell's nucleus 1 and its pathogen 1 the same name.
"""
label = str(row[schema.OBJECT_LABEL_KEY])
if object_type is not None and schema.is_object_type(object_type):
label = schema.object_id(label, object_type=object_type)
return schema.KEY_SEPARATOR.join([field_key(row), label])
@dataclass(frozen=True)
[docs]
class LineageNode:
"""One object and the objects it contains.
:param key: shared typed object key used by spaCR's other views and
selections.
:param table: object-table name from which the source row came.
:param label: integer object label within its field.
:param field: ``prcf`` field identifier containing the object.
:param children: contained objects, grouped in :data:`LINEAGE_TABLES`
order and then by label for deterministic trees.
:param row: copied source row retained so views can display measurements
without reopening the frame.
"""
key: str
table: str
label: int
field: str
children: Tuple["LineageNode", ...] = ()
row: Mapping[str, Any] = _field(default_factory=dict)
@property
[docs]
def node_id(self) -> str:
"""``'pathogen:plate1_r1_c1_f1_pathogen1'`` — the table, then the key.
Distinct by construction, which :attr:`key` was not until the object
type went into it. Now that it has, this is the same identity said
twice — and it stays, because it is what proves the other one:
:meth:`key_collisions` is exactly the comparison between them, and a
second identity that cannot collide is what makes the first one's
collisions detectable rather than invisible.
"""
return f"{self.table}{ID_SEPARATOR}{self.key}"
[docs]
def walk(self, depth: int = 0) -> Iterable[Tuple[int, "LineageNode"]]:
"""This node then its descendants, depth-first, with their depth."""
yield depth, self
for child in self.children:
yield from child.walk(depth + 1)
[docs]
def descendants(self) -> Tuple["LineageNode", ...]:
"""Everything below this node, depth-first, excluding itself."""
return tuple(node for depth, node in self.walk() if depth)
[docs]
def node_ids(self) -> Tuple[str, ...]:
"""Every :attr:`node_id` below (and at) this node, depth-first.
Always distinct — unlike :meth:`keys`, which cannot be.
"""
return tuple(node.node_id for _depth, node in self.walk())
[docs]
def keys(self) -> Tuple[str, ...]:
"""This node's key and every descendant's, depth-first, de-duplicated.
The order a selection made on this node publishes in, so the parent
comes first and the crops open with the cell at the front of the grid.
**As long as the subtree**, now that the shared key carries the object
type. It used not to be: a nucleus 1 and a pathogen 1 inside the same
cell were one key, de-duplicating was required
(sending the same key twice would draw the same crop twice), and four
objects opened as three. :meth:`key_collisions` is the check that this
no longer happens — it returns nothing on a typed forest.
"""
out: List[str] = []
seen = set()
for _depth, node in self.walk():
if node.key not in seen:
seen.add(node.key)
out.append(node.key)
return tuple(out)
[docs]
def key_collisions(self) -> Dict[str, Tuple[str, ...]]:
"""``{shared key: the tables that share it}``, for the ones that do.
**Empty on a correctly keyed forest.** Non-empty means this subtree holds
objects that every other view will treat as one: the crop grid shows
one of them, and which one depends on the order ``png_list`` happens
to be in. That was the ordinary case before the object type went into
the key; it is a regression now, and it is still detectable because
:attr:`node_id` cannot collide even when :attr:`key` can.
"""
by_key: Dict[str, List[str]] = {}
for _depth, node in self.walk():
by_key.setdefault(node.key, []).append(node.table)
return {key: tuple(tables) for key, tables in by_key.items()
if len(tables) > 1}
[docs]
def counts(self) -> Dict[str, int]:
"""How many of each table are inside this node (itself included)."""
out: Dict[str, int] = {}
for _depth, node in self.walk():
out[node.table] = out.get(node.table, 0) + 1
return out
[docs]
def find(self, key: str) -> Optional["LineageNode"]:
"""The node with this key, anywhere below (or at) this one.
:param key: shared object key to look for, compared as a string with
each node's :attr:`key` in depth-first order; the first match wins.
"""
for _depth, node in self.walk():
if node.key == str(key):
return node
return None
[docs]
def describe(self) -> str:
"""One line: what this is, and what is inside it."""
inside = {t: n for t, n in self.counts().items() if t != self.table}
if not inside:
return f"{self.table} {self.label} · nothing inside it"
parts = ", ".join(f"{n} {t}" for t, n in sorted(inside.items()))
return f"{self.table} {self.label} · {parts}"
def _normalise(frame: pd.DataFrame, table: str) -> pd.DataFrame:
"""Check one object table and give it string identity columns."""
needed = list(schema.FIELD_KEY_COLUMNS) + [schema.OBJECT_LABEL_KEY]
missing = [column for column in needed if column not in frame.columns]
if missing:
raise LineageError(
f"the {table!r} table is missing {missing}, so its objects cannot "
f"be named. A lineage needs "
f"{needed} on every table it assembles.")
out = frame.copy()
for column in needed:
out[column] = out[column].astype(str)
return out
[docs]
def build_forest(frames: Mapping[str, pd.DataFrame], *,
root: str = ROOT_TABLE,
typed: bool = True) -> Tuple[LineageNode, ...]:
"""Assemble object tables into one tree per root object.
:param frames: ``{table name: rows}``. Only the tables named in
:data:`LINEAGE_TABLES` are read; anything else is ignored, so a
caller can hand over everything it loaded.
:param root: the table whose rows become the roots.
:param typed: put each node's object table into its shared key, so a
cell's nucleus 1 and its pathogen 1 are two keys. ``False`` rebuilds
the untyped keys spaCR wrote before object types existed — kept so
the collapse can be *reproduced* rather than only remembered, which
is what makes :meth:`LineageNode.key_collisions` a test with two
sides to it.
:returns: one :class:`LineageNode` per root row, in field order then
label order.
:raises LineageError: when the root table is absent or unusable. A
missing *child* table is not an error — a run that measured cells and
not pathogens produces a forest of childless cells.
Childless roots are kept. A cell with no pathogens in an infection assay
is the negative control working, and a tree that dropped it would show
the infected population as if it were the whole plate.
"""
root = str(root)
if root not in frames:
raise LineageError(
f"no {root!r} table to build a lineage from; got "
f"{sorted(frames)}. Load the parent table as well as the "
f"children — a tree with no roots is a list.")
parents = _normalise(frames[root], root)
by_parent: Dict[Tuple[str, str], List[LineageNode]] = {}
for table in LINEAGE_TABLES:
if table == root or table not in frames:
continue
children = _normalise(frames[table], table)
parent_column = _parent_column(table, children)
if parent_column is None:
continue
rows = children.to_dict("records")
rows.sort(key=lambda r: _sort_label(r[schema.OBJECT_LABEL_KEY]))
for row in rows:
parent_label = _object_label(row.get(parent_column))
if not parent_label:
continue
node = _node(row, table, typed=typed)
by_parent.setdefault((node.field, parent_label), []).append(node)
roots: List[LineageNode] = []
parent_rows = parents.to_dict("records")
parent_rows.sort(key=lambda r: (field_key(r),
_sort_label(r[schema.OBJECT_LABEL_KEY])))
for row in parent_rows:
node = _node(row, root, typed=typed)
label = _object_label(row[schema.OBJECT_LABEL_KEY])
children = tuple(by_parent.get((node.field, label), ()))
roots.append(LineageNode(key=node.key, table=root, label=node.label,
field=node.field, children=children,
row=node.row))
return tuple(roots)
def _parent_column(table: str, frame: pd.DataFrame) -> Optional[str]:
"""The column linking ``table``'s rows to their parent, if it is there."""
contract = schema.OBJECT_TABLE_SCHEMAS.get(table)
candidates = [contract.parent_column] if contract is not None else []
candidates.append("cell_id")
candidates.append(f"{table}_cell_id")
for candidate in candidates:
if candidate and candidate in frame.columns:
return candidate
return None
def _sort_label(value: Any) -> Tuple[int, Any]:
"""Sort key that puts real labels in numeric order and junk last."""
text = _object_label(value)
return (0, int(text)) if text else (1, str(value))
def _node(row: Mapping[str, Any], table: str, *,
typed: bool = True) -> LineageNode:
"""Build a leaf lineage node from one measurement row.
:param row: Measurement row containing object and field identifiers.
:param table: Object-table name recorded on the node and optionally in its
key.
:param typed: Include ``table`` in the generated object key when true.
:returns: Leaf node with a normalized numeric label and a copied row.
"""
label = _object_label(row.get(schema.OBJECT_LABEL_KEY))
return LineageNode(key=node_key(row, table if typed else None),
table=table,
label=int(label) if label else 0,
field=field_key(row), children=(), row=dict(row))
[docs]
def tree_for(frames: Mapping[str, pd.DataFrame], key: str, *,
root: str = ROOT_TABLE,
typed: bool = True) -> Optional[LineageNode]:
"""The tree containing ``key``, or ``None``.
``key`` may name the root or anything inside it: asked about a pathogen,
this returns the *cell* it lives in, because the useful view of a
pathogen is the cell around it. A caller that wants only the subtree
calls :meth:`LineageNode.find` on the result.
The whole forest is rebuilt and rescanned on every call, and the cost is
the same whether the key is the first root or absent entirely, so a run
of lookups should call :func:`build_forest` once and use
:meth:`LineageNode.find` on what it gets back.
:param frames: ``{table name: rows}``, forwarded to :func:`build_forest`.
Only the tables in :data:`LINEAGE_TABLES` are read, so anything else
handed over is ignored, and a run that measured no pathogens
searches childless cells.
:param key: a shared object key, compared against :attr:`LineageNode.key`
after ``str()``. It is *not* compared against
:attr:`LineageNode.node_id`, so the table-prefixed spelling of the
same identity finds nothing and returns ``None``.
:param root: the table whose rows are the roots being searched. It is not
checked against what the children's parent column actually points at:
with ``root='nucleus'``, a pathogen whose ``cell_id`` equals a nucleus
label is attached to that nucleus, and a cell key then finds nothing
because no cell is in the forest at all.
:param typed: must agree with how ``key`` is spelled, and nothing checks
that it does. A typed key searched with ``typed=False`` — or a legacy
untyped one searched with the default — returns ``None``, the same
answer as "no such object". With ``typed=False``, collisions inside
one family still identify that family, but a key found in different
families raises rather than choosing whichever root sorts first.
:raises LineageError: when ``root`` is missing from ``frames``, or when a
table that is present cannot be named. The forest is built before the
search, so a ``nucleus`` table without its field columns raises even
when the wanted key belongs to a pathogen. A key that is merely not
there is ``None``, not an exception. Also raised when ``key`` names
objects in more than one family; use typed keys to disambiguate them.
"""
wanted = str(key)
matches: List[LineageNode] = []
for node in build_forest(frames, root=root, typed=typed):
if node.find(wanted) is not None:
matches.append(node)
if len(matches) > 1:
families = ", ".join(node.node_id for node in matches)
raise LineageError(
f"key {wanted!r} names objects in multiple lineage families: "
f"{families}. Use a typed object key to choose one family.")
return matches[0] if matches else None
[docs]
def orphans(frames: Mapping[str, pd.DataFrame], *,
root: str = ROOT_TABLE) -> pd.DataFrame:
"""Child rows whose parent link names no row in the root table.
A finding, not an error. A nucleus whose ``cell_id`` is 12 in a field
whose cell table has no object 12 means the two masks disagree — the
nucleus segmentation found something the cell segmentation did not — and
that is worth showing rather than dropping on the way into a tree.
:param frames: ``{table name: rows}``. The ``root`` table is required; each
other table in :data:`LINEAGE_TABLES` that is present and has a
parent-link column is checked, and anything else is ignored.
:returns: the offending rows with ``table`` and ``parent_id`` columns
added, in table then field then label order. Empty when everything
attaches, which is the healthy case.
"""
root = str(root)
if root not in frames:
raise LineageError(f"no {root!r} table to check parents against")
parents = _normalise(frames[root], root)
known = {
(field_key(row), _object_label(row[schema.OBJECT_LABEL_KEY]))
for row in parents.to_dict("records")
}
loose: List[Dict[str, Any]] = []
for table in LINEAGE_TABLES:
if table == root or table not in frames:
continue
children = _normalise(frames[table], table)
parent_column = _parent_column(table, children)
if parent_column is None:
continue
for row in children.to_dict("records"):
parent_label = _object_label(row.get(parent_column))
if not parent_label:
loose.append({**row, "table": table, "parent_id": ""})
elif (field_key(row), parent_label) not in known:
loose.append({**row, "table": table,
"parent_id": parent_label})
if not loose:
return pd.DataFrame(columns=["table", "parent_id"])
out = pd.DataFrame(loose)
return out.sort_values(
["table"] + list(schema.FIELD_KEY_COLUMNS) + [schema.OBJECT_LABEL_KEY],
kind="stable").reset_index(drop=True)
[docs]
def lineage_frame(forest: Sequence[LineageNode]) -> pd.DataFrame:
"""The forest flattened: one row per node, with its parent and depth.
For export, for a table view, and for the tests — a tree is awkward to
assert on and this is the same information in a shape pandas can compare.
:param forest: root nodes as returned by :func:`build_forest`, flattened
depth-first in order; roots get an empty ``parent_key`` and depth 0.
"""
rows: List[Dict[str, Any]] = []
def visit(node: LineageNode, parent: str, depth: int) -> None:
"""Append one node and recursively flatten its descendants.
:param node: lineage node to record before visiting its children.
:param parent: key of the caller-supplied parent, or an empty string
for a root.
:param depth: zero-based depth to store for this node.
:returns: None. A row containing node metadata and its current child
count is appended to the captured list, then children are visited
in their existing order with this node as parent.
"""
rows.append({"key": node.key, "table": node.table,
"label": node.label, "field": node.field,
"parent_key": parent, "depth": depth,
"n_children": len(node.children)})
for child in node.children:
visit(child, node.key, depth + 1)
for root in forest:
visit(root, "", 0)
return pd.DataFrame(rows, columns=["key", "table", "label", "field",
"parent_key", "depth", "n_children"])
[docs]
def forest_key_collisions(forest: Sequence[LineageNode]
) -> Dict[str, Tuple[str, ...]]:
"""Every shared key in ``forest`` that names more than one object.
Collisions are counted *within a family*, not across the whole forest:
two different cells' pathogens both labelled 1 in the same field cannot
happen (the label is unique per mask), while a nucleus 1 and a pathogen 1
inside one cell is the ordinary case. Merging the two would report a
collision on every plate.
:param forest: root nodes as returned by :func:`build_forest`; each root's
:meth:`LineageNode.key_collisions` are merged into one mapping.
"""
out: Dict[str, Tuple[str, ...]] = {}
for root in forest:
out.update(root.key_collisions())
return out
[docs]
def describe_forest(forest: Sequence[LineageNode]) -> str:
"""The shape of a whole forest in words.
Reports what a tree of ten thousand rows does not show at a glance: how
many parents have nothing inside them. In an infection assay that number
is the readout.
:param forest: root nodes as returned by :func:`build_forest`. The first
root's table is taken as the root table; an empty forest gets a
sentence saying there is nothing to show.
"""
if not forest:
return "No parent objects, so there is no lineage to show."
totals: Dict[str, int] = {}
childless = 0
for root in forest:
if not root.children:
childless += 1
for table, count in root.counts().items():
totals[table] = totals.get(table, 0) + count
root_table = forest[0].table
inside = ", ".join(f"{n} {t}" for t, n in sorted(totals.items())
if t != root_table) or "nothing"
return (f"{len(forest)} {root_table}(s) holding {inside}. "
f"{childless} of them ({childless / len(forest):.0%}) have "
f"nothing inside.")
[docs]
def read_object_tables(db_path: str,
tables: Optional[Sequence[str]] = None,
*, limit: int = 200_000) -> Dict[str, pd.DataFrame]:
"""Read the object tables a lineage needs. Safe on a worker thread.
Missing tables are absent from the result — a run that measured
cells and nuclei but no pathogens is a legitimate experiment, not a
broken database.
:param db_path: path to the measurements SQLite database, opened
read-only so the loader is safe to run on a worker thread.
:param limit: per-table row cap, so a mis-aimed path cannot turn into a
two-minute read behind a spinner.
:raises LineageError: when there is no database at ``db_path``.
"""
if not db_path or not os.path.isfile(db_path):
raise LineageError(f"no measurements database at {db_path!r}")
wanted = list(tables or LINEAGE_TABLES)
out: Dict[str, pd.DataFrame] = {}
from .database_concurrency import connect as _connect_database
connection = _connect_database(db_path, readonly=True)
try:
present = {
str(row[0]) for row in connection.execute(
"SELECT name FROM sqlite_master WHERE type='table'")
}
for table in wanted:
if table not in present:
continue
out[table] = pd.read_sql_query(
f'SELECT * FROM "{table}" LIMIT {int(limit)}', connection)
finally:
connection.close()
return out