"""
An implementation of VF2 algorithm for graph ismorphism testing, as seen here:

   Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
      "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs,"
      IEEE Transactions on Pattern Analysis and Machine Intelligence,
      vol. 26,  no. 10,  pp. 1367-1372,  Oct.,  2004.

Modified to handle undirected graphs.
Modified to handle multiple edges.
"""

__date__ = "$Date: 2007-08-21 16:49:09 -0600 (Tue, 21 Aug 2007) $"
__credits__ = "$Credits:$"
__revision__ = "$Revision: 680 $"

#    Copyright (C) 2007 by
#    Christopher Ellison <cellison@cse.ucdavis.edu>
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html
#
# This work was completed as part of the
# Computational Mechanics Python (CMPy) project.
# James P. Crutchfield, principal investigator.
# Center for Computational Science and Engineering and Physics Department,
# UC Davis.

import sys
from sets import Set

class GraphMatcher(object):
    """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.
    
    """
    def __init__(self, G1, G2):
        """Initialize GraphMatcher.
        
        Suppose G1 and G2 are undirected graphs.
        
        >>> GM = GraphMatcher(G1,G2)
        
        creates a GraphMatcher which only checks for syntactic feasibility.
        """
        self.G1 = G1
        self.G2 = G2
 
        # Set recursion limit.
        self.old_recursion_limit = sys.getrecursionlimit()
        expected_max_recursion_level = len(self.G2)
        if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
            # Give some breathing room.
            sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
        
        # Declare that we will be searching for a graph-graph isomorphism.
        self.test = 'graph'

        # Initialize the isomorphism mapping.
        self.state = GMState(self)

    def __del__(self):
        # Restore the recursion limit
        sys.setrecursionlimit(self.old_recursion_limit)
                
    def candidate_pairs_iter(self):
        """This function returns an iterator over pairs to be considered
        for inclusion in the current partial isomorphism mapping."""

        # All computations are done using the current state!
        
        # First we compute the inout-terminal sets.
        T1_inout = [node for node in self.G1.nodes_iter() if (node in GMState.inout_1) and (node not in GMState.core_1)]
        T2_inout = [node for node in self.G2.nodes_iter() if (node in GMState.inout_2) and (node not in GMState.core_2)]
        
        # If T1_inout and T2_inout are both nonempty.
        # P(s) = T1_inout x {min T2_inout}
        if T1_inout and T2_inout:
            for node in T1_inout:
                yield node, min(T2_inout)
            
        else:
            # If T1_inout and T2_inout were both empty....
            # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
            if not (T1_inout or T2_inout):
                # First we determine the candidate node for G2
                other_node = min(Set(self.G2.nodes()) - Set(GMState.core_2))
                for node in self.G1:
                    if node not in GMState.core_1:
                        yield node, other_node

        # For all other cases, we don't have any candidate pairs.        

    def is_isomorphic(self):
        """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
        returns False."""

        # Declare that we are looking for a graph-graph isomorphism.
        self.test = 'graph'

        # Let's do two very quick checks!
        # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
        # For now, I just copy the code.
        
        # Check global properties
        if self.G1.order() != self.G2.order(): return False
    
        # Check local properties
        d1=self.G1.degree()
        d1.sort()
        d2=self.G2.degree()
        d2.sort()
        if d1 != d2: return False
        
        # Recall, self.match() will not return False.
        # It raises an exception or returns None
        try:
            self.match(self.state)
            return False
        except StopIteration:
            return True
        
    def match(self, state):
        """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.
        """
        if len(GMState.core_1) == len(self.G2):
            # Save the final mapping, otherwise garbage collection deletes it.
            self.mapping = GMState.core_1.copy()
            # The mapping is complete.
            raise StopIteration
        else:
            for G1_node, G2_node in self.candidate_pairs_iter():
                if self.syntactic_feasibility(G1_node, G2_node):
                    if self.semantic_feasibility(G1_node, G2_node):
                        # Recursive call, adding the feasible state.
                        self.match(GMState(self, G1_node, G2_node))
            # Garbage collection for GMState() will 'restore data structures'.
    
    def 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.   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.        
        """
        return True
                    
    def subgraph_is_isomorphic(self):
        """Returns True if a subgraph of G1 is isomorphic to G2.  Otherwise,
        it returns False."""
        
        # Declare that we are looking for graph-subgraph isomorphism.
        self.test = 'subgraph'
        
        # Recall, self.match() will not return False.
        # It raises an exception or returns None
        try:
            self.match(self.state)
            return False
        except StopIteration:
            return True
        
    def 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.  The addition
        is allowable if the inclusion of the candidate pair does not make it
        impossible for an isomorphism to be found.
        """
        
        # The VF2 algorithm was designed to work with graphs having, at most,
        # only one edge connecting any two nodes.  This is not the case when
        # dealing with an XGraph or XDiGraph that has multiedges=True.
        # 
        # Basically, when we test the look-ahead rules R_pred and R_succ, we
        # will make sure that the number of edges are also taken into account.
        #
        # When multiedges=False, the value in the innermost dictionary is a 
        # singlet.  When multiedges=True, the value in the innermost dictionary
        # is a list.  However strange it may be, it is certainly possible to
        # have graphs which are isomorphic but with only one of them having
        # multiedges=True.  Thus, we must ALWAYS perform this check.
        
        
        
        ###
        ### Test at each step to get a return value as soon as possible.
        ###
        
        
        
        ### Look ahead 0
        
        # R_self

        # The number of selfloops for G1_node must equal the number of 
        # self-loops for G2_node. Without this check, we would fail on 
        # R_pred at the next recursion level. But it is good to prune the
        # search tree now.
        if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
            return False
                
        
        # R_neighbor
        
        # For each neighbor n' of n in the partial mapping, the corresponding
        # node m' is a neighbor of m, and vice versa. Also, the number of
        # edges must be equal.
        for neighbor in self.G1.adj[G1_node]:
            if neighbor in GMState.core_1:
                if not (GMState.core_1[neighbor] in self.G2.adj[G2_node]):
                    return False
                elif self.G1.number_of_edges(neighbor, G1_node) != self.G2.number_of_edges(GMState.core_1[neighbor], G2_node):
                    return False
        for neighbor in self.G2.adj[G2_node]:
            if neighbor in GMState.core_2:
                if not (GMState.core_2[neighbor] in self.G1.adj[G1_node]):
                    return False
                elif self.G1.number_of_edges(GMState.core_2[neighbor], G1_node) != self.G2.number_of_edges(neighbor, G2_node):
                    return False
        
        ### Look ahead 1
        
        # R_terminout
        # The number of neighbors of n that are in T_1^{inout} is equal to the
        # number of neighbors of m that are in T_2^{inout}, and vice versa.
        num1 = 0
        for neighbor in self.G1.adj[G1_node]:
            if (neighbor in GMState.inout_1) and (neighbor not in GMState.core_1):
                num1 += 1
        num2 = 0
        for neighbor in self.G2.adj[G2_node]:
            if (neighbor in GMState.inout_2) and (neighbor not in GMState.core_2):
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False


        ### Look ahead 2

        # R_new
        
        # The number of neighbors of n that are neither in the core_1 nor
        # T_1^{inout} is equal to the number of neighbors of m 
        # that are neither in core_2 nor T_2^{inout}.
        num1 = 0
        for neighbor in self.G1.adj[G1_node]:
            if neighbor not in GMState.inout_1:
                num1 += 1
        num2 = 0
        for neighbor in self.G2.adj[G2_node]:
            if neighbor not in GMState.inout_2:
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False
            
        # Otherwise, this node pair is syntactically feasible!
        return True
    
    
