Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/generators/small.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
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) 2004-2019 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,..,n-1.
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=Lederberg-Coxeter-Fruchte) 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 n-cycle with nodes 0,...,n-1.
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 n-cycle
133 to generate an edge between v_current and v_current+shift mod n.
134
135 For v1 cycling through the n-cycle 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 n-cycle
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 3-regular 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 Hoffman-Singleton 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 = 'Hoffman-Singleton 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 "House-with-X-inside 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 Moebius-Kantor graph."""
345 G = LCF_graph(16, [5, -5], 8, create_using)
346 G.name = "Moebius-Kantor 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 3-regular 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