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
11
12
13
14
15
16 import networkx.cluster
17 import networkx.cliques
18 import networkx.isomorphvf2
19 from networkx.exception import NetworkXException, NetworkXError
20
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
30 if G1.order() != G2.order(): return False
31
32
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
47
48 return False
49
50
51 return True
52
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
62 if G1.order() != G2.order(): return False
63
64
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
78 return True
79
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
89 if G1.order() != G2.order(): return False
90
91
92 d1=G1.degree()
93 d1.sort()
94 d2=G2.degree()
95 d2.sort()
96
97 if d1 != d2: return False
98
99
100 return True
101
117
118
119
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
134 nxbase=sys.path[0]+os.sep+os.pardir
135 sys.path.insert(0,nxbase)
136 unittest.TextTestRunner().run(_test_suite())
137