CODEWITHSUNDEEP
neo4jcypher
alexanoid
alexanoid

Reputation: 25790

Neo4j Cypher order nodes by dependencies

I have the following Nodes tree structure, for example:

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

I may have any such combinations where one Node depends on another.

How do I write the Cypher query to return all :Node lists ordered by their dependencies, so that the least dependent ones come first?

Additionally, is it possible to handle cyclical dependencies with a Cypher query and fail the query in such cases?

Upvotes: 1

Views: 120

Answers (1)

Finbar Good
Finbar Good

Reputation: 1391

I'm assuming the count of dependencies is the number of distinct nodes that can be reached by -[:DEPENDS_ON]->. So here's a suggestion:

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

// Find all leaves 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;

Results with your example data:

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

Upvotes: 1

Related Questions