networkx.generators.small

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 # Copyright (C) 2004,2005 by 10 # Aric Hagberg <hagberg@lanl.gov> 11 # Dan Schult <dschult@colgate.edu> 12 # Pieter Swart <swart@lanl.gov> 13 # Distributed under the terms of the GNU Lesser General Public License 14 # http://www.gnu.org/copyleft/lesser.html 15 import networkx 16 17 #------------------------------------------------------------------------------ 18 # Tools for creating small graphs 19 #------------------------------------------------------------------------------

20 -def make_small_graph(graph_description, create_using=None):

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

75 -def LCF_graph(n,shift_list,repeats):

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 # start with the n-cycle 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 # edges are added n_extra_edges times 122 # (not all of these need be new) 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)] #cycle through shift_list 128 v1=nodes[i%n] # cycle repeatedly through nodes 129 v2=nodes[(i + shift)%n] 130 G.add_edge(v1, v2) 131 return G

132 133 134 #------------------------------------------------------------------------------- 135 # Various small and named graphs 136 #------------------------------------------------------------------------------- 137

138 -def bull_graph():

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

149 -def chvatal_graph():

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

162 -def cubical_graph():

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

174 -def desargues_graph():

175 """ Return the Desargues graph.""" 176 G=LCF_graph(20,[5,-5,9,-9],5) 177 G.name="Desargues Graph" 178 return G

179

180 -def diamond_graph():

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

191 -def dodecahedral_graph():

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

197 -def frucht_graph():

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

211 -def heawood_graph():

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

217 -def house_graph():

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

228 -def house_x_graph():

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

239 -def icosahedral_graph():

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

253 -def krackhardt_kite_graph():

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

274 -def moebius_kantor_graph():

275 """Return the Moebius-Kantor graph.""" 276 G=LCF_graph(16,[5,-5],8) 277 G.name="Moebius-Kantor Graph" 278 return G

279

280 -def octahedral_graph():

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

291 -def pappus_graph():

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

297 -def petersen_graph():

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

310 -def sedgewick_maze_graph():

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

327 -def tetrahedral_graph():

328 """ Return the 3-regular Platonic Tetrahedral graph.""" 329 from networkx.generators.classic import complete_graph 330 G=complete_graph(4) 331 G.name="Platonic Tetrahedral graph" 332 return G

333

334 -def truncated_cube_graph():

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

350 -def truncated_tetrahedron_graph():

351 """Return the skeleton of the truncated Platonic tetrahedron.""" 352 G=networkx.path_graph(12) 353 # G.add_edges_from([(1,3),(1,10),(2,7),(4,12),(5,12),(6,8),(9,11)]) 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

358 -def tutte_graph():

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

378 -def _test_suite():

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 # directory of networkx package (relative to this) 394 nxbase=sys.path[0]+os.sep+os.pardir 395 sys.path.insert(0,nxbase) # prepend to search path 396 unittest.TextTestRunner().run(_test_suite()) 397

Source Code for Module networkx.generators.small