Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

"""
====================
====================

"""
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']

[docs]def bfs_edges(G, source, reverse=False):
"""Produce edges in a breadth-first-search starting at source.

Parameters
----------
G : NetworkX graph

source : node, optional
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()
>>> print(list(nx.bfs_edges(G,0)))
[(0, 1), (1, 2)]

Notes
-----
by D. Eppstein, July 2004.

If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.
"""
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
queue.append((child, neighbors(child)))
except StopIteration:
queue.popleft()

[docs]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, optional
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()
>>> print(list(nx.bfs_edges(G,0)))
[(0, 1), (1, 2)]

Notes
-----
by D. Eppstein, July 2004.

If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.
"""
T = nx.DiGraph()
return T

[docs]def bfs_predecessors(G, source):
"""Return dictionary of predecessors in breadth-first-search from source.

Parameters
----------
G : NetworkX graph

source : node, optional
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()
>>> print(nx.bfs_predecessors(G,0))
{1: 0, 2: 1}

Notes
-----
by D. Eppstein, July 2004.

If a source is not specified then a source is chosen arbitrarily and
repeatedly until all components in the graph are searched.
"""
return dict((t,s) for s,t in bfs_edges(G,source))

[docs]def bfs_successors(G, source):
"""Return dictionary of successors in breadth-first-search from source.

Parameters
----------
G : NetworkX graph

source : node, optional
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()
>>> print(nx.bfs_successors(G,0))
{0: [1], 1: [2]}

Notes
-----