7

I found this topological sorting function for PHP:

Source: http://www.calcatraz.com/blog/php-topological-sort-function-384/

function topological_sort($nodeids, $edges) {
    $L = $S = $nodes = array();
    foreach($nodeids as $id) {
        $nodes[$id] = array('in'=>array(), 'out'=>array());
        foreach($edges as $e) {
            if ($id==$e[0]) { $nodes[$id]['out'][]=$e[1]; }
            if ($id==$e[1]) { $nodes[$id]['in'][]=$e[0]; }
        }
    }
    foreach ($nodes as $id=>$n) { if (empty($n['in'])) $S[]=$id; }
    while (!empty($S)) {
        $L[] = $id = array_shift($S);
        foreach($nodes[$id]['out'] as $m) {
            $nodes[$m]['in'] = array_diff($nodes[$m]['in'], array($id));
            if (empty($nodes[$m]['in'])) { $S[] = $m; }
        }
        $nodes[$id]['out'] = array();
    }
    foreach($nodes as $n) {
        if (!empty($n['in']) or !empty($n['out'])) {
            return null; // not sortable as graph is cyclic
        }
    }
    return $L;
}

I looks nice and short. Anyways, for some input - I get duplicate lines in the output - see http://codepad.org/thpzCOyn

Generally the sorting seems to be correct if I remove the duplicates with array_unique()

I checked the function with two examples and the sorting itself looks correct.

Should I just call array_unique() on the result?

2
  • 1
    Based on the output you want, here is a fix. I've not properly examined the code to figure out whether it is correct, but it certainly fixes the problem you report.
    – DaveRandom
    Aug 14, 2012 at 13:30
  • When upgrading from EE 1.12 to 1.13 I experienced that a cyclic graph was created for order invoices. You may want to throw an exception with a clear error message instead of returning null as wrong /no totals will be produced. Returning null will only result in a PHP warning because PHP expects an array later on. An exception would be easier to debug and it would be clearer that you have to take action. Sep 9, 2013 at 14:04

2 Answers 2

7

I'm the author of the original topological sorting function. Thanks to Alex for bringing the duplicate edge issue to my attention. I've updated the function to correctly remove duplicate edges and nodes. The updated version is here:

http://www.calcatraz.com/blog/php-topological-sort-function-384 (Same as original link)

I added the following to achieve the deduplication:

// remove duplicate nodes
$nodeids = array_unique($nodeids);  

// remove duplicate edges
$hashes = array();
foreach($edges as $k=>$e) {
    $hash = md5(serialize($e));
    if (in_array($hash, $hashes)) { unset($edges[$k]); }
    else { $hashes[] = $hash; }; 
}

I had to serialize the edges to make sure duplicates were removed correctly. I also tidied the rest of the function up a bit and added some comments.

1
  • Hi Dan, thank you for sharing your algorithm. Do you know if possible to make the function support cyclic links inside tree another way - like if there are some cyclic links just use the first one and ignore all the next (not retrning null). I have a tree of nodes, and they already have some order from database like 1,2,3,4. So if there are edges like [1, 2], [2, 3], [3, 1], I would like to ignore [3, 1] as it is a cycle.
    – Ross
    Oct 26, 2015 at 8:24
3

You get duplicate lines because there are duplicate edges. I'm no graph theory thug but I'm pretty sure this is not legal :

0 => 
array (
  0 => 'nominal',
  1 => 'subtotal',
),
2 => 
array (
  0 => 'nominal',
  1 => 'subtotal',
),
...

You can either add a test in the part that constructs the nodes, something like this :

if ($id==$e[0] && !in_array($e[1], $nodes[$id]['out']))
{
  $nodes[$id]['out'][]=$e[1];
}
if ($id==$e[1] && !in_array($e[0], $nodes[$id]['in'])) // Not needed but cleaner
{
  $nodes[$id]['in'][]=$e[0];
}

... or just make sure you don't pass duplicate edges to the function. :P

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.