Как найти все пути через набор заданных узлов в группе обеспечения доступности баз данных?

Question

У меня есть список элементов (синие узлы ниже), которые классифицированы пользователями моего приложения. Сами категории могут быть сгруппированы и классифицированы сами.

Полученная структура может быть представлена ​​в виде Направленного ациклического графа (DAG) , где элементы являются приемниками в нижней части топологии графика, а верхние категории являются источниками. Обратите внимание, что хотя некоторые категории могут быть четко определены, многое будет определяться пользователем и может быть очень грязным.

Пример:

_{(источник: theuprightape.net )}

На этой структуре я хочу выполнить следующие операции:

• найти все предметы (стоки) ниже определенного узла (все предметы в Европе)
• найти все пути (если есть), которые проходят через весь набор из n узлов (все элементы, отправленные через SMTP с сайта example.com)
• найти все узлы, которые лежат ниже всего набора узлов (пересечение: каштановая пища)

Первое кажется довольно простым: начните с узла, пройдите все возможные пути вниз и соберите предметы там. Однако есть ли более быстрый подход? Помните, что узлы, через которые я уже прошел, вероятно, помогают избежать ненужного повторения, но есть ли еще оптимизации?

Как мне перейти ко второму? Похоже, что первым шагом было бы определить высоту каждого узла в наборе, чтобы определить, с какого из них начинать, а затем найти все пути ниже того, который включает остальную часть набора. Но это лучший (или даже хороший) подход?

Алгоритмы обхода графа , перечисленные в Википедии , похоже, связаны с поиском конкретного узла или самого короткого или наиболее эффективного маршрута между двумя узлами. Я думаю, что оба не то, что я хочу, или я просто не смог понять, как это относится к моей проблеме? Где еще мне почитать?

Answer 1

Мне кажется, что это по сути одна и та же операция для всех 3 вопросов. Вы всегда спрашиваете: «Найти все X ниже узла (ов) Y, где X имеет тип Z». Все, что вам нужно, это общий механизм для «определения местоположения всех узлов под узлом» (решает вопрос 3), а затем вы можете отфильтровать результаты для «тип узла = сток» (решает вопрос Q1). Для Q2 у вас есть начальная точка (ваш набор узлов) и ваша конечная точка (любой сток ниже начальной точки), поэтому ваш набор решений - это все пути от начального узла, указанного до приемника. Поэтому я хотел бы предположить, что у вас есть дерево, и базовые алгоритмы обхода дерева могли бы пойти по этому пути.

Answer 2

Несмотря на то, что ваш график ацикличен, цитируемые вами операции напоминают мне о похожих аспектах анализа потоков управления графами. Существует широкий набор алгоритмов, основанных на доминировании , которые могут быть применимы. Например, ваша третья операция напоминает мне границы компьютерного доминирования; Я считаю, что алгоритм будет работать напрямую, если вы временно введете узлы «входа» и «выхода». Узел входа соединяет «заданный набор узлов», а узлы выхода соединяют приемники.

Также см. Основные алгоритмы Роберта Тарьяна .