Задать вопрос
vshemarov
@vshemarov
php

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

Есть массив, внутри которого элементы могут зависеть друг от друга. Например, вот такой:
$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'

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

ЗЫ. Ясень пень, что могут быть и циклические зависимости и это тоже надо как-то учитывать.
  • Вопрос задан
  • 274 просмотра
Комментировать
Подписаться 1 Оценить Комментировать
Решения вопроса 1
27cm
@27cm
TODO: Написать статус
Как предлагаете отсортировать такое?
$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;
}
Ответ написан
2 комментария
2 комментария
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
PHP разработчик
Ведисофт • Екатеринбург
от 25 000 ₽
PHP-разработчик
M-Social Production • Брянск
от 70 000 ₽
PHP Developer
YCLIENTS • Москва
от 200 000 до 350 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Разработать парсер и админку
19 апр. 2024, в 14:12
30000 руб./за проект
Создать логотип
19 апр. 2024, в 14:10
500 руб./за проект
Разработка дизайна мобильного приложения которое управляет вентиляцией
19 апр. 2024, в 14:01
70000 руб./за проект
Ещё заказы