Mercurial > repos > shellac > sam_consensus_v3
view env/lib/python3.9/site-packages/networkx/algorithms/tests/test_cuts.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 source
"""Unit tests for the :mod:`networkx.algorithms.cuts` module.""" import networkx as nx class TestCutSize: """Unit tests for the :func:`~networkx.cut_size` function.""" def test_symmetric(self): """Tests that the cut size is symmetric.""" G = nx.barbell_graph(3, 0) S = {0, 1, 4} T = {2, 3, 5} assert nx.cut_size(G, S, T) == 4 assert nx.cut_size(G, T, S) == 4 def test_single_edge(self): """Tests for a cut of a single edge.""" G = nx.barbell_graph(3, 0) S = {0, 1, 2} T = {3, 4, 5} assert nx.cut_size(G, S, T) == 1 assert nx.cut_size(G, T, S) == 1 def test_directed(self): """Tests that each directed edge is counted once in the cut.""" G = nx.barbell_graph(3, 0).to_directed() S = {0, 1, 2} T = {3, 4, 5} assert nx.cut_size(G, S, T) == 2 assert nx.cut_size(G, T, S) == 2 def test_directed_symmetric(self): """Tests that a cut in a directed graph is symmetric.""" G = nx.barbell_graph(3, 0).to_directed() S = {0, 1, 4} T = {2, 3, 5} assert nx.cut_size(G, S, T) == 8 assert nx.cut_size(G, T, S) == 8 def test_multigraph(self): """Tests that parallel edges are each counted for a cut.""" G = nx.MultiGraph(["ab", "ab"]) assert nx.cut_size(G, {"a"}, {"b"}) == 2 class TestVolume: """Unit tests for the :func:`~networkx.volume` function.""" def test_graph(self): G = nx.cycle_graph(4) assert nx.volume(G, {0, 1}) == 4 def test_digraph(self): G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0)]) assert nx.volume(G, {0, 1}) == 2 def test_multigraph(self): edges = list(nx.cycle_graph(4).edges()) G = nx.MultiGraph(edges * 2) assert nx.volume(G, {0, 1}) == 8 def test_multidigraph(self): edges = [(0, 1), (1, 2), (2, 3), (3, 0)] G = nx.MultiDiGraph(edges * 2) assert nx.volume(G, {0, 1}) == 4 class TestNormalizedCutSize: """Unit tests for the :func:`~networkx.normalized_cut_size` function. """ def test_graph(self): G = nx.path_graph(4) S = {1, 2} T = set(G) - S size = nx.normalized_cut_size(G, S, T) # The cut looks like this: o-{-o--o-}-o expected = 2 * ((1 / 4) + (1 / 2)) assert expected == size def test_directed(self): G = nx.DiGraph([(0, 1), (1, 2), (2, 3)]) S = {1, 2} T = set(G) - S size = nx.normalized_cut_size(G, S, T) # The cut looks like this: o-{->o-->o-}->o expected = 2 * ((1 / 2) + (1 / 1)) assert expected == size class TestConductance: """Unit tests for the :func:`~networkx.conductance` function.""" def test_graph(self): G = nx.barbell_graph(5, 0) # Consider the singleton sets containing the "bridge" nodes. # There is only one cut edge, and each set has volume five. S = {4} T = {5} conductance = nx.conductance(G, S, T) expected = 1 / 5 assert expected == conductance class TestEdgeExpansion: """Unit tests for the :func:`~networkx.edge_expansion` function.""" def test_graph(self): G = nx.barbell_graph(5, 0) S = set(range(5)) T = set(G) - S expansion = nx.edge_expansion(G, S, T) expected = 1 / 5 assert expected == expansion class TestNodeExpansion: """Unit tests for the :func:`~networkx.node_expansion` function. """ def test_graph(self): G = nx.path_graph(8) S = {3, 4, 5} expansion = nx.node_expansion(G, S) # The neighborhood of S has cardinality five, and S has # cardinality three. expected = 5 / 3 assert expected == expansion class TestBoundaryExpansion: """Unit tests for the :func:`~networkx.boundary_expansion` function. """ def test_graph(self): G = nx.complete_graph(10) S = set(range(4)) expansion = nx.boundary_expansion(G, S) # The node boundary of S has cardinality six, and S has # cardinality three. expected = 6 / 4 assert expected == expansion class TestMixingExpansion: """Unit tests for the :func:`~networkx.mixing_expansion` function. """ def test_graph(self): G = nx.barbell_graph(5, 0) S = set(range(5)) T = set(G) - S expansion = nx.mixing_expansion(G, S, T) # There is one cut edge, and the total number of edges in the # graph is twice the total number of edges in a clique of size # five, plus one more for the bridge. expected = 1 / (2 * (5 * 4 + 1)) assert expected == expansion