diff env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/vf2userfunc.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/vf2userfunc.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,200 @@
+"""
+    Module to simplify the specification of user-defined equality functions for
+    node and edge attributes during isomorphism checks.
+
+    During the construction of an isomorphism, the algorithm considers two
+    candidate nodes n1 in G1 and n2 in G2.  The graphs G1 and G2 are then
+    compared with respect to properties involving n1 and n2, and if the outcome
+    is good, then the candidate nodes are considered isomorphic. NetworkX
+    provides a simple mechanism for users to extend the comparisons to include
+    node and edge attributes.
+
+    Node attributes are handled by the node_match keyword. When considering
+    n1 and n2, the algorithm passes their node attribute dictionaries to
+    node_match, and if it returns False, then n1 and n2 cannot be
+    considered to be isomorphic.
+
+    Edge attributes are handled by the edge_match keyword. When considering
+    n1 and n2, the algorithm must verify that outgoing edges from n1 are
+    commensurate with the outgoing edges for n2. If the graph is directed,
+    then a similar check is also performed for incoming edges.
+
+    Focusing only on outgoing edges, we consider pairs of nodes (n1, v1) from
+    G1 and (n2, v2) from G2. For graphs and digraphs, there is only one edge
+    between (n1, v1) and only one edge between (n2, v2). Those edge attribute
+    dictionaries are passed to edge_match, and if it returns False, then
+    n1 and n2 cannot be considered isomorphic. For multigraphs and
+    multidigraphs, there can be multiple edges between (n1, v1) and also
+    multiple edges between (n2, v2).  Now, there must exist an isomorphism
+    from "all the edges between (n1, v1)" to "all the edges between (n2, v2)".
+    So, all of the edge attribute dictionaries are passed to edge_match, and
+    it must determine if there is an isomorphism between the two sets of edges.
+"""
+
+from . import isomorphvf2 as vf2
+
+__all__ = ["GraphMatcher", "DiGraphMatcher", "MultiGraphMatcher", "MultiDiGraphMatcher"]
+
+
+def _semantic_feasibility(self, G1_node, G2_node):
+    """Returns True if mapping G1_node to G2_node is semantically feasible.
+    """
+    # Make sure the nodes match
+    if self.node_match is not None:
+        nm = self.node_match(self.G1.nodes[G1_node], self.G2.nodes[G2_node])
+        if not nm:
+            return False
+
+    # Make sure the edges match
+    if self.edge_match is not None:
+
+        # Cached lookups
+        G1nbrs = self.G1_adj[G1_node]
+        G2nbrs = self.G2_adj[G2_node]
+        core_1 = self.core_1
+        edge_match = self.edge_match
+
+        for neighbor in G1nbrs:
+            # G1_node is not in core_1, so we must handle R_self separately
+            if neighbor == G1_node:
+                if G2_node in G2nbrs and not edge_match(
+                    G1nbrs[G1_node], G2nbrs[G2_node]
+                ):
+                    return False
+            elif neighbor in core_1:
+                G2_nbr = core_1[neighbor]
+                if G2_nbr in G2nbrs and not edge_match(
+                    G1nbrs[neighbor], G2nbrs[G2_nbr]
+                ):
+                    return False
+        # syntactic check has already verified that neighbors are symmetric
+
+    return True
+
+
+class GraphMatcher(vf2.GraphMatcher):
+    """VF2 isomorphism checker for undirected graphs.
+    """
+
+    def __init__(self, G1, G2, node_match=None, edge_match=None):
+        """Initialize graph matcher.
+
+        Parameters
+        ----------
+        G1, G2: graph
+            The graphs to be tested.
+
+        node_match: callable
+            A function that returns True iff node n1 in G1 and n2 in G2
+            should be considered equal during the isomorphism test. The
+            function will be called like::
+
+               node_match(G1.nodes[n1], G2.nodes[n2])
+
+            That is, the function will receive the node attribute dictionaries
+            of the nodes under consideration. If None, then no attributes are
+            considered when testing for an isomorphism.
+
+        edge_match: callable
+            A function that returns True iff the edge attribute dictionary for
+            the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be
+            considered equal during the isomorphism test. The function will be
+            called like::
+
+               edge_match(G1[u1][v1], G2[u2][v2])
+
+            That is, the function will receive the edge attribute dictionaries
+            of the edges under consideration. If None, then no attributes are
+            considered when testing for an isomorphism.
+
+        """
+        vf2.GraphMatcher.__init__(self, G1, G2)
+
+        self.node_match = node_match
+        self.edge_match = edge_match
+
+        # These will be modified during checks to minimize code repeat.
+        self.G1_adj = self.G1.adj
+        self.G2_adj = self.G2.adj
+
+    semantic_feasibility = _semantic_feasibility
+
+
+class DiGraphMatcher(vf2.DiGraphMatcher):
+    """VF2 isomorphism checker for directed graphs.
+    """
+
+    def __init__(self, G1, G2, node_match=None, edge_match=None):
+        """Initialize graph matcher.
+
+        Parameters
+        ----------
+        G1, G2 : graph
+            The graphs to be tested.
+
+        node_match : callable
+            A function that returns True iff node n1 in G1 and n2 in G2
+            should be considered equal during the isomorphism test. The
+            function will be called like::
+
+               node_match(G1.nodes[n1], G2.nodes[n2])
+
+            That is, the function will receive the node attribute dictionaries
+            of the nodes under consideration. If None, then no attributes are
+            considered when testing for an isomorphism.
+
+        edge_match : callable
+            A function that returns True iff the edge attribute dictionary for
+            the pair of nodes (u1, v1) in G1 and (u2, v2) in G2 should be
+            considered equal during the isomorphism test. The function will be
+            called like::
+
+               edge_match(G1[u1][v1], G2[u2][v2])
+
+            That is, the function will receive the edge attribute dictionaries
+            of the edges under consideration. If None, then no attributes are
+            considered when testing for an isomorphism.
+
+        """
+        vf2.DiGraphMatcher.__init__(self, G1, G2)
+
+        self.node_match = node_match
+        self.edge_match = edge_match
+
+        # These will be modified during checks to minimize code repeat.
+        self.G1_adj = self.G1.adj
+        self.G2_adj = self.G2.adj
+
+    def semantic_feasibility(self, G1_node, G2_node):
+        """Returns True if mapping G1_node to G2_node is semantically feasible."""
+
+        # Test node_match and also test edge_match on successors
+        feasible = _semantic_feasibility(self, G1_node, G2_node)
+        if not feasible:
+            return False
+
+        # Test edge_match on predecessors
+        self.G1_adj = self.G1.pred
+        self.G2_adj = self.G2.pred
+        feasible = _semantic_feasibility(self, G1_node, G2_node)
+        self.G1_adj = self.G1.adj
+        self.G2_adj = self.G2.adj
+
+        return feasible
+
+
+# The "semantics" of edge_match are different for multi(di)graphs, but
+# the implementation is the same.  So, technically we do not need to
+# provide "multi" versions, but we do so to match NetworkX's base classes.
+
+
+class MultiGraphMatcher(GraphMatcher):
+    """VF2 isomorphism checker for undirected multigraphs. """
+
+    pass
+
+
+class MultiDiGraphMatcher(DiGraphMatcher):
+    """VF2 isomorphism checker for directed multigraphs. """
+
+    pass