shortest_path
==============

>>> import networkx as NX
>>> from networkx.operators import convert_node_labels_to_integers as cnlti
>>> G=cnlti(NX.grid_2d_graph(4,4),first_label=1,ordering="sorted")

    .. image:: paths_G.png

>>> H=NX.cycle_graph(7)
>>> DH=NX.cycle_graph(7,create_using=NX.DiGraph())

Paths and path lengths
----------------------

>>> NX.shortest_path_length(G,1,16)
6
>>> sp=NX.single_source_shortest_path_length(G,1)
>>> sp[16]
6
>>> NX.shortest_path(G,1,12)
[1, 2, 3, 4, 8, 12]

>>> NX.bidirectional_shortest_path(G,1,12)
[1, 2, 3, 4, 8, 12]

>>> sp=NX.single_source_shortest_path(G,1)
>>> sp[12] 
[1, 2, 3, 4, 8, 12]

>>> NX.shortest_path(H,0,3)
[0, 1, 2, 3]
>>> NX.shortest_path(H,0,4)
[0, 6, 5, 4]
>>> NX.bidirectional_shortest_path(H,0,3)
[0, 1, 2, 3]
>>> NX.bidirectional_shortest_path(H,0,4)
[0, 6, 5, 4]

>>> NX.shortest_path(DH,0,3)
[0, 1, 2, 3]
>>> NX.shortest_path(DH,0,4)
[0, 1, 2, 3, 4]
>>> NX.bidirectional_shortest_path(DH,0,3)
[0, 1, 2, 3]
>>> NX.bidirectional_shortest_path(DH,0,4)
[0, 1, 2, 3, 4]




Dijkstra
--------

>>> XG=NX.XDiGraph()
>>> XG.add_edges_from([('s','u',10) ,('s','x',5) ,('u','v',1) ,('u','x',2) ,('v','y',1) ,('x','u',3) ,('x','v',5) ,('x','y',2) ,('y','s',7) ,('y','v',6)])
>>> (D,P)= NX.single_source_dijkstra(XG,'s')
>>> P['v']
['s', 'x', 'u', 'v']
>>> D['v']
9
>>> NX.single_source_dijkstra_path(XG,'s')['v']
['s', 'x', 'u', 'v']
>>> NX.single_source_dijkstra_path_length(XG,'s')['v']
9

>>> NX.single_source_dijkstra(XG,'s')[1]['v'] 
['s', 'x', 'u', 'v']

>>> GG=XG.to_undirected()
>>> (D,P)= NX.single_source_dijkstra(GG,'s')
>>> P['v'] 
['s', 'x', 'u', 'v']
>>> D['v']     # uses lower weight of 2 on u<->x edge
8

>>> NX.dijkstra_path(GG,'s','v')
['s', 'x', 'u', 'v']
>>> NX.dijkstra_path_length(GG,'s','v')
8

>>> XG2=NX.XDiGraph()
>>> XG2.add_edges_from([[1,4,1],[4,5,1],[5,6,1],[6,3,1],[1,3,50],[1,2,100],[2,3,100]])
>>> NX.dijkstra_path(XG2,1,3)
[1, 4, 5, 6, 3]

>>> XG3=NX.XGraph()
>>> XG3.add_edges_from([ [0,1,2],[1,2,12],[2,3,1],[3,4,5],[4,5,1],[5,0,10] ])
>>> NX.dijkstra_path(XG3,0,3)
[0, 1, 2, 3]
>>> NX.dijkstra_path_length(XG3,0,3)
15
>>> XG4=NX.XGraph()
>>> XG4.add_edges_from([ [0,1,2],[1,2,2],[2,3,1],[3,4,1],[4,5,1],[5,6,1],[6,7,1],[7,0,1] ])
>>> NX.dijkstra_path(XG4,0,2)
[0, 1, 2]
>>> NX.dijkstra_path_length(XG4,0,2)
4

>>> G=NX.DiGraph()  # no weights
>>> G.add_edges_from([('s','u'), ('s','x'), ('u','v'), ('u','x'), ('v','y'), ('x','u'), ('x','v'), ('x','y'), ('y','s'), ('y','v')])
>>> NX.single_source_dijkstra(G,'s','v')[1]['v'] 
['s', 'u', 'v']
>>> NX.single_source_dijkstra(G,'s')[1]['v'] 
['s', 'u', 'v']

