Topological Sorting in PHP by Using a Random Permutation

Are you OK? I hope so! Today I’ve had the opportunity to dig deeper into the world of permutations and I’ve figured out a way to perform a topological sort (also known as topsort) in PHP without using Kahn’s algorithm nor Depth-first search – which are a couple of usual solutions to this problem — but relying on a random permutation.

This is a graph

Cool! Don’t miss out on today’s post if you’re interested in an alternative solution to ordering all vertices of a graph. This is specially useful if you’re looking for a simple code snippet which is acceptable in terms of computational cost. You want things get done, which means that you are not now writing any data structure for representing any graph at all.

What Is a Topological Sort?

OK, let’s briefly recap and provide some context for what we’re about to do. A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices.

For instance, given the following DAG:

To be exact, this is a directed acyclic graph (DAG)

These are all topological orderings that can be obtained from it:

A Fisher-Yates Random Permutation and a Few Regex

Here is my strategy for computing a random topological ordering: generate a random permutation with the help of the Fisher–Yates shuffle algorithm, and then check whether or not it is a topological order by comparing it against the batch of regular expressions defined by the DAG.

This is how my PHP code looks like.

The code above computes a random topological order given the DAG above. By the way, note that the graph is represented with a PHP array called $graph.

And here is the Permutation class I am using at this moment:

You see, apart from the Fisher–Yates shuffle algorithm it also implements Heap’s algorithm for computing permutations because this class is intended to be used in several different contexts.

The code above works OK for larger graphs, as the one shown below:

And that’s it. Thanks for reading today’s tip. I hope you found it useful.

You may be also interested in…