root/sandbox/sigis/christian.gonzalez/trunk/README.shortest_path

----------------------------------------------------------------------------------------
The Shortest Path based on Dijkstra algorithm
----------------------------------------------------------------------------------------

The shortest_path functions have the following signature:

CREATE OR REPLACE FUNCTION shortest_path(sql text, source_id integer, target_id integer, 
                                         directed boolean, has_reverse_cost boolean)
RETURNS SETOF path_result

Where path_result is:

CREATE TYPE path_result AS (vertex_id integer, edge_id integer, cost float8);

Arguments are:

* sql (text): a SQL query, which should return a set of rows with the following columns:
                        - id (int4): an int4 identifier of the edge
                        - source (int4): an int4 identifier of the source vertex
                        - target (int4): an int4 identifier of the target vertex
                        - cost (float8): double precision value of the edge traversal cost. (a negative cost 
                                         will prevent the edge from being inserted in the graph).
                        - bidirectional (bool) (optional): specify if the edge is bidirectional, when you use it, 
                                                                                                the algorithm is more efficient!, because only the 
                                                                                                marked edges are added instead of all all edges.
                        - reverse_cost (float8) (optional): the cost for the reverse traversal of the
                                                                                edge. This is only used when the directed 
                                                                                and has_reverse_cost parameters are true (see the above 
                                                                                remark about negative costs).

* dource_id (int4): start node id

* target_id (int4): end node id

* directed (bool): true if the graph is directed.  if you want to use bidirectional and/or reverse_cost 
                        parameters in the query, you need to pass it as true. otherwise these will not be taken.
                                                
* has_reverse_cost (bool): (deprecated, no used by the function internally. Now however, with only passing the 
                                        argument "directed" and "reverse_cost" in the SQL does the same). 
                                        if true, the reverse_cost column of the SQL generated set of rows 
                                        will be used for the cost of the traversal of the edge in the 
                                        opposite direction.

EXAMPLE:

           graph1
        
                           10
                        A----->B
                        |      |
                100     |      |110
                        |      |
        E<------C------D
        |       60      |  20
  35|           |50
        |               |
        G------>F<-----H
           25      15
           
Legend:  
        ------> Unidirectional element
        ------- Bidirectional element
          |
          |             Bidirectional element
          |
          
creating my Graph tables:

-- Vertices of my Graph
CREATE TABLE graph1_vertices
(
   id integer, 
   name varchar(25), 
   CONSTRAINT pk_graph1_vertices_gid PRIMARY KEY (id)
) WITH (OIDS=TRUE);

-- Edges of my Graph
CREATE TABLE graph1_edges
(
   id integer, 
   source integer, 
   target integer,
   bidirectional bool, 
   cost float,
   reverse_cost float, 
   CONSTRAINT pk_graph1_edges_gid PRIMARY KEY (id)
) WITH (OIDS=TRUE);

INSERT INTO graph1_vertices VALUES (100, 'A');
INSERT INTO graph1_vertices VALUES (200, 'B');
INSERT INTO graph1_vertices VALUES (300, 'C');
INSERT INTO graph1_vertices VALUES (400, 'D');
INSERT INTO graph1_vertices VALUES (500, 'E');
INSERT INTO graph1_vertices VALUES (600, 'F');
INSERT INTO graph1_vertices VALUES (700, 'G');
INSERT INTO graph1_vertices VALUES (800, 'H');

INSERT INTO graph1_edges VALUES (1, 100, 200, false, 10, 0.5); -- A->B
INSERT INTO graph1_edges VALUES (2, 200, 400, true, 110, 0.7);  -- B->D
INSERT INTO graph1_edges VALUES (3, 100, 300, true, 100, 0.9); -- A->C
INSERT INTO graph1_edges VALUES (4, 400, 300, true, 20, 1);    -- D->C
INSERT INTO graph1_edges VALUES (5, 300, 600, true, 50, 1);    -- C->F
INSERT INTO graph1_edges VALUES (6, 300, 500, false, 60, 1);   -- C->E
INSERT INTO graph1_edges VALUES (7, 500, 700, true, 35, 1);    -- E->G
INSERT INTO graph1_edges VALUES (8, 700, 600, false, 25, .05); -- G->F
INSERT INTO graph1_edges VALUES (9, 800, 600, false, 45, 1);   -- H->F

Testing my graph:

ROUTE 1:
Undirected Graph:
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'H'),false, false);

result:
 vertex_id | edge_id | cost 
-----------+---------+------
       200 |       1 |   10
       100 |       3 |  100
       300 |       5 |   50
       600 |       9 |   45
       800 |      -1 |    0
(5 rows)

Directed Graph:
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'H'),true, false);

result:
 vertex_id | edge_id | cost 
-----------+---------+------
(0 rows)

ROUTE 2:
Undirected Graph:
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'G'),false, false);

result:
 vertex_id | edge_id | cost 
-----------+---------+------
       200 |       1 |   10
       100 |       3 |  100
       300 |       5 |   50
       600 |       8 |   25
       700 |      -1 |    0
(5 rows)


Directed Graph:
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'G'),true, false);

result:
 vertex_id | edge_id | cost 
-----------+---------+------
       200 |       2 |  110
       400 |       4 |   20
       300 |       6 |   60
       500 |       7 |   35
       700 |      -1 |    0
(5 rows)

Directed Graph with reverse_cost (old version):
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8, reverse_cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'G'),true, true);

 vertex_id | edge_id | cost 
-----------+---------+------
       200 |       1 |  0.5
       100 |       3 |  100
       300 |       5 |   50
       600 |       8 | 0.05
       700 |      -1 |    0
(5 rows)

Directed Graph with reverse_cost (new version):
SELECT * FROM shortest_path('SELECT id::int4, source::int4, target::int4, cost::float8, reverse_cost::float8 FROM graph1_edges', 
(SELECT id::int4 FROM graph1_vertices WHERE name = 'B'), (SELECT id::int4 FROM graph1_vertices WHERE name = 'G'),true, false);

 vertex_id | edge_id | cost 
-----------+---------+------
       200 |       1 |  0.5
       100 |       3 |  100
       300 |       5 |   50
       600 |       8 | 0.05
       700 |      -1 |    0
(5 rows)

LICENCE

Most features are available under GPL.
Some Boost extesions are available under Boost license (see LICENSE_1_0.txt)

AUTHORS
Christian Gonzalez <christian.gonzalez@sigis.com.ve>
Anton A. Patrushev <anton@orkney.co.jp>
Mario H. Basa <mbasa@orkney.co.jp>

Dijkstra part was made by
Sylvain Pasche <sylvain.pasche@camptocamp.com>