/usr/lib/python3/dist-packages/networkx/algorithms/shortest_paths/tests/test_unweighted.py is in python3-networkx 1.11-1ubuntu2.
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 | #!/usr/bin/env python
from nose.tools import *
import networkx as nx
def validate_grid_path(r, c, s, t, p):
ok_(isinstance(p, list))
assert_equal(p[0], s)
assert_equal(p[-1], t)
s = ((s - 1) // c, (s - 1) % c)
t = ((t - 1) // c, (t - 1) % c)
assert_equal(len(p), abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1)
p = [((u - 1) // c, (u - 1) % c) for u in p]
for u in p:
ok_(0 <= u[0] < r)
ok_(0 <= u[1] < c)
for u, v in zip(p[:-1], p[1:]):
ok_((abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)])
class TestUnweightedPath:
def setUp(self):
from networkx import convert_node_labels_to_integers as cnlti
self.grid=cnlti(nx.grid_2d_graph(4,4),first_label=1,ordering="sorted")
self.cycle=nx.cycle_graph(7)
self.directed_cycle=nx.cycle_graph(7,create_using=nx.DiGraph())
def test_bidirectional_shortest_path(self):
assert_equal(nx.bidirectional_shortest_path(self.cycle,0,3),
[0, 1, 2, 3])
assert_equal(nx.bidirectional_shortest_path(self.cycle,0,4),
[0, 6, 5, 4])
validate_grid_path(4, 4, 1, 12, nx.bidirectional_shortest_path(self.grid,1,12))
assert_equal(nx.bidirectional_shortest_path(self.directed_cycle,0,3),
[0, 1, 2, 3])
def test_shortest_path_length(self):
assert_equal(nx.shortest_path_length(self.cycle,0,3),3)
assert_equal(nx.shortest_path_length(self.grid,1,12),5)
assert_equal(nx.shortest_path_length(self.directed_cycle,0,4),4)
# now with weights
assert_equal(nx.shortest_path_length(self.cycle,0,3,weight=True),3)
assert_equal(nx.shortest_path_length(self.grid,1,12,weight=True),5)
assert_equal(nx.shortest_path_length(self.directed_cycle,0,4,weight=True),4)
def test_single_source_shortest_path(self):
p=nx.single_source_shortest_path(self.cycle,0)
assert_equal(p[3],[0,1,2,3])
p=nx.single_source_shortest_path(self.cycle,0, cutoff=0)
assert_equal(p,{0 : [0]})
def test_single_source_shortest_path_length(self):
assert_equal(nx.single_source_shortest_path_length(self.cycle,0),
{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
def test_all_pairs_shortest_path(self):
p=nx.all_pairs_shortest_path(self.cycle)
assert_equal(p[0][3],[0,1,2,3])
p=nx.all_pairs_shortest_path(self.grid)
validate_grid_path(4, 4, 1, 12, p[1][12])
def test_all_pairs_shortest_path_length(self):
l=nx.all_pairs_shortest_path_length(self.cycle)
assert_equal(l[0],{0:0,1:1,2:2,3:3,4:3,5:2,6:1})
l=nx.all_pairs_shortest_path_length(self.grid)
assert_equal(l[1][16],6)
def test_predecessor(self):
G=nx.path_graph(4)
assert_equal(nx.predecessor(G,0),{0: [], 1: [0], 2: [1], 3: [2]})
assert_equal(nx.predecessor(G,0,3),[2])
G=nx.grid_2d_graph(2,2)
assert_equal(sorted(nx.predecessor(G,(0,0)).items()),
[((0, 0), []), ((0, 1), [(0, 0)]),
((1, 0), [(0, 0)]), ((1, 1), [(0, 1), (1, 0)])])
def test_predecessor_cutoff(self):
G=nx.path_graph(4)
p = nx.predecessor(G,0,3)
assert_false(4 in p)
def test_predecessor_target(self):
G=nx.path_graph(4)
p = nx.predecessor(G,0,3)
assert_equal(p,[2])
p = nx.predecessor(G,0,3,cutoff=2)
assert_equal(p,[])
p,s = nx.predecessor(G,0,3,return_seen=True)
assert_equal(p,[2])
assert_equal(s,3)
p,s = nx.predecessor(G,0,3,cutoff=2,return_seen=True)
assert_equal(p,[])
assert_equal(s,-1)
|