Given an acyclic directed graph, return a collection of collections of nodes "at the same level"?
Why would bfs not solve it? A bfs algorithm is breadth traversal algorithm, i.e. it traverses the tree level wise. This also means, all nodes at same level are traversed at once, which is your desired output.
As pointed out in comment, this will however, assume a starting point in the graph.
Firstly I am not sure what such an algorithm is called, which is the primary problem - so first part of the question is what is this algorithm called?
Basically I have a DiGraph() into which I insert the nodes [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and the edges ([1,3],[2,3],[3,5],[4,5],[5,7],[6,7],[7,8],[7,9],[7,10])
From this I'm wondering if it's possible to get a collection as follows: [[1, 2, 4, 6], [3], [5], [7], [8, 9, 10]]
EDIT: Let me add some constraints if it helps.
- There are no cycles, this is guaranteed
- There is no one start point for the graph
What I'm trying to do is to collect the nodes at the same level such that their processing can be parallelized, but within the outer collection, the processing is serial.
EDIT2: So clearly I hadn't thought about this enough, so the easiest way to describe "level" is interms of deepest predecessor, all nodes that have the same depth of predecessors. So the first entry in the above list are all nodes that have 0 as the deepest predecessor, the second has one, third has two and so on. Within each list, the order of the siblings is irrelevant as they will be parallelly processed.