Shortest path that traverses all instances of a relationship - skiing plan

I've been trying unsuccessfully to find a way to plot a route that traverses every instance of a relationship. It might help if I explain that it's for a ski region map to find the shortest path to ski every run. It doesn't matter how many times a lift is used, and it doesn't matter if some runs needs to be skiied twice. With a next step to be able to select for example, filter to exclude grade black runs (grade being a property of the relationship, as is the name of the run). I've attached an image of my simple starter ski region(V1 is valleystation1, TV1 is top of lift from V1, M is mid-station etc). I realise I could set each lift and ski-run as a node then shortest path to include all ski-run nodes, but I was hoping there was a way to use the relationships so the data is simply stations joined by lifts or ski-runs. I'm fairly new to Neo4j so please don't baffle me (too much)! Thanks for any suggestions

SKI_TO properties, eg
grade Black
Ht -500
Name Run_1
Time 20


Just a few quick notes, to help with anyone looking at this.

// create the mini example to play with
CREATE (tv2:Station {id:'TV2'})
CREATE (mv2:Station {id:'MV2'})
CREATE (v2:Station {id:'V2'})
CREATE (tv1:Station {id:'TV1'})
CREATE (v1:Station {id:'V1'})
MERGE (tv2)-[:SKI_TO]->(mv2)
MERGE (tv2)<-[:LIFT_TO]-(mv2)
MERGE (mv2)-[:SKI_TO]->(v2)
MERGE (mv2)<-[:LIFT_TO]-(v2)
MERGE (tv2)-[:SKI_TO]->(v1)
MERGE (tv1)-[:SKI_TO]->(v2)
MERGE (tv1)-[:SKI_TO]->(v1)
MERGE (tv1)<-[:LIFT_TO]-(v1);

Adding more notes... After some thought I think we should be able to approach this as essentially a variation on TSP (a classic problem) over the LineGraph (swap edges for nodes, and nodes for edges) representation of the information. Working with the LineGraph version of the graph may not be necessary but it feels more natural to me. Note: TSP is an NP-hard problem. In this case we must travel every ski run, but we necessarily may need to travel both lifts and runs one or more times in order to do that. This makes the problem a little more challenging. To start I attempted to create the LineGraph, giving names to each of the lifts/runs like this
Please send corrections if anyone finds issues, I created this by hand (and creating the LineGraph doesn't seem to come naturally to me), so caveats apply. I purposefully avoided label overlap so this graph and the original graph can exist in the same db without overlap.

// remove previous LineGraph (if needed)
MATCH (n) WHERE n:Lift or n:Run detach delete n;

// Create LineGraph
CREATE (R1:Run {id:'TV2_MV2'})
CREATE (L1:Lift {id:'MV2_TV2'})

CREATE (R2:Run {id:'MV2_V2'})
CREATE (L2:Lift {id:'V2_MV2'})

CREATE (R3:Run {id:'TV2_V1'})
CREATE (R4:Run {id:'TV1_V2'})

CREATE (R5:Run {id:'TV1_V1'})
CREATE (L3:Lift {id:'V1_TV1'})

MERGE (L1)-[:STATION {station:'TV2', cost:1.0}]->(R3)
MERGE (L1)-[:STATION {station:'TV2', cost:1.0}]->(R1)

MERGE (R1)-[:STATION {station:'MV2', cost:1.0}]->(L1)
MERGE (R1)-[:STATION {station:'MV2', cost:1.0}]->(R2)

MERGE (R2)-[:STATION {station:'V2', cost:1.0}]->(L2)
MERGE (R4)-[:STATION {station:'V2', cost:1.0}]->(L2)

MERGE (L3)-[:STATION {station:'TV1', cost:1.0}]->(R4)
MERGE (L3)-[:STATION {station:'TV1', cost:1.0}]->(R5)

MERGE (R5)-[:STATION {station:'V1', cost:1.0}]->(L3)
MERGE (R3)-[:STATION {station:'V1', cost:1.0}]->(L3)

the resulting graph looks like this

Sorry this may be hard to read/interpret. For the LineGraph we have to name every lift and run, I had to make up a naming convention.

Note: Thinking a real example might be better I took a quick look at Alta, Utah mountain map (one of my favorite deep powder skiing resorts) but quickly realized a lot of key (e.g. connecting) runs are not even named, so it is much better to just stick with the faux example data.

I've tinkered around with various attempts, but needing to criss-cross multiple times over various lifts and runs you've been on before seems to put a kink in every approach I've tried. At this point, if I had to solve this I'd probably look into using Gremlin. I've never used Gremlin, but have read it may be able to handle this type of dynamic path finding better? Or write a custom modified TSP solver (e.g. in python) probably using NetworkX.

Hi Joel
Thanks for looking at this, and sorry for my delayed reply - I can't get into my "community" account for some reason. It looks like this is a much bigger challenge than I thought it would be. It seemed like a good practical exercise to help with learning graph databases - an easier version of the konigsberg bridge problem(?!) . As you say, the switch of nodes-edges makes it more difficult (for me at least) to follow intuitively but I think there are two links missing - circled - so you don't end up stuck at the top of lift V2-MV2.
Match (a:Lift {id:'V2_MV2'}), (b:Lift {id:'MV2_TV2'}), (c:Run {id:'MV2_V2'})
Merge (a)-[:STATION {station:'MV2', cost:1.0}]->(b)
Merge (a)-[:STATION {station:'MV2', cost:1.0}]->(c)

I still can't figure out a query to "visit" every "run" node, but it looks like a version of this might work?


I could have skied all the runs in my "ski resort" ten times over, with just 5 minutes planning, in the time I've spent trying to figure this out!! so I think I'll leave it until I've got a bit more experience with Neo4j but still happy to have a solution if there is one.

Thanks again

I ran across the Christmas Market as well, which was referenced in one of the Santa's path articles. However, here we need a derivative which can handle criss crossing back over rels and nodes we've been at before (as opposed to the bridges problem which must avoid doing that).

I suspect it may be reasonable to programmatically unravel the lifts/runs aspect into a new (larger) graph that can be solved with a pure TSP solver, but I don't like that idea, I see potential pitfalls before even trying it.

Agree this feels like a graphy problem we should be able to solve, I would have thought, solve easily, but I don't see it yet (without coding).

Confirming that this would be difficult to solve using pure Cypher in large part because Cypher makes use of relationship isomorphism

The same relationship cannot be returned more than once in the same result record.

Thanks for that Joel. I'll redo the model along the lines you suggested but I'll add the stations as nodes as well (so I can add way-points for back country routing options)