graph_processing#

Module providing tools to create and manipulate graphs. Functions include graph construction from skeletons, simplification, reduction and clean-up of graphs.

class Percentile(p: float = 33.33)[source]#

Bases: object

Reducer that returns True if the p-th percentile of a binary array is 1.

For binary arrays this is equivalent to mean >= (1 - p/100), implemented as a parallel Cython mean + single vectorised threshold.

Warning

Only valid for binary (0/1) arrays. For quantitative properties use np.percentile directly.

Parameters:: p (float) – Percentile threshold in [0, 100]. p=33 means at least 67% of values must be 1 (consensus vote). p=50 means at least 50% of values must be 1 (simple majority).

tmp_dtype#: alias of float64

finalise(means: ndarray, offsets: ndarray, arr_dtype: dtype) → ndarray[source]#

Convert Cython-computed means to a binary result.

Parameters:

means (np.ndarray) – Float means computed by cy_reduce (one per chain).
offsets (np.ndarray) – Chain boundary offsets (length n_chains + 1).
arr_dtype (np.dtype) – dtype of the source binary array — used for output dtype.

is_compatible(prop_name, arr)[source]#

class PropertyAggregator(graph: Graph, mapping: Dict[str, Callable], kind: str = 'edge', n_processes: int | None = None)[source]#

Bases: object

accumulate(indices: Sequence[int]) → None[source]#

Append the result of aggregating (applying the specified function) a chain of vertices or edges to the aggregator.

indiceslist/array of edge IDs (kind=”edge”): or vertex IDs (kind=”vertex”) that form one chain.

aggregate() → None[source]#: Aggregate the accumulated chains by applying the specified reduction functions

Note

For simple reduction functions (np.sum, np.mean, np.min, np.max), this is implemented in parallel using Cython for performance. Otherwise, this will fall back to a pure Python/numpy implementation.

apply(reduced_graph: Graph, reduced_edge_order: ndarray) → None[source]#

Attach the aggregated values as edge properties on graph. In cases where self.src_graph has edge geometry, this will also reduce this geometry and the edge_geometry_indices.

Note

This method is typically called once after reduce_graph has finished processing the chains and before returning the reduced graph.

Parameters:

reduced_graph (GraphGt.Graph) – The graph to which the aggregated properties will be added. This is typically the reduced graph returned by reduce_graph.
reduced_edge_order (np.ndarray) – The new edge order, i.e. the order in which edges are stored in the reduced graph.

get_indices_and_ranges(reduced_edge_order) -> (<class 'numpy.ndarray'>, <class 'numpy.ndarray'>)[source]#: Return a 1D array of all accumulated indices, concatenated from all chains. and the start and end indices for each chain as a 2D array.

ALLOWED_KINDS = ('edge', 'vertex', 'edge_geometry')#

Collect & aggregate graph-tool properties while you walk chains.

Parameters:

graph (GraphGt.Graph) – The working copy of the graph (g in reduce_graph).
mapping (Dict[str, Callable]) – Keys are property names (e.g. “length”), values are aggregation functions (e.g. np.sum, np.max …).
kind (str) – “edge” → aggregating edge properties “vertex”→ aggregating vertex properties

property edge_connectivity: ndarray#

property property_names#

class TwoPhaseReducer(*args, **kwargs)[source]#

Bases: Protocol

Protocol for reducers that require an intermediate dtype different from the output dtype — e.g. computing float means before thresholding to a binary output.

Implementors must define:: __name__ : str — maps to Cython reducer enum tmp_dtype : np.dtype — dtype for intermediate Cython accumulation finalise() : method — converts intermediate result to final output

finalise(intermediate: ndarray, offsets: ndarray, arr_dtype: dtype) → ndarray[source]#

is_compatible(prop_name: str, arr: ndarray) → None[source]#

tmp_dtype: dtype#

add_chain_id(graph, prop_kind)[source]#

annotate_edge_lengths(graph: Graph, coord_prop=None, edges=None, spacing=None)[source]#

Compute the length property for edges in a graph based on the voxel coordinates and the resolution of the voxels.

Parameters:

graph (graph_tool.Graph) – The source graph to annotate.
coord_prop (VertexPropertyMap | np.ndarray) – Array of shape (N,3) voxel indices (⟨x,y,z⟩)
spacing (tuple(float, float, float) | None) – Voxel pitch along each axis. If None, the value is retrieved from the graph’s spacing property.
warning:: (..) – Because this uses adjacent connectivity, it can only be used for graphs before reduction, i.e. before reduce_graph is called. Also, coord_prop must be integer-valued, i.e. voxel indices.

Notes

Works because every edge links adjacent voxels → only 26 displacement vectors.
Complexity: O(|E|) but with only cheap integer arithmetics + one final lookup.

check_chains(graph, chains, degree_2_v_ids, non_degree_2_v_ids)[source]#

Check if the chains computation is correct by verifying that all degree 2 vertices are included in the chains and that all non-degree 2 vertices are not included in the chains.

Parameters:

