/usr/lib/python2.7/dist-packages/networkx/algorithms/tests/test_cycles.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 | #!/usr/bin/env python
from nose.tools import *
import networkx
import networkx as nx
class TestCycles:
def setUp(self):
G=networkx.Graph()
G.add_cycle([0,1,2,3])
G.add_cycle([0,3,4,5])
G.add_cycle([0,1,6,7,8])
G.add_edge(8,9)
self.G=G
def is_cyclic_permutation(self,a,b):
n=len(a)
if len(b)!=n:
return False
l=a+a
return any(l[i:i+n]==b for i in range(2*n-n+1))
def test_cycle_basis(self):
G=self.G
cy=networkx.cycle_basis(G,0)
sort_cy= sorted( sorted(c) for c in cy )
assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
cy=networkx.cycle_basis(G,1)
sort_cy= sorted( sorted(c) for c in cy )
assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
cy=networkx.cycle_basis(G,9)
sort_cy= sorted( sorted(c) for c in cy )
assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5]])
# test disconnected graphs
G.add_cycle(list("ABC"))
cy=networkx.cycle_basis(G,9)
sort_cy= sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])]
assert_equal(sort_cy, [[0,1,2,3],[0,1,6,7,8],[0,3,4,5],['A','B','C']])
@raises(nx.NetworkXNotImplemented)
def test_cycle_basis(self):
G=nx.DiGraph()
cy=networkx.cycle_basis(G,0)
@raises(nx.NetworkXNotImplemented)
def test_cycle_basis(self):
G=nx.MultiGraph()
cy=networkx.cycle_basis(G,0)
def test_simple_cycles(self):
G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
cc=sorted(nx.simple_cycles(G))
ca=[[0], [0, 1, 2], [0, 2], [1, 2], [2]]
for c in cc:
assert_true(any(self.is_cyclic_permutation(c,rc) for rc in ca))
@raises(nx.NetworkXNotImplemented)
def test_simple_cycles_graph(self):
G = nx.Graph()
c = sorted(nx.simple_cycles(G))
def test_unsortable(self):
# TODO What does this test do? das 6/2013
G=nx.DiGraph()
G.add_cycle(['a',1])
c=list(nx.simple_cycles(G))
def test_simple_cycles_small(self):
G = nx.DiGraph()
G.add_cycle([1,2,3])
c=sorted(nx.simple_cycles(G))
assert_equal(len(c),1)
assert_true(self.is_cyclic_permutation(c[0],[1,2,3]))
G.add_cycle([10,20,30])
cc=sorted(nx.simple_cycles(G))
ca=[[1,2,3],[10,20,30]]
for c in cc:
assert_true(any(self.is_cyclic_permutation(c,rc) for rc in ca))
def test_simple_cycles_empty(self):
G = nx.DiGraph()
assert_equal(list(nx.simple_cycles(G)),[])
def test_complete_directed_graph(self):
# see table 2 in Johnson's paper
ncircuits=[1,5,20,84,409,2365,16064]
for n,c in zip(range(2,9),ncircuits):
G=nx.DiGraph(nx.complete_graph(n))
assert_equal(len(list(nx.simple_cycles(G))),c)
def worst_case_graph(self,k):
# see figure 1 in Johnson's paper
# this graph has excactly 3k simple cycles
G=nx.DiGraph()
for n in range(2,k+2):
G.add_edge(1,n)
G.add_edge(n,k+2)
G.add_edge(2*k+1,1)
for n in range(k+2,2*k+2):
G.add_edge(n,2*k+2)
G.add_edge(n,n+1)
G.add_edge(2*k+3,k+2)
for n in range(2*k+3,3*k+3):
G.add_edge(2*k+2,n)
G.add_edge(n,3*k+3)
G.add_edge(3*k+3,2*k+2)
return G
def test_worst_case_graph(self):
# see figure 1 in Johnson's paper
for k in range(3,10):
G=self.worst_case_graph(k)
l=len(list(nx.simple_cycles(G)))
assert_equal(l,3*k)
def test_recursive_simple_and_not(self):
for k in range(2,10):
G=self.worst_case_graph(k)
cc=sorted(nx.simple_cycles(G))
rcc=sorted(nx.recursive_simple_cycles(G))
assert_equal(len(cc),len(rcc))
for c in cc:
assert_true(any(self.is_cyclic_permutation(c,rc) for rc in rcc))
|