ܛ7idZdgZddlZddlmZmZddlmZmZddl Z dZ d dZ dZ d ZGd d ZGd dZy)a) ISMAGS Algorithm ================ Provides a Python implementation of the ISMAGS algorithm. [1]_ ISMAGS does a symmetry analysis to find the constraints on isomorphisms if we preclude yielding isomorphisms that differ by a symmetry of the subgraph. For example, if the subgraph contains a 4-cycle, every isomorphism would have a symmetric version with the nodes rotated relative to the original isomorphism. By encoding these symmetries as constraints we reduce the search space for isomorphisms and we also simplify processing the resulting isomorphisms. ISMAGS finds (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 are an exponential number of isomorphisms that are symmetrically equivalent. In that case, the ISMAGS algorithm will provide only one isomorphism per symmetry group, speeding up finding isomorphisms and avoiding the task of post-processing many effectively identical isomorphisms. >>> petersen = nx.petersen_graph() >>> ismags = nx.isomorphism.ISMAGS(petersen, petersen) >>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=False)) >>> len(isomorphisms) 120 >>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=True)) >>> answer = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}] >>> answer == isomorphisms True 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 = nx.isomorphism.ISMAGS(graph1, graph2) >>> ismags.is_isomorphic() False >>> largest_common_subgraph = list(ismags.largest_common_subgraph()) >>> answer = [{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}] >>> answer == largest_common_subgraph True >>> ismags2 = nx.isomorphism.ISMAGS(graph2, graph1) >>> largest_common_subgraph = list(ismags2.largest_common_subgraph()) >>> answer = [ ... {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}, ... ] >>> answer == largest_common_subgraph True However, when not taking symmetry into account, it doesn't matter: >>> largest_common_subgraph = list(ismags.largest_common_subgraph(symmetry=False)) >>> answer = [ ... {1: 0, 0: 1, 2: 2}, ... {1: 0, 2: 1, 0: 2}, ... {2: 0, 1: 1, 3: 2}, ... {2: 0, 3: 1, 1: 2}, ... {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}, ... ] >>> answer == largest_common_subgraph True >>> largest_common_subgraph = list(ismags2.largest_common_subgraph(symmetry=False)) >>> answer = [ ... {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}, ... {1: 1, 0: 2, 2: 3}, ... {1: 1, 0: 2, 3: 3}, ... {2: 1, 0: 2, 1: 3}, ... {2: 1, 0: 2, 3: 3}, ... {3: 1, 0: 2, 1: 3}, ... {3: 1, 0: 2, 2: 3}, ... ] >>> answer == largest_common_subgraph True Notes ----- - 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. - With a method that yields subgraph isomorphisms, we can construct functions like ``is_subgraph_isomorphic`` by checking for any yielded mapping. And functions like ``is_isomorphic`` by checking whether the subgraph has the same number of nodes as the graph and is also subgraph isomorphic. This subpackage also allows a ``symmetry`` bool keyword argument so you can find isomorphisms with or without the symmetry constraints. - For more information, see [2]_ and the documentation for :class:`ISMAGS` which includes a description of the algorithm. References ---------- .. [1] 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 .. [2] https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph ISMAGSN)Counter defaultdict)reducewrapsc |j}t|dkDrd}t|dt |}t |dt fd|DS#t$rY6wxYw)af Returns ``True`` if and only if all elements in `iterable` are equal; and ``False`` otherwise. Parameters ---------- iterable: collections.abc.Iterable The container whose elements will be checked. Returns ------- bool ``True`` iff all elements in `iterable` compare equal, ``False`` otherwise. z7The function does not works on multidimensional arrays.Nc3(K|] }|k( ywN).0itemfirsts c/home/rose/Desktop/poly/venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/ismags.py z are_all_equal..s2tu})shapelenNotImplementedErrorAttributeErroriternextall)iterablermessageiteratorrs @r are_all_equalrsj 9 u:>OG%g.D 8H~H 4 E 22 22    s A A"!A"cg|D]K}D]2}tt|}||s!|j|9j|hM|r_t fdDst j ddt fdDst j ddDcgc] }t|c}Scc}w)a 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 match/tests so need to end up in the same part of the partition, and `False` otherwise. check : bool optional (default: True) If ``True``, check that the resulting partition satisfies the match criteria. Every item should match every item in its part and none outside the part. Returns ------- list[set] A partition as a list of sets (the parts). Each set contains some of the items in `items`, such that all items are in exactly one part and every pair of items in each part matches. The following will be true: ``all(thing_matcher(*pair) for pair in itertools.combinations(items, 2))`` 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``. The function `test` is assumed to be commutative: if ``test(a, b)`` returns ``True`` then ``test(b, a)`` returns ``True``. c3K|]6}tj|dD]\}}||xr ||8yw)N) itertools combinations)r partt1t2tests rrz!make_partition..sK !#00q9B RL )T"b\ )9 *!s.sg Rx#++B3B R  1T"b\!1 14 2 2sA A z;. Some items match multiple parts. This leads to partition=)rraddappendrnx NetworkXErrorset)itemsr&checkrr#p_itemr+s ` @rmake_partitionr4s@ID$t*%FD&!    dV $  !  ""3D6:,      ""3D6:,   #, ,)$CI) ,, ,s:Cc`t|Dcic]\}}|D]}||c}}}Scc}}}w)a# Creates a dictionary that maps each item in each part to the index of the part to which it belongs. Parameters ---------- partition: collections.abc.Sequence[collections.abc.Iterable] As returned by :func:`make_partition`. Returns ------- dict ) enumerate)r+IDr#nodes rnode_to_part_ID_dictr9s3&/y%9 K%9TddD"HdD%9 KK Ks)c  tt|kr0|jD]\}}|vs d|<|D] }d||f< |js>|jDcic]!\}tfd|Df#c}}S|jDcic]C\}tfd|Dtfd|jDfEc}}Scc}}wcc}}w)aReturns a dict by node to counts of edge and node color for that node. This returns a dict by node to a 2-tuple of node color and degree by (edge color and nbr color). E.g. ``{0: (1, {(0, 2): 5})}`` means that node ``0`` has node type 1 and has 5 edges of type 0 that go to nodes of type 2. Thus, this is a measure of degree (edge count) by color of edge and color of the node on the other side of that edge. For directed graphs the degree counts is a 2-tuple of (in, out) degree counts. Ideally, if edge_match is None, this could get simplified to just the node color on the other end of the edge. Similarly if node_match is None then only edge color is tracked. And if both are None, we simply count the number of edges. Nc36K|]}|f|fywr r r ve_colorsn_colorsus rrz'color_degree_by_node..s#$QDqhq!tnhqk%BDc36K|]}|f|fywr r r<s rrz'color_degree_by_node..s#@4aXad^Xa[14rAc36K|]}|f|fywr r r<s rrz'color_degree_by_node..s#F:aXad^Xa[1:rA)r adjacency is_directedr_pred)Gr?r>nnbrsr=r@s `` `rcolor_degree_by_noderJs  8}s1v{{}GAt " A%)HQTN% ==?;;= (4  W$QD$QQR R(  {{}   %GAt QK @4@ @ F1771:F F  %     s /&C9-AC?c"eZdZdZdZdZdZy) EdgeLookupaClass to handle getitem for undirected edges. Note that ``items()`` iterates over one of the two representations of the edge (u, v) and (v, u). So this technically doesn't violate the Mapping invariant that (k,v) pairs reported by ``items()`` satisfy ``.__getitem__(k) == v``. But we are violating the spirit of the protocol by having keys available for lookup by ``__getitem__`` that are not reported by ``items()``. Note that if we used frozensets for undirected edges we would have the same behavior we see here. You could ``__getitem__`` either ``{u, v}`` or ``{v, u}`` and get the same value -- yet ``items()`` would only report one of the two. So from that perspective we *are* following the Mapping protocol. Our keys are undirected edges. We are using 2-tuples as an imperfect representation of these edges. We are not using 2-tuples as keys. Only as imperfect edges and we use the edges as keys. c||_yr  edge_dict)selfrOs r__init__zEdgeLookup.__init__0s "cf||jvr|j|S|j|dddS)NrN)rPedges r __getitem__zEdgeLookup.__getitem__3s4 4>> !>>$' '~~d4R4j))rRc6|jjSr )rOr1)rPs rr1zEdgeLookup.items8s~~##%%rRN)__name__ __module__ __qualname____doc__rQrVr1r rRrrLrLs"#* &rRrLceZdZdZddZdZddZdZddZdZ dd Z dd Z dd Z dd Z d ZedZddZddZedZedZdZedZdZy)ra?, Implements the ISMAGS subgraph matching algorithm. [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. Attributes ---------- graph: networkx.Graph subgraph: networkx.Graph Notes ----- ISMAGS does a symmetry analysis to find the constraints on isomorphisms if we preclude yielding isomorphisms that differ by a symmetry of the subgraph. For example, if the subgraph is a 4-cycle, every isomorphism would have a symmetric version with the nodes rotated relative to the original isomorphism. By encoding these symmetries as constraints we reduce the search space for isomorphisms and we also simplify processing the resulting isomorphisms. **Symmetry Analysis** The constraints in ISMAGS are based off the handling in ``nauty`` and its many variants, in particular ``saucy``, as discussed in the ISMAGS paper [1]_. That paper cites [3]_ for details on symmetry handling. Figure 2 of [3]_ describes the DFS approach to symmetries used here and relying on a data structure called an Ordered Pair Partitions(OPP). This consists of a pair of partitions where each part represents nodes with the same degree-by-color over all colors. We refine these partitions simultaneously in a way to result in permutations of the nodes that preserve the graph structure. We thus find automorphisms for the subgraph of interest. From those we identify pairs of nodes which are structurally equivalent. We then constrain our problem by requiring the first of the pair to always be assigned first in the isomorphism -- thus constraining the isomorphisms reported to only one example from the set of all symmetrically equivalent isomorphisms. These constraints are computed once based on the subgraph symmetries and then used throughout the DFS search for isomorphisms. Finding the symmetries involves a DFS of the OPP wherein we "couple" a node to a node in its degree-by-color part of the partition. This "coupling" is done via assigning a new color in the top partition to the node being coupled, and the same new color in the bottom partition to the node being coupled to. This new color has only one node in each partition. The new color also requires that we "refine" both top and bottom partitions by splitting parts until each part represents a common degree-by-color value. Those refinements introduce new colors as the parts are split during refinement. Parts do not get combined during refinement. So the coupling/refining process always results in at least one new part with only one node in both the top and bottom partition. In practice we usually refine into many new one-node parts in both partitions. We continue in this way until each node has its own part/color in the top partition -- and the node in the bottom partition with that color is the symmetric node. That is, an OPP represents an automorphism, and thus a symmetry of the subgraph when each color has a single node in the top partition and a single node in the bottom partition. From those automorphisms we build up a set of nodes that can be obtained from each other by symmetry (they are mutually symmetric). That set of nodes is called an "orbit" of the subgraph under symmetry. After finding the orbits for one symmetry, we backtrack in the DFS by removing the latest coupling and replacing it with a coupling from the same top node to a new bottom node in its degree-by-color grouping. When all possible couplings for that node are considered we backtrack to the previously coupled node and recouple in a DFS manner. We can prune the DFS search tree in helpful ways. The paper [2]_ demonstrates 6 situations of interest in the DFS where pruning is possible: - An **Automorphism OPP** is an OPP where every part in both partitions contains a single node. The mapping/automorphism is found by mapping each top node to the bottom node in the same color part. For example, ``[({1}, {2}, {3}); ({2}, {3}, {1})]`` represents the mapping of each node to the next in a triangle. It rotates the nodes around the triangle. - The **Identity OPP** is the first automorphism found during the DFS. It appears on the left side of the DFS tree and is first due to our ordering of coupling nodes to be in an arbitrary but fixed ordering of the nodes. This automorphism does not show any symmetries, but it ensures the orbit for each node includes itself and it sets us up for handling the symmetries. Note that a subgraph with no symmetries will only have the identity automorphism. - A **Non-isomorphic OPP** occurs when refinement creates a different number of parts in the top partition than in the bottom partition. This means no symmetries will be found during further processing of that subtree of the DFS. We prune the subtree and continue. - A **Matching OPP** is such that each top part that has more than one node is in fact equal to the bottom part with the same color. The many-node-parts match exactly. The single-node parts then represent symmetries that do not permute any matching nodes. Matching OPPs arise while finding the Identity Mapping. But the single-node parts are identical in the two partitions, so no useful symmetries are found. But after the Identity Mapping is found, every Matching OPP encountered will have different nodes in at least two single-node parts of the same color. So these positions in the DFS provide us with symmetries without any need to find the whole automorphism. We can prune the subtree, update the orbits and backtrack. Any larger symmetries that combine these symmetries with symmetries of the many-node-parts do not need to be explored because the symmetry "generators" found in this way provide a basis for all symmetries. We will find the symmetry generators of the many-node-parts at another subtree of the DFS. - An **Orbit Pruning OPP** is an OPP where the node coupling to be considered next has both nodes already known to be in the same orbit. We have already identified those permutations when we discovered the orbit. So we can prune the resulting subtree. This is the primary pruning discussed in [1]_. - A **Coset Point** in the DFS is a point of the tree when a node is first back-tracked. That is, its couplings have all been analyzed once and we backtrack to its parent. So, said another way, when a node is backtracked to and is about to be mapped to a different node for the first time, its child in the DFS has been completely analysed. Thus the orbit for that child at this point in the DFS is the full orbit for symmetries involving only that child or larger nodes in the node order. All smaller nodes are mapped to themselves. This orbit is due to symmetries not involving smaller nodes. Such an orbit is called the "coset" of that node. The Coset Point does not lead to pruning or to more symmetries. It is the point in the process where we store the **coset** of the node being backtracked. We use the cosets to construct the symmetry constraints. Once the pruned DFS tree has been traversed, we have collected the cosets of some special nodes. Often most nodes are not coupled during the progression down the left side of the DFS. They are separated from other nodes during the partition refinement process after coupling. So they never get coupled directly. Thus the number of cosets we find is typically many fewer than the number of nodes. We turn those cosets into constraints on the nodes when building non-symmetric isomorphisms. The node whose coset is used is paired with each other node in the coset. These node-pairs form the constraints. During isomorphism construction we always select the first of the constraint before the other. This removes subtrees from the DFS traversal space used to build isomorphisms. The constraints we obtain via symmetry analysis of the subgraph are used for finding non-symmetric isomorphisms. We prune the isomorphism tree based on the constraints we obtain from the symmetry analysis. **Isomorphism Construction** Once we have symmetry constraints on the isomorphisms, ISMAGS constructs the allowed isomorphisms by mapping each node of the subgraph to all possible nodes (with the same degree-by-color) from the graph. We partition all nodes into degree-by-color parts and order the subgraph nodes we consider using smallest part size first. The idea is to try to map the most difficult subgraph nodes first (most difficult here means least number of graph candidates). By considering each potential subgraph node to graph candidate mapping image in turn, we perform a DFS traversal of partial mappings. If the mapping is rejected due to the graph neighbors not matching the degree-by-color of the subgraph neighbors, or rejected due to the constraints imposed from symmetry, we prune that subtree and consider a new graph candidate node for that subgraph node. When no more graph candidates remain we backtrack to the previous node in the mapping and consider a new graph candidate for that node. If we ever get to a depth where all subgraph nodes are mapped and no structural requirements or symmetry constraints are violated, we have found an isomorphism. We yield that mapping and backtrack to find other isomorphisms. As we visit more neighbors, the graph candidate nodes have to satisfy more structural restrictions. As described in the ISMAGS paper, [1]_, we store each set of structural restrictions separately as a set of possible candidate nodes rather than computing the intersection of that set with the known graph candidates for the subgraph node. We delay taking the intersection until that node is selected to be in the mapping. While choosing the node with fewest candidates, we avoid computing the intersection by using the size of the minimal set to be intersected rather than the size of the intersection. This may make the node ordering slightly worse via a savings of many intersections most of which are not ever needed. References ---------- .. [1] 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 .. [2] https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph .. [3] Hadi Katebi, Karem A. Sakallah and Igor L. Markov "Graph Symmetry Detection and Canonical Labeling: Differences and Synergies" in "Turing-100. The Alan Turing Centenary" Ed: A. Voronkov p. 181 -- 195, (2012). https://doi.org/10.29007/gzc1 https://arxiv.org/abs/1208.6271 Nch|j|jk7r td||_||_||_|j ||jj |jj }|\|_|_|_ t|j|_ t|j|_ |j ||jj|jj}|\|_|_|_|jjr5t|j|_t|j|_yt't|j|_t't|j|_y)a 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 :func:`~networkx.algorithms.isomorphism.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 :func:`~networkx.algorithms.isomorphism.categorical_edge_match` and friends. If `None`, all edges are considered equal. cache: collections.abc.Mapping A cache used for caching graph symmetries. z2Directed and undirected graphs cannot be compared.N)rE ValueErrorgraphsubgraph_symmetry_cachecreate_aligned_partitionsnodes_sgn_partition _gn_partition N_node_colorsr9 _sgn_colors _gn_colorsedges_sge_partition _ge_partition N_edge_colors _sge_colors _ge_colorsrL)rPr_r` node_match edge_matchcache node_partsedge_partitionss rrQzISMAGS.__init__s].    ("6"6"8 8QR R   $33  ++TZZ-=-= GQCT/1C/0C0CD.t/A/AB88  ++-tzz/?/?/A GVCT/1C :: ! ! #3D4G4GHD 243E3EFDO)*>t?R?R*STD ()=d>P>P)QRDOrRc.tg}tg}||dfSttjjj }ttjjj }|sfd}nfd}|sfd} nfd} t |}t | }i} i} t|t|} } tjt| t| D]\}}tt||}tt||}|s|nj|d|d}|s|nj|d|d}||s||| vr4tjdd|d |d ||d ||d || |d || vr7tjdd|d|d |d||d||d || |d || |<|| |<| j!Dcgc]\}}||||f}}}t|}|r#t#|Dcgc] }t%|c}\}}ngg}}|| krQt| Dcgc] }|| vs||}}t%||z}t%|tgt|zz}|| krQt| Dcgc] }|| vs||}}t%||z}t%|tgt|zz}|||fScc}}wcc}wcc}wcc}w)aPartitions of "things" (nodes or edges) from subgraph and graph based on function `thing_matcher`. Returns: sg_partition, g_partition, number_of_matched_parts The first `number_of_matched_parts` parts in each partition match in order, e.g. 2nd part matches other's 2nd part. Warning: nodes in parts after that have no matching nodes in the other graph. For morphisms those nodes can't appear in the mapping. r c"||Sr r )thing1thing2 sg_things thing_matchers rsg_matchz2ISMAGS.create_aligned_partitions..sg_match5s$Yv%6 &8IJJrRcl||c\}}\}}j||j||Sr )r`rvrwu1v1u2v2rPrys rrzz2ISMAGS.create_aligned_partitions..sg_match:s@%+V"R(2r$T]]2%6r%:DMM".g_match@s$Xf%5x7GHHrRcl||c\}}\}}j||j||Sr )r_r|s rrz1ISMAGS.create_aligned_partitions..g_matchEs>%+V"R(2r$TZZ^B%7B9KLLrRrz Matching function z- seems faulty. Partition found: sg_partition=z So z in subgraph part z matches two graph parts z and  z! Matching function seems broken: z Partitions found: g_partition=z sg_partition=z in graph part z matches two subgraph parts )r0 isinstancer.classes reportviewsOutEdgeDataViewr4rr!r(rangerrr`r_r/r1ziplist)rPryrxr sg_partition g_partition sg_multiedge g_multiedgerzr sgc_to_gc gc_to_sgcsNNsgcgcsgtgtsgt_gt_ new_orderNcolorsxnew_sg_pnew_g_pcextras```` rrbz ISMAGS.create_aligned_partitionss   N+Lx=/Ka/ /")RZZ-C-C-S-ST  2::+A+A+Q+QR  K  S I  M&i: $Xw7   L!3{#3A ((rE!H=GCtL-./Cd;r?+,B)59S>4==Q;PQTUVQW;XD&1(2,tzz"Q%7HA7OCT3')#**.}o>:,8?;!U"4\#5F4GH''22&7u&y~67r ;?**<]OL:-8N/L?K TR0AB**6s*;)8AJ@Q @QWS"\#  B 0@Q  i. 25y/ B/Qa/ B Hg "BgH R<.3BiNi1I;M\!_iENH~-H7msugE &::G Q;-21XLX)9K[^XEL7me+GH~#e*(<...s8VAQminrH cand_setss rz*ISMAGS.find_isomorphisms..sS8VST8V5VrRkey)r`r_rrdrfrjrlanalyze_subgraph_symmetryr1_get_node_color_candidate_sets_get_color_degree_candidatesr, frozensetanyvaluesr intersection _map_nodes) rPsymmetrycosetsrHcsco constraintslookahead_candidatessgnlookahead_cands start_sgnrs @rfind_isomorphismszISMAGS.find_isomorphisms~sn$}}H   _s4==1 1  $$ %(:(: :  $$ %(:(: :  335F06 Wuq"2qTVwAr77KWK779 #@@B$8$>$>$@ C cN  y9 :%A y! " I+VWI$-$:$:Ii.sB'? V)/ vhsmE22)73'?s03) rJr_rhrnr`rgrmr1rr6)rPg_degsg_degr_ needed_countsgnrs `rrz#ISMAGS._get_color_degree_candidatess %TZZ$//R%dmmT5E5EtGWGWX-3LLN   -;((a- */++-*7&BX'0'?*7 -;    s/ C +C:C C c#K|jsiy|jsy|rD|j}|jDcgc]\}}|D] }||k7s ||f}}}}ng}|j }t |j rH|jd|j}td|Dh} |j||| Ed{yycc}}}w7 w)a Find the largest common induced subgraphs between :attr:`subgraph` and :attr:`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}. Nc3.K|] }|D]}|ywr r )r prHs rrz1ISMAGS.largest_common_subgraph..s%KAAaas) r`r_rr1rrrrdrfr_largest_common_subgraph) rPrrrHrcnrcandidate_setsrelevant_parts to_be_mappeds rlargest_common_subgraphzISMAGS.largest_common_subgraphs$}}H   335F06 Wuq"2qTVwAr77KWK<<> ~$$& '!001E43E3EFN%%K%KKLL44 \   X s%AC$CC"A2C$C"C$c \|j|j}}|jtt |j j t |j jt tttt |j|j jf}||jvr|j|S|j|j ||}|j|j |||}|j||j<|S)aF Find a minimal set of permutations and corresponding co-sets that describe the symmetry of ``self.subgraph``, given the node and edge equalities given by `node_partition` and `edge_colors`, respectively. Returns ------- 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``. )rdrmrahashtupler`rcrimapnode_partitionr1rE_refine_node_partition _process_ordered_pair_partitions)rPr+ edge_colorsrrs rrz ISMAGS.analyze_subgraph_symmetrys"&!4!4d6F6F;    +$----.$----.#e^45+++-.MM--/ Cd***++C00// y+V 66 MM9i     +(.D  % rRc~t|jt|jk(xr|j|S)z Returns True if :attr:`graph` is isomorphic to :attr:`subgraph` and False otherwise. Returns ------- bool )rr`r_subgraph_is_isomorphicrPrs r is_isomorphiczISMAGS.is_isomorphics74==!S_4 9T9T :  rRcBt|j|d}|duS)z Returns True if a subgraph of :attr:`graph` is isomorphic to :attr:`subgraph` and False otherwise. Returns ------- bool rN)rsubgraph_isomorphisms_iter)rPrisoms rrzISMAGS.subgraph_is_isomorphic&s)D33X3FM4rRc#Kt|jt|jk(r|j|Ed{yy7w)z Does the same as :meth:`find_isomorphisms` if :attr:`graph` and :attr:`subgraph` have the same number of nodes. rN)rr_r`rrs risomorphisms_iterzISMAGS.isomorphisms_iter5s@ tzz?c$--0 0666I I I 1 IsAA A A c$|j|S)z/Alternative name for :meth:`find_isomorphisms`.)rrs rrz!ISMAGS.subgraph_isomorphisms_iter=s%%h//rRctt}|jjD]P}|j|}||j k\r||'||j t|j|Rt|S)ab Per node in subgraph find all nodes in graph that have the same color. Stored as a dict-of-set-of-frozenset. The dict is keyed by node to a collection of frozensets of graph nodes. Each of these frozensets are a restriction. The node can be mapped only to nodes in the frozenset. Thus it must be mapped to nodes in the intersection of all these sets. We store the sets to delay taking the intersection of them. This helps for two reasons: Firstly any duplicate restriction sets can be ignored; Secondly, some nodes will not need the intersection to be constructed. Note: a dict-of-list-of-set would store duplicate sets in the list and we want to avoid that. But I wonder if checking hash/equality when `add`ing removes the benefit of avoiding computing intersections. ) rr0r`rcrgrfr,rredict)rPrr sgn_colors rrz%ISMAGS._get_node_color_candidate_setsAsx%S)==&&C((-ID...s#s#'' $2D2DY2O(PQ ' N##rRc dfd}t|}t|||tfd|Dsw|Dcgc]=}tfd|Dr|gnt t ||dt D]}|?}}}t|}t|||tfd|Dsw|Scc}}w)Nc||k(Sr r node1node2 color_degrees r equal_colorz2ISMAGS._refine_node_partition..equal_colorZ&,u*== =rRc3FK|]}tfd|Dyw)c3(K|] }| ywr r r rHrs rrz:ISMAGS._refine_node_partition..._s#?QLOQrNrr rrs rrz0ISMAGS._refine_node_partition.._sSAm#?Q#??!c3(K|] }| ywr r rs rrz0ISMAGS._refine_node_partition..es$Cd\!_drFr2r)r9rJrrsortedr4r) clsr_r+rr node_colorsr#rrs @rrzISMAGS._refine_node_partitionXs >+95 +E; L SSS&%D%$Cd$CCFt[ NTWXYY% /y9K/{KPLSSSsAB,c #!K|j}|j}|j}|j}|j} |j} |j } t |} t|D cic]\} }||  }} }i}i}||j}tj||}|h||<||t|fg}|r|d\}}}|D]}||vr ||vr||}||=|||<|||<t|t|k(r|j||=||=O||jz }|j!| su||}|j||jz }|D]E}||vr|}n'| | ||f}|Dchc]}||vs|D]}|}}}!|t|hz!|<Gn7||j}|j|j}|j||jz |j|jz }|D]}||vr-||vr|}n| | ||f}|Dchc]}||dk(s |d}}nx||vr&| | ||f}|Dchc]}||dk(s |d}}nN| | ||f}|Dchc]}||dk(s |d}}| | ||f}||Dchc]}||dk(s |dc}z}!|t|hz!|<|D]K}||f|vrt| ||dzd}n||f|vrt| d||}n7!|t|hz!|<Mt!|!fd}tj!|} | s| h!|<|j#|!t| fn|j%||vr |||=||=|ryycc}} wcc}}wcc}wcc}wcc}wcc}ww)a Find all subgraph isomorphisms honoring constraints. The collection `candidate_sets` is stored as a dict-of-set-of-frozenset. The dict is keyed by node to a collection of candidate frozensets. Any viable candidate must belong to all the frozensets in the collection. So each frozenset added to the collection is a restriction on the candidates. According to the paper, we store the collection of sets rather than their intersection to delay computing many intersections with the hope of avoiding them completely. Having the middle collection be a set also means that duplicate restrictions on candidates are ignored, avoiding another intersection. NrTr rc.td|DS)Nc32K|]}t|ywr rrs rrz6ISMAGS._map_nodes....s2P.ss2P9Q<2P/PrRr)r`_adjr_rkrmrErr6keysrrrrcopyrFr0rr-pop)"rPrrrrr` subgraph_adjr_ graph_adjself_ge_partitionself_sge_colorsrE gn_ID_to_nodeidrH gn_node_to_IDmapping rev_mappingsgn_candidatesqueue sgn_cand_iterrold_gn left_to_mapsgn_nbrs not_gn_nbrssgn2 gn2_candsg_edgese sgn_predsnew_sgnnew_sgn_candidatesrs" @rrzISMAGS._map_nodesms==}}  JJ  ..****, U ,5e,<=,<52qB,< =  ',,.L#//1DE-.s~tN';<=16r .C#$'>$S\F#F+! "% Bw<3|#44%**,, #B*W\\^; +//1 #+C0H"+.."2Yr]5G5G5I"IK +x/(3I&7T 8R&SG4;(RGqrQwPQ1PQGI(R +4D/Yy=Q#GCL1 G)>t)S(-R-R-R-RsuA2O5 N5D O N;  N; B,O OO!O6 OO O O *O 1O O O CO3"Oc#VK| t|jjh}tt t |g}d}|t|j krWt|tD]C}t|fd}|j|||} t |} | |Ed{d}E|s|dk(ryt} |D]-}|D]&} |j| ||} | j| (/|j|| Ed{y7i#t$rYwxYw7w)zI Find all largest common subgraphs honoring constraints. NFrc.td|DS)Nc32K|]}t|ywr rrs rrzDISMAGS._largest_common_subgraph....s7V 1A rr)rH candidatess rrz1ISMAGS._largest_common_subgraph..sC7V ST 7V4VrR)rTr )rr`rcrrrr_rrr StopIterationr0 _remove_noder,r) rPr rr current_size found_isorcnext_sgn isomorphsrleft_to_be_mappedr new_nodess ` rrzISMAGS._largest_common_subgraphsH  %dmm&9&9:;L4\ 2B78  3tzz? * &9u*VW OOj+E, % ?DJ((( $I!:&  ) E!E!--c5+F !%%i0"00  2C1   3) %: sCBD) D# D),D-A#D)D'D) D$!D)#D$$D)cT |D]\}}||k(s ||vs|}nt||hz S()a& Returns a new set where node has been removed from nodes, subject to symmetry constraints. We know, that for every constraint we have those subgraph nodes are equal. So whenever we would remove the lower part of a constraint, remove the higher instead. )r)r8rcrlowhighs rr"zISMAGS._remove_node@sB( T$;45=D) !$00 rRctt|D]}t|j|!tt j fdt DS)a Get all permutations of items, but only permute items with the same length. >>> found = list(ISMAGS._get_permutations_by_length([{1}, {2}, {3, 4}, {4, 5}])) >>> answer = [ ... (({1}, {2}), ({3, 4}, {4, 5})), ... (({1}, {2}), ({4, 5}, {3, 4})), ... (({2}, {1}), ({3, 4}, {4, 5})), ... (({2}, {1}), ({4, 5}, {3, 4})), ... ] >>> found == answer True c3NK|]}tj|ywr )r! permutations)r lby_lens rrz5ISMAGS._get_permutations_by_length..fs!L^)((3^s"%)rrrr-r!r(r)r1rr0s @r_get_permutations_by_lengthz"ISMAGS._get_permutations_by_lengthPsY T"D 3t9  $ $T *   LVF^L   rRc #JKfd}|j|||}|g}|ru|j}t|}t|||t fd|Drt |t |k(r||f]gg}|D]} t | dk(st fd| Dr|D]} | j| >t| |d} t | } | dk(s%| t | D chc] } t | c} k(r(|D]"}|jt| t $|j| }g}|D]5}|D].} | Dcgc] }|D]}| }}}|j||z07|}|j|ddd|rtyycc} wcc}}ww) Nc||k(Sr r rs rrz'ISMAGS._refine_opp..equal_colorkrrRc3FK|]}tfd|Dyw)c3(K|] }| ywr r rs rrz/ISMAGS._refine_opp...us .usMf= .~s2WRV$<3ERVrFrrrT) rrr9rJrrrr-r4extendrr1)rr_topbottomrrpossible_bottomsr more_bottomsr# new_bottom refined_partRrn_pr.new_partitions new_partitiontupsflat_prs @r _refine_oppzISMAGS._refine_oppjs >(([A"8%))+F.v6K/{KPLMfMMs8s6{*v+%4Lt9>]2WRV2W%W&2 "))$/'3$2$ 5#QLL)AAvc<*H.s6 s3x1} Tc fdt|D}t|\}}}||}tt| }|j |||||gy)Nc3^K|]$\}}|D]}t|dkDr |||f&ywrNr)r rt_partr8 node_to_IDs rrzZISMAGS._process_ordered_pair_partitions.._load_next_queue_entry..sA#;KC"Dv;?D!4-".#;s*-r)r6rrrr-) rrHrIunmapped_nodesrr8part_ib_part node2_iterrT sort_by_IDs r_load_next_queue_entryzGISMAGS._process_ordered_pair_partitions.._load_next_queue_entrys\#,]#;N ".1OAtV%f-FfV<=J LL-)94T UrRrTc38K|]}t|dkywrNrrOs rrz:ISMAGS._process_ordered_pair_partitions..s?s3x1}rPrFc3LK|]\}}t|dkxs||k(ywrNr)r tbs rrz:ISMAGS._process_ordered_pair_partitions..s)Iytq!SVq[2AF2ys"$c3&K|]}|f ywr r )r rHorb1s rrz:ISMAGS._process_ordered_pair_partitions.. s/N:aD :s) rr6rVrinsertrErrKupdater0r7r)%rPr_rHrIrfinding_identityorbit_ir8orbit_idorbitsrirHrZrtopsbottomsrVrXr new_top_part new_bot_partr8new_toprJnew_botoppsnew_qoppr.n1n2orb2 orbit_set2rTr`rYs% @@@rrz'ISMAGS._process_ordered_pair_partitionss 6 6 6I 7@7GH7GmgtD'M7GH%*+UT4&U+'0'78'7tq!ad'78 ++  Vum5EF6;Bi 3D'4#5=Xd^x%F!%v %w 156#388:6</v|4189#388:9</v|4''wMC (?A??/4,$IsCyII(?t'>'>'D &2FB#+B#>#@F4Lyz kI+9@7:s H9 H? I6I 2I)NNNT)Fr )rXrYrZr[rQrbrrrrrrrrr classmethodrrr staticmethodr"r1rErKrr rRrrr<siV5Sn]*~5n ,(T"H    J0$.(N%`A F 1 1  208d4crRru)r[__all__r! collectionsrr functoolsrrnetworkxr.rr4r9rJrLrr rRrr|sOxt *,#3