ioftools / networkxMiCe / networkxmaster / networkx / generators / small.py @ 5cef0f13
History  View  Annotate  Download (13.7 KB)
1 
# * coding: utf8 *


2 
"""

3 
Various small and named graphs, together with some compact generators.

4 

5 
"""

6 
__author__ = """Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)"""

7 
# Copyright (C) 20042019 by

8 
# Aric Hagberg <hagberg@lanl.gov>

9 
# Dan Schult <dschult@colgate.edu>

10 
# Pieter Swart <swart@lanl.gov>

11 
# All rights reserved.

12 
# BSD license.

13  
14 
__all__ = ['make_small_graph',

15 
'LCF_graph',

16 
'bull_graph',

17 
'chvatal_graph',

18 
'cubical_graph',

19 
'desargues_graph',

20 
'diamond_graph',

21 
'dodecahedral_graph',

22 
'frucht_graph',

23 
'heawood_graph',

24 
'hoffman_singleton_graph',

25 
'house_graph',

26 
'house_x_graph',

27 
'icosahedral_graph',

28 
'krackhardt_kite_graph',

29 
'moebius_kantor_graph',

30 
'octahedral_graph',

31 
'pappus_graph',

32 
'petersen_graph',

33 
'sedgewick_maze_graph',

34 
'tetrahedral_graph',

35 
'truncated_cube_graph',

36 
'truncated_tetrahedron_graph',

37 
'tutte_graph']

38  
39 
import networkx as nx 
40 
from networkx.generators.classic import empty_graph, cycle_graph, path_graph, complete_graph 
41 
from networkx.exception import NetworkXError 
42  
43 
#

44 
# Tools for creating small graphs

45 
#

46  
47  
48 
def make_small_undirected_graph(graph_description, create_using=None): 
49 
"""

50 
Return a small undirected graph described by graph_description.

51 

52 
See make_small_graph.

53 
"""

54 
G = empty_graph(0, create_using)

55 
if G.is_directed():

56 
raise NetworkXError("Directed Graph not supported") 
57 
return make_small_graph(graph_description, G)

58  
59  
60 
def make_small_graph(graph_description, create_using=None): 
61 
"""

62 
Return the small graph described by graph_description.

63 

64 
graph_description is a list of the form [ltype,name,n,xlist]

65 

66 
Here ltype is one of "adjacencylist" or "edgelist",

67 
name is the name of the graph and n the number of nodes.

68 
This constructs a graph of n nodes with integer labels 0,..,n1.

69 

70 
If ltype="adjacencylist" then xlist is an adjacency list

71 
with exactly n entries, in with the j'th entry (which can be empty)

72 
specifies the nodes connected to vertex j.

73 
e.g. the "square" graph C_4 can be obtained by

74 

75 
>>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[1,3],[2,4],[1,3]]])

76 

77 
or, since we do not need to add edges twice,

78 

79 
>>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[3],[4],[]]])

80 

81 
If ltype="edgelist" then xlist is an edge list

82 
written as [[v1,w2],[v2,w2],...,[vk,wk]],

83 
where vj and wj integers in the range 1,..,n

84 
e.g. the "square" graph C_4 can be obtained by

85 

86 
>>> G=nx.make_small_graph(["edgelist","C_4",4,[[1,2],[3,4],[2,3],[4,1]]])

87 

88 
Use the create_using argument to choose the graph class/type.

89 
"""

90 
ltype = graph_description[0]

91 
name = graph_description[1]

92 
n = graph_description[2]

93  
94 
G = empty_graph(n, create_using) 
95 
nodes = G.nodes() 
96  
97 
if ltype == "adjacencylist": 
98 
adjlist = graph_description[3]

99 
if len(adjlist) != n: 
100 
raise NetworkXError("invalid graph_description") 
101 
G.add_edges_from([(u  1, v) for v in nodes for u in adjlist[v]]) 
102 
elif ltype == "edgelist": 
103 
edgelist = graph_description[3]

104 
for e in edgelist: 
105 
v1 = e[0]  1 
106 
v2 = e[1]  1 
107 
if v1 < 0 or v1 > n  1 or v2 < 0 or v2 > n  1: 
108 
raise NetworkXError("invalid graph_description") 
109 
else:

110 
G.add_edge(v1, v2) 
111 
G.name = name 
112 
return G

