[joss] What is the purpose of bfs_successors()?

[szhorvat]

I am a bit confused about what bfs_successors() is supposed to do and when one might use it.

https://qiskit.org/documentation/retworkx/stubs/retworkx.bfs_successors.html#retworkx.bfs_successors

It is stated that

The return format is [(Parent Node, [Children Nodes])] in a bfs order from the source node provided.

But in fact it does not return nodes. It returns payloads. In other issues, I mentioned that the terminology should be cleaned up and made consistent both in the API and the documentation. Node payloads are at different places referred to as:

• payload (which is clear)
• weight (which is quite confusing—the payload is not a weight in many cases)
• nodes (this is extremely confusing, as "node" usually refers to a vertex and not its payload)

Since only payloads are returned, it is impossible to tell what the actual nodes were. I don't know in what circumstances and for what purposes this result is useful.

Taking the very example from here: https://qiskit.org/documentation/retworkx/stubs/retworkx.BFSSuccessors.html#retworkx.BFSSuccessors

graph = rx.generators.directed_path_graph(5)
bfs_succ = rx.bfs_successors(g, 0) # note that the example contained bfs_successors(0) which is incorrect
print(bfs_succ)

BFSSuccessors[(None, [None, None]), (None, [None, None]), (None, [None])]

This does not look like a useful result.

---

The function works only on directed graphs. Why? I don't see why it couldn't work the same way on undirected graphs.

---

The docs state that it works on DAGs, but this is not true in practice:

graph (PyDiGraph) – The DAG to get the bfs_successors from

node (int) – The index of the dag node to get the bfs successors for

[georgios-ts]

Here we need to improve documentation and state more explicitly that this function returns the data payload of parent/children node, and add support for undirected graphs.

@mtreinish But there might be also a "bug" in this function since it returns all adjacent nodes of a parent node, and not the children nodes in the BFS tree. This might be unexpected since in PR #17, was stated that this function is equivalent to https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.traversal.breadth_first_search.bfs_successors.html#networkx.algorithms.traversal.breadth_first_search.bfs_successors, which it isn't.

[mtreinish]

Hmm, yeah that's a good point, I agree it's probably broken. I added that for DAGCircuit.bfs_successors() which is not widely used so I could see that being in an issue.