### view env/lib/python3.9/site-packages/networkx/algorithms/tests/test_minors.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""Unit tests for the :mod:`networkx.algorithms.minors` module."""
import pytest

import networkx as nx
from networkx.testing.utils import assert_edges_equal, assert_nodes_equal
from networkx.utils import arbitrary_element

class TestQuotient:
"""Unit tests for computing quotient graphs."""

def test_quotient_graph_complete_multipartite(self):
"""Tests that the quotient graph of the complete *n*-partite graph
under the "same neighbors" node relation is the complete graph on *n*
nodes.

"""
G = nx.complete_multipartite_graph(2, 3, 4)
# Two nodes are equivalent if they are not adjacent but have the same
# neighbor set.

def same_neighbors(u, v):
return u not in G[v] and v not in G[u] and G[u] == G[v]

expected = nx.complete_graph(3)
actual = nx.quotient_graph(G, same_neighbors)
# It won't take too long to run a graph isomorphism algorithm on such
# small graphs.
assert nx.is_isomorphic(expected, actual)

def test_quotient_graph_complete_bipartite(self):
"""Tests that the quotient graph of the complete bipartite graph under
the "same neighbors" node relation is `K_2`.

"""
G = nx.complete_bipartite_graph(2, 3)
# Two nodes are equivalent if they are not adjacent but have the same
# neighbor set.

def same_neighbors(u, v):
return u not in G[v] and v not in G[u] and G[u] == G[v]

expected = nx.complete_graph(2)
actual = nx.quotient_graph(G, same_neighbors)
# It won't take too long to run a graph isomorphism algorithm on such
# small graphs.
assert nx.is_isomorphic(expected, actual)

def test_quotient_graph_edge_relation(self):
"""Tests for specifying an alternate edge relation for the quotient
graph.

"""
G = nx.path_graph(5)

def identity(u, v):
return u == v

def same_parity(b, c):
return arbitrary_element(b) % 2 == arbitrary_element(c) % 2

actual = nx.quotient_graph(G, identity, same_parity)
expected = nx.Graph()
expected.add_edges_from([(0, 2), (0, 4), (2, 4)])
assert nx.is_isomorphic(actual, expected)

def test_condensation_as_quotient(self):
"""This tests that the condensation of a graph can be viewed as the
quotient graph under the "in the same connected component" equivalence
relation.

"""
# This example graph comes from the file `test_strongly_connected.py`.
G = nx.DiGraph()
[
(1, 2),
(2, 3),
(2, 11),
(2, 12),
(3, 4),
(4, 3),
(4, 5),
(5, 6),
(6, 5),
(6, 7),
(7, 8),
(7, 9),
(7, 10),
(8, 9),
(9, 7),
(10, 6),
(11, 2),
(11, 4),
(11, 6),
(12, 6),
(12, 11),
]
)
scc = list(nx.strongly_connected_components(G))
C = nx.condensation(G, scc)
component_of = C.graph["mapping"]
# Two nodes are equivalent if they are in the same connected component.

def same_component(u, v):
return component_of[u] == component_of[v]

Q = nx.quotient_graph(G, same_component)
assert nx.is_isomorphic(C, Q)

