在PHP拓扑排序 [英] Topological sorting in PHP

问题描述

我发现这个拓扑排序函数PHP：

I found this topological sorting function for PHP:

来源：<一href="http://www.calcatraz.com/blog/php-topological-sort-function-384/">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;
}

我看起来不错，很短。不管怎么说，对于一些输入 - 我得到的输出重复行 - 看 HTTP：//$c$cpad.org/thpzCOyn

一般排序似乎是正确的，如果我删除与 array_unique重复的（）

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.

我是不是应该叫 array_unique（）的结果？

Should I just call array_unique() on the result?

推荐答案

您得到重复的线路，因为有重复的边缘。我不是图论暴徒但我pretty的肯定，这是不合法的：

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];
}

...或者只是确保你不将重复的边缘功能。 ：P

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

这篇关于在PHP拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！