/usr/lib/python2.7/dist-packages/networkx/algorithms/shortest_paths/tests/test_dense.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #!/usr/bin/env python
from nose.tools import *
from nose import SkipTest
import networkx as nx
class TestFloyd:
def setUp(self):
pass
def test_floyd_warshall_predecessor_and_distance(self):
XG=nx.DiGraph()
XG.add_weighted_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)])
path, dist =nx.floyd_warshall_predecessor_and_distance(XG)
assert_equal(dist['s']['v'],9)
assert_equal(path['s']['v'],'u')
assert_equal(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}})
GG=XG.to_undirected()
# make sure we get lower weight
# to_undirected might choose either edge with weight 2 or weight 3
GG['u']['x']['weight']=2
path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
assert_equal(dist['s']['v'],8)
# skip this test, could be alternate path s-u-v
# assert_equal(path['s']['v'],'y')
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')])
path, dist = nx.floyd_warshall_predecessor_and_distance(G)
assert_equal(dist['s']['v'],2)
# skip this test, could be alternate path s-u-v
# assert_equal(path['s']['v'],'x')
# alternate interface
dist = nx.floyd_warshall(G)
assert_equal(dist['s']['v'],2)
def test_cycle(self):
path, dist = nx.floyd_warshall_predecessor_and_distance(nx.cycle_graph(7))
assert_equal(dist[0][3],3)
assert_equal(path[0][3],2)
assert_equal(dist[0][4],3)
def test_weighted(self):
XG3=nx.Graph()
XG3.add_weighted_edges_from([ [0,1,2],[1,2,12],[2,3,1],
[3,4,5],[4,5,1],[5,0,10] ])
path, dist = nx.floyd_warshall_predecessor_and_distance(XG3)
assert_equal(dist[0][3],15)
assert_equal(path[0][3],2)
def test_weighted2(self):
XG4=nx.Graph()
XG4.add_weighted_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] ])
path, dist = nx.floyd_warshall_predecessor_and_distance(XG4)
assert_equal(dist[0][2],4)
assert_equal(path[0][2],1)
def test_weight_parameter(self):
XG4 = nx.Graph()
XG4.add_edges_from([ (0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}),
(2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}),
(4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}),
(6, 7, {'heavy': 1}), (7, 0, {'heavy': 1}) ])
path, dist = nx.floyd_warshall_predecessor_and_distance(XG4,
weight='heavy')
assert_equal(dist[0][2], 4)
assert_equal(path[0][2], 1)
def test_zero_distance(self):
XG=nx.DiGraph()
XG.add_weighted_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)])
path, dist =nx.floyd_warshall_predecessor_and_distance(XG)
for u in XG:
assert_equal(dist[u][u], 0)
GG=XG.to_undirected()
# make sure we get lower weight
# to_undirected might choose either edge with weight 2 or weight 3
GG['u']['x']['weight']=2
path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
for u in GG:
dist[u][u] = 0
|