/usr/lib/python2.7/dist-packages/networkx/algorithms/components/tests/test_strongly_connected.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 130 131 132 133 134 135 136 137 138 | #!/usr/bin/env python
from nose.tools import *
import networkx as nx
from networkx import NetworkXError
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):
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])
def test_connected_raise(self):
G=nx.Graph()
assert_raises(NetworkXError,nx.strongly_connected_components,G)
assert_raises(NetworkXError,nx.kosaraju_strongly_connected_components,G)
assert_raises(NetworkXError,nx.strongly_connected_components_recursive,G)
assert_raises(NetworkXError,nx.strongly_connected_component_subgraphs,G)
assert_raises(NetworkXError,nx.is_strongly_connected,G)
assert_raises(NetworkXError,nx.condensation,G)
|