Find all relationship disjoint longest paths in cypher/traversal API ordered by size

Question

I have an algorithm that I want to implement that finds the longest path/s in a graph. Then finds the next longest path/s that do not have any relationships in common with the previous path/s and so forth until the entire graph is represented as disjoint paths. They are disjoint with respect to the relationships they contain but will have overlapping nodes where they connect. I want each of these relationship disjoint paths ordered from largest to smallest.

I was wondering if anybody could give me pointers at how to do this with Cypher or the Traversal API. Speed would be preferable, but if there is not a big difference between Cypher and the Traversal API I'd rather go with a nice Cypher expression.

I can imagine finding the largest path/s, removing it/them, then searching for the next largest path/s but this is not ideal at all.

Answer 1

I think you can do it but i do not necessarily think it is a good idea particularly in a large graph. I think if you were to give it a starting point; limit the number of relationships you matched (i.e. start with known long length ranges); and limit the number of paths you return then it might be doable in chunks. But I think an open ended unconstrained search for the longest paths in a large graph would probably never return successfully.

But, it is and interesting question and test of what you can do with cypher so I gave it a shot and this is what I came up with.

I created a little test data to work with.

create (n1:Node {name: 'A'})
create (n2:Node {name: 'B'})
create (n3:Node {name: 'C'})
create (n4:Node {name: 'D'})
create (n5:Node {name: 'E'})
create (n6:Node {name: 'F'})
create (n7:Node {name: 'G'})
create (n1)-[:NEXT {touched: false}]->(n2)
create (n2)-[:NEXT {touched: false}]->(n3)
create (n3)-[:NEXT {touched: false}]->(n4)
create (n5)-[:NEXT {touched: false}]->(n3)
create (n4)-[:NEXT {touched: false}]->(n6)
create (n7)-[:NEXT {touched: false}]->(n4)
return *

This is what it looked like when loaded. For every property i added a flag called touched that i could test when matching and then change to true if it had been used.

I decided to operate with the constraint of directed relationships in the graph.

// start by matching all of the directed paths in the graph
// where all the relationships in the path have a touched
// property of 'false'
// order those paths by length in descending order 
// and stick them in a collection
match p=(:Node)-[:NEXT* {touched: false}]->(:Node)
with p
order by length(p) desc
with collect(p) as all_paths
with all_paths

// unwind the collection of paths
// that are organized longest to shortest
// isolate the first node and end node of each path 
unwind all_paths as curr_path
with curr_path
, nodes(curr_path)[0] as a
, nodes(curr_path)[length(curr_path)] as b

// re-match the path from a to b to see if it is still good
// and a realtioship has not been used in an earlier matched
// path
optional match test_path=(a)-[:NEXT* {touched: false}]->(b)
with curr_path
, test_path

// if the first node and last node are the same and all
// of the nodes in one are in the other then i am assuming they
// are the same. to be safe, i could have added a length comparison
// too or done the reverse lookup of test_path in curr_path 
, case 
    when all(n in nodes(curr_path) 
      where n in nodes(test_path)) then [1]
    else []
  end as equal

// if the original path match, curr_path, matches 
// test_path then set all of the flags ont he relationships to
// 'true' so these relationships will not be used again
foreach (n in equal |
  foreach (r in relationships(curr_path) |
    set r.touched = true))

// filter out the paths that do not match
// on the subsequent test and return only those that do
with curr_path, test_path, equal
, case when length(equal) = 1 then curr_path
  end as path
with collect (path) as disparate_paths
return disparate_paths

This returns three paths:

• A-->B-->C-->D-->F
• E-->C
• G-->D