networkx.generators.classic

1 """ 2 Generators for some classic graphs. 3 4 The typical graph generator is called as follows: 5 6 >>> G=complete_graph(100) 7 8 returning the complete graph on n nodes labeled 0,..,99 9 as a simple graph. Except for empty_graph, all the generators 10 in this module return a Graph class (i.e. a simple, undirected graph). 11 12 """ 13 # Copyright (C) 2004,2005 by 14 # Aric Hagberg <hagberg@lanl.gov> 15 # Dan Schult <dschult@colgate.edu> 16 # Pieter Swart <swart@lanl.gov> 17 # Distributed under the terms of the GNU Lesser General Public License 18 # http://www.gnu.org/copyleft/lesser.html 19 __author__ ="""Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)""" 20 __date__ = "$Date: 2005-06-17 14:06:03 -0600 (Fri, 17 Jun 2005) $" 21 __credits__ = """""" 22 __revision__ = "$Revision: 1056 $" 23 24 25 #------------------------------------------------------------------- 26 # Some Classic Graphs 27 #------------------------------------------------------------------- 28 import networkx 29 30

31 -def balanced_tree(r,h):

32 """Return the perfectly balanced r-tree of height h. 33 34 For r>=2, h>=1, this is the rooted tree where all leaves 35 are at distance h from the root. 36 The root has degree r and all other internal nodes have degree r+1. 37 38 number_of_nodes = 1+r+r**2+...+r**h = (r**(h+1)-1)/(r-1), 39 number_of_edges = number_of_nodes - 1. 40 41 Node labels are the integers 0 (the root) up to 42 number_of_nodes - 1. 43 44 """ 45 if r<2: 46 raise networkx.NetworkXError, \ 47 "Invalid graph description, r should be >=2" 48 if h<1: 49 raise networkx.NetworkXError, \ 50 "Invalid graph description, h should be >=1" 51 52 G=empty_graph() 53 G.name="balanced_tree(%d,%d)"%(r,h) 54 55 # Grow tree of increasing height by repeatedly adding a layer 56 # of new leaves to current leaves. 57 58 # First create root of degree r 59 root=0 60 v=root 61 G.add_node(v) 62 newleavelist=[] 63 i=0 64 while i < r: 65 v=v+1 66 G.add_edge(root,v) 67 newleavelist.append(v) 68 i=i+1 69 # All other internal nodes have degree r+1 70 height=1 71 while height<h: 72 leavelist=newleavelist[:] 73 newleavelist=[] 74 for leave in leavelist: 75 for i in xrange(r): 76 v=v+1 77 G.add_edge(leave,v) 78 newleavelist.append(v) 79 height=height+1 80 return G

81

82 -def barbell_graph(m1,m2):

83 """Return the Barbell Graph: two complete graphs connected by a path. 84 85 For m1 > 1 and m2 >= 0. 86 87 Two identical complete graphs K_{m1} form the left and right bells, 88 and are connected by a path P_{m2}. 89 90 The 2*m1+m2 nodes are numbered 91 0,...,m1-1 for the left barbell, 92 m1,...,m1+m2-1 for the path, 93 and m1+m2,...,2*m1+m2-1 for the right barbell. 94 95 The 3 subgraphs are joined via the edges (m1-1,m1) and (m1+m2-1,m1+m2). 96 If m2=0, this is merely two complete graphs joined together. 97 98 This graph is an extremal example in David Aldous 99 and Jim Fill's etext on Random Walks on Graphs. 100 101 """ 102 if m1<2: 103 raise networkx.NetworkXError, \ 104 "Invalid graph description, m1 should be >=2" 105 if m2<0: 106 raise networkx.NetworkXError, \ 107 "Invalid graph description, m2 should be >=0" 108 109 # left barbell 110 G=complete_graph(m1) 111 G.name="barbell_graph(%d,%d)"%(m1,m2) 112 113 # connecting path 114 G.add_nodes_from([v for v in range(m1,m1+m2-1)]) 115 if m2>1: 116 G.add_edges_from([(v,v+1) for v in range(m1,m1+m2-1)]) 117 # right barbell 118 for u in range(m1+m2,2*m1+m2): 119 for v in range(u,2*m1+m2): 120 G.add_edge(u,v) 121 # connect it up 122 G.add_edge(m1-1,m1) 123 if m2>0: 124 G.add_edge(m1+m2-1,m1+m2) 125 return G

