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

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: ###### Figure 1. To be exact, this is a directed acyclic graph (DAG)

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

``````abcde
acbde
acdbe
acdeb``````

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

``````use Challenge\Combinatorics\Permutation;

\$graph = [
'a' => null,
'b' => 'a',
'c' => 'a',
'd' => 'b',
'd' => 'a',
'd' => 'c',
'e' => 'a',
'e' => 'c',
'e' => 'd',
];

try {
\$permutation = new Permutation();
\$permutation->setItems(array_keys(\$graph))->setAlgorithm(Permutation::FISHER_YATES);

\$ordered = '';
set_time_limit(25);

while (empty(\$ordered)) {
\$random = \$permutation->getResult();
\$isValid = 0;
foreach (\$graph as \$key => \$value) {
!preg_match("/\$value.*\$key/", \$random) ? \$isValid = 0 : \$isValid++;
}
count(\$graph) == \$isValid ? \$ordered = \$random : false;
}

echo "Sequence found: \$ordered".PHP_EOL;
} catch (\Exception \$e) {
echo \$e->getMessage();
}``````

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:

``````namespace Challenge\Combinatorics;

/**
* Permutation.
*/
class Permutation
{
const HEAPS = 'heaps';
const FISHER_YATES = 'fisher-yates';

/**
* @var string
*/
protected \$algorithm;

/**
* @var array
*/
protected \$items;

/**
* @var array
*/
protected \$result;

/**
* Get algorithm.
*
* @return string
*/
public function getAlgorithm()
{
return \$this->algorithm;
}

/**
* Get items.
*
* @return array
*/
public function getItems()
{
return \$this->items;
}

/**
* Get result.
*
* @return array
*/
public function getResult()
{
switch (\$this->algorithm) {
case self::HEAPS:
\$this->heaps(\$this->n, \$this->items);
sort(\$this->result);
break;

case self::FISHER_YATES:
\$this->fisherYates(\$this->items);
break;
}

return \$this->result;
}

/**
* Set algorithm.
*
* @param string \$algorithm
*/
public function setAlgorithm(\$algorithm)
{
\$this->algorithm = \$algorithm;

return \$this;
}

/**
* Set items.
*
* @param array \$items
*/
public function setItems(\$items)
{
sort(\$items);
\$this->items = \$items;
\$this->n = count(\$items);

return \$this;
}

/**
* Swaps two elements in the given array of items.
*
* @param array \$items
* @param int   \$i
* @param int   \$j
*/
private function swap(&\$items, \$i, \$j)
{
\$temp = \$items[\$i];
\$items[\$i] = \$items[\$j];
\$items[\$j] = \$temp;
}

/**
* This is Heap's algorithm, generates all possible permutations of n items.
*
* @param int   \$n
* @param array \$items
*/
private function heaps(\$n, &\$items)
{
if (\$n == 1) {
\$this->result[] = implode('', \$items);
} else {
for (\$i = 0; \$i < \$n; ++\$i) {
\$this->heaps(\$n - 1, \$items);
if (\$n % 2 == 0) {
\$this->swap(\$items, 0, \$n - 1);
} else {
\$this->swap(\$items, \$i, \$n - 1);
}
}
}
}

/**
* This is Fisher–Yates shuffle algorithm, generates a random permutation.
*
* @param array \$items
*/
private function fisherYates(&\$items)
{
\$n = count(\$items);
for (\$i = 0; \$i <= \$n - 2; ++\$i) {
\$random = rand(\$i, \$n - 1);
\$this->swap(\$items, \$i, \$random);
}
\$this->result = implode('', \$items);
}
}``````

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:

``````\$graph = [
'a' => null,
'b' => 'c',
'c' => 'f',
'd' => 'a',
'e' => 'b',
'f' => null,
'g' => 'c',
'h' => null,
'i' => 'h',
'j' => 'i',
'k' => null,
'l' => null,
'm' => 'n',
'n' => null,
'o' => null,
'p' => 'n',
'q' => null,
'r' => 'q',
's' => 'r',
't' => null,
];``````

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