A few years ago I had a very interesting chat with Danial Kastl, one of the leads of http://pgrouting.org/, the well known routing library for PostGIS. He described to me various ideas for how to route on a graph, and how to deal with turning restrictions. I don't remember all the details, but I can describe what I do remember briefly.
One idea Daniel suggested was to transpose the graph so that nodes were edges and edges were nodes. This did not make sense to be at first, until I thought about it further and what he was actually saying, I believe, was that you need an edge to describe each of the choices you make (turning right, turning left, etc) and these edges have a cost associate with making that turn. For example, at an inmanaged, high traffic intersection, you might find the right turn easy to make, but the left turn hard. This means the routing graph should experience a higher cost to turn left, even if the total distance travelled could be the same with either choice. So instead of the intersection being a single node, it could be a cluster of nodes. I thought it would be easier to perhaps show this idea with a graphgist, so I started making one at http://gist.neo4j.org/?9843702. It is not complete, because I have only created sample models, not queried them, but I think it shows the idea. See the gist, and the attached image I mocked up in the neo4j 2.0 browser. On Fri, Mar 28, 2014 at 3:23 PM, Antonio Grimaldi < [email protected]> wrote: > Hi, > Starting from OSM data file, i already create nodes and edges in neo4j > graph and i can correctly calculate the shortest path with Dijkstra > algorithm. > Then, i created a restriction's list, where each is identified by fromRel, > viaNode, toRel. > Now i would like to manage this information (restriction) too. > Does anyone have any idea how to insert this information in my graph and > as used in the calculation of shortest path with Dijkstra? > > Thank You > Antonio Grimaldi > > -- > You received this message because you are subscribed to the Google Groups > "Neo4j" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Neo4j" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
<<attachment: neo4j-browser-routing.png>>
