Search code examples
c#algorithmgraphgraph-theorygraph-traversal

Which graph traversal algo suits in this scenario

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

Graph to traverse

  • 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#.

Solution

  • 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.