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, embedding_sims=None) classmethod

Analyze a path to determine the 'Standard Anchor'.

It traverses the path from the candidate term. The first Standard Concept encountered via a MAPPING or VERSIONING edge is promoted as the Anchor.

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

Priority Queue Item for Dijkstra/A* search.

StandardConcept dataclass

A resolved Standard Concept resulting from a search.

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

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[ClassIDEnum]	Restrict traversal to specific edge types.	None
max_depth	int	Maximum path length.	6
on	date	Date for validity checks.	None
max_paths	int	Maximum number of paths to return.	20
traced	bool	If True, returns a GraphTrace object recording the search process.	False

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)

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[ClassIDEnum], frozenset[ClassIDEnum] optional	Restrict traversal to specific edge types.	None
max_depth	int	Maximum path length.	6
on	date	Date for validity checks.	None
max_paths	int	Maximum number of paths to return.	20

Returns:

Type	Description
list[GraphPath]	Found paths.

find_standard_paths(kg, target, candidate, predicate_kinds=None, max_depth=6, max_concepts=None, num_hops=1, *args, **kwargs)

Search for Standard Concepts related to a target ID, starting from a candidate.

This method traverses from the candidate (Non-Standard) concept to find Standard Concepts, then verifies if those Standard Concepts are ancestors of the target concept in the hierarchy.

Parameters:

Name	Type	Description	Default
kg	KnowledgeGraph	The graph instance.	required
target	int	The ancestor concept ID to check against.	required
candidate	CandidateHit	The search hit to start traversal from.	required
predicate_kinds	frozenset	Allowed edge types for traversal.	None
max_depth	int	Max separation levels allowed in the ancestor check.	6
max_concepts	int	Stop after finding this many unique standard concepts.	None
num_hops	int	Max hops allowed from the candidate to reach a standard concept.	1

Returns:

Type	Description
list[StandardConcept]	The resolved concepts.

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)

Helper function to reconstruct full paths from bidirectional BFS parent pointers.

trace_contains_step(trace, step)

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