126

127 -def complete_graph(n,create_using=None):

128 """ Return the Complete graph K_n with n nodes. 129 130 Node labels are the integers 0 to n-1. 131 132 """ 133 G=empty_graph(n,create_using) 134 G.name="complete_graph(%d)"%n 135 for u in xrange(n): 136 for v in xrange(n): 137 G.add_edge(u,v) 138 return G

139

140 -def complete_bipartite_graph(n1,n2):

141 """Return the complete bipartite graph K_{n1_n2}. 142 143 Composed of two partitions with n1 nodes in the first 144 and n2 nodes in the second. Each node in the first is 145 connected to each node in the second. 146 147 Node labels are the integers 0 to n1+n2-1 148 149 """ 150 G=empty_graph(n1+n2) 151 G.name="complete_bipartite_graph(%d,%d)"%(n1,n2) 152 for v1 in xrange(n1): 153 for v2 in xrange(n2): 154 G.add_edge(v1,n1+v2) 155 return G

156

157 -def circular_ladder_graph(n):

158 """Return the circular ladder graph CL_n of length n. 159 160 CL_n consists of two concentric n-cycles in which 161 each of the n pairs of concentric nodes are joined by an edge. 162 163 Node labels are the integers 0 to n-1 164 165 """ 166 G=ladder_graph(n) 167 G.name="circular_ladder_graph(%d)"%n 168 G.add_edge(0,n-1) 169 G.add_edge(n,2*n-1) 170 return G

171

172 -def cycle_graph(n,create_using=None):

173 """Return the cycle graph C_n over n nodes. 174 175 C_n is the n-path with two end-nodes connected. 176 177 Node labels are the integers 0 to n-1 178 If create_using is a DiGraph, the direction is in increasing order. 179 180 """ 181 G=path_graph(n,create_using) 182 G.name="cycle_graph(%d)"%n 183 if n>1: G.add_edge(n-1,0) 184 return G

185

186 -def dorogovtsev_goltsev_mendes_graph(n):

187 """Return the hierarchically constructed Dorogovtsev-Goltsev-Mendes graph. 188 189 n is the generation. 190 See: arXiv:/cond-mat/0112143 by Dorogovtsev, Goltsev and Mendes. 191 192 """ 193 G=networkx.Graph() 194 G.name="Dorogovtsev-Goltsev-Mendes Graph" 195 G.add_edge(0,1) 196 if n==0: 197 return G 198 new_node = 2 # next node to be added 199 for i in range(1,n+1): #iterate over number of generations. 200 last_generation_edges = G.edges() 201 number_of_edges_in_last_generation = len(last_generation_edges) 202 for j in range(0,number_of_edges_in_last_generation): 203 G.add_edge(new_node,last_generation_edges[j][0]) 204 G.add_edge(new_node,last_generation_edges[j][1]) 205 new_node += 1 206 return G

207

208 -def empty_graph(n=0,create_using=None):

