Найти все листья выбранного подграфа с помощью Neo4j / Cypher

Question

Исходная ситуация

• Большой граф Neo4j 3.4.6 с древовидной структурой (10 уровней в глубину, 10 миллионов узлов).
• Необыкновенно все узлы связаны друг с другом. Узлы, а также отношения в каждом случае имеют одинаковый тип.
• Ровно один центральный корневой узел.
• Сокращенный и упрощенный пример:

Графическое представление

CREATE (Root:CustomType {name: 'Root'})
CREATE (NodeA:CustomType {name: 'NodeA'})
CREATE (NodeB:CustomType {name: 'NodeB'})
CREATE (NodeC:CustomType {name: 'NodeC'})
CREATE (NodeD:CustomType {name: 'NodeD'})
CREATE (NodeE:CustomType {name: 'NodeE'})
CREATE (NodeF:CustomType {name: 'NodeF'})
CREATE (NodeG:CustomType {name: 'NodeG'})
CREATE (NodeH:CustomType {name: 'NodeH'})
CREATE (NodeI:CustomType {name: 'NodeI'})
CREATE (NodeJ:CustomType {name: 'NodeJ'})
CREATE (NodeK:CustomType {name: 'NodeK'})
CREATE (NodeL:CustomType {name: 'NodeL'})
CREATE (NodeM:CustomType {name: 'NodeM'})
CREATE (NodeN:CustomType {name: 'NodeN'})
CREATE (NodeO:CustomType {name: 'NodeO'})
CREATE (NodeP:CustomType {name: 'NodeP'})
CREATE (NodeQ:CustomType {name: 'NodeQ'})

CREATE
  (Root)-[:CONTAINS]->(NodeA),
  (Root)-[:CONTAINS]->(NodeB),
  (Root)-[:CONTAINS]->(NodeC),
  (NodeA)-[:CONTAINS]->(NodeD),
  (NodeA)-[:CONTAINS]->(NodeE),
  (NodeA)-[:CONTAINS]->(NodeF),
  (NodeE)-[:CONTAINS]->(NodeG),
  (NodeE)-[:CONTAINS]->(NodeH),
  (NodeF)-[:CONTAINS]->(NodeI),
  (NodeF)-[:CONTAINS]->(NodeJ),
  (NodeF)-[:CONTAINS]->(NodeK),
  (NodeI)-[:CONTAINS]->(NodeL),
  (NodeI)-[:CONTAINS]->(NodeM),
  (NodeJ)-[:CONTAINS]->(NodeN),
  (NodeK)-[:CONTAINS]->(NodeO),
  (NodeK)-[:CONTAINS]->(NodeP),
  (NodeM)-[:CONTAINS]->(NodeQ);

Будет решена задача

• Посредством запроса Cypher с MATCH-WITH-UNWIND я успешно могу выбрать поддерево и связать его с путем. Допустим, поддерево охватывает узлы A, E, F, I и J.
• Основываясь на этом пути, мне нужны все листья поддерева, а не полное дерево.

.

MATCH
  path = (:CustomType {name:'NodeA'})-[:CONTAINS*]->(:CustomType {name:'NodeJ'}) /* simplified */
WITH
  nodes(path) as selectedPath
  /* here: necessary magic to identify the leaf nodes of the subtree */
RETURN
  leafNode;

• Помимо прочего, я пытался решить требование с помощью подхода WHERE NOT(node-->()), но понял, что это работает только для листьев полного дерева. К сожалению, я не смог убедить предложение WHERE NOT(node-->()) уважать выбранные границы поддерева.
• Итак, как мне найти все листья выбранного подграфа с помощью Cypher и Neo4j? Можете ли вы дать мне совет, как решить эту проблему? Заранее большое спасибо за указание в правильном направлении!

Answer 1

Вы правильно заметили, что проверочный узел без дочерних элементов подходит только для всего дерева. Таким образом, вам нужно пройти через все отношения в поддереве и найти такой узел поддерева, который является концом отношения, но не началом его:

MATCH
  path = (:CustomType {name:'NodeA'})-[:CONTAINS*]->(:CustomType {name:'NodeJ'})
UNWIND relationShips(path) AS r
WITH collect(DISTINCT endNode(r))   AS endNodes, 
     collect(DISTINCT startNode(r)) AS startNodes
UNWIND endNodes AS leaf
WITH leaf WHERE NOT leaf IN startNodes
RETURN leaf