dhart.pathfinding.calculate_distance_and_predecessor

dhart.pathfinding.calculate_distance_and_predecessor(graph: Graph, cost_type: str = '') → Tuple[FloatArray2D, IntArray2D]

Calculate distance and predecessor matricies for a graph in C++

Parameters:

• graph – Graph to generate predecessor/distance matricies from

• cost_type – Type of cost to use to generate distance and predecessor matricies. Uses graph’s default cost type if left blank

Raises:

KeyError – cost_type wasn’t left blank, and didn’t already exist in the graph.

Returns:

The Distance and Predecessor matricies for graph.

Examples

Create the predecessor and distance matricies for a graph

>>> from dhart.pathfinding import calculate_distance_and_predecessor
>>> from dhart.spatialstructures import Graph

>>> # Create a graph, add some nodes and edges, then compress
>>> g = Graph()
>>> nodes = [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 1, 2)]
>>> g.AddEdgeToGraph(nodes[1], nodes[2], 20)
>>> g.AddEdgeToGraph(nodes[0], nodes[2], 5)
>>> g.AddEdgeToGraph(nodes[1], nodes[0], 10)
>>> csr = g.CompressToCSR()
>>> # Calculate distance/predecessor matrix
>>> distance_matrix, predecessor_matrix = calculate_distance_and_predecessor(g)
>>> print(distance_matrix)
[[ 0. 15. 10.]
 [-1.  0. -1.]
 [-1.  5.  0.]]
>>> print(predecessor_matrix)
[[ 0  2  0]
 [-1  1 -1]
 [-1  2  2]]