Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.68 KB)

1
#    Copyright (C) 2004-2019 by
2
#    Aric Hagberg <hagberg@lanl.gov>
3
#    Dan Schult <dschult@colgate.edu>
4
#    Pieter Swart <swart@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
#
8
# Author:
9
#     Pieter Swart <swart@lanl.gov>
10
"""
11
Generators for the small graph atlas.
12
"""
13
import gzip
14
from itertools import islice
15
import os
16
import os.path
17

    
18
import networkx as nx
19

    
20
__all__ = ['graph_atlas', 'graph_atlas_g']
21

    
22
#: The total number of graphs in the atlas.
23
#:
24
#: The graphs are labeled starting from 0 and extending to (but not
25
#: including) this number.
26
NUM_GRAPHS = 1253
27

    
28
#: The absolute path representing the directory containing this file.
29
THIS_DIR = os.path.dirname(os.path.abspath(__file__))
30

    
31
#: The path to the data file containing the graph edge lists.
32
#:
33
#: This is the absolute filename of the gzipped text file containing the
34
#: edge list for each graph in the atlas. The file contains one entry
35
#: per graph in the atlas, in sequential order, starting from graph
36
#: number 0 and extending through graph number 1252 (see
37
#: :data:`NUM_GRAPHS`). Each entry looks like
38
#:
39
#: .. sourcecode:: text
40
#:
41
#:    GRAPH 6
42
#:    NODES 3
43
#:    0 1
44
#:    0 2
45
#:
46
#: where the first two lines are the graph's index in the atlas and the
47
#: number of nodes in the graph, and the remaining lines are the edge
48
#: list.
49
#:
50
#: This file was generated from a Python list of graphs via code like
51
#: the following::
52
#:
53
#:     import gzip
54
#:     from networkx.generators.atlas import graph_atlas_g
55
#:     from networkx.readwrite.edgelist import write_edgelist
56
#:
57
#:     with gzip.open('atlas.dat.gz', 'wb') as f:
58
#:         for i, G in enumerate(graph_atlas_g()):
59
#:             f.write(bytes('GRAPH {}\n'.format(i), encoding='utf-8'))
60
#:             f.write(bytes('NODES {}\n'.format(len(G)), encoding='utf-8'))
61
#:             write_edgelist(G, f, data=False)
62
#:
63
ATLAS_FILE = os.path.join(THIS_DIR, 'atlas.dat.gz')
64

    
65

    
66
def _generate_graphs():
67
    """Sequentially read the file containing the edge list data for the
68
    graphs in the atlas and generate the graphs one at a time.
69

70
    This function reads the file given in :data:`.ATLAS_FILE`.
71

72
    """
73
    with gzip.open(ATLAS_FILE, 'rb') as f:
74
        line = f.readline()
75
        while line and line.startswith(b'GRAPH'):
76
            # The first two lines of each entry tell us the index of the
77
            # graph in the list and the number of nodes in the graph.
78
            # They look like this:
79
            #
80
            #     GRAPH 3
81
            #     NODES 2
82
            #
83
            graph_index = int(line[6:].rstrip())
84
            line = f.readline()
85
            num_nodes = int(line[6:].rstrip())
86
            # The remaining lines contain the edge list, until the next
87
            # GRAPH line (or until the end of the file).
88
            edgelist = []
89
            line = f.readline()
90
            while line and not line.startswith(b'GRAPH'):
91
                edgelist.append(line.rstrip())
92
                line = f.readline()
93
            G = nx.Graph()
94
            G.name = 'G{}'.format(graph_index)
95
            G.add_nodes_from(range(num_nodes))
96
            G.add_edges_from(tuple(map(int, e.split())) for e in edgelist)
97
            yield G
98

    
99

    
100
def graph_atlas(i):
101
    """Returns graph number `i` from the Graph Atlas.
102

103
    For more information, see :func:`.graph_atlas_g`.
104

105
    Parameters
106
    ----------
107
    i : int
108
        The index of the graph from the atlas to get. The graph at index
109
        0 is assumed to be the null graph.
110

111
    Returns
112
    -------
113
    list
114
        A list of :class:`~networkx.Graph` objects, the one at index *i*
115
        corresponding to the graph *i* in the Graph Atlas.
116

117
    See also
118
    --------
119
    graph_atlas_g
120

121
    Notes
122
    -----
123
    The time required by this function increases linearly with the
124
    argument `i`, since it reads a large file sequentially in order to
125
    generate the graph [1]_.
126

127
    References
128
    ----------
129
    .. [1] Ronald C. Read and Robin J. Wilson, *An Atlas of Graphs*.
130
           Oxford University Press, 1998.
131

132
    """
133
    if not (0 <= i < NUM_GRAPHS):
134
        raise ValueError('index must be between 0 and {}'.format(NUM_GRAPHS))
135
    return next(islice(_generate_graphs(), i, None))
136

    
137

    
138
def graph_atlas_g():
139
    """Returns the list of all graphs with up to seven nodes named in the
140
    Graph Atlas.
141

142
    The graphs are listed in increasing order by
143

144
    1. number of nodes,
145
    2. number of edges,
146
    3. degree sequence (for example 111223 < 112222),
147
    4. number of automorphisms,
148

149
    in that order, with three exceptions as described in the *Notes*
150
    section below. This causes the list to correspond with the index of
151
    the graphs in the Graph Atlas [atlas]_, with the first graph,
152
    ``G[0]``, being the null graph.
153

154
    Returns
155
    -------
156
    list
157
        A list of :class:`~networkx.Graph` objects, the one at index *i*
158
        corresponding to the graph *i* in the Graph Atlas.
159

160
    See also
161
    --------
162
    graph_atlas
163

164
    Notes
165
    -----
166
    This function may be expensive in both time and space, since it
167
    reads a large file sequentially in order to populate the list.
168

169
    Although the NetworkX atlas functions match the order of graphs
170
    given in the "Atlas of Graphs" book, there are (at least) three
171
    errors in the ordering described in the book. The following three
172
    pairs of nodes violate the lexicographically nondecreasing sorted
173
    degree sequence rule:
174

175
    - graphs 55 and 56 with degree sequences 001111 and 000112,
176
    - graphs 1007 and 1008 with degree sequences 3333444 and 3333336,
177
    - graphs 1012 and 1213 with degree sequences 1244555 and 1244456.
178

179
    References
180
    ----------
181
    .. [atlas] Ronald C. Read and Robin J. Wilson,
182
               *An Atlas of Graphs*.
183
               Oxford University Press, 1998.
184

185
    """
186
    return list(_generate_graphs())