Backtracking in neo4j / following a relationship.

[Ratul Jain]

Hi, I am working on a project dealing with bus routes and I’m using neo4j to retrive indirect routes between two stops. I modelled it in a way in which I was creating a ‘Route’ relationship for all the routes between two stops. This was okay at first but then I reached a point where I had at-least 10 relationships between any two given nodes and that led to most of the queries getting timed out.

So to reduce the number of relationships between two nodes, I am maintaining the routes between two stops as an array relationship property.  

My question is how can I query the DB in such a way that I get that route which requires the lest number of bus changes. Can I implement something like backtracking to achieve this?

I have set up a neo4j instance with some dummy data. Here’s the link to it - http://207.154.231.108:7474/browser/ 

The query I’m using to find the shortest distance between two nodes.

MATCH (origin:Stop {name: "Petraro"}), (destination:Stop {name: "Rossano Scalo - Torre Pisani"}),
path = allShortestPaths((origin)-[:Route*]->(destination))
RETURN path

[Kamal Murthy]

Hi Ratul,

From your link, I picked up the nodes that have relationships and analysed. Here is my recommendation to achieve your goals.

1. I selected two routes: 9 and 23. Here is the Cypher script that I used:

CREATE (bus:Routes {name: "Routes"})

CREATE (route:RtNbr {id: 9})

CREATE (route2:RtNbr {id: 23})

CREATE (bus)-[:ROUTES]->(route)

CREATE (bus)-[:ROUTES]->(route2)

MERGE (stop20: StopID {id:20})

MERGE (stop21: StopID {id:21})

MERGE (stop109: StopID {id:109})

MERGE (stop111: StopID {id:111})

MERGE (stop48: StopID {id:48})

MERGE (stop113: StopID {id:113})

MERGE (stop110: StopID {id:110})

MERGE (route2)-[:START]->(stop20)

MERGE (stop20)-[:TO]->(stop110)

MERGE (stop110)-[:TO]->(stop111)

MERGE (stop111)-[:TO]->(stop48)

MERGE (route)-[:START]->(stop20)

MERGE (stop20)-[:TO]->(stop21)

MERGE (stop21)-[:TO]->(stop109)

MERGE (stop109)-[:TO]->(stop111)

MERGE (stop111)-[:TO]->(stop48)

MERGE (stop48)-[:TO]->(stop113)

; 

2. Shortest path between stop id = 20 and stop id = 38:

MATCH (origin:StopID {id: 20}), (destination:StopID {id: 48}),

path = allShortestPaths((origin)-[:TO*]->(destination))

RETURN path;

Hope this will help you.

Thanks,

-Kamal

[Ratul Jain]

On Wednesday, June 14, 2017 at 1:00:41 AM UTC+5:30, Kamal Murthy wrote:

~snip

Hi Kamal,

Thank you so much for taking your time to answer my query. 

My initial model was kind of similar but this design doesn't scale well. At some point I had multiple [:TO] relationships between various stops and that is when the query started to become really slow.

This is the screenshot of my previous model.

That's the main reason the routes are denoted as an array property rather than their own relationship.

Thanks,

Ratul

[Sudha Murthy]

Hi Ratul,

If you don't mind send me the Cypher script that you used to create it. I keep the info confidential.

My design of keeping the route number as the root node should work. I can try with your data and let you know.

Thanks,

-Kamal

--
You received this message because you are subscribed to a topic in the Google Groups "Neo4j" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/neo4j/_xNewWFaxOU/unsubscribe.
To unsubscribe from this group and all its topics, send an email to neo4j+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Sudha Murthy]

Hi Ratul,

While creating the relationships use MERGE instead of CREATE.  This ensures that a single relation exists between any two stops.  From your screenshot I am assuming you are using a CREATE for every relation.

-Kamal 

On Wed, Jun 14, 2017 at 12:36 AM, Ratul Jain <ratulj...@gmail.com> wrote:

--

[Ratul Jain]

Hi Kamal, 

Sure, I'll set up a test instance with some dummy data. 

Thanks,

Ratul 

To unsubscribe from this group and all its topics, send an email to neo4j+un...@googlegroups.com.

[Ratul Jain]

Hi Kamal,

There are multiple relationships between the stop due to multiple routes between the stops. Each relationship denotes a unique route between two stops.

Thanks,

Ratul

To unsubscribe from this group and all its topics, send an email to neo4j+un...@googlegroups.com.