問題タブ [push-relabel]

CLRS から次の補題を理解するのが困難です。

G をフロー ネットワーク、s と t をソース ノードとシンク ノード、f を s から t へのプリフロー、h を G の高さ関数とします。この場合、残差グラフ G _fには s から t への拡張パスはありません。 .

どうしてこれなの？

push-relabel FIFO コードの MATLAB バージョンを実行しました (wikipedia のものとまったく同じで、試してみました。放電関数は wikipedia とまったく同じです。

これは、小さなグラフ (ノード数 = 7 など) に最適です。ただし、グラフのサイズを大きくすると (つまり、ノード/頂点の数 > 3500 以上)、「ディスチャージ」関数で呼び出される「再ラベル付け」関数の実行が非常に遅くなります。グラフが巨大 (つまり > 3000 ノード) であるため、コードを最適化する必要があります。

グローバルな再ラベル付け/ギャップの再ラベル付けに関する WIKIPEDIA の提案に従って、コードを最適化しようとしました。2) ギャップヒューリスティックを使用します。

私は最初のもので立ち往生しています。詳細が省略されているように見えるので、正確に何をしなければならないのかわかりません。(頂点 u の場合、u に接続されたノード v(1..n) が既に隣接リストにあるように隣接リストを作成しましたが、見た [u] インデックスで反復する方法がわからないだけです)。

AND 放電関数は、「s」近傍構造体リストを使用します。

while (excess(u) > 0) %現在のノードの超過が >0 かどうかをテストし、そうであれば...

終わり

誰かが私を指示したり、見せたり、助けてくれませんか?

push relabel を使用してギャップヒューリスティックを実装する方法がわかりません。Wiki では次のように説明されています。

「ギャップ再ラベル付けヒューリスティックでは、サイズ n の配列 A を維持し、A[i] に各ラベルのノード数 (n まで) を保持します。A[d] = 0 のようなラベル d が見つかった場合、ラベル > d を持つすべてのノードは、ラベル n に再ラベル付けされます。"

ギャップヒューリスティックを使用します。ノードの高さ (u) = k がないような「k」がある場合、ソースを除くすべてのノードに対して高さ (u) = max(高さ (u)、高さ (ソース) +1) を設定できます。 (u) >k. これは、そのような 'k' がグラフの最小カットを表し、ノード S={u where height(u) > k} から T={v, where height(v) のノードにフローが移動しないためです。 0. しかし、その後は height(u) > height(v)+1 となり、height(u) > k および height(v) < k と矛盾します。

wikiのサンプルコードに示されているように、FIFOプッシュリラベルにギャップヒューリスティックを追加する方法を疑似コードで説明してもらえますか?

ありがとう、ヴィンス

私は、一般的なグラフのグラフカットを解決するために、ゴールドバーグのプッシュと再ラベル付け、または preflow-push 、 preflow-relabel を行うオープンソースコードを見つけようとしています。

CUDA には npp GrabCut 2D サンプル コードがあることを知っています。また、すべてのピクセルがノードとして扱われる場合、nppiGraphCut() が 2D 平面のグラフカットを解決することも知っています。ただし、次のグラフ入力が与えられた場合に解決するものが必要です。

ソース、シンク、ノード数、ノードからノードへ、フォワード アークの重み (ノードからノードへ) バックワード アークの重み (ノードからノードへ) ソースの重み (ソースから非ターミナル ノードへの容量) シンクの重み (非ターミナル ノードへの容量)容量をシンクする端末ノード)

ソースがsourceWeightsでノード<1><2><3>に接続し、ノード<1><2><3>がsinkWeightsでシンクノードに接続する次のグラフがこのように与えられるように、私はこれをmatlabに持っています。同様に、容量間にノードがありますが、一方向にしか接続されていません (つまり、逆容量は 0 です)。

<1> -> <2> -> <3> -> <4> -> <5> -> <6> ...

これを nppGraphCut で 1D 配列 (<1><2><3>) として使用してグラフ カットを実行できますか?

トップコーダー サイトからプッシュ再ラベル アルゴリズムを学習していました: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel 実装に何か問題があると思います。ノードが飽和したときに、ノードはどのようにして過剰なフローをノードに押し戻すことができますか。例えば：

1 から 3 までの最大フローを見つけながら、ある段階でフローを 2 から 1 に戻す必要があります (2 には出力エッジがないため)。しかし、先入れ先出しアルゴリズムのコード実装では、16行目のループが から実行され0 to G[u].size()ます。2 には 2 から 1 へのエッジがないため、フローを 1 に戻すにはどうすればよいでしょうか?

必要に応じて、私のくだらない実装を次に示します。

私はこのコードを理解しようとしています。これは、C++ での push-relabel アルゴリズムの実装です。

コードはコンパイルされて機能しますが、入力を渡す方法がわかりません。理想的には、main()関数はソースとシンク (どちらにしても「虚数」であり、アルゴリズムが機能するためにのみ必要です) を読み取り、次に でグラフを作成するために必要なすべてのデータを読み取る必要がありますAddEdge()。しかし、それを行う方法は現在私を超えています。

私main()はこのように見えるはずです

いくつかの ssourceを初期化するために使用する必要があり、いくつかの sEdge.fromと似ているはずですが、グラフを作成する方法がわかりません。sinkEdge.to

最大フローの最上位ラベル プッシュ再ラベル アルゴリズムの第 1 フェーズを実装しましたが、第 2 フェーズの実装方法、つまりプリフロー プッシュ ネットワークを有効なフロー ネットワークに変換する方法に関するリソースが見つかりませんでした。

最大フローを見つけるためにboostライブラリを使用しています（push relabel）。データを読み取るファイルread_dimacs.hppがありますが、標準入力です。問題は、データ ファイルが大きすぎるため、ファイルから直接データ ファイルを読み取りたいことです。誰でも私を助けることができます.コードは以下です