Package networkx :: Module isomorph
[hide private]
[frames] | no frames]

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