グラフ - 再帰における最短経路

Question

ノードxからノードyまでのエッジを含むテーブルがあります。私は（マテリアライズ）を作成したい

n1 | n2 
------- 
a | a 
a | b 
a | c 
b | b 
b | d 
b | c 
d | e 

ノードの最短の数を示す図で/パスホップYノードするXから到達するために含まれていますどのようにすべき

n1 | n2 | c 
----------- 
a | a | 0 
a | b | 1 
a | c | 1 
a | d | 2 
a | e | 3 
b | b | 0 
b | d | 1 
b | c | 1 
b | e | 2 
d | e | 1 

をこれを容易にするためにテーブルとビューをモデル化しますか？私は再帰のいくつかの種類が必要だと思うが、私はかなりSQLで達成することは困難だと思う。パスが10ノード/ホップを含む場合、クライアントが10クエリを実行する必要があるということを避けたいと思います。

Answer 1

むしろその場でこれらの値を計算するよりも、なぜ最短パス値と一緒にすべての興味深いペアで実際のテーブルを作成していません。その後、データテーブルにデータが挿入、削除、または更新されるたびに、最短パス情報をすべて再計算できます。 （PerlのGraphモジュールはこの作業に特に適しており、PerlのDBIインターフェイスでコードが簡単になります）。

再計算の回数を制限することもできます。 PostgreSQLのトリガーを使用すると、再計算がすべての挿入時に発生させ、更新、削除、しかし、あなたはポイントの20組を追加するつもりだった知っていたならば、あなたのインサートが計算を実行する前に完了したまで、あなたは待つことができるでしょう。

Answer 2

これは私のために動作しますが、それはちょっと醜いです：

WITH RECURSIVE paths (n1, n2, distance) AS (
    SELECT 
     nodes.n1, 
     nodes.n2, 
     1 
    FROM 
     nodes 
    WHERE 
     nodes.n1 <> nodes.n2 

    UNION ALL 

    SELECT 
     paths.n1, 
     nodes.n2, 
     paths.distance + 1 
    FROM 
     paths 
     JOIN nodes 
     ON 
      paths.n2 = nodes.n1 
    WHERE 
     nodes.n1 <> nodes.n2 
) 
SELECT 
    paths.n1, 
    paths.n2, 
    min(distance) 
FROM 
    paths 
GROUP BY 
    1, 2 

UNION 

SELECT 
    nodes.n1, 
    nodes.n2, 
    0 
FROM 
    nodes 
WHERE 
    nodes.n1 = nodes.n2 

はまた、私はそれがより大きなデータセットに対して実行されますどのように良いことを確認していません。 Mark Mannの示唆しているように、代わりにグラフライブラリを使用することができます。 pygraph。

編集：ここでグラフの構築時間を除くpygraph

from pygraph.algorithms.minmax import shortest_path 
from pygraph.classes.digraph import digraph 


g = digraph() 

g.add_node('a') 
g.add_node('b') 
g.add_node('c') 
g.add_node('d') 
g.add_node('e') 

g.add_edge(('a', 'a')) 
g.add_edge(('a', 'b')) 
g.add_edge(('a', 'c')) 
g.add_edge(('b', 'b')) 
g.add_edge(('b', 'd')) 
g.add_edge(('b', 'c')) 
g.add_edge(('d', 'e')) 

for source in g.nodes(): 
    tree, distances = shortest_path(g, source) 
    for target, distance in distances.iteritems(): 
     if distance == 0 and not g.has_edge((source, target)): 
      continue 
     print source, target, distance 

とサンプルがありますSQLのバージョンは0.5ミリ秒を要しながら、これは0.3msかかります。マークの答えに拡大

Answer 3

、同様SQLのグラフを探索するいくつかの非常に合理的なアプローチがあります。実際に、彼らはそのDBにインデックスがあなたのグラフを探索する必要性を惜しまます、PerlやPythonでは、専用のライブラリよりも速くなります。

（グラフは常に変化していない場合）、インデックスの最も効率的ではGRIPP indexと呼ばれる、ネストされたツリーのバリエーションです。

グラフが常に変化している場合は、GRIPPがネストしたセットを拡張するのと同様の方法で、グラフにnested intervalsアプローチを適用するか、単純に整数の代わりに浮動小数点を使用することができます（数値にキャストして浮動小数点に戻して正規化することを忘れないでください）。