Tag Archives: graph database

Graph Databases II: Routing

18 Aug

I wrote a previous post on graph databases that did little more than add some nodes and a relationship. The post required me to install neo4j and python py2neo. It was simple, but it was a start. I have moved on to other things since then, most notably Go. But I have found myself coming back in a round about way. I recently wrote a plugin for Open Trail Data in Leaflet. Trails are a network but the data is really just lines. I thought if we add nodes at the starting points, intersections and eds of the trails, we could use them for routing. I set off to work.

The Data

The first step was grabbing a simple network. I used the Open Trail Data dummy data. I was going to draw nodes then import them in to a graph database, but I decided to shelve that for later – when I know I can route. The data is drawn in the image below.

Open Trail Data

Open Trail Data

The Graph

Next, I needed to create the graph database. I started with all the endpoints of the lines and then added nodes to the intersections. The code below shows how I created two nodes and a path between them.

one = Node(“trail”,id=”1″,junction=”1″)
oneint = Node(“trail”,id=”1″,junction=”1,2,3,4″)
p=Path(one, Rel(“connects”),oneint)

The end result was a graph database as seen in the image below.

Finished Graph Database

Finished Graph Database

Route

Now it was time to route. I do not have weights or costs on the edges. I just wanted to see if I could get from one point to another. I chose node 3 to node 6. They are both on the left. I like it because there are two possibly ways to go. To route, I used the following query:

results=graph.cypher.execute(“START beginning=node(22),end=node(32) MATCH p = shortestPath(beginning-[*..5000]-end) RETURN p”)

The nodes are 22 and 32 because that it the internal ID assigned by the database. My result is a path:

(:trail {id:”3″,junction:”3″})-[:connects]->(:trail {id:”1″,junction:”1,2,3,4″})-[:connects]->(:trail {id:”1″,junction:”1,7″})-
[:connects]->(:trail {id:”7″,junction:”7,6,8,9,12″})-[:connects]->(:trail {id:”6″,junction:”6″})

This tells me the database is going from node 3 to the intersection of 1,2,3,4 to the intersection of 1,7 to the intersection of 7,6,8,9,12 to the end node 6.

You can see the nodes by using

resultPath = results[0][0]
solved=newPath.nodes
for n in solved:
   print n

Now I know all the nodes required to get from one point to another. If I added (lat,long) values to each node, I could have drawn the path on a map.

I will put this in my pocket for later. I am sure it will come up again and I will be better suited to solve a problem. In the meantime, I think I will work on figuring out how to get a standard data format in to the Database – shapefile or geojson?

Advertisements