File size: 6,227 Bytes
57db94b |
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 146 147 148 149 150 151 152 153 154 155 |
"""Unit tests for the :mod:`networkx.algorithms.boundary` module."""
from itertools import combinations
import pytest
import networkx as nx
from networkx import convert_node_labels_to_integers as cnlti
from networkx.utils import edges_equal
class TestNodeBoundary:
"""Unit tests for the :func:`~networkx.node_boundary` function."""
def test_null_graph(self):
"""Tests that the null graph has empty node boundaries."""
null = nx.null_graph()
assert nx.node_boundary(null, []) == set()
assert nx.node_boundary(null, [], []) == set()
assert nx.node_boundary(null, [1, 2, 3]) == set()
assert nx.node_boundary(null, [1, 2, 3], [4, 5, 6]) == set()
assert nx.node_boundary(null, [1, 2, 3], [3, 4, 5]) == set()
def test_path_graph(self):
P10 = cnlti(nx.path_graph(10), first_label=1)
assert nx.node_boundary(P10, []) == set()
assert nx.node_boundary(P10, [], []) == set()
assert nx.node_boundary(P10, [1, 2, 3]) == {4}
assert nx.node_boundary(P10, [4, 5, 6]) == {3, 7}
assert nx.node_boundary(P10, [3, 4, 5, 6, 7]) == {2, 8}
assert nx.node_boundary(P10, [8, 9, 10]) == {7}
assert nx.node_boundary(P10, [4, 5, 6], [9, 10]) == set()
def test_complete_graph(self):
K10 = cnlti(nx.complete_graph(10), first_label=1)
assert nx.node_boundary(K10, []) == set()
assert nx.node_boundary(K10, [], []) == set()
assert nx.node_boundary(K10, [1, 2, 3]) == {4, 5, 6, 7, 8, 9, 10}
assert nx.node_boundary(K10, [4, 5, 6]) == {1, 2, 3, 7, 8, 9, 10}
assert nx.node_boundary(K10, [3, 4, 5, 6, 7]) == {1, 2, 8, 9, 10}
assert nx.node_boundary(K10, [4, 5, 6], []) == set()
assert nx.node_boundary(K10, K10) == set()
assert nx.node_boundary(K10, [1, 2, 3], [3, 4, 5]) == {4, 5}
def test_petersen(self):
"""Check boundaries in the petersen graph
cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
"""
def cheeger(G, k):
return min(len(nx.node_boundary(G, nn)) / k for nn in combinations(G, k))
P = nx.petersen_graph()
assert cheeger(P, 1) == pytest.approx(3.00, abs=1e-2)
assert cheeger(P, 2) == pytest.approx(2.00, abs=1e-2)
assert cheeger(P, 3) == pytest.approx(1.67, abs=1e-2)
assert cheeger(P, 4) == pytest.approx(1.00, abs=1e-2)
assert cheeger(P, 5) == pytest.approx(0.80, abs=1e-2)
def test_directed(self):
"""Tests the node boundary of a directed graph."""
G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
S = {0, 1}
boundary = nx.node_boundary(G, S)
expected = {2}
assert boundary == expected
def test_multigraph(self):
"""Tests the node boundary of a multigraph."""
G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
S = {0, 1}
boundary = nx.node_boundary(G, S)
expected = {2, 4}
assert boundary == expected
def test_multidigraph(self):
"""Tests the edge boundary of a multidigraph."""
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
G = nx.MultiDiGraph(edges * 2)
S = {0, 1}
boundary = nx.node_boundary(G, S)
expected = {2}
assert boundary == expected
class TestEdgeBoundary:
"""Unit tests for the :func:`~networkx.edge_boundary` function."""
def test_null_graph(self):
null = nx.null_graph()
assert list(nx.edge_boundary(null, [])) == []
assert list(nx.edge_boundary(null, [], [])) == []
assert list(nx.edge_boundary(null, [1, 2, 3])) == []
assert list(nx.edge_boundary(null, [1, 2, 3], [4, 5, 6])) == []
assert list(nx.edge_boundary(null, [1, 2, 3], [3, 4, 5])) == []
def test_path_graph(self):
P10 = cnlti(nx.path_graph(10), first_label=1)
assert list(nx.edge_boundary(P10, [])) == []
assert list(nx.edge_boundary(P10, [], [])) == []
assert list(nx.edge_boundary(P10, [1, 2, 3])) == [(3, 4)]
assert sorted(nx.edge_boundary(P10, [4, 5, 6])) == [(4, 3), (6, 7)]
assert sorted(nx.edge_boundary(P10, [3, 4, 5, 6, 7])) == [(3, 2), (7, 8)]
assert list(nx.edge_boundary(P10, [8, 9, 10])) == [(8, 7)]
assert sorted(nx.edge_boundary(P10, [4, 5, 6], [9, 10])) == []
assert list(nx.edge_boundary(P10, [1, 2, 3], [3, 4, 5])) == [(2, 3), (3, 4)]
def test_complete_graph(self):
K10 = cnlti(nx.complete_graph(10), first_label=1)
def ilen(iterable):
return sum(1 for i in iterable)
assert list(nx.edge_boundary(K10, [])) == []
assert list(nx.edge_boundary(K10, [], [])) == []
assert ilen(nx.edge_boundary(K10, [1, 2, 3])) == 21
assert ilen(nx.edge_boundary(K10, [4, 5, 6, 7])) == 24
assert ilen(nx.edge_boundary(K10, [3, 4, 5, 6, 7])) == 25
assert ilen(nx.edge_boundary(K10, [8, 9, 10])) == 21
assert edges_equal(
nx.edge_boundary(K10, [4, 5, 6], [9, 10]),
[(4, 9), (4, 10), (5, 9), (5, 10), (6, 9), (6, 10)],
)
assert edges_equal(
nx.edge_boundary(K10, [1, 2, 3], [3, 4, 5]),
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)],
)
def test_directed(self):
"""Tests the edge boundary of a directed graph."""
G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
S = {0, 1}
boundary = list(nx.edge_boundary(G, S))
expected = [(1, 2)]
assert boundary == expected
def test_multigraph(self):
"""Tests the edge boundary of a multigraph."""
G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
S = {0, 1}
boundary = list(nx.edge_boundary(G, S))
expected = [(0, 4), (0, 4), (1, 2), (1, 2)]
assert boundary == expected
def test_multidigraph(self):
"""Tests the edge boundary of a multidigraph."""
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
G = nx.MultiDiGraph(edges * 2)
S = {0, 1}
boundary = list(nx.edge_boundary(G, S))
expected = [(1, 2), (1, 2)]
assert boundary == expected
|