Paths

`omop_graph.graph.paths`

Pathfinding algorithms for the OMOP Knowledge Graph.

This module provides pure path-finding functions that accept a KnowledgeGraph instance. It focuses on discovering topological connections between nodes, including shortest paths, batch traversal, and specific standard concept resolution.

Scope

Algorithms that find paths between nodes. This module answers "what paths exist" but does not inherently score or explain them (that is handled by the reasoning module).

`GraphPath` `dataclass`

A sequence of steps representing a path through the graph.

Parameters:

Name	Type	Description	Default
`steps`	`tuple[PathStep, ...]`	The ordered sequence of steps.	required

`start_concept_id` `property`

Get the concept ID of the first node in the path.

Raises:

Type	Description
`ValueError`	If the path is empty.

`explain(kg)`

Generate a human-readable string explaining the path.

Parameters:

Name	Type	Description	Default
`kg`	`KnowledgeGraph`	The graph instance used to lookup names.	required

Returns:

Type	Description
`str`	A multi-line string description of the path.

`get_first_standard_concept_id()`

Find the ID of the first Standard Concept encountered in the path.

Returns:

Type	Description
`int \| None`	The concept ID if found, otherwise None.

`nodes()`

Get all concept IDs in the path (start node + all object nodes).

`Node` `dataclass`

A lightweight representation of a graph node for pathfinding.

Parameters:

Name	Type	Description	Default
`concept_id`	`int`	The OMOP Concept ID.	required
`is_standard`	`bool`	Whether this concept is a Standard Concept.	required

`PathExplanation` `dataclass`

A full explanation of a graph path, including semantic reasoning.

`from_path(kg, path, trace, match_kind)` `classmethod`

Construct an explanation by combining the path, the trace log, and semantic profiles.

`PathExplanationStep` `dataclass`

A single step in the explanation of a path.

`PathProfile` `dataclass`

Represents the resolved 'Anchor Concept' discovered along a graph path.

Attributes:

Name	Type	Description
`concept_id`	`int`	The ID of the resolved concept.
`concept_name`	`str`	The name of the resolved concept.
`is_standard`	`bool`	True if `concept_id` is a Standard OMOP Concept.
`original_concept_id`	`int`	The ID of the starting node (candidate).
`original_concept_name`	`str`	The name of the starting node.
`path`	`GraphPath`	The full topological path.

`from_path(kg, path, match_kind, source_concept_id=None)` `classmethod`

Analyze a path to determine the 'Standard Anchor'.

The first Standard Concept encountered via an IDENTITY edge is promoted as the anchor.

Notes

For zero-hop paths (source == target), source_concept_id must be provided; a ValueError is raised otherwise.

Parameters:

Name	Type	Description	Default
`source_concept_id`	`int`	Required when `path` has no steps (i.e. source == target).	`None`

`PathStep` `dataclass`

A single step in a graph path.

Parameters:

Name	Type	Description	Default
`subject`	`Node`	The starting node of the step.	required
`predicate`	`str`	The relationship ID connecting the nodes.	required
`object`	`Node`	The ending node of the step.	required

`QueueItem` `dataclass`

Frontier item for the cost-prioritised BFS in find_standard_paths.

Attributes:

Name	Type	Description
`cost`	`float`	Accumulated traversal cost. Currently always 0.0 (uniform BFS). Reserved as live infrastructure for future weighted traversal; see Notes in find_standard_paths.
`node`	`Node`	The graph node at this position in the frontier.
`mk`	`LabelMatchKind`	Match kind inherited from the originating candidate hit.
`iterations`	`int`	BFS depth (number of hops from the candidate).

`StandardConcept` `dataclass`

A resolved Standard Concept resulting from a search.

Attributes:

Name	Type	Description
`concept_id`	`int`	The OMOP Concept ID of the resolved standard concept.
`concept_name`	`str`	The name of the resolved standard concept.
`separation`	`int`	How far this standard concept is from where it needs to be, with a meaning that depends on whether ancestor targets were given to `find_standard_paths`: - Targets given (ancestor-constrained grounding): this is the ancestor- hierarchy distance (via `concept_ancestor.min_levels_of_separation`) from this concept to the required parent. - No targets given (unconstrained grounding): this is the hop count from the original found concept to the standard concept. This is the only distance field consumed by scoring (`scoring.py`'s parsimony penalty).
`original_id`	`int`	The OMOP Concept ID of the original candidate that search started from.
`original_name`	`str`	The name of the original candidate concept.
`matched_concept_label`	`str`	The text (name or synonym) that the original candidate matched on.
`match_kind`	`LabelMatchKind`	How the original candidate was matched (exact, partial, full-text, embedding).
`synonym`	`bool`	Whether the original candidate matched via a synonym rather than the primary concept name.
`hierarchy_cost`	`float, default 0.0`	Reserved for future weighted traversal; see `QueueItem.cost` and the Notes on `find_standard_paths`. Currently always 0.0.
`identity_hops`	`int, default 0`	The number of edges walked from the original candidate to reach this concept. Not used in scoring as of now.

`find_shortest_paths(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, traced=False, within_domain=True)`

Find shortest paths between source and target using bidirectional BFS.

Parameters:

Name	Type	Description	Default
`kg`	`KnowledgeGraph`	The graph instance.	required
`source`	`int`	Start concept ID.	required
`target`	`int`	End concept ID.	required
`predicate_kinds`	`set[PredicateKind]`	Restrict traversal to specific edge types.	`None`
`max_depth`	`int`	Maximum path length. Defaults to `6`.	`6`
`on`	`date`	Date for validity checks.	`None`
`max_paths`	`int`	Maximum number of paths to return. Defaults to `20`.	`20`
`traced`	`bool`	If True, returns a GraphTrace object recording the search process.	`False`
`within_domain`	`bool`	If True (default), only traverse edges where both concepts share the same domain_id. Set to False to allow cross-domain edges such as SNOMED attribute relationships (Has asso morph, Has finding site, etc.).	`True`

Returns:

Type	Description
`tuple[list[GraphPath], GraphTrace \| None]`	A list of paths and optionally the trace object.

`find_shortest_paths_batch(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, within_domain=True)`

Find shortest paths using an optimized batch-BFS approach.

This reduces the number of database queries by fetching edges for entire frontiers at once.

Parameters:

Name	Type	Description	Default
`kg`	`KnowledgeGraph`	The graph instance.	required
`source`	`int`	Start concept ID.	required
`target`	`int`	End concept ID.	required
`predicate_kinds`	`set[PredicateKind], frozenset[PredicateKind] optional`	Restrict traversal to specific edge types.	`None`
`max_depth`	`int`	Maximum path length. Defaults to `6`.	`6`
`on`	`date`	Date for validity checks.	`None`
`max_paths`	`int`	Maximum number of paths to return. Defaults to `20`.	`20`
`within_domain`	`bool`	If True (default), only traverse edges where both concepts share the same domain_id. Set to False to allow cross-domain edges such as SNOMED attribute relationships (Has asso morph, Has finding site, etc.).	`True`

Returns:

Type	Description
`list[GraphPath]`	Found paths.

`find_standard_paths(kg, targets, candidate, predicate_kinds=None, max_depth=6, max_concepts=None, within_domain=True)`

Search for standard concepts reachable from a candidate, optionally verified against ancestor targets.

Performs a breadth-first search (BFS) starting from the candidate. Each BFS wave drains the entire frontier at once. Non-standard concepts are expanded by fetching their outgoing edges and enqueueing standard neighbours.

Notes

This function has two modes:

When targets is provided, each wave issues a single batched concept_ancestor query for all standard concepts in that wave to reduce DB round trips (O(N) to O(W), where W is the number of waves. Standard concepts that satisfy at least one target ancestor constraint are recorded and not expanded further, preventing dilution by more distant concepts. Standard concepts with no ancestry match are expanded further (e.g. deprecated-standard -> replacement-standard chains).
When targets is None or empty, there is no ancestor to verify against: the first standard concept reached on each branch is accepted directly and not expanded further. This is a looser, unconstrained form of grounding. It "grounds" a candidate to its standard form without being able to disambiguate against a known hierarchy branch. See StandardConcept.separation for how distance is measured in this mode.

Parameters:

Name	Type	Description	Default
`kg`	`KnowledgeGraph`	The graph instance.	required
`targets`	`tuple of int`	Ancestor concept IDs to verify candidates against. A result is produced for each target that a reached standard concept is a genuine descendant of. When None or empty, no ancestor verification is performed (see above).	required
`candidate`	`CandidateHit`	The initial search hit to start traversal from.	required
`predicate_kinds`	`frozenset`	Allowed edge types for traversal. Defaults to all kinds when None. Callers in the grounding pipeline pass PredicateKind.IDENTITY exclusively, limiting traversal to Maps-to relationships between non-standard and standard concepts.	`None`
`max_depth`	`int`	Maximum min_levels_of_separation permitted in the concept_ancestor check when `targets` is given, or maximum identity-hop count permitted when `targets` is None. Defaults to `6`.	`6`
`max_concepts`	`int`	Per-target cap on unique standard concepts collected (or an overall cap when `targets` is None). Once every bucket has reached this count the search stops early.	`None`
`within_domain`	`bool`	When True (default), only traverse edges where both concepts share the same domain_id. Set to False to allow cross-domain edges such as SNOMED attribute relationships.	`True`

Returns:

Type	Description
`list of StandardConcept`	Flat deduplicated list of standard concepts that satisfy at least one target ancestor constraint, or, when `targets` is None, every standard concept reached.

Notes

The search is currently plain BFS because all edge costs are uniform (0.0). The QueueItem.cost field and the heapq structure are preserved as infrastructure for future weighted traversal. To upgrade to Dijkstra, define a COST_PREDICATES mapping from PredicateKind to a numeric cost (e.g. IDENTITY=0, HIERARCHY=1, ASSOCIATION=2), set new_cost accordingly in the expansion loop, and change the wave drain from a full-queue drain to a single-cost-level drain so that lower-cost nodes are always processed before higher-cost ones. A* would additionally require a domain-specific admissible heuristic added to the priority.

`get_unique_standard_concepts(concepts)`

Filter a list of StandardConcepts to keep only the best match per Concept ID.

Ranking criteria: 1. Separation (lower is better) 2. Match Kind (lower value is better in this enum) 3. Hierarchy Cost (lower is better)

`reconstruct_paths(source, target, meet, parents_fwd, parents_bwd, concept_standard_map)`

Reconstruct full paths from bidirectional BFS parent pointers.

Parameters:

Name	Type	Description	Default
`concept_standard_map`	`dict[int, bool]`	Mapping of concept_id → is_standard for all nodes discovered during BFS. Built with a single batched `kg.concept_views` call after the BFS completes so that every `Node` carries the correct flag with zero extra DB round-trips.	required

`trace_contains_step(trace, step)`

Check if a specific path step appears in the search trace.

Paths

omop_graph.graph.paths

GraphPath dataclass

start_concept_id property

explain(kg)

get_first_standard_concept_id()

nodes()

Node dataclass

PathExplanation dataclass

from_path(kg, path, trace, match_kind) classmethod

PathExplanationStep dataclass

PathProfile dataclass

from_path(kg, path, match_kind, source_concept_id=None) classmethod

PathStep dataclass

QueueItem dataclass

StandardConcept dataclass

find_shortest_paths(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, traced=False, within_domain=True)

find_shortest_paths_batch(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, within_domain=True)

find_standard_paths(kg, targets, candidate, predicate_kinds=None, max_depth=6, max_concepts=None, within_domain=True)

get_unique_standard_concepts(concepts)

reconstruct_paths(source, target, meet, parents_fwd, parents_bwd, concept_standard_map)

trace_contains_step(trace, step)

`omop_graph.graph.paths`

`GraphPath` `dataclass`

`start_concept_id` `property`

`explain(kg)`

`get_first_standard_concept_id()`

`nodes()`

`Node` `dataclass`

`PathExplanation` `dataclass`

`from_path(kg, path, trace, match_kind)` `classmethod`

`PathExplanationStep` `dataclass`

`PathProfile` `dataclass`

`from_path(kg, path, match_kind, source_concept_id=None)` `classmethod`

`PathStep` `dataclass`

`QueueItem` `dataclass`

`StandardConcept` `dataclass`

`find_shortest_paths(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, traced=False, within_domain=True)`

`find_shortest_paths_batch(kg, source, target, predicate_kinds=None, max_depth=6, on=None, max_paths=20, within_domain=True)`

`find_standard_paths(kg, targets, candidate, predicate_kinds=None, max_depth=6, max_concepts=None, within_domain=True)`

`get_unique_standard_concepts(concepts)`

`reconstruct_paths(source, target, meet, parents_fwd, parents_bwd, concept_standard_map)`

`trace_contains_step(trace, step)`