Shortest Path Shooting Star

[日本語]

The shortest_path_shooting_star function has the following declaration: 

CREATE OR REPLACE FUNCTION shortest_path_shooting_star(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: a SQL query, which should return a set of rows with the following columns: 

SELECT id, source, target, cost, x1, y1, x2, y2, rule, to_cost FROM edges
  • id: an int4 identifier of the edge
  • source: an int4 identifier of the source vertex
  • target: an int4 identifier of the target vertex
  • cost: double precision value of the edge traversal cost. (a negative cost will prevent the edge from being inserted in the graph).
  • reverse_cost (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).
  • directed: true if the graph is directed
  • has_reverse_cost: 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.
  • x1: double precision value of x coordinate for edge's start vertex
  • y1: double precision value of y coordinate for edge's start vertex
  • x2: double precision value of x coordinate for edge's end vertex
  • y2: double precision value of y coordinate for edge's end vertex
  • rule: a string with a comma separated list of edge ids which describes a rule for turning restriction (if you came along these edges, you can pass through the current one only with the cost stated in to_cost column)
  • to_cost: a cost of restricted passage (can be very high in a case of turn restriction or comparable with an edge cost in a case of traffic light)

source_id: int4 id of the start point

directed: true if the graph is directed

has_reverse_cost: 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.

The function returns a set of rows. There is one row for each crossed edge, and an additional one containing the terminal vertex. The columns of each row are:

  • vertex_id: the identifier of source vertex of each edge. There is one more row after the last edge, which contains the vertex identifier of the target path.
  • edge_id: the identifier of the edge crossed
  • cost: The cost associated to the current edge. It is 0 for the row after the last edge. Thus, the path total cost can be computated using a sum of all rows in the cost column.

Example

Shooting* algorithm calculates a path from edge to edge (not from vertex to vertex). Column vertex_id contains start vertex of an edge from column edge_id.

To describe turn restrictions: 

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14

means that the cost of going from edge 14 to edge 12 is 1000, and 

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  12 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 14, 4

means that the cost of going from edge 14 to edge 12 through edge 4 is 1000.

If you need multiple restrictions for a given edge then you have to add multiple records for that edge each with a separate restriction. For example: 

 gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
-----+--------+--------+------+----+----+----+----+---------+------
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
  11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12

means that the cost of going from either edge 4 or 12 to edge 11 is 1000. And then you always need to order your data by gid when you load it to a shortest path function..

To search a path using the Shooting* algorithm: 

SELECT * FROM shortest_path_shooting_star('SELECT id, source, target, cost, 
         x1, y1, x2, y2, rule, to_cost FROM edges', 17, 9, true, false);

 vertex_id | edge_id | cost
-----------+---------+------
        16 |      17 |    1
        15 |      16 |    1
         2 |       5 |    1
         3 |       4 |    1
        20 |      12 |    2
        10 |       9 |    2
(6 rows)