7

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

2 つの例で関数を確認したところ、並べ替え自体は正しいように見えます。

私array_unique()は結果を呼び出すだけですか？

4

2 に答える 2

7

私は元のトポロジカル ソート関数の作成者です。重複エッジの問題を指摘してくれた 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; }; 
}

重複が正しく削除されたことを確認するために、エッジをシリアル化する必要がありました。また、関数の残りの部分を少し整理し、いくつかのコメントを追加しました。

于 2013-05-28T19:51:19.317 に答える
3

重複したエッジがあるため、重複した線が得られます。私はグラフ理論の凶悪犯ではありませんが、これは合法ではないと確信しています:

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

于 2012-08-14T13:53:44.943 に答える