pyrieef.graph package

Submodules

pyrieef.graph.shortest_path module

class pyrieef.graph.shortest_path.CostmapToSparseGraph(costmap, average_cost=False)

Bases: object

Class that convert image to sparse graph representation TODO write a test for and decide weather it should be the costmap or the transpose of the costmap that should be passed to initialize the class.

Performs a shortest path querry and returns the shortes path between some source cell and target cell expressed in costmap coordinates. This method is targeted for single querry.

graph_dense : dense graph retpresentation of the costmap

convert()

Converts a costmap to a compressed sparse graph

costThe M x N matrix of costs. cost[i,j]

gives the cost of a certain node

node_map_coord = (i, j) node_graph_id = i + j * M

costmap_id(g_id)
dijkstra(graph_dense, s_i, s_j, t_i, t_j)

Performs a graph search for source and target

graph_dense : dense graph retpresentation of the costmap s_i, s_j : source coordinate on the costmap t_i, t_j : target coordinate on the costmap

dijkstra_on_map(costmap, s_i, s_j, t_i, t_j)

Performs a graph search for source and target on costmap this is the most efficient implementation for single querry graph search on a 2D costmap with scipy

costmapmatrix of costs, the type of edge cost

is given by the class option, either average of node cost or simply node cost which results in a directed graph.

s_i, s_j : source coordinate on the costmap t_i, t_j : target coordinate on the costmap

edge_cost(c_i, c_j, n_i, n_j)
graph_edge_cost(n1_i, n1_j, n2_i, n2_j)

return the value of an edge in the graph from n1 to n2

graph_id(i, j)
is_in_costmap(i, j)

Returns true if the node coord is in the costmap

static neiborghs(i, j)

returns the costmap coordinates of all neighbor nodes

shortest_path(predecessors, s_i, s_j, t_i, t_j)

Performs a shortest path querry and returns the shortes path between some source cell and target cell expressed in costmap coordinates

predecessors : as obdtained by shortest_paths function

shortest_path_on_map(costmap, s_i, s_j, t_i, t_j)

Performs a graph search for source and target on costmap this is the most efficient implementation for single querry graph search on a 2D costmap with scipy

update_graph(costmap)

updates the graph fast

pyrieef.graph.shortest_path.check_symmetric(a, tol=1e-08)
pyrieef.graph.shortest_path.shortest_paths(graph_dense)
pyrieef.graph.shortest_path.symmetrize(a)

Module contents