Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Generators for the small graph atlas.
3"""
5import gzip
6import importlib.resources
7from itertools import islice
9import networkx as nx
11__all__ = ["graph_atlas", "graph_atlas_g"]
13#: The total number of graphs in the atlas.
14#:
15#: The graphs are labeled starting from 0 and extending to (but not
16#: including) this number.
17NUM_GRAPHS = 1253
19#: The path to the data file containing the graph edge lists.
20#:
21#: This is the absolute path of the gzipped text file containing the
22#: edge list for each graph in the atlas. The file contains one entry
23#: per graph in the atlas, in sequential order, starting from graph
24#: number 0 and extending through graph number 1252 (see
25#: :data:`NUM_GRAPHS`). Each entry looks like
26#:
27#: .. sourcecode:: text
28#:
29#: GRAPH 6
30#: NODES 3
31#: 0 1
32#: 0 2
33#:
34#: where the first two lines are the graph's index in the atlas and the
35#: number of nodes in the graph, and the remaining lines are the edge
36#: list.
37#:
38#: This file was generated from a Python list of graphs via code like
39#: the following::
40#:
41#: import gzip
42#: from networkx.generators.atlas import graph_atlas_g
43#: from networkx.readwrite.edgelist import write_edgelist
44#:
45#: with gzip.open('atlas.dat.gz', 'wb') as f:
46#: for i, G in enumerate(graph_atlas_g()):
47#: f.write(bytes(f'GRAPH {i}\n', encoding='utf-8'))
48#: f.write(bytes(f'NODES {len(G)}\n', encoding='utf-8'))
49#: write_edgelist(G, f, data=False)
50#:
52# Path to the atlas file
53ATLAS_FILE = importlib.resources.files("networkx.generators") / "atlas.dat.gz"
56def _generate_graphs():
57 """Sequentially read the file containing the edge list data for the
58 graphs in the atlas and generate the graphs one at a time.
60 This function reads the file given in :data:`.ATLAS_FILE`.
62 """
63 with gzip.open(ATLAS_FILE, "rb") as f:
64 line = f.readline()
65 while line and line.startswith(b"GRAPH"):
66 # The first two lines of each entry tell us the index of the
67 # graph in the list and the number of nodes in the graph.
68 # They look like this:
69 #
70 # GRAPH 3
71 # NODES 2
72 #
73 graph_index = int(line[6:].rstrip())
74 line = f.readline()
75 num_nodes = int(line[6:].rstrip())
76 # The remaining lines contain the edge list, until the next
77 # GRAPH line (or until the end of the file).
78 edgelist = []
79 line = f.readline()
80 while line and not line.startswith(b"GRAPH"):
81 edgelist.append(line.rstrip())
82 line = f.readline()
83 G = nx.Graph()
84 G.name = f"G{graph_index}"
85 G.add_nodes_from(range(num_nodes))
86 G.add_edges_from(tuple(map(int, e.split())) for e in edgelist)
87 yield G
90@nx._dispatchable(graphs=None, returns_graph=True)
91def graph_atlas(i):
92 """Returns graph number `i` from the Graph Atlas.
94 For more information, see :func:`.graph_atlas_g`.
96 Parameters
97 ----------
98 i : int
99 The index of the graph from the atlas to get. The graph at index
100 0 is assumed to be the null graph.
102 Returns
103 -------
104 list
105 A list of :class:`~networkx.Graph` objects, the one at index *i*
106 corresponding to the graph *i* in the Graph Atlas.
108 See also
109 --------
110 graph_atlas_g
112 Notes
113 -----
114 The time required by this function increases linearly with the
115 argument `i`, since it reads a large file sequentially in order to
116 generate the graph [1]_.
118 References
119 ----------
120 .. [1] Ronald C. Read and Robin J. Wilson, *An Atlas of Graphs*.
121 Oxford University Press, 1998.
123 """
124 if not (0 <= i < NUM_GRAPHS):
125 raise ValueError(f"index must be between 0 and {NUM_GRAPHS}")
126 return next(islice(_generate_graphs(), i, None))
129@nx._dispatchable(graphs=None, returns_graph=True)
130def graph_atlas_g():
131 """Returns the list of all graphs with up to seven nodes named in the
132 Graph Atlas.
134 The graphs are listed in increasing order by
136 1. number of nodes,
137 2. number of edges,
138 3. degree sequence (for example 111223 < 112222),
139 4. number of automorphisms,
141 in that order, with three exceptions as described in the *Notes*
142 section below. This causes the list to correspond with the index of
143 the graphs in the Graph Atlas [atlas]_, with the first graph,
144 ``G[0]``, being the null graph.
146 Returns
147 -------
148 list
149 A list of :class:`~networkx.Graph` objects, the one at index *i*
150 corresponding to the graph *i* in the Graph Atlas.
152 Examples
153 --------
154 >>> from pprint import pprint
155 >>> atlas = nx.graph_atlas_g()
157 There are 1253 graphs in the atlas
159 >>> len(atlas)
160 1253
162 The number of graphs with *n* nodes, where *n* ranges from 0 to 7:
164 >>> from collections import Counter
165 >>> num_nodes_per_graph = [len(G) for G in atlas]
166 >>> Counter(num_nodes_per_graph)
167 Counter({7: 1044, 6: 156, 5: 34, 4: 11, 3: 4, 2: 2, 0: 1, 1: 1})
169 Since the atlas is ordered by the number of nodes in the graph, all graphs
170 with *n* nodes can be obtained by slicing the atlas. For example, all
171 graphs with 5 nodes:
173 >>> G5_list = atlas[19:53]
174 >>> all(len(G) == 5 for G in G5_list)
175 True
177 Or all graphs with at least 3 nodes but fewer than 7 nodes:
179 >>> G3_6_list = atlas[4:209]
181 More generally, the indices that partition the atlas by the number of nodes
182 per graph:
184 >>> import itertools
185 >>> partition_indices = [0] + list(
186 ... itertools.accumulate(Counter(num_nodes_per_graph).values()) # cumsum
187 ... )
188 >>> partition_indices
189 [0, 1, 2, 4, 8, 19, 53, 209, 1253]
190 >>> partition_mapping = dict(enumerate(itertools.pairwise(partition_indices)))
191 >>> pprint(partition_mapping)
192 {0: (0, 1),
193 1: (1, 2),
194 2: (2, 4),
195 3: (4, 8),
196 4: (8, 19),
197 5: (19, 53),
198 6: (53, 209),
199 7: (209, 1253)}
201 See also
202 --------
203 graph_atlas
205 Notes
206 -----
207 This function may be expensive in both time and space, since it
208 reads a large file sequentially in order to populate the list.
210 Although the NetworkX atlas functions match the order of graphs
211 given in the "Atlas of Graphs" book, there are (at least) three
212 errors in the ordering described in the book. The following three
213 pairs of nodes violate the lexicographically nondecreasing sorted
214 degree sequence rule:
216 - graphs 55 and 56 with degree sequences 001111 and 000112,
217 - graphs 1007 and 1008 with degree sequences 3333444 and 3333336,
218 - graphs 1012 and 1213 with degree sequences 1244555 and 1244456.
220 References
221 ----------
222 .. [atlas] Ronald C. Read and Robin J. Wilson,
223 *An Atlas of Graphs*.
224 Oxford University Press, 1998.
226 """
227 return list(_generate_graphs())