Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / small.py @ 5cef0f13

History | View | Annotate | Download (13.7 KB)

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