Orienteering Gist

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. 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!

you need a //console to run against. We should probably do that by default in later updates :)

• Also, //graph1 -> //graph, numbers not used anymore, it's always taking the previous query.
• name the gist file something like "orienteering.adoc" to get Githubs ASCIIDOC markup when viewing the raw gist :)

check out

//setup
//hide

for the first query!

Really nice gist!

If there's no console defined, we should add one at the end of the page. I'll fix that.

Really cool to the see the different query results in the graphs!

You could hide the first query as Peter says, but I like it as it is. Using //setup would make sense, but due to bugs the data is already in the console even without it most of the time (and would then get duplicated if using //setup). The server side needs to be fixed ...

I'd suggest to reformat Query 3, so it doesn't render with a horizontal scrollbar.

If fixed so that a console is added at the end of the page, if there wasn't a console defined already.

Hi @rvanbruggen! I've updated this gist to work with the latest 2.0 milestone: https://gist.github.com/cleishm/7311886. If you could update this copy, that would be great.