Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / shortest_paths / tests / test_unweighted.py @ 5cef0f13

History | View | Annotate | Download (4.74 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4

    
5

    
6
def validate_grid_path(r, c, s, t, p):
7
    ok_(isinstance(p, list))
8
    assert_equal(p[0], s)
9
    assert_equal(p[-1], t)
10
    s = ((s - 1) // c, (s - 1) % c)
11
    t = ((t - 1) // c, (t - 1) % c)
12
    assert_equal(len(p), abs(t[0] - s[0]) + abs(t[1] - s[1]) + 1)
13
    p = [((u - 1) // c, (u - 1) % c) for u in p]
14
    for u in p:
15
        ok_(0 <= u[0] < r)
16
        ok_(0 <= u[1] < c)
17
    for u, v in zip(p[:-1], p[1:]):
18
        ok_((abs(v[0] - u[0]), abs(v[1] - u[1])) in [(0, 1), (1, 0)])
19

    
20

    
21
class TestUnweightedPath:
22

    
23
    def setUp(self):
24
        from networkx import convert_node_labels_to_integers as cnlti
25
        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1, ordering="sorted")
26
        self.cycle = nx.cycle_graph(7)
27
        self.directed_cycle = nx.cycle_graph(7, create_using=nx.DiGraph())
28

    
29
    def test_bidirectional_shortest_path(self):
30
        assert_equal(nx.bidirectional_shortest_path(self.cycle, 0, 3),
31
                     [0, 1, 2, 3])
32
        assert_equal(nx.bidirectional_shortest_path(self.cycle, 0, 4),
33
                     [0, 6, 5, 4])
34
        validate_grid_path(4, 4, 1, 12, nx.bidirectional_shortest_path(self.grid, 1, 12))
35
        assert_equal(nx.bidirectional_shortest_path(self.directed_cycle, 0, 3),
36
                     [0, 1, 2, 3])
37

    
38
    def test_shortest_path_length(self):
39
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3), 3)
40
        assert_equal(nx.shortest_path_length(self.grid, 1, 12), 5)
41
        assert_equal(nx.shortest_path_length(self.directed_cycle, 0, 4), 4)
42
        # now with weights
43
        assert_equal(nx.shortest_path_length(self.cycle, 0, 3, weight=True), 3)
44
        assert_equal(nx.shortest_path_length(self.grid, 1, 12, weight=True), 5)
45
        assert_equal(nx.shortest_path_length(self.directed_cycle, 0, 4, weight=True), 4)
46

    
47
    def test_single_source_shortest_path(self):
48
        p = nx.single_source_shortest_path(self.directed_cycle, 3)
49
        assert_equal(p[0], [3, 4, 5, 6, 0])
50
        p = nx.single_source_shortest_path(self.cycle, 0)
51
        assert_equal(p[3], [0, 1, 2, 3])
52
        p = nx.single_source_shortest_path(self.cycle, 0, cutoff=0)
53
        assert_equal(p, {0: [0]})
54

    
55
    def test_single_source_shortest_path_length(self):
56
        pl = nx.single_source_shortest_path_length
57
        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
58
        assert_equal(dict(pl(self.cycle, 0)), lengths)
59
        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
60
        assert_equal(dict(pl(self.directed_cycle, 0)), lengths)
61

    
62
    def test_single_target_shortest_path(self):
63
        p = nx.single_target_shortest_path(self.directed_cycle, 0)
64
        assert_equal(p[3], [3, 4, 5, 6, 0])
65
        p = nx.single_target_shortest_path(self.cycle, 0)
66
        assert_equal(p[3], [3, 2, 1, 0])
67
        p = nx.single_target_shortest_path(self.cycle, 0, cutoff=0)
68
        assert_equal(p, {0: [0]})
69

    
70
    def test_single_target_shortest_path_length(self):
71
        pl = nx.single_target_shortest_path_length
72
        lengths = {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1}
73
        assert_equal(dict(pl(self.cycle, 0)), lengths)
74
        lengths = {0: 0, 1: 6, 2: 5, 3: 4, 4: 3, 5: 2, 6: 1}
75
        assert_equal(dict(pl(self.directed_cycle, 0)), lengths)
76

    
77
    def test_all_pairs_shortest_path(self):
78
        p = dict(nx.all_pairs_shortest_path(self.cycle))
79
        assert_equal(p[0][3], [0, 1, 2, 3])
80
        p = dict(nx.all_pairs_shortest_path(self.grid))
81
        validate_grid_path(4, 4, 1, 12, p[1][12])
82

    
83
    def test_all_pairs_shortest_path_length(self):
84
        l = dict(nx.all_pairs_shortest_path_length(self.cycle))
85
        assert_equal(l[0], {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
86
        l = dict(nx.all_pairs_shortest_path_length(self.grid))
87
        assert_equal(l[1][16], 6)
88

    
89
    def test_predecessor_path(self):
90
        G = nx.path_graph(4)
91
        assert_equal(nx.predecessor(G, 0), {0: [], 1: [0], 2: [1], 3: [2]})
92
        assert_equal(nx.predecessor(G, 0, 3), [2])
93

    
94
    def test_predecessor_cycle(self):
95
        G = nx.cycle_graph(4)
96
        pred = nx.predecessor(G, 0)
97
        assert_equal(pred[0], [])
98
        assert_equal(pred[1], [0])
99
        assert_true(pred[2] in [[1, 3], [3, 1]])
100
        assert_equal(pred[3], [0])
101

    
102
    def test_predecessor_cutoff(self):
103
        G = nx.path_graph(4)
104
        p = nx.predecessor(G, 0, 3)
105
        assert_false(4 in p)
106

    
107
    def test_predecessor_target(self):
108
        G = nx.path_graph(4)
109
        p = nx.predecessor(G, 0, 3)
110
        assert_equal(p, [2])
111
        p = nx.predecessor(G, 0, 3, cutoff=2)
112
        assert_equal(p, [])
113
        p, s = nx.predecessor(G, 0, 3, return_seen=True)
114
        assert_equal(p, [2])
115
        assert_equal(s, 3)
116
        p, s = nx.predecessor(G, 0, 3, cutoff=2, return_seen=True)
117
        assert_equal(p, [])
118
        assert_equal(s, -1)