1 #!/usr/bin/env python 2 from nose.tools import * 3 import networkx as nx 4 from networkx import NetworkXError 5 6 class TestStronglyConnected: 7 8 def setUp(self): 9 self.gc=[] 10 G=nx.DiGraph() 11 G.add_edges_from([(1,2),(2,3),(2,8),(3,4),(3,7), 12 (4,5),(5,3),(5,6),(7,4),(7,6),(8,1),(8,7)]) 13 C=[[3, 4, 5, 7], [1, 2, 8], [6]] 14 self.gc.append((G,C)) 15 16 G= nx.DiGraph() 17 G.add_edges_from([(1,2),(1,3),(1,4),(4,2),(3,4),(2,3)]) 18 C = [[2, 3, 4],[1]] 19 self.gc.append((G,C)) 20 21 G = nx.DiGraph() 22 G.add_edges_from([(1,2),(2,3),(3,2),(2,1)]) 23 C = [[1, 2, 3]] 24 self.gc.append((G,C)) 25 26 # Eppstein's tests 27 G = nx.DiGraph({ 0:[1],1:[2,3],2:[4,5],3:[4,5],4:[6],5:[],6:[]}) 28 C = [[0],[1],[2],[3],[4],[5],[6]] 29 self.gc.append((G,C)) 30 31 G = nx.DiGraph({0:[1],1:[2,3,4],2:[0,3],3:[4],4:[3]}) 32 C = [[0,1,2],[3,4]] 33 self.gc.append((G,C)) 34 35 36 def test_tarjan(self): 37 scc=nx.strongly_connected_components 38 for G,C in self.gc: 39 assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) 40 41 42 def test_tarjan_recursive(self): 43 scc=nx.strongly_connected_components_recursive 44 for G,C in self.gc: 45 assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) 46 47 48 def test_kosaraju(self): 49 scc=nx.kosaraju_strongly_connected_components 50 for G,C in self.gc: 51 assert_equal(sorted([sorted(g) for g in scc(G)]),sorted(C)) 52 53 def test_number_strongly_connected_components(self): 54 ncc=nx.number_strongly_connected_components 55 for G,C in self.gc: 56 assert_equal(ncc(G),len(C)) 57 58 def test_is_strongly_connected(self): 59 for G,C in self.gc: 60 if len(C)==1: 61 assert_true(nx.is_strongly_connected(G)) 62 else: 63 assert_false(nx.is_strongly_connected(G)) 64 65 66 def test_strongly_connected_component_subgraphs(self): 67 scc=nx.strongly_connected_component_subgraphs 68 for G,C in self.gc: 69 assert_equal(sorted([sorted(g.nodes()) for g in scc(G)]),sorted(C)) 70 G,C=self.gc[0] 71 G.add_edge(1,2,eattr='red') 72 G.node[1]['nattr']='blue' 73 G.graph['gattr']='green' 74 sgs=scc(G)[1] 75 assert_equal(sgs[1][2]['eattr'],'red') 76 assert_equal(sgs.node[1]['nattr'],'blue') 77 assert_equal(sgs.graph['gattr'],'green') 78 sgs[1][2]['eattr']='blue' 79 assert_equal(G[1][2]['eattr'],'red') 80 assert_equal(sgs[1][2]['eattr'],'blue') 81 82 def test_contract_scc1(self): 83 G = nx.DiGraph() 84 G.add_edges_from([(1,2),(2,3),(2,11),(2,12),(3,4),(4,3),(4,5), 85 (5,6),(6,5),(6,7),(7,8),(7,9),(7,10),(8,9), 86 (9,7),(10,6),(11,2),(11,4),(11,6),(12,6),(12,11)]) 87 scc = nx.strongly_connected_components(G) 88 cG = nx.condensation(G, scc) 89 # DAG 90 assert_true(nx.is_directed_acyclic_graph(cG)) 91 # # nodes 92 assert_equal(sorted(cG.nodes()),[0,1,2,3]) 93 # # edges 94 mapping={} 95 for i,component in enumerate(scc): 96 for n in component: 97 mapping[n] = i 98 edge=(mapping[2],mapping[3]) 99 assert_true(cG.has_edge(*edge)) 100 edge=(mapping[2],mapping[5]) 101 assert_true(cG.has_edge(*edge)) 102 edge=(mapping[3],mapping[5]) 103 assert_true(cG.has_edge(*edge)) 104 105 def test_contract_scc_isolate(self): 106 # Bug found and fixed in [1687]. 107 G = nx.DiGraph() 108 G.add_edge(1,2) 109 G.add_edge(2,1) 110 scc = nx.strongly_connected_components(G) 111 cG = nx.condensation(G, scc) 112 assert_equal(cG.nodes(),[0]) 113 assert_equal(cG.edges(),[]) 114 115 def test_contract_scc_edge(self): 116 G = nx.DiGraph() 117 G.add_edge(1,2) 118 G.add_edge(2,1) 119 G.add_edge(2,3) 120 G.add_edge(3,4) 121 G.add_edge(4,3) 122 scc = nx.strongly_connected_components(G) 123 cG = nx.condensation(G, scc) 124 assert_equal(cG.nodes(),[0,1]) 125 if 1 in scc[0]: 126 edge = (0,1) 127 else: 128 edge = (1,0) 129 assert_equal(cG.edges(),[edge]) 130 131 def test_connected_raise(self): 132 G=nx.Graph() 133 assert_raises(NetworkXError,nx.strongly_connected_components,G) 134 assert_raises(NetworkXError,nx.kosaraju_strongly_connected_components,G) 135 assert_raises(NetworkXError,nx.strongly_connected_components_recursive,G) 136 assert_raises(NetworkXError,nx.strongly_connected_component_subgraphs,G) 137 assert_raises(NetworkXError,nx.is_strongly_connected,G) 138 assert_raises(NetworkXError,nx.condensation,G) 139