[pgrouting-dev] APSP Implementation
Stephen Woodbridge
woodbri at swoodbridge.com
Wed Dec 1 19:32:06 EST 2010
Jay,
Sounds like you have a good handle on all the pieces to this problem.
What do you need to get started :)
-Steve
On 12/1/2010 6:21 PM, Jay Mahadeokar wrote:
> When (v^2 log n) > n^2 we can use Warshall algo. Extracting paths will
>
> be complicated task.
>
> I think some thought needs to go into:
>
> 1. what are the results? just a V^2 table of costs?
>
> 2. can we extract the paths? In pgRouting, this has some
> additional
> implications beyond is it physically possible to extract
> paths from
> the algorithm.
> a. typically queries do not store results, they only
> return sets
> b. extracting paths, implies computing assembling a graph,
> computing the results and holding the results for additional
> queries
> against them to extract paths.
> c. while this is potentially possible using temp tables,
> we do not
> currently do that
>
>
> I did not properly understand point b above.
>
>
> OK, I will try to explain. Typically the process of running a
> pgRouting query follows something along this pseudo code:
>
> 1. select a subset of all node that we think will be enough to solve
> our problem. This is done via a bounding box of the start and end
> nodes inw question and expanded somewhat in case the route wanders
> out of the bounding box.
>
> 2. these nodes and the edges connected to them are built into a
> boost graph
>
> 3. the boost graph is solved
>
> 4. the results are return to the SQL caller as a set of database
> records.
>
> 5. the boost graph is destroyed
>
> So basically one input, one process, one output. Nothing is saved.
> If on the other hand we had a process like:
>
> 1. build graph
> 2. solve graph
> 3. return matrix of distances
> 4. hold onto graph because these might be addition requests the need
> the matrix
> 5. request path A-B from graph
> 6. request path D-H from graph
> 7. request ...
> 8. we are done with the graph so destroy it
>
> Which is my assumption that we would need to do to extract paths,
> then we do not have a paradigm for this in SQL.
>
> Now we may not need to do that, but I was assuming that there was
> information in the graph that was easy to extract about the paths
> that gave the distance returned in the distance matrix.
>
>
>
> Hey.. Again, during step 3 above, if we build the path matrix along
> with the distance matrix for Warshall Algo, we can use that to extract
> all paths, we will not need any more queries to database. We also need
> not hold on to the graph! And the overall time is still O(n^3) :)
>
>
>
> I am not sure if the boost implementation of Warshall returns a path
> matrix,
> http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html
> says that it will just return the distance matrix.
>
> In theory, we can simultaneously create a n^2 path matrix along
> with the
> distance matrix and use that to extract paths. Pseudo code is
> present
> here:
> http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm. So,
> if we want to build the path matrix, we need to code Warshall from
> scratch, using maybe boost data structures.
>
>
> I guess this is up to the use cases for this and maybe we should ask
> others to chime in based on their needs.
>
> I think this really depends on the number of nodes that a user needs
> to work with. If you assume asymmetric directed graph, the you need
> to compute n^2 distances. for small say n<20 that is 400 routes and
> if at 1 sec per route it takes 6.67 minutes; n=100 it takes about
> 2.78 hours.
>
>
> I guess assuming 1 sec per route is too slow for modern processors! If
> you are including the database query latency, then again Path Matrix
> will make sure we need to query database only once, so the rest of the
> work should be fast.
>
> My use case would be to feed the results into TSP solver to order
> the nodes, then to extract the routes between the ordered nodes. I
> have used simulated annealing to solve TSP very fast.
>
> http://imaptools.com/cgi-bin/tsp.cgi
>
> Copy and paste the cities into the text area and compute the TSP.
> This demo application geocodes all the cities and comput the
> straight line distance between them and then solves the TSP problem.
> It would really be grate to compute the network paths before solving
> the TSP.
>
> I know pgRouting has a TSP solver, but it requires the CGAL package
> I think which is hard to find and build on many systems.
>
>
> Nice Application! I am not sure what is complexity of your algorithm.
> But if you want to compute actual paths before feeding the algo, I guess
> the number of nodes in the path will increase by a big factor which will
> slow down APSP significantly. (You may just consider Highways to get
> around this, could discuss this on a separate topic!)
>
>
> If we have vertex ids of whole graph, the path matrix is
> sufficient to
> extract all paths (extracting one path will take O(n) time), and
> I think
> there is no need for additional queries to database.
>
>
> I saw the path extraction code in the wiki page , but I need to go
> back over it in more detail.
>
> Best regards,
> -Steve W
>
> Please correct me if I am missing something.
>
> Anyway, these are some things to start a discussion and
> provoke some
> thoughts. I do not want to grow the scope of this project to the
> point that it is problematic, so we should focus on what can
> be done
> and plan for future additions if they are needed.
>
> I look forward to working with you. Thank you for your
> interest in
> pgRouting.
>
> Best regards,
> -Steve W
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>
> <mailto:pgrouting-dev at lists.osgeo.org
> <mailto:pgrouting-dev at lists.osgeo.org>>
>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org <mailto:pgrouting-dev at lists.osgeo.org>
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
>
>
> --
> Regards,
> -Jay Mahadeokar
>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
More information about the pgrouting-dev
mailing list