Find Longest Path in Graph

2019-05-09 21:58发布

I have been trying hard to find out longest path in a complex network. I have been through many questions in StackOverflow and Internet, but none could help me. I have written a CQL as

start n=node(*)
match p = (n)-[:LinkTo*1..]->(m)
with n,MAX(length(p)) as L
match p = (n)-[:LinkTo*1..]->(m)
where length(p) = L
return p,L

I don't get any solution. Neo4J would keep running for the answer, and I also tried executing it in Neo4J Cloud Hosting. I didn't any solution even there, but got an error "Error undefined-undefined" I am in dire need of a solution. The result for this answer will help me complete my project. So, anyone please help me in correcting the query.

标签: neo4j cypher
2条回答
虎瘦雄心在
2楼-- · 2019-05-09 22:39

Well for one you're doing a highly expensive operation twice when you only have to do it once.

Additionally, you are returning one path per every single node in your database, at least (as there may be multiple paths for a node that are the longest paths available for that node). But from your question it sounds like you want the single largest path in the graph, not one each for every single node.

We can also improve your match by only performing the longest-path match on nodes that are at the head of the path, and not somewhere in the middle.

Maybe try this one?

match (n)
where (n)-[:LinkTo]->() and not ()-[:LinkTo]->(n)
match p = (n)-[:LinkTo*1..]->(m)
return p, length(p) as L
order by L desc
limit 1
查看更多
男人必须洒脱
3楼-- · 2019-05-09 22:57

The problem you're trying to solve is NP-hard. On small sparse graphs a brute-force approach such as the one suggested by InverseFalcon may succeed in reasonable time, but on any reasonably large and/or densely connected graph, you will quickly run into both time and space problems.

If you have a weighted graph, you can find the longest path between 2 nodes by negating all the edge-weights, and running a shortest weighted path algorithm over the modified graph. However if you want to find the longest path in the entire graph, you are effectively trying to solve the Travelling Salesman Problem, but with -ve edge weights. You can't do that with Cypher.

If your graph is unweighted, I'd find an easier problem, or see if you can convert your graph to a weighted one and tackle it as described above. Alternatively, see if you can frame your requirements in such a way that you don't need to find a longest path.

查看更多
登录 后发表回答