RoadGraph

class roadgraph.RoadGraph(memo=None)

Graph implementation for easy access.

Parameters:memo – parameter for deepcopy operator.

append_way(nodes)

Stores list of waypoints.

Parameters:nodes – list of waypoints Returns:

dfs(node, ignore=None, skip_history=0)

Implements depth-first search with some modifications for RoadGraph.

Parameters:

• node – the node where the DFS should start
• skip_history – number of steps back in history that cannot be visited
• ignore – sequence of nodes that may not be revisited

Returns:

list of nodes

Return type:

iterator

edges()

Returns a list of all edges in the graph.

Return type:list

find_next_node(prev_node, cur_node)

Finds next final node with more than 1 child. Required for graph simplification algorithm.

Parameters:

• prev_node – previous node, limits the search from running backwards
• cur_node – current node

Returns:

(total_length, new_end_node, path between cur_node and new_end_node that can be simplified)

simplify(copy=True)

Simplifies graph, i.e. removes all nodes that contain only one child by connecting the preceding node to the following.

Parameters:copy – should create a copy of the graph; if False, will overwrite current graph Returns:the simplified graph, where each node has more than 1 child, or 1 (if it is an end node). Return type:RoadGraph

traverse_paths(node=None, length=1)

Traverses the graph for paths of the required length.

Parameters:

• node – starting node; if None, then all graph nodes are analyzed once
• length – Length of each path segment.

:rtype iterator

class roadgraph.RoadGraphX

Stores roads in a graph.

append_road(tags, nodes)

Adds a road to the graph.

Parameters:

• tags (dict) – a list of tags that describe the road (e.g. the name, maxspeed and other parameters)
• nodes (list) – list of waypoints aka nodes

Returns:

???

edges()

Returns all road segments in the road graph.

Returns:the edges aka the road segments Return type:list

nodes()

Returns all waypoints in the road graph.

Returns:the nodes aka the waypoints Return type:list

num_edges()

Returns total number of road segments in the road graph.

Returns:number of edges aka road segments Return type:int

num_nodes()

Returns total number of waypoints in the road graph.

Returns:number of nodes aka waypoints Return type:int