• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# Generating graphs

JimboBimbo Oct 12th, 2012 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ##########################
2. ####
3. ####  Helper functions
4. ####
5. ##########################
6.
7. import copy
8.
9. ## Returns the input list with the input value removed
10.
11. def lf(lst,num):
12.     lst.remove(num)
13.     return lst
14.
15. ## Returns a list with all instances of target replaced with new
16.
17. def lr(l,target,new):
18.     ll = []
19.     for i in l:
20.         cl = []
21.         for j in i:
22.             if j == target:
23.                 cl.append(new)
24.             else:
25.                 cl.append(j)
26.         ll.append(cl)
27.     return ll
28.
29. ## Checks if every value appears exactly twice in a list
30.
31. def checkl(l):
32.     a = max(flatten(l))
33.     for i in range(1,a+1):
34.         if len(filter(lambda z: z[0] == i,l)) == 1 and len(filter(lambda z: z[1] == i,l)) == 1:
35.             continue
36.         else:
37.             return False
38.     return True
39.
40. ## Gives the degree of the vertex in the graph
41.
42. def deg(g,v):
43.     a = len(g[v]) + len(filter(lambda x: x == v, flatten(g.values())))
44.     return a
45.
46. ## Creates a Mathematica graph
47.
48. def tomg(g):
49.     s = "GraphPlot[{"
50.     for i in g.keys():
51.         for j in g[i]:
52.             s += "%g->%g,"%(i,j)
53.     s = s[:-1]
54.     s += "}]"
55.     return s
56.
57. ## Checks for graph isomorphism
58. ## m is number of vertices
59.
60. def isog(g1,g2,m):
61.     lg1t = []
62.     lg1 = []
63.     for i in g1.keys():
64.         for j in g1[i]:
65.             lg1t.append([i,j])
66.     for t in lg1t:
67.         t.sort()
68.         lg1.append(t)
69.     lg1.sort()
70.     lg2t = []
71.     lg2 = []
72.     for i in g2.keys():
73.         for j in g2[i]:
74.             lg2t.append([i,j])
75.     for t in lg2t:
76.         t.sort()
77.         lg2.append(t)
78.     lg2.sort()
79.     ##Checks if same edges, same vertices
80.     if lg1 == lg2:
81.         return True
82.     ##Checks if permutations of vertices
83.     l1 = Arrangements(range(1,m+1)+range(1,m+1),2).list()
84.     l2 = Combinations(l1,m).list()
85.     l3 = filter(lambda y: checkl(y), l2)
86.     for i in l3:
87.         lG2 = copy.deepcopy(lg2)
88.         for j in i:
89.             lG2 = lr(lG2,j[0],str(j[1]))
90.         for j in i:
91.             lG2 = lr(lG2,str(j[1]),j[1])
92.         LG2 = []
93.         for t in lG2:
94.             t.sort()
95.             LG2.append(t)
96.         LG2.sort()
97.         if lg1 == LG2:
98.             return True
99.     return False
100.
101. ##########################
102. ####
103. ####  Main sequence
104. ####
105. ##########################
106.
107. ## Gives a list of at most trivalent graphs with n+1 vertices, where the list l has graphs with n vertices
108. ## Uses dictionary structure, because graph object was inconsistent
109.
110. a = max(flatten(map(lambda x: x.keys(), l)))
111. vl = range(1,a+1)
112. nl = []
113. for i in l:
114.     im = max(flatten(i.values()))
115.     itemp = copy.deepcopy(i)
116.     l1 = filter(lambda x: deg(i,x) == 1, i.keys())
117.     l2 = filter(lambda x: deg(i,x) == 2, i.keys())
118.     for j1 in l1:
119.         for j2 in l1:
120.             itemp[j1] += [j2]
121.             nl.append(itemp)
122.             itemp = copy.deepcopy(i)
123.         for j3 in l2:
124.             itemp[j1] += [j3]
125.             nl.append(itemp)
126.             itemp = copy.deepcopy(i)
127.         itemp[j1] += [im+1]
128.         nl.append(itemp)
129.         itemp = copy.deepcopy(i)
130.     for j4 in l2:
131.         for j5 in lf(l2,j4):
132.             itemp[j4] += [j5]
133.             nl.append(itemp)
134.             itemp = copy.deepcopy(i)
135.         itemp[j4] += [im+1]
136.         nl.append(itemp)
137.         itemp = copy.deepcopy(i)
138. nnl = []
139. for i in nl:
140.     im = max(flatten(i.values()))
141.     if max(map(lambda x: deg(i,x), i.keys())) <= 3:
142.         if len(filter(lambda x: not isog(i,x,im),nnl)) == len(nnl):
143.             nnl.append(i)
144. for i in nnl:
145.     for j in flatten(i.values()):
146.         if j not in i.keys():
147.             i[j] = []
148. print nnl
149.
150. ##########################
151. ####
152. ####  Initialization and continuation
153. ####
154. ##########################
155.
156. ## First list
157.
158. l = [{1:[2],2:[]}]
159.
160. ## Next list
161.
162. l = copy.deepcopy(nnl)
RAW Paste Data
Top