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"""
2**************
3Adjacency List
4**************
5Read and write NetworkX graphs as adjacency lists.
7Adjacency list format is useful for graphs without data associated
8with nodes or edges and for nodes that can be meaningfully represented
9as strings.
11Format
12------
13The adjacency list format consists of lines with node labels. The
14first label in a line is the source node. Further labels in the line
15are considered target nodes and are added to the graph along with an edge
16between the source node and target node.
18The graph with edges a-b, a-c, d-e can be represented as the following
19adjacency list (anything following the # in a line is a comment)::
21 a b c # source target target
22 d e
23"""
25__all__ = ["generate_adjlist", "write_adjlist", "parse_adjlist", "read_adjlist"]
27import networkx as nx
28from networkx.utils import open_file
31def generate_adjlist(G, delimiter=" "):
32 """Generate lines representing a graph in adjacency list format.
34 Parameters
35 ----------
36 G : NetworkX graph
38 delimiter : str, default=" "
39 Separator for node labels.
41 Yields
42 ------
43 str
44 Adjacency list for a node in `G`. The first item is the node label,
45 followed by the labels of its neighbors.
47 Examples
48 --------
49 >>> G = nx.lollipop_graph(4, 3)
50 >>> for line in nx.generate_adjlist(G):
51 ... print(line)
52 0 1 2 3
53 1 2 3
54 2 3
55 3 4
56 4 5
57 5 6
58 6
60 When `G` is undirected, each edge is only listed once. For directed graphs,
61 edges appear once for each direction.
63 >>> G = nx.complete_graph(3, create_using=nx.DiGraph)
64 >>> for line in nx.generate_adjlist(G):
65 ... print(line)
66 0 1 2
67 1 0 2
68 2 0 1
70 Node labels are shown multiple times for multiedges, but edge data (including keys)
71 are not included in the output.
73 >>> G = nx.MultiGraph([(0, 1, {"weight": 1}), (0, 1, {"weight": 2})])
74 >>> for line in nx.generate_adjlist(G):
75 ... print(line)
76 0 1 1
77 1
79 See Also
80 --------
81 write_adjlist, read_adjlist
83 Notes
84 -----
85 The default `delimiter=" "` will result in unexpected results if node names contain
86 whitespace characters. To avoid this problem, specify an alternate delimiter when spaces are
87 valid in node names.
89 NB: This option is not available for data that isn't user-generated.
91 """
92 seen = set()
93 directed = G.is_directed()
94 multigraph = G.is_multigraph()
95 for s, nbrs in G.adjacency():
96 nodes = [str(s)]
97 for t, data in nbrs.items():
98 if t in seen:
99 continue
100 if multigraph and len(data) > 1:
101 nodes.extend((str(t),) * len(data))
102 else:
103 nodes.append(str(t))
104 if not directed:
105 seen.add(s)
106 yield delimiter.join(nodes)
109@open_file(1, mode="wb")
110def write_adjlist(G, path, comments="#", delimiter=" ", encoding="utf-8"):
111 """Write graph G in single-line adjacency-list format to path.
114 Parameters
115 ----------
116 G : NetworkX graph
118 path : string or file
119 Filename or file handle for data output.
120 Filenames ending in .gz or .bz2 will be compressed.
122 comments : string, optional
123 Marker for comment lines
125 delimiter : string, optional
126 Separator for node labels
128 encoding : string, optional
129 Text encoding.
131 Examples
132 --------
133 >>> G = nx.path_graph(4)
134 >>> nx.write_adjlist(G, "path4.adjlist")
136 The path can be a filehandle or a string with the name of the file. If a
137 filehandle is provided, it has to be opened in 'wb' mode.
139 >>> fh = open("path4.adjlist2", "wb")
140 >>> nx.write_adjlist(G, fh)
142 Notes
143 -----
144 The default `delimiter=" "` will result in unexpected results if node names contain
145 whitespace characters. To avoid this problem, specify an alternate delimiter when spaces are
146 valid in node names.
147 NB: This option is not available for data that isn't user-generated.
149 This format does not store graph, node, or edge data.
151 See Also
152 --------
153 read_adjlist, generate_adjlist
154 """
155 import sys
156 import time
158 pargs = comments + " ".join(sys.argv) + "\n"
159 header = (
160 pargs
161 + comments
162 + f" GMT {time.asctime(time.gmtime())}\n"
163 + comments
164 + f" {G.name}\n"
165 )
166 path.write(header.encode(encoding))
168 for line in generate_adjlist(G, delimiter):
169 line += "\n"
170 path.write(line.encode(encoding))
173@nx._dispatchable(graphs=None, returns_graph=True)
174def parse_adjlist(
175 lines, comments="#", delimiter=None, create_using=None, nodetype=None
176):
177 """Parse lines of a graph adjacency list representation.
179 Parameters
180 ----------
181 lines : list or iterator of strings
182 Input data in adjlist format
184 create_using : NetworkX graph constructor, optional (default=nx.Graph)
185 Graph type to create. If graph instance, then cleared before populated.
187 nodetype : Python type, optional
188 Convert nodes to this type.
190 comments : string, optional
191 Marker for comment lines
193 delimiter : string, optional
194 Separator for node labels. The default is whitespace.
196 Returns
197 -------
198 G: NetworkX graph
199 The graph corresponding to the lines in adjacency list format.
201 Examples
202 --------
203 >>> lines = ["1 2 5", "2 3 4", "3 5", "4", "5"]
204 >>> G = nx.parse_adjlist(lines, nodetype=int)
205 >>> nodes = [1, 2, 3, 4, 5]
206 >>> all(node in G for node in nodes)
207 True
208 >>> edges = [(1, 2), (1, 5), (2, 3), (2, 4), (3, 5)]
209 >>> all((u, v) in G.edges() or (v, u) in G.edges() for (u, v) in edges)
210 True
212 See Also
213 --------
214 read_adjlist
216 """
217 G = nx.empty_graph(0, create_using)
218 for line in lines:
219 p = line.find(comments)
220 if p >= 0:
221 line = line[:p]
222 if not len(line):
223 continue
224 vlist = line.rstrip("\n").split(delimiter)
225 u = vlist.pop(0)
226 # convert types
227 if nodetype is not None:
228 try:
229 u = nodetype(u)
230 except BaseException as err:
231 raise TypeError(
232 f"Failed to convert node ({u}) to type {nodetype}"
233 ) from err
234 G.add_node(u)
235 if nodetype is not None:
236 try:
237 vlist = list(map(nodetype, vlist))
238 except BaseException as err:
239 raise TypeError(
240 f"Failed to convert nodes ({','.join(vlist)}) to type {nodetype}"
241 ) from err
242 G.add_edges_from([(u, v) for v in vlist])
243 return G
246@open_file(0, mode="rb")
247@nx._dispatchable(graphs=None, returns_graph=True)
248def read_adjlist(
249 path,
250 comments="#",
251 delimiter=None,
252 create_using=None,
253 nodetype=None,
254 encoding="utf-8",
255):
256 """Read graph in adjacency list format from path.
258 Parameters
259 ----------
260 path : string or file
261 Filename or file handle to read.
262 Filenames ending in .gz or .bz2 will be decompressed.
264 create_using : NetworkX graph constructor, optional (default=nx.Graph)
265 Graph type to create. If graph instance, then cleared before populated.
267 nodetype : Python type, optional
268 Convert nodes to this type.
270 comments : string, optional
271 Marker for comment lines
273 delimiter : string, optional
274 Separator for node labels. The default is whitespace.
276 Returns
277 -------
278 G: NetworkX graph
279 The graph corresponding to the lines in adjacency list format.
281 Examples
282 --------
283 >>> G = nx.path_graph(4)
284 >>> nx.write_adjlist(G, "test.adjlist")
285 >>> G = nx.read_adjlist("test.adjlist")
287 The path can be a filehandle or a string with the name of the file. If a
288 filehandle is provided, it has to be opened in 'rb' mode.
290 >>> fh = open("test.adjlist", "rb")
291 >>> G = nx.read_adjlist(fh)
293 Filenames ending in .gz or .bz2 will be compressed.
295 >>> nx.write_adjlist(G, "test.adjlist.gz")
296 >>> G = nx.read_adjlist("test.adjlist.gz")
298 The optional nodetype is a function to convert node strings to nodetype.
300 For example
302 >>> G = nx.read_adjlist("test.adjlist", nodetype=int)
304 will attempt to convert all nodes to integer type.
306 Since nodes must be hashable, the function nodetype must return hashable
307 types (e.g. int, float, str, frozenset - or tuples of those, etc.)
309 The optional create_using parameter indicates the type of NetworkX graph
310 created. The default is `nx.Graph`, an undirected graph.
311 To read the data as a directed graph use
313 >>> G = nx.read_adjlist("test.adjlist", create_using=nx.DiGraph)
315 Notes
316 -----
317 This format does not store graph or node data.
319 See Also
320 --------
321 write_adjlist
322 """
323 lines = (line.decode(encoding) for line in path)
324 return parse_adjlist(
325 lines,
326 comments=comments,
327 delimiter=delimiter,
328 create_using=create_using,
329 nodetype=nodetype,
330 )