Algorithms Module API Reference

graphite.algorithms

Implemented standard graph algorithms for Graphite graph database.

Functions:

• all_shortest_paths –

  All shortest paths from from_node to to_end.

• bfs –

  Highly Customizable BFS

• connected_components –

  Splits given nodes to connected components.

• neighborhood –

  Returns neighbors of start in given max_distance.

• shortest_path –

  Finds shortest path from from_node to to_end.

Classes

Functions

all_shortest_paths

all_shortest_paths(engine: GraphiteEngine, from_node: Node | str, to_end: Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None = None, direction: Direction = OUTGOING, relation_type: str | None = None, max_depth: int | None = None, allow_direction_switch: bool = False, ignore_nodes: set[str] | None = None, weight: str | None = None, max_results: int | None = None) -> list[tuple[str, int, list[tuple[Relation, Node]]]]

All shortest paths from from_node to to_end.

Non-weighted mode uses bfs() internally.

Not Implemented Completely

Weighted mode is not implemented yet.

Parameters:

• from_node (Node | str) –

  Starting node ID or object.

• to_end (Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None, default: None ) –

  One of below:

  • None: Match on all nodes in the result. It means all (or max_results) nearest neighbors.
  • Node ID or object: Match on all paths to given node.
  • Callable ((path) -> bool): Match on a path when given callable returns True.
• direction (Direction, default: OUTGOING ) –

  Direction to traverse.

• relation_type (str | None, default: None ) –

  Type of relations to limit traverse.

• max_depth (int | None, default: None ) –

  Maximum depth to traverse.

• allow_direction_switch (bool, default: False ) –

  If True allow direction switch in a path when direction=Direction.BOTH.

• ignore_nodes (set[str] | None, default: None ) –

  Visited set of node IDs to ignore.

• weight (str | None, default: None ) –

  Optional field name to weighted pathfinding.

• max_results (int | None, default: None ) –

  Maximum number of results to return.

Returns:

• list[tuple[str, int, list[tuple[Relation, Node]]]] –

  An empty list or a list of found paths sorted by distance with each item as:

  (destination_node_id, path_depth, [(step_relation_obj, step_node_obj), ...])
                                    ^^^^^^^  path_to_destination_node  ^^^^^^^
  

  path_depth is 0 for starting node, it means this is equal to the size of path_to_destination_node.

bfs

bfs(engine: GraphiteEngine, start: Node | str, end: Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None = None, stop_at_first: bool = True, direction: Direction = OUTGOING, relation_type: str | None = None, max_depth: int | None = None, include_start: bool = False, allow_direction_switch: bool = False, visited: set[str] | None = None, max_results: int | None = None) -> list[tuple[str, int, list[tuple[Relation, Node]]]]

Highly Customizable BFS (Breadth-First Search) in the graph.

Note

Steps are sorted by distance in returned result.

Parameters:

• start (Node | str) –

  Starting node ID or object.

• end (Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None, default: None ) –

  One of below:

  • None: Match on all nodes in the result.
  • Node ID or object: Match on all paths to given node.
  • Callable ((path) -> bool): Match on a path when given callable returns True.
• stop_at_first (bool, default: True ) –

  If True and end is provided, stops at first match.

• direction (Direction, default: OUTGOING ) –

  Direction to traverse.

• relation_type (str | None, default: None ) –

  Type of relations to limit traverse.

• max_depth (int | None, default: None ) –

  Maximum depth to traverse.

• include_start (bool, default: False ) –

  If True check starting node on result.

• allow_direction_switch (bool, default: False ) –

  If True allow direction switch in a path when direction=Direction.BOTH.

• visited (set[str] | None, default: None ) –

  Visited set of node IDs to ignore.

• max_results (int | None, default: None ) –

  Maximum number of results to return.

Returns:

• list[tuple[str, int, list[tuple[Relation, Node]]]] –

  An empty list or a list of found paths sorted by distance with each item as:

  (destination_node_id, path_depth, [(step_relation_obj, step_node_obj), ...])
                                    ^^^^^^^  path_to_destination_node  ^^^^^^^
  

  path_depth is 0 for starting node, it means this is equal to the size of path_to_destination_node.

connected_components

