Path finding algorithms for explanation (indra.explanation.pathfinding)

Path finding functions (indra.explanation.pathfinding.pathfinding)

indra.explanation.pathfinding.pathfinding.shortest_simple_paths(G, source, target, weight=None, ignore_nodes=None, ignore_edges=None)[source]
Generate all simple paths in the graph G from source to target,
starting from shortest ones.

A simple path is a path with no repeated nodes.

If a weighted shortest path search is to be used, no negative weights are allowed.

Parameters:
  • G (NetworkX graph) –
  • source (node) – Starting node for path
  • target (node) – Ending node for path
  • weight (string) – Name of the edge attribute to be used as a weight. If None all edges are considered to have unit weight. Default value None.
  • ignore_nodes (container of nodes) – nodes to ignore, optional
  • ignore_edges (container of edges) – edges to ignore, optional
Returns:

path_generator – A generator that produces lists of simple paths, in order from shortest to longest.
Return type:

generator
Raises:
  • NetworkXNoPath – If no path exists between source and target.
  • NetworkXError – If source or target nodes are not in the input graph.
  • NetworkXNotImplemented – If the input graph is a Multi[Di]Graph.

Examples

>>> G = nx.cycle_graph(7)
>>> paths = list(nx.shortest_simple_paths(G, 0, 3))
>>> print(paths)
[[0, 1, 2, 3], [0, 6, 5, 4, 3]]

You can use this function to efficiently compute the k shortest/best paths between two nodes.

>>> from itertools import islice
>>> def k_shortest_paths(G, source, target, k, weight=None):
...     return list(islice(nx.shortest_simple_paths(G, source, target,
...         weight=weight), k))
>>> for path in k_shortest_paths(G, 0, 3, 2):
...     print(path)
[0, 1, 2, 3]
[0, 6, 5, 4, 3]

Notes

This procedure is based on algorithm by Jin Y. Yen [1]. Finding the first $K$ paths requires $O(KN^3)$ operations.

See also

all_shortest_paths(), shortest_path(), all_simple_paths()

References

[1]Jin Y. Yen, “Finding the K Shortest Loopless Paths in a Network”, Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716.

Do breadth first search from a given node and yield paths

Parameters:
  • g (nx.Digraph) – An nx.DiGraph to search in. Can also be a signed node graph.
  • source_node (node) – Node in the graph to start from.
  • g_nodes (nx.classes.reportviews.nodesNodeView) – The nodes property to look up nodes from. Set this if the node attribute ‘ns’ needs to be looked up from another graph object than the one provided as g. Default: g.nodes
  • g_edges (nx.classes.reportviews.OutMultiEdgeView|OutEdgeView) – The edges property to look up edges and their data from. Set this if the edge beliefs needs to be looked up from another grapth object than g. Default: d.edges
  • reverse (bool) – If True go upstream from source, otherwise go downstream. Default: False.
  • depth_limit (int) – Stop when all paths with this many edges have been found. Default: 2.
  • path_limit (int) – The maximum number of paths to return. Default: no limit.
  • max_per_node (int) – The maximum number of paths to yield per parent node. If 1 is chosen, the search only goes down to the leaf node of its first encountered branch. Default: 5
  • node_filter (list[str]) – The allowed namespaces (node attribute ‘ns’) for the nodes in the path
  • node_blacklist (set[node]) – A set of nodes to ignore. Default: None.
  • terminal_ns (list[str]) – Force a path to terminate when any of the namespaces in this list are encountered and only yield paths that terminate at these namepsaces
  • sign (int) – If set, defines the search to be a signed search. Default: None. max_memory : int The maximum memory usage in bytes allowed for the variables queue and visited. Default: 1073741824 bytes (== 1 GiB).
Yields:

path (tuple(node)) – Paths in the bfs search starting from source.
indra.explanation.pathfinding.pathfinding.find_sources(graph, target, sources)[source]

Get the set of source nodes with paths to the target.

Given a common target and a list of sources (or None if test statement subject is None), perform a breadth-first search upstream from the target to determine whether there are any sources that have paths to the target. For efficiency, does not return the full path, but identifies the upstream sources and the length of the path.

Parameters:
  • graph (nx.DiGraph) – A DiGraph with signed nodes to find paths in.
  • target (node) – The signed node (usually common target node) in the graph to start looking upstream for matching sources.
  • sources (list[node]) – Signed nodes corresponding to the subject or upstream influence being checked.
Returns:

Yields tuples of source node and path length (int). If there are no paths to any of the given source nodes, the generator is empty.
Return type:

generator of (source, path_length)
indra.explanation.pathfinding.pathfinding.get_path_iter(graph, source, target, path_length, loop)[source]

Return a generator of paths with path_length cutoff from source to target.

Path finding utilities (indra.explanation.pathfinding.util)

indra.explanation.pathfinding.util.path_sign_to_signed_nodes(source, target, edge_sign)[source]

Translates a signed edge or path to valid signed nodes

Pairs with a negative source node are filtered out.

Parameters:
  • source (str|int) – The source node
  • target (str|int) – The target node
  • edge_sign (int) – The sign of the edge
Returns:

sign_tuple – Tuple of tuples of the valid combination of signed nodes
Return type:

(a, sign), (b, sign)
indra.explanation.pathfinding.util.signed_nodes_to_signed_edge(source, target)[source]

Create the triple (node, node, sign) from a pair of signed nodes

Assuming source, target forms an edge of signed nodes: edge = (a, sign), (b, sign), return the corresponding signed edge triple

Parameters:
  • source (tuple(str|int, sign)) – A valid signed node
  • target (tuple(str|int, sign)) – A valid signed node
Returns:

A tuple, (source, target, sign), representing the corresponding signed edge.
Return type:

tuple
indra.explanation.pathfinding.util.get_sorted_neighbors(G, node, reverse, g_edges)[source]

Sort the returned neighbors in descending order by belief

Parameters:
  • G (nx.DiGraph) – A networkx DiGraph
  • node (str|int) – A valid networkx node name
  • reverse (bool) – Indicates direction of search. Neighbors are either successors (downstream search) or predecessors (reverse search).
  • g_edges (nx.classes.reportviews.OutMultiEdgeView|OutEdgeView) – The edges graph property to look up edges and their data from. Typically this is G.edges.