# vermouth.ismags module¶

## ISMAGS Algorithm¶

Provides a Python implementation of the ISMAGS algorithm. 

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  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

  (1, 2) M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle, M. Pickavet, “The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration”, PLoS One 9(5): e97896, 2014. https://doi.org/10.1371/journal.pone.0097896
class vermouth.ismags.ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]

Bases: object

Implements the ISMAGS subgraph matching algorith.  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.

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.

Parameters: graph (networkx.Graph) – subgraph (networkx.Graph) – node_match (collections.abc.Callable or None) – Function used to determine whether two nodes are equivalent. Its signature should look like f(n1: dict, n2: dict) -> bool, with n1 and n2 node property dicts. See also categorical_node_match() and friends. If None, all nodes are considered equal. edge_match (collections.abc.Callable or None) – Function used to determine whether two edges are equivalent. Its signature should look like f(e1: dict, e2: dict) -> bool, with e1 and e2 edge property dicts. See also categorical_edge_match() and friends. If None, all edges are considered equal. cache (collections.abc.Mapping) – A cache used for caching graph symmetries.
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. 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.

Returns: 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. 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.

Returns: 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. An intersection of all sets in collection_of_sets. Will have the same type as the item initially taken from collection_of_sets. 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: items (collections.abc.Iterable[collections.abc.Hashable]) – Items to partition test (collections.abc.Callable[collections.abc.Hashable, collections.abc.Hashable]) – A function that will be called with 2 arguments, taken from items. Should return True if those 2 items need to end up in the same partition, and False otherwise. 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 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(). dict[collections.abc.Hashable, int]