chains (list of list of edges) – List of chains in the graph.
degree_2_v_ids (array-like) – Array of vertex ids with degree 2.
non_degree_2_v_ids (array-like) – Array of vertex ids with degree not equal to 2.

Returns

bool: True if the computation is correct, False otherwise.

check_graph_is_reduce_compatible(graph)[source]#

clean_graph(graph: Graph, remove_self_loops: bool = True, remove_isolated_vertices: bool = True, vertex_mappings: dict[str, Callable] | None = None, verbose: bool = False) → Graph[source]#

Remove all cliques to get pure branch structure of a graph.

A clique is a cluster of vertices, defined as a connected component of branch points

Warning

This function is meant to be used on graphs before reduction, in which case clusters of branch points are immediately adjacent to each other.

Note

cliques are replaced by a single vertex connecting to all non-clique neighbours The center coordinate is used as the coordinate for that vertex. The vertex properties are reduced using the provided vertex_mappings functions. The edge properties are not reduced. The length edge property is computed as the length of the edge connecting the clique center to its neighbours.

Arguments

graphGraph: The graph to clean up.
remove_self_loops: bool: If True, remove self-loops from the graph.
remove_isolated_vertices: bool: If True, remove isolated vertices from the graph.
vertex_mappingsdict[str, Callable] | None: Dictionary of reduction functions to apply to vertex properties within cliques.
verbosebool: If True, prin progress information.

Returns

graphGraph: A graph removed of all cliques.

compute_label_confidence(graph, labels, conflict_mask, max_decay_steps=5)[source]#

Compute a per-vertex confidence score based on distance from conflict boundaries.

Vertices at a conflict boundary get confidence 0. Vertices further away decay linearly back to 1 over max_decay_steps steps.

Parameters:

graph (Graph) – The graph (typically edge-graph / line graph).
labels (np.ndarray) – Current label array (used only for array length).
conflict_mask (np.ndarray) – Boolean array from detect_label_conflicts().
max_decay_steps (int) – Number of graph steps over which confidence recovers from 0 to 1.

Returns

confidencenp.ndarray: Float array in [0, 1]. 0 = conflict boundary, 1 = at least max_decay_steps away from any conflict.

detect_label_conflicts(graph, labels, competing_pairs, label_masks=None, dilated_masks=None)[source]#

Detect vertices where competing labels are directly adjacent.

Parameters:

graph (Graph) – The graph (typically edge-graph / line graph).
labels (np.ndarray) – Current label array.
competing_pairs (dict of int to int) – Maps each label to its competitor (symmetric, e.g. {1: 2, 2: 1}).
label_masks (dict of int to np.ndarray, or None) – Pre-computed boolean masks per label value (labels == label_value). If None, recomputed here.
dilated_masks (dict of int to np.ndarray, or None) – Pre-computed dilated masks per label value. If None, recomputed here.

Returns

conflict_masknp.ndarray: Boolean array, True at direct conflict boundaries.
n_conflictsint: Total number of conflict vertices found.

drop_degree2_loops(graph)[source]#

Drop all loops in the graph that consist only of vertices with degree 2.

Parameters:: graph (GraphGt.Graph)

Returns

GraphGt.Graph: The graph with all pure degree 2 loops removed.

expand_graph(graph)[source]#

expand_graph_length(graph, length='length', return_edge_mapping=False)[source]#: Expand a reduced graph to a full graph.

find_chains(graph, *, return_endpoints_mask=False, return_edge_descriptors: bool = False)[source]#

Find chains (i.e. list of edges between vertices that are either branching points or end points) in a graph.

This is done in three steps and the results are combined: - Compute chains between degree 2 vertices that are connected to non-degree 2 vertices. - Add direct edges between non-degree 2 vertices. - Add pure degree 2 loops that are not connected to any non-degree 2 vertices. (if the graph is not fully connected, this will find isolated loops)

Parameters:

graph (Graph) – The graph to process.
return_endpoints_mask (bool) – If True, return a mask indicating which vertices are endpoints of the chains. This is particularly useful for debugging or further processing, especially in large graphs and when there may be pure degree 2 loops. where endpoint_mask is a 1-D bool np.NdArray aligned with vertex_ids. A value True means “this vertex is a real endpoint (degree != 2)”, False means “internal degree-2 vertex”. Default is False.
return_edge_descriptors (bool) – If True, also return a list of edge descriptors (e.g. edge objects or tuples) for each chain. This is particularly useful for debugging or further processing, however, it has a computational cost because it materialises python objects.

Returns

chainslist

Without mask (default):: list of 2-tuples (edge_ids, vertex_ids)
With mask (return_endpoint_mask=True):: list of 3-tuples (edge_ids, vertex_ids, endpoint_mask)

get_clique_neighbours(graph, clique_vertices)[source]#

get_clique_neighbours_set(g, clique_vertices)[source]#

get_distance_map_27(resolution)[source]#

Create a distance lookup table for the 26 possible displacements in 3D. Uses the resolution to convert voxel displacements to physical distances.

Parameters:: resolution (tuple(float, float, float)) – Size of one voxel along each axis (x, y, z).

