[postgis-devel] Routing Algorithms

[Anton Patrushev]

I checked GEOS geomgraph class and it seams like it has everything we
need - directed graph representation and connectivity and adjacency
check routines. I understand Andrew's concern about reusable libraries
and support it indeed. As Mateusz mentioned, we currently use Dijkstra
and A* from BGL, while Shooting* is written from scratch. I can say it
is a piece of cake to implement first two algorithm with GEOS graph
(as they are well known and described in any book on algorithms
theory), but I can't tell anything about moving Shooting* to GEOS - it
is definitely possible, just can't estimate it right away sitting here
at Helsinki airport.

Anyway, pgRouting source code needs to be cleaned up and probably all
interfaces of all routing functions should also be revisited (I don't
think that evaluating strings as SQL queries is a common practice). I
started this process last year, but it didn't meet any support from my
employer that time, but now I'm going to brush up this project.

So, my conclusion is - if you guys think it makes more sense to
migrate from Boost to GEOS, we can do it. But as long as I'm just one
person (which could be distracted by some other projects Georepublic
needs would to take to survive), any help would be really appreciated
:)


Anton.