Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / components / tests / test_strongly_connected.py @ 5cef0f13

History | View | Annotate | Download (6.55 KB)

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

    
7

    
8
class TestStronglyConnected:
9

    
10
    def setUp(self):
11
        self.gc = []
12
        G = nx.DiGraph()
13
        G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5),
14
                          (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)])
15
        C = {frozenset([3, 4, 5, 7]), frozenset([1, 2, 8]), frozenset([6])}
16
        self.gc.append((G, C))
17

    
18
        G = nx.DiGraph()
19
        G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)])
20
        C = {frozenset([2, 3, 4]), frozenset([1])}
21
        self.gc.append((G, C))
22

    
23
        G = nx.DiGraph()
24
        G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)])
25
        C = {frozenset([1, 2, 3])}
26
        self.gc.append((G, C))
27

    
28
        # Eppstein's tests
29
        G = nx.DiGraph({0: [1], 1: [2, 3], 2: [4, 5], 3: [4, 5], 4: [6], 5: [], 6: []})
30
        C = {
31
            frozenset([0]),
32
            frozenset([1]),
33
            frozenset([2]),
34
            frozenset([3]),
35
            frozenset([4]),
36
            frozenset([5]),
37
            frozenset([6]),
38
        }
39
        self.gc.append((G, C))
40

    
41
        G = nx.DiGraph({0: [1], 1: [2, 3, 4], 2: [0, 3], 3: [4], 4: [3]})
42
        C = {frozenset([0, 1, 2]), frozenset([3, 4])}
43
        self.gc.append((G, C))
44

    
45
    def test_tarjan(self):
46
        scc = nx.strongly_connected_components
47
        for G, C in self.gc:
48
            assert_equal({frozenset(g) for g in scc(G)}, C)
49

    
50
    def test_tarjan_recursive(self):
51
        scc = nx.strongly_connected_components_recursive
52
        for G, C in self.gc:
53
            assert_equal({frozenset(g) for g in scc(G)}, C)
54

    
55
    def test_kosaraju(self):
56
        scc = nx.kosaraju_strongly_connected_components
57
        for G, C in self.gc:
58
            assert_equal({frozenset(g) for g in scc(G)}, C)
59

    
60
    def test_number_strongly_connected_components(self):
61
        ncc = nx.number_strongly_connected_components
62
        for G, C in self.gc:
63
            assert_equal(ncc(G), len(C))
64

    
65
    def test_is_strongly_connected(self):
66
        for G, C in self.gc:
67
            if len(C) == 1:
68
                assert_true(nx.is_strongly_connected(G))
69
            else:
70
                assert_false(nx.is_strongly_connected(G))
71

    
72
    # deprecated
73
    def test_strongly_connected_component_subgraphs(self):
74
        scc = nx.strongly_connected_component_subgraphs
75
        for G, C in self.gc:
76
            assert_equal({frozenset(g) for g in scc(G)}, C)
77

    
78
    def test_contract_scc1(self):
79
        G = nx.DiGraph()
80
        G.add_edges_from([
81
            (1, 2), (2, 3), (2, 11), (2, 12), (3, 4), (4, 3), (4, 5), (5, 6),
82
            (6, 5), (6, 7), (7, 8), (7, 9), (7, 10), (8, 9), (9, 7), (10, 6),
83
            (11, 2), (11, 4), (11, 6), (12, 6), (12, 11),
84
        ])
85
        scc = list(nx.strongly_connected_components(G))
86
        cG = nx.condensation(G, scc)
87
        # DAG
88
        assert_true(nx.is_directed_acyclic_graph(cG))
89
        # nodes
90
        assert_equal(sorted(cG.nodes()), [0, 1, 2, 3])
91
        # edges
92
        mapping = {}
93
        for i, component in enumerate(scc):
94
            for n in component:
95
                mapping[n] = i
96
        edge = (mapping[2], mapping[3])
97
        assert_true(cG.has_edge(*edge))
98
        edge = (mapping[2], mapping[5])
99
        assert_true(cG.has_edge(*edge))
100
        edge = (mapping[3], mapping[5])
