Mercurial > repos > shellac > sam_consensus_v3
diff env/lib/python3.9/site-packages/networkx/algorithms/tests/test_boundary.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/env/lib/python3.9/site-packages/networkx/algorithms/tests/test_boundary.py Mon Mar 22 18:12:50 2021 +0000 @@ -0,0 +1,152 @@ +"""Unit tests for the :mod:`networkx.algorithms.boundary` module.""" + +from itertools import combinations + +import networkx as nx +from networkx.testing import almost_equal, assert_edges_equal +from networkx import convert_node_labels_to_integers as cnlti + + +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 almost_equal(cheeger(P, 1), 3.00, places=2) + assert almost_equal(cheeger(P, 2), 2.00, places=2) + assert almost_equal(cheeger(P, 3), 1.67, places=2) + assert almost_equal(cheeger(P, 4), 1.00, places=2) + assert almost_equal(cheeger(P, 5), 0.80, places=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 multdiigraph.""" + 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 multdiigraph.""" + 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