connected_components(engine: GraphiteEngine, nodes: Node | str | set[Node | str] | None = None, return_all_nodes: bool = False, direction: Direction = OUTGOING, relation_type: str | None = None, allow_direction_switch: bool = False, ignore_nodes: set[str] | None = None) -> list[set[str]]

Splits given nodes to connected components.

Note

Uses bfs() internally.

Parameters:

• nodes (Node | str | set[Node | str] | None, default: None ) –

  One or a set of node (objects or IDs) to group, or None to get all nodes from engine.

• return_all_nodes (bool, default: False ) –

  If True, includes all nodes in each component, not just intersection of them with input nodes. Has no effect when nodes = None. False is unusual when using a single node.

• direction (Direction, default: OUTGOING ) –

  Direction to traverse.

• relation_type (str | None, default: None ) –

  Type of relations to allow traverse.

• allow_direction_switch (bool, default: False ) –

  If True, allow direction switch in a path when direction = Direction.BOTH.

• ignore_nodes (set[str] | None, default: None ) –

  Node IDs to ignore.

Returns:

• list[set[str]] –

  List of component nodes.

neighborhood

neighborhood(engine: GraphiteEngine, start: Node | str, max_distance: int | None = None, filter_method: Callable[[list[tuple[Relation, Node]]], bool] | None = None, max_results: int | None = None, direction: Direction = OUTGOING, relation_type: str | None = None, allow_direction_switch: bool = False, ignore_nodes: set[str] | None = None) -> tuple[set[tuple[Node, int]], set[Relation]]

Returns neighbors of start in given max_distance.

Note

Uses bfs() internally.

Parameters:

• start (Node | str) –

  Starting node object or ID.

• max_distance (int | None, default: None ) –

  Maximum distance to traverse.

• filter_method (Callable[[list[tuple[Relation, Node]]], bool] | None, default: None ) –

  Optional callable to filter neighbors ((path) -> bool).

• max_results (int | None, default: None ) –

  Maximum number of results to return.

• direction (Direction, default: OUTGOING ) –

  Direction to traverse.

• relation_type (str | None, default: None ) –

  Type of relations to allow traverse.

• allow_direction_switch (bool, default: False ) –

  If True, allow direction switch in a path when direction = Direction.BOTH.

• ignore_nodes (set[str] | None, default: None ) –

  Node IDs to ignore.

Returns:

• tuple[set[tuple[Node, int]], set[Relation]] –

  Set of neighbors (including start) with their distance to start, and set of relations in neighborhood.

shortest_path

shortest_path(engine: GraphiteEngine, from_node: Node | str, to_end: Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None = None, direction: Direction = OUTGOING, relation_type: str | None = None, max_depth: int | None = None, allow_direction_switch: bool = False, ignore_nodes: set[str] | None = None, weight: str | None = None) -> tuple[str, int, list[tuple[Relation, Node]]] | None

Finds shortest path from from_node to to_end.

Non-weighted mode uses bfs() internally.

Not Implemented Completely

Weighted mode is not implemented yet.

Parameters:

• from_node (Node | str) –

  Starting node Id or object.

• to_end (Node | str | Callable[[list[tuple[Relation, Node]]], bool] | None, default: None ) –

  One of below:

  • None: Match on all nodes in the result. It means nearest neighbor.
  • Node ID or object: Match on all paths to given node.
  • Callable ((path) -> bool): Match on a path when given callable returns True.
• direction (Direction, default: OUTGOING ) –

  Direction to traverse.

• relation_type (str | None, default: None ) –

  Type of relations to allow traverse.

• max_depth (int | None, default: None ) –

  Maximum depth to traverse.

• allow_direction_switch (bool, default: False ) –

  If True allow direction switch in a path when direction = Direction.BOTH.

• ignore_nodes (set[str] | None, default: None ) –

  Node IDs to ignore.

• weight (str | None, default: None ) –

  Optional field name to weighted pathfinding. (Not implemented yet)

Returns:

• tuple[str, int, list[tuple[Relation, Node]]] | None –

  None or the shortest found path as:

  (destination_node_id, path_depth, [(step_relation_obj, step_node_obj), ...])
                                    ^^^^^^^  path_to_destination_node  ^^^^^^^
  

  path_depth is 0 for starting node, it means this is equal to the size of path_to_destination_node.