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.
