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