Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/generators/atlas.py: 41%

1""" 

2Generators for the small graph atlas. 

3""" 

4import gzip 

5import importlib.resources 

6import os 

7import os.path 

8from itertools import islice 

9 

10import networkx as nx 

11 

12__all__ = ["graph_atlas", "graph_atlas_g"] 

13 

14#: The total number of graphs in the atlas. 

15#: 

16#: The graphs are labeled starting from 0 and extending to (but not 

17#: including) this number. 

18NUM_GRAPHS = 1253 

19 

20#: The path to the data file containing the graph edge lists. 

21#: 

22#: This is the absolute path of the gzipped text file containing the 

23#: edge list for each graph in the atlas. The file contains one entry 

24#: per graph in the atlas, in sequential order, starting from graph 

25#: number 0 and extending through graph number 1252 (see 

26#: :data:`NUM_GRAPHS`). Each entry looks like 

27#: 

28#: .. sourcecode:: text 

29#: 

30#: GRAPH 6 

31#: NODES 3 

32#: 0 1 

33#: 0 2 

34#: 

35#: where the first two lines are the graph's index in the atlas and the 

36#: number of nodes in the graph, and the remaining lines are the edge 

37#: list. 

38#: 

39#: This file was generated from a Python list of graphs via code like 

40#: the following:: 

41#: 

42#: import gzip 

43#: from networkx.generators.atlas import graph_atlas_g 

44#: from networkx.readwrite.edgelist import write_edgelist 

45#: 

46#: with gzip.open('atlas.dat.gz', 'wb') as f: 

47#: for i, G in enumerate(graph_atlas_g()): 

48#: f.write(bytes(f'GRAPH {i}\n', encoding='utf-8')) 

49#: f.write(bytes(f'NODES {len(G)}\n', encoding='utf-8')) 

50#: write_edgelist(G, f, data=False) 

51#: 

52 

53# Path to the atlas file 

54ATLAS_FILE = importlib.resources.files("networkx.generators") / "atlas.dat.gz" 

55 

56 

57def _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@nx._dispatch(graphs=None) 

92def graph_atlas(i): 

93 """Returns graph number `i` from the Graph Atlas. 

94 

95 For more information, see :func:`.graph_atlas_g`. 

96 

97 Parameters 

98 ---------- 

99 i : int 

100 The index of the graph from the atlas to get. The graph at index 

101 0 is assumed to be the null graph. 

102 

103 Returns 

104 ------- 

105 list 

106 A list of :class:`~networkx.Graph` objects, the one at index *i* 

107 corresponding to the graph *i* in the Graph Atlas. 

108 

109 See also 

110 -------- 

111 graph_atlas_g 

112 

113 Notes 

114 ----- 

115 The time required by this function increases linearly with the 

116 argument `i`, since it reads a large file sequentially in order to 

117 generate the graph [1]_. 

118 

119 References 

120 ---------- 

121 .. [1] Ronald C. Read and Robin J. Wilson, *An Atlas of Graphs*. 

122 Oxford University Press, 1998. 

123 

124 """ 

125 if not (0 <= i < NUM_GRAPHS): 

126 raise ValueError(f"index must be between 0 and {NUM_GRAPHS}") 

127 return next(islice(_generate_graphs(), i, None)) 

128 

129 

130@nx._dispatch(graphs=None) 

131def graph_atlas_g(): 

132 """Returns the list of all graphs with up to seven nodes named in the 

133 Graph Atlas. 

134 

135 The graphs are listed in increasing order by 

136 

137 1. number of nodes, 

138 2. number of edges, 

139 3. degree sequence (for example 111223 < 112222), 

140 4. number of automorphisms, 

141 

142 in that order, with three exceptions as described in the *Notes* 

143 section below. This causes the list to correspond with the index of 

144 the graphs in the Graph Atlas [atlas]_, with the first graph, 

145 ``G[0]``, being the null graph. 

146 

147 Returns 

148 ------- 

149 list 

150 A list of :class:`~networkx.Graph` objects, the one at index *i* 

151 corresponding to the graph *i* in the Graph Atlas. 

152 

153 See also 

154 -------- 

155 graph_atlas 

156 

157 Notes 

158 ----- 

159 This function may be expensive in both time and space, since it 

160 reads a large file sequentially in order to populate the list. 

161 

162 Although the NetworkX atlas functions match the order of graphs 

163 given in the "Atlas of Graphs" book, there are (at least) three 

164 errors in the ordering described in the book. The following three 

165 pairs of nodes violate the lexicographically nondecreasing sorted 

166 degree sequence rule: 

167 

168 - graphs 55 and 56 with degree sequences 001111 and 000112, 

169 - graphs 1007 and 1008 with degree sequences 3333444 and 3333336, 

170 - graphs 1012 and 1213 with degree sequences 1244555 and 1244456. 

171 

172 References 

173 ---------- 

174 .. [atlas] Ronald C. Read and Robin J. Wilson, 

175 *An Atlas of Graphs*. 

176 Oxford University Press, 1998. 

177 

178 """ 

179 return list(_generate_graphs())