class DiGraphMatcher(object):
    """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.
    
    """
        
    def __init__(self, G1, G2):
        """Initialize DiGraphMatcher.
        
        Suppose G1 and G2 are graphs.
        
        >>> GM = DiGraphMatcher(G1,G2)
        
        creates a DiGraphMatcher which only checks for syntactic feasibility.
        
        """
        self.G1 = G1
        self.G2 = G2
 
        # Set recursion limit.
        self.old_recursion_limit = sys.getrecursionlimit()
        expected_max_recursion_level = len(self.G2)
        if self.old_recursion_limit < 1.5 * expected_max_recursion_level:
            # Give some breathing room.
            sys.setrecursionlimit(int(1.5 * expected_max_recursion_level))
        
        # Declare that we will be searching for a graph-graph isomorphism.
        self.test = 'graph'
        
        # Initialize the isomorphism mapping.
        self.state = DiGMState(self)
        
        # Provide a convienient was to access the isomorphism mapping.
        self.mapping = DiGMState.core_1
               
    def __del__(self):
        # Restore the recursion limit
        sys.setrecursionlimit(self.old_recursion_limit)
        
    def candidate_pairs_iter(self):
        """This function returns an iterator over pairs to be considered
        for inclusion in the current partial isomorphism mapping."""
        
        # All computations are done using the current state!
        
        # First we compute the out-terminal sets.
        T1_out = [node for node in self.G1.nodes_iter() if (node in DiGMState.out_1) and (node not in DiGMState.core_1)]
        T2_out = [node for node in self.G2.nodes_iter() if (node in DiGMState.out_2) and (node not in DiGMState.core_2)]
        
        # If T1_out and T2_out are both nonempty.
        # P(s) = T1_out x {min T2_out}
        if T1_out and T2_out:
            node_2 = min(T2_out)
            for node_1 in T1_out:
                yield node_1, node_2
            
        else:
            # If T1_out and T2_out were both empty....
            # We compute the in-terminal sets.
            if not (T1_out or T2_out):
                T1_in = [node for node in self.G1.nodes_iter() if (node in DiGMState.in_1) and (node not in DiGMState.core_1)]
                T2_in = [node for node in self.G2.nodes_iter() if (node in DiGMState.in_2) and (node not in DiGMState.core_2)]
                
                # If T1_in and T2_in are both nonempty.
                # P(s) = T1_out x {min T2_out}
                if T1_in and T2_in:
                    node_2 = min(T2_in)
                    for node_1 in T1_in:
                        yield node_1, node_2
                else:
                    # If all terminal sets are empty...
                    # P(s) = (N_1 - M_1) x {min (N_2 - M_2)}
                    if not (T1_out or T2_out or T1_in or T2_in):
                        # First we determine the candidate node for G2
                        node_2 = min(Set(self.G2.nodes()) - Set(DiGMState.core_2))
                        for node_1 in self.G1:
                            if node_1 not in DiGMState.core_1:
                                yield node_1, node_2

        # For all other cases, we don't have any candidate pairs.        
        
    def is_isomorphic(self):
        """Returns True if G1 and G2 are isomorphic graphs. Otherwise, it
        returns False."""

        # Declare that we are looking for a graph-graph isomorphism.
        self.test = 'graph'

        # Let's do two very quick checks!
        # QUESTION: Should we call faster_graph_could_be_isomorphic(G1,G2)?
        # For now, I just copy the code.
        
        # Check global properties
        if self.G1.order() != self.G2.order(): return False
    
        # Check local properties
        d1=self.G1.degree()
        d1.sort()
        d2=self.G2.degree()
        d2.sort()
        if d1 != d2: return False
        
        # Recall, self.match() will not return False.
        # It raises an exception or returns None
        try:
            self.match(self.state)
            return False
        except StopIteration:
            return True
        
    def match(self, state):
        """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.
        
        """
        if len(DiGMState.core_1) == len(self.G2):
            # Save the final mapping, otherwise garbage collection deletes it.
            self.mapping = DiGMState.core_1.copy()
            # The mapping is complete.
            raise StopIteration
        else:
            for G1_node, G2_node in self.candidate_pairs_iter():
                if self.syntactic_feasibility(G1_node, G2_node):
                    if self.semantic_feasibility(G1_node, G2_node):
                        # Recursive call, adding the feasible state.
                        self.match(DiGMState(self, G1_node,G2_node))
            # Garbage collection for DiGMState() will 'restore data structures'.


    def 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.   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.
        
        """
        return True
                    
    def subgraph_is_isomorphic(self):
        """Returns True if a subgraph of G1 is isomorphic to G2.  Otherwise,
        it returns False."""
        
        # Declare that we are looking for graph-subgraph isomorphism.
        self.test = 'subgraph'
        
        # Recall, self.match() will not return False.
        # It raises an exception or returns None
        try:
            self.match(self.state)
            return False
        except StopIteration:
            return True

    def 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.
        
        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.
        
        """
        
        # The VF2 algorithm was designed to work with graphs that have, at most
        # only one edge connecting any two nodes.  This is not the case when
        # dealing with an XGraph or XDiGraph that has multiedges=True.
        # 
        # Basically, when we test the look-ahead rules R_pred and R_succ, 
        # we will make sure that the number of edges are also considered.
        #
        # We also have R_self, a test that performs the edge count on the 
        # candidate nodes themselves.
        #
        # When multiedges=False, the value in the innermost dictionary is a 
        # singlet.  When multiedges=True, the value in the innermost dictionary
        # is a list.  However strange it may be, it is certainly possible to
        # have graphs which are isomorphic but with only one of them having
        # multiedges=True.  Thus, we must ALWAYS perform this check, and we
        # must perform the check separately for each graph.
        
        
        
        ###
        ### Test at each step to get a return value as soon as possible.
        ###
        
        
        
        ### Look ahead 0
        
        # R_self
        
        # The number of selfloops for G1_node must equal the number of
        # self-loops for G2_node. Without this check, we would fail on R_pred
        # at the next recursion level. This should prune the tree even further.
        
        if self.G1.number_of_edges(G1_node,G1_node) != self.G2.number_of_edges(G2_node,G2_node):
            return False

        ### predecessors_iter, successors_iter and neighbors_iter does not 
        ### behave how we need it to. With multiedges, it returns the same
        ### node multiple times.  The result is that we do the same check
        ### repeatedly.  If NetworkX changes this behavior, we can go back to
        ### predecessors_iter (etc), but for now, we must access the underlying
        ### structure. For example, 
        ###   self.G1.pred[G1_node] 
        ### vs 
        ###   self.G1.predecessors_iter(G1_node)


        # R_pred
        
        # For each predecessor n' of n in the partial mapping, the
        # corresponding node m' is a predecessor of m, and vice versa. Also,
        # the number of edges must be equal.
        for predecessor in self.G1.pred[G1_node]:
            if predecessor in DiGMState.core_1:
                if not (DiGMState.core_1[predecessor] in self.G2.pred[G2_node]):
                    return False
                elif self.G1.number_of_edges(predecessor, G1_node) != self.G2.number_of_edges(DiGMState.core_1[predecessor], G2_node):
                    return False
                
        for predecessor in self.G2.pred[G2_node]:
            if predecessor in DiGMState.core_2:
                if not (DiGMState.core_2[predecessor] in self.G1.pred[G1_node]):
                    return False
                elif self.G1.number_of_edges(DiGMState.core_2[predecessor], G1_node) != self.G2.number_of_edges(predecessor, G2_node):
                    return False


        # R_succ

        # For each successor n' of n in the partial mapping, the corresponding 
        # node m' is a successor of m, and vice versa. Also, the number of
        # edges must be equal.
        for successor in self.G1.succ[G1_node]:
            if successor in DiGMState.core_1:
                if not (DiGMState.core_1[successor] in self.G2.succ[G2_node]):
                    return False
                elif self.G1.number_of_edges(G1_node, successor) != self.G2.number_of_edges(G2_node, DiGMState.core_1[successor]):
                    return False
                                
        for successor in self.G2.succ[G2_node]:
            if successor in DiGMState.core_2:
                if not (DiGMState.core_2[successor] in self.G1.succ[G1_node]):
                    return False
                elif self.G1.number_of_edges(G1_node, DiGMState.core_2[successor]) != self.G2.number_of_edges(G2_node, successor):
                    return False

        
        ### Look ahead 1
        
        # R_termin
        # The number of predecessors of n that are in T_1^{in} is equal to the
        # number of predecessors of m that are in T_2^{in}.
        num1 = 0
        for predecessor in self.G1.pred[G1_node]:
            if (predecessor in DiGMState.in_1) and (predecessor not in DiGMState.core_1):
                num1 += 1
        num2 = 0
        for predecessor in self.G2.pred[G2_node]:
            if (predecessor in DiGMState.in_2) and (predecessor not in DiGMState.core_2):
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False

        # The number of successors of n that are in T_1^{in} is equal to the
        # number of successors of m that are in T_2^{in}.
        num1 = 0
        for successor in self.G1.succ[G1_node]:
            if (successor in DiGMState.in_1) and (successor not in DiGMState.core_1):
                num1 += 1
        num2 = 0
        for successor in self.G2.succ[G2_node]:
            if (successor in DiGMState.in_2) and (successor not in DiGMState.core_2):
                num2 += 1                
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False

        # R_termout
        
        # The number of predecessors of n that are in T_1^{out} is equal to the
        # number of predecessors of m that are in T_2^{out}.
        num1 = 0
        for predecessor in self.G1.pred[G1_node]:
            if (predecessor in DiGMState.out_1) and (predecessor not in DiGMState.core_1):
                num1 += 1
        num2 = 0
        for predecessor in self.G2.pred[G2_node]:
            if (predecessor in DiGMState.out_2) and (predecessor not in DiGMState.core_2):
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False

        # The number of successors of n that are in T_1^{out} is equal to the
        # number of successors of m that are in T_2^{out}.
        num1 = 0
        for successor in self.G1.succ[G1_node]:
            if (successor in DiGMState.out_1) and (successor not in DiGMState.core_1):
                num1 += 1
        num2 = 0
        for successor in self.G2.succ[G2_node]:
            if (successor in DiGMState.out_2) and (successor not in DiGMState.core_2):
                num2 += 1                                
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False
        
        ### Look ahead 2

        # R_new
        
        # The number of predecessors of n that are neither in the core_1 nor
        # T_1^{in} nor T_1^{out} is equal to the number of predecessors of m 
        # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
        num1 = 0
        for predecessor in self.G1.pred[G1_node]:
            if (predecessor not in DiGMState.in_1) and (predecessor not in DiGMState.out_1):
                num1 += 1
        num2 = 0
        for predecessor in self.G2.pred[G2_node]:
            if (predecessor not in DiGMState.in_2) and (predecessor not in DiGMState.out_2):
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False
            
        # The number of successors of n that are neither in the core_1 nor
        # T_1^{in} nor T_1^{out} is equal to the number of successors of m 
        # that are neither in core_2 nor T_2^{in} nor T_2^{out}.
        num1 = 0
        for successor in self.G1.succ[G1_node]:
            if (successor not in DiGMState.in_1) and (successor not in DiGMState.out_1):
                num1 += 1
        num2 = 0
        for successor in self.G2.succ[G2_node]:
            if (successor not in DiGMState.in_2) and (successor not in DiGMState.out_2):
                num2 += 1
        if self.test == 'graph':
            if not (num1 == num2):
                return False
        else: # self.test == 'subgraph'
            if not (num1 >= num2):
                return False
        
        # Otherwise, this node pair is syntactically feasible!
        return True
    
        
class GMState(object):
    """This class is used internally by the GraphMatcher class.  It is used
    only to store state specific data. There will be at most G2.order() of
    these objects in memory at a time, due to the depth-first search
    strategy employed by the VF2 algorithm.
    """
    
    ###
    ### The following variables are class variables.
    ### So they will be shared by all instances of the GMState class.
    ### This is the improvement of the VF2 algorithm over the VF algorithm.
    ###
    
    # core_1[n] contains the index of the node paired with n, which is m,
    #           provided n is in the mapping.
    # core_2[m] contains the index of the node paired with m, which is n,
    #           provided m is in the mapping.
    core_1 = {}
    core_2 = {}
    
    # See the paper for definitions of M_x and T_x^{y}
    
    # inout_1[n]  is non-zero if n is in M_1 or in T_1^{inout}
    # inout_2[m]  is non-zero if m is in M_2 or in T_2^{inout}
    #
    # The value stored is the depth of the SSR tree when the node became
    # part of the corresponding set.
    inout_1 = {}
    inout_2 = {}
    # Practically, these sets simply store the nodes in the subgraph.
    
    def __init__(self, GM, G1_node=None, G2_node=None):
        """Initializes GMState object.
        
        Pass in the GraphMatcher to which this DiGMState belongs and the
        new node pair that will be added to the GraphMatcher's current
        isomorphism mapping.
        """
        # Initialize the last stored node pair.
        self.G1_node = None
        self.G2_node = None
        self.depth = len(GMState.core_1)
      
        # Watch out! G1_node == 0 should evaluate to True.
        if G1_node is not None and G2_node is not None:
            # Add the node pair to the isomorphism mapping.
            GMState.core_1[G1_node] = G2_node
            GMState.core_2[G2_node] = G1_node

            # Store the node that was added last.
            self.G1_node = G1_node
            self.G2_node = G2_node
            
            # Now we must update the other two vectors.
            # We will add only if it is not in there already!
            self.depth = len(GMState.core_1)
            
            # First we add the new nodes...
            if G1_node not in GMState.inout_1:
                GMState.inout_1[G1_node] = self.depth
            if G2_node not in GMState.inout_2:
                    GMState.inout_2[G2_node] = self.depth
                    
            # Now we add every other node...
            
            # Updates for T_1^{inout}
            new_nodes = Set([])
            for node in GMState.core_1:
                new_nodes.update([neighbor for neighbor in GM.G1.neighbors(node) if neighbor not in GMState.core_1])
            for node in new_nodes:
                if node not in GMState.inout_1:
                    GMState.inout_1[node] = self.depth

            # Updates for T_2^{inout}
            new_nodes = Set([])
            for node in GMState.core_2:
                new_nodes.update([neighbor for neighbor in GM.G2.neighbors(node) if neighbor not in GMState.core_2])
            for node in new_nodes:
                if node not in GMState.inout_2:
                    GMState.inout_2[node] = self.depth
                
    def __del__(self):
        """Deletes the GMState object and restores the class variables."""
        
        # First we remove the node that was added from the core vectors.
        # Watch out! G1_node == 0 should evaluate to True.
        if self.G1_node is not None and self.G2_node is not None:
            del GMState.core_1[self.G1_node]
            del GMState.core_2[self.G2_node]

        # Now we revert the other two vectors.        
        # Thus, we delete all entries which have this depth level.
        for vector in (GMState.inout_1, GMState.inout_2):
            for node in vector.keys():
                if vector[node] == self.depth:
                    del vector[node]
                    
    

class DiGMState(object):
    """This class is used internally by the DiGraphMatcher class.  It is used
    only to store state specific data. There will be at most G2.order() of
    these objects in memory at a time, due to the depth-first search
    strategy employed by the VF2 algorithm.
    """
    
    ###
    ### The following variables are class variables.
    ### So they will be shared by all instances of the DiGMState class.
    ### This is the improvement of the VF2 algorithm over the VF algorithm.
    ###
    
    # core_1[n] contains the index of the node paired with n, which is m,
    #           provided n is in the mapping.
    # core_2[m] contains the index of the node paired with m, which is n,
    #           provided m is in the mapping.
    core_1 = {}
    core_2 = {}
    
    # See the paper for definitions of M_x and T_x^{y}
    
    # in_1[n]  is non-zero if n is in M_1 or in T_1^{in}
    # out_1[n] is non-zero if n is in M_1 or in T_1^{out}
    #
    # in_2[m]  is non-zero if m is in M_2 or in T_2^{in}
    # out_2[m] is non-zero if m is in M_2 or in T_2^{out}
    #
    # The value stored is the depth of the search tree when the node became
    # part of the corresponding set.
    in_1 = {}
    in_2 = {}
    out_1 = {}
    out_2 = {}
    
    def __init__(self, DiGM, G1_node=None, G2_node=None):
        """Initializes DiGMState object.
        
        Pass in the DiGraphMatcher to which this DiGMState belongs and the
        new node pair that will be added to the GraphMatcher's current
        isomorphism mapping.
        """
        # Initialize the last stored node pair.
        self.G1_node = None
        self.G2_node = None
        self.depth = len(DiGMState.core_1)
      
        # Watch out! G1_node == 0 should evaluate to True.
        if G1_node is not None and G2_node is not None:
            # Add the node pair to the isomorphism mapping.
            DiGMState.core_1[G1_node] = G2_node
            DiGMState.core_2[G2_node] = G1_node
            
            # Store the node that was added last.
            self.G1_node = G1_node
            self.G2_node = G2_node
            
            # Now we must update the other four vectors.
            # We will add only if it is not in there already!
            self.depth = len(DiGMState.core_1)
            
            # First we add the new nodes...
            for vector in (DiGMState.in_1, DiGMState.out_1):
                if G1_node not in vector:
                    vector[G1_node] = self.depth
            for vector in (DiGMState.in_2, DiGMState.out_2):
                if G2_node not in vector:
                    vector[G2_node] = self.depth
                    
            # Now we add every other node...
            
            # Updates for T_1^{in}
            new_nodes = Set([])
            for node in DiGMState.core_1:
                new_nodes.update([predecessor for predecessor in DiGM.G1.predecessors(node) if predecessor not in DiGMState.core_1])
            for node in new_nodes:
                if node not in DiGMState.in_1:
                    DiGMState.in_1[node] = self.depth
                
            # Updates for T_2^{in}
            new_nodes = Set([])
            for node in DiGMState.core_2:
                new_nodes.update([predecessor for predecessor in DiGM.G2.predecessors(node) if predecessor not in DiGMState.core_2])
            for node in new_nodes:
                if node not in DiGMState.in_2:
                    DiGMState.in_2[node] = self.depth
                
            # Updates for T_1^{out}
            new_nodes = Set([])        
            for node in DiGMState.core_1:
                new_nodes.update([successor for successor in DiGM.G1.successors(node) if successor not in DiGMState.core_1])
            for node in new_nodes:
                if node not in DiGMState.out_1:                
                    DiGMState.out_1[node] = self.depth
    
            # Updates for T_2^{out}
            new_nodes = Set([])        
            for node in DiGMState.core_2:
                new_nodes.update([successor for successor in DiGM.G2.successors(node) if successor not in DiGMState.core_2])
            for node in new_nodes:
                if node not in DiGMState.out_2:
                    DiGMState.out_2[node] = self.depth

    def __del__(self):
        """Deletes the DiGMState object and restores the class variables."""
        
        # First we remove the node that was added from the core vectors.
        # Watch out! G1_node == 0 should evaluate to True.
        if self.G1_node is not None and self.G2_node is not None:
            del DiGMState.core_1[self.G1_node]
            del DiGMState.core_2[self.G2_node]

        # Now we revert the other four vectors.        
        # Thus, we delete all entries which have this depth level.
        for vector in (DiGMState.in_1, DiGMState.in_2, DiGMState.out_1, DiGMState.out_2):
            for node in vector.keys():
                if vector[node] == self.depth:
                    del vector[node]
                    
                    
def _test_suite():
    import doctest
    suite = doctest.DocFileSuite('tests/isomorphvf2.txt',package='networkx')
    return suite

if __name__ == "__main__":
    import os
    import sys
    import unittest
    if sys.version_info[:2] < (2, 4):
        print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2]
        sys.exit(-1)
    # directory of networkx package (relative to this)
    nxbase=sys.path[0]+os.sep+os.pardir
    sys.path.insert(0,nxbase) # prepend to search path
    unittest.TextTestRunner().run(_test_suite())
    
