root/branches/workshop/FOSS4G2008/Docs/09_pgrouting.shootingstar.chapter

= pgRouting with Shooting-Star algorithm =

Shooting-Star algorithm is the latest of pgRouting shortest path algorithms.
Its speciality is that it routes from link to link, not from vertex to vertex 
as Dijkstra and A-Star algorithms do.
This makes it possible to define relations between links for example, and it 
solves some other vertex-based algorithm issues like "parallel links", which
have same source and target but different costs.

== Prepare routing table for Shooting-Star ==

For Shooting-Star you need to prepare your network table and add the 
"reverse_cost" and "to_cost" column. Like A-Star this algorithm also has a
heuristic function, which prefers links closer to the target of the search.

{{{
ALTER TABLE ways ADD COLUMN reverse_cost double precision;
UPDATE ways SET reverse_cost = length;
}}}

{{{
ALTER TABLE ways ADD COLUMN to_cost double precision;
ALTER TABLE ways ADD COLUMN rule text;
}}}

== Shortest Path Shooting-Star core function ==

Shooting-Star algorithm introduces two new attributes:
 * 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 a restricted passage (can be very high in a case of turn 
 restriction or comparable with an edge cost in a case of traffic light)

{{{
shortest_path_shooting_star( sql text, 
                   source_id integer, 
                   target_id integer, 
                   directed boolean, 
                   has_reverse_cost boolean ) 
}}}

Note: 
 * Source and target IDs are link IDs.
 * Undirected graphs ("directed false") ignores "has_reverse_cost" setting

=== Example for Shooting-Star "rule" ===

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.
{{{
 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..

=== Example of Shooting-Star core function ===

{{{
SELECT * FROM shortest_path_shooting_star('
                SELECT gid as id, 
                         source::integer,
                         target::integer, 
                         length::double precision as cost, 
                         x1, y1, x2, y2,
                         rule, to_cost 
                        FROM ways', 
                293, 761, false, false); 
}}}

{{{
 vertex_id | edge_id |        cost         
-----------+---------+---------------------
      4232 |     293 |  0.0059596293824534
      3144 |     293 |  0.0059596293824534
      4232 |    4632 |  0.0846731039249787
       ... |     ... |  ...
        51 |     761 |  0.0305298478239596
(63 rows)
}}}

=== Wrapper function WITH bounding box ===

Wrapper functions extend the core functions with transformations, bounding box 
limitations, etc.. 

{{{
SELECT gid, AsText(the_geom) AS the_geom
        FROM shootingstar_sp('ways', 293, 761, 0.1, 'length', true, true);
}}}

{{{
  gid   |                              the_geom      
--------+---------------------------------------------------------------
    293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
    293 | MULTILINESTRING((18.4074149 -33.9443308,18.4074019 -33.9443833))
   4632 | MULTILINESTRING((18.4074149 -33.9443308,18.4077388 -33.9436183))
    ... | ...
    762 | MULTILINESTRING((18.4241422 -33.9179275,18.4237423 -33.9182966))
    761 | MULTILINESTRING((18.4243523 -33.9177154,18.4241422 -33.9179275))
(62 rows)
}}}

Note: 
 * There is currently no wrapper function for A-Star without bounding box,
since bounding boxes are very useful to increase performance. If you don't need
a bounding box Dijkstra will be enough anyway.
 * The projection of OSM data is "degree", so we set a bounding box 
containing start and end vertex plus a 0.1 degree buffer for example.