PHP中的拓扑排序

Question

我找到了PHP的拓扑排序功能:

资料来源: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://codepad.org/thpzCOyn

通常,如果我删除重复项,排序似乎是正确的 array_unique()

我用两个例子检查了函数,排序本身看起来是正确的.

我应该打电话array_unique()给结果吗？

Answer 1

我是原始拓扑排序功能的作者.感谢Alex将重复边缘问题引起我的注意.我已更新该函数以正确删除重复的边和节点.更新版本在这里:

http://www.calcatraz.com/blog/php-topological-sort-function-384(与原始链接相同)

我添加了以下内容来实现重复数据删除:

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

我不得不序列化边缘以确保正确删除重复项.我还整理了其余的功能并添加了一些注释.

Answer 2

因为有重复的边，所以会得到重复的线。我不是图论暴徒，但我很确定这是不合法的：

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

您可以在构造节点的部分添加测试，如下所示：

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