5.7.6.1 最短パスの例
次の例は、SQLベースの最短パス分析を示しています。
例5-18 最短パスの設定および計算
たとえば、最短パスについて考えます。内部的に、Oracle Databaseは双方向Dijkstraアルゴリズムを使用します。次のコード・スニペットは、準備、実行、およびクリーンアップのワークフロー全体を示しています。
set serveroutput on
DECLARE
wt1 varchar2(100); -- intermediate working tables
n number;
path varchar2(1000);
weights varchar2(1000);
BEGIN
-- prepare
opg_apis.find_sp_prep('connectionsGE$', wt1);
dbms_output.put_line('working table name ' || wt1);
-- compute
opg_apis.find_sp(
'connectionsGE$',
1, -- start vertex ID
53, -- destination vertex ID
wt1, -- working table (for Dijkstra expansion)
dop => 1, -- degree of parallelism
stats_freq=>1000, -- frequency to collect statistics
path_output => path, -- shortest path (a sequence of vertices)
weights_output => weights, -- edge weights
options => null
);
dbms_output.put_line('path ' || path);
dbms_output.put_line('weights ' || weights);
-- cleanup (commented out here; see text after the example)
-- opg_apis.find_sp_cleanup('connectionsGE$', wt1);
END;
/
この例では、次のような出力が生成されます。作業表の名前が指定されていない場合、準備ステップで、自動的に一時表の名前が生成され作成されます。一時作業表の名前にはセッションIDが使用されるので、出力はおそらく異なります。
working table name "CONNECTIONSGE$$TWFS12" path 1 3 52 53 weights 4 3 1 1 1 PL/SQL procedure successfully completed.
作用表の定義を知りたい場合は、クリーンアップ・フェーズをスキップします(find_sp_cleanupへのコールをコメントアウトしている前の例を参照)。計算が実行された後で、作業表を記述できます。
SQL> describe "CONNECTIONSGE$$TWFS12"
Name Null? Type
--------- -------- ----------------------------
NID NUMBER
D2S NUMBER
P2S NUMBER
D2T NUMBER
P2T NUMBER
F NUMBER(38)
B NUMBER(38)
インメモリーや高度な圧縮の使用などの様々な表作成オプションの試行を希望する上級ユーザーの場合、前の作業表を事前に作成して名前を渡すことができます。
例5-19 最短パス:作業表の作成および分析の実行
次の文は、最初に同じ列構造と基本的圧縮を有効にして作業表を作成してからそれをSQLベースの計算に渡す、いくつかの高度なオプションを示しています。このコードは、CREATE TABLE圧縮とインメモリーのオプションを使用して計算用の中間表を最適化します。
create table connections$MY_EXP(
NID NUMBER,
D2S NUMBER,
P2S NUMBER,
D2T NUMBER,
P2T NUMBER,
F NUMBER(38),
B NUMBER(38)
) compress nologging;
DECLARE
wt1 varchar2(100) := 'connections$MY_EXP';
n number;
path varchar2(1000);
weights varchar2(1000);
BEGIN
dbms_output.put_line('working table name ' || wt1);
-- compute
opg_apis.find_sp(
'connectionsGE$',
1,
53,
wt1,
dop => 1,
stats_freq=>1000,
path_output => path,
weights_output => weights,
options => null
);
dbms_output.put_line('path ' || path);
dbms_output.put_line('weights ' || weights);
-- cleanup
-- opg_apis.find_sp_cleanup('connectionsGE$', wt1);
END;
/
計算の終了時に、作業表が削除または切り捨てられていない場合は、次のように作業表の内容をチェックできます。作業表の構造はリリース間で異なる可能性があることに注意してください。
SQL> select * from connections$MY_EXP;
NID D2S P2S D2T P2T F B
---------- ---------- ---------- ---------- ---------- ---------- ----------
1 0 1.000E+100 1 -1
53 1.000E+100 0 -1 1
54 1.000E+100 1 53 -1 1
52 1.000E+100 1 53 -1 1
5 1 1 1.000E+100 0 -1
26 1 1 1.000E+100 0 -1
8 1000 1 1.000E+100 0 -1
3 1 1 2 52 0 0
15 1 1 1.000E+100 0 -1
21 1 1 1.000E+100 0 -1
19 1 1 1.000E+100 0 -1
...
例5-20 最短パス:同じグラフへの複数コールの実行
同じグラフへの複数のコールを実行するには、準備ステップへの1つのコールだけが必要です。次に、同じグラフ内で複数の頂点のペアの最短パスを計算する例を示します。
DECLARE
wt1 varchar2(100); -- intermediate working tables
n number;
path varchar2(1000);
weights varchar2(1000);
BEGIN
-- prepare
opg_apis.find_sp_prep('connectionsGE$', wt1);
dbms_output.put_line('working table name ' || wt1);
-- find shortest path from vertex 1 to vertex 53
opg_apis.find_sp( 'connectionsGE$', 1, 53,
wt1, dop => 1, stats_freq=>1000, path_output => path, weights_output => weights, options => null);
dbms_output.put_line('path ' || path);
dbms_output.put_line('weights ' || weights);
-- find shortest path from vertex 2 to vertex 36
opg_apis.find_sp( 'connectionsGE$', 2, 36,
wt1, dop => 1, stats_freq=>1000, path_output => path, weights_output => weights, options => null);
dbms_output.put_line('path ' || path);
dbms_output.put_line('weights ' || weights);
-- find shortest path from vertex 30 to vertex 4
opg_apis.find_sp( 'connectionsGE$', 30, 4,
wt1, dop => 1, stats_freq=>1000, path_output => path, weights_output => weights, options => null);
dbms_output.put_line('path ' || path);
dbms_output.put_line('weights ' || weights);
-- cleanup
opg_apis.find_sp_cleanup('connectionsGE$', wt1);
END;
/
この例の出力は次のようになります。指定した頂点の複数のペアに対し、3つの最短パスが見つかりました。
working table name "CONNECTIONSGE$$TWFS12" path 1 3 52 53 weights 4 3 1 1 1 path 2 36 weights 2 1 1 path 30 21 1 4 weights 4 3 1 1 1 PL/SQL procedure successfully completed.
親トピック: SQLベース・プロパティ・グラフ分析