Orienteering with APOCs

1-Original Orienteering graph.cql

create index on :Control(name);
create index on :Waypoint(name);

create (zero:Control {name:'Start'}),
(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);

2-original and new weighted shortest path.cql

//Original weighted shortestPath query rewritten for schema indexes
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;

//New weighted shortestPath using Apoc implementation of Dijkstra's algorithm
MATCH  (startNode:Control {name:"Start"}), (endNode:Control {name:"Finish"})
call apoc.algo.dijkstra(startNode, endNode, 'NAVIGATE_TO', 'distance') YIELD path, weight
return path;

3-original and new weighted shortest path using calculated runnability param.cql

//Original query with RUNNABILITY rewritten for schema indexes
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;

//add the calculated property for dijkstra to work
match (a)-[r:NAVIGATE_TO]->(b)
set r.calculated=r.distance/r.runnability;

//New weighted shortestPath using Apoc implementation of Dijkstra's algorithm
MATCH  (startNode:Control {name:"Start"}), (endNode:Control {name:"Finish"})
call apoc.algo.dijkstra(startNode, endNode, 'NAVIGATE_TO', 'calculated') YIELD path, weight
return path;

4-larger graph to play with

// Let's try this on a larger orienteering problem
// 10 controls
// 3 routes
// 5 waypoints per route

// ON THIS GRAPH, BOTH IMPLEMENTATIONS WILL WORK - BUT THE SPEED WILL BE VERY DIFFERENT

create index on :Control(seq);

unwind range(0,10) as range
merge (c2:Control {seq: range});
match (n1:Control {seq:0}),(n2:Control {seq:10})
set n1.name = "Start"
set n2.name = "Finish";

match (c1:Control), (c2:Control)
where c2.seq=c1.seq+1
merge (c1)-[:COURSE_TO]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route1Waypoint {name: "Waypoint 1.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route1Waypoint {name: "Waypoint 1.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route1Waypoint {name: "Waypoint 1.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route1Waypoint {name: "Waypoint 1.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route1Waypoint {name: "Waypoint 1.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route2Waypoint {name: "Waypoint 2.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route2Waypoint {name: "Waypoint 2.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route2Waypoint {name: "Waypoint 2.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route2Waypoint {name: "Waypoint 2.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route2Waypoint {name: "Waypoint 2.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route3Waypoint {name: "Waypoint 3.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route3Waypoint {name: "Waypoint 3.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route3Waypoint {name: "Waypoint 3.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route3Waypoint {name: "Waypoint 3.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route3Waypoint {name: "Waypoint 3.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);

5-very large graph to play with.cql

// Let's try this on a larger orienteering problem
// 1000 controls
// 3 routes
// 5 waypoints per route

// ON THIS GRAPH, ONLY THE DIJKSTRA APOC IMPLEMENTATION WILL WORK - BUT THE SPEED WILL BE VERY DIFFERENT

create index on :Control(seq);

unwind range(0,1000) as range
merge (c2:Control {seq: range});
match (n1:Control {seq:0}),(n2:Control {seq:1000})
set n1.name = "Start"
set n2.name = "Finish";

match (c1:Control), (c2:Control)
where c2.seq=c1.seq+1
merge (c1)-[:COURSE_TO]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route1Waypoint {name: "Waypoint 1.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route1Waypoint {name: "Waypoint 1.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route1Waypoint {name: "Waypoint 1.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route1Waypoint {name: "Waypoint 1.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route1Waypoint {name: "Waypoint 1.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route2Waypoint {name: "Waypoint 2.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route2Waypoint {name: "Waypoint 2.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route2Waypoint {name: "Waypoint 2.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route2Waypoint {name: "Waypoint 2.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route2Waypoint {name: "Waypoint 2.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);

match (c1:Control)-->(c2:Control)
where c2.seq=c1.seq+1
with distinct c1,c2
create (c1)-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w1:Route3Waypoint {name: "Waypoint 3.1"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w2:Route3Waypoint {name: "Waypoint 3.2"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w3:Route3Waypoint {name: "Waypoint 3.3"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w4:Route3Waypoint {name: "Waypoint 3.4"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(w5:Route3Waypoint {name: "Waypoint 3.5"})-[:NAVIGATE_TO {distance: toInt(rand()*1000), runnability: ceil(rand()*10)/10}]->(c2);