約 100 万のノードと 1,000 万を超えるエッジを持つ巨大な有向グラフがあります。エッジは重み付けされていません。グラフは小さな世界のようなグラフです。実際、すべてのノードが (平均して) 3 つの中間ノードを介して別のノードに接続されていることがわかります。
このグラフを考えると、開始ノードと宛先ノードの間のすべてのパス (サイクルなし) を返す高速アルゴリズムを考えることができますが、指定された最大数 N の中間ノードまでしか返されません (私の場合、ほとんどの場合 N は0 から 3 の間)?
グラフが無向の場合、双方向の幅優先検索を実行する必要があります。長さ 2 のパスの場合、開始ノードと終了ノードからエッジを列挙し、交差する場所を確認します。長さ 3 のパスの場合、次数の小さい終点から 2 深さ、次数の大きいノードの 1 深さまで進みます。
グラフは有向であるため、同じトリックを実行できるように逆エッジも保持する必要がある場合があります。
おそらく、一度に両方の方向から息をのむように？A の隣人、および B の隣人を取ります。まだリンクが見つからない場合は、A を「a の隣人」に追加し、B を「B の隣人」に追加してから、2 つのセット間のリンクを見つけます。
3 つのリンクよりも少し拡張するには、「A/B の近隣」リストにもう少し多くのリンクを含める必要があります。インメモリで行うことはできません-スクラッチテーブルが必要です
whatever TRANSACTION_ID; (or use an ORACLE 1-per-session temp table)
boolean MY_BFS_WAS_ROOTED_AT_A;
int NODE_ID;
int previous_node_id;
(挿入ステートメントでループをチェックする場合は、深さを追跡する必要はありません)
パスが存在する場合、パスを見つけたことになります。
select from pathfinder a, pathfinder b
where a.taxn_id = foo and b.tnx_id=foo
and a.MY_BFS_WAS_ROOTED_AT_A = false
and b.MY_BFS_WAS_ROOTED_AT_A = true
and a.node_id = b.node_id
終わったら、テーブルをきれいにすることを忘れないでください！すべてを 1 つのトランザクションとして実行し、ロールバックするのが最も簡単な方法かもしれません。