Я нашел эту функцию топологической сортировки для 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() для результата?
Вы получаете повторяющиеся строки, потому что есть дубликаты ребер. Я не голова теории графа, но я уверен, что это не законно:
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]; }
… или просто убедитесь, что вы не передаете дубликаты ребер функции. :П
Я автор оригинальной топологической функции сортировки. Спасибо Алексу за то, что привлек внимание к проблеме дублирования. Я обновил функцию для правильного удаления повторяющихся ребер и узлов. Обновленная версия находится здесь:
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; }; }
Мне пришлось сериализовать ребра, чтобы убедиться, что дубликаты были удалены правильно. Я также немного подобрал остальную часть функции и добавил некоторые комментарии.