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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
line wrap: on
line source
```
"""
Tests for ISMAGS isomorphism algorithm.
"""

import pytest
import networkx as nx
from networkx.algorithms import isomorphism as iso

def _matches_to_sets(matches):
"""
Helper function to facilitate comparing collections of dictionaries in
which order does not matter.
"""
return set(map(lambda m: frozenset(m.items()), matches))

class TestSelfIsomorphism:
data = [
(
[
(0, dict(name="a")),
(1, dict(name="a")),
(2, dict(name="b")),
(3, dict(name="b")),
(4, dict(name="a")),
(5, dict(name="a")),
],
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
),
(range(1, 5), [(1, 2), (2, 4), (4, 3), (3, 1)]),
(
[],
[
(0, 1),
(1, 2),
(2, 3),
(3, 4),
(4, 5),
(5, 0),
(0, 6),
(6, 7),
(2, 8),
(8, 9),
(4, 10),
(10, 11),
],
),
([], [(0, 1), (1, 2), (1, 4), (2, 3), (3, 5), (3, 6)]),
]

def test_self_isomorphism(self):
"""
For some small, symmetric graphs, make sure that 1) they are isomorphic
to themselves, and 2) that only the identity mapping is found.
"""
for node_data, edge_data in self.data:
graph = nx.Graph()

ismags = iso.ISMAGS(
graph, graph, node_match=iso.categorical_node_match("name", None)
)
assert ismags.is_isomorphic()
assert ismags.subgraph_is_isomorphic()
assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
{n: n for n in graph.nodes}
]

def test_edgecase_self_isomorphism(self):
"""
This edgecase is one of the cases in which it is hard to find all
symmetry elements.
"""
graph = nx.Graph()

ismags = iso.ISMAGS(graph, graph)
assert ismags_answer == [{n: n for n in graph.nodes}]

graph = nx.relabel_nodes(graph, {0: 0, 1: 1, 2: 2, 3: 3, 4: 6, 5: 4, 6: 5})
ismags = iso.ISMAGS(graph, graph)
assert ismags_answer == [{n: n for n in graph.nodes}]

@pytest.mark.skip()
def test_directed_self_isomorphism(self):
"""
For some small, directed, symmetric graphs, make sure that 1) they are
isomorphic to themselves, and 2) that only the identity mapping is
found.
"""
for node_data, edge_data in self.data:
graph = nx.Graph()

ismags = iso.ISMAGS(
graph, graph, node_match=iso.categorical_node_match("name", None)
)
assert ismags.is_isomorphic()
assert ismags.subgraph_is_isomorphic()
assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
{n: n for n in graph.nodes}
]

class TestSubgraphIsomorphism:
def test_isomorphism(self):
g1 = nx.Graph()

g2 = nx.Graph()
g2.add_edges_from([(n, m) for n, m in zip(g2, range(4, 8))])
ismags = iso.ISMAGS(g2, g1)
assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
{n: n for n in g1.nodes}
]

def test_isomorphism2(self):
g1 = nx.Graph()

g2 = g1.copy()

ismags = iso.ISMAGS(g2, g1)
matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
expected_symmetric = [
{0: 0, 1: 1, 2: 2},
{0: 0, 1: 1, 3: 2},
{2: 0, 1: 1, 3: 2},
]
assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)

matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
expected_asymmetric = [
{0: 2, 1: 1, 2: 0},
{0: 2, 1: 1, 3: 0},
{2: 2, 1: 1, 3: 0},
]
assert _matches_to_sets(matches) == _matches_to_sets(
expected_symmetric + expected_asymmetric
)

def test_labeled_nodes(self):
g1 = nx.Graph()
g1.nodes[1]["attr"] = True

g2 = g1.copy()
ismags = iso.ISMAGS(g2, g1, node_match=lambda x, y: x == y)
matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
expected_symmetric = [{0: 0, 1: 1, 2: 2}]
assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)

matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
expected_asymmetric = [{0: 2, 1: 1, 2: 0}]
assert _matches_to_sets(matches) == _matches_to_sets(
expected_symmetric + expected_asymmetric
)

def test_labeled_edges(self):
g1 = nx.Graph()
g1.edges[1, 2]["attr"] = True

g2 = g1.copy()
ismags = iso.ISMAGS(g2, g1, edge_match=lambda x, y: x == y)
matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
expected_symmetric = [{0: 0, 1: 1, 2: 2}]
assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)

matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
expected_asymmetric = [{1: 2, 0: 0, 2: 1}]
assert _matches_to_sets(matches) == _matches_to_sets(
expected_symmetric + expected_asymmetric
)

class TestWikipediaExample:
# Nodes 'a', 'b', 'c' and 'd' form a column.
# Nodes 'g', 'h', 'i' and 'j' form a column.
g1edges = [
["a", "g"],
["a", "h"],
["a", "i"],
["b", "g"],
["b", "h"],
["b", "j"],
["c", "g"],
["c", "i"],
["c", "j"],
["d", "h"],
["d", "i"],
["d", "j"],
]

# Nodes 1,2,3,4 form the clockwise corners of a large square.
# Nodes 5,6,7,8 form the clockwise corners of a small square
g2edges = [
[1, 2],
[2, 3],
[3, 4],
[4, 1],
[5, 6],
[6, 7],
[7, 8],
[8, 5],
[1, 5],
[2, 6],
[3, 7],
[4, 8],
]

def test_graph(self):
g1 = nx.Graph()
g2 = nx.Graph()
gm = iso.ISMAGS(g1, g2)
assert gm.is_isomorphic()

class TestLargestCommonSubgraph:
def test_mcis(self):
# Example graphs from DOI: 10.1002/spe.588
graph1 = nx.Graph()
graph1.add_edges_from([(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)])
graph1.nodes[1]["color"] = 0

graph2 = nx.Graph()
[(1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6), (5, 7), (6, 7)]
)
graph2.nodes[1]["color"] = 1
graph2.nodes[6]["color"] = 2
graph2.nodes[7]["color"] = 2

ismags = iso.ISMAGS(
graph1, graph2, node_match=iso.categorical_node_match("color", None)
)
assert list(ismags.subgraph_isomorphisms_iter(True)) == []
assert list(ismags.subgraph_isomorphisms_iter(False)) == []
found_mcis = _matches_to_sets(ismags.largest_common_subgraph())
expected = _matches_to_sets(
[{2: 2, 3: 4, 4: 3, 5: 5}, {2: 4, 3: 2, 4: 3, 5: 5}]
)
assert expected == found_mcis

ismags = iso.ISMAGS(
graph2, graph1, node_match=iso.categorical_node_match("color", None)
)
assert list(ismags.subgraph_isomorphisms_iter(True)) == []
assert list(ismags.subgraph_isomorphisms_iter(False)) == []
found_mcis = _matches_to_sets(ismags.largest_common_subgraph())
expected = _matches_to_sets(
[{2: 2, 3: 4, 4: 3, 5: 5}, {4: 2, 2: 3, 3: 4, 5: 5}]
)
assert expected == found_mcis

def test_symmetry_mcis(self):
graph1 = nx.Graph()

graph2 = nx.Graph()

# Only the symmetry of graph2 is taken into account here.
ismags1 = iso.ISMAGS(
graph1, graph2, node_match=iso.categorical_node_match("color", None)
)
assert list(ismags1.subgraph_isomorphisms_iter(True)) == []
found_mcis = _matches_to_sets(ismags1.largest_common_subgraph())
expected = _matches_to_sets([{0: 0, 1: 1, 2: 2}, {1: 0, 3: 2, 2: 1}])
assert expected == found_mcis

# Only the symmetry of graph1 is taken into account here.
ismags2 = iso.ISMAGS(
graph2, graph1, node_match=iso.categorical_node_match("color", None)
)
assert list(ismags2.subgraph_isomorphisms_iter(True)) == []
found_mcis = _matches_to_sets(ismags2.largest_common_subgraph())
expected = _matches_to_sets(
[
{3: 2, 0: 0, 1: 1},
{2: 0, 0: 2, 1: 1},
{3: 0, 0: 2, 1: 1},
{3: 0, 1: 1, 2: 2},
{0: 0, 1: 1, 2: 2},
{2: 0, 3: 2, 1: 1},
]
)

assert expected == found_mcis

found_mcis1 = _matches_to_sets(ismags1.largest_common_subgraph(False))
found_mcis2 = ismags2.largest_common_subgraph(False)
found_mcis2 = [{v: k for k, v in d.items()} for d in found_mcis2]
found_mcis2 = _matches_to_sets(found_mcis2)

expected = _matches_to_sets(
[
{3: 2, 1: 3, 2: 1},
{2: 0, 0: 2, 1: 1},
{1: 2, 3: 3, 2: 1},
{3: 0, 1: 3, 2: 1},
{0: 2, 2: 3, 1: 1},
{3: 0, 1: 2, 2: 1},
{2: 0, 0: 3, 1: 1},
{0: 0, 2: 3, 1: 1},
{1: 0, 3: 3, 2: 1},
{1: 0, 3: 2, 2: 1},
{0: 3, 1: 1, 2: 2},
{0: 0, 1: 1, 2: 2},
]
)
assert expected == found_mcis1
assert expected == found_mcis2
```