def test_path(self):
G = nx.path_graph(6)
partition = [{0, 1}, {2, 3}, {4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M:
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 1

def test_multigraph_path(self):
G = nx.MultiGraph(nx.path_graph(6))
partition = [{0, 1}, {2, 3}, {4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M:
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 1

def test_directed_path(self):
G = nx.DiGraph()
partition = [{0, 1}, {2, 3}, {4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M:
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 0.5

def test_directed_multigraph_path(self):
G = nx.MultiDiGraph()
partition = [{0, 1}, {2, 3}, {4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M:
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 0.5

def test_overlapping_blocks(self):
with pytest.raises(nx.NetworkXException):
G = nx.path_graph(6)
partition = [{0, 1, 2}, {2, 3}, {4, 5}]
nx.quotient_graph(G, partition)

def test_weighted_path(self):
G = nx.path_graph(6)
for i in range(5):
G[i][i + 1]["weight"] = i + 1
partition = [{0, 1}, {2, 3}, {4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
assert M["weight"] == 2
assert M["weight"] == 4
for n in M:
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 1

def test_barbell(self):
G = nx.barbell_graph(3, 0)
partition = [{0, 1, 2}, {3, 4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1])
assert_edges_equal(M.edges(), [(0, 1)])
for n in M:
assert M.nodes[n]["nedges"] == 3
assert M.nodes[n]["nnodes"] == 3
assert M.nodes[n]["density"] == 1

def test_barbell_plus(self):
G = nx.barbell_graph(3, 0)
# Add an extra edge joining the bells.
partition = [{0, 1, 2}, {3, 4, 5}]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M, [0, 1])
assert_edges_equal(M.edges(), [(0, 1)])
assert M["weight"] == 2
for n in M:
assert M.nodes[n]["nedges"] == 3
assert M.nodes[n]["nnodes"] == 3
assert M.nodes[n]["density"] == 1

def test_blockmodel(self):
G = nx.path_graph(6)
partition = [[0, 1], [2, 3], [4, 5]]
M = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(M.nodes(), [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M.nodes():
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 1.0

def test_multigraph_blockmodel(self):
G = nx.MultiGraph(nx.path_graph(6))
partition = [[0, 1], [2, 3], [4, 5]]
M = nx.quotient_graph(G, partition, create_using=nx.MultiGraph(), relabel=True)
assert_nodes_equal(M.nodes(), [0, 1, 2])
assert_edges_equal(M.edges(), [(0, 1), (1, 2)])
for n in M.nodes():
assert M.nodes[n]["nedges"] == 1
assert M.nodes[n]["nnodes"] == 2
assert M.nodes[n]["density"] == 1.0

def test_quotient_graph_incomplete_partition(self):
G = nx.path_graph(6)
partition = []
H = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(H.nodes(), [])
assert_edges_equal(H.edges(), [])

partition = [[0, 1], [2, 3], ]
H = nx.quotient_graph(G, partition, relabel=True)
assert_nodes_equal(H.nodes(), [0, 1, 2])
assert_edges_equal(H.edges(), [(0, 1)])

class TestContraction:
"""Unit tests for node and edge contraction functions."""

def test_undirected_node_contraction(self):
"""Tests for node contraction in an undirected graph."""
G = nx.cycle_graph(4)
actual = nx.contracted_nodes(G, 0, 1)
expected = nx.cycle_graph(3)
assert nx.is_isomorphic(actual, expected)

def test_directed_node_contraction(self):
"""Tests for node contraction in a directed graph."""
G = nx.DiGraph(nx.cycle_graph(4))
actual = nx.contracted_nodes(G, 0, 1)
expected = nx.DiGraph(nx.cycle_graph(3))
assert nx.is_isomorphic(actual, expected)

def test_undirected_node_contraction_no_copy(self):
"""Tests for node contraction in an undirected graph
by making changes in place."""
G = nx.cycle_graph(4)
actual = nx.contracted_nodes(G, 0, 1, copy=False)
expected = nx.cycle_graph(3)
assert nx.is_isomorphic(actual, G)
assert nx.is_isomorphic(actual, expected)

def test_directed_node_contraction_no_copy(self):
"""Tests for node contraction in a directed graph
by making changes in place."""
G = nx.DiGraph(nx.cycle_graph(4))
actual = nx.contracted_nodes(G, 0, 1, copy=False)
expected = nx.DiGraph(nx.cycle_graph(3))
assert nx.is_isomorphic(actual, G)
assert nx.is_isomorphic(actual, expected)

def test_create_multigraph(self):
"""Tests that using a MultiGraph creates multiple edges."""
G = nx.path_graph(3, create_using=nx.MultiGraph())
actual = nx.contracted_nodes(G, 0, 2)
expected = nx.MultiGraph()
assert_edges_equal(actual.edges, expected.edges)

def test_multigraph_keys(self):
"""Tests that multiedge keys are reset in new graph."""
G = nx.path_graph(3, create_using=nx.MultiGraph())
actual = nx.contracted_nodes(G, 0, 2)
expected = nx.MultiGraph()
expected.add_edge(0, 1, 2)  # keyed as 2 b/c 2 edges already in G
expected.add_edge(0, 0, 1)  # this comes from (0, 2, 5)
assert_edges_equal(actual.edges, expected.edges)

def test_node_attributes(self):
"""Tests that node contraction preserves node attributes."""
G = nx.cycle_graph(4)
# Add some data to the two nodes being contracted.
G.nodes["foo"] = "bar"
G.nodes["baz"] = "xyzzy"
actual = nx.contracted_nodes(G, 0, 1)
# We expect that contracting the nodes 0 and 1 in C_4 yields K_3, but
# with nodes labeled 0, 2, and 3, and with a self-loop on 0.
expected = nx.complete_graph(3)
expected = nx.relabel_nodes(expected, {1: 2, 2: 3})
cdict = {1: {"baz": "xyzzy"}}
expected.nodes.update(dict(foo="bar", contraction=cdict))
assert nx.is_isomorphic(actual, expected)
assert actual.nodes == expected.nodes

def test_without_self_loops(self):
"""Tests for node contraction without preserving self-loops."""
G = nx.cycle_graph(4)
actual = nx.contracted_nodes(G, 0, 1, self_loops=False)
expected = nx.complete_graph(3)
assert nx.is_isomorphic(actual, expected)

def test_contract_selfloop_graph(self):
"""Tests for node contraction when nodes have selfloops."""
G = nx.cycle_graph(4)
actual = nx.contracted_nodes(G, 0, 1)
expected = nx.complete_graph([0, 2, 3])
assert_edges_equal(actual.edges, expected.edges)
actual = nx.contracted_nodes(G, 1, 0)
expected = nx.complete_graph([1, 2, 3])
assert_edges_equal(actual.edges, expected.edges)

def test_undirected_edge_contraction(self):
"""Tests for edge contraction in an undirected graph."""
G = nx.cycle_graph(4)
actual = nx.contracted_edge(G, (0, 1))
expected = nx.complete_graph(3)