Как отсортировать массив с зависимостями?

Question

[Вадим]

Есть массив, внутри которого элементы могут зависеть друг от друга. Например, вот такой:

$items = [
	'item_a' => ['require' => ['item_b']], // этот элемент зависит от 'item_b'
	'item_b' => ['require' => []], // этот элемент не зависит от других
	'item_c' => ['require' => ['item_a']],
	'item_d' => ['require' => ['item_a', 'item_e']], // этот элемент зависит сразу от двух других - 'item_a' и 'item_b'
	'item_e' => ['require' => ['item_a']],
];

И нужно его отсортировать так, чтобы зависимые элементы шли всегда после тех элементов, от которых они зависят. В моем примере порядок ключей в результате сортировки будет такой:

'item_b', 'item_a', 'item_c', 'item_e', 'item_d'

Собственно, вопрос: как такую сортировку выполнить? Идеально, если есть какие-то готовые библиотеки для подобных сортировок.

ЗЫ. Ясень пень, что могут быть и циклические зависимости и это тоже надо как-то учитывать.

Answer 1

[Котик Антон]

Как предлагаете отсортировать такое?

$items = [
    'item_a' => ['require' => ['item_b']],
    'item_b' => ['require' => ['item_с']],
    'item_c' => ['require' => ['item_a']],
];

Если циклов и взаимозависимостей не будет, тогда так:

foreach (array_keys($items) as $key) {
    $items[$key]['name'] = $key;
}

uasort($items, function($a, $b) {
    return (in_array($b['name'], $a['require']) || empty($b['require']));
});

https://ideone.com/ClHFqW

Для поиска циклических зависимостей у меня получилось такая функция:

/**
 * @param array $items
 * @return bool
 */
function search_cycle($items)
{
    $search = function(array $path) use ($items, &$search)
    {
        $count = count($path);
        $first = $path[0];
        $last  = $path[$count - 1];
        if ($count > 1 && in_array($last, array_slice($path, 0, $count - 1))) {
            return true;
        }
        
        foreach ($items[$last]['require'] as $key) {
            if ($search(array_merge($path, [$key]))) {
                return true;
            }
        }
        
        return false;
    };
    
    foreach ($items as $key => $data) {
        if ($search([$key])) {
            return true;
        }
    }
    
    return false;
}

Comments

[Вадим]

В общем случае циклические зависимости, конечно, могут быть, и выполнение алгоритма тут должно, разумеется, обрываться (напр., в коде выбрасывается исключение). Или считаете, что нереально это обнаружить?

[Вадим]

Идея интересная, и, главное, реализация простая, как пятак. Циклические зависимости не выявляет, но, как вариант, их можно проверить отдельно, уже после сортировки