ja/ShootingStar

Shooting*アルゴリズムを用いた最短経路探索

shortest_path_shooting_star機能を利用するためには以下の宣言文が必要です: 

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

path_result(探索経路結果)の型: 

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

引数:

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: エッジの識別子[int4]
  • source: 始点ノードの識別子[int4]
  • target: 終点ノードの識別子[int4]
  • cost: エッジにかかる重み(負の重みはエッジがグラフに挿入されることを防ぎます)[float8]
  • reverse_cost (オプション): エッジの反対方向のコスト。この値はdirectedおよびhas_reverse_costパラメータがtrueの場合のみ使用されます。(負のコストについては前述の通りです)
  • directed: 有向グラフの場合はtrueを指定
  • has_reverse_cost: trueの場合、SQLで生成される行セットのreverse_costカラムは、エッジの逆方向にかかる重みとして使用されます。各行のカラム構成は: 関数は行のセットを返します。それぞれの交差しているエッジあたり1行、また終点を含む追加行が1行あります。
  • x1: エッジの始点のx座標[float8]
  • y1: エッジの始点のy座標[float8]
  • x2: エッジの終点のx座標[float8]
  • y2: エッジの終点のy座標[float8]
  • rule: 指定方向外進行禁止の規則を記述する、エッジID毎にカンマで区切られた文字列(これらのエッジに沿って行くならば、to_costカラムで指定された値のコストがかかります)。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: 制限のある通行のコスト(指定方向外通行禁止の場合には非常に高くし、信号機の場合にはエッジのコストに見合う値にします)

source_id: 始点ノードのID[int4]

directed: 有向グラフの場合はtrueを指定

has_reverse_cost: trueの場合、SQLで生成される行セットのreverse_costカラムは、エッジの逆方向にかかる重みとして使用されます。各行のカラム構成は: 関数は行のセットを返します。それぞれの交差しているエッジあたり1行、また終点を含む追加行が1行あります。

関数は行のセットを返します。それぞれの交差しているエッジあたり1行、また終点を含む追加行が1行あります。 各行のカラム構成は:

  • vertex_id: 各エッジの始点ノードIDです。経路探索の終点ノードIDを含む最後のエッジの後に、もう一行あります。(最後のエッジの終点ノードから続くエッジがないことを示すため)
  • edge_id: 交差したエッジのID
  • cost: 現在のエッジに関連付けられたコスト。最後のエッジの場合は0となります。したがって、経路の合計コストはcostカラムの合計となります。

例

Shooting*アルゴリズムは、頂点から頂点ではなく、エッジからエッジへと経路を探索します。vertex_idカラムはedge_idカラムが示すエッジの始点ノードを含みます。

指定方向外進行禁止の記述例: 

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

エッジ14からエッジ12へ行く場合のコストは1000であることを意味します。次は、 

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

エッジ14からエッジ4を経由してエッジ12へ行くためのコストが1000であることを意味します。

Shooting*アルゴリズムを使用した経路探索: 

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)

この日本語訳の著作権は、日本ユニシス株式会社に帰属しています。また、この日本語訳は、GNU FDLのもとで提供されています。