Как я могу найти множество нижестоящих родительских (или предковых) узлов P1, которые пересекают все пути между P1 и P2

Question

Предположим, у меня есть следующий график. Как мне найти самый низкий набор узлов, которые пересекают все (ориентированные) пути между узлами [1,2,3,4] и узлом [66]. В моем случае я хочу найти узлы [11, 5,9, 6] (узел 7 должен быть исключен, поскольку узлы 6 и 9 являются более низкими предками узлов 3 и 4. Спасибо за помощь.

Answer 1

У меня есть ответ на подобный вопрос здесь .

Вот шаги, которые я бы предпринял:

1. Подберите начальные узлы [1,2,3,4] и соберите их для дальнейшего использования.
2. Сопоставление и расширение от вашего конечного узла (66) до всех подключенных узлов (с использованием направленного шаблона), внесение в черный список начальных узлов с шага 1 (поэтому мы не включаем пути к этим узлам или за их пределами). Соберите эти узлы как потомки.
3. Расширяйте от ваших начальных узлов, заканчивая потомками (таким образом, мы получаем пути к первому встречному потомку, но не продолжаем расширяться после любого из них).

Cypher не имеет большой поддержки для выполнения завершения во время поведения расширения в шаге 3, поэтому нам нужно процедур расширения пути из процедур APOC для этого.

Предположим, что это узлы типа: Node со id свойствами для числовых значений с отношениями PARENT между ними, указывающими на родителей / предков. Допустим, у нас есть индекс: Node (id) для быстрого поиска. При использовании APOC наш запрос будет выглядеть примерно так:

MATCH (n:Node)
WHERE n.id IN [1,2,3,4]
WITH collect(n) as startNodes
MATCH path = (end:Node {id:66})<-[:PARENT*]-(descendent)
WHERE none(node in nodes(path) WHERE node in startNodes)
WITH startNodes, end, collect(DISTINCT descendent) as descendents
CALL apoc.path.subgraphNodes(startNodes, {terminatorNodes:descendents}) YIELD node as mostRecentDescendents
RETURN mostRecentDescendents