Walking a graph without recursion

Question

I'm working on a class that receives a relational EDM/data model (e.g. a SQL DB or OData API manifest) and performs a couple tasks on them (not necessarily at the same time, could be two separate runs). The class/alg doesn't know anything when it starts, finds everything from the schema data, but the schema doc is static so could be re-processed. What I call "sets" are tables, REST API endpoints, etc., i.e. publicly/user-accessible entry points to the data. One of the things I output is a "path" to each type (e.g. A is a set, so just "A"; B is not a set but is a child of A, so "A→B"). Another is whether anything changes between two models (true/false equality of the model pair).

Unfortunately, the input isn't necessarily "correct"--some related child types are not available on their own (only through parents), some are missing relations (no ID fields) so I infer based on existence of the property, some have relation loops (A → B → C → A). Some have child collections (1:N) with no mapping type, so I infer that based on the relation prop and invent a mapping type.

Anywho, my current solution uses depth-first and recursion and keeps track of the types it has seen to prevent overflow and false negatives. We've found some wacky corner cases (in addition to the above; such as a type set existing, but the type definition itself isn't in the schema). What I have written works, for what we've tested/seen so far, but I am curious if there are other methods by which this sort of traversal or processing might be done, hopefully that could be implemented more simply than what I have now, which gets increasingly ugly and seems more fragile as more weird cases come up.

Generally, what I do now, single-threaded, is: get the list of sets, find outliers that don't exist in the opposing model, then for each set common between the two models get the type of that set, call CompareType(t1, t2). This will compare properties on those types between the two models and then descend into each related type. If a child has been seen before or is itself a set, I assume it's OK (skip/return true) because it gets checked on its own.

This is in C# though I'm not sure that is very important as far as the general design of the algorithm. I was curious if there is a better way to do it, e.g. some sort of token walking like I've seen in JSON parsers, or a FSM-like solution, or something like that.

Answer 1

Recursion

Unfortunately trees, and recursion go hand in hand.

It turns out that stacks are what you need to maintain a state when processing a graph. It just so happens that trees fit stacks even better by offering assurances around visitation, which are very handy for algorithms.

The lowest cost stack available to a programmer is the call stack. The language manages the state for you.

Iteration

You can achieve the same effect in two different ways using iteration:

1. Store parent pointers in each child node (and perhaps direct pointers to the next/prior sibling too).
2. create and manage the stack separately.

Local Navigation

The first solution does not have a stack, but now suffers from a history problem. That stack was storing extra meta-data such as where in the process of analysing the parent you are, whether the other siblings are or are not correct, etc...

If the algorithm you are using only needs a small amount of local knowledge , then local navigation through the tree will be sufficient. A complex matching algorithm like you are describing does not fit this well. However many tree balancing algorithms do fit here (such as red/black or b trees), all of the actions and knowledge is local, the navigation is local, even though the effect is global. A stack can assist but is not mandatory for the algorithm to work.

Stacks

The second solution requires that you manage more state yourself. When you return to a parent, you must manage the stack and restore any necessary state. When you navigate to a child, you have to store state onto the stack. The benefits is that your algorithm has access to the full analysis path, and you do not just have to recurse down. You can use the stack to store traversal information to siblings, or cousins of a tree node, etc...

Non-Determinism

Graphs are often processed by a non-deterministic algorithm. Therefore it might make more sense to use a non-deterministic machine to evaluate them. This is even easier if you are managing the stack yourself, or using local navigation data.

To do this you'll need to manage threads yourself. This isn't hard (but it is more work). The payoff is that when your algorithm reaches a point where multiple choices might be valid, instead of analysing one (and being wrong). You analyse them all.

By thread, I'm not talking OS thread but a line of reasoning through the algorithm. You've already done most of the work, that stack is the line of reasoning of your single threaded algorithm.

The difference between the single threaded algorithm and the non-deterministic algorithm is when you reach a point where multiple choices could be valid. The thread is duplicated with each duplicate following one of the valid choices. If a thread turns out to be wrong, that is fine just delete that stack and keep looking at the other threads.

If you happen to finish processing and discover that:

• there are no threads left, then the match was not successful.
• there is one thread left. then that was the match.
• there is more than one thread left. Then there are multiple ways this could match, and they are all valid matches.
  • You can prioritise the matches by ordering how you duplicate threads. Duplicate the threads and insert at the same place in the list. The thread closest to the start takes the most preferred match path, the thread closest to the end takes the least preferred match path.
  • You could also proffer each solution up the chain. Perhaps the next algorithm is non-deterministic too, or perhaps the multiple solutions hold some value, such as presenting them to the user.
  • Or you can rank them using some other technique based on what the match determined.

In this system the problem is managing the global state.

• Which thread do you progress?

  • all of them together
  • the most likely (the first thread on the list).

• What global state is changed?

  • you will need to buffer effects to be applied when everything becomes certain.
  • you may need to restore the input back to a given state when a thread fails.
  • you may need to move all threads through the input simultaneously.

Invert The Graph

As an aside, it appears that you are taking a top down approach. In matching it often makes more sense to perform a bottom up match, particularly if the default case is that there are differences.

So flip the problem upside down. Make all of the leaves top level entries in a list. Their parents become their leaves. As you identify candidate pairs, they suggest candidate parent pairs. When all of the leaves have been matched, you now have a list of candidate parent pairs.

Now perform some validation and see how closely these candidate parents match. If they do not match then it is clear that no further parents will match. Otherwise the candidates parents become possible matches. Process that list similarly. Repeat until no further matches found.

Your specific use case may vary so alter the algorithm to fit.