from itertools import chain, islice, tee
from math import inf
from random import shuffle
import pytest
import networkx as nx
from networkx.algorithms.traversal.edgedfs import FORWARD, REVERSE
def check_independent(basis):
if len(basis) == 0:
return
np = pytest.importorskip("numpy")
sp = pytest.importorskip("scipy") # Required by incidence_matrix
H = nx.Graph()
for b in basis:
nx.add_cycle(H, b)
inc = nx.incidence_matrix(H, oriented=True)
rank = np.linalg.matrix_rank(inc.toarray(), tol=None, hermitian=False)
assert inc.shape[1] - rank == len(basis)
class TestCycles:
@classmethod
def setup_class(cls):
G = nx.Graph()
nx.add_cycle(G, [0, 1, 2, 3])
nx.add_cycle(G, [0, 3, 4, 5])
nx.add_cycle(G, [0, 1, 6, 7, 8])
G.add_edge(8, 9)
cls.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(n))
def test_cycle_basis(self):
G = self.G
cy = nx.cycle_basis(G, 0)
sort_cy = sorted(sorted(c) for c in cy)
assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
cy = nx.cycle_basis(G, 1)
sort_cy = sorted(sorted(c) for c in cy)
assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
cy = nx.cycle_basis(G, 9)
sort_cy = sorted(sorted(c) for c in cy)
assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5]]
# test disconnected graphs
nx.add_cycle(G, "ABC")
cy = nx.cycle_basis(G, 9)
sort_cy = sorted(sorted(c) for c in cy[:-1]) + [sorted(cy[-1])]
assert sort_cy == [[0, 1, 2, 3], [0, 1, 6, 7, 8], [0, 3, 4, 5], ["A", "B", "C"]]
def test_cycle_basis2(self):
with pytest.raises(nx.NetworkXNotImplemented):
G = nx.DiGraph()
cy = nx.cycle_basis(G, 0)
def test_cycle_basis3(self):
with pytest.raises(nx.NetworkXNotImplemented):
G = nx.MultiGraph()
cy = nx.cycle_basis(G, 0)
def test_cycle_basis_ordered(self):
# see gh-6654 replace sets with (ordered) dicts
G = nx.cycle_graph(5)
G.update(nx.cycle_graph(range(3, 8)))
cbG = nx.cycle_basis(G)
perm = {1: 0, 0: 1} # switch 0 and 1
H = nx.relabel_nodes(G, perm)
cbH = [[perm.get(n, n) for n in cyc] for cyc in nx.cycle_basis(H)]
assert cbG == cbH
def test_cycle_basis_self_loop(self):
"""Tests the function for graphs with self loops"""
G = nx.Graph()
nx.add_cycle(G, [0, 1, 2, 3])
nx.add_cycle(G, [0, 0, 6, 2])
cy = nx.cycle_basis(G)
sort_cy = sorted(sorted(c) for c in cy)
assert sort_cy == [[0], [0, 1, 2], [0, 2, 3], [0, 2, 6]]
def test_simple_cycles(self):
edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
G = nx.DiGraph(edges)
cc = sorted(nx.simple_cycles(G))
ca = [[0], [0, 1, 2], [0, 2], [1, 2], [2]]
assert len(cc) == len(ca)
for c in cc:
assert any(self.is_cyclic_permutation(c, rc) for rc in ca)
def test_simple_cycles_singleton(self):
G = nx.Graph([(0, 0)]) # self-loop
assert list(nx.simple_cycles(G)) == [[0]]
def test_unsortable(self):
# this test ensures that graphs whose nodes without an intrinsic
# ordering do not cause issues
G = nx.DiGraph()
nx.add_cycle(G, ["a", 1])
c = list(nx.simple_cycles(G))
assert len(c) == 1
def test_simple_cycles_small(self):
G = nx.DiGraph()
nx.add_cycle(G, [1, 2, 3])
c = sorted(nx.simple_cycles(G))
assert len(c) == 1
assert self.is_cyclic_permutation(c[0], [1, 2, 3])
nx.add_cycle(G, [10, 20, 30])
cc = sorted(nx.simple_cycles(G))
assert len(cc) == 2
ca = [[1, 2, 3], [10, 20, 30]]
for c in cc:
assert any(self.is_cyclic_permutation(c, rc) for rc in ca)
def test_simple_cycles_empty(self):
G = nx.DiGraph()
assert list(nx.simple_cycles(G)) == []
def worst_case_graph(self, k):
# see figure 1 in Johnson's paper
# this graph has exactly 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 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 len(cc) == len(rcc)
for c in cc:
assert any(self.is_cyclic_permutation(c, r) for r in rcc)
for rc in rcc:
assert any(self.is_cyclic_permutation(rc, c) for c in cc)
def test_simple_graph_with_reported_bug(self):
G = nx.DiGraph()
edges = [
(0, 2),
(0, 3),
(1, 0),
(1, 3),
(2, 1),
(2, 4),
(3, 2),
(3, 4),
(4, 0),
(4, 1),
(4, 5),
(5, 0),
(5, 1),
(5, 2),
(5, 3),
]
G.add_edges_from(edges)
cc = sorted(nx.simple_cycles(G))
assert len(cc) == 26
rcc = sorted(nx.recursive_simple_cycles(G))
assert len(cc) == len(rcc)
for c in cc:
assert any(self.is_cyclic_permutation(c, rc) for rc in rcc)
for rc in rcc:
assert any(self.is_cyclic_permutation(rc, c) for c in cc)
def pairwise(iterable):
a, b = tee(iterable)
next(b, None)
return zip(a, b)
def cycle_edges(c):
return pairwise(chain(c, islice(c, 1)))
def directed_cycle_edgeset(c):
return frozenset(cycle_edges(c))
def undirected_cycle_edgeset(c):
if len(c) == 1:
return frozenset(cycle_edges(c))
return frozenset(map(frozenset, cycle_edges(c)))
def multigraph_cycle_edgeset(c):
if len(c) <= 2:
return frozenset(cycle_edges(c))
else:
return frozenset(map(frozenset, cycle_edges(c)))
class TestCycleEnumeration:
@staticmethod
def K(n):
return nx.complete_graph(n)
@staticmethod
def D(n):
return nx.complete_graph(n).to_directed()
@staticmethod
def edgeset_function(g):
if g.is_directed():
return directed_cycle_edgeset
elif g.is_multigraph():
return multigraph_cycle_edgeset
else:
return undirected_cycle_edgeset
def check_cycle(self, g, c, es, cache, source, original_c, length_bound, chordless):
if length_bound is not None and len(c) > length_bound:
raise RuntimeError(
f"computed cycle {original_c} exceeds length bound {length_bound}"
)
if source == "computed":
if es in cache:
raise RuntimeError(
f"computed cycle {original_c} has already been found!"
)
else:
cache[es] = tuple(original_c)
else:
if es in cache:
cache.pop(es)
else:
raise RuntimeError(f"expected cycle {original_c} was not computed")
if not all(g.has_edge(*e) for e in es):
raise RuntimeError(
f"{source} claimed cycle {original_c} is not a cycle of g"
)
if chordless and len(g.subgraph(c).edges) > len(c):
raise RuntimeError(f"{source} cycle {original_c} is not chordless")
def check_cycle_algorithm(
self,
g,
expected_cycles,
length_bound=None,
chordless=False,
algorithm=None,
):
if algorithm is None:
algorithm = nx.chordless_cycles if chordless else nx.simple_cycles
# note: we shuffle the labels of g to rule out accidentally-correct
# behavior which occurred during the development of chordless cycle
# enumeration algorithms
relabel = list(range(len(g)))
shuffle(relabel)
label = dict(zip(g, relabel))
unlabel = dict(zip(relabel, g))
h = nx.relabel_nodes(g, label, copy=True)
edgeset = self.edgeset_function(h)
params = {}
if length_bound is not None:
params["length_bound"] = length_bound
cycle_cache = {}
for c in algorithm(h, **params):
original_c = [unlabel[x] for x in c]
es = edgeset(c)
self.check_cycle(
h, c, es, cycle_cache, "computed", original_c, length_bound, chordless
)
if isinstance(expected_cycles, int):
if len(cycle_cache) != expected_cycles:
raise RuntimeError(
f"expected {expected_cycles} cycles, got {len(cycle_cache)}"
)
return
for original_c in expected_cycles:
c = [label[x] for x in original_c]
es = edgeset(c)
self.check_cycle(
h, c, es, cycle_cache, "expected", original_c, length_bound, chordless
)
if len(cycle_cache):
for c in cycle_cache.values():
raise RuntimeError(
f"computed cycle {c} is valid but not in the expected cycle set!"
)
def check_cycle_enumeration_integer_sequence(
self,
g_family,
cycle_counts,
length_bound=None,
chordless=False,
algorithm=None,
):
for g, num_cycles in zip(g_family, cycle_counts):
self.check_cycle_algorithm(
g,
num_cycles,
length_bound=length_bound,
chordless=chordless,
algorithm=algorithm,
)
def test_directed_chordless_cycle_digons(self):
g = nx.DiGraph()
nx.add_cycle(g, range(5))
nx.add_cycle(g, range(5)[::-1])
g.add_edge(0, 0)
expected_cycles = [(0,), (1, 2), (2, 3), (3, 4)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=2)
expected_cycles = [c for c in expected_cycles if len(c) < 2]
self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=1)
def test_directed_chordless_cycle_undirected(self):
g = nx.DiGraph([(1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (5, 1), (0, 2)])
expected_cycles = [(0, 2, 3, 4, 5), (1, 2, 3, 4, 5)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
g = nx.DiGraph()
nx.add_cycle(g, range(5))
nx.add_cycle(g, range(4, 9))
g.add_edge(7, 3)
expected_cycles = [(0, 1, 2, 3, 4), (3, 4, 5, 6, 7), (4, 5, 6, 7, 8)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
g.add_edge(3, 7)
expected_cycles = [(0, 1, 2, 3, 4), (3, 7), (4, 5, 6, 7, 8)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
expected_cycles = [(3, 7)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True, length_bound=4)
g.remove_edge(7, 3)
expected_cycles = [(0, 1, 2, 3, 4), (4, 5, 6, 7, 8)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
g = nx.DiGraph((i, j) for i in range(10) for j in range(i))
expected_cycles = []
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
def test_chordless_cycles_directed(self):
G = nx.DiGraph()
nx.add_cycle(G, range(5))
nx.add_cycle(G, range(4, 12))
expected = [[*range(5)], [*range(4, 12)]]
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
G.add_edge(7, 3)
expected.append([*range(3, 8)])
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
G.add_edge(3, 7)
expected[-1] = [7, 3]
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
expected.pop()
G.remove_edge(7, 3)
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
def test_directed_chordless_cycle_diclique(self):
g_family = [self.D(n) for n in range(10)]
expected_cycles = [(n * n - n) // 2 for n in range(10)]
self.check_cycle_enumeration_integer_sequence(
g_family, expected_cycles, chordless=True
)
expected_cycles = [(n * n - n) // 2 for n in range(10)]
self.check_cycle_enumeration_integer_sequence(
g_family, expected_cycles, length_bound=2
)
def test_directed_chordless_loop_blockade(self):
g = nx.DiGraph((i, i) for i in range(10))
nx.add_cycle(g, range(10))
expected_cycles = [(i,) for i in range(10)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
self.check_cycle_algorithm(g, expected_cycles, length_bound=1)
g = nx.MultiDiGraph(g)
g.add_edges_from((i, i) for i in range(0, 10, 2))
expected_cycles = [(i,) for i in range(1, 10, 2)]
self.check_cycle_algorithm(g, expected_cycles, chordless=True)
def test_simple_cycles_notable_clique_sequences(self):
# A000292: Number of labeled graphs on n+3 nodes that are triangles.
g_family = [self.K(n) for n in range(2, 12)]
expected = [0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, length_bound=3
)
def triangles(g, **kwargs):
yield from (c for c in nx.simple_cycles(g, **kwargs) if len(c) == 3)
# directed complete graphs have twice as many triangles thanks to reversal
g_family = [self.D(n) for n in range(2, 12)]
expected = [2 * e for e in expected]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, length_bound=3, algorithm=triangles
)
def four_cycles(g, **kwargs):
yield from (c for c in nx.simple_cycles(g, **kwargs) if len(c) == 4)
# A050534: the number of 4-cycles in the complete graph K_{n+1}
expected = [0, 0, 0, 3, 15, 45, 105, 210, 378, 630, 990]
g_family = [self.K(n) for n in range(1, 12)]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, length_bound=4, algorithm=four_cycles
)
# directed complete graphs have twice as many 4-cycles thanks to reversal
expected = [2 * e for e in expected]
g_family = [self.D(n) for n in range(1, 15)]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, length_bound=4, algorithm=four_cycles
)
# A006231: the number of elementary circuits in a complete directed graph with n nodes
expected = [0, 1, 5, 20, 84, 409, 2365]
g_family = [self.D(n) for n in range(1, 8)]
self.check_cycle_enumeration_integer_sequence(g_family, expected)
# A002807: Number of cycles in the complete graph on n nodes K_{n}.
expected = [0, 0, 0, 1, 7, 37, 197, 1172]
g_family = [self.K(n) for n in range(8)]
self.check_cycle_enumeration_integer_sequence(g_family, expected)
def test_directed_chordless_cycle_parallel_multiedges(self):
g = nx.MultiGraph()
nx.add_cycle(g, range(5))
expected = [[*range(5)]]
self.check_cycle_algorithm(g, expected, chordless=True)
nx.add_cycle(g, range(5))
expected = [*cycle_edges(range(5))]
self.check_cycle_algorithm(g, expected, chordless=True)
nx.add_cycle(g, range(5))
expected = []
self.check_cycle_algorithm(g, expected, chordless=True)
g = nx.MultiDiGraph()
nx.add_cycle(g, range(5))
expected = [[*range(5)]]
self.check_cycle_algorithm(g, expected, chordless=True)
nx.add_cycle(g, range(5))
self.check_cycle_algorithm(g, [], chordless=True)
nx.add_cycle(g, range(5))
self.check_cycle_algorithm(g, [], chordless=True)
g = nx.MultiDiGraph()
nx.add_cycle(g, range(5))
nx.add_cycle(g, range(5)[::-1])
expected = [*cycle_edges(range(5))]
self.check_cycle_algorithm(g, expected, chordless=True)
nx.add_cycle(g, range(5))
self.check_cycle_algorithm(g, [], chordless=True)
def test_chordless_cycles_graph(self):
G = nx.Graph()
nx.add_cycle(G, range(5))
nx.add_cycle(G, range(4, 12))
expected = [[*range(5)], [*range(4, 12)]]
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
G.add_edge(7, 3)
expected.append([*range(3, 8)])
expected.append([4, 3, 7, 8, 9, 10, 11])
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 5], length_bound=5, chordless=True
)
def test_chordless_cycles_giant_hamiltonian(self):
# ... o - e - o - e - o ... # o = odd, e = even
# ... ---/ \-----/ \--- ... # <-- "long" edges
#
# each long edge belongs to exactly one triangle, and one giant cycle
# of length n/2. The remaining edges each belong to a triangle
n = 1000
assert n % 2 == 0
G = nx.Graph()
for v in range(n):
if not v % 2:
G.add_edge(v, (v + 2) % n)
G.add_edge(v, (v + 1) % n)
expected = [[*range(0, n, 2)]] + [
[x % n for x in range(i, i + 3)] for i in range(0, n, 2)
]
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 3], length_bound=3, chordless=True
)
# ... o -> e -> o -> e -> o ... # o = odd, e = even
# ... <---/ \---<---/ \---< ... # <-- "long" edges
#
# this time, we orient the short and long edges in opposition
# the cycle structure of this graph is the same, but we need to reverse
# the long one in our representation. Also, we need to drop the size
# because our partitioning algorithm uses strongly connected components
# instead of separating graphs by their strong articulation points
n = 100
assert n % 2 == 0
G = nx.DiGraph()
for v in range(n):
G.add_edge(v, (v + 1) % n)
if not v % 2:
G.add_edge((v + 2) % n, v)
expected = [[*range(n - 2, -2, -2)]] + [
[x % n for x in range(i, i + 3)] for i in range(0, n, 2)
]
self.check_cycle_algorithm(G, expected, chordless=True)
self.check_cycle_algorithm(
G, [c for c in expected if len(c) <= 3], length_bound=3, chordless=True
)
def test_simple_cycles_acyclic_tournament(self):
n = 10
G = nx.DiGraph((x, y) for x in range(n) for y in range(x))
self.check_cycle_algorithm(G, [])
self.check_cycle_algorithm(G, [], chordless=True)
for k in range(n + 1):
self.check_cycle_algorithm(G, [], length_bound=k)
self.check_cycle_algorithm(G, [], length_bound=k, chordless=True)
def test_simple_cycles_graph(self):
testG = nx.cycle_graph(8)
cyc1 = tuple(range(8))
self.check_cycle_algorithm(testG, [cyc1])
testG.add_edge(4, -1)
nx.add_path(testG, [3, -2, -3, -4])
self.check_cycle_algorithm(testG, [cyc1])
testG.update(nx.cycle_graph(range(8, 16)))
cyc2 = tuple(range(8, 16))
self.check_cycle_algorithm(testG, [cyc1, cyc2])
testG.update(nx.cycle_graph(range(4, 12)))
cyc3 = tuple(range(4, 12))
expected = {
(0, 1, 2, 3, 4, 5, 6, 7), # cyc1
(8, 9, 10, 11, 12, 13, 14, 15), # cyc2
(4, 5, 6, 7, 8, 9, 10, 11), # cyc3
(4, 5, 6, 7, 8, 15, 14, 13, 12, 11), # cyc2 + cyc3
(0, 1, 2, 3, 4, 11, 10, 9, 8, 7), # cyc1 + cyc3
(0, 1, 2, 3, 4, 11, 12, 13, 14, 15, 8, 7), # cyc1 + cyc2 + cyc3
}
self.check_cycle_algorithm(testG, expected)
assert len(expected) == (2**3 - 1) - 1 # 1 disjoint comb: cyc1 + cyc2
# Basis size = 5 (2 loops overlapping gives 5 small loops
# E
# / \ Note: A-F = 10-15
# 1-2-3-4-5
# / | | \ cyc1=012DAB -- left
# 0 D F 6 cyc2=234E -- top
# \ | | / cyc3=45678F -- right
# B-A-9-8-7 cyc4=89AC -- bottom
# \ / cyc5=234F89AD -- middle
# C
#
# combinations of 5 basis elements: 2^5 - 1 (one includes no cycles)
#
# disjoint combs: (11 total) not simple cycles
# Any pair not including cyc5 => choose(4, 2) = 6
# Any triple not including cyc5 => choose(4, 3) = 4
# Any quad not including cyc5 => choose(4, 4) = 1
#
# we expect 31 - 11 = 20 simple cycles
#
testG = nx.cycle_graph(12)
testG.update(nx.cycle_graph([12, 10, 13, 2, 14, 4, 15, 8]).edges)
expected = (2**5 - 1) - 11 # 11 disjoint combinations
self.check_cycle_algorithm(testG, expected)
def test_simple_cycles_bounded(self):
# iteratively construct a cluster of nested cycles running in the same direction
# there should be one cycle of every length
d = nx.DiGraph()
expected = []
for n in range(10):
nx.add_cycle(d, range(n))
expected.append(n)
for k, e in enumerate(expected):
self.check_cycle_algorithm(d, e, length_bound=k)
# iteratively construct a path of undirected cycles, connected at articulation
# points. there should be one cycle of every length except 2: no digons
g = nx.Graph()
top = 0
expected = []
for n in range(10):
expected.append(n if n < 2 else n - 1)
if n == 2:
# no digons in undirected graphs
continue
nx.add_cycle(g, range(top, top + n))
top += n
for k, e in enumerate(expected):
self.check_cycle_algorithm(g, e, length_bound=k)
def test_simple_cycles_bound_corner_cases(self):
G = nx.cycle_graph(4)
DG = nx.cycle_graph(4, create_using=nx.DiGraph)
assert list(nx.simple_cycles(G, length_bound=0)) == []
assert list(nx.simple_cycles(DG, length_bound=0)) == []
assert list(nx.chordless_cycles(G, length_bound=0)) == []
assert list(nx.chordless_cycles(DG, length_bound=0)) == []
def test_simple_cycles_bound_error(self):
with pytest.raises(ValueError):
G = nx.DiGraph()
for c in nx.simple_cycles(G, -1):
assert False
with pytest.raises(ValueError):
G = nx.Graph()
for c in nx.simple_cycles(G, -1):
assert False
with pytest.raises(ValueError):
G = nx.Graph()
for c in nx.chordless_cycles(G, -1):
assert False
with pytest.raises(ValueError):
G = nx.DiGraph()
for c in nx.chordless_cycles(G, -1):
assert False
def test_chordless_cycles_clique(self):
g_family = [self.K(n) for n in range(2, 15)]
expected = [0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, chordless=True
)
# directed cliques have as many digons as undirected graphs have edges
expected = [(n * n - n) // 2 for n in range(15)]
g_family = [self.D(n) for n in range(15)]
self.check_cycle_enumeration_integer_sequence(
g_family, expected, chordless=True
)
# These tests might fail with hash randomization since they depend on
# edge_dfs. For more information, see the comments in:
# networkx/algorithms/traversal/tests/test_edgedfs.py
class TestFindCycle:
@classmethod
def setup_class(cls):
cls.nodes = [0, 1, 2, 3]
cls.edges = [(-1, 0), (0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]
def test_graph_nocycle(self):
G = nx.Graph(self.edges)
pytest.raises(nx.exception.NetworkXNoCycle, nx.find_cycle, G, self.nodes)
def test_graph_cycle(self):
G = nx.Graph(self.edges)
G.add_edge(2, 0)
x = list(nx.find_cycle(G, self.nodes))
x_ = [(0, 1), (1, 2), (2, 0)]
assert x == x_
def test_graph_orientation_none(self):
G = nx.Graph(self.edges)
G.add_edge(2, 0)
x = list(nx.find_cycle(G, self.nodes, orientation=None))
x_ = [(0, 1), (1, 2), (2, 0)]
assert x == x_
def test_graph_orientation_original(self):
G = nx.Graph(self.edges)
G.add_edge(2, 0)
x = list(nx.find_cycle(G, self.nodes, orientation="original"))
x_ = [(0, 1, FORWARD), (1, 2, FORWARD), (2, 0, FORWARD)]
assert x == x_
def test_digraph(self):
G = nx.DiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes))
x_ = [(0, 1), (1, 0)]
assert x == x_
def test_digraph_orientation_none(self):
G = nx.DiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes, orientation=None))
x_ = [(0, 1), (1, 0)]
assert x == x_
def test_digraph_orientation_original(self):
G = nx.DiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes, orientation="original"))
x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
assert x == x_
def test_multigraph(self):
G = nx.MultiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes))
x_ = [(0, 1, 0), (1, 0, 1)] # or (1, 0, 2)
# Hash randomization...could be any edge.
assert x[0] == x_[0]
assert x[1][:2] == x_[1][:2]
def test_multidigraph(self):
G = nx.MultiDiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes))
x_ = [(0, 1, 0), (1, 0, 0)] # (1, 0, 1)
assert x[0] == x_[0]
assert x[1][:2] == x_[1][:2]
def test_digraph_ignore(self):
G = nx.DiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes, orientation="ignore"))
x_ = [(0, 1, FORWARD), (1, 0, FORWARD)]
assert x == x_
def test_digraph_reverse(self):
G = nx.DiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes, orientation="reverse"))
x_ = [(1, 0, REVERSE), (0, 1, REVERSE)]
assert x == x_
def test_multidigraph_ignore(self):
G = nx.MultiDiGraph(self.edges)
x = list(nx.find_cycle(G, self.nodes, orientation="ignore"))
x_ = [(0, 1, 0, FORWARD), (1, 0, 0, FORWARD)] # or (1, 0, 1, 1)
assert x[0] == x_[0]
assert x[1][:2] == x_[1][:2]
assert x[1][3] == x_[1][3]
def test_multidigraph_ignore2(self):
# Loop traversed an edge while ignoring its orientation.
G = nx.MultiDiGraph([(0, 1), (1, 2), (1, 2)])
x = list(nx.find_cycle(G, [0, 1, 2], orientation="ignore"))
x_ = [(1, 2, 0, FORWARD), (1, 2, 1, REVERSE)]
assert x == x_
def test_multidigraph_original(self):
# Node 2 doesn't need to be searched again from visited from 4.
# The goal here is to cover the case when 2 to be researched from 4,
# when 4 is visited from the first time (so we must make sure that 4
# is not visited from 2, and hence, we respect the edge orientation).
G = nx.MultiDiGraph([(0, 1), (1, 2), (2, 3), (4, 2)])
pytest.raises(
nx.exception.NetworkXNoCycle,
nx.find_cycle,
G,
[0, 1, 2, 3, 4],
orientation="original",
)
def test_dag(self):
G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
pytest.raises(
nx.exception.NetworkXNoCycle, nx.find_cycle, G, orientation="original"
)
x = list(nx.find_cycle(G, orientation="ignore"))
assert x == [(0, 1, FORWARD), (1, 2, FORWARD), (0, 2, REVERSE)]
def test_prev_explored(self):
# https://github.com/networkx/networkx/issues/2323
G = nx.DiGraph()
G.add_edges_from([(1, 0), (2, 0), (1, 2), (2, 1)])
pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G, source=0)
x = list(nx.find_cycle(G, 1))
x_ = [(1, 2), (2, 1)]
assert x == x_
x = list(nx.find_cycle(G, 2))
x_ = [(2, 1), (1, 2)]
assert x == x_
x = list(nx.find_cycle(G))
x_ = [(1, 2), (2, 1)]
assert x == x_
def test_no_cycle(self):
# https://github.com/networkx/networkx/issues/2439
G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 0), (3, 1), (3, 2)])
pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G, source=0)
pytest.raises(nx.NetworkXNoCycle, nx.find_cycle, G)
def assert_basis_equal(a, b):
assert sorted(a) == sorted(b)
class TestMinimumCycleBasis:
@classmethod
def setup_class(cls):
T = nx.Graph()
nx.add_cycle(T, [1, 2, 3, 4], weight=1)
T.add_edge(2, 4, weight=5)
cls.diamond_graph = T
def test_unweighted_diamond(self):
mcb = nx.minimum_cycle_basis(self.diamond_graph)
assert_basis_equal(mcb, [[2, 4, 1], [3, 4, 2]])
def test_weighted_diamond(self):
mcb = nx.minimum_cycle_basis(self.diamond_graph, weight="weight")
assert_basis_equal(mcb, [[2, 4, 1], [4, 3, 2, 1]])
def test_dimensionality(self):
# checks |MCB|=|E|-|V|+|NC|
ntrial = 10
for seed in range(1234, 1234 + ntrial):
rg = nx.erdos_renyi_graph(10, 0.3, seed=seed)
nnodes = rg.number_of_nodes()
nedges = rg.number_of_edges()
ncomp = nx.number_connected_components(rg)
mcb = nx.minimum_cycle_basis(rg)
assert len(mcb) == nedges - nnodes + ncomp
check_independent(mcb)
def test_complete_graph(self):
cg = nx.complete_graph(5)
mcb = nx.minimum_cycle_basis(cg)
assert all(len(cycle) == 3 for cycle in mcb)
check_independent(mcb)
def test_tree_graph(self):
tg = nx.balanced_tree(3, 3)
assert not nx.minimum_cycle_basis(tg)
def test_petersen_graph(self):
G = nx.petersen_graph()
mcb = list(nx.minimum_cycle_basis(G))
expected = [
[4, 9, 7, 5, 0],
[1, 2, 3, 4, 0],
[1, 6, 8, 5, 0],
[4, 3, 8, 5, 0],
[1, 6, 9, 4, 0],
[1, 2, 7, 5, 0],
]
assert len(mcb) == len(expected)
assert all(c in expected for c in mcb)
# check that order of the nodes is a path
for c in mcb:
assert all(G.has_edge(u, v) for u, v in nx.utils.pairwise(c, cyclic=True))
# check independence of the basis
check_independent(mcb)
def test_gh6787_variable_weighted_complete_graph(self):
N = 8
cg = nx.complete_graph(N)
cg.add_weighted_edges_from([(u, v, 9) for u, v in cg.edges])
cg.add_weighted_edges_from([(u, v, 1) for u, v in nx.cycle_graph(N).edges])
mcb = nx.minimum_cycle_basis(cg, weight="weight")
check_independent(mcb)
def test_gh6787_and_edge_attribute_names(self):
G = nx.cycle_graph(4)
G.add_weighted_edges_from([(0, 2, 10), (1, 3, 10)], weight="dist")
expected = [[1, 3, 0], [3, 2, 1, 0], [1, 2, 0]]
mcb = list(nx.minimum_cycle_basis(G, weight="dist"))
assert len(mcb) == len(expected)
assert all(c in expected for c in mcb)
# test not using a weight with weight attributes
expected = [[1, 3, 0], [1, 2, 0], [3, 2, 0]]
mcb = list(nx.minimum_cycle_basis(G))
assert len(mcb) == len(expected)
assert all(c in expected for c in mcb)
class TestGirth:
@pytest.mark.parametrize(
("G", "expected"),
(
(nx.chvatal_graph(), 4),
(nx.tutte_graph(), 4),
(nx.petersen_graph(), 5),
(nx.heawood_graph(), 6),
(nx.pappus_graph(), 6),
(nx.random_labeled_tree(10, seed=42), inf),
(nx.empty_graph(10), inf),
(nx.Graph(chain(cycle_edges(range(5)), cycle_edges(range(6, 10)))), 4),
(
nx.Graph(
[
(0, 6),
(0, 8),
(0, 9),
(1, 8),
(2, 8),
(2, 9),
(4, 9),
(5, 9),
(6, 8),
(6, 9),
(7, 8),
]
),
3,
),
),
)
def test_girth(self, G, expected):
assert nx.girth(G) == expected