209 """Return the empty graph with n nodes and zero edges. 210 211 Node labels are the integers 0 to n-1 212 213 For example: 214 >>> from networkx import * 215 >>> G=empty_graph(10) 216 >>> G.number_of_nodes() 217 10 218 >>> G.number_of_edges() 219 0 220 221 The variable create_using should point to a "graph"-like object that 222 will be cleaned (nodes and edges will be removed) and refitted as 223 an empty "graph" with n nodes with integer labels. This capability 224 is useful for specifying the class-nature of the resulting empty 225 "graph" (i.e. Graph, DiGraph, MyWeirdGraphClass, etc.). 226 227 The variable create_using has two main uses: 228 Firstly, the variable create_using can be used to create an 229 empty digraph, network,etc. For example, 230 231 >>> n=10 232 >>> G=empty_graph(n,create_using=DiGraph()) 233 234 will create an empty digraph on n nodes. 235 236 Secondly, one can pass an existing graph (digraph, pseudograph, 237 etc.) via create_using. For example, if G is an existing graph 238 (resp. digraph, pseudograph, etc.), then empty_graph(n,create_using=G) 239 will empty G (i.e. delete all nodes and edges using G.clear() in 240 base) and then add n nodes and zero edges, and return the modified 241 graph (resp. digraph, pseudograph, etc.). 242 243 See also create_empty_copy(G). 244 245 """ 246 if create_using is None: 247 # default empty graph is a simple graph 248 G=networkx.Graph() 249 else: 250 G=create_using 251 G.clear() 252 253 G.add_nodes_from(xrange(n)) 254 G.name="empty_graph(%d)"%n 255 return G

256

257 -def grid_2d_graph(m,n,periodic=False):

258 """ Return the 2d grid graph of mxn nodes, 259 each connected to its nearest neighbors. 260 Optional argument periodic=True will connect 261 boundary nodes via periodic boundary conditions. 262 """ 263 G=empty_graph() 264 G.name="grid 2d graph" 265 rows=range(m) 266 columns=range(n) 267 def _label(i,j): 268 return (i,j)

269 for i in rows: 270 for j in columns: 271 G.add_node( _label(i,j) ) 272 for i in rows: 273 for j in columns: 274 if i>0: G.add_edge( _label(i,j), _label(i-1,j) ) 275 if i<m-1: G.add_edge( _label(i,j), _label(i+1,j) ) 276 if j>0: G.add_edge( _label(i,j), _label(i,j-1) ) 277 if j<n-1: G.add_edge( _label(i,j), _label(i,j+1) ) 278 if periodic: 279 for i in rows: 280 G.add_edge(_label(i,0), _label(i,n-1)) 281 for j in columns: 282 G.add_edge(_label(0,j), _label(m-1,j)) 283 G.name="periodic_grid_2d_graph(%d,%d)"%(m,n) 284 return G 285 286

287 -def grid_graph(dim,periodic=False):

288 """ Return the n-dimensional grid graph. 289 290 The dimension is the length of the list 'dim' and the 291 size in each dimension is the value of the list element. 292 293 E.g. G=grid_graph(dim=[2,3]) produces a 2x3 grid graph. 294 295 If periodic=True then join grid edges with periodic boundary conditions. 296 297 """ 298 from networkx.utils import is_list_of_ints 299 dlabel="%s"%dim 300 if dim==[]: 301 G=networkx.Graph() 302 G.name="grid_graph(%s)"%dim 303 return G 304 if not is_list_of_ints(dim): 305 raise networkx.NetworkXError,"dim is not a list of integers" 306 if min(dim)<=0: 307 raise networkx.NetworkXError,\ 308 "dim is not a list of strictly positive integers" 309 if periodic: 310 func=cycle_graph 311 else: 312 func=path_graph 313 314 current_dim=dim.pop() 315 G=func(current_dim) 316 while len(dim)>0: 317 current_dim=dim.pop() 318 Gnew=func(current_dim) 319 Gold=G.copy() 320 G=networkx.operators.cartesian_product(Gnew,Gold) 321 # graph G is done but has labels of the form (1,(2,(3,1))) 322 # so relabel 323 H=networkx.operators.relabel_nodes(G, networkx.utils.flatten) 324 H.name="grid_graph(%s)"%dlabel 325 return H

326

327 -def hypercube_graph(n):

328 """Return the n-dimensional hypercube. 329 330 Node labels are the integers 0 to 2**n - 1. 331 332 """ 333 dim=n*[2] 334 G=grid_graph(dim) 335 G.name="hypercube_graph_(%d)"%n 336 return G

337

338 -def ladder_graph(n):

339 """Return the Ladder graph of length n. 340 341 This is two rows of n nodes, with 342 each pair connected by a single edge. 343 344 Node labels are the integers 0 to 2*n - 1. 345 346 """ 347 G=empty_graph(2*n) 348 G.name="ladder_graph_(%d)"%n 349 G.add_edges_from([(v,v+1) for v in xrange(n-1)]) 350 G.add_edges_from([(v,v+1) for v in xrange(n,2*n-1)]) 351 G.add_edges_from([(v,v+n) for v in xrange(n)]) 352 return G

353

354 -def lollipop_graph(m,n):

355 """Return the Lollipop Graph; K_m connected to P_n. 356 357 This is the Barbell Graph without the right barbell. 358 359 For m>1 and n>=0, the complete graph K_m is connected to the 360 path P_n. The resulting m+n nodes are labelled 0,...,m-1 for the 361 complete graph and m,...,m+n-1 for the path. The 2 subgraphs 362 are joined via the edge (m-1,m). If n=0, this is merely a complete 363 graph. 364 365 Node labels are the integers 0 to number_of_nodes - 1. 366 367 (This graph is an extremal example in David Aldous and Jim 368 Fill's etext on Random Walks on Graphs.) 369 370 """ 371 if m<2: 372 raise networkx.NetworkXError, \ 373 "Invalid graph description, m should be >=2" 374 if n<0: 375 raise networkx.NetworkXError, \ 376 "Invalid graph description, n should be >=0" 377 # the ball 378 G=complete_graph(m) 379 # the stick 380 G.add_nodes_from([v for v in xrange(m,m+n)]) 381 if n>1: 382 G.add_edges_from([(v,v+1) for v in xrange(m,m+n-1)]) 383 # connect ball to stick 384 if m>0: G.add_edge(m-1,m) 385 G.name="lollipop_graph(%d,%d)"%(m,n) 386 return G

387

388 -def null_graph(create_using=None):

389 """ Return the Null graph with no nodes or edges. 390 391 See empty_graph for the use of create_using. 392 393 """ 394 G=empty_graph(0,create_using) 395 G.name="null_graph()" 396 return G

397

398 -def path_graph(n,create_using=None):

399 """Return the Path graph P_n of n nodes linearly connected 400 by n-1 edges. 401 402 Node labels are the integers 0 to n - 1. 403 If create_using is a DiGraph then the edges are directed in 404 increasing order. 405 406 """ 407 G=empty_graph(n,create_using) 408 G.name="path_graph(%d)"%n 409 G.add_edges_from([(v,v+1) for v in xrange(n-1)]) 410 return G

411

412 -def star_graph(n):

413 """ Return the Star graph with n+1 nodes: 414 one center node, connected to n outer nodes. 415 416 Node labels are the integers 0 to n. 417 418 """ 419 G=complete_bipartite_graph(1,n) 420 G.name="star_graph(%d)"%n 421 return G

422

423 -def trivial_graph():

424 """ Return the Trivial graph with one node (with integer label 0) 425 and no edges. 426 427 """ 428 G=empty_graph(1) 429 G.name="trivial_graph()" 430 return G

431

432 -def wheel_graph(n):

433 """ Return the wheel graph: a single hub node connected 434 to each node of the (n-1)-node cycle graph. 435 436 Node labels are the integers 0 to n - 1. 437 438 """ 439 G=star_graph(n-1) 440 G.name="wheel_graph(%d)"%n 441 G.add_edges_from([(v,v+1) for v in xrange(1,n-1)]) 442 if n>1: 443 G.add_edge(1,n-1) 444 return G

445 446

447 -def _test_suite():

448 import doctest 449 suite = doctest.DocFileSuite('tests/generators/classic.txt', 450 package='networkx') 451 return suite

452 453 454 if __name__ == "__main__": 455 import os 456 import sys 457 import unittest 458 if sys.version_info[:2] < (2, 4): 459 print "Python version 2.4 or later required (%d.%d detected)."\ 460 % sys.version_info[:2] 461 sys.exit(-1) 462 # directory of networkx package (relative to this) 463 nxbase=sys.path[0]+os.sep+os.pardir 464 sys.path.insert(0,nxbase) # prepend to search path 465 unittest.TextTestRunner().run(_test_suite()) 466

Source Code for Module networkx.generators.classic