vermouth.ismags module

ISMAGS Algorithm

Provides a Python implementation of the ISMAGS algorithm. [1]

It is capable of finding (subgraph) isomorphisms between two graphs, taking the symmetry of the subgraph into account. In most cases the VF2 algorithm is faster (at least on small graphs) than this implementation, but in some cases there is an exponential number of isomorphisms that are symmetrically equivalent. In that case, the ISMAGS algorithm will provide only one solution per symmetry group.

In addition, this implementation also provides an interface to find the largest common induced subgraph [2] between any two graphs, again taking symmetry into account. Given graph and subgraph the algorithm will remove nodes from the subgraph until subgraph is isomorphic to a subgraph of graph. Since only the symmetry of subgraph is taken into account it is worth thinking about how you provide your graphs:

>>> graph1 = nx.path_graph(4)
>>> graph2 = nx.star_graph(3)
>>> ismags = isomorphism.ISMAGS(graph1, graph2)
>>> ismags.is_isomorphic()
False
>>> list(ismags.largest_common_subgraph())
[{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}]
>>> ismags2 = isomorphism.ISMAGS(graph2, graph1)
>>> list(ismags2.largest_common_subgraph())
[{1: 0, 0: 1, 2: 2},
 {1: 0, 0: 1, 3: 2},
 {2: 0, 0: 1, 1: 2},
 {2: 0, 0: 1, 3: 2},
 {3: 0, 0: 1, 1: 2},
 {3: 0, 0: 1, 2: 2}]

However, when not taking symmetry into account, it doesn’t matter:

>>> list(ismags.largest_common_subgraph(symmetry=False))
[{1: 0, 0: 1, 2: 3},
 {1: 0, 2: 1, 0: 3},
 {2: 0, 1: 1, 3: 3},
 {2: 0, 3: 1, 1: 3},
 {1: 0, 0: 2, 2: 3},
 {1: 0, 2: 2, 0: 3},
 {2: 0, 1: 2, 3: 3},
 {2: 0, 3: 2, 1: 3},
 {1: 0, 0: 1, 2: 2},
 {1: 0, 2: 1, 0: 2},
 {2: 0, 1: 1, 3: 2},
 {2: 0, 3: 1, 1: 2}]
>>> list(ismags2.largest_common_subgraph(symmetry=False))
[{1: 0, 0: 1, 2: 3},
 {1: 0, 2: 1, 0: 3},
 {2: 0, 1: 1, 3: 3},
 {2: 0, 3: 1, 1: 3},
 {1: 0, 0: 2, 2: 3},
 {1: 0, 2: 2, 0: 3},
 {2: 0, 1: 2, 3: 3},
 {2: 0, 3: 2, 1: 3},
 {1: 0, 0: 1, 2: 2},
 {1: 0, 2: 1, 0: 2},
 {2: 0, 1: 1, 3: 2},
 {2: 0, 3: 1, 1: 2}]

Notes

  • The current implementation works for undirected graphs only. The algorithm in general should work for directed graphs as well though.

  • Node keys for both provided graphs need to be fully orderable as well as hashable.

  • Node and edge equality is assumed to be transitive: if A is equal to B, and B is equal to C, then A is equal to C.

References

class vermouth.ismags.ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]

Bases: object

Implements the ISMAGS subgraph matching algorith. [1] ISMAGS stands for “Index-based Subgraph Matching Algorithm with General Symmetries”. As the name implies, it is symmetry aware and will only generate non-symmetric isomorphisms.

Notes

The implementation imposes additional conditions compared to the VF2 algorithm on the graphs provided and the comparison functions (node_equality and edge_equality):

  • Node keys in both graphs must be orderable as well as hashable.

  • Equality must be transitive: if A is equal to B, and B is equal to C, then A must be equal to C.

graph
Type:

networkx.Graph

subgraph
Type:

networkx.Graph

node_equality

The function called to see if two nodes should be considered equal. It’s signature looks like this: f(graph1: networkx.Graph, node1, graph2: networkx.Graph, node2) -> bool. node1 is a node in graph1, and node2 a node in graph2. Constructed from the argument node_match.

Type:

collections.abc.Callable

edge_equality

The function called to see if two edges should be considered equal. It’s signature looks like this: f(graph1: networkx.Graph, edge1, graph2: networkx.Graph, edge2) -> bool. edge1 is an edge in graph1, and edge2 an edge in graph2. Constructed from the argument edge_match.

Type:

collections.abc.Callable

Parameters:
analyze_symmetry(graph, node_partitions, edge_colors)[source]

Find a minimal set of permutations and corresponding co-sets that describe the symmetry of subgraph.

Returns:

  • set[frozenset] – The found permutations. This is a set of frozenset of pairs of node keys which can be exchanged without changing subgraph.

  • dict[collections.abc.Hashable, set[collections.abc.Hashable]] – The found co-sets. The co-sets is a dictionary of {node key: set of node keys}. Every key-value pair describes which values can be interchanged without changing nodes less than key.

find_isomorphisms(symmetry=True)[source]

Find all subgraph isomorphisms between subgraph <= graph.

Parameters:

symmetry (bool) – Whether symmetry should be taken into account. If False, found isomorphisms may be symmetrically equivalent.

Yields:

dict – The found isomorphism mappings of {graph_node: subgraph_node}.

is_isomorphic(symmetry=False)[source]

Returns True if graph is isomorphic to subgraph and False otherwise.

Return type:

bool

isomorphisms_iter(symmetry=True)[source]

Does the same as find_isomorphisms() if graph and subgraph have the same number of nodes.

largest_common_subgraph(symmetry=True)[source]

Find the largest common induced subgraphs between subgraph and graph.

Parameters:

symmetry (bool) – Whether symmetry should be taken into account. If False, found largest common subgraphs may be symmetrically equivalent.

Yields:

dict – The found isomorphism mappings of {graph_node: subgraph_node}.

subgraph_is_isomorphic(symmetry=False)[source]

Returns True if a subgraph of graph is isomorphic to subgraph and False otherwise.

Return type:

bool

subgraph_isomorphisms_iter(symmetry=True)[source]

Alternative name for find_isomorphisms().

vermouth.ismags.intersect(collection_of_sets)[source]

Given an collection of sets, returns the intersection of those sets.

Parameters:

collection_of_sets (collections.abc.Collection[set]) – A collection of sets.

Returns:

An intersection of all sets in collection_of_sets. Will have the same type as the item initially taken from collection_of_sets.

Return type:

set

vermouth.ismags.make_partitions(items, test)[source]

Partitions items into sets based on the outcome of test(item1, item2). Pairs of items for which test returns True end up in the same set.

Parameters:
Returns:

A list of sets, with each set containing part of the items in items, such that all(test(*pair) for pair in  itertools.combinations(set, 2)) == True

Return type:

list[set]

Notes

The function test is assumed to be transitive: if test(a, b) and test(b, c) return True, then test(a, c) must also be True.

vermouth.ismags.partition_to_color(partitions)[source]

Creates a dictionary with for every item in partition for every partition in partitions the index of partition in partitions.

Parameters:

partitions (collections.abc.Sequence[collections.abc.Iterable]) – As returned by make_partitions().

Return type:

dict[collections.abc.Hashable, int]