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()吗？

- Alex

---

根据您想要的输出，这里有一个修复方案。我还没有仔细检查代码以确定它是否正确，但它肯定解决了您报告的问题。 - DaveRandom

在从EE 1.12升级到1.13时，我遇到了订单发票的循环图问题。你可能希望抛出一个带有清晰错误信息的异常，而不是返回null，因为这样会产生错误/无效的总数。返回null只会导致PHP警告，因为PHP后面需要一个数组。使用异常更容易调试，并且更清楚地表明您必须采取行动。 - Matthias Zeis

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

我需要序列化边缘以确保正确删除重复项。我也对函数的其余部分进行了整理，并添加了一些注释。

- Dan

---

嗨，丹，感谢您分享您的算法。您是否知道是否有可能以另一种方式使函数支持树内的循环链接 - 就像如果存在某些循环链接，只使用第一个链接并忽略所有后续链接（不返回null）？我有一个节点树，它们已经从数据库中按顺序排列，如1、2、3、4。因此，如果存在[1,2]，[2,3]，[3,1]这样的边缘，我想忽略[3,1]，因为它是一个循环。 - Ross

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

（注：该句为技术提示，并无需翻译）

- ttzn