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
andedge_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:
- subgraph¶
- Type:
- 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:
- 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:
- 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 alsocategorical_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 alsocategorical_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.
- Yields:
dict – The found isomorphism mappings of {graph_node: subgraph_node}.
- is_isomorphic(symmetry=False)[source]¶
Returns True if
graph
is isomorphic tosubgraph
and False otherwise.- Return type:
- isomorphisms_iter(symmetry=True)[source]¶
Does the same as
find_isomorphisms()
ifgraph
andsubgraph
have the same number of nodes.
- largest_common_subgraph(symmetry=True)[source]¶
Find the largest common induced subgraphs between
subgraph
andgraph
.- 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 tosubgraph
and False otherwise.- Return type:
- 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:
- 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.
- 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:
Notes
The function test is assumed to be transitive: if
test(a, b)
andtest(b, c)
returnTrue
, thentest(a, c)
must also beTrue
.
- 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: