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

Question

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

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

Пример:

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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