/usr/lib/python3/dist-packages/networkx/algorithms/traversal/breadth_first_search.py is in python3-networkx 1.11-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | """
====================
Breadth-first search
====================
Basic algorithms for breadth-first searching the nodes of a graph.
"""
import networkx as nx
from collections import defaultdict, deque
__author__ = """\n""".join(['Aric Hagberg <aric.hagberg@gmail.com>'])
__all__ = ['bfs_edges', 'bfs_tree', 'bfs_predecessors', 'bfs_successors']
def bfs_edges(G, source, reverse=False):
"""Produce edges in a breadth-first-search starting at source.
Parameters
----------
G : NetworkX graph
source : node
Specify starting node for breadth-first search and return edges in
the component reachable from source.
reverse : bool, optional
If True traverse a directed graph in the reverse direction
Returns
-------
edges: generator
A generator of edges in the breadth-first-search.
Examples
--------
>>> G = nx.Graph()
>>> G.add_path([0,1,2])
>>> print(list(nx.bfs_edges(G,0)))
[(0, 1), (1, 2)]
Notes
-----
Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
by D. Eppstein, July 2004.
"""
if reverse and isinstance(G, nx.DiGraph):
neighbors = G.predecessors_iter
else:
neighbors = G.neighbors_iter
visited = set([source])
queue = deque([(source, neighbors(source))])
while queue:
parent, children = queue[0]
try:
child = next(children)
if child not in visited:
yield parent, child
visited.add(child)
queue.append((child, neighbors(child)))
except StopIteration:
queue.popleft()
def bfs_tree(G, source, reverse=False):
"""Return an oriented tree constructed from of a breadth-first-search
starting at source.
Parameters
----------
G : NetworkX graph
source : node
Specify starting node for breadth-first search and return edges in
the component reachable from source.
reverse : bool, optional
If True traverse a directed graph in the reverse direction
Returns
-------
T: NetworkX DiGraph
An oriented tree
Examples
--------
>>> G = nx.Graph()
>>> G.add_path([0,1,2])
>>> print(list(nx.bfs_edges(G,0)))
[(0, 1), (1, 2)]
Notes
-----
Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
by D. Eppstein, July 2004.
"""
T = nx.DiGraph()
T.add_node(source)
T.add_edges_from(bfs_edges(G,source,reverse=reverse))
return T
def bfs_predecessors(G, source):
"""Return dictionary of predecessors in breadth-first-search from source.
Parameters
----------
G : NetworkX graph
source : node
Specify starting node for breadth-first search and return edges in
the component reachable from source.
Returns
-------
pred: dict
A dictionary with nodes as keys and predecessor nodes as values.
Examples
--------
>>> G = nx.Graph()
>>> G.add_path([0,1,2])
>>> print(nx.bfs_predecessors(G,0))
{1: 0, 2: 1}
Notes
-----
Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
by D. Eppstein, July 2004.
"""
return dict((t,s) for s,t in bfs_edges(G,source))
def bfs_successors(G, source):
"""Return dictionary of successors in breadth-first-search from source.
Parameters
----------
G : NetworkX graph
source : node
Specify starting node for breadth-first search and return edges in
the component reachable from source.
Returns
-------
succ: dict
A dictionary with nodes as keys and list of succssors nodes as values.
Examples
--------
>>> G = nx.Graph()
>>> G.add_path([0,1,2])
>>> print(nx.bfs_successors(G,0))
{0: [1], 1: [2]}
Notes
-----
Based on http://www.ics.uci.edu/~eppstein/PADS/BFS.py
by D. Eppstein, July 2004.
"""
d = defaultdict(list)
for s,t in bfs_edges(G,source):
d[s].append(t)
return dict(d)
|