[Algorithm] グラフ/格子簡略化


Answers

Question

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

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

ノードnの次のノードN(n)を、a <bでa <c <bのcが存在しないノードbの集合として定義する。 同様に、 前のノード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.

このプロパティを使用すると、マッピングで新しい格子を作成できます。

  • 1つのノードにサブ格子
  • (パーティションカーディナリティ番号)より上位のパーティションが見つかった場合

簡単には、lattice - > lattice mappingのアルゴリズムは次のようになります。

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までの最短経路だけを切り詰めたい(阻止したい)。 有向グラフの簡略化を行うために、edge (a,b)aからsinkへの最短経路にある場合は単純グラフになります。 エッジウェイトが正の場合、簡略化された有向グラフは格子です。 これを私が「最短経路の有向グラフ」と呼んでいます。

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

ネイティブカットは「波」です。たとえば、素敵なカット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回、各反復で小さくなるために示される。 これは、最小のノードMN(M)が同じストライプにあり、格子の直径が小さくなるからです。

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

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

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