Sort dependency list or Topological Sorting in PHP

From Wikipedia

In the field of computer science, a topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

Sometimes, we fall into situations where we have a list of tasks to be done, but with a condition that each of the tasks may need one or more tasks from the list to be done before them. Let’s, consider that we have to do tasks a,b,c,d and the condition is b & d has to be done before the task a, then the sorting will become b,d,a,c.

Practical Case:

In a system I was working, I faced the problem as some of the modules in the system depends on some others. So at the moment of execution, those modules has to be loaded to have every module working. Consider plugins, where one plugin may depend on another. For example, a plugin that enables user actions such as like-dislike etc. on contents may need the contents plugin to be executed first.

Topological or Dependency list sorting or ordering in PHP:

First take a look at the following lines of codes

```\$data = array(
'a' => 'a',
'b' => 'b',
'c' => 'c',
'd' => 'd',
'e' => 'e',
);
\$dependency = array(
'a' => array('c','d','e'),
'b' => array('a','d'),
'c' => array('e')
);
function _process_toposort(\$pointer, &\$dependency, &\$order, &\$pre_processing){
if(isset(\$pre_processing[\$pointer])) return false;
else \$pre_processing[\$pointer] = \$pointer;

foreach(\$dependency[\$pointer] as \$i=>\$v){
if(isset(\$dependency[\$v])){
if(!_process_toposort(\$v, \$dependency, \$order, \$pre_processing)) return false;
}
\$order[\$v] = \$v;
unset(\$pre_processing[\$v]);
}
\$order[\$pointer] = \$pointer;
unset(\$pre_processing[\$pointer]);
return true;
}

function _topological_sort(\$data, \$dependency){
\$order = array();
\$pre_processing = array();
\$order = array_diff_key(\$data, \$dependency);
\$data = array_diff_key(\$data, \$order);
foreach(\$data as \$i=>\$v){
if(!_process_toposort(\$i,\$dependency,\$order, \$pre_processing)) return false;
}
return \$order;
}

\$out = _topological_sort(\$data, \$dependency);
var_dump(\$out);
```

So, here we have our all tasks listed in \$data array and the dependencies of tasks are listing in \$dependency array. We fire the sorting by calling the _topological_sort(\$data, \$dependency) function.

The very first thing we do is, we cut out those tasks which has no dependency at all from \$data to \$order, as they don’t have any dependency we can put them anywhere in the sorting.

Then we just simply keep those tasks in the \$data array which is present as keys in the \$dependency array.

Then we start looping over the \$data array and for each key (each key in the array is a task) we call the actual sorting function, _process_toposort(\$pointer, &\$dependency, &\$order, &\$pre_processing)

In this function, we store the \$pointer in a stack called \$pre_processing. We will explain this later.

So what we do is, we start looping through the dependencies of this task (\$pointer) in the \$dependency array. If the tasks (every \$v) on which this task (\$pointer) depends has further dependency, then we again call this same function in a recursive fashion and if not then the task (\$v) will be simply added to the \$order array and as this task (\$v) has been added to \$order list, we remove it from the \$pre_processing array. At the end of the loop, we add the \$pointer to the \$order list as all the dependencies of this task (\$pointer) has been processed so now we can execute this task.

And this continues for every task in the \$data array and when done, we have a sorted array \$order that we return from _topological_sort(\$data, \$dependency).

However, we may get a Boolean False return from the function there is a cycle in the \$dependency array.

The exception or cycle in the dependency list: Alright, consider the following dependency list.

```\$dependency = array(
'a' => array('c','d','e'),
'b' => array('a','d'),
'c' => array('a')
);
```

As you can see, task ‘a’ depends on task ‘c’ and again task ‘c’ depends on task ‘a’. This is a cycle and obviously we can’t sort this dependency list. So how we checked it? Okay, you noticed the \$pre_processing array in the _process_toposort function, right? Let’s debug the function to watch how it works.
1. \$pointer is ‘a’ and it is not in \$pre_processing array, so we keep it. \$pre_processing now have array(‘a’=>’a’);
2. First dependency of task ‘a’ is task ‘c’. So we set \$pointer as ‘c’ and called the function again.
3. \$pointer is ‘c’ and it is not in \$pre_processing array, so we keep it. \$pre_processing now have array(‘a’=>’a’, ‘c’=>’c’);
4. First dependency of task ‘c’ is task ‘a’. So we set \$pointer as ‘a’ and called the function again.
5. \$pointer is ‘a’ and it is IN \$pre_processing array, so THIS IS A CYCLE and we returned false. Thus all the recursive calls return false and as the _process_toposort returns falls, so does _topological_sort function.
This is how we handle a cycle in dependency list or topological sort.

I don’t know much theory, but is seems to me very close to DFS or depth first search. Anyway, I hope this helps.

Author: Tanmay Chakrabarty

Tanmay Chakrabarty is a former CSE student, currently working as a Senior Software Engineer with 5+ years of experience in the field of Web Application development in PHP+MySQL platform with strong skills in Javascript, JQuery, JQuery UI and CSS. He tries to write notes every week but fails due to heavy loads of duty.