Path planning

These methods find a path from a start vertex to a goal vertex. path_BFS() finds the path with the fewest edges, while path_UCS() and path_Astar() find the path with the lowest total cost.

`path_BFS`	Breadth-first search for path
`path_UCS`	Uniform cost search for path
`path_Astar`	A* search for path

Details

Graph.path_BFS(S, G, verbose=False, summary=False)[source]

Breadth-first search for path

Parameters:

S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
verbose (bool) – print search progress, defaults to False
summary (bool) – print a one-line search summary, defaults to False

Raises:

TypeError – S or G is neither a vertex nor a string
KeyError – S or G is a name not in the graph
ValueError – an edge on the path has no cost

Returns:

list of vertices from S to G inclusive and path length, or None if there is no path

Return type:

(list of Vertex subclass, float) or None

Compute a path from vertex S to vertex G using breadth-first search. The path is guaranteed to be the shortest in terms of number of edges, but not necessarily the cheapest in terms of edge costs. This search is not suited to graphs with edge weights, and is inefficient in that it explores all vertices.

Returns a list of vertices that starts with vertex S and ends with vertex G if possible, otherwise returns None – so check the result before unpacking it.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,0], name='v2')
>>> v3 = g.add_vertex(coord=[2,0], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1}
>>> g.add_edge(v2, v3)
Edge{[v2] -- [v3], cost=1}
>>> path, length = g.path_BFS(v1, v3)
>>> print(path)
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 0)], Vertex[v3, coord=(2, 0)]]
>>> print(length)
2.0

Note

Self-loops are ignored. If there are parallel edges the cheapest is used for the path length.

Seealso:: path_UCS() path_Astar()

Graph.path_UCS(S, G, verbose=False, summary=False)[source]

Uniform cost search for path

Parameters:

S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
verbose (bool) – print search progress, defaults to False
summary (bool) – print a one-line search summary, defaults to False

Raises:

TypeError – S or G is neither a vertex nor a string
KeyError – S or G is a name not in the graph
ValueError – an edge examined during the search has no cost

Returns:

list of vertices from S to G inclusive, path length and search tree, or None if there is no path

Return type:

(list of Vertex subclass, float, dict) or None

Compute the lowest-cost path from vertex S to vertex G using uniform cost search. The path is guaranteed to be the shortest in terms of traversed edge cost, but is inefficient in that it explores all vertices.

Returns a list of vertices that starts with vertex S and ends with vertex G if possible, otherwise returns None – so check the result before unpacking it.

The search tree is returned as dict that maps a vertex to its parent.

The heuristic is the distance metric of the graph, which defaults to Euclidean distance.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,0], name='v2')
>>> v3 = g.add_vertex(coord=[2,0], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1}
>>> g.add_edge(v2, v3)
Edge{[v2] -- [v3], cost=1}
>>> path, length, tree = g.path_UCS(v1, v3)
>>> print(path)
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 0)], Vertex[v3, coord=(2, 0)]]
>>> print(length)
2.0

Note

Self-loops are ignored. If there are parallel edges the cheapest is used for the path length.

Seealso:: path_BFS() path_Astar()

Graph.path_Astar(S, G, verbose=False, summary=False)[source]

A* search for path

Parameters:

S (Vertex subclass) – start vertex
G (Vertex subclass) – goal vertex
verbose (bool) – print search progress, defaults to False
summary (bool) – print a one-line search summary, defaults to False

Raises:

TypeError – S or G is neither a vertex nor a string
KeyError – S or G is a name not in the graph
ValueError – an edge examined during the search has no cost

Returns:

list of vertices from S to G inclusive, path length and search tree, or None if there is no path

Return type:

(list of Vertex subclass, float, dict) or None

Compute the lowest-cost path from vertex S to vertex G using A*t search. The path is guaranteed to be the shortest in terms of traversed edge cost, and the search is efficient in terms of the number of vertices explored.

Returns a list of vertices that starts with vertex S and ends with vertex G if possible, otherwise returns None – so check the result before unpacking it.

The search tree is returned as dict that maps a vertex to its parent.

The heuristic is the distance metric of the graph, which defaults to Euclidean distance.

>>> from pgraph import UGraph
>>> g = UGraph()
>>> v1 = g.add_vertex(coord=[0,0], name='v1')
>>> v2 = g.add_vertex(coord=[1,0], name='v2')
>>> v3 = g.add_vertex(coord=[2,0], name='v3')
>>> g.add_edge(v1, v2)
Edge{[v1] -- [v2], cost=1}
>>> g.add_edge(v2, v3)
Edge{[v2] -- [v3], cost=1}
>>> path, length, tree = g.path_Astar(v1, v3)
>>> print(path)
[Vertex[v1, coord=(0, 0)], Vertex[v2, coord=(1, 0)], Vertex[v3, coord=(2, 0)]]
>>> print(length)
2.0

Note

Self-loops are ignored. If there are parallel edges the cheapest is used for the path length.

Seealso:: heuristic() path_BFS() path_UCS()