dhart.pathfinding.DijkstraShortestPath

dhart.pathfinding.DijkstraShortestPath(graph: Graph, start: List[int | Tuple[float, float, float]], end: List[int | Tuple[float, float, float]], cost_type: str = '') → List[Path | None] | Path | None

Find the shortest path from start to end using Dijkstra’s shortest path algorithm

Accepts a list of starting / ending points or single starting/ending points.

Parameters:

• Graph – A valid C++ Graph

• start – one or more Starting Node IDs

• end – one or more Ending Node IDs

• cost_type – Which cost to use for path generation. If no cost type is specified, then the graph’s default cost type will be used. If a cost type is specified then it must already exist in the graph.

Returns:

if multiple start/end ids were passed.If a path cannot be found to

connect a start and end point that path will be set as None.

Union[Path, None]:

One start or end point was passed, return the single path or none if no path could be found between start and end.

Return type:

List[Union[path, None]]

Preconditions:

1. If using multiple paths, The length of start_ids must match the length of end_ids.

2. Each node in start_nodes and end_nodes must contain the x,y,z position (or id) of an existing node in graph

3. If cost_type is not left as the default, then it must be the name of a valid cost already defined in graph.

Raises:

• ValueError – Length of start and end arrays did not match

• KeyError – cost_type wasn’t blank and did not point to an already defined cost in the graph

Example

Creating a graph, adding edges to it, then generating a path from node 0 to 3.

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

>>> g = Graph()
>>> g.AddEdgeToGraph(0, 1, 100)
>>> g.AddEdgeToGraph(0, 2, 50)
>>> g.AddEdgeToGraph(1, 3, 10)
>>> g.AddEdgeToGraph(2, 3, 10)
>>> csr = g.CompressToCSR()

>>> SP = DijkstraShortestPath(g, 0, 3)
>>> print(SP)
[(50., 0) (10., 2) ( 0., 3)]

The same, but creating multiple paths.

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

>>> g = Graph()
>>> g.AddEdgeToGraph(0, 1, 100)
>>> g.AddEdgeToGraph(0, 2, 50)
>>> g.AddEdgeToGraph(1, 3, 10)
>>> g.AddEdgeToGraph(2, 3, 10)
>>> csr = g.CompressToCSR()

>>> SP = DijkstraShortestPath(g, [1] * 10, [3] * 10)
>>> for path in SP:
...     print(path)
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]
[(10., 1) ( 0., 3)]

Example

Creating a graph then calculating an alternate cost type and generating a path on it.

>>> import numpy as np
>>> from dhart import get_sample_model
>>> from dhart.geometry.obj_loader import LoadOBJ
>>> from dhart.graphgenerator import GenerateGraph
>>> from dhart.pathfinding import DijkstraShortestPath
>>> from dhart.raytracer import EmbreeBVH
>>> from dhart.spatialstructures.cost_algorithms import (
...                CalculateEnergyExpenditure, CostAlgorithmKeys)

Load the energy blob and create a BVH from it

>>> energy_blob_path = get_sample_model("energy_blob_zup.obj")
>>> energy_blob_mesh = LoadOBJ(energy_blob_path)
>>> bvh = EmbreeBVH(energy_blob_mesh)

Define graph generator parameters

>>> start_point = (-30, 0, 20)
>>> spacing = (1, 1, 10)
>>> max_nodes = 10000
>>> up_step, down_step = 5, 5
>>> up_slope, down_slope = 60, 60
>>> max_step_connections = 1

Generate a graph on it

>>> g = GenerateGraph(bvh, start_point, spacing, max_nodes,
...                    up_step, up_slope, down_step, down_slope,
...                    max_step_connections, cores=-1)

Compress the graph

>>> csr = g.CompressToCSR()

Generate an alternate cost type and store it in the graph

>>> CalculateEnergyExpenditure(g)

Generate a path using the energy expenditure cost and distance (the default)

>>> start_point = 1
>>> end_point = 150
>>> energy_expend_key = CostAlgorithmKeys.ENERGY_EXPENDITURE
>>> distance_path = DijkstraShortestPath(g, start_point, end_point)
>>> energy_path = DijkstraShortestPath(g, start_point, end_point, energy_expend_key)
>>>
>>> # Print both paths
>>> print("Distance Path:", [ (np.around(x[0],5), x[1]) for x in distance_path.array ] )
Distance Path: [(1.0, 1), (1.0, 12), (1.0, 26), (1.0, 43), (1.0, 64), (1.00001, 89), (1.41489, 118), (0.0, 150)]

>>> print("Energy Path:", [ (np.around(x[0],5), x[1]) for x in energy_path.array ] )
Energy Path: [(2.47461, 1), (2.49217, 12), (2.5, 26), (2.48045, 43), (2.45134, 64), (2.43783, 89), (2.75192, 118), (0.0, 150)]