Sounds like you have a good handle on all the pieces to this problem.

What do you need to get started

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–Warshall_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@lists.osgeo.org

<mailto:pgrouting-dev@lists.osgeo.org>

<mailto:pgrouting-dev@lists.osgeo.org

<mailto:pgrouting-dev@lists.osgeo.org>>

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--

Regards,

-Jay Mahadeokar

_______________________________________________

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

_______________________________________________

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--

Regards,

-Jay Mahadeokar

_______________________________________________

pgrouting-dev mailing list

pgrouting-dev@lists.osgeo.org

http://lists.osgeo.org/mailman/listinfo/pgrouting-dev