Algorithm to detect when graph re-converges (similar to common subtree?)

Question

I've been working on this problem all day, I'm re-writing one of our legacy products and I'm having a hard time determining how to find a specific node in my flow chart. The problem reminds me of University, but for the life of me I can't come up with an algorithm to solve this.

I've attached 3 screen shots to help explain this, but the basic problem is, given a YES/NO? decision node, locate the closest child node that terminates the branch.

I'm working in C# .NET and JSON. In JSON I've got an object that gives each node a unique identifier, and also identifies each "link" from one node to the next. I would hope to write a function (or several) to determine the first "end node" given a branched node in C#. Currently I've built out the jSON into XML in C#.

Any and all ideas encouraged, not really looking for code but an approach/algorithm.

Attached is the output in jSON from the diagram:

{ "class": "go.GraphLinksModel",
  "linkFromPortIdProperty": "fromPort",
  "linkToPortIdProperty": "toPort",
  "nodeDataArray": [ 
{"key":-1, "category":"Start", "loc":"169 288", "text":"Start"},
{"key":-2, "category":"End", "loc":"855 394", "text":"End"},
{"category":"Branch", "text":"Yes or No", "key":-4, "loc":"284.8837209302326 285.7848837209302"},
{"category":"DelayNode", "text":"Delay", "key":-3, "loc":"365.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-5, "loc":"478.8837209302326 214.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-6, "loc":"568.8837209302326 151.52345997177622"},
{"category":"DelayNode", "text":"Delay", "key":-7, "loc":"573.8837209302326 268.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-8, "loc":"653.8837209302326 215.52345997177622"},
{"category":"Branch", "text":"Yes or No", "key":-9, "loc":"392.8837209302326 392.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-10, "loc":"454.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-11, "loc":"550.8837209302326 473.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-12, "loc":"549.8837209302326 317.5234599717762"},
{"category":"DelayNode", "text":"Delay", "key":-13, "loc":"711.8837209302326 343.5234599717762"},
{"category":"Branch", "text":"Yes or No", "key":-14, "loc":"434.8837209302326 487.5234599717762"}
 ],
  "linkDataArray": [ 
{"from":-4, "to":-3, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-1, "to":-4, "fromPort":"R", "toPort":"L"},
{"from":-3, "to":-5, "fromPort":"R", "toPort":"L"},
{"from":-5, "to":-6, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-5, "to":-7, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-6, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-7, "to":-8, "fromPort":"R", "toPort":"L"},
{"from":-4, "to":-9, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-9, "to":-10, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-10, "to":-12, "fromPort":"R", "toPort":"L"},
{"from":-11, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-12, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-8, "to":-13, "fromPort":"R", "toPort":"L"},
{"from":-13, "to":-2, "fromPort":"R", "toPort":"L"},
{"from":-9, "to":-14, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"},
{"from":-14, "to":-11, "fromPort":"T", "toPort":"L", "visible":true},
{"from":-14, "to":-11, "fromPort":"B", "toPort":"L", "visible":true, "text":"NO"}
 ]}

Answer 1

I like Alex's answer and it seems highly efficient. Here's another way to solve your problem, which as it turns out is actually the Lowest Common Ancestor problem. This is an extremely well studied problem in graph theory; I just didn't see it at first because you have to reverse all the arrows.

With this solution you do an expensive preprocessing once, and then you have a data structure that you can just read the answer off of.

I've labelled the nodes in your graph. What you do is first you reverse all the arrows and then you construct the Eulerian traversal of the resulting DAG, at each step remembering how far from the "root" (end) you are.

The Eulerian traversal goes "visit yourself, recurse on a neighbour, visit yourself, recurse on a neighbour, ... visit yourself". That is, if we were writing it in C# we'd say something like:

void Eulerian(Node n, int i, List<Tuple<Node, int>> traversal)
{
    traversal.Add(Tuple.Create(node, i));
    foreach(Node neighbour in node.Neighbours)
    {
        Eulerian(neighbour, i + 1, traversal);
        traversal.Add(Tuple.Create(node, i));
    }
}

The Eulerian traversal is the traversal you would actually take if you were walking the graph.

The graph you've given as an example has the following Eulerian traversal when you reverse all the arrows and start from END.

A0 B1 C2 D3 E4 F5 G6 H7 G6 F5 E4 D3 C2 I3 E4 F5 G6 H7 G6 F5 E4 I3 C2 
B1 J2 K3 L4 G5 H6 G5 L4 K3 J2 B1 M2 N3 L4 G5 H6 G5 L4 N3 M2 N3 L4 G5 
H6 G5 L4 N3 M2 B1 A0

The answer to your question can now be read off the traversal. In your examples, you have decision nodes E, L and G.

For E: find the first and last occurrences of E in the traversal. Now search the nodes between those two in the traversal for the one with the smallest number. It's C, with a score of 2.

For L: find the first and last occurrences of L in the traversal. The node with the smallest number between them is B, with a score of 1.

For G: again the node with the lowest score between the first and last occurrences of G is B.

Computing the traversal might be expensive if the graph is large, but the nice thing is that you only have to do it once. After that, it's just a linear search problem. (And you could make it a sublinear search problem if you really wanted to, but that seems like a lot of extra work.)

Answer 2

If I understand the problem, you're trying to find the first common node between the "yes" and "no" subtrees. In that case, a simple way to do that would be an breadth-first traversal of the yes subtree, adding each element to a list. Then do a breadth-first traversal or the no subtree, stopping when an element in that subtree appears in the "yes" list.