Returns

distance_table: np.ndarray: A 1D array of shape (27,) containing the distances for each of the 26 possible displacements in 3D, plus one entry for the zero displacement.

graph_from_skeleton(skeleton, points=None, radii=None, compute_vertex_coordinates=True, compute_edge_length=True, check_border=True, delete_border=False, spacing=None, physical_units='', n_processes=-2, verbose=False)[source]#

Converts a binary skeleton image to a graph-tool graph.

Note

Edges are detected between neighbouring foreground pixels using 26-connectivity.

Warning

If delete_border is True, the input skeleton will be mutated in-place. Otherwise the behaviour is RO

Arguments

skeleton: array: Source with 2d/3d binary skeleton.
points: array: List of skeleton points as 1d indices of flat skeleton array (optional to save processing time).
radii: array: List of radii associated with each vertex.
compute_vertex_coordinates: bool: If True, store coordinates of the vertices / edges.
compute_edge_length: bool: If True, compute the length of each edge based on the vertex coordinates. If spacing is also provided, the length is computed in physical units.
check_border: bool: If True, check if the border is empty. The algorithm requires this.
delete_border: bool: If True, delete the border (check_border is ignored in this case).
spacing: array: Spacing of the voxels in the skeleton in physical units (e.g. micrometers) in each dimension.
physical_units: str: Description of the physical units of the spacing, e.g. ‘micrometers’, ‘µm’…
verbose: bool: If True, print progress information.

Returns

graphGraph class: The graph corresponding to the skeleton.

graph_to_skeleton(graph, sink=None, dtype=<class 'bool'>, values=True)[source]#: Create a binary skeleton from a graph.

mean_vertex_coordinates(coordinates)[source]#

medoid_vertex_coordinates(coordinates)[source]#

Compute the vertex coordinates as the median of the coordinates. This gives a vertex on the grid that is closest to the median of the coordinates.

Note

The vertex may not be one of the original coordinates, but it is guaranteed to be a valid vertex coordinate in the graph.

Parameters:: coordinates

Returns

neighbours(indices: ndarray, offset: int) → ndarray[source]#: indices – sorted 1-D array of flat voxel indices (int64) offset – neighbour offset in elements (signed) returns – (m,2) array with vertex-index pairs

print_graph_info(graph, timer, non_degree_2_vertices_ids)[source]#

propagate_labels(graph, *, label_property, score_properties, competing_pairs, radii_property=None, min_radii=None, surface_mask_properties=None, label_priority=None, max_iterations=20, initial_threshold=0.15, threshold_growth=1.15, threshold_ceiling=0.6, unlabelled_value=0)[source]#

Simultaneously propagate competing labels outward from seeds on a graph.

At each iteration, each label type dilates by one graph step. A newly reached vertex/edge is claimed if:

its score for that label exceeds the current threshold
it is not already labelled
it is not masked by a surface mask
it is not adjacent to a competing label (1-step buffer)

All input arrays are read from vertex properties of graph by name. This is designed to work with the edge-graph (line graph).

Confidence decreases with distance from seeds: the acceptance threshold increases each iteration.

After propagation, direct boundaries between competing labels are detected and stored as vertex properties 'label_conflict' (boolean) and 'label_confidence' (float in [0, 1]). A warning is emitted if any conflicts are found.

Parameters:

graph (Graph) – The graph to propagate on (meant to be a line graph). Vertex properties are read by name.
label_property (str) – Name of the vertex property holding initial labels (int). Modified in place during propagation. unlabelled_value marks unclaimed elements.
score_properties (dict of int to str) – Maps label value to vertex property name holding scores for that label (float in [0, 1]). Keys are kind label values
competing_pairs (dict of int to int) – Maps each label to its competitor (e.g. {1: 2, 2: 1}). Both directions must be present.
radii_property (str or None) – Name of the vertex property holding radii (float). Used with min_radii for a hard radius floor.
min_radii (dict of int to float, or None) – Per-label minimum radius. Vertices below this cannot receive that label. If None, no radius constraint.
surface_mask_properties (dict of int to str or None) – Maps label value to vertex property name holding a boolean surface mask (True = propagation forbidden), use np.zeros or None for labels with no surface constraint.
label_priority (dict of int to int, or None) – Maps label to priority. Higher-priority labels can convert adjacent lower-priority boundary edges. Currently unused; reserved for future use.
max_iterations (int) – Maximum propagation rounds.
initial_threshold (float) – Starting score threshold (energy) to cross for accepting a label (starts low near seeds).
threshold_growth (float) – Multiplicative factor per iteration (> 1.0 means increasing).
threshold_ceiling (float) – Maximum threshold — propagation stops trying above this.
unlabelled_value (int) – The label value for unclaimed elements (means “not yet classified”).

Returns

labelsnp.ndarray: Updated label array (extracted from the vertex property).
n_iterationsint: Number of iterations actually performed.

Warns:: UserWarning – If direct boundaries between competing labels are detected after propagation. Inspect the 'label_conflict' and 'label_confidence' vertex properties for details.