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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#!/usr/bin/env python
from nose.tools import *
import networkx as nx
class TestStronglyConnected:
def setUp(self):
self.gc=[]
G=nx.DiGraph()
G.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7),
(4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)])
C=[[3, 4, 5, 7], [1, 2, 8], [6]]
self.gc.append((G,C))
G= nx.DiGraph()
G.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)])
C = [[2, 3, 4],[1]]
self.gc.append((G,C))
G = nx.DiGraph()
G.add_edges_from([(1,2),(2,3),(3,2),(2,1)])
C = [[1, 2, 3]]
self.gc.append((G,C))
# Eppstein's tests
G = nx.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]})
C = [[0],[1],[2],[3],[4],[5],[6]]
self.gc.append((G,C))
G = nx.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]})
C = [[0,1,2],[3,4]]
self.gc.append((G,C))
def test_tarjan(self):
scc=nx.strongly_connected_components
for G,C in self.gc:
assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
def test_tarjan_recursive(self):
scc=nx.strongly_connected_components_recursive
for G,C in self.gc:
assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
def test_kosaraju(self):
scc=nx.kosaraju_strongly_connected_components
for G,C in self.gc:
assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C))
def test_number_strongly_connected_components(self):
ncc=nx.number_strongly_connected_components
for G,C in self.gc:
assert_equal(ncc(G),len(C))
def test_is_strongly_connected(self):
ncc=nx.number_strongly_connected_components
for G,C in self.gc:
if len(C)==1:
assert_true(nx.is_strongly_connected(G))
else:
assert_false(nx.is_strongly_connected(G))
def test_strongly_connected_component_subgraphs(self):
scc=nx.strongly_connected_component_subgraphs
for G,C in self.gc:
assert_equal(sorted([sorted(g.nodes()) for g in scc(G)]),sorted(C))
G,C=self.gc[0]
G.add_edge(1,2,eattr='red')
G.node[1]['nattr']='blue'
G.graph['gattr']='green'
sgs=scc(G)[1]
assert_equal(sgs[1][2]['eattr'],'red')
assert_equal(sgs.node[1]['nattr'],'blue')
assert_equal(sgs.graph['gattr'],'green')
sgs[1][2]['eattr']='blue'
assert_equal(G[1][2]['eattr'],'red')
assert_equal(sgs[1][2]['eattr'],'blue')
def test_contract_scc1(self):
G = nx.DiGraph()
G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5),
(5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9),
(9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)])
scc = nx.strongly_connected_components(G)
cG = nx.condensation(G, scc)
# DAG
assert_true(nx.is_directed_acyclic_graph(cG))
# # nodes
assert_equal(sorted(cG.nodes()),[0,1,2,3])
# # edges
mapping={}
for i,component in enumerate(scc):
for n in component:
mapping[n] = i
edge=(mapping[2],mapping[3])
assert_true(cG.has_edge(*edge))
edge=(mapping[2],mapping[5])
assert_true(cG.has_edge(*edge))
edge=(mapping[3],mapping[5])
assert_true(cG.has_edge(*edge))
def test_contract_scc_isolate(self):
# Bug found and fixed in [1687].
G = nx.DiGraph()
G.add_edge(1,2)
G.add_edge(2,1)
scc = nx.strongly_connected_components(G)
cG = nx.condensation(G, scc)
assert_equal(cG.nodes(),[0])
assert_equal(cG.edges(),[])
def test_contract_scc_edge(self):
G = nx.DiGraph()
G.add_edge(1,2)
G.add_edge(2,1)
G.add_edge(2,3)
G.add_edge(3,4)
G.add_edge(4,3)
scc = nx.strongly_connected_components(G)
cG = nx.condensation(G, scc)
assert_equal(cG.nodes(),[0,1])
if 1 in scc[0]:
edge = (0,1)
else:
edge = (1,0)
assert_equal(cG.edges(),[edge])
|
