2

We are using Neo4J 2.0 embedded; we have a Graph with around 1 Million of Nodes, and 50 Million of relationships; we have to find N shortestPath but with a well known cost property We saw that there is no such method in GraphAlgo class of neo4j and we were thinking to use Chyper, but when run this query

START startNode = node(269604), endNode = node(269605)
MATCH path=(startNode)-[:CAR_MAIN_NODES_RELATION*]->(endNode)
RETURN path AS shortestPath, reduce(cost=0, rel in relationships(path) | cost + rel.edgeLength) AS totalCost
ORDER BY totalCost ASC
LIMIT 3

after 10 minutes, we have not had any results yet...

Did anybody find a solution to this problem? How could we implement such functionality?

Any suggestion is really apreciated... Thank you Antonio

tstorms
  • 4,941
  • 1
  • 25
  • 47
Antonio Grimaldi
  • 43
  • 6
  • There are a couple of algorithms (Dijkstra, A*) available in `GraphAlgoFactory`. Did you check those? – tstorms Mar 25 '14 at 14:21
  • Yes we did.. But there's a limiter in Dijkstra and A* that will stop the iterator after all paths with the lowest cost (if there are multiple) have been returned... So always one path is returned, except when there are two or more paths with the same cost. Instead we would like to found the first 3 alternative path, with different cost. – Antonio Grimaldi Mar 25 '14 at 14:37
  • Maybe it's an option to specify the path depth in the match clause, e.g. `[:CAR_MAIN_NODES_RELATION*..6]`? This will reduce query time greatly. Maybe you can also take a look at `allShortestPaths(startNode)-[:CAR_MAIN_NODES_RELATION*]->(endNode))`? – tstorms Mar 25 '14 at 15:59
  • Yes, if i specify the path depth in the match clause, in this way [:CAR_MAIN_NODES_RELATION*1..5], this will reduce query time greatly, but I'm implementing a routing algorithm, and then I do not know how many nodes and edges I have to cross to calculate the route between two locations. I tried **allShortestPaths(startNode)-[:CAR_MAIN_NODES_RELATION*]->(endNode))** too, but i have this strange behavior : For points very close, one or more routes are calculated, but for two very distant locations, there is no route calculated. – Antonio Grimaldi Mar 25 '14 at 16:07
  • I create plugin for similarly tasks. It is not difficult. – Evgenii Mar 28 '14 at 06:26
  • where can i found your plugin? thanks Antonio – Antonio Grimaldi Apr 14 '14 at 15:44
  • I would need it too, thanks evgeny – M4rk May 01 '14 at 08:54
  • @AntonioGrimaldi Are you able to solve your problem.I am facing the same issue – Arpit Nov 28 '18 at 09:52
  • @Evgenii Have you created something for these types of problem ? – Arpit Nov 28 '18 at 12:53
  • No, only for A* and Dijkstra – Evgenii Nov 30 '18 at 15:21

0 Answers0