113  
114  
115 
def LCF_graph(n, shift_list, repeats, create_using=None): 
116 
"""

117 
Return the cubic graph specified in LCF notation.

118 

119 
LCF notation (LCF=LederbergCoxeterFruchte) is a compressed

120 
notation used in the generation of various cubic Hamiltonian

121 
graphs of high symmetry. See, for example, dodecahedral_graph,

122 
desargues_graph, heawood_graph and pappus_graph below.

123 

124 
n (number of nodes)

125 
The starting graph is the ncycle with nodes 0,...,n1.

126 
(The null graph is returned if n < 0.)

127 

128 
shift_list = [s1,s2,..,sk], a list of integer shifts mod n,

129 

130 
repeats

131 
integer specifying the number of times that shifts in shift_list

132 
are successively applied to each v_current in the ncycle

133 
to generate an edge between v_current and v_current+shift mod n.

134 

135 
For v1 cycling through the ncycle a total of k*repeats

136 
with shift cycling through shiftlist repeats times connect

137 
v1 with v1+shift mod n

138 

139 
The utility graph $K_{3,3}$

140 

141 
>>> G = nx.LCF_graph(6, [3, 3], 3)

142 

143 
The Heawood graph

144 

145 
>>> G = nx.LCF_graph(14, [5, 5], 7)

146 

147 
See http://mathworld.wolfram.com/LCFNotation.html for a description

148 
and references.

149 

150 
"""

151 
if n <= 0: 
152 
return empty_graph(0, create_using) 
153  
154 
# start with the ncycle

155 
G = cycle_graph(n, create_using) 
156 
if G.is_directed():

157 
raise NetworkXError("Directed Graph not supported") 
158 
G.name = "LCF_graph"

159 
nodes = sorted(list(G)) 
160  
161 
n_extra_edges = repeats * len(shift_list)

162 
# edges are added n_extra_edges times

163 
# (not all of these need be new)

164 
if n_extra_edges < 1: 
165 
return G

166  
167 
for i in range(n_extra_edges): 
168 
shift = shift_list[i % len(shift_list)] # cycle through shift_list 
169 
v1 = nodes[i % n] # cycle repeatedly through nodes

170 
v2 = nodes[(i + shift) % n] 
171 
G.add_edge(v1, v2) 
172 
return G

173  
174  
175 
#

176 
# Various small and named graphs

177 
#

178  
179 
def bull_graph(create_using=None): 
180 
"""Returns the Bull graph. """

181 
description = [ 
182 
"adjacencylist",

183 
"Bull Graph",

184 
5,

185 
[[2, 3], [1, 3, 4], [1, 2, 5], [2], [3]] 
186 
] 
187 
G = make_small_undirected_graph(description, create_using) 
188 
return G

189  
190  
191 
def chvatal_graph(create_using=None): 
192 
"""Returns the Chvátal graph."""

193 
description = [ 
194 
"adjacencylist",

195 
"Chvatal Graph",

196 
12,

197 
[[2, 5, 7, 10], [3, 6, 8], [4, 7, 9], [5, 8, 10], 
198 
[6, 9], [11, 12], [11, 12], [9, 12], 
199 
[11], [11, 12], [], []] 
200 
] 
201 
G = make_small_undirected_graph(description, create_using) 
202 
return G

203  
204  
205 
def cubical_graph(create_using=None): 
206 
"""Returns the 3regular Platonic Cubical graph."""

207 
description = [ 
208 
"adjacencylist",

209 
"Platonic Cubical Graph",

210 
8,

211 
[[2, 4, 5], [1, 3, 8], [2, 4, 7], [1, 3, 6], 
212 
[1, 6, 8], [4, 5, 7], [3, 6, 8], [2, 5, 7]] 
213 
] 
214 
G = make_small_undirected_graph(description, create_using) 
215 
return G

216  
217  
218 
def desargues_graph(create_using=None): 
219 
""" Return the Desargues graph."""

220 
G = LCF_graph(20, [5, 5, 9, 9], 5, create_using) 
221 
G.name = "Desargues Graph"

222 
return G

223  
224  
225 
def diamond_graph(create_using=None): 
226 
"""Returns the Diamond graph. """

227 
description = [ 
228 
"adjacencylist",

229 
"Diamond Graph",

230 
4,

231 
[[2, 3], [1, 3, 4], [1, 2, 4], [2, 3]] 
232 
] 
233 
G = make_small_undirected_graph(description, create_using) 
234 
return G

235  
236  
237 
def dodecahedral_graph(create_using=None): 
238 
""" Return the Platonic Dodecahedral graph. """

239 
G = LCF_graph(20, [10, 7, 4, 4, 7, 10, 4, 7, 7, 4], 2, create_using) 
240 
G.name = "Dodecahedral Graph"

