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"""Basic algorithms for breadth-first searching the nodes of a graph."""
3from collections import deque
5import networkx as nx
7__all__ = [
8 "bfs_edges",
9 "bfs_tree",
10 "bfs_predecessors",
11 "bfs_successors",
12 "descendants_at_distance",
13 "bfs_layers",
14 "bfs_labeled_edges",
15 "generic_bfs_edges",
16]
19@nx._dispatchable
20def generic_bfs_edges(G, source, neighbors=None, depth_limit=None):
21 """Iterate over edges in a breadth-first search.
23 The breadth-first search begins at `source` and enqueues the
24 neighbors of newly visited nodes specified by the `neighbors`
25 function.
27 Parameters
28 ----------
29 G : NetworkX graph
31 source : node
32 Starting node for the breadth-first search; this function
33 iterates over only those edges in the component reachable from
34 this node.
36 neighbors : function
37 A function that takes a newly visited node of the graph as input
38 and returns an *iterator* (not just a list) of nodes that are
39 neighbors of that node with custom ordering. If not specified, this is
40 just the ``G.neighbors`` method, but in general it can be any function
41 that returns an iterator over some or all of the neighbors of a
42 given node, in any order.
44 depth_limit : int, optional(default=len(G))
45 Specify the maximum search depth.
47 Yields
48 ------
49 edge
50 Edges in the breadth-first search starting from `source`.
52 Examples
53 --------
54 >>> G = nx.path_graph(7)
55 >>> list(nx.generic_bfs_edges(G, source=0))
56 [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
57 >>> list(nx.generic_bfs_edges(G, source=2))
58 [(2, 1), (2, 3), (1, 0), (3, 4), (4, 5), (5, 6)]
59 >>> list(nx.generic_bfs_edges(G, source=2, depth_limit=2))
60 [(2, 1), (2, 3), (1, 0), (3, 4)]
62 The `neighbors` param can be used to specify the visitation order of each
63 node's neighbors generically. In the following example, we modify the default
64 neighbor to return *odd* nodes first:
66 >>> def odd_first(n):
67 ... return sorted(G.neighbors(n), key=lambda x: x % 2, reverse=True)
69 >>> G = nx.star_graph(5)
70 >>> list(nx.generic_bfs_edges(G, source=0)) # Default neighbor ordering
71 [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5)]
72 >>> list(nx.generic_bfs_edges(G, source=0, neighbors=odd_first))
73 [(0, 1), (0, 3), (0, 5), (0, 2), (0, 4)]
75 Notes
76 -----
77 This implementation is from `PADS`_, which was in the public domain
78 when it was first accessed in July, 2004. The modifications
79 to allow depth limits are based on the Wikipedia article
80 "`Depth-limited-search`_".
82 .. _PADS: http://www.ics.uci.edu/~eppstein/PADS/BFS.py
83 .. _Depth-limited-search: https://en.wikipedia.org/wiki/Depth-limited_search
84 """
85 if neighbors is None:
86 neighbors = G.neighbors
87 if depth_limit is None:
88 depth_limit = len(G)
90 seen = {source}
91 n = len(G)
92 depth = 0
93 next_parents_children = [(source, neighbors(source))]
94 while next_parents_children and depth < depth_limit:
95 this_parents_children = next_parents_children
96 next_parents_children = []
97 for parent, children in this_parents_children:
98 for child in children:
99 if child not in seen:
100 seen.add(child)
101 next_parents_children.append((child, neighbors(child)))
102 yield parent, child
103 if len(seen) == n:
104 return
105 depth += 1
108@nx._dispatchable
109def bfs_edges(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
110 """Iterate over edges in a breadth-first-search starting at source.
112 Parameters
113 ----------
114 G : NetworkX graph
116 source : node
117 Specify starting node for breadth-first search; this function
118 iterates over only those edges in the component reachable from
119 this node.
121 reverse : bool, optional
122 If True traverse a directed graph in the reverse direction
124 depth_limit : int, optional(default=len(G))
125 Specify the maximum search depth
127 sort_neighbors : function (default=None)
128 A function that takes an iterator over nodes as the input, and
129 returns an iterable of the same nodes with a custom ordering.
130 For example, `sorted` will sort the nodes in increasing order.
132 Yields
133 ------
134 edge: 2-tuple of nodes
135 Yields edges resulting from the breadth-first search.
137 Examples
138 --------
139 To get the edges in a breadth-first search:
141 >>> G = nx.path_graph(3)
142 >>> list(nx.bfs_edges(G, 0))
143 [(0, 1), (1, 2)]
144 >>> list(nx.bfs_edges(G, source=0, depth_limit=1))
145 [(0, 1)]
147 To get the nodes in a breadth-first search order:
149 >>> G = nx.path_graph(3)
150 >>> root = 2
151 >>> edges = nx.bfs_edges(G, root)
152 >>> nodes = [root] + [v for u, v in edges]
153 >>> nodes
154 [2, 1, 0]
156 Notes
157 -----
158 The naming of this function is very similar to
159 :func:`~networkx.algorithms.traversal.edgebfs.edge_bfs`. The difference
160 is that ``edge_bfs`` yields edges even if they extend back to an already
161 explored node while this generator yields the edges of the tree that results
162 from a breadth-first-search (BFS) so no edges are reported if they extend
163 to already explored nodes. That means ``edge_bfs`` reports all edges while
164 ``bfs_edges`` only reports those traversed by a node-based BFS. Yet another
165 description is that ``bfs_edges`` reports the edges traversed during BFS
166 while ``edge_bfs`` reports all edges in the order they are explored.
168 Based on the breadth-first search implementation in PADS [1]_
169 by D. Eppstein, July 2004; with modifications to allow depth limits
170 as described in [2]_.
172 References
173 ----------
174 .. [1] http://www.ics.uci.edu/~eppstein/PADS/BFS.py.
175 .. [2] https://en.wikipedia.org/wiki/Depth-limited_search
177 See Also
178 --------
179 bfs_tree
180 :func:`~networkx.algorithms.traversal.depth_first_search.dfs_edges`
181 :func:`~networkx.algorithms.traversal.edgebfs.edge_bfs`
183 """
184 if reverse and G.is_directed():
185 successors = G.predecessors
186 else:
187 successors = G.neighbors
189 if sort_neighbors is not None:
190 yield from generic_bfs_edges(
191 G, source, lambda node: iter(sort_neighbors(successors(node))), depth_limit
192 )
193 else:
194 yield from generic_bfs_edges(G, source, successors, depth_limit)
197@nx._dispatchable(returns_graph=True)
198def bfs_tree(G, source, reverse=False, depth_limit=None, sort_neighbors=None):
199 """Returns an oriented tree constructed from of a breadth-first-search
200 starting at source.
202 Parameters
203 ----------
204 G : NetworkX graph
206 source : node
207 Specify starting node for breadth-first search
209 reverse : bool, optional
210 If True traverse a directed graph in the reverse direction
212 depth_limit : int, optional(default=len(G))
213 Specify the maximum search depth
215 sort_neighbors : function (default=None)
216 A function that takes an iterator over nodes as the input, and
217 returns an iterable of the same nodes with a custom ordering.
218 For example, `sorted` will sort the nodes in increasing order.
220 Returns
221 -------
222 T: NetworkX DiGraph
223 An oriented tree
225 Examples
226 --------
227 >>> G = nx.path_graph(3)
228 >>> list(nx.bfs_tree(G, 1).edges())
229 [(1, 0), (1, 2)]
230 >>> H = nx.Graph()
231 >>> nx.add_path(H, [0, 1, 2, 3, 4, 5, 6])
232 >>> nx.add_path(H, [2, 7, 8, 9, 10])
233 >>> sorted(list(nx.bfs_tree(H, source=3, depth_limit=3).edges()))
234 [(1, 0), (2, 1), (2, 7), (3, 2), (3, 4), (4, 5), (5, 6), (7, 8)]
237 Notes
238 -----
239 Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
240 by D. Eppstein, July 2004. The modifications
241 to allow depth limits based on the Wikipedia article
242 "`Depth-limited-search`_".
244 .. _Depth-limited-search: https://en.wikipedia.org/wiki/Depth-limited_search
246 See Also
247 --------
248 dfs_tree
249 bfs_edges
250 edge_bfs
251 """
252 T = nx.DiGraph()
253 T.add_node(source)
254 edges_gen = bfs_edges(
255 G,
256 source,
257 reverse=reverse,
258 depth_limit=depth_limit,
259 sort_neighbors=sort_neighbors,
260 )
261 T.add_edges_from(edges_gen)
262 return T
265@nx._dispatchable
266def bfs_predecessors(G, source, depth_limit=None, sort_neighbors=None):
267 """Returns an iterator of predecessors in breadth-first-search from source.
269 Each yielded ``(node, predecessor)`` tuple describes a node and
270 the node from which it is discovered in the breadth-first-search.
272 The term "predecessor" here is not the directed graph term "predecessor".
273 We are not doing BFS in reverse direction. We are just reporting the
274 preceding node for each node in a BFS.
276 Parameters
277 ----------
278 G : NetworkX graph
280 source : node
281 Specify starting node for breadth-first search
283 depth_limit : int, optional(default=len(G))
284 Specify the maximum search depth
286 sort_neighbors : function (default=None)
287 A function that takes an iterator over nodes as the input, and
288 returns an iterable of the same nodes with a custom ordering.
289 For example, `sorted` will sort the nodes in increasing order.
291 Returns
292 -------
293 pred: iterator
294 (node, predecessor) iterator where `predecessor` is the predecessor of
295 `node` in a breadth first search starting from `source`.
297 Examples
298 --------
299 >>> G = nx.path_graph(3)
300 >>> dict(nx.bfs_predecessors(G, 0))
301 {1: 0, 2: 1}
302 >>> H = nx.Graph()
303 >>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
304 >>> dict(nx.bfs_predecessors(H, 0))
305 {1: 0, 2: 0, 3: 1, 4: 1, 5: 2, 6: 2}
306 >>> M = nx.Graph()
307 >>> nx.add_path(M, [0, 1, 2, 3, 4, 5, 6])
308 >>> nx.add_path(M, [2, 7, 8, 9, 10])
309 >>> sorted(nx.bfs_predecessors(M, source=1, depth_limit=3))
310 [(0, 1), (2, 1), (3, 2), (4, 3), (7, 2), (8, 7)]
311 >>> N = nx.DiGraph()
312 >>> nx.add_path(N, [0, 1, 2, 3, 4, 7])
313 >>> nx.add_path(N, [3, 5, 6, 7])
314 >>> sorted(nx.bfs_predecessors(N, source=2))
315 [(3, 2), (4, 3), (5, 3), (6, 5), (7, 4)]
317 Notes
318 -----
319 Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
320 by D. Eppstein, July 2004. The modifications
321 to allow depth limits based on the Wikipedia article
322 "`Depth-limited-search`_".
324 .. _Depth-limited-search: https://en.wikipedia.org/wiki/Depth-limited_search
326 See Also
327 --------
328 bfs_tree
329 bfs_edges
330 edge_bfs
331 """
332 for s, t in bfs_edges(
333 G, source, depth_limit=depth_limit, sort_neighbors=sort_neighbors
334 ):
335 yield (t, s)
338@nx._dispatchable
339def bfs_successors(G, source, depth_limit=None, sort_neighbors=None):
340 """Returns an iterator of successors in breadth-first-search from source.
342 Parameters
343 ----------
344 G : NetworkX graph
346 source : node
347 Specify starting node for breadth-first search
349 depth_limit : int, optional(default=len(G))
350 Specify the maximum search depth
352 sort_neighbors : function (default=None)
353 A function that takes an iterator over nodes as the input, and
354 returns an iterable of the same nodes with a custom ordering.
355 For example, `sorted` will sort the nodes in increasing order.
357 Returns
358 -------
359 succ: iterator
360 (node, successors) iterator where `successors` is the non-empty list of
361 successors of `node` in a breadth first search from `source`.
362 To appear in the iterator, `node` must have successors.
364 Examples
365 --------
366 >>> G = nx.path_graph(3)
367 >>> dict(nx.bfs_successors(G, 0))
368 {0: [1], 1: [2]}
369 >>> H = nx.Graph()
370 >>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
371 >>> dict(nx.bfs_successors(H, 0))
372 {0: [1, 2], 1: [3, 4], 2: [5, 6]}
373 >>> G = nx.Graph()
374 >>> nx.add_path(G, [0, 1, 2, 3, 4, 5, 6])
375 >>> nx.add_path(G, [2, 7, 8, 9, 10])
376 >>> dict(nx.bfs_successors(G, source=1, depth_limit=3))
377 {1: [0, 2], 2: [3, 7], 3: [4], 7: [8]}
378 >>> G = nx.DiGraph()
379 >>> nx.add_path(G, [0, 1, 2, 3, 4, 5])
380 >>> dict(nx.bfs_successors(G, source=3))
381 {3: [4], 4: [5]}
383 Notes
384 -----
385 Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
386 by D. Eppstein, July 2004.The modifications
387 to allow depth limits based on the Wikipedia article
388 "`Depth-limited-search`_".
390 .. _Depth-limited-search: https://en.wikipedia.org/wiki/Depth-limited_search
392 See Also
393 --------
394 bfs_tree
395 bfs_edges
396 edge_bfs
397 """
398 parent = source
399 children = []
400 for p, c in bfs_edges(
401 G, source, depth_limit=depth_limit, sort_neighbors=sort_neighbors
402 ):
403 if p == parent:
404 children.append(c)
405 continue
406 yield (parent, children)
407 children = [c]
408 parent = p
409 yield (parent, children)
412@nx._dispatchable
413def bfs_layers(G, sources):
414 """Returns an iterator of all the layers in breadth-first search traversal.
416 Parameters
417 ----------
418 G : NetworkX graph
419 A graph over which to find the layers using breadth-first search.
421 sources : node in `G` or iterable of nodes in `G`
422 Specify starting nodes for single source or multiple sources
423 breadth-first search.
425 Yields
426 ------
427 layer : list of nodes
428 Yields list of nodes at the same distance from `sources`.
430 Examples
431 --------
432 >>> G = nx.path_graph(5)
433 >>> dict(enumerate(nx.bfs_layers(G, [0, 4])))
434 {0: [0, 4], 1: [1, 3], 2: [2]}
435 >>> H = nx.Graph()
436 >>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
437 >>> dict(enumerate(nx.bfs_layers(H, [1])))
438 {0: [1], 1: [0, 3, 4], 2: [2], 3: [5, 6]}
439 >>> dict(enumerate(nx.bfs_layers(H, [1, 6])))
440 {0: [1, 6], 1: [0, 3, 4, 2], 2: [5]}
441 """
442 if sources in G:
443 sources = [sources]
445 visited = set(sources)
446 current_layer = list(visited)
448 for source in current_layer:
449 if source not in G:
450 raise nx.NetworkXError(f"The node {source} is not in the graph.")
452 # this is basically BFS, except that the current layer only stores the nodes at
453 # same distance from sources at each iteration
454 while current_layer:
455 yield current_layer
456 next_layer = []
457 for node in current_layer:
458 for child in G[node]:
459 if child not in visited:
460 visited.add(child)
461 next_layer.append(child)
462 current_layer = next_layer
465REVERSE_EDGE = "reverse"
466TREE_EDGE = "tree"
467FORWARD_EDGE = "forward"
468LEVEL_EDGE = "level"
471@nx._dispatchable
472def bfs_labeled_edges(G, sources):
473 """Iterate over edges in a breadth-first search (BFS) labeled by type.
475 We generate triple of the form (*u*, *v*, *d*), where (*u*, *v*) is the
476 edge being explored in the breadth-first search and *d* is one of the
477 strings 'tree', 'forward', 'level', or 'reverse'. A 'tree' edge is one in
478 which *v* is first discovered and placed into the layer below *u*. A
479 'forward' edge is one in which *u* is on the layer above *v* and *v* has
480 already been discovered. A 'level' edge is one in which both *u* and *v*
481 occur on the same layer. A 'reverse' edge is one in which *u* is on a layer
482 below *v*.
484 We emit each edge exactly once. In an undirected graph, 'reverse' edges do
485 not occur, because each is discovered either as a 'tree' or 'forward' edge.
487 Parameters
488 ----------
489 G : NetworkX graph
490 A graph over which to find the layers using breadth-first search.
492 sources : node in `G` or list of nodes in `G`
493 Starting nodes for single source or multiple sources breadth-first search
495 Yields
496 ------
497 edges: generator
498 A generator of triples (*u*, *v*, *d*) where (*u*, *v*) is the edge being
499 explored and *d* is described above.
501 Examples
502 --------
503 >>> G = nx.cycle_graph(4, create_using=nx.DiGraph)
504 >>> list(nx.bfs_labeled_edges(G, 0))
505 [(0, 1, 'tree'), (1, 2, 'tree'), (2, 3, 'tree'), (3, 0, 'reverse')]
506 >>> G = nx.complete_graph(3)
507 >>> list(nx.bfs_labeled_edges(G, 0))
508 [(0, 1, 'tree'), (0, 2, 'tree'), (1, 2, 'level')]
509 >>> list(nx.bfs_labeled_edges(G, [0, 1]))
510 [(0, 1, 'level'), (0, 2, 'tree'), (1, 2, 'forward')]
511 """
512 if sources in G:
513 sources = [sources]
515 neighbors = G._adj
516 directed = G.is_directed()
517 visited = set()
518 visit = visited.discard if directed else visited.add
519 # We use visited in a negative sense, so the visited set stays empty for the
520 # directed case and level edges are reported on their first occurrence in
521 # the undirected case. Note our use of visited.discard -- this is built-in
522 # thus somewhat faster than a python-defined def nop(x): pass
523 depth = {s: 0 for s in sources}
524 queue = deque(depth.items())
525 push = queue.append
526 pop = queue.popleft
527 while queue:
528 u, du = pop()
529 for v in neighbors[u]:
530 if v not in depth:
531 depth[v] = dv = du + 1
532 push((v, dv))
533 yield u, v, TREE_EDGE
534 else:
535 dv = depth[v]
536 if du == dv:
537 if v not in visited:
538 yield u, v, LEVEL_EDGE
539 elif du < dv:
540 yield u, v, FORWARD_EDGE
541 elif directed:
542 yield u, v, REVERSE_EDGE
543 visit(u)
546@nx._dispatchable
547def descendants_at_distance(G, source, distance):
548 """Returns all nodes at a fixed `distance` from `source` in `G`.
550 Parameters
551 ----------
552 G : NetworkX graph
553 A graph
554 source : node in `G`
555 distance : the distance of the wanted nodes from `source`
557 Returns
558 -------
559 set()
560 The descendants of `source` in `G` at the given `distance` from `source`
562 Examples
563 --------
564 >>> G = nx.path_graph(5)
565 >>> nx.descendants_at_distance(G, 2, 2)
566 {0, 4}
567 >>> H = nx.DiGraph()
568 >>> H.add_edges_from([(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)])
569 >>> nx.descendants_at_distance(H, 0, 2)
570 {3, 4, 5, 6}
571 >>> nx.descendants_at_distance(H, 5, 0)
572 {5}
573 >>> nx.descendants_at_distance(H, 5, 1)
574 set()
575 """
576 if source not in G:
577 raise nx.NetworkXError(f"The node {source} is not in the graph.")
579 bfs_generator = nx.bfs_layers(G, source)
580 for i, layer in enumerate(bfs_generator):
581 if i == distance:
582 return set(layer)
583 return set()