Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2ISMAGS Algorithm
3================
5Provides a Python implementation of the ISMAGS algorithm. [1]_
7ISMAGS does a symmetry analysis to find the constraints on isomorphisms if
8we preclude yielding isomorphisms that differ by a symmetry of the subgraph.
9For example, if the subgraph contains a 4-cycle, every isomorphism would have a
10symmetric version with the nodes rotated relative to the original isomorphism.
11By encoding these symmetries as constraints we reduce the search space for
12isomorphisms and we also simplify processing the resulting isomorphisms.
14ISMAGS finds (subgraph) isomorphisms between two graphs, taking the
15symmetry of the subgraph into account. In most cases the VF2 algorithm is
16faster (at least on small graphs) than this implementation, but in some cases
17there are an exponential number of isomorphisms that are symmetrically
18equivalent. In that case, the ISMAGS algorithm will provide only one isomorphism
19per symmetry group, speeding up finding isomorphisms and avoiding the task of
20post-processing many effectively identical isomorphisms.
22>>> petersen = nx.petersen_graph()
23>>> ismags = nx.isomorphism.ISMAGS(petersen, petersen)
24>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=False))
25>>> len(isomorphisms)
26120
27>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=True))
28>>> answer = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}]
29>>> answer == isomorphisms
30True
32In addition, this implementation also provides an interface to find the
33largest common induced subgraph [2]_ between any two graphs, again taking
34symmetry into account. Given ``graph`` and ``subgraph`` the algorithm will remove
35nodes from the ``subgraph`` until ``subgraph`` is isomorphic to a subgraph of
36``graph``. Since only the symmetry of ``subgraph`` is taken into account it is
37worth thinking about how you provide your graphs:
39>>> graph1 = nx.path_graph(4)
40>>> graph2 = nx.star_graph(3)
41>>> ismags = nx.isomorphism.ISMAGS(graph1, graph2)
42>>> ismags.is_isomorphic()
43False
44>>> largest_common_subgraph = list(ismags.largest_common_subgraph())
45>>> answer = [{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}]
46>>> answer == largest_common_subgraph
47True
48>>> ismags2 = nx.isomorphism.ISMAGS(graph2, graph1)
49>>> largest_common_subgraph = list(ismags2.largest_common_subgraph())
50>>> answer = [
51... {1: 0, 0: 1, 2: 2},
52... {1: 0, 0: 1, 3: 2},
53... {2: 0, 0: 1, 1: 2},
54... {2: 0, 0: 1, 3: 2},
55... {3: 0, 0: 1, 1: 2},
56... {3: 0, 0: 1, 2: 2},
57... ]
58>>> answer == largest_common_subgraph
59True
61However, when not taking symmetry into account, it doesn't matter:
63>>> largest_common_subgraph = list(ismags.largest_common_subgraph(symmetry=False))
64>>> answer = [
65... {1: 0, 0: 1, 2: 2},
66... {1: 0, 2: 1, 0: 2},
67... {2: 0, 1: 1, 3: 2},
68... {2: 0, 3: 1, 1: 2},
69... {1: 0, 0: 1, 2: 3},
70... {1: 0, 2: 1, 0: 3},
71... {2: 0, 1: 1, 3: 3},
72... {2: 0, 3: 1, 1: 3},
73... {1: 0, 0: 2, 2: 3},
74... {1: 0, 2: 2, 0: 3},
75... {2: 0, 1: 2, 3: 3},
76... {2: 0, 3: 2, 1: 3},
77... ]
78>>> answer == largest_common_subgraph
79True
80>>> largest_common_subgraph = list(ismags2.largest_common_subgraph(symmetry=False))
81>>> answer = [
82... {1: 0, 0: 1, 2: 2},
83... {1: 0, 0: 1, 3: 2},
84... {2: 0, 0: 1, 1: 2},
85... {2: 0, 0: 1, 3: 2},
86... {3: 0, 0: 1, 1: 2},
87... {3: 0, 0: 1, 2: 2},
88... {1: 1, 0: 2, 2: 3},
89... {1: 1, 0: 2, 3: 3},
90... {2: 1, 0: 2, 1: 3},
91... {2: 1, 0: 2, 3: 3},
92... {3: 1, 0: 2, 1: 3},
93... {3: 1, 0: 2, 2: 3},
94... ]
95>>> answer == largest_common_subgraph
96True
98Notes
99-----
100- Node and edge equality is assumed to be transitive: if A is equal to B, and
101 B is equal to C, then A is equal to C.
103- With a method that yields subgraph isomorphisms, we can construct functions like
104 ``is_subgraph_isomorphic`` by checking for any yielded mapping. And functions like
105 ``is_isomorphic`` by checking whether the subgraph has the same number of nodes as
106 the graph and is also subgraph isomorphic. This subpackage also allows a
107 ``symmetry`` bool keyword argument so you can find isomorphisms with or
108 without the symmetry constraints.
110- For more information, see [2]_ and the documentation for :class:`ISMAGS`
111 which includes a description of the algorithm.
113References
114----------
115.. [1] M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle,
116 M. Pickavet, "The Index-Based Subgraph Matching Algorithm with General
117 Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph
118 Enumeration", PLoS One 9(5): e97896, 2014.
119 https://doi.org/10.1371/journal.pone.0097896
120.. [2] https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph
121"""
123__all__ = ["ISMAGS"]
125import itertools
126from collections import Counter, defaultdict
127from functools import reduce, wraps
129import networkx as nx
132def are_all_equal(iterable):
133 """
134 Returns ``True`` if and only if all elements in `iterable` are equal; and
135 ``False`` otherwise.
137 Parameters
138 ----------
139 iterable: collections.abc.Iterable
140 The container whose elements will be checked.
142 Returns
143 -------
144 bool
145 ``True`` iff all elements in `iterable` compare equal, ``False``
146 otherwise.
147 """
148 try:
149 shape = iterable.shape
150 except AttributeError:
151 pass
152 else:
153 if len(shape) > 1:
154 message = "The function does not works on multidimensional arrays."
155 raise NotImplementedError(message) from None
157 iterator = iter(iterable)
158 first = next(iterator, None)
159 return all(item == first for item in iterator)
162def make_partition(items, test, check=True):
163 """
164 Partitions items into sets based on the outcome of ``test(item1, item2)``.
165 Pairs of items for which `test` returns `True` end up in the same set.
167 Parameters
168 ----------
169 items : collections.abc.Iterable[collections.abc.Hashable]
170 Items to partition
171 test : collections.abc.Callable[collections.abc.Hashable, collections.abc.Hashable]
172 A function that will be called with 2 arguments, taken from items.
173 Should return `True` if those 2 items match/tests so need to end up in the same
174 part of the partition, and `False` otherwise.
175 check : bool optional (default: True)
176 If ``True``, check that the resulting partition satisfies the match criteria.
177 Every item should match every item in its part and none outside the part.
179 Returns
180 -------
181 list[set]
182 A partition as a list of sets (the parts). Each set contains some of
183 the items in `items`, such that all items are in exactly one part and every
184 pair of items in each part matches. The following will be true:
185 ``all(thing_matcher(*pair) for pair in itertools.combinations(items, 2))``
187 Notes
188 -----
189 The function `test` is assumed to be transitive: if ``test(a, b)`` and
190 ``test(b, c)`` return ``True``, then ``test(a, c)`` must also be ``True``.
191 The function `test` is assumed to be commutative: if ``test(a, b)``
192 returns ``True`` then ``test(b, a)`` returns ``True``.
193 """
194 partition = []
195 for item in items:
196 for part in partition:
197 p_item = next(iter(part))
198 if test(item, p_item):
199 part.add(item)
200 break
201 else: # No break
202 partition.append({item})
204 if check:
205 if not all(
206 test(t1, t2) and test(t2, t1)
207 for part in partition
208 for t1, t2 in itertools.combinations(part, 2)
209 ):
210 raise nx.NetworkXError(
211 f"\nInvalid partition created with {test}.\n"
212 "Some items in a part do not match. This leads to\n"
213 f"{partition=}"
214 )
215 if not all(
216 not test(t1, t2) and not test(t2, t1)
217 for p1 in partition
218 for p2 in partition
219 if p1 != p2
220 for t1, t2 in itertools.product(p1, p2)
221 ):
222 raise nx.NetworkXError(
223 f"\nInvalid partition created with {test}.\n"
224 "Some items match multiple parts. This leads to\n"
225 f"{partition=}"
226 )
227 return [set(part) for part in partition]
230def node_to_part_ID_dict(partition):
231 """
232 Creates a dictionary that maps each item in each part to the index of
233 the part to which it belongs.
235 Parameters
236 ----------
237 partition: collections.abc.Sequence[collections.abc.Iterable]
238 As returned by :func:`make_partition`.
240 Returns
241 -------
242 dict
243 """
244 return {node: ID for ID, part in enumerate(partition) for node in part}
247def color_degree_by_node(G, n_colors, e_colors):
248 """Returns a dict by node to counts of edge and node color for that node.
250 This returns a dict by node to a 2-tuple of node color and degree by
251 (edge color and nbr color). E.g. ``{0: (1, {(0, 2): 5})}`` means that
252 node ``0`` has node type 1 and has 5 edges of type 0 that go to nodes of type 2.
253 Thus, this is a measure of degree (edge count) by color of edge and color
254 of the node on the other side of that edge.
256 For directed graphs the degree counts is a 2-tuple of (in, out) degree counts.
258 Ideally, if edge_match is None, this could get simplified to just the node
259 color on the other end of the edge. Similarly if node_match is None then only
260 edge color is tracked. And if both are None, we simply count the number of edges.
261 """
262 # n_colors might be incomplete when using `largest_common_subgraph()`
263 if len(n_colors) < len(G):
264 for n, nbrs in G.adjacency():
265 if n not in n_colors:
266 n_colors[n] = None
267 for v in nbrs:
268 e_colors[n, v] = None
269 # undirected colored degree
270 if not G.is_directed():
271 return {
272 u: (n_colors[u], Counter((e_colors[u, v], n_colors[v]) for v in nbrs))
273 for u, nbrs in G.adjacency()
274 }
275 # directed colored out and in degree
276 return {
277 u: (
278 n_colors[u],
279 Counter((e_colors[u, v], n_colors[v]) for v in nbrs),
280 Counter((e_colors[v, u], n_colors[v]) for v in G._pred[u]),
281 )
282 for u, nbrs in G.adjacency()
283 }
286class EdgeLookup:
287 """Class to handle getitem for undirected edges.
289 Note that ``items()`` iterates over one of the two representations of the edge
290 (u, v) and (v, u). So this technically doesn't violate the Mapping
291 invariant that (k,v) pairs reported by ``items()`` satisfy ``.__getitem__(k) == v``.
292 But we are violating the spirit of the protocol by having keys available
293 for lookup by ``__getitem__`` that are not reported by ``items()``.
295 Note that if we used frozensets for undirected edges we would have the same
296 behavior we see here. You could ``__getitem__`` either ``{u, v}`` or ``{v, u}``
297 and get the same value -- yet ``items()`` would only report one of the two.
298 So from that perspective we *are* following the Mapping protocol. Our keys
299 are undirected edges. We are using 2-tuples as an imperfect representation
300 of these edges. We are not using 2-tuples as keys. Only as imperfect edges
301 and we use the edges as keys.
302 """
304 def __init__(self, edge_dict):
305 self.edge_dict = edge_dict
307 def __getitem__(self, edge):
308 if edge in self.edge_dict:
309 return self.edge_dict[edge]
310 return self.edge_dict[edge[::-1]]
312 def items(self):
313 return self.edge_dict.items()
316class ISMAGS:
317 """
318 Implements the ISMAGS subgraph matching algorithm. [1]_ ISMAGS stands for
319 "Index-based Subgraph Matching Algorithm with General Symmetries". As the
320 name implies, it is symmetry aware and will only generate non-symmetric
321 isomorphisms.
323 Attributes
324 ----------
325 graph: networkx.Graph
326 subgraph: networkx.Graph
328 Notes
329 -----
330 ISMAGS does a symmetry analysis to find the constraints on isomorphisms if
331 we preclude yielding isomorphisms that differ by a symmetry of the subgraph.
332 For example, if the subgraph is a 4-cycle, every isomorphism would have a
333 symmetric version with the nodes rotated relative to the original isomorphism.
334 By encoding these symmetries as constraints we reduce the search space for
335 isomorphisms and we also simplify processing the resulting isomorphisms.
337 **Symmetry Analysis**
339 The constraints in ISMAGS are based off the handling in ``nauty`` and its many
340 variants, in particular ``saucy``, as discussed in the ISMAGS paper [1]_.
341 That paper cites [3]_ for details on symmetry handling. Figure 2 of [3]_
342 describes the DFS approach to symmetries used here and relying on a data structure
343 called an Ordered Pair Partitions(OPP). This consists of a pair of partitions
344 where each part represents nodes with the same degree-by-color over all colors.
345 We refine these partitions simultaneously in a way to result in permutations
346 of the nodes that preserve the graph structure. We thus find automorphisms
347 for the subgraph of interest. From those we identify pairs of nodes which
348 are structurally equivalent. We then constrain our problem by requiring the
349 first of the pair to always be assigned first in the isomorphism -- thus
350 constraining the isomorphisms reported to only one example from the set of all
351 symmetrically equivalent isomorphisms. These constraints are computed once
352 based on the subgraph symmetries and then used throughout the DFS search for
353 isomorphisms.
355 Finding the symmetries involves a DFS of the OPP wherein we "couple" a node
356 to a node in its degree-by-color part of the partition. This "coupling" is done
357 via assigning a new color in the top partition to the node being coupled,
358 and the same new color in the bottom partition to the node being coupled to.
359 This new color has only one node in each partition. The new color also requires
360 that we "refine" both top and bottom partitions by splitting parts until each
361 part represents a common degree-by-color value. Those refinements introduce
362 new colors as the parts are split during refinement. Parts do not get combined
363 during refinement. So the coupling/refining process always results in at least
364 one new part with only one node in both the top and bottom partition. In practice
365 we usually refine into many new one-node parts in both partitions.
366 We continue in this way until each node has its own part/color in the top partition
367 -- and the node in the bottom partition with that color is the symmetric node.
368 That is, an OPP represents an automorphism, and thus a symmetry
369 of the subgraph when each color has a single node in the top partition and a single
370 node in the bottom partition. From those automorphisms we build up a set of nodes
371 that can be obtained from each other by symmetry (they are mutually symmetric).
372 That set of nodes is called an "orbit" of the subgraph under symmetry.
374 After finding the orbits for one symmetry, we backtrack in the DFS by removing the
375 latest coupling and replacing it with a coupling from the same top node to a new
376 bottom node in its degree-by-color grouping. When all possible couplings for that
377 node are considered we backtrack to the previously coupled node and recouple in
378 a DFS manner.
380 We can prune the DFS search tree in helpful ways. The paper [2]_ demonstrates 6
381 situations of interest in the DFS where pruning is possible:
383 - An **Automorphism OPP** is an OPP where every part in both partitions
384 contains a single node. The mapping/automorphism is found by mapping
385 each top node to the bottom node in the same color part. For example,
386 ``[({1}, {2}, {3}); ({2}, {3}, {1})]`` represents the mapping of each
387 node to the next in a triangle. It rotates the nodes around the triangle.
388 - The **Identity OPP** is the first automorphism found during the DFS. It
389 appears on the left side of the DFS tree and is first due to our ordering of
390 coupling nodes to be in an arbitrary but fixed ordering of the nodes. This
391 automorphism does not show any symmetries, but it ensures the orbit for each
392 node includes itself and it sets us up for handling the symmetries. Note that
393 a subgraph with no symmetries will only have the identity automorphism.
394 - A **Non-isomorphic OPP** occurs when refinement creates a different number of
395 parts in the top partition than in the bottom partition. This means no symmetries
396 will be found during further processing of that subtree of the DFS. We prune
397 the subtree and continue.
398 - A **Matching OPP** is such that each top part that has more than one node is
399 in fact equal to the bottom part with the same color. The many-node-parts match
400 exactly. The single-node parts then represent symmetries that do not permute
401 any matching nodes. Matching OPPs arise while finding the Identity Mapping. But
402 the single-node parts are identical in the two partitions, so no useful symmetries
403 are found. But after the Identity Mapping is found, every Matching OPP encountered
404 will have different nodes in at least two single-node parts of the same color.
405 So these positions in the DFS provide us with symmetries without any
406 need to find the whole automorphism. We can prune the subtree, update the orbits
407 and backtrack. Any larger symmetries that combine these symmetries with symmetries
408 of the many-node-parts do not need to be explored because the symmetry "generators"
409 found in this way provide a basis for all symmetries. We will find the symmetry
410 generators of the many-node-parts at another subtree of the DFS.
411 - An **Orbit Pruning OPP** is an OPP where the node coupling to be considered next
412 has both nodes already known to be in the same orbit. We have already identified
413 those permutations when we discovered the orbit. So we can prune the resulting
414 subtree. This is the primary pruning discussed in [1]_.
415 - A **Coset Point** in the DFS is a point of the tree when a node is first
416 back-tracked. That is, its couplings have all been analyzed once and we backtrack
417 to its parent. So, said another way, when a node is backtracked to and is about to
418 be mapped to a different node for the first time, its child in the DFS has been
419 completely analysed. Thus the orbit for that child at this point in the DFS is
420 the full orbit for symmetries involving only that child or larger nodes in the
421 node order. All smaller nodes are mapped to themselves.
422 This orbit is due to symmetries not involving smaller nodes. Such an orbit is
423 called the "coset" of that node. The Coset Point does not lead to pruning or to
424 more symmetries. It is the point in the process where we store the **coset** of
425 the node being backtracked. We use the cosets to construct the symmetry
426 constraints.
428 Once the pruned DFS tree has been traversed, we have collected the cosets of some
429 special nodes. Often most nodes are not coupled during the progression down the left
430 side of the DFS. They are separated from other nodes during the partition refinement
431 process after coupling. So they never get coupled directly. Thus the number of cosets
432 we find is typically many fewer than the number of nodes.
434 We turn those cosets into constraints on the nodes when building non-symmetric
435 isomorphisms. The node whose coset is used is paired with each other node in the
436 coset. These node-pairs form the constraints. During isomorphism construction we
437 always select the first of the constraint before the other. This removes subtrees
438 from the DFS traversal space used to build isomorphisms.
440 The constraints we obtain via symmetry analysis of the subgraph are used for
441 finding non-symmetric isomorphisms. We prune the isomorphism tree based on
442 the constraints we obtain from the symmetry analysis.
444 **Isomorphism Construction**
446 Once we have symmetry constraints on the isomorphisms, ISMAGS constructs the allowed
447 isomorphisms by mapping each node of the subgraph to all possible nodes (with the
448 same degree-by-color) from the graph. We partition all nodes into degree-by-color
449 parts and order the subgraph nodes we consider using smallest part size first.
450 The idea is to try to map the most difficult subgraph nodes first (most difficult
451 here means least number of graph candidates).
453 By considering each potential subgraph node to graph candidate mapping image in turn,
454 we perform a DFS traversal of partial mappings. If the mapping is rejected due to
455 the graph neighbors not matching the degree-by-color of the subgraph neighbors, or
456 rejected due to the constraints imposed from symmetry, we prune that subtree and
457 consider a new graph candidate node for that subgraph node. When no more graph
458 candidates remain we backtrack to the previous node in the mapping and consider a
459 new graph candidate for that node. If we ever get to a depth where all subgraph nodes
460 are mapped and no structural requirements or symmetry constraints are violated,
461 we have found an isomorphism. We yield that mapping and backtrack to find other
462 isomorphisms.
464 As we visit more neighbors, the graph candidate nodes have to satisfy more structural
465 restrictions. As described in the ISMAGS paper, [1]_, we store each set of structural
466 restrictions separately as a set of possible candidate nodes rather than computing
467 the intersection of that set with the known graph candidates for the subgraph node.
468 We delay taking the intersection until that node is selected to be in the mapping.
469 While choosing the node with fewest candidates, we avoid computing the intersection
470 by using the size of the minimal set to be intersected rather than the size of the
471 intersection. This may make the node ordering slightly worse via a savings of
472 many intersections most of which are not ever needed.
474 References
475 ----------
476 .. [1] M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle,
477 M. Pickavet, "The Index-Based Subgraph Matching Algorithm with General
478 Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph
479 Enumeration", PLoS One 9(5): e97896, 2014.
480 https://doi.org/10.1371/journal.pone.0097896
481 .. [2] https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph
482 .. [3] Hadi Katebi, Karem A. Sakallah and Igor L. Markov
483 "Graph Symmetry Detection and Canonical Labeling: Differences and Synergies"
484 in "Turing-100. The Alan Turing Centenary" Ed: A. Voronkov p. 181 -- 195, (2012).
485 https://doi.org/10.29007/gzc1 https://arxiv.org/abs/1208.6271
486 """
488 def __init__(self, graph, subgraph, node_match=None, edge_match=None, cache=None):
489 """
490 Parameters
491 ----------
492 graph: networkx.Graph
493 subgraph: networkx.Graph
494 node_match: collections.abc.Callable or None
495 Function used to determine whether two nodes are equivalent. Its
496 signature should look like ``f(n1: dict, n2: dict) -> bool``, with
497 `n1` and `n2` node property dicts. See also
498 :func:`~networkx.algorithms.isomorphism.categorical_node_match` and
499 friends.
500 If `None`, all nodes are considered equal.
501 edge_match: collections.abc.Callable or None
502 Function used to determine whether two edges are equivalent. Its
503 signature should look like ``f(e1: dict, e2: dict) -> bool``, with
504 `e1` and `e2` edge property dicts. See also
505 :func:`~networkx.algorithms.isomorphism.categorical_edge_match` and
506 friends.
507 If `None`, all edges are considered equal.
508 cache: collections.abc.Mapping
509 A cache used for caching graph symmetries.
510 """
511 if graph.is_directed() != subgraph.is_directed():
512 raise ValueError("Directed and undirected graphs cannot be compared.")
514 # TODO: allow for precomputed partitions and colors
515 self.graph = graph
516 self.subgraph = subgraph
517 self._symmetry_cache = cache
518 # Naming conventions are taken from the original paper.
519 # For your sanity:
520 # sg: subgraph
521 # g: graph
522 # e: edge(s)
523 # n: node(s)
524 # So: sgn means "subgraph nodes".
525 node_parts = self.create_aligned_partitions(
526 node_match, self.subgraph.nodes, self.graph.nodes
527 )
528 self._sgn_partition, self._gn_partition, self.N_node_colors = node_parts
529 self._sgn_colors = node_to_part_ID_dict(self._sgn_partition)
530 self._gn_colors = node_to_part_ID_dict(self._gn_partition)
532 edge_partitions = self.create_aligned_partitions(
533 edge_match, self.subgraph.edges(), self.graph.edges()
534 )
535 self._sge_partition, self._ge_partition, self.N_edge_colors = edge_partitions
536 if self.graph.is_directed():
537 self._sge_colors = node_to_part_ID_dict(self._sge_partition)
538 self._ge_colors = node_to_part_ID_dict(self._ge_partition)
539 else: # allow lookups (u, v) or (v, u)
540 self._sge_colors = EdgeLookup(node_to_part_ID_dict(self._sge_partition))
541 self._ge_colors = EdgeLookup(node_to_part_ID_dict(self._ge_partition))
543 def create_aligned_partitions(self, thing_matcher, sg_things, g_things):
544 """Partitions of "things" (nodes or edges) from subgraph and graph
545 based on function `thing_matcher`.
547 Returns: sg_partition, g_partition, number_of_matched_parts
549 The first `number_of_matched_parts` parts in each partition
550 match in order, e.g. 2nd part matches other's 2nd part.
551 Warning: nodes in parts after that have no matching nodes in the other graph.
552 For morphisms those nodes can't appear in the mapping.
553 """
554 if thing_matcher is None:
555 sg_partition = [set(sg_things)]
556 g_partition = [set(g_things)]
557 return sg_partition, g_partition, 1
559 # Use thing_matcher to create a partition
560 # Note: isinstance(G.edges(), OutEdgeDataView) is only true for multi(di)graph
561 sg_multiedge = isinstance(sg_things, nx.classes.reportviews.OutEdgeDataView)
562 g_multiedge = isinstance(g_things, nx.classes.reportviews.OutEdgeDataView)
563 if not sg_multiedge:
565 def sg_match(thing1, thing2):
566 return thing_matcher(sg_things[thing1], sg_things[thing2])
568 else: # multiedges (note nodes of multigraphs use simple case above)
570 def sg_match(thing1, thing2):
571 (u1, v1), (u2, v2) = thing1, thing2
572 return thing_matcher(self.subgraph[u1][v1], self.subgraph[u2][v2])
574 if not g_multiedge:
576 def g_match(thing1, thing2):
577 return thing_matcher(g_things[thing1], g_things[thing2])
579 else: # multiedges (note nodes of multigraphs use simple case above)
581 def g_match(thing1, thing2):
582 (u1, v1), (u2, v2) = thing1, thing2
583 return thing_matcher(self.graph[u1][v1], self.graph[u2][v2])
585 sg_partition = make_partition(sg_things, sg_match)
586 g_partition = make_partition(g_things, g_match)
588 # Align order of g_partition to that of sg_partition
589 sgc_to_gc = {}
590 gc_to_sgc = {}
591 sN, N = len(sg_partition), len(g_partition)
592 for sgc, gc in itertools.product(range(sN), range(N)):
593 sgt = next(iter(sg_partition[sgc]))
594 gt = next(iter(g_partition[gc]))
595 sgt_ = sg_things[sgt] if not sg_multiedge else self.subgraph[sgt[0]][sgt[1]]
596 gt_ = g_things[gt] if not g_multiedge else self.graph[gt[0]][gt[1]]
597 if thing_matcher(sgt_, gt_):
598 # TODO: remove these two if-checks when confident they never arise
599 # The `check` feature in match_partitions should ensure they do not
600 if sgc in sgc_to_gc:
601 raise nx.NetworkXError(
602 f"\nMatching function {thing_matcher} seems faulty.\n"
603 f"Partition found: {sg_partition=}\n"
604 f"So {sgt} in subgraph part {sg_partition[sgc]} matches two "
605 f"graph parts {g_partition[gc]} and "
606 f"{g_partition[sgc_to_gc[sgc]]}\n"
607 )
608 if gc in gc_to_sgc:
609 raise nx.NetworkXError(
610 f"\nMatching function seems broken: {thing_matcher}\n"
611 f"Partitions found: {g_partition=} {sg_partition=}\n"
612 f"So {gt} in graph part {g_partition[gc]} matches two "
613 f"subgraph parts {sg_partition[sgc]} and "
614 f"{sg_partition[gc_to_sgc[gc]]}\n"
615 )
616 sgc_to_gc[sgc] = gc
617 gc_to_sgc[gc] = sgc
618 ## return two lists and the number of partitions that match.
619 new_order = [
620 (sg_partition[sgc], g_partition[gc]) for sgc, gc in sgc_to_gc.items()
621 ]
622 Ncolors = len(new_order)
623 if Ncolors:
624 new_sg_p, new_g_p = [list(x) for x in zip(*new_order)]
625 else:
626 new_sg_p, new_g_p = [], []
627 if Ncolors < sN:
628 extra = [sg_partition[c] for c in range(sN) if c not in sgc_to_gc]
629 new_sg_p = list(new_sg_p) + extra
630 new_g_p = list(new_g_p) + [set()] * len(extra)
631 if Ncolors < N:
632 extra = [g_partition[c] for c in range(N) if c not in gc_to_sgc]
633 new_g_p = list(new_g_p) + extra
634 new_sg_p = list(new_sg_p) + [set()] * len(extra)
636 return new_sg_p, new_g_p, Ncolors
638 def find_isomorphisms(self, symmetry=True):
639 """Find all subgraph isomorphisms between subgraph and graph
641 Finds isomorphisms where :attr:`subgraph` <= :attr:`graph`.
643 Parameters
644 ----------
645 symmetry: bool
646 Whether symmetry should be taken into account. If False, found
647 isomorphisms may be symmetrically equivalent.
649 Yields
650 ------
651 dict
652 The found isomorphism mappings of {graph_node: subgraph_node}.
653 """
654 # The networkx VF2 algorithm is slightly funny in when it yields an
655 # empty dict and when not.
656 if not self.subgraph:
657 yield {}
658 return
659 elif not self.graph:
660 return
661 elif len(self.graph) < len(self.subgraph):
662 return
663 elif len(self._sgn_partition) > self.N_node_colors:
664 # some subgraph nodes have a color that doesn't occur in graph
665 return
666 elif len(self._sge_partition) > self.N_edge_colors:
667 # some subgraph edges have a color that doesn't occur in graph
668 return
670 if symmetry:
671 cosets = self.analyze_subgraph_symmetry()
672 # Turn cosets into constraints.
673 constraints = [(n, co) for n, cs in cosets.items() for co in cs if n != co]
674 else:
675 constraints = []
677 cand_sets = self._get_node_color_candidate_sets()
679 lookahead_candidates = self._get_color_degree_candidates()
680 for sgn, lookahead_cands in lookahead_candidates.items():
681 cand_sets[sgn].add(frozenset(lookahead_cands))
683 if any(cand_sets.values()):
684 # Choose start node based on a heuristic for the min # of candidates
685 # Heuristic here is length of smallest frozenset in candidates' set
686 # of frozensets for that node. Using the smallest length avoids
687 # computing the intersection of the frozensets for each node.
688 start_sgn = min(cand_sets, key=lambda n: min(len(x) for x in cand_sets[n]))
689 cand_sets[start_sgn] = (frozenset.intersection(*cand_sets[start_sgn]),)
690 yield from self._map_nodes(start_sgn, cand_sets, constraints)
691 return
693 def _get_color_degree_candidates(self):
694 """
695 Returns a mapping of {subgraph node: set of graph nodes} for
696 which the graph nodes are feasible mapping candidate_sets for the
697 subgraph node, as determined by looking ahead one edge.
698 """
699 g_deg = color_degree_by_node(self.graph, self._gn_colors, self._ge_colors)
700 sg_deg = color_degree_by_node(self.subgraph, self._sgn_colors, self._sge_colors)
702 return {
703 sgn: {
704 gn
705 for gn, (_, *g_counts) in g_deg.items()
706 if all(
707 sg_cnt <= g_counts[idx][color]
708 for idx, counts in enumerate(needed_counts)
709 for color, sg_cnt in counts.items()
710 )
711 }
712 for sgn, (_, *needed_counts) in sg_deg.items()
713 }
715 def largest_common_subgraph(self, symmetry=True):
716 """
717 Find the largest common induced subgraphs between :attr:`subgraph` and
718 :attr:`graph`.
720 Parameters
721 ----------
722 symmetry: bool
723 Whether symmetry should be taken into account. If False, found
724 largest common subgraphs may be symmetrically equivalent.
726 Yields
727 ------
728 dict
729 The found isomorphism mappings of {graph_node: subgraph_node}.
730 """
731 # The networkx VF2 algorithm is slightly funny in when it yields an
732 # empty dict and when not.
733 if not self.subgraph:
734 yield {}
735 return
736 elif not self.graph:
737 return
739 if symmetry:
740 cosets = self.analyze_subgraph_symmetry()
741 # Turn cosets into constraints.
742 constraints = [(n, cn) for n, cs in cosets.items() for cn in cs if n != cn]
743 else:
744 constraints = []
746 candidate_sets = self._get_node_color_candidate_sets()
748 if any(candidate_sets.values()):
749 relevant_parts = self._sgn_partition[: self.N_node_colors]
750 to_be_mapped = {frozenset(n for p in relevant_parts for n in p)}
751 yield from self._largest_common_subgraph(
752 candidate_sets, constraints, to_be_mapped
753 )
754 else:
755 return
757 def analyze_subgraph_symmetry(self):
758 """
759 Find a minimal set of permutations and corresponding co-sets that
760 describe the symmetry of ``self.subgraph``, given the node and edge
761 equalities given by `node_partition` and `edge_colors`, respectively.
763 Returns
764 -------
765 dict[collections.abc.Hashable, set[collections.abc.Hashable]]
766 The found co-sets. The co-sets is a dictionary of
767 ``{node key: set of node keys}``.
768 Every key-value pair describes which ``values`` can be interchanged
769 without changing nodes less than ``key``.
770 """
771 partition, edge_colors = self._sgn_partition, self._sge_colors
773 if self._symmetry_cache is not None:
774 key = hash(
775 (
776 tuple(self.subgraph.nodes),
777 tuple(self.subgraph.edges),
778 tuple(map(tuple, node_partition)),
779 tuple(edge_colors.items()),
780 self.subgraph.is_directed(),
781 )
782 )
783 if key in self._symmetry_cache:
784 return self._symmetry_cache[key]
785 partition = self._refine_node_partition(self.subgraph, partition, edge_colors)
786 cosets = self._process_ordered_pair_partitions(
787 self.subgraph, partition, partition, edge_colors
788 )
789 if self._symmetry_cache is not None:
790 self._symmetry_cache[key] = cosets
791 return cosets
793 def is_isomorphic(self, symmetry=False):
794 """
795 Returns True if :attr:`graph` is isomorphic to :attr:`subgraph` and
796 False otherwise.
798 Returns
799 -------
800 bool
801 """
802 return len(self.subgraph) == len(self.graph) and self.subgraph_is_isomorphic(
803 symmetry
804 )
806 def subgraph_is_isomorphic(self, symmetry=False):
807 """
808 Returns True if a subgraph of :attr:`graph` is isomorphic to
809 :attr:`subgraph` and False otherwise.
811 Returns
812 -------
813 bool
814 """
815 # symmetry=False, since we only need to know whether there is any
816 # example; figuring out all symmetry elements probably costs more time
817 # than it gains.
818 isom = next(self.subgraph_isomorphisms_iter(symmetry=symmetry), None)
819 return isom is not None
821 def isomorphisms_iter(self, symmetry=True):
822 """
823 Does the same as :meth:`find_isomorphisms` if :attr:`graph` and
824 :attr:`subgraph` have the same number of nodes.
825 """
826 if len(self.graph) == len(self.subgraph):
827 yield from self.subgraph_isomorphisms_iter(symmetry=symmetry)
829 def subgraph_isomorphisms_iter(self, symmetry=True):
830 """Alternative name for :meth:`find_isomorphisms`."""
831 return self.find_isomorphisms(symmetry)
833 def _get_node_color_candidate_sets(self):
834 """
835 Per node in subgraph find all nodes in graph that have the same color.
836 Stored as a dict-of-set-of-frozenset. The dict is keyed by node to a
837 collection of frozensets of graph nodes. Each of these frozensets are
838 a restriction. The node can be mapped only to nodes in the frozenset.
839 Thus it must be mapped to nodes in the intersection of all these sets.
840 We store the sets to delay taking the intersection of them. This helps
841 for two reasons: Firstly any duplicate restriction sets can be ignored;
842 Secondly, some nodes will not need the intersection to be constructed.
843 Note: a dict-of-list-of-set would store duplicate sets in the list and
844 we want to avoid that. But I wonder if checking hash/equality when `add`ing
845 removes the benefit of avoiding computing intersections.
846 """
847 candidate_sets = defaultdict(set)
848 for sgn in self.subgraph.nodes:
849 sgn_color = self._sgn_colors[sgn]
850 if sgn_color >= self.N_node_colors: # color has no candidates
851 candidate_sets[sgn] # creates empty set entry in defaultdict
852 else:
853 candidate_sets[sgn].add(frozenset(self._gn_partition[sgn_color]))
854 return dict(candidate_sets)
856 @classmethod
857 def _refine_node_partition(cls, graph, partition, edge_colors):
858 def equal_color(node1, node2):
859 return color_degree[node1] == color_degree[node2]
861 node_colors = node_to_part_ID_dict(partition)
862 color_degree = color_degree_by_node(graph, node_colors, edge_colors)
863 while not all(are_all_equal(color_degree[n] for n in p) for p in partition):
864 partition = [
865 p
866 for part in partition
867 for p in (
868 [part]
869 if are_all_equal(color_degree[n] for n in part)
870 else sorted(make_partition(part, equal_color, check=False), key=len)
871 )
872 ]
873 node_colors = node_to_part_ID_dict(partition)
874 color_degree = color_degree_by_node(graph, node_colors, edge_colors)
875 return partition
877 def _map_nodes(self, sgn, candidate_sets, constraints, to_be_mapped=None):
878 """
879 Find all subgraph isomorphisms honoring constraints.
880 The collection `candidate_sets` is stored as a dict-of-set-of-frozenset.
881 The dict is keyed by node to a collection of candidate frozensets. Any
882 viable candidate must belong to all the frozensets in the collection.
883 So each frozenset added to the collection is a restriction on the candidates.
885 According to the paper, we store the collection of sets rather than their
886 intersection to delay computing many intersections with the hope of avoiding
887 them completely. Having the middle collection be a set also means that
888 duplicate restrictions on candidates are ignored, avoiding another intersection.
889 """
890 # shortcuts for speed
891 subgraph = self.subgraph
892 subgraph_adj = subgraph._adj
893 graph = self.graph
894 graph_adj = graph._adj
895 self_ge_partition = self._ge_partition
896 self_sge_colors = self._sge_colors
897 is_directed = subgraph.is_directed()
899 gn_ID_to_node = list(graph)
900 gn_node_to_ID = {n: id for id, n in enumerate(graph)}
902 mapping = {}
903 rev_mapping = {}
904 if to_be_mapped is None:
905 to_be_mapped = subgraph_adj.keys()
907 # Note that we don't copy candidates here. This means we leak
908 # information between the branches of the search. This is intentional!
909 # Specifically, we modify candidates here. That's OK because we substitute
910 # the set of frozensets with a set containing the frozenset intersection.
911 # So, it doesn't change the membership rule or the length rule for sorting.
912 # Membership: any candidate must be an element of each of the frozensets.
913 # Length: length of the intersection set. Use heuristic min(len of frozensets).
914 # This intersection improves future length heuristics which can only occur
915 # after this element of the queu is popped. But it means future additional
916 # restriction frozensets that duplicate previous ones are not ignored.
917 sgn_candidates = frozenset.intersection(*candidate_sets[sgn])
918 candidate_sets[sgn] = {sgn_candidates}
919 queue = [(sgn, candidate_sets, iter(sgn_candidates))]
920 while queue: # DFS over all possible mappings
921 sgn, candidate_sets, sgn_cand_iter = queue[-1]
923 for gn in sgn_cand_iter:
924 # We're going to try to map sgn to gn.
925 if gn in rev_mapping:
926 continue # pragma: no cover
928 # REDUCTION and COMBINATION
929 if sgn in mapping:
930 old_gn = mapping[sgn]
931 del rev_mapping[old_gn]
932 mapping[sgn] = gn
933 rev_mapping[gn] = sgn
934 # BASECASE
935 if len(mapping) == len(to_be_mapped):
936 yield rev_mapping.copy()
937 del mapping[sgn]
938 del rev_mapping[gn]
939 continue
940 left_to_map = to_be_mapped - mapping.keys()
942 # We copy the candidates dict. But it is not a deepcopy.
943 # This avoids inner set copies, yet still allows updates b/c setitem
944 # changes sgn in new dict without changing original set.
945 # Below be careful to not change the sets of frozensets.
946 cand_sets = candidate_sets.copy()
948 # update the candidate_sets for unmapped sgn based on sgn mapped
949 if not is_directed:
950 sgn_nbrs = subgraph_adj[sgn]
951 not_gn_nbrs = graph_adj.keys() - graph_adj[gn].keys()
952 for sgn2 in left_to_map:
953 # edge color must match when sgn2 connected to sgn
954 if sgn2 not in sgn_nbrs:
955 gn2_cands = not_gn_nbrs
956 else:
957 g_edges = self_ge_partition[self_sge_colors[sgn, sgn2]]
958 gn2_cands = {n for e in g_edges if gn in e for n in e}
959 # Node color compatibility should be taken care of by the
960 # initial candidate lists made by find_subgraphs
962 # Add gn2_cands to the right collection.
963 # Do not change the original set. So do not use |= operator
964 cand_sets[sgn2] = cand_sets[sgn2] | {frozenset(gn2_cands)}
965 else: # directed
966 sgn_nbrs = subgraph_adj[sgn].keys()
967 sgn_preds = subgraph._pred[sgn].keys()
968 not_gn_nbrs = (
969 graph_adj.keys() - graph_adj[gn].keys() - graph._pred[gn].keys()
970 )
971 for sgn2 in left_to_map:
972 # edge color must match when sgn2 connected to sgn
973 if sgn2 not in sgn_nbrs:
974 if sgn2 not in sgn_preds:
975 gn2_cands = not_gn_nbrs
976 else: # sgn2 in sgn_preds
977 g_edges = self_ge_partition[self_sge_colors[sgn2, sgn]]
978 gn2_cands = {e[0] for e in g_edges if gn == e[1]}
979 else:
980 if sgn2 not in sgn_preds:
981 g_edges = self_ge_partition[self_sge_colors[sgn, sgn2]]
982 gn2_cands = {e[1] for e in g_edges if gn == e[0]}
983 else:
984 # gn2 must have correct color in both directions
985 g_edges = self_ge_partition[self_sge_colors[sgn, sgn2]]
986 gn2_cands = {e[1] for e in g_edges if gn == e[0]}
987 g_edges = self_ge_partition[self_sge_colors[sgn2, sgn]]
988 gn2_cands &= {e[0] for e in g_edges if gn == e[1]}
989 # Do not change the original set. So do not use |= operator
990 cand_sets[sgn2] = cand_sets[sgn2] | {frozenset(gn2_cands)}
992 for sgn2 in left_to_map:
993 # symmetry must match. constraints mean gn2>gn iff sgn2>sgn
994 if (sgn, sgn2) in constraints:
995 gn2_cands = set(gn_ID_to_node[gn_node_to_ID[gn] + 1 :])
996 elif (sgn2, sgn) in constraints:
997 gn2_cands = set(gn_ID_to_node[: gn_node_to_ID[gn]])
998 else:
999 continue # pragma: no cover
1000 # Do not change the original set. So do not use |= operator
1001 cand_sets[sgn2] = cand_sets[sgn2] | {frozenset(gn2_cands)}
1003 # The next node is the one that is unmapped and has fewest candidates
1004 # Use the heuristic of the min size of the frozensets rather than
1005 # intersection of all frozensets to delay computing intersections.
1006 new_sgn = min(
1007 left_to_map, key=lambda n: min(len(x) for x in cand_sets[n])
1008 )
1009 new_sgn_candidates = frozenset.intersection(*cand_sets[new_sgn])
1010 if not new_sgn_candidates:
1011 continue
1012 cand_sets[new_sgn] = {new_sgn_candidates}
1013 queue.append((new_sgn, cand_sets, iter(new_sgn_candidates)))
1014 break
1015 else: # all gn candidates tried for sgn.
1016 queue.pop()
1017 if sgn in mapping:
1018 del rev_mapping[mapping[sgn]]
1019 del mapping[sgn]
1021 def _largest_common_subgraph(self, candidates, constraints, to_be_mapped=None):
1022 """
1023 Find all largest common subgraphs honoring constraints.
1024 """
1025 # to_be_mapped is a set of frozensets of subgraph nodes
1026 if to_be_mapped is None:
1027 to_be_mapped = {frozenset(self.subgraph.nodes)}
1029 # The LCS problem is basically a repeated subgraph isomorphism problem
1030 # with smaller and smaller subgraphs. We store the nodes that are
1031 # "part of" the subgraph in to_be_mapped, and we make it a little
1032 # smaller every iteration.
1034 current_size = len(next(iter(to_be_mapped), []))
1036 found_iso = False
1037 if current_size <= len(self.graph):
1038 # There's no point in trying to find isomorphisms of
1039 # graph >= subgraph if subgraph has more nodes than graph.
1041 # Try the isomorphism first with the nodes with lowest ID. So sort
1042 # them. Those are more likely to be part of the final correspondence.
1043 # In theory, this makes finding the first answer(s) faster.
1044 for nodes in sorted(to_be_mapped, key=sorted):
1045 # Find the isomorphism between subgraph[to_be_mapped] <= graph
1046 next_sgn = min(nodes, key=lambda n: min(len(x) for x in candidates[n]))
1047 isomorphs = self._map_nodes(
1048 next_sgn, candidates, constraints, to_be_mapped=nodes
1049 )
1051 # This is effectively `yield from isomorphs`, except that we look
1052 # whether an item was yielded.
1053 try:
1054 item = next(isomorphs)
1055 except StopIteration:
1056 pass
1057 else:
1058 yield item
1059 yield from isomorphs
1060 found_iso = True
1062 # BASECASE
1063 if found_iso or current_size == 1:
1064 # Shrinking has no point because either 1) we end up with a smaller
1065 # common subgraph (and we want the largest), or 2) there'll be no
1066 # more subgraph.
1067 return
1069 left_to_be_mapped = set()
1070 for nodes in to_be_mapped:
1071 for sgn in nodes:
1072 # We're going to remove sgn from to_be_mapped, but subject to
1073 # symmetry constraints. We know that for every constraint we
1074 # have those subgraph nodes are equal. So whenever we would
1075 # remove the lower part of a constraint, remove the higher
1076 # instead. This is all dealth with by _remove_node. And because
1077 # left_to_be_mapped is a set, we don't do double work.
1079 # And finally, make the subgraph one node smaller.
1080 # REDUCTION
1081 new_nodes = self._remove_node(sgn, nodes, constraints)
1082 left_to_be_mapped.add(new_nodes)
1083 # COMBINATION
1084 yield from self._largest_common_subgraph(
1085 candidates, constraints, to_be_mapped=left_to_be_mapped
1086 )
1088 @staticmethod
1089 def _remove_node(node, nodes, constraints):
1090 """
1091 Returns a new set where node has been removed from nodes, subject to
1092 symmetry constraints. We know, that for every constraint we have
1093 those subgraph nodes are equal. So whenever we would remove the
1094 lower part of a constraint, remove the higher instead.
1095 """
1096 while True:
1097 for low, high in constraints:
1098 if low == node and high in nodes:
1099 node = high
1100 break
1101 else: # no break, couldn't find node in constraints
1102 return frozenset(nodes - {node})
1104 @staticmethod
1105 def _get_permutations_by_length(items):
1106 """
1107 Get all permutations of items, but only permute items with the same
1108 length.
1110 >>> found = list(ISMAGS._get_permutations_by_length([{1}, {2}, {3, 4}, {4, 5}]))
1111 >>> answer = [
1112 ... (({1}, {2}), ({3, 4}, {4, 5})),
1113 ... (({1}, {2}), ({4, 5}, {3, 4})),
1114 ... (({2}, {1}), ({3, 4}, {4, 5})),
1115 ... (({2}, {1}), ({4, 5}, {3, 4})),
1116 ... ]
1117 >>> found == answer
1118 True
1119 """
1120 by_len = defaultdict(list)
1121 for item in items:
1122 by_len[len(item)].append(item)
1124 return list(
1125 itertools.product(
1126 *(itertools.permutations(by_len[l]) for l in sorted(by_len))
1127 )
1128 )
1130 def _refine_opp(cls, graph, top, bottom, edge_colors):
1131 def equal_color(node1, node2):
1132 return color_degree[node1] == color_degree[node2]
1134 top = cls._refine_node_partition(graph, top, edge_colors)
1136 possible_bottoms = [bottom]
1137 while possible_bottoms:
1138 bottom = possible_bottoms.pop()
1139 node_colors = node_to_part_ID_dict(bottom)
1140 color_degree = color_degree_by_node(graph, node_colors, edge_colors)
1141 if all(are_all_equal(color_degree[n] for n in p) for p in bottom):
1142 if len(top) == len(bottom):
1143 yield top, bottom
1144 # else Non-isomorphic OPP (pruned here)
1145 # either way continue to next possible bottom
1146 continue
1147 # refine bottom partition
1148 more_bottoms = [[]]
1149 for part in bottom:
1150 if len(part) == 1 or are_all_equal(color_degree[node] for node in part):
1151 for new_bottom in more_bottoms:
1152 new_bottom.append(part)
1153 else:
1154 # This part needs to be refined
1155 refined_part = make_partition(part, equal_color, check=False)
1156 R = len(refined_part)
1157 if R == 1 or R == len({len(p) for p in refined_part}):
1158 # no two parts have same length -- simple case
1159 for n_p in more_bottoms:
1160 n_p.extend(sorted(refined_part, key=len))
1161 else:
1162 # Any part might match any other part with the same size.
1163 # Before refinement they were the same color. So we need to
1164 # include all possible orderings/colors within each size.
1165 permutations = cls._get_permutations_by_length(refined_part)
1166 # Add all permutations of the refined parts to each possible
1167 # bottom. So the number of new possible bottoms is multiplied
1168 # by the number of permutations of the refined parts.
1169 new_partitions = []
1170 for new_partition in more_bottoms:
1171 for p in permutations:
1172 # p is tuple-of-tuples-of-sets. Flatten to list-of-sets
1173 flat_p = [s for tup in p for s in tup]
1174 new_partitions.append(new_partition + flat_p)
1175 more_bottoms = new_partitions
1177 # reverse more_bottoms to keep the "finding identity" bottom first
1178 possible_bottoms.extend(more_bottoms[::-1])
1180 @staticmethod
1181 def _find_permutations(top_partition, bottom_partition):
1182 """
1183 Return a set of 2-tuples of nodes. These nodes are not equal
1184 but are mapped to each other in the symmetry represented by this OPP.
1185 Swapping all the 2-tuples of nodes in this set permutes the nodes
1186 but retains the graph structure. Thus it is a symmetry of the subgraph.
1187 """
1188 # Find permutations
1189 permutations = set()
1190 for top, bot in zip(top_partition, bottom_partition):
1191 if len(top) > 1 or len(bot) > 1:
1192 # ignore parts with > 1 element when they are equal
1193 # These are called Matching OPPs in Katebi 2012.
1194 # Symmetries in matching partitions are built by considering
1195 # only parts that have 1 element.
1196 if top == bot:
1197 continue
1198 raise IndexError(
1199 "Not all nodes are matched. This is"
1200 f" impossible: {top_partition}, {bottom_partition}"
1201 )
1202 # top and bot have only one element
1203 elif top != bot:
1204 permutations.add(frozenset((next(iter(top)), next(iter(bot)))))
1205 return permutations
1207 def _process_ordered_pair_partitions(
1208 self,
1209 graph,
1210 top_partition,
1211 bottom_partition,
1212 edge_colors,
1213 ):
1214 if all(len(top) <= 1 for top in top_partition):
1215 # no symmetries. Each node unique.
1216 return {}
1218 # first mapping found is the identity mapping
1219 finding_identity = True
1221 orbit_id = {node: orbit_i for orbit_i, node in enumerate(graph)}
1222 orbits = [{node} for node in graph]
1223 cosets = {}
1225 node_to_ID = {n: i for i, n in enumerate(graph)}
1226 sort_by_ID = node_to_ID.__getitem__
1228 def _load_next_queue_entry(queue, top_partition, bottom_partition):
1229 # find smallest node (by ID) in a |part|>1 and its partition index
1230 unmapped_nodes = (
1231 (node_to_ID[node], node, idx)
1232 for idx, t_part in enumerate(top_partition)
1233 for node in t_part
1234 if len(t_part) > 1
1235 )
1236 _, node, part_i = min(unmapped_nodes)
1237 b_part = bottom_partition[part_i]
1238 node2_iter = iter(sorted(b_part, key=sort_by_ID))
1240 queue.append([top_partition, bottom_partition, node, part_i, node2_iter])
1242 queue = []
1243 _load_next_queue_entry(queue, top_partition, bottom_partition)
1245 while queue:
1246 tops, bottoms, node, part_i, node2_iter = queue[-1]
1248 for node2 in node2_iter:
1249 if node != node2 and orbit_id[node] == orbit_id[node2]:
1250 # Orbit prune
1251 continue
1253 # couple node to node2
1254 new_top_part = {node}
1255 new_bot_part = {node2}
1257 new_top = [top.copy() for top in tops]
1258 new_top[part_i] -= new_top_part
1259 new_top.insert(part_i, new_top_part)
1261 new_bot = [bot.copy() for bot in bottoms]
1262 new_bot[part_i] -= new_bot_part
1263 new_bot.insert(part_i, new_bot_part)
1265 # collect OPPs
1266 opps = self._refine_opp(graph, new_top, new_bot, edge_colors)
1267 new_q = []
1268 for opp in opps:
1269 # Use OPP to find any of: Identity, Automorphism or Matching OPPs
1270 # else load the OPP onto queue for further exploration
1271 # Note that we check for Orbit pruning later because orbits may
1272 # be updated while OPP is sitting on the queue.
1273 # Note that we check for Non-isomorphic OPPs in `_refine_opp`.
1274 if finding_identity:
1275 # Note: allow zero size parts in identity check
1276 # b/c largest_common_subgraph allows empty parts
1277 if all(len(top) <= 1 for top in opp[0]):
1278 # Identity found. Set flag. Can now prune Matching OPPs
1279 finding_identity = False
1280 continue
1281 elif all(len(t) <= 1 or t == b for t, b in zip(*opp)):
1282 # Found a symmetry! (Full mapping or Matching OPP)
1283 # update orbits using the permutations from the OPP.
1284 permutations = self._find_permutations(*opp)
1285 for n1, n2 in permutations:
1286 orb1 = orbit_id[n1]
1287 orb2 = orbit_id[n2]
1288 if orb1 != orb2:
1289 orbit_set2 = orbits[orb2]
1290 orbits[orb1].update(orbit_set2)
1291 orbits[orb2] = set()
1292 orbit_id.update((n, orb1) for n in orbit_set2)
1293 continue
1295 _load_next_queue_entry(new_q, *opp)
1296 # reverse order to maintain node order DFS (Identity comes first)
1297 queue.extend(new_q[::-1])
1298 break
1299 else: # no more node2 options
1300 queue.pop()
1301 if node not in cosets:
1302 # coset of `node` is its orbit at the time `node` has completed
1303 # its first DFS traversal. DFS is about to go to previous node.
1304 # Make copy so future orbit changes do not change the coset.
1305 cosets[node] = orbits[orbit_id[node]].copy()
1306 return cosets