ioftools / networkxMiCe / networkxmaster / networkx / generators / atlas.py @ 5cef0f13
History  View  Annotate  Download (5.68 KB)
1 
# Copyright (C) 20042019 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='utf8'))

60 
#: f.write(bytes('NODES {}\n'.format(len(G)), encoding='utf8'))

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()) 