グラフ/格子簡略化

Question

グラフカットアルゴリズムのデータ構造に取り組んでいます。問題は最短経路で異なるカットを作ることです。私はプロパティについてわからないデータ構造を作った。

入力は、最短経路の有向グラフであり、有界格子であり、最小および最大要素を有する部分的順序集合である。

は次のノードN（n）は、ノードの N個のノードBのための< Bの集合として定義し、< C < Bとはcが存在しません。同様に、前のノードP（n）をと定義します。集合の定義を拡張する.N（S）のnのN（S）の集合であり、P（S）の場合も同様である。

ノードL、N（L）、N（N（L））の集合のリストに対して異なるカットを作ることは容易である...ここで、隣接する各ペアAに対してN（A）= Bマッピングに新しい格子を作成し、この特性を有する

A = A_1 union A_2 
B = B_1 union B_2 
with B_i = N(A_i), A_i = P(B_i) for i=1,2. 

：いいえパーティションが存在しないことを保持する上部隔壁は縁を作成するよりも、発見された場合

• 副格子ノード
• いずれかに（パーティションカーディナリティー番号）。格子のための単純なアルゴリズムで

- >格子マッピングは次のとおりです。

A = {minimum node} 
new_node = [A] 
1: 
while A, N(A) don't have partitions 
    append N(A) to new_node 
    A = N(A) 
for each partition $B_i$ 
    last_new_node = new_node 
    create new_node = [B_i] 
    create edge last_new_node to new_node 
    go to 1 
At the end fix maximum node in new lattice if needed 

このアルゴリズムは、新たな格子上で、繰り返し呼び出すことができます。私は心配しています：

• 1ノードの格子に到達する保証はありますか？
• 1ノードの格子に到達する反復の尺度はありますか？境界は入力グラフの直径です。

同様のデータ構造へのリンクをありがたいです。

TNX

背景：

私が働いていたもので最大フローネットワークの禁止の問題を使用するためのアイデアを持っていました。頂点の数をネットワークから削除して最大のフローを最小限に抑えることができる頂点拘束バージョンについて考えていました。私が取り組んでいたネットワークは、非常に規則的な平面有向グラフ（平面が六角形に分割され、各頂点は6頂点に接続されていました）でした。私はsourceからsinkへの最短経路のみをカット（禁止）したかったのです。有向グラフの簡略化を行うために、aからsinkまでの最短経路にある場合、エッジ(a,b)は単純化されたグラフになります。エッジウェイトが正の場合、簡略化された有向グラフは格子です。これを私が「最短経路の有向グラフ」と呼んでいます。

私は素敵な頂点カット（平行、伝播、...）、より簡単な（非常に構造化された）格子を持っていたいと思っていました。

ネイティブカットは「波」です。 1つの素敵なカットCも良いですN(C)を生成します。そのため、上記の操作で格子を単純化しようとしました。私はカットに興味があり、マッピングに使用される頂点の2つのサブセットを記述しようとしました： - ノードの波 - パラレルセット。 Cが1波の場合、N(C)が別の波です。 - ストライプ - 他のストライプと交差しない一連の波。 C, N(C), N(N(C))。

B1--C1--D1 ... 
/\/\/
A X X 
\/\/\ 
    B2--C2--D2 

Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2} 
Stripe is made of these 4 waves. 

マッピングは、初期格子から新しい格子のノードにストライプをマップします。新しい格子のノードは、波を共有する場合に接続されます。エッジの方向は、最初の波を共有する最後の波を共有するストライプからのものです。

マッピングでは同じプロパティを持つ新しいラティスが生成されるため、ノードが1つのみの格子が存在するまでプロシージャを繰り返すことができます。これは格子の直径が少なくとも1回、各反復で小さくなるために示される。最小のノードMとN(M)が同じストライプにあり、格子の直径が小さくなるためです。

ここで、カットを実行または検索することは再帰的な作業です.1つのノードだけで最後のものより前の格子で開始し、1つの波全体または隣接する波を階段状にカットします。切断されたノードは、それにマップされたサブ格子を取り、そのサブ格子を切断する。初期ラティスに達するまで同じことが行われます。

この構造は、格子圧縮である種のものです。私は動的格子カット検索に使用できると思います。

私の場合、他のいくつかのプロジェクトの制限があるので、私はそれを使用しません。私は最初の問題をほんの数行のコードで簡単に解決しましたが、前にそのようにすることはできませんでした:-)

Answer 1

1ノードの格子に到達する保証はありますか？

私が正しくあなたの擬似コードを理解していれば、何も：それはN -nodeリニアためにn個 -node線形順序を運びません。

私はあなたのコードを部分的な注文を受け入れて、それが合理的に "忠実な"埋め込みを持つseries-parallel partial orderを見つけるものとして記述します。

平面グラフで最大フロー/最小カットを見つけることに興味があれば、O(n log n) algorithmがあります。