Neo4j Cypher 按依赖关系对节点进行排序

Question

我有以下节点树结构，例如：

(n1:Node)-[:DEPENDS_ON]->(n2:Node)
(n4:Node)-[:DEPENDS_ON]->(n2:Node)
(n5:Node)-[:DEPENDS_ON]->(n1:Node)
(n5:Node)-[:DEPENDS_ON]->(n4:Node)

我可能有任何这样的组合，其中一个节点依赖于另一个节点。

如何编写 Cypher 查询以返回所有 :Node 列表（按其依赖关系排序），以便最不依赖的节点排在前面？

此外，是否可以使用 Cypher 查询处理循环依赖关系并在这种情况下查询失败？

Answer 1

我假设依赖项的数量是

-[:DEPENDS_ON]->

可以到达的不同节点的数量。所以这里有一个建议：

// Raise an exception if a cycle is found
CALL apoc.util.validate(
    EXISTS { (n:Node)-[:DEPENDS_ON]->+(n) }, 
    'Cyclical dependencies exists', 
    [0]
)

// Find all leafs connected to each other
// The first two NOT EXISTS check for leaves
// The third NOT EXISTS removes duplicates
MATCH (a:Node)-[:DEPENDS_ON]-*(b:Node)
WHERE NOT EXISTS { (a)-[:DEPENDS_ON]->(:Node) }
    AND NOT EXISTS { (b)-[:DEPENDS_ON]->(:Node) }
    AND a <= b
    AND NOT EXISTS { 
            MATCH (a)-[:DEPENDS_ON]-+(c:Node) 
            WHERE NOT EXISTS { (c)-[:DEPENDS_ON]->(:Node) } 
            AND c < a 
        }
WITH a, collect(DISTINCT b) AS connectedLeaves

// Find all nodes connected to those sets of leaves 
// a is the group key, so each disconnected dependency graph is kept separate
UNWIND a + connectedLeaves AS leaf
MATCH (n:Node)-[:DEPENDS_ON]->*(leaf)
WITH a, collect(DISTINCT n) AS connected

// Collect into list ordered by number of dependencies
RETURN COLLECT {
    WITH connected
    UNWIND connected AS n
    MATCH (n:Node)-[:DEPENDS_ON]->*(t:Node)
    WITH n, count(DISTINCT t) AS numDependencies
    RETURN n ORDER BY numDependencies
} AS connectedDependencies;

示例数据的结果：

+----------------------------------------------------------------------+
| connectedDependencies                                                |
+----------------------------------------------------------------------+
| [(:Node {id: 2}), (:Node {id: 4}), (:Node {id: 1}), (:Node {id: 5})] |
+----------------------------------------------------------------------+