## Mercurial > repos > shellac > sam_consensus_v3

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

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

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