Traversing Neo4j graph in increasing order of relationship weights using Cypher

Question

Consider I have following graph with edge weights:

I want to know if I can perform traversal starting at node a and following edges with increasing order of their weight using CYPHER. That is above it should return (a)-4->(e)-3->(c)-3->(d)

Is this possible using cypher?

Answer 1

As @FrankPavageau stated, coding the solution in Java may be less cumbersome and faster. Nevertheless, by taking advantage of the existing APOC procedure apoc.periodic.commit, you do not have to implement anything in Java.

apoc.periodic.commit will repeatedly execute a Cypher query until it returns a value of 0 or no results at all. Here is an example of how to use it to solve your problem.

First, let's create your sample data:

CREATE (a:Foo {id: 'a'}), (b:Foo {id: 'b'}), (c:Foo {id: 'c'}), (d:Foo {id: 'd'}), (e:Foo {id: 'e'}), (f:Foo {id: 'f'}), (g:Foo {id: 'g'}),
  (a)-[:NEXT {value: 3}]->(b),
  (a)-[:NEXT {value: 4}]->(e),
  (e)-[:NEXT {value: 3}]->(c),
  (e)-[:NEXT {value: 1}]->(f),
  (e)-[:NEXT {value: 2}]->(g),
  (c)-[:NEXT {value: 3}]->(d),
  (c)-[:NEXT {value: 2}]->(g);

This technique involves 3 queries on your part:

1. A query to create a temporary node with the Temp label (to persist state between the repeated executions performed in step 2, below, and to hold the final results). (In the sample data, the starting node has an id of a.)

   MERGE (temp:Temp)
   SET temp = {values: [], ids: ['a']};
   

2. A query to call apoc.periodic.commit to perform repeated executions of the passed Cypher statement. Each time that Cypher statement is executed, it starts from the last-found node (the one whose id is at the tail end of temp.ids), and attempts to find the next node whose relationship has the highest value value. If the last node was a leaf node, then the Cypher statement returns nothing (since the second MATCH will fail, aborting the statement) -- which will terminate the procedure; otherwise, the Cypher statement will append the max value to temp.values and the corresponding node id to temp.ids, and return 1.

   CALL apoc.periodic.commit("
     MATCH (temp:Temp)
     MATCH (:Foo {id: LAST(temp.ids)})-[n:NEXT]->(f:Foo)
     WITH temp, REDUCE(s = {max: 0}, x IN COLLECT({v: n.value, id: f.id}) |
       CASE WHEN x.v > s.max
         THEN {max: x.v, id: x.id}
         ELSE s
       END
     ) AS curr
     SET temp.values = temp.values + curr.max, temp.ids = temp.ids + curr.id
     RETURN 1;
   ", NULL);
   

3. A query to get the final results. The ids collection will be the ids of the nodes along the "maximum path", and the values collection will be the values of the NEXT relationships along that same path.

   MATCH (temp:Temp)
   RETURN temp;
   

Here is the result:

╒══════════════════════════════════════╕
│temp                                  │
╞══════════════════════════════════════╡
│{values: [4, 3, 3], ids: [a, e, c, d]}│
└──────────────────────────────────────┘

Answer 2

Your description is slightly wrong (based on your example), as you don't want to traverse relationships with an increasing weight, you want to traverse the relationship(s) with the maximum weight at each step.

You can't do it in a generic way in Cypher, because the result is built iteratively, and you can't know the maximum length of a result path.

In Cypher, you'd have to

1. build all the paths
2. filter them by the weight of the first relationship
3. filter the remaining ones by the weight of the second relationship (it if exists)
4. etc.

The declarative nature of Cypher is not really compatible: it would be cumbersome, and probably slow as well. It would be much easier to build a procedure or function (in the upcoming Neo4j 3.1) traversing the longest path(s), with the PathExpander only returning the relationships with the maximum weight from the current node.