can Breadth First Search be simplified with corout...

# coroutines

[groostav]

can Breadth First Search be simplified with coroutines? eg if i have a tree of `Node`'s where I want to do a BFS for a node that passes a certain Predicate<Node>, can I use a suspend fun to avoid all the queue offer and remove malarky?

[elizarov]

Yes. When you visit a node in a graph you can traverse all the outgoing edges and launch a new coroutine for each adjacent node. However, unless you are traversing a DAG, you also need to ensure that you visit each node at most once. That is, you get rid of a queue, but you still need to maintain a set of visited nodes and this set has to be shared between all the coroutines. At this point you have to choices:
1. Thread confinement. Using a single-threaded dispatcher you can just share this set between all the coroutines. It will work just like the classical single-threaded BFS, but I don’t really see that it is going simpler algo. It looks that there will be more code.
2. You can use something like ConcucrrentHashMap to maintain this set. Be careful to avoid “check&act” problem when you check if the node is not visited yet and launch a new coroutine (use an atomic computeIfAbsent to launch a new coroutine). This way you can get a fully concurrent BFS, so that you can do some complex processing of each node (including async calls) and it will scale to lots of CPUs. This use-case might be worth it, IMHO.