"""
Fast checking to see if graphs are not isomorphic.

This isn't a graph isomorphism checker.
"""
__author__ = """Pieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)"""
#    Copyright (C) 2004-2008 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

import networkx as nx
from networkx.exception import NetworkXException, NetworkXError

__all__ = ['could_be_isomorphic',
           'fast_could_be_isomorphic',
           'faster_could_be_isomorphic',
           'is_isomorphic']

def could_be_isomorphic(G1,G2):
    """Returns False if graphs are definitely not isomorphic.
    True does NOT guarantee isomorphism.

    Parameters
    ----------
    G1, G2 : NetworkX graph instances
       The two graphs G1 and G2 must be the same type.
       
    Notes
    -----
    Checks for matching degree, triangle, and number of cliques sequences.
    """
  
    # Check global properties
    if G1.order() != G2.order(): return False
    
    # Check local properties
    d1=G1.degree()
    t1=nx.triangles(G1)
    c1=nx.number_of_cliques(G1)
    props1=[ [d1[v], t1[v], c1[v]] for v in d1 ]
    props1.sort()
    
    d2=G2.degree()
    t2=nx.triangles(G2)
    c2=nx.number_of_cliques(G2)
    props2=[ [d2[v], t2[v], c2[v]] for v in d2 ]
    props2.sort()

    if props1 != props2: 
#        print props1
#        print props2
        return False

    # OK...
    return True

graph_could_be_isomorphic=could_be_isomorphic

def fast_could_be_isomorphic(G1,G2):
    """Returns False if graphs are definitely not isomorphic.
    True does NOT guarantee isomorphism.

    Parameters
    ----------
    G1, G2 : NetworkX graph instances
       The two graphs G1 and G2 must be the same type.
       
    Notes
    -----
    Checks for matching degree and triangle sequences.
    """
  
    # Check global properties
    if G1.order() != G2.order(): return False
    
    # Check local properties
    d1=G1.degree()
    t1=nx.triangles(G1)
    props1=[ [d1[v], t1[v]] for v in d1 ]
    props1.sort()
    
    d2=G2.degree()
    t2=nx.triangles(G2)
    props2=[ [d2[v], t2[v]] for v in d2 ]
    props2.sort()

    if props1 != props2: return False

    # OK...
    return True

fast_graph_could_be_isomorphic=fast_could_be_isomorphic

def faster_could_be_isomorphic(G1,G2):
    """Returns False if graphs are definitely not isomorphic.
    True does NOT guarantee isomorphism.

    Parameters
    ----------
    G1, G2 : NetworkX graph instances
       The two graphs G1 and G2 must be the same type.
       
    Notes
    -----
    Checks for matching degree sequences.
    """
  
    # Check global properties
    if G1.order() != G2.order(): return False
    
    # Check local properties
    d1=G1.degree().values()
    d1.sort()
    d2=G2.degree().values()
    d2.sort()

    if d1 != d2: return False

    # OK...
    return True

faster_graph_could_be_isomorphic=faster_could_be_isomorphic

def is_isomorphic(G1,G2,weighted=False,rtol=1e-6,atol=1e-9):
    """Returns True if the graphs G1 and G2 are isomorphic and False otherwise.

    Parameters
    ----------
    G1, G2: NetworkX graph instances
       The two graphs G1 and G2 must be the same type.
       
    weighted: bool, optional
       Optionally check isomorphism for weighted graphs.
       G1 and G2 must be valid weighted graphs.

    rtol: float, optional
        The relative error tolerance when checking weighted edges

    atol: float, optional
        The absolute error tolerance when checking weighted edges
    
    Notes
    -----
    Uses the vf2 algorithm.
    Works for Graph, DiGraph, MultiGraph, and MultiDiGraph

    See Also
    --------
    isomorphvf2()

    """
    gm=None
    if weighted==True:
#        assert(G1.weighted and G2.weighted)
        if not G1.is_directed() and not G1.is_multigraph():
            assert(not G2.is_directed() and not G2.is_multigraph())
            gm = nx.WeightedGraphMatcher(G1,G2,rtol,atol)
        elif not G1.is_directed() and G1.is_multigraph():
            assert(not G2.is_directed() and G2.is_multigraph())
            gm = nx.WeightedMultiGraphMatcher(G1,G2,rtol,atol)
        elif G1.is_directed() and not G1.is_multigraph():
            assert(G2.is_directed() and not G2.is_multigraph())
            gm = nx.WeightedDiGraphMatcher(G1,G2,rtol,atol)
        else:
            assert(G2.is_directed() and G2.is_multigraph())
            gm = nx.WeightedMultiDiGraphMatcher(G1,G2,rtol,atol)
    else:
        if G1.is_directed() and G2.is_directed():
            gm=  nx.DiGraphMatcher(G1,G2)
        elif not (G1.is_directed() and G2.is_directed()):
            gm = nx.GraphMatcher(G1,G2)
    if gm==None:
        # Graphs are of mixed type. We could just return False, 
        # but then there is the case of completely disconnected graphs...
        # which could be isomorphic.
        raise NetworkXError("Graphs G1 and G2 are not of the same type.")
    
    return gm.is_isomorphic()