/usr/lib/python2.7/dist-packages/networkx/algorithms/connectivity/tests/test_connectivity.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 139 140 141 142 143 144 145 | from nose.tools import assert_equal, assert_true, assert_false
import networkx as nx
# helper functions for tests
def _generate_no_biconnected(max_attempts=50):
attempts = 0
while True:
G = nx.fast_gnp_random_graph(100,0.0575)
if nx.is_connected(G) and not nx.is_biconnected(G):
attempts = 0
yield G
else:
if attempts >= max_attempts:
msg = "Tried %d times: no suitable Graph."
raise Exception(msg % max_attempts)
else:
attempts += 1
def is_dominating_set(G, nbunch):
# Proposed by Dan on the mailing list
allnodes=set(G)
testset=set(n for n in nbunch if n in G)
nbrs=set()
for n in testset:
nbrs.update(G[n])
if nbrs - allnodes: # some nodes left--not dominating
return False
else:
return True
# Tests for node and edge connectivity
def test_average_connectivity():
# figure 1 from:
# Beineke, L., O. Oellermann, and R. Pippert (2002). The average
# connectivity of a graph. Discrete mathematics 252(1-3), 31-45
# http://www.sciencedirect.com/science/article/pii/S0012365X01001807
G1 = nx.path_graph(3)
G1.add_edges_from([(1,3),(1,4)])
assert_equal(nx.average_node_connectivity(G1),1)
G2 = nx.path_graph(3)
G2.add_edges_from([(1,3),(1,4),(0,3),(0,4),(3,4)])
assert_equal(nx.average_node_connectivity(G2),2.2)
G3 = nx.Graph()
assert_equal(nx.average_node_connectivity(G3),0)
def test_articulation_points():
Ggen = _generate_no_biconnected()
for i in range(5):
G = next(Ggen)
assert_equal(nx.node_connectivity(G), 1)
def test_brandes_erlebach():
# Figure 1 chapter 7: Connectivity
# http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
G = nx.Graph()
G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(2,3),(2,6),(3,4),
(3,6),(4,6),(4,7),(5,7),(6,8),(6,9),(7,8),
(7,10),(8,11),(9,10),(9,11),(10,11)])
assert_equal(3,nx.local_edge_connectivity(G,1,11))
assert_equal(3,nx.edge_connectivity(G,1,11))
assert_equal(2,nx.local_node_connectivity(G,1,11))
assert_equal(2,nx.node_connectivity(G,1,11))
assert_equal(2,nx.edge_connectivity(G)) # node 5 has degree 2
assert_equal(2,nx.node_connectivity(G))
def test_white_harary_1():
# Figure 1b white and harary (2001)
# # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
# A graph with high adhesion (edge connectivity) and low cohesion
# (vertex connectivity)
G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
G.remove_node(7)
for i in range(4,7):
G.add_edge(0,i)
G = nx.disjoint_union(G, nx.complete_graph(4))
G.remove_node(G.order()-1)
for i in range(7,10):
G.add_edge(0,i)
assert_equal(1, nx.node_connectivity(G))
assert_equal(3, nx.edge_connectivity(G))
def test_white_harary_2():
# Figure 8 white and harary (2001)
# # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
G.add_edge(0,4)
# kappa <= lambda <= delta
assert_equal(3, min(nx.core_number(G).values()))
assert_equal(1, nx.node_connectivity(G))
assert_equal(1, nx.edge_connectivity(G))
def test_complete_graphs():
for n in range(5, 25, 5):
G = nx.complete_graph(n)
assert_equal(n-1, nx.node_connectivity(G))
assert_equal(n-1, nx.node_connectivity(G.to_directed()))
assert_equal(n-1, nx.edge_connectivity(G))
assert_equal(n-1, nx.edge_connectivity(G.to_directed()))
def test_empty_graphs():
for k in range(5, 25, 5):
G = nx.empty_graph(k)
assert_equal(0, nx.node_connectivity(G))
assert_equal(0, nx.edge_connectivity(G))
def test_petersen():
G = nx.petersen_graph()
assert_equal(3, nx.node_connectivity(G))
assert_equal(3, nx.edge_connectivity(G))
def test_tutte():
G = nx.tutte_graph()
assert_equal(3, nx.node_connectivity(G))
assert_equal(3, nx.edge_connectivity(G))
def test_dodecahedral():
G = nx.dodecahedral_graph()
assert_equal(3, nx.node_connectivity(G))
assert_equal(3, nx.edge_connectivity(G))
def test_octahedral():
G=nx.octahedral_graph()
assert_equal(4, nx.node_connectivity(G))
assert_equal(4, nx.edge_connectivity(G))
def test_icosahedral():
G=nx.icosahedral_graph()
assert_equal(5, nx.node_connectivity(G))
assert_equal(5, nx.edge_connectivity(G))
def test_directed_edge_connectivity():
G = nx.cycle_graph(10,create_using=nx.DiGraph()) # only one direction
D = nx.cycle_graph(10).to_directed() # 2 reciprocal edges
assert_equal(1, nx.edge_connectivity(G))
assert_equal(1, nx.local_edge_connectivity(G,1,4))
assert_equal(1, nx.edge_connectivity(G,1,4))
assert_equal(2, nx.edge_connectivity(D))
assert_equal(2, nx.local_edge_connectivity(D,1,4))
assert_equal(2, nx.edge_connectivity(D,1,4))
def test_dominating_set():
for i in range(5):
G = nx.gnp_random_graph(100,0.1)
D = nx.dominating_set(G)
assert_true(is_dominating_set(G,D))
|