Which graph traversal algo suits in this scenario

Question

I have a problem to traverse a graph of the following kind.

• At each node there could be multiple inputs and outputs.
• Each output can direct to multiple inputs (e.g. third output of A goes to C and D)
• At each node some calculations are done based on the values provided in inputs. The results of outputs are provided to the inputs of other nodes.
• To traverse from one node to the next I have to know the values of all the inputs.

This traversal comes to mind:

• At A, use the only input to calculate all the outputs
• Move from A to C using first output of A.
• At C, we do not know the other input so backtrack to A.
• At A, use second output to reach B.
• At B, we do not have all the inputs so backtrack to A.
• At A, take third output and reach B.
• At B, now we have all the inputs to calculate outputs.
• At B, via first output reach C.
• At C, we have all the inputs so do the calculations and reach E.
• and so on

So what traversal algo you think would work best in this scenario. BFS would probably not work because in my case I do not know all the inputs when I reach a node and backtracking is not possible.

I have to implement this in C#.

Answer 1

Idea:

Use breadth-first search, but also have a count on each node (or, similarly, a list of the inputs).

When you visit a node:

• Increase its count
• If the count is less than the number of incoming edges it has, don't do anything
• Otherwise, process the node as usual

Your example:

Candidates: A
We process A.

Candidates: C, B, D
We visit C, but don't process it as its count = 1 < 2 = incoming edges.

Candidates: B, D
We visit B and process it.

Candidates: D, C, E, D
We visit D, but don't process it as its count = 1 < 2 = incoming edges (the second edge hasn't been processed yet).

Candidates: C, E, D
We visit C and process it.

Candidates: E, D, E
We visit E, but don't process it as its count = 1 < 3 = incoming edges (the second and third edges haven't been processed yet).

Candidates: D, E
We visit D and process it.

Candidates: D, E, E
We visit D and process it.

Candidates: E, E
We visit E, but don't process it as its count = 2 < 3 = incoming edges (the third edge hasn't been processed yet).

Candidates: E
We visit E and process it.