dijkstra – Dijkstra search

dijkstra.backtrack(previous, start)

Collect edges visited by dijkstra kernel.

Parameters:

• previous – dictionary of settled nodes
• start – node id to start backtracking from

Returns:

reversed list of edges

Example:

>>> list(backtrack({3: (2, 25, 15), 2: (1, 10, 10), 1: (None, 0.0, None)}, 3))
[(2, 3, 15), (1, 2, 10)]

dijkstra.bidirect_dijkstra(graph, start, end, bwd_graph=None, cost_fn=<function identity>)

Bidirectional dijkstra search on directed graph.

Search from both start and end of the graph reducing search space substantially.

Parameters:

• graph – adjacency list of graph
• start – node to start search at
• end – final node
• bwd_graph – reversed graph for backward search
• cost_fn – cost function applied on edges

Example:

>>> graph = make_graph([(1, 2, 10.0), (2, 3, 15.0), (1, 3, 30.0)])
>>> bidirect_dijkstra(graph, 1, 3)
(25.0, [(1, 2, 10.0), (2, 3, 15.0)])

dijkstra.dijkstra(graph, start, end, cost_fn=<function identity>)

Dijkstra search on directed graph.

Parameters:

• graph – adjacency list of graph
• start – node to start search at
• end – final node
• cost_fn – cost function applied on edges

Example:

>>> graph = make_graph([(1, 2, 10.0), (2, 3, 15.0), (1, 3, 30.0)])
>>> dijkstra(graph, 1, 3)
(25.0, [(1, 2, 10.0), (2, 3, 15.0)])

dijkstra.dijkstra_kernel(graph, start, previous, cost_fn)

Generator for dijkstra search.

Each iteration yields visited node id and cost to reach it from start node.

Parameters:

• graph – adjacency list of graph
• start – start node id
• previous – dictionary for storing settled nodes
• cost_fn – cost function applied for each edge, must be stateless

dijkstra.identity(value)

Identity mapping of single argument.

dijkstra.just_ids(source)

Convert dijkstra result to contain only node ids.

Parameters:source – (cost, edges) tuple returned by dijkstra search

Example:

>>> just_ids((25.0, [(1, 2, 10.0), (2, 3, 15.0)]))
(25.0, [1, 2, 3])

dijkstra.make_graph(source, edge_factory=<function identity>)

Make graph out of list of edges.

Parameters:

• source – list of tuples in form of (from, to, *payload)
• edge_factory – factory for edge attributes

Returns:

adjacency list

Example:

>>> make_graph([(1, 2, 10), (2, 3, 15), (1, 3, 30)])
defaultdict(<type 'list'>, {1: [(2, 10), (3, 30)], 2: [(3, 15)]})

>>> from collections import namedtuple
>>> EdgeAttrs = namedtuple('EdgeAttrs', 'time distance mode')
>>> make_graph([(1, 2, 10, 0.4, 'WALK'), (2, 3, 30, 15, 'BUS'), (1, 3, 15, 30, 'TRAIN')], edge_factory=EdgeAttrs) 
defaultdict(<type 'list'>, {1: [(2, EdgeAttrs(time=10, distance=0.4, mode='WALK')), (3, EdgeAttrs(time=15, distance=30, mode='TRAIN'))], 2: [(3, EdgeAttrs(time=30, distance=15, mode='BUS'))]})

dijkstra.reverse_graph(source)

Reverse direction of graph.

Parameters:source – adjacency list of graph

Example:

>>> reverse_graph(make_graph([(1, 2, 10), (2, 3, 15), (1, 3, 30)]))
defaultdict(<type 'list'>, {2: [(1, 10)], 3: [(1, 30), (2, 15)]})