101
        assert_true(cG.has_edge(*edge))
102

    
103
    def test_contract_scc_isolate(self):
104
        # Bug found and fixed in [1687].
105
        G = nx.DiGraph()
106
        G.add_edge(1, 2)
107
        G.add_edge(2, 1)
108
        scc = list(nx.strongly_connected_components(G))
109
        cG = nx.condensation(G, scc)
110
        assert_equal(list(cG.nodes()), [0])
111
        assert_equal(list(cG.edges()), [])
112

    
113
    def test_contract_scc_edge(self):
114
        G = nx.DiGraph()
115
        G.add_edge(1, 2)
116
        G.add_edge(2, 1)
117
        G.add_edge(2, 3)
118
        G.add_edge(3, 4)
119
        G.add_edge(4, 3)
120
        scc = list(nx.strongly_connected_components(G))
121
        cG = nx.condensation(G, scc)
122
        assert_equal(sorted(cG.nodes()), [0, 1])
123
        if 1 in scc[0]:
124
            edge = (0, 1)
125
        else:
126
            edge = (1, 0)
127
        assert_equal(list(cG.edges()), [edge])
128

    
129
    def test_condensation_mapping_and_members(self):
130
        G, C = self.gc[1]
131
        C = sorted(C, key=len, reverse=True)
132
        cG = nx.condensation(G)
133
        mapping = cG.graph['mapping']
134
        assert_true(all(n in G for n in mapping))
135
        assert_true(all(0 == cN for n, cN in mapping.items() if n in C[0]))
136
        assert_true(all(1 == cN for n, cN in mapping.items() if n in C[1]))
137
        for n, d in cG.nodes(data=True):
138
            assert_equal(set(C[n]), cG.nodes[n]['members'])
139

    
140
    def test_null_graph(self):
141
        G = nx.DiGraph()
142
        assert_equal(list(nx.strongly_connected_components(G)), [])
143
        assert_equal(list(nx.kosaraju_strongly_connected_components(G)), [])
144
        assert_equal(list(nx.strongly_connected_components_recursive(G)), [])
145
        assert_equal(len(nx.condensation(G)), 0)
146
        assert_raises(nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph())
147

    
148
    def test_connected_raise(self):
149
        G = nx.Graph()
150
        assert_raises(NetworkXNotImplemented, nx.strongly_connected_components, G)
151
        assert_raises(NetworkXNotImplemented, nx.kosaraju_strongly_connected_components, G)
152
        assert_raises(NetworkXNotImplemented, nx.strongly_connected_components_recursive, G)
153
        assert_raises(NetworkXNotImplemented, nx.is_strongly_connected, G)
154
        assert_raises(nx.NetworkXPointlessConcept, nx.is_strongly_connected, nx.DiGraph())
155
        assert_raises(NetworkXNotImplemented, nx.condensation, G)
156
        # deprecated
157
        assert_raises(NetworkXNotImplemented, nx.strongly_connected_component_subgraphs, G)
158

    
159
#    Commented out due to variability on Travis-CI hardware/operating systems
160
#    def test_linear_time(self):
161
#        # See Issue #2831
162
#        count = 100  # base case
163
#        dg = nx.DiGraph()
164
#        dg.add_nodes_from([0, 1])
165
#        for i in range(2, count):
166
#            dg.add_node(i)
167
#            dg.add_edge(i, 1)
168
#            dg.add_edge(0, i)
169
#        t = time.time()
170
#        ret = tuple(nx.strongly_connected_components(dg))
171
#        dt = time.time() - t
172
#
173
#        count = 200
174
#        dg = nx.DiGraph()
175
#        dg.add_nodes_from([0, 1])
176
#        for i in range(2, count):
177
#            dg.add_node(i)
178
#            dg.add_edge(i, 1)
179
#            dg.add_edge(0, i)
180
#        t = time.time()
181
#        ret = tuple(nx.strongly_connected_components(dg))
182
#        dt2 = time.time() - t
183
#        assert_less(dt2, dt * 2.3)  # should be 2 times longer for this graph