Есть последовательность сущностей — A, B, C, D, E, F, .....
Любая сущность может содержать в себе ссылку на любую другую из этой последовательности, кроме самой себя.
Обязательно есть сущность, которая не зависит ни от какой другой.
Вопроса два
1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B?
2) Как отсортировать эту последовательность по принципу зависимостей? То есть первые должны стоять те, которые ни от кого не зависят, дальше, те, которые зависят только от первых и так далее?
Впрочем, по второму у меня придумалось решение. Ввести число для каждой сущности — коэффициент зависимостей. У тех, которые ни от кого не зависят — он равен нулю, а у тех, которые завият — от равен (максимум коэффициента детей + 1). И по этому числу и отсортировать. Этот подход будет работать? Нет подводных камней?
А вот по первому что-то ничего оптимального не придумалось, кроме кучи переборов.
Здравствуйте, SergeyOsipov, Вы писали:
SO>1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B?
Решение в лоб.
Для каждого узла построить дерево зависимостей.
Если в этом дереве окажется сам стартовый узел, то петля имеется.
Если до стартового узла не добрался, но дерево получилось слишком длинным, то петля наверняка есть, только стартовый узел в ней не участвует.
Здравствуйте, Mihas, Вы писали:
SO>>1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B? M>Решение в лоб. M>Для каждого узла построить дерево зависимостей. M>Если в этом дереве окажется сам стартовый узел, то петля имеется. M>Если до стартового узла не добрался, но дерево получилось слишком длинным, то петля наверняка есть, только стартовый узел в ней не участвует.
Но если построить такое дерево для каждого узла, то наверняка найдется дерево, где стартовый узел повторится. Так ведь? Или нет?
Просто термин "слишком длинное" довольно размыт.
Здравствуйте, SergeyOsipov, Вы писали:
SO>Но если построить такое дерево для каждого узла, то наверняка найдется дерево, где стартовый узел повторится. Так ведь? Или нет?
Поясню. Дерево нужно строить отдельно для каждого узла. И контролировать его появление только в этом дереве. В соседние деревья лезть не зачем.
SO>Просто термин "слишком длинное" довольно размыт.
Здесь надо подумать. Внутренний голос подсказывает: если имеем всего N узлов, то глубина дерева не должна превышать N. Если больше, то где-то пошли по второму кругу.
Здравствуйте, SergeyOsipov, Вы писали:
SO>Есть последовательность сущностей — A, B, C, D, E, F, ..... SO>Любая сущность может содержать в себе ссылку на любую другую из этой последовательности, кроме самой себя. SO>Обязательно есть сущность, которая не зависит ни от какой другой.
SO>Вопроса два SO>1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B? SO>2) Как отсортировать эту последовательность по принципу зависимостей? То есть первые должны стоять те, которые ни от кого не зависят, дальше, те, которые зависят только от первых и так далее?
SO>Впрочем, по второму у меня придумалось решение. Ввести число для каждой сущности — коэффициент зависимостей. У тех, которые ни от кого не зависят — он равен нулю, а у тех, которые завият — от равен (максимум коэффициента детей + 1). И по этому числу и отсортировать. Этот подход будет работать? Нет подводных камней?
Будет работать.
SO>А вот по первому что-то ничего оптимального не придумалось, кроме кучи переборов.
На самом деле решение вопроса 2 будет работать и для 1 тоже и наоборот.
Подробнее
1) выбираются вершины (графа) без исходящих зависимостей. Если таковых нет — значит присутствуют циклы. Выбранные вершины добавляем в результирующую последовательность, полагая что они все равны (или сортируя еще по какому-нибудь признаку)
2) удаляем их графа ребра, входящие в выбранные вершины.
3) готу 1)
Если достаточно определить, есть ли циклы — это уже будет работать. Если нужно определить, какие узлы входят в циклы, придется действовать сложнее.
З.Ы. Вряд ли алгоритм оптимален, зато прост.
Здравствуйте, SergeyOsipov, Вы писали:
SO>Есть последовательность сущностей — A, B, C, D, E, F, ..... SO>Любая сущность может содержать в себе ссылку на любую другую из этой последовательности, кроме самой себя. SO>Обязательно есть сущность, которая не зависит ни от какой другой.
SO>Вопроса два SO>1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B?
проверка графа на ацикличность
SO>2) Как отсортировать эту последовательность по принципу зависимостей? То есть первые должны стоять те, которые ни от кого не зависят, дальше, те, которые зависят только от первых и так далее?
поиск в ширину
Здравствуйте, samius, Вы писали:
S>На самом деле решение вопроса 2 будет работать и для 1 тоже и наоборот. S>Подробнее S>1) выбираются вершины (графа) без исходящих зависимостей. Если таковых нет — значит присутствуют циклы. Выбранные вершины добавляем в результирующую последовательность, полагая что они все равны (или сортируя еще по какому-нибудь признаку) S>2) удаляем их графа ребра, входящие в выбранные вершины. S>3) готу 1)
S>Если достаточно определить, есть ли циклы — это уже будет работать.
Интересно. Надо обдумать. А в какой именно момент такого упрощения графа придут уверенность, что циклы есть? Граф больше не упрощается, а зависимости остались?
Здравствуйте, SergeyOsipov, Вы писали:
SO>Здравствуйте, samius, Вы писали:
S>>Если достаточно определить, есть ли циклы — это уже будет работать.
SO>Интересно. Надо обдумать. А в какой именно момент такого упрощения графа придут уверенность, что циклы есть? Граф больше не упрощается, а зависимости остались?
Когда необработанные вершины еще остались, но среди них нет ни одной с 0-ой степенью исхода (без зависимостей) — значит цикл.
Здравствуйте, SergeyOsipov, Вы писали:
SO>Впрочем, по второму у меня придумалось решение. Ввести число для каждой сущности — коэффициент зависимостей. У тех, которые ни от кого не зависят — он равен нулю, а у тех, которые завият — от равен (максимум коэффициента детей + 1). И по этому числу и отсортировать. Этот подход будет работать? Нет подводных камней?
A
/ \
B \
/ \
C E
/ / \
D F G
У B коэффициент зависимостей получается больше, чем у E, что, эээ, контринтуитивно.
SO>А вот по первому что-то ничего оптимального не придумалось, кроме кучи переборов.
Заводим множество необработанных узлов, и изначально кладем все узлы туда.
В каждом узле заводим признак, что он уже обработан, и множество узлов, от которых он зависит.
Пока множество необработанных узлов не опустеет:
* берем оттуда первый попавшийся узел
* применяем к нему алгоритм поиска зависимостей для узла.
Алгоритм рекурсивный:
* для всех узлов, от которых данный узел зависит напрямую:
** если узел еще не обработан, рекурсивно применяем этот алгоритм
** заносим в множество собственных зависимостей этот узел и его зависимости
* помечаем узел, как обработанный, и удаляем его из "глобального" множество необработанных узлов
Когда мы чего-нибудь заносим в список зависимостей, проверяем, не занесли ли мы туда себя. Если да, значит в графе зависимостей случился цикл, аварийно завершаемся.
Если операции добавления/удаления узла в множество зависимостей и объединения двух множеств имеют сложность O(1), этот алгоритм имеет сложность O(N), что весьма неплохо.
Естественно, я этот алгоритм не отлаживал, а прям сейчас из головы выдумал, так что где-то мог и ошибиться
Здравствуйте, SergeyOsipov, Вы писали:
SO>1) Как найти есть ли петли в зависимостях? То есть исключить случаи, когда В зависит от С, С зависит от D и А, а D зависит от F и B? SO>2) Как отсортировать эту последовательность по принципу зависимостей? То есть первые должны стоять те, которые ни от кого не зависят, дальше, те, которые зависят только от первых и так далее?
Перекуём баги на фичи!