>>> NX.dijkstra_path(G,'s','v')
['s', 'u', 'v']
>>> NX.dijkstra_path_length(G,'s','v')
2


>>> NX.dijkstra_path(G,'s','moon')
Traceback (most recent call last):
...
NetworkXError: node s not reachable from moon


>>> NX.dijkstra_path_length(G,'s','moon')
Traceback (most recent call last):
...
NetworkXError: node s not reachable from moon

>>> NX.dijkstra_path(H,0,3)
[0, 1, 2, 3]

>>> NX.dijkstra_path(H,0,4)
[0, 6, 5, 4]

Bidirectional Dijkstra
----------------------

>>> NX.bidirectional_dijkstra(XG, 's', 'v')
(9, ['s', 'x', 'u', 'v'])
>>> NX.bidirectional_dijkstra(GG,'s','v')
(8, ['s', 'y', 'v'])
>>> NX.bidirectional_dijkstra(G,'s','v')
(2, ['s', 'x', 'v'])
>>> NX.bidirectional_dijkstra(H,0,3)
(3, [0, 1, 2, 3])
>>> NX.bidirectional_dijkstra(H,0,4)
(3, [0, 6, 5, 4])
>>> NX.bidirectional_dijkstra(XG3,0,3)
(15, [0, 1, 2, 3])
>>> NX.bidirectional_dijkstra(XG4,0,2)
(4, [0, 1, 2])

# need more tests here
>>> NX.dijkstra_path(XG,'s','v')==NX.single_source_dijkstra_path(XG,'s')['v']
True

Floyd-Warshall all pair shortest path
-------------------------------------

>>> dist, path = NX.floyd_warshall(XG)
>>> dist['s']['v']
9
>>> path['s']['v']
'u'

>>> dist
{'y': {'y': 0, 'x': 12, 's': 7, 'u': 15, 'v': 6}, 'x': {'y': 2, 'x': 0, 's': 9, 'u': 3, 'v': 4}, 's': {'y': 7, 'x': 5, 's': 0, 'u': 8, 'v': 9}, 'u': {'y': 2, 'x': 2, 's': 9, 'u': 0, 'v': 1}, 'v': {'y': 1, 'x': 13, 's': 8, 'u': 16, 'v': 0}}

>>> dist, path = NX.floyd_warshall(GG)
>>> dist['s']['v']
8
>>> path['s']['v']
'y'
>>> dist, path = NX.floyd_warshall(G)
>>> dist['s']['v']
2
>>> path['s']['v']
'x'


>>> dist, path = NX.floyd_warshall(H)
>>> dist[0][3]
3
>>> path[0][3]
2

>>> dist[0][4]
3

>>> XG3=NX.XGraph()
>>> XG3.add_edges_from([ [0,1,2],[1,2,12],[2,3,1],[3,4,5],[4,5,1],[5,0,10] ])
>>> dist, path = NX.floyd_warshall(XG3)
>>> dist[0][3]
15
>>> path[0][3]
2

>>> XG4=NX.XGraph()
>>> XG4.add_edges_from([ [0,1,2],[1,2,2],[2,3,1],[3,4,1],[4,5,1],[5,6,1],[6,7,1],[7,0,1] ])
>>> dist, path = NX.floyd_warshall(XG4)
>>> dist[0][2]
4
>>> path[0][2]
1



Predecessor
-----------

>>> G=NX.path_graph(4)
>>> NX.predecessor(G,0)
{0: [], 1: [0], 2: [1], 3: [2]}
>>> NX.predecessor(G,0,3)
[2]
>>> G=NX.grid_2d_graph(2,2)
>>> sorted(NX.predecessor(G,(0,0)).items())
[((0, 0), []), ((0, 1), [(0, 0)]), ((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])]

BFS
---

Smoke test

>>> G=NX.path_graph(5)
>>> NX.bfs(G,0)
[0, 1, 2, 3, 4]
>>> NX.bfs(G,4)
[4, 3, 2, 1, 0]


DFS
---

Smoke test

>>> G=NX.path_graph(5)
>>> NX.dfs(G,0)
[0, 1, 2, 3, 4]
>>> NX.dfs(G,4)
[4, 3, 2, 1, 0]