Поиск в глубину, Как обнаружить алмазные зависимости?

Question

Мне было интересно, кто-нибудь может предоставить несколько указателей о том, как проверять наличие алмазных зависимостей при выполнении поиска в глубину по графику ... У меня есть следующий график A -> B, A -> F, B -> C, B-> E, C -> D, E -> D.

Я пытаюсь построить наемный архив контейнеров, которые представляют указанный граф, однако, когда я достигаю алмазной зависимости, я не уверен, что делать. Например, на моем графике C и E являются дочерними контейнерами B, когда я решаю D, мне нужно сослаться на C и E. Могу ли я обнаружить зависимость от алмаза и объединить C и E в один контейнер?

Answer 1

Мне проще всего представить алгоритмы графов, использующие цвета.

Все узлы начинаются с белого цвета.

Обрабатываемый узел окрашен в серый цвет.

Как только узел обработан, он становится черным.

Вы окрашиваете узел в серый, как только встречаете его.

Вы окрашиваете узел в черный, когда закончите обработку его дочерних элементов.

Если вы столкнулись с черным узлом, вы попали в зависимость от алмаза.

Answer 2

Рохан, вы можете использовать поиск в глубину, чтобы обнаружить "алмазные углубления", ища поперечные или передние края. Если вы посмотрите на реализацию псевдокода deep-first-search на домашней странице boost-graph-library.

... еще если (цвет [v] = черный) (u, v) - поперечный или передний край ...

Answer 3

Рохан, так как я иногда преподаю алгоритмы и структуры данных, я могу быть предвзятым, но я подозреваю, что вам нужно заглянуть в книгу алгоритмов графа. Есть много разных способов сделать что-то, что, кажется, это предлагает, но не совсем понятно, что вы действительно пытаетесь сделать . Да, в этом случае, когда у вас есть два узла с входящими ребрами и исходящими ребрами в / из одинаковых узлов (здесь, (B, E), (B, C) (C, D), (E, D)) это было бы правильно объединить два узла C и E в узел "C, E". Также было бы правомерно разбить D на D ₁ , а D ₂ сделали это дерево вместо DAG.

То есть было бы законно сделать в зависимости от проблемы.

Answer 4

Я не совсем уверен, что вы пытаетесь сделать, но самое позднее, когда ваш график содержит циклы, вам действительно нужно обнаруживать узлы, которые вы неоднократно находите во время поиска. Обычно это делается путем пометки узлов каким-либо образом во время их обработки, чтобы позже вы могли увидеть, посещали ли вы их ранее. Насколько это работает в вашем случае, зависит от вашей реализации и от того, как эти узлы выглядят ...

Answer 5

Теория графов - очень большая и сложная область математики. Это одна из тех вещей, где немного знаний может быть опасной вещью :) Также может быть трудно найти простые объяснения даже для базовых применений теории графов. Очень велики шансы, что все, с чем вы, вероятно, столкнетесь с графиками, будет забито до смерти и имеет в 5 раз больше ловушек и ошибок, чем вы могли себе представить, когда решали проблему.

Полагаю, вы увидите здесь очень разумные предложения, а чуть позже они будут определены как частично или даже в основном неверные. Шаг осторожно.

Answer 6

Я не знаю, как вы определяете узлы графа. Допустим, один из способов представления узла выглядит так:

public interface Node {
            int getValue();
            List<Node> getChildren();
        }

Проблема с такой реализацией заключается в том, что мы не знаем родителя одного узла. Если у нас есть какой-то способ узнать, кто является родителем одного узла, мы можем выяснить зависимость от алмаза.

Например, в вашем случае, мы должны начать с нижней части дерева, и мы можем видеть, что у D есть два Parenets, и они приходят из B. Поэтому я бы сказал, Постройте свой график, который заботится не только о детях, но и о родителях. Затем за один проход выясните, у каких узлов более одного родителя (как у D), и если у этих паренетов (C и E) один и тот же родитель (B).