APSP

Basic Idea

    Notations:
    m - edges.
    n - vertices.
    v - vertices in subset.

As the map is a planar graph, number of edges m = O(n). In that case, the Dijkstra Shortest Path algorithm will take O(m + n log n) that is O(n logn) time. Now, if we want to find APSP between small subset of vertices v, we can call Dijkstra v^2 times to get total complexity O(v^2* n log n). We will have a good bound until (v^2 log n) < n^2. This will also return the paths between vertices.

When (v^2 log n) > n^2 we can use Warshall algo. 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. The paths can be extracted again in O(n^3) time as it takes O(n) time to extract one path.

The boost implementation of Warshall returns just a distance matrix: http://www.boost.org/doc/libs/1_45_0/libs/graph/doc/floyd_warshall_shortest.html

Here is a quick tutorial to test the APSP function.

        cmake -DWITH_DD=ON
        sudo make install

To make sure the time_dependent_shortest_path function is installed, log in to pgrouting-worskhop database.

        Psql pgrouting-workshop

Now, to make sure you have installed the tdsp function, type:

       \df+ 'all_pairs_shortest_path'

It should show the installed function. If not perform the following command:

 
        CREATE TYPE apsp_result AS (src_vertex_id integer, dest_vertex_id integer, cost float8);

        CREATE OR REPLACE FUNCTION all_pairs_shortest_path
        (
               sql text, 
               directed boolean, 
               has_reverse_cost boolean
        )
        RETURNS SETOF apsp_result
        AS '$libdir/librouting'
        LANGUAGE 'C' IMMUTABLE STRICT;

Now we are ready to try out the queries.

To try out the query for all vertices common to edges with source id < 100 perform the following query@

    SELECT * from all_pairs_shortest_path
    ('SELECT gid as id,source::integer,target::integer,length::double precision as cost 
    from ways where source in (select source from ways where source < 100)'::TEXT
    ,false,false);

You should get the following output with 21025 rows!

src_vertex_id | dest_vertex_id |         cost          
---------------+----------------+-----------------------
             9 |              9 |                     0
             9 |             10 |     0.014958594862191
             9 |             11 |    0.0287867803774313
             9 |             12 |     0.044636516452449
             9 |             13 |     0.059403394078866
             9 |             14 |    0.0743539641311647
             9 |             15 |    0.0930155625983352
             9 |             16 |     0.108330428173798
             9 |             17 |     0.122591925210141
             9 |             18 |     0.138302851116736
             9 |             19 |     0.150664065575401
             9 |             20 |     0.166092365114059
             9 |             21 |     0.178507416424473
             9 |             22 |     0.160924381208636
             9 |             23 |     0.145278116092299
             9 |             24 |     0.130117668773631
             9 |             25 |     0.113082979539731
             9 |             26 |    0.0985825868141995
             9 |             27 |    0.0834156721012654
             9 |             28 | 1.79769313486232e+308
             9 |             29 | 1.79769313486232e+308
             9 |             30 | 1.79769313486232e+308