Orienteering Gist

This is the Orienteering Dataset based on the blog.neo4j.org post.

XrXYFfsENq 5EpcOtyGN1UU7Z3RGhYdqfnWAjEafGjmmh0nCYdu8 LfImLcm7c3bjRIX8wJUnYaIpKFoAoMO3igUiVre3HKoYkqG5fHVkdmBfudfT7qlF7QbeA

It’s a simple, three-leg training course in an Antwerp park. The graph is really simple: it contains * the Controls of the simple course that I have here * the different route choices (in the form of a series of Waypoints) that an Orienteer could make to go from start to control point, to control point, to finish. Each of the "legs" of the course, and every route choice of that "leg", has a certain distance and runnability score (value from 0,1 to 1). We are thus dealing with a classic pathfinding problem, where we want to find the best route choice to complete the course.

Let’s set this up as a graph in Neo4j - it should be easy enough:

create (one:Control {name:'1'}),
(two:Control {name:'2'}),
(three:Control {name:'Finish'}),
(oneone:Waypoint {name:'011'}),
(onetwo:Waypoint {name:'012'}),
(onethree:Waypoint {name:'013'}),
(onefour:Waypoint {name:'014'}),
(onefive:Waypoint {name:'015'}),
(twoone:Waypoint {name:'021'}),
(twotwo:Waypoint {name:'022'}),
(oneoneone:Waypoint {name:'111'}),
(oneonetwo:Waypoint {name:'112'}),
(oneonethree:Waypoint {name:'113'}),
(onetwoone:Waypoint {name:'121'}),
(twooneone:Waypoint {name:'211'}),
(twotwoone:Waypoint {name:'221'}),
(twotwotwo:Waypoint {name:'222'}),
(twothreeone:Waypoint {name:'231'}),
(twothreetwo:Waypoint {name:'232'}),
(zero)-[:COURSE_TO {distance:110, time:0, runnability:0}]->(one),
(one)-[:COURSE_TO {distance:100, time:0, runnability:0}]->(two),
(two)-[:COURSE_TO {distance:90, time:0, runnability:0}]->(three),
(zero)-[:NAVIGATE_TO {distance:5, time:0, runnability:1}]->(oneone),
(oneone)-[:NAVIGATE_TO {distance:15, time:0, runnability:1}]->(onetwo),
(onetwo)-[:NAVIGATE_TO {distance:5, time:0, runnability:1}]->(onethree),
(onethree)-[:NAVIGATE_TO {distance:100, time:0, runnability:1}]->(onefour),
(onefour)-[:NAVIGATE_TO {distance:80, time:0, runnability:0.9}]->(onefive),
(onefive)-[:NAVIGATE_TO {distance:5, time:0, runnability:0.8}]->(one),
(zero)-[:NAVIGATE_TO {distance:100, time:0, runnability:0.9}]->(twoone),
(twoone)-[:NAVIGATE_TO {distance:10, time:0, runnability:0.8}]->(twotwo),
(twotwo)-[:NAVIGATE_TO {distance:10, time:0, runnability:0.8}]->(one),
(one)-[:NAVIGATE_TO {distance:5, time:0, runnability:0.8}]->(oneoneone),
(oneoneone)-[:NAVIGATE_TO {distance:10, time:0, runnability:0.8}]->(oneonetwo),
(oneonetwo)-[:NAVIGATE_TO {distance:30, time:0, runnability:0.8}]->(oneonethree),
(oneonethree)-[:NAVIGATE_TO {distance:60, time:0, runnability:0.8}]->(two),
(one)-[:NAVIGATE_TO {distance:5, time:0, runnability:0.8}]->(onefive),
(onefive)-[:NAVIGATE_TO {distance:105, time:0, runnability:0.9}]->(onetwoone),
(onetwoone)-[:NAVIGATE_TO {distance:5, time:0, runnability:0.8}]->(two),
(two)-[:NAVIGATE_TO {distance:15, time:0, runnability:0.8}]->(twooneone),
(twooneone)-[:NAVIGATE_TO {distance:75, time:0, runnability:0.9}]->(three),
(two)-[:NAVIGATE_TO {distance:20, time:0, runnability:0.7}]->(twotwoone),
(twotwoone)-[:NAVIGATE_TO {distance:15, time:0, runnability:0.9}]->(twotwotwo),
(twotwotwo)-[:NAVIGATE_TO {distance:75, time:0, runnability:1}]->(three),
(two)-[:NAVIGATE_TO {distance:5, time:0, runnability:0.9}]->(onetwoone),
(onetwoone)-[:NAVIGATE_TO {distance:40, time:0, runnability:0.9}]->(twothreeone),
(twothreeone)-[:NAVIGATE_TO {distance:40, time:0, runnability:0.9}]->(twothreetwo),
(twothreetwo)-[:NAVIGATE_TO {distance:70, time:0, runnability:1}]->(three);

The actual graph then looks like this:

Then I could query it for a shortest path, using just the "distance" as the weights on the relationships/navigation stretches:

MATCH  (startNode:Control {name:"Start"}),
       (endNode:Control {name:"Finish"}),
       p=(startNode)-[:NAVIGATE_TO*]->(endNode)
RETURN p AS shortestPath,
       reduce(distance=0, r in relationships(p) | distance+r.distance) AS totalDistance
       ORDER BY totalDistance ASC
       LIMIT 1;

Of course, a more realistic estimate of the fastest route choice would be to take distance / runnability:

MATCH  (startNode:Control {name:"Start"}),
      (endNode:Control {name:"Finish"}),
      p=(startNode)-[:NAVIGATE_TO*]->(endNode)
RETURN p AS shortestPath,
      reduce(EstimatedTime=0, r in relationships(p) | EstimatedTime+(r.distance/r.runnability)) AS TotalEstimatedTime
      ORDER BY TotalEstimatedTime ASC
      LIMIT 1;

As you can see, this yields a different route choice for the leg from control 1 to 2.

To play some more, use the console below. Enjoy!

rvanbruggen/Orienteering.adoc

Orienteering Gist

nawroth commented Aug 20, 2013

cleishm commented Nov 5, 2013