問題タブ [max-flow]

グラフ G= (V, E) にいくつかの制約があるソース ノード s から宛先ノード t への Max-flow を使用してk (k が指定されている) パスを見つけようとしています。V の異なるサブセット A_i が与えられると、1 つのサブセットは 1 つまたは複数のノードを持つことができます。問題は、1 つのパスでのみ 1 つのサブセットを使用できることです。私はこのコードを使用しています

このコードで各サブセットを追加するにはどうすればよいですか (つまり、パス 1 でサブセット A_1 を使用すると、他のパスに A_1 を再度使用できなくなりますか?私は Java が初めてです。問題をアップロードしようとしました)写真ですが、私はこの面が初めてなのでできませんでした. ありがとう

matlab の頂点の各ペア間の最大フローを見つける方法はありますか?

また

したがって、疎行列を取得して、1 つの頂点から他のすべての頂点への最大フローを取得できます。これを続けて、すべてのペアの最大フローを取得する方法はありますか?

最終的には、有向加重グラフのすべてのペアの最大フローを見つけられるようにしたいと考えています。. .

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

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

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

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

私はいくつかの単純なコンピューター ビジョン アルゴリズムを自分自身に教えようとしており、ノイズで破損した画像があるという問題を解決しようとしています。現在、背景の RGB チャンネルは、ノイズが含まれている可能性があるため、すべてが完全にゼロというわけではありません。ただし、人間の目は前景と背景を簡単に区別できます。

そこで、SLIC アルゴリズムを使用して画像をスーパー ピクセルに分解しました。画像はノイズで破損しているため、パッチで統計を行うと、SNR が高くなるため、背景と前景の分類が向上する可能性があるという考えです。

この後、同様のプロファイルを持つはずの約 100 個のパッチを取得し、SLIC の結果は妥当と思われます。私はグラフ カット (コルモゴロフの論文) について読んでいて、私が抱えている 2 項問題を解決するのに何か良い方法があるように思えました。そこで、一次MRFであるグラフを作成し、すぐ隣同士の間にエッジがあります（4連結グラフ）。

ここで、セグメンテーションを行うためにここで使用できる単項および 2 項の用語を考えていました。したがって、私は単項項について考えていました。背景の平均強度がゼロで、前景の平均がゼロでない単純なガウスとしてモデル化できます。ただし、これをエンコードする方法を理解するのに苦労しています。いくつかのノイズ分散を想定し、パッチ統計を使用して確率を直接計算する必要がありますか?

同様に、隣接するパッチについても、同様のラベルを使用するよう奨励したいのですが、それを反映するように設計できる 2 項用語がわかりません。ラベル（1または0）の違いだけが奇妙に思えます...

長文の質問で申し訳ありません。誰かが開始方法について役立つヒントを提供してくれることを願っています。

プロジェクトの画像でグラフカットアルゴリズムを使用したいのですが、python 2.7を使用しています。pymaxflow の実装
を見つけましたが、ドキュメントはあまり明確ではないようです。私は例を作ります、ここに私の5 * 5行列があります:

仮想ターミナル ノードS (ソース) とT (シンク) は、それぞれ行列の左端と右端の列のすべてのピクセルに無限の重みアークで接続する必要があります。これが私が取得したいものです：

これを取得するための私のコードは次のとおりですが、機能しません

g.maxflow()Python コンソールを無限ループにします。実装についてよくわかりません: グラフ カット アルゴリズムで使用できる正しいグラフを作成する方法は何ですか?

ありがとう！

Ps別のライブラリでの解決策を知っている場合は、教えてください。どんな提案でも大歓迎です。

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

ネットワーク フローがあり、Edmond-Karp アルゴリズムを使用すると、ネットワーク上にすでに最大フローがあるとします。では、任意のエッジ (一定の容量を持つ) をネットワークに追加した場合、最大フローを更新する最良の方法は何ですか? 新しいエッジに関する残差ネットワークを更新し、新しい最大フローが見つかるまで再び拡張パスを探すことを考えていましたが、それが機能するかどうか、またはそれが最善の方法であるかどうかはわかりません!