Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.53 KB)

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

    
5

    
6
class TestFloyd:
7
    def setUp(self):
8
        pass
9

    
10
    def test_floyd_warshall_predecessor_and_distance(self):
11
        XG = nx.DiGraph()
12
        XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
13
                                    ('u', 'v', 1), ('u', 'x', 2),
14
                                    ('v', 'y', 1), ('x', 'u', 3),
15
                                    ('x', 'v', 5), ('x', 'y', 2),
16
                                    ('y', 's', 7), ('y', 'v', 6)])
17
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG)
18
        assert_equal(dist['s']['v'], 9)
19
        assert_equal(path['s']['v'], 'u')
20
        assert_equal(dist,
21
                     {'y': {'y': 0, 'x': 12, 's': 7, 'u': 15, 'v': 6},
22
                      'x': {'y': 2, 'x': 0, 's': 9, 'u': 3, 'v': 4},
23
                      's': {'y': 7, 'x': 5, 's': 0, 'u': 8, 'v': 9},
24
                      'u': {'y': 2, 'x': 2, 's': 9, 'u': 0, 'v': 1},
25
                      'v': {'y': 1, 'x': 13, 's': 8, 'u': 16, 'v': 0}})
26

    
27
        GG = XG.to_undirected()
28
        # make sure we get lower weight
29
        # to_undirected might choose either edge with weight 2 or weight 3
30
        GG['u']['x']['weight'] = 2
31
        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
32
        assert_equal(dist['s']['v'], 8)
33
        # skip this test, could be alternate path s-u-v
34
#        assert_equal(path['s']['v'],'y')
35

    
36
        G = nx.DiGraph()  # no weights
37
        G.add_edges_from([('s', 'u'), ('s', 'x'),
38
                          ('u', 'v'), ('u', 'x'),
39
                          ('v', 'y'), ('x', 'u'),
40
                          ('x', 'v'), ('x', 'y'),
41
                          ('y', 's'), ('y', 'v')])
42
        path, dist = nx.floyd_warshall_predecessor_and_distance(G)
43
        assert_equal(dist['s']['v'], 2)
44
        # skip this test, could be alternate path s-u-v
45
 #       assert_equal(path['s']['v'],'x')
46

    
47
        # alternate interface
48
        dist = nx.floyd_warshall(G)
49
        assert_equal(dist['s']['v'], 2)
50

    
51
    @raises(KeyError)
52
    def test_reconstruct_path(self):
53
        XG = nx.DiGraph()
54
        XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
55
                                    ('u', 'v', 1), ('u', 'x', 2),
56
                                    ('v', 'y', 1), ('x', 'u', 3),
57
                                    ('x', 'v', 5), ('x', 'y', 2),
58
                                    ('y', 's', 7), ('y', 'v', 6)])
59
        predecessors, _ = nx.floyd_warshall_predecessor_and_distance(XG)
60

    
61
        path = nx.reconstruct_path('s', 'v', predecessors)
62
        assert_equal(path, ['s', 'x', 'u', 'v'])
63

    
64
        path = nx.reconstruct_path('s', 's', predecessors)
65
        assert_equal(path, [])
66

    
67
        # this part raises the keyError
68
        nx.reconstruct_path('1', '2', predecessors)
69

    
70
    def test_cycle(self):
71
        path, dist = nx.floyd_warshall_predecessor_and_distance(
72
            nx.cycle_graph(7))
73
        assert_equal(dist[0][3], 3)
74
        assert_equal(path[0][3], 2)
75
        assert_equal(dist[0][4], 3)
76

    
77
    def test_weighted(self):
78
        XG3 = nx.Graph()
79
        XG3.add_weighted_edges_from([[0, 1, 2], [1, 2, 12], [2, 3, 1],
80
                                     [3, 4, 5], [4, 5, 1], [5, 0, 10]])
81
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG3)
82
        assert_equal(dist[0][3], 15)
83
        assert_equal(path[0][3], 2)
84

    
85
    def test_weighted2(self):
86
        XG4 = nx.Graph()
87
        XG4.add_weighted_edges_from([[0, 1, 2], [1, 2, 2], [2, 3, 1],
88
                                     [3, 4, 1], [4, 5, 1], [5, 6, 1],
89
                                     [6, 7, 1], [7, 0, 1]])
90
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4)
91
        assert_equal(dist[0][2], 4)
92
        assert_equal(path[0][2], 1)
93

    
94
    def test_weight_parameter(self):
95
        XG4 = nx.Graph()
96
        XG4.add_edges_from([(0, 1, {'heavy': 2}), (1, 2, {'heavy': 2}),
97
                            (2, 3, {'heavy': 1}), (3, 4, {'heavy': 1}),
98
                            (4, 5, {'heavy': 1}), (5, 6, {'heavy': 1}),
99
                            (6, 7, {'heavy': 1}), (7, 0, {'heavy': 1})])
100
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG4,
101
                                                                weight='heavy')
102
        assert_equal(dist[0][2], 4)
103
        assert_equal(path[0][2], 1)
104

    
105
    def test_zero_distance(self):
106
        XG = nx.DiGraph()
107
        XG.add_weighted_edges_from([('s', 'u', 10), ('s', 'x', 5),
108
                                    ('u', 'v', 1), ('u', 'x', 2),
109
                                    ('v', 'y', 1), ('x', 'u', 3),
110
                                    ('x', 'v', 5), ('x', 'y', 2),
111
                                    ('y', 's', 7), ('y', 'v', 6)])
112
        path, dist = nx.floyd_warshall_predecessor_and_distance(XG)
113

    
114
        for u in XG:
115
            assert_equal(dist[u][u], 0)
116

    
117
        GG = XG.to_undirected()
118
        # make sure we get lower weight
119
        # to_undirected might choose either edge with weight 2 or weight 3
120
        GG['u']['x']['weight'] = 2
121
        path, dist = nx.floyd_warshall_predecessor_and_distance(GG)
122

    
123
        for u in GG:
124
            dist[u][u] = 0
125

    
126
    def test_zero_weight(self):
127
        G = nx.DiGraph()
128
        edges = [(1, 2, -2), (2, 3, -4), (1, 5, 1),
129
                 (5, 4, 0), (4, 3, -5), (2, 5, -7)]
130
        G.add_weighted_edges_from(edges)
131
        dist = nx.floyd_warshall(G)
132
        assert_equal(dist[1][3], -14)
133

    
134
        G = nx.MultiDiGraph()
135
        edges.append((2, 5, -7))
136
        G.add_weighted_edges_from(edges)
137
        dist = nx.floyd_warshall(G)
138
        assert_equal(dist[1][3], -14)