241 
return G

242  
243  
244 
def frucht_graph(create_using=None): 
245 
"""Returns the Frucht Graph.

246 

247 
The Frucht Graph is the smallest cubical graph whose

248 
automorphism group consists only of the identity element.

249 

250 
"""

251 
G = cycle_graph(7, create_using)

252 
G.add_edges_from([[0, 7], [1, 7], [2, 8], [3, 9], [4, 9], [5, 10], [6, 10], 
253 
[7, 11], [8, 11], [8, 9], [10, 11]]) 
254  
255 
G.name = "Frucht Graph"

256 
return G

257  
258  
259 
def heawood_graph(create_using=None): 
260 
""" Return the Heawood graph, a (3,6) cage. """

261 
G = LCF_graph(14, [5, 5], 7, create_using) 
262 
G.name = "Heawood Graph"

263 
return G

264  
265  
266 
def hoffman_singleton_graph(): 
267 
'''Return the HoffmanSingleton Graph.'''

268 
G = nx.Graph() 
269 
for i in range(5): 
270 
for j in range(5): 
271 
G.add_edge(('pentagon', i, j), ('pentagon', i, (j  1) % 5)) 
272 
G.add_edge(('pentagon', i, j), ('pentagon', i, (j + 1) % 5)) 
273 
G.add_edge(('pentagram', i, j), ('pentagram', i, (j  2) % 5)) 
274 
G.add_edge(('pentagram', i, j), ('pentagram', i, (j + 2) % 5)) 
275 
for k in range(5): 
276 
G.add_edge(('pentagon', i, j),

277 
('pentagram', k, (i * k + j) % 5)) 
278 
G = nx.convert_node_labels_to_integers(G) 
279 
G.name = 'HoffmanSingleton Graph'

280 
return G

281  
282  
283 
def house_graph(create_using=None): 
284 
"""Returns the House graph (square with triangle on top)."""

285 
description = [ 
286 
"adjacencylist",

287 
"House Graph",

288 
5,

289 
[[2, 3], [1, 4], [1, 4, 5], [2, 3, 5], [3, 4]] 
290 
] 
291 
G = make_small_undirected_graph(description, create_using) 
292 
return G

293  
294  
295 
def house_x_graph(create_using=None): 
296 
"""Returns the House graph with a cross inside the house square."""

297 
description = [ 
298 
"adjacencylist",

299 
"HousewithXinside Graph",

300 
5,

301 
[[2, 3, 4], [1, 3, 4], [1, 2, 4, 5], [1, 2, 3, 5], [3, 4]] 
302 
] 
303 
G = make_small_undirected_graph(description, create_using) 
304 
return G

305  
306  
307 
def icosahedral_graph(create_using=None): 
308 
"""Returns the Platonic Icosahedral graph."""

309 
description = [ 
310 
"adjacencylist",

311 
"Platonic Icosahedral Graph",

312 
12,

313 
[[2, 6, 8, 9, 12], [3, 6, 7, 9], [4, 7, 9, 10], [5, 7, 10, 11], 
314 
[6, 7, 11, 12], [7, 12], [], [9, 10, 11, 12], 
315 
[10], [11], [12], []] 
316 
] 
317 
G = make_small_undirected_graph(description, create_using) 
318 
return G

319  
320  
321 
def krackhardt_kite_graph(create_using=None): 
322 
"""

323 
Return the Krackhardt Kite Social Network.

324 

325 
A 10 actor social network introduced by David Krackhardt

326 
to illustrate: degree, betweenness, centrality, closeness, etc.

327 
The traditional labeling is:

328 
Andre=1, Beverley=2, Carol=3, Diane=4,

329 
Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10.

330 

331 
"""

332 
description = [ 
333 
"adjacencylist",

334 
"Krackhardt Kite Social Network",

335 
10,

336 
[[2, 3, 4, 6], [1, 4, 5, 7], [1, 4, 6], [1, 2, 3, 5, 6, 7], [2, 4, 7], 
337 
[1, 3, 4, 7, 8], [2, 4, 5, 6, 8], [6, 7, 9], [8, 10], [9]] 
338 
] 
339 
G = make_small_undirected_graph(description, create_using) 
340 
return G

341  
342  
343 
def moebius_kantor_graph(create_using=None): 
344 
"""Returns the MoebiusKantor graph."""

345 
G = LCF_graph(16, [5, 5], 8, create_using) 
346 
G.name = "MoebiusKantor Graph"

347 
return G

348  
349  
350 
def octahedral_graph(create_using=None): 
351 
"""Returns the Platonic Octahedral graph."""

352 
description = [ 
353 
"adjacencylist",

354 
"Platonic Octahedral Graph",

355 
6,

356 
[[2, 3, 4, 5], [3, 4, 6], [5, 6], [5, 6], [6], []] 
357 
] 
358 
G = make_small_undirected_graph(description, create_using) 
359 
return G

360  
361  
362 
def pappus_graph(): 
363 
""" Return the Pappus graph."""

364 
G = LCF_graph(18, [5, 7, 7, 7, 7, 5], 3) 
365 
G.name = "Pappus Graph"

366 
return G

367  
368  
369 
def petersen_graph(create_using=None): 
370 
"""Returns the Petersen graph."""

371 
description = [ 
372 
"adjacencylist",

373 
"Petersen Graph",

374 
10,

375 
[[2, 5, 6], [1, 3, 7], [2, 4, 8], [3, 5, 9], [4, 1, 10], [1, 8, 9], [2, 9, 10], 
376 
[3, 6, 10], [4, 6, 7], [5, 7, 8]] 
377 
] 
378 
G = make_small_undirected_graph(description, create_using) 
379 
return G

380  
381  
382 
def sedgewick_maze_graph(create_using=None): 
383 
"""

384 
Return a small maze with a cycle.

385 

386 
This is the maze used in Sedgewick,3rd Edition, Part 5, Graph

387 
Algorithms, Chapter 18, e.g. Figure 18.2 and following.

388 
Nodes are numbered 0,..,7

389 
"""

390 
G = empty_graph(0, create_using)

391 
G.add_nodes_from(range(8)) 
392 
G.add_edges_from([[0, 2], [0, 7], [0, 5]]) 
393 
G.add_edges_from([[1, 7], [2, 6]]) 
394 
G.add_edges_from([[3, 4], [3, 5]]) 
395 
G.add_edges_from([[4, 5], [4, 7], [4, 6]]) 
396 
G.name = "Sedgewick Maze"

397 
return G

398  
399  
400 
def tetrahedral_graph(create_using=None): 
401 
""" Return the 3regular Platonic Tetrahedral graph."""

402 
G = complete_graph(4, create_using)

403 
G.name = "Platonic Tetrahedral graph"

404 
return G

405  
406  
407 
def truncated_cube_graph(create_using=None): 
408 
"""Returns the skeleton of the truncated cube."""

409 
description = [ 
410 
"adjacencylist",

411 
"Truncated Cube Graph",

412 
24,

413 
[[2, 3, 5], [12, 15], [4, 5], [7, 9], 
414 
[6], [17, 19], [8, 9], [11, 13], 
415 
[10], [18, 21], [12, 13], [15], 
416 
[14], [22, 23], [16], [20, 24], 
417 
[18, 19], [21], [20], [24], 
418 
[22], [23], [24], []] 
419 
] 
420 
G = make_small_undirected_graph(description, create_using) 
421 
return G

422  
423  
424 
def truncated_tetrahedron_graph(create_using=None): 
425 
"""Returns the skeleton of the truncated Platonic tetrahedron."""

426 
G = path_graph(12, create_using)

427 
# G.add_edges_from([(1,3),(1,10),(2,7),(4,12),(5,12),(6,8),(9,11)])

428 
G.add_edges_from([(0, 2), (0, 9), (1, 6), (3, 11), (4, 11), (5, 7), (8, 10)]) 
429 
G.name = "Truncated Tetrahedron Graph"

430 
return G

431  
432  
433 
def tutte_graph(create_using=None): 
434 
"""Returns the Tutte graph."""

435 
description = [ 
436 
"adjacencylist",

437 
"Tutte's Graph",

438 
46,

439 
[[2, 3, 4], [5, 27], [11, 12], [19, 20], [6, 34], 
440 
[7, 30], [8, 28], [9, 15], [10, 39], [11, 38], 
441 
[40], [13, 40], [14, 36], [15, 16], [35], 
442 
[17, 23], [18, 45], [19, 44], [46], [21, 46], 
443 
[22, 42], [23, 24], [41], [25, 28], [26, 33], 
444 
[27, 32], [34], [29], [30, 33], [31], 
445 
[32, 34], [33], [], [], [36, 39], 
446 
[37], [38, 40], [39], [], [], 
447 
[42, 45], [43], [44, 46], [45], [], []] 
448 
] 
449 
G = make_small_undirected_graph(description, create_using) 
450 
return G
