Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/generators/atlas.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Generators for the small graph atlas. | |
3 """ | |
4 import gzip | |
5 from itertools import islice | |
6 import os | |
7 import os.path | |
8 | |
9 import networkx as nx | |
10 | |
11 __all__ = ["graph_atlas", "graph_atlas_g"] | |
12 | |
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. | |
17 NUM_GRAPHS = 1253 | |
18 | |
19 #: The absolute path representing the directory containing this file. | |
20 THIS_DIR = os.path.dirname(os.path.abspath(__file__)) | |
21 | |
22 #: The path to the data file containing the graph edge lists. | |
23 #: | |
24 #: This is the absolute filename of the gzipped text file containing the | |
25 #: edge list for each graph in the atlas. The file contains one entry | |
26 #: per graph in the atlas, in sequential order, starting from graph | |
27 #: number 0 and extending through graph number 1252 (see | |
28 #: :data:`NUM_GRAPHS`). Each entry looks like | |
29 #: | |
30 #: .. sourcecode:: text | |
31 #: | |
32 #: GRAPH 6 | |
33 #: NODES 3 | |
34 #: 0 1 | |
35 #: 0 2 | |
36 #: | |
37 #: where the first two lines are the graph's index in the atlas and the | |
38 #: number of nodes in the graph, and the remaining lines are the edge | |
39 #: list. | |
40 #: | |
41 #: This file was generated from a Python list of graphs via code like | |
42 #: the following:: | |
43 #: | |
44 #: import gzip | |
45 #: from networkx.generators.atlas import graph_atlas_g | |
46 #: from networkx.readwrite.edgelist import write_edgelist | |
47 #: | |
48 #: with gzip.open('atlas.dat.gz', 'wb') as f: | |
49 #: for i, G in enumerate(graph_atlas_g()): | |
50 #: f.write(bytes(f'GRAPH {i}\n', encoding='utf-8')) | |
51 #: f.write(bytes(f'NODES {len(G)}\n', encoding='utf-8')) | |
52 #: write_edgelist(G, f, data=False) | |
53 #: | |
54 ATLAS_FILE = os.path.join(THIS_DIR, "atlas.dat.gz") | |
55 | |
56 | |
57 def _generate_graphs(): | |
58 """Sequentially read the file containing the edge list data for the | |
59 graphs in the atlas and generate the graphs one at a time. | |
60 | |
61 This function reads the file given in :data:`.ATLAS_FILE`. | |
62 | |
63 """ | |
64 with gzip.open(ATLAS_FILE, "rb") as f: | |
65 line = f.readline() | |
66 while line and line.startswith(b"GRAPH"): | |
67 # The first two lines of each entry tell us the index of the | |
68 # graph in the list and the number of nodes in the graph. | |
69 # They look like this: | |
70 # | |
71 # GRAPH 3 | |
72 # NODES 2 | |
73 # | |
74 graph_index = int(line[6:].rstrip()) | |
75 line = f.readline() | |
76 num_nodes = int(line[6:].rstrip()) | |
77 # The remaining lines contain the edge list, until the next | |
78 # GRAPH line (or until the end of the file). | |
79 edgelist = [] | |
80 line = f.readline() | |
81 while line and not line.startswith(b"GRAPH"): | |
82 edgelist.append(line.rstrip()) | |
83 line = f.readline() | |
84 G = nx.Graph() | |
85 G.name = f"G{graph_index}" | |
86 G.add_nodes_from(range(num_nodes)) | |
87 G.add_edges_from(tuple(map(int, e.split())) for e in edgelist) | |
88 yield G | |
89 | |
90 | |
91 def graph_atlas(i): | |
92 """Returns graph number `i` from the Graph Atlas. | |
93 | |
94 For more information, see :func:`.graph_atlas_g`. | |
95 | |
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. | |
101 | |
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. | |
107 | |
108 See also | |
109 -------- | |
110 graph_atlas_g | |
111 | |
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]_. | |
117 | |
118 References | |
119 ---------- | |
120 .. [1] Ronald C. Read and Robin J. Wilson, *An Atlas of Graphs*. | |
121 Oxford University Press, 1998. | |
122 | |
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)) | |
127 | |
128 | |
129 def graph_atlas_g(): | |
130 """Returns the list of all graphs with up to seven nodes named in the | |
131 Graph Atlas. | |
132 | |
133 The graphs are listed in increasing order by | |
134 | |
135 1. number of nodes, | |
136 2. number of edges, | |
137 3. degree sequence (for example 111223 < 112222), | |
138 4. number of automorphisms, | |
139 | |
140 in that order, with three exceptions as described in the *Notes* | |
141 section below. This causes the list to correspond with the index of | |
142 the graphs in the Graph Atlas [atlas]_, with the first graph, | |
143 ``G[0]``, being the null graph. | |
144 | |
145 Returns | |
146 ------- | |
147 list | |
148 A list of :class:`~networkx.Graph` objects, the one at index *i* | |
149 corresponding to the graph *i* in the Graph Atlas. | |
150 | |
151 See also | |
152 -------- | |
153 graph_atlas | |
154 | |
155 Notes | |
156 ----- | |
157 This function may be expensive in both time and space, since it | |
158 reads a large file sequentially in order to populate the list. | |
159 | |
160 Although the NetworkX atlas functions match the order of graphs | |
161 given in the "Atlas of Graphs" book, there are (at least) three | |
162 errors in the ordering described in the book. The following three | |
163 pairs of nodes violate the lexicographically nondecreasing sorted | |
164 degree sequence rule: | |
165 | |
166 - graphs 55 and 56 with degree sequences 001111 and 000112, | |
167 - graphs 1007 and 1008 with degree sequences 3333444 and 3333336, | |
168 - graphs 1012 and 1213 with degree sequences 1244555 and 1244456. | |
169 | |
170 References | |
171 ---------- | |
172 .. [atlas] Ronald C. Read and Robin J. Wilson, | |
173 *An Atlas of Graphs*. | |
174 Oxford University Press, 1998. | |
175 | |
176 """ | |
177 return list(_generate_graphs()) |