CODEWITHSUNDEEP
pythongraphnetworkxbreadth-first-search
langlauf.io
langlauf.io

Reputation: 3221

Using networkx bfs_tree to obtain a list of nodes of a directed graph in BFS order

For example, given:

G = nx.DiGraph()
G.add_path([0, 1])
G.add_path([0, 2])
G.add_path([0, 3])

G.add_path([1, 11])
G.add_path([1, 12])

G.add_path([2, 21])
G.add_path([2, 22])

G.add_path([3, 31])
G.add_path([3, 32])

I want this: 0, 1, 2, 3, 11, 12, 21, 22, 31, 32

Why does the networkx documentation of bfs_tree actually uses bfs_edges in its example? And not bfs_tree? The key line from the example given in the bfs_tree documentation:

print(list(nx.bfs_edges(G,0)))

Using bfs_edge instead, e.g. via print(list(nx.algorithms.bfs_tree(G, 0).edges())) seems to result in the same list as returned by the example code but is obviously more complicated. Can I use bfs_tree() in a simpler way to obtain a list of _nodes_ of a directed graph in BFS order?

Of course, I could iterate the list returned from bfs_tree or bfs_edges and only take the second element. But isn't there a simpler way?

Upvotes: 3

Views: 5459

Answers (2)

Aristide
Aristide

Reputation: 3994

As of Networkx 2.6.2, this actually works:

[0] + [successor for successors in dict(nx.bfs_successors(G, 0)).values() for successor in successors]

Edit. My original suggestion:

[0] + sum(dict(nx.bfs_successors(G, 0)).values(), [])

The sum(l ,[]) idiom flattens the list, but is quadratic. Discussion on How to make a flat list out of a list of lists.

Upvotes: 1

Tui Popenoe
Tui Popenoe

Reputation: 2124

Why not flatten the list of edge tuples (each 2 nodes), and then take the set of nodes to ensure uniqueness? 

list(set(sum(list(nx.algorithms.bfs_tree(G, 0).edges()), ())))

In your hypothetical solution, you would ignore the 0 node, and it would not be included in your output.

Or you could use the bfs_successors() method to get a dict of nodes (passing in the 0 node) and take the values.

[0].extend(nx.algorithms.bfs_successors(G, 0).values())
# Get your first, node, and extend with a list of all successor nodes in BFS order

Upvotes: 2

Related Questions