1 """
2 Various small and named graphs, together with some compact generators.
3
4 """
5 __author__ ="""Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)"""
6 __date__ = "$Date: 2005-06-15 12:53:08 -0600 (Wed, 15 Jun 2005) $"
7 __credits__ = """"""
8 __revision__ = "$Revision: 1040 $"
9
10
11
12
13
14
15 import networkx
16
17
18
19
21 """
22 Return the small graph described by graph_description.
23
24 graph_description is a list of the form [ltype,name,n,xlist]
25
26 Here ltype is one of "adjacencylist" or "edgelist",
27 name is the name of the graph and n the number of nodes.
28 This constructs a graph of n nodes with integer labels 1,..,n.
29
30 If ltype="adjacencylist" then xlist is an adjacency list
31 with exactly n entries, in with the j'th entry (which can be empty)
32 specifies the nodes connected to vertex j.
33 e.g. the "square" graph C_4 can be obtained by
34
35 >>> G=make_small_graph(["adjacencylist","C_4",4,[[2,4],[1,3],[2,4],[1,3]]])
36
37 or, since we do not need to add edges twice,
38
39 >>> G=make_small_graph(["adjacencylist","C_4",4,[[2,4],[3],[4],[]]])
40
41 If ltype="edgelist" then xlist is an edge list
42 written as [[v1,w2],[v2,w2],...,[vk,wk]],
43 where vj and wj integers in the range 1,..,n
44 e.g. the "square" graph C_4 can be obtained by
45
46 >>> G=make_small_graph(["edgelist","C_4",4,[[1,2],[3,4],[2,3],[4,1]]])
47
48 Use the create_using argument to choose the graph class/type.
49 """
50 ltype=graph_description[0]
51 name=graph_description[1]
52 n=graph_description[2]
53
54 G=networkx.empty_graph(n, create_using)
55 nodes=G.nodes()
56
57 if ltype=="adjacencylist":
58 adjlist=graph_description[3]
59 if len(adjlist) != n:
60 raise networkx.NetworkXError,"invalid graph_description"
61 G.add_edges_from([(u-1,v) for v in nodes for u in adjlist[v]])
62 elif ltype=="edgelist":
63 edgelist=graph_description[3]
64 for e in edgelist:
65 v1=e[0]-1
66 v2=e[1]-1
67 if v1<0 or v1>n-1 or v2<0 or v2>n-1:
68 raise networkx.NetworkXError,"invalid graph_description"
69 else:
70 G.add_edge(v1,v2)
71 G.name=name
72 return G
73
74
76 """
77 Return the cubic graph specified in LCF notation.
78
79 LCF notation (LCF=Lederberg-Coxeter-Fruchte) is a compressed
80 notation used in the generation of various cubic Hamiltonian
81 graphs of high symmetry. See, for example, dodecahedral_graph,
82 desargues_graph, heawood_graph and pappus_graph below.
83
84 n (number of nodes)
85 The starting graph is the n-cycle with nodes 0,...,n-1.
86 (The null graph is returned if n < 0.)
87
88 shift_list = [s1,s2,..,sk], a list of integer shifts mod n,
89
90 repeats
91 integer specifying the number of times that shifts in shift_list
92 are successively applied to each v_current in the n-cycle
93 to generate an edge between v_current and v_current+shift mod n.
94
95 For v1 cycling through the n-cycle a total of k*repeats
96 with shift cycling through shiftlist repeats times connect
97 v1 with v1+shift mod n
98
99 The utility graph K_{3,3}
100
101 >>> G=LCF_graph(6,[3,-3],3)
102
103 The Heawood graph
104
105 >>> G=LCF_graph(14,[5,-5],7)
106
107 See http://mathworld.wolfram.com/LCFNotation.html for a description
108 and references.
109
110 """
111
112 if n <= 0:
113 return networkx.empty_graph()
114
115
116 G=networkx.cycle_graph(n)
117 G.name="LCF_graph"
118 nodes=G.nodes()
119
120 n_extra_edges=repeats*len(shift_list)
121
122
123 if n_extra_edges < 1:
124 return G
125
126 for i in range(n_extra_edges):
127 shift=shift_list[i%len(shift_list)]
128 v1=nodes[i%n]
129 v2=nodes[(i + shift)%n]
130 G.add_edge(v1, v2)
131 return G
132
133
134
135
136
137
139 """Return the Bull graph. """
140 description=[
141 "adjacencylist",
142 "Bull Graph",
143 5,
144 [[2,3],[1,3,4],[1,2,5],[2],[3]]
145 ]
146 G=make_small_graph(description)
147 return G
148
150 """Return the Chvatal graph."""
151 description=[
152 "adjacencylist",
153 "Chvatal Graph",
154 12,
155 [[2,5,7,10],[3,6,8],[4,7,9],[5,8,10],
156 [6,9],[11,12],[11,12],[9,12],
157 [11],[11,12],[],[]]
158 ]
159 G=make_small_graph(description)
160 return G
161
163 """Return the 3-regular Platonic Cubical graph."""
164 description=[
165 "adjacencylist",
166 "Platonic Cubical Graph",
167 8,
168 [[2,4,5],[1,3,8],[2,4,7],[1,3,6],
169 [1,6,8],[4,5,7],[3,6,8],[2,5,7]]
170 ]
171 G=make_small_graph(description)
172 return G
173
175 """ Return the Desargues graph."""
176 G=LCF_graph(20,[5,-5,9,-9],5)
177 G.name="Desargues Graph"
178 return G
179
181 """Return the Diamond graph. """
182 description=[
183 "adjacencylist",
184 "Diamond Graph",
185 4,
186 [[2,3],[1,3,4],[1,2,4],[2,3]]
187 ]
188 G=make_small_graph(description)
189 return G
190
192 """ Return the Platonic Dodecahedral graph. """
193 G=LCF_graph(20,[10,7,4,-4,-7,10,-4,7,-7,4],2)
194 G.name="Dodecahedral Graph"
195 return G
196
198 """Return the Frucht Graph.
199
200 The Frucht Graph is the smallest cubical graph whose
201 automorphism group consists only of the identity element.
202
203 """
204 G=networkx.cycle_graph(7)
205 G.add_edges_from([[0,7],[1,7],[2,8],[3,9],[4,9],[5,10],[6,10],
206 [7,11],[8,11],[8,9],[10,11]])
207
208 G.name="Frucht Graph"
209 return G
210
212 """ Return the Heawood graph, a (3,6) cage. """
213 G=LCF_graph(14,[5,-5],7)
214 G.name="Heawood Graph"
215 return G
216
218 """Return the House graph (square with triangle on top)."""
219 description=[
220 "adjacencylist",
221 "House Graph",
222 5,
223 [[2,3],[1,4],[1,4,5],[2,3,5],[3,4]]
224 ]
225 G=make_small_graph(description)
226 return G
227
229 """Return the House graph with a cross inside the house square."""
230 description=[
231 "adjacencylist",
232 "House-with-X-inside Graph",
233 5,
234 [[2,3,4],[1,3,4],[1,2,4,5],[1,2,3,5],[3,4]]
235 ]
236 G=make_small_graph(description)
237 return G
238
240 """Return the Platonic Icosahedral graph."""
241 description=[
242 "adjacencylist",
243 "Platonic Icosahedral Graph",
244 12,
245 [[2,6,8,9,12],[3,6,7,9],[4,7,9,10],[5,7,10,11],
246 [6,7,11,12],[7,12],[],[9,10,11,12],
247 [10],[11],[12],[]]
248 ]
249 G=make_small_graph(description)
250 return G
251
252
254 """
255 Return the Krackhardt Kite Social Network.
256
257 A 10 actor social network introduced by David Krackhardt
258 to illustrate: degree, betweenness, centrality, closeness, etc.
259 The traditional labeling is:
260 Andre=1, Beverley=2, Carol=3, Diane=4,
261 Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.
262
263 """
264 description=[
265 "adjacencylist",
266 "Krackhardt Kite Social Network",
267 10,
268 [[2,3,4,6],[1,4,5,7],[1,4,6],[1,2,3,5,6,7],[2,4,7],
269 [1,3,4,7,8],[2,4,5,6,8],[6,7,9],[8,10],[9]]
270 ]
271 G=make_small_graph(description)
272 return G
273
275 """Return the Moebius-Kantor graph."""
276 G=LCF_graph(16,[5,-5],8)
277 G.name="Moebius-Kantor Graph"
278 return G
279
281 """Return the Platonic Octahedral graph."""
282 description=[
283 "adjacencylist",
284 "Platonic Octahedral Graph",
285 6,
286 [[2,3,4,5],[3,4,6],[5,6],[5,6],[6],[]]
287 ]
288 G=make_small_graph(description)
289 return G
290
292 """ Return the Pappus graph."""
293 G=LCF_graph(18,[5,7,-7,7,-7,-5],3)
294 G.name="Pappus Graph"
295 return G
296
298 """Return the Petersen graph."""
299 description=[
300 "adjacencylist",
301 "Petersen Graph",
302 10,
303 [[2,5,6],[1,3,7],[2,4,8],[3,5,9],[4,1,10],[1,8,9],[2,9,10],
304 [3,6,10],[4,6,7],[5,7,8]]
305 ]
306 G=make_small_graph(description)
307 return G
308
309
311 """
312 Return a small maze with a cycle.
313
314 This is the maze used in Sedgewick,3rd Edition, Part 5, Graph
315 Algorithms, Chapter 18, e.g. Figure 18.2 and following.
316 Nodes are numbered 0,..,7
317 """
318 G=networkx.empty_graph(0)
319 G.add_nodes_from(range(8))
320 G.add_edges_from([[0,2],[0,7],[0,5]])
321 G.add_edges_from([[1,7],[2,6]])
322 G.add_edges_from([[3,4],[3,5]])
323 G.add_edges_from([[4,5],[4,7],[4,6]])
324 G.name="Sedgewick Maze"
325 return G
326
333
335 """Return the skeleton of the truncated cube."""
336 description=[
337 "adjacencylist",
338 "Truncated Cube Graph",
339 24,
340 [[2,3,5],[12,15],[4,5],[7,9],
341 [6],[17,19],[8,9],[11,13],
342 [10],[18,21],[12,13],[15],
343 [14],[22,23],[16],[20,24],
344 [18,19],[21],[20],[24],
345 [22],[23],[24],[]]
346 ]
347 G=make_small_graph(description)
348 return G
349
351 """Return the skeleton of the truncated Platonic tetrahedron."""
352 G=networkx.path_graph(12)
353
354 G.add_edges_from([(0,2),(0,9),(1,6),(3,11),(4,11),(5,7),(8,10)])
355 G.name="Truncated Tetrahedron Graph"
356 return G
357
359 """Return the Tutte graph."""
360 description=[
361 "adjacencylist",
362 "Tutte's Graph",
363 46,
364 [[2,3,4],[5,27],[11,12],[19,20],[6,34],
365 [7,30],[8,28],[9,15],[10,39],[11,38],
366 [40],[13,40],[14,36],[15,16],[35],
367 [17,23],[18,45],[19,44],[46],[21,46],
368 [22,42],[23,24],[41],[25,28],[26,33],
369 [27,32],[34],[29],[30,33],[31],
370 [32,34],[33],[],[],[36,39],
371 [37],[38,40],[39],[],[],
372 [42,45],[43],[44,46],[45],[],[]]
373 ]
374 G=make_small_graph(description)
375 return G
376
377
379 """test hook"""
380 import doctest
381 suite = doctest.DocFileSuite('tests/generators/small.txt',\
382 package='networkx')
383 return suite
384
385 if __name__ == "__main__":
386 import os
387 import sys
388 import unittest
389 if sys.version_info[:2] < (2, 4):
390 print "Python version 2.4 or later required for tests (%d.%d detected)"\
391 % sys.version_info[:2]
392 sys.exit(-1)
393
394 nxbase=sys.path[0]+os.sep+os.pardir
395 sys.path.insert(0,nxbase)
396 unittest.TextTestRunner().run(_test_suite())
397