найти все "древовидные" вершины в DAG - PullRequest
Новая
       56

найти все "древовидные" вершины в DAG

0 голосов
/ 02 июня 2018

Я ищу алгоритм в DAG, который бы идентифицировал все вершины, которые удовлетворяют следующему требованию для данной вершины V: все пути от любого предшественника V к любой наследник V содержит вершину V. Сюда входят как прямой , так и косвенный предшественники и преемники.

Входной DAG всегда будетимеет один корень и будет подключен.

Я думаю, что корень и листья отвечают вышеуказанному требованию, есть пустой набор путей, и «все они» содержат все, что вы хотите :).В любом случае, их легко найти.

Примечание. Если DAG - это политическое дерево, результат содержит все вершины.

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

         (A) 
        / | \
       b  |  \
     / |  |   \
    c (J) r    \
    |    /     (K)
    |  /      /   \
    |/       /     \
   (D)      l       o
    | \      \     / \
    |  \      \   /  (P) 
    e   h      (M)     \
    |  / \       \     (Q)  
    | /  (I)     (N) 
   (F)               
    |                
   (G)
    |
   (H)

Есть идеи?У этой проблемы есть имя?

Ответы [ 2 ]

0 голосов
/ 13 июня 2018

DAG - это набор частичных порядков , и последний подход легче описать в терминах poset.

Поскольку DAG имеет корни, он эквивалентен замене «любого предшественника» корнем.

Если вершина B имеет более одного непосредственного предшественника.Назовите их B1, B2, ..., Bk.Установите A = объединение из B1, B2, ..., Bk.Он существует с момента появления DAG.Вершины V с A

Схема алгоритма такая же, как в верхнем описании: 

solution_set = all vertices
for vertex B that has more incoming edges
   (a) find A join (B1, B2, ..., Bk)
   (b) remove all V, A < V < B, from solution_set

Реализация линий a и b может быть выполнена путем сохранения предшественников для каждой вершины.Это можно найти путем топологической сортировки .Пусть P (v) будет множеством всех предшественников вершины v.

Линия a реализована аналогично.Пусть I - пересечение P (B1), P (B2), ..., P (Bk).Найти самую большую вершину в I, которая достижима от корня только одним путем, который является целым в I. Это делается путем обхода от корня и поиска, если только один преемник последней вершины пути находится в I.

Строка bэто просто P (B) - P (A) - A.

0 голосов
/ 02 июня 2018

Я считаю, что проверка вершины V, такой, что средняя степень соседства V равна нулю, должна быть хорошей отправной точкой для вашего вопроса.

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

NB: Это НЕ ГАРАНТИРУЕТ УНИКАЛЬНОСТЬ V, то есть путьмежду P и S может быть какой-то другой узел U. Это нормально для вас?Мой ответ работает, если узлы-преемники не могут быть связаны с другими узлами-преемниками V, и аналогично, узлы-предшественники не могут быть связаны с другими предшественниками V.

Также под преемниками и предшественниками вы подразумеваете НЕМЕДЛЕННЫЕ преемники / предшественники?Я не уверен, что мой метод будет работать для не немедленных, но если для непосредственного без связей между ними, средняя степень соседа должна работать.

Поскольку вы упомянули DAG, у вас уже будут данные Directed Graph.структура, следовательно, средняя степень соседа для этой структуры данных должна быть в порядке.

NetworkX - это библиотека, с которой мне удобнее всего работать, поэтому эту функцию я бы использовал:

https://networkx.github.io/documentation/networkx-1.5/reference/generated/networkx.algorithms.neighbor_degree.average_neighbor_degree.html#networkx.algorithms.neighbor_degree.average_neighbor_degree

Вышеприведенная функция позволяет вам указать узлы на графике, которые вы хотите проанализировать.Так что кормите его узлом V и всеми узлами S и P.Он должен возвращать среднюю степень соседа для всех узлов.Из dict извлеките значение для узла V и проверьте, равен ли он нулю

Было бы трудно помочь вам в дальнейшем без некоторого кода или образца структуры данных с вашей стороны.Я могу обновить этот ответ с помощью некоторого кода NetworkX, если вы можете предоставить мне начальный код

...