Stable Topological Sort

Human beings take a lot of things for granted.

Just a straight example. Want to find a fast way to get the greatest common divisor of two numbers? Just use Euclidean algorithm. It would take minutes to find it in Google and port to your code.

Want to sort elements according to dependencies between them? No problem, there is a Wikipedia article on topological sort. It is so comfy to be on the shoulders of Titans.

Everything is documented, explained and proven. But...

What if there is no such thing invented yet?

Then you have a good chance to try your own skills by inventing, proving and delivering the solution. This is what happened to me when I needed an algorithm for stable topological sorting.

Problem Definition

Say we have a sequence of elements {A, B, C, D, E, F}. Some elements depend on others:

• A depends on B
• B depends on D

Objective: Sort the sequence so that its elements are ordered according to their dependencies. The resulting sequence should have the minimal Levenshtein distance to original one. In other words, sequence should be topologically sorted while preserving the original order of elements whenever it is possible.

Example: Given the input elements {A, B, C, D, E, F} where A depends on B and B depends on D, the result of stable topological sort is {D, B, A, C, E, F}.

Existing sources describe topological sort in details, but none of them provides the algorithm for stable topological sort that meets the objective.

Algorithm

After many hours and trials I came up with a small and effective algorithm:

int n = list.Count;

Restart:
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < i; ++j)
    {
        if (graph.DoesXHaveDirectDependencyOnY(list[j], list[i]))
        {
            bool jOnI = graph.DoesXHaveTransitiveDependencyOnY(list[j], list[i]);
            bool iOnJ = graph.DoesXHaveTransitiveDependencyOnY(list[i], list[j]);

            bool circularDependency = jOnI && iOnJ;

            if (!circularDependency)
            {
                var t = list[i];
                list.RemoveAt(i);
                list.Insert(j, t);

                goto Restart;
            }
        }
    }
}

return list;

View the full C# source code

The algorithm ressembles a fusion of bubble sort with order criteria.

An interesting property of a stable topological sort is that cyclic dependencies are tolerated and resolved according to original order of elements in sequence. This is a desirable feature for many applications because it allows to sort any sequence with any imaginable dependencies between the elements.

Proof

Algorithm proofing turned out to be a very important step during the research. I tried several algorithm candidates and it was a typical symptom when a candidate properly covered 99.5% of cases while giving wrong results for remaining 0.5%. Those 0.5% were a pretty tough target to spot in debugger.

I ended up writing a combinatorial proofer in code, so that the designed algorithm has a 100% coverage for all possible input combinations.

Please note that the given proof applies to topological order criteria only. The minimal Levenshtein distance criteria is met in most cases, but the algorithm is known to deliver slightly suboptimal results for some edge-case inputs. At the same time, algorithm remains reasonably fast without descending into brute force search.

Conclusion

The primary use of stable topological algorithm is scheduling of things and planning. Thanks to inherent tolerance to cyclic dependencies and order preservation, the algorithm delivers more natural experience when compared to its non-stable sibling.