The focus of this blog post is to introduce Yen’s k-shortest path algorithm that was recently added to Neo4j graph algorithms. I will use Californian road network dataset made available by Feifei Li.

Next, we will enrich our graph using Google’s reverse geocoding API and then proceed to find the shortest path with Dijkstra algorithm and the second shortest path using Yen’s k-shortest algorithm.

Graph schema

Our graph has a simple schema of nodes labeled Intersection connected with relationship CONNECTION to other intersections.

cas.png

Import

Lets first define the constraint in our graph schema.

CREATE CONSTRAINT ON (i:Intersection) ASSERT i.id IS UNIQUE;

Dataset is split into nodes and relationship files. Let’s import them both to get all the data we need.

Import nodes

USING PERIODIC COMMIT
LOAD CSV FROM
"https://www.cs.utah.edu/~lifeifei/research/tpq/cal.cnode" 
as row fieldterminator " "
MERGE (i:Intersection{id:row[0]})
ON CREATE SET i.longitude = toFloat(row[1]),
              i.latitude = toFloat(row[2])

Import relationships

USING PERIODIC COMMIT
LOAD CSV FROM
"https://www.cs.utah.edu/~lifeifei/research/tpq/cal.cedge" 
as row fieldterminator " "
MATCH (start:Intersection{id:row[1]})
MATCH (end:Intersection{id:row[2]})
MERGE (start)-[c:CONNECTION{id:row[0]}]->(end)
ON CREATE SET c.length = toFloat(row[3])

Reverse geocode API

For every intersection in our graph, we can get the address based on the GPS location with the help of Google’s reverse geocoding API . I used apoc.util.sleep(50) to throttle and wait 50 ms between each API call. It cost me around €7 to get this data as I couldn’t find a free version of the API :/.

MATCH (i:Intersection)
CALL apoc.util.sleep(50)
WITH "https://maps.googleapis.com/maps/api/geocode/json?latlng=" + 
toString(i.latitude) + "," + toString(i.longitude) + "&key={google_api_key}" as json,i
CALL apoc.load.json(json) yield value
SET i.name = value.results[0].formatted_address

Analysis

Let’s start with visualizing Santa Barbara’s part of the road network with neovis.js.

 

santa_barbara.png

Neovis configuration
var config = {
   container_id: "viz",
   server_url: "bolt://localhost:7687",
   server_user: "neo4j",
   server_password: "neo4j",
   labels: {
     "Intersection": {
      "caption": "title"
      }
    },
   relationships: {
     "CONNECTION": {
      "caption": false
      }
    },
   initial_cypher: "MATCH p=(i1:Intersection)-[:CONNECTION]->(i2:Intersection)" +
     "WHERE i1.name contains 'Santa Barbara' AND i2.name contains 'Santa Barbara'" +
     "RETURN p limit 500"
 };

Shortest path

We use algo.shortestPath, that uses the Dijkstra algorithm,  to find the shortest path between “Cathedral Peak Trail” and “5750 Stagecoach Rd”. We set direction:BOTH to treat our graph as undirected.

MATCH (start:Intersection{title:"Cathedral Peak Trail"}),
      (end:Intersection{title:"5750 Stagecoach Rd"})
CALL algo.shortestPath.stream(start,end,'length',{direction:'BOTH'}) YIELD nodeId,cost
MATCH (n) where id(n)= nodeId
RETURN n.title,cost

Visualization made with neovis.js.

shortest_path.png

Neovis configuration
var config = {
   container_id: "viz",
   server_url: "bolt://localhost:7687",
   server_user: "neo4j",
   server_password: "neo4j",
   labels: {
     "Intersection": {
       "caption": "title"
     }
   },
   relationships: {
     "CONNECTION": {
       "thickness": "length",
       "caption": false
     }
   },
   initial_cypher: "MATCH (start:Intersection{title:'Cathedral Peak Trail'}),(end:Intersection{title:'5750 Stagecoach Rd'}) " +
     "CALL algo.shortestPath.stream(start,end,'length',{direction:'BOTH',nodeQuery:'Intersection',relationshipQuery:'CONNECTION'}) YIELD nodeId,cost " +
     "MATCH (n) where id(n)=nodeId " + 
     "WITH collect(n) as nodes " +
     "UNWIND range(0, length(nodes)-2) as index " +
     "WITH nodes[index] as from, nodes[index + 1] as to " + 
     "MATCH p=(from)-[:CONNECTION]-(to) " +
     "RETURN p"
 };

Yen’s k-shortest paths

Yen’s k-shortest paths algorithm computes single-source K-shortest loopless paths for a graph with non-negative relationship weights.

It uses the Dijkstra algorithm to find the shortest path and then proceeds to find k-1 deviations of the shortest paths. If we want to find the second shortest path we use k=2 as shown below.

MATCH (start:Intersection{title:"Cathedral Peak Trail"}),
(end:Intersection{title:"5750 Stagecoach Rd"})
CALL algo.kShortestPaths(start, end, 2, 'length' ,{})
YIELD resultCount
RETURN resultCount

Results are stored as paths in our graph.

MATCH p=()-[:PATH_0|:PATH_1]->()
RETURN p

The shortest path is visualized in red and second shortest path in yellow. We can easily observe that the paths diverge right at the start and join together 2 hops before the end.

yens-k2.png

Conclusion

With the addition of Yen’s k-shortest algorithm to the Neo4j graph algorithms library, we can now search for alternative shortest routes in our graph. This can come in handy in various domains.

Register now for your copy of the O’Reilly book, Graph Algorithms: Practical Examples in Apache Spark and Neo4j by Mark Needham and Amy E. Hodler.

Social-AlgoTwitter2 .png

https://www.quora.com/If-Python-and-Java-both-compile-to-bytecode-why-is-Java-so-much-faster

https://coachmancini.com/the-data-scientist-of-the-future/

https://spectrum.ieee.org/tech-talk/semiconductors/processors/ibms-new-doitall-deep-learning-chip