Orienteering.adoc

Orienteering Gist

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

It’s a simple, three-leg training course in an Antwerp park. Setting this up as a graph in neo4j was easy enough:

CREATE

// create the nodes

(zero:Control{name:'Start'}),
(one:Control{name:'1'}),
(two:Control{name:'2'}),
(three:Control{name:'Finish'}),
(oneone:Waypoint{name:'Waypoint 011'}),
(onetwo:Waypoint{name:'Waypoint 012'}),
(onethree:Waypoint{name:'Waypoint 013'}),
(onefour:Waypoint{name:'Waypoint 014'}),
(onefive:Waypoint{name:'Waypoint 015'}),
(twoone:Waypoint{name:'Waypoint 021'}),
(twotwo:Waypoint{name:'Waypoint 022'}),
(oneoneone:Waypoint{name:'Waypoint 111'}),
(oneonetwo:Waypoint{name:'Waypoint 112'}),
(oneonethree:Waypoint{name:'Waypoint 113'}),
(onetwoone:Waypoint{name:'Waypoint 121'}),
(twooneone:Waypoint{name:'Waypoint 211'}),
(twotwoone:Waypoint{name:'Waypoint 221'}),
(twotwotwo:Waypoint{name:'Waypoint 222'}),
(twothreeone:Waypoint{name:'Waypoint 231'}),
(twothreetwo:Waypoint{name:'Waypoint 232'}),

// create the relationships

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:

START  startNode=node:node_auto_index(name="Start"),
       endNode=node:node_auto_index(name="Finish")
MATCH  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:

START  startNode=node:node_auto_index(name="Start"),
       endNode=node:node_auto_index(name="Finish")
MATCH  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!