semantic_feasibility(self,
G1_node,
G2_node)
| source code
|
The semantic feasibility function should return True if it is
acceptable to add the candidate pair (G1_node, G2_node) to the current
partial isomorphism mapping. The logic should focus on semantic
information contained in the edge data or a formalized node class.
By acceptable, we mean that the subsequent mapping can still become a
complete isomorphism mapping. Thus, if adding the candidate pair
definitely makes it so that the subsequent mapping cannot become a
complete isomorphism mapping, then this function must return False.
The default semantic feasibility function always returns True. The
effect is that semantics are not considered in the matching of G1
and G2.
The semantic checks might differ based on the what type of test is
being performed. A keyword description of the test is stored in
self.test. Here is a quick description of the currently implemented
tests:
- test='graph'
- Indicates that the graph matcher is looking for a graph-graph
isomorphism.
- test='subgraph'
- Indicates that the graph matcher is looking for a subgraph-graph
isomorphism such that a subgraph of G1 is isomorphic to G2.
Any subclass of GraphMatcher which redefines semantic_feasibility()
must maintain the above form to keep the match() method functional.
Implementation considerations should include directed and undirected
graphs, as well as graphs with multiple edges.
As an example, if edges have weights, one feasibility function would be
to demand that the weight values/relationships are preserved in the
isomorphism mapping.
|