有向グラフを保存/アクセスする最良の方法

StackOverflow https://stackoverflow.com/questions/191897

質問

フローパスを決定するネットワーク（本質的には有向グラフ）として表現したい約3500の洪水制御施設があります。現在、SqlServerとCTEを使用して、すべてのノードとその上流コンポーネントを再帰的に検査しています。これは、上流パスが分岐しない限り機能します。ただし、一部のクエリは、アップストリームの複雑さが増しているため、パスを物理的にそれほど遠く離れていなくても（つまり、2つまたは3つのセグメント「ダウンストリーム」）、他のクエリよりも指数関数的に長くかかります。場合によっては、クエリを強制終了する前に10分以上待機させました。単純な2列のテーブルを使用しています。1列は施設自体であり、もう1列は最初の列にリストされている施設の上流にある施設です。

現在の機能を使用してインデックスを追加して、速度を上げようとしましたが、違いはありませんでした。そして、グラフ内の可能な接続に関しては、どのノードも複数のアップストリーム接続を持つことができ、複数の「ダウンストリーム」から接続できます。ノード。

データにサイクルが存在する可能性は確かにありますが、これを検証する良い方法をまだ見つけていません（CTEクエリが最大再帰カウントヒットを報告した場合を除き、修正は簡単でした）。

だから、私の質問は、この情報を間違って保存していますか？アップストリームポイントを照会するCTE以外のより良い方法はありますか？

役に立ちましたか？

解決

洪水制御施設については何も知りません。しかし、私は最初の施設を取るでしょう。そして、一時テーブルとwhileループを使用してパスを生成します。

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)



DECLARE @intN INT
SET @intN = 1



INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- Insert first item in list with no up stream items...call this initial condition
  SELECT LastNode, CurrentNode, @intN
  FROM your table
  WHERE node has nothing upstream



WHILE @intN <= 3500
BEGIN
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode, CurrentNode, @intN
      FROM your table
      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)



IF @@ROWCOUNT = 0
     BREAK




 END

すべてのノードが1つの子を指していると仮定した場合。その後、これには3500回以上の反復は必要ありません。複数のノードが同じアップストリームプロバイダーを使用している場合は、時間がかかりません。しかし、もっと重要なことは、これでこれができるということです...

SELECT LastNode、CurrentNode、N TempTableから Nによる並べ替え

これにより、プロバイダーにループやその他の問題があるかどうかを確認できます。ちなみに、3500行はそれほど多くないので、各プロバイダーが異なるアップストリームプロバイダーを指す最悪の場合でも、それほど長くはかかりません。

他のヒント

グラフを保存する最良の方法は、もちろんネイティブのグラフdbを使用することです：-）

neo4j をご覧ください。 Javaで実装されており、PythonおよびRubyバインディングもあります。

neo4jを使用したグラフとして表されるドメインモデルの簡単な例を使用して、2つのwikiページを作成しました。アセンブリおよび役割。その他の例は、ドメインモデリングギャラリーページにあります。

従来、グラフは行列またはベクトルで表されます。マトリックスはより多くのスペースを必要としますが、処理が簡単です（3500x3500エントリの場合）。ベクトルのスペースは少なくて済みます（3500エントリ、それぞれに接続先のリストがあります）。

それはあなたを助けますか？

iデータ構造は良好だと思いますが（SQL Serverの場合）、CTEはクエリにとって最も効率的なソリューションではないかもしれません。代わりに一時テーブルをキューとして使用してグラフを走査するストアドプロシージャを作成してみてください。これはより効率的です。

一時テーブルは、グラフ内のサイクルを削除するためにも使用できますが、存在しないはずです

はい（たぶん）。データセットは比較的小さく聞こえますが、プログラムを想定して、グラフを隣接行列または隣接リストとしてメモリにロードし、グラフを直接クエリすることができます。

オンディスク形式に関しては、 DOT は特に移植性が高く人気があります。また、次のようなフラットファイル形式でエッジのリストを保存することも非常に一般的なようです。

vertex1 vertex2 {edge_label1}+

ファイルの最初の行にグラフ内の頂点の数が含まれ、その後のすべての行はエッジを表します。エッジが有向か無向かは、実装者次第です。明示的な有向エッジが必要な場合は、次のような有向エッジを使用してそれらを記述します。

vertex1 vertex2
vertex2 vertex1

SQL Serverデータベースに記述されているようなものを保存した私の経験：

ポイントAからポイントBに移動するのにかかる時間を示す距離行列を格納していました。単純な表現を行い、A、B、distance、time列の距離と呼ばれるテーブルに直接格納しました。

これは単純な検索では非常に遅いです。マトリックス全体をテキストとして保存する方がはるかに良いことがわかりました。次に、計算の前にメモリに取得し、メモリ内に行列構造を作成して、そこで作業します。

いくつかのコードを提供できますが、C＃になります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top