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

Class DiGraphMatcher

source code

object --+
         |
        DiGraphMatcher

A DiGraphMatcher is responsible for matching directed graphs (DiGraph or XDiGraph) 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 DiGraphMatcher 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, you should subclass the GraphMatcher class and redefine semantic_feasibility(). 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. Verfication 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 DiGraphMatcher.		 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 DiGraphMatcher.

Suppose G1 and G2 are graphs.

>>> GM = DiGraphMatcher(G1,G2)

creates a DiGraphMatcher 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. Because of this, this function will not return True or False. If a mapping is found, we will jump out of the recursion by throwing an exception. Otherwise, we will return nothing.

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 DiGraphMatcher 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.

Keywords:
test='graph'
Checks for graph-graph isomorphism. This is the default value.
test='subgraph'
Checks for graph-subgraph isomorphism in such a way that a subgraph of G1 might be isomorphic to G2.

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