2

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?

langlauf.io
  • 3,009
  • 2
  • 28
  • 45

2 Answers2

1

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
Tui Popenoe
  • 2,098
  • 2
  • 23
  • 44
  • 1
    Ok I get it. There is no way to get the nodes directly. I need to go by the edges. Then, your suggestion [0].extend(nx.algorithms.bfs_successors(G, 0).values()) is neat. Thank you! – langlauf.io Mar 17 '15 at 08:35
  • Hi! I tried it too but it seems not to be working. I got this error: _bfs = [start].extend(nx.algorithms.bfs_successors(maze,start).values()) AttributeError: 'generator' object has no attribute 'values'_ . Do you have any idea of why? start is made of a (0, 0) tuple and maze is the name of the graph – hellomynameisA Jun 16 '20 at 16:06
  • @hellomynameisA Yes, and `[0].extend` would yield no result too. Please see my answer. – Aristide Nov 25 '21 at 11:49
1

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.

Aristide
  • 3,606
  • 2
  • 30
  • 50