Home       Trees       Indices       Help   
Package networkx :: Module isomorphvf2 :: Class GraphMatcher
[hide private]
[frames] | no frames]

Class GraphMatcher

source code

object --+
         |
        GraphMatcher

A GraphMatcher is responsible for matching undirected graphs (Graph or XGraph) in a predetermined manner. For graphs G1 and G2, this typically means a check for an isomorphism between them, though other checks are also possible. For example, the GraphMatcher class can check if a subgraph of G1 is isomorphic to G2.

Matching is done via syntactic feasibility. It is also possible to check for semantic feasibility. Feasibility, then, is defined as the logical AND of the two functions.

To include a semantic check, the GraphMatcher class should be subclassed, and the semantic_feasibility() function should be redefined. By default, the semantic feasibility function always returns True. The effect of this is that semantics are not considered in the matching of G1 and G2.

For more information, see the docmentation for:
syntactic_feasibliity() semantic_feasibility()

Suppose G1 and G2 are isomorphic graphs. Verification is as follows:

>>> GM = GraphMatcher(G1,G2)
>>> GM.is_isomorphic()
True
>>> GM.mapping

GM.mapping stores the isomorphism mapping.



Instance Methods [hide private]
 
__init__(self, G1, G2)
Initialize GraphMatcher.		 source code
 
__del__(self) source code
 
candidate_pairs_iter(self)
This function returns an iterator over pairs to be considered for inclusion in the current partial isomorphism mapping.		 source code
 
is_isomorphic(self)
Returns True if G1 and G2 are isomorphic graphs.		 source code
 
match(self, state)
This function is called recursively to determine if a complete isomorphism can be found between G1 and G2.		 source code
 
semantic_feasibility(self, G1_node, G2_node)
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.		 source code
 
subgraph_is_isomorphic(self)
Returns True if a subgraph of G1 is isomorphic to G2.		 source code
 
syntactic_feasibility(self, G1_node, G2_node)
This function returns True if it is adding the candidate pair to the current partial isomorphism mapping is allowable.		 source code

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__, __str__

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, G1, G2)
(Constructor)

source code 

Initialize GraphMatcher.

Suppose G1 and G2 are undirected graphs.

>>> GM = GraphMatcher(G1,G2)

creates a GraphMatcher which only checks for syntactic feasibility.

Overrides: object.__init__

is_isomorphic(self)

source code 
Returns True if G1 and G2 are isomorphic graphs. Otherwise, it returns False.

match(self, state)

source code 
This function is called recursively to determine if a complete isomorphism can be found between G1 and G2. It cleans up the class variables after each recursive call. If an isomorphism is found, we raise a StopIteration and jump immediately out of the recursion.

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.

subgraph_is_isomorphic(self)

source code 
Returns True if a subgraph of G1 is isomorphic to G2. Otherwise, it returns False.

syntactic_feasibility(self, G1_node, G2_node)

source code 
This function returns True if it is adding the candidate pair to the current partial isomorphism mapping is allowable. The addition is allowable if the inclusion of the candidate pair does not make it impossible for an isomorphism to be found.

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0beta1 on Sun Aug 17 12:04:45 2008 http://epydoc.sourceforge.net