Source Code for Module networkx.isomorph

  1  """ 
  2  Fast checking to see if graphs are not isomorphic. 
  3   
  4  This isn't a graph isomorphism checker. 
  5  """ 
  6  __author__ = """Pieter Swart (swart@lanl.gov)\nDan Schult (dschult@colgate.edu)""" 
  7  __date__ = "$Date: 2005-05-31 17:00:13 -0600 (Tue, 31 May 2005) $" 
  8  __credits__ = """""" 
  9  __revision__ = "$Revision: 1002 $" 
 10  #    Copyright (C) 2004,2005 by  
 11  #    Aric Hagberg <hagberg@lanl.gov> 
 12  #    Dan Schult <dschult@colgate.edu> 
 13  #    Pieter Swart <swart@lanl.gov> 
 14  #    Distributed under the terms of the GNU Lesser General Public License 
 15  #    http://www.gnu.org/copyleft/lesser.html 
 16  import networkx.cluster  
 17  import networkx.cliques  
 18  import networkx.isomorphvf2 
 19  from networkx.exception import NetworkXException, NetworkXError 
 20   
 21 -def graph_could_be_isomorphic(G1,G2): 
 22      """ 
 23      Returns False if graphs G1 and G2 are definitely not isomorphic. 
 24      True does NOT garantee isomorphism. 
 25     
 26      Checks for matching degree, triangle, and number of cliques sequences. 
 27      """ 
 28     
 29      # Check global properties 
 30      if G1.order() != G2.order(): return False 
 31       
 32      # Check local properties 
 33      d1=G1.degree(with_labels=True) 
 34      t1=networkx.cluster.triangles(G1,with_labels=True) 
 35      c1=networkx.cliques.number_of_cliques(G1,with_labels=True) 
 36      props1=[ [d1[v], t1[v], c1[v]] for v in d1 ] 
 37      props1.sort() 
 38       
 39      d2=G2.degree(with_labels=True) 
 40      t2=networkx.cluster.triangles(G2,with_labels=True) 
 41      c2=networkx.cliques.number_of_cliques(G2,with_labels=True) 
 42      props2=[ [d2[v], t2[v], c2[v]] for v in d2 ] 
 43      props2.sort() 
 44   
 45      if props1 != props2:  
 46  #        print props1 
 47  #        print props2 
 48          return False 
 49   
 50      # OK... 
 51      return True 
 52   
 53 -def fast_graph_could_be_isomorphic(G1,G2): 
 54      """ 
 55      Returns False if graphs G1 and G2 are definitely not isomorphic. 
 56      True does NOT garantee isomorphism. 
 57     
 58      Checks for matching degree and triangle sequences. 
 59      """ 
 60     
 61      # Check global properties 
 62      if G1.order() != G2.order(): return False 
 63       
 64      # Check local properties 
 65      d1=G1.degree(with_labels=True) 
 66      t1=networkx.cluster.triangles(G1,with_labels=True) 
 67      props1=[ [d1[v], t1[v]] for v in d1 ] 
 68      props1.sort() 
 69       
 70      d2=G2.degree(with_labels=True) 
 71      t2=networkx.cluster.triangles(G2,with_labels=True) 
 72      props2=[ [d2[v], t2[v]] for v in d2 ] 
 73      props2.sort() 
 74   
 75      if props1 != props2: return False 
 76   
 77      # OK... 
 78      return True 
 79   
 80 -def faster_graph_could_be_isomorphic(G1,G2): 
 81      """ 
 82      Returns False if graphs G1 and G2 are definitely not isomorphic. 
 83      True does NOT garantee isomorphism. 
 84     
 85      Checks for matching degree sequences in G1 and G2. 
 86      """ 
 87     
 88      # Check global properties 
 89      if G1.order() != G2.order(): return False 
 90       
 91      # Check local properties 
 92      d1=G1.degree() 
 93      d1.sort() 
 94      d2=G2.degree() 
 95      d2.sort() 
 96   
 97      if d1 != d2: return False 
 98   
 99      # OK... 
100      return True 
101   
102 -def is_isomorphic(G1,G2): 
103      """Returns True if the graphs G1 and G2 are isomorphic and False otherwise. 
104   
105      Uses the vf2 algorithm - see networkx.isomorphvf2 
106           
107      """ 
108      if G1.is_directed() and G2.is_directed(): 
109          return networkx.isomorphvf2.DiGraphMatcher(G1,G2).is_isomorphic() 
110      elif not (G1.is_directed() and G2.is_directed()): 
111          return networkx.isomorphvf2.GraphMatcher(G1,G2).is_isomorphic() 
112      else: 
113              # Graphs are of mixed type. We could just return False,  
114              # but then there is the case of completely disconnected graphs... 
115              # which could be isomorphic. 
116          raise NetworkXError, "Both graphs were not directed or both graphs were not undirected." 
117       
118   
119   
120 -def _test_suite(): 
121      import doctest 
122      suite = doctest.DocFileSuite('tests/isomorph.txt',package='networkx') 
123      return suite 
124   
125   
126  if __name__ == "__main__": 
127      import os 
128      import sys 
129      import unittest 
130      if sys.version_info[:2] < (2, 4): 
131          print "Python version 2.4 or later required for tests (%d.%d detected)." %  sys.version_info[:2] 
132          sys.exit(-1) 
133      # directory of networkx package (relative to this) 
134      nxbase=sys.path[0]+os.sep+os.pardir 
135      sys.path.insert(0,nxbase) # prepend to search path 
136      unittest.TextTestRunner().run(_test_suite()) 
137