Graf/uproszczenie siatki graficznej

Question

Pracuję nad strukturą danych dla algorytmu cięcia wykresów. Problem polega na tym, aby wykonać różne cięcia na najkrótszych ścieżkach. Zrobiłem strukturę danych, dla której nie jestem pewien właściwości.

Wejście jest skierowanym wykresem najkrótszych ścieżek, które są ograniczone siatką, częściowo uporządkowany zestaw z elementem minimalnym i maksymalnym.

zdefiniować następnego węzła N (n) węzła N, jako zestaw punktów węzłowych B, dla których < B i C nie ma z < C < b. Podobne zdefiniuj poprzedni węzeł P (n). Rozszerz definicje na zbiorach, N (S) unii N (n) dla n w S, podobnie dla P (S).

Łatwo wykonać różne cięcia na liście zestawów węzłów L, N (L), N (N (L)), ... gdzie dla każdej sąsiedniej pary zestawów A, N (A) = B utrzymuje, że nie ma partycji:

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. 

z tej posiadłości utworzyć nową siatkę z mapowaniem:

• sub-krata do jednego węzła
• jeśli górna przegroda znajduje niż tworzyć krawędzie (numer liczność partycji).

W prosty algorytm do kraty -> Mapowanie kratownica jest:

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 

Ten algorytm może być wielokrotnie wzywała nowych krat. Obawiam się:

• Czy istnieje gwarancja osiągnięcia sieci z jednym węzłem?
• Czy istnieje jakakolwiek miara liczby iteracji w celu uzyskania sieci z jednym węzłem? Szewuje mi, że granica jest średnicą wykresu wejściowego.

Cenię link do dowolnej podobnej struktury danych.

Tnx

Tło:

miałem pomysł, aby użyć Maksymalny przepływ sieciowy Interdiction problemu w rzeczy byłem w pracy. Myślałem o wersji z zakazem wierzchołków, w której dana liczba wierzchołków może zostać usunięta z sieci, aby zminimalizować maksymalny przepływ. Sieć, nad którą pracowałem, była bardzo regularnym grafem skierowanym na płaszczyznę (płaszczyzna podzielona na sześciokąty, każdy wierzchołek jest połączony z 6 wierzchołkami). Chciałem przeciąć (interdyktować) tylko najkrótsze ścieżki od source do sink. Aby to zrobić, użyłem uproszczenia grafu skierowanego, krawędź (a,b) znajduje się w uproszczonym wykresie, jeśli znajduje się na najkrótszej ścieżce od a do sink. Jeśli grubość krawędzi jest dodatnia, to uproszczony kierowany wykres to siatka. To właśnie nazwałem "ukierunkowanym wykresem najkrótszych ścieżek".

Chciałem mieć ciąć wierzchołki, które są ładne (równoległe, propagacyjne, ...), co jest łatwiejsze na (bardzo uporządkowanej) sieci.

Cięcia rodzime to "fale", np. jeden miły krój C również produkuje N(C) co jest miłe.Z tego powodu próbowałem uprościć sieć za pomocą operacji opisanych powyżej. Próbowałem opisać 2 podzbiory wierzchołków, które są interesujące dla cięć i użyte w mapowaniu: - wave - równoległy zestaw węzłów. Jeśli C jest jedną falą, to inną jest N(C). - pasek - seria fal bez przecięć z innymi paskami. 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. 

Mapowanie odwzorowuje pasek od początkowej siatki do węzła nowej sieci. Węzły w nowej sieci są połączone, jeśli mają wspólną falę. Kierunek krawędzi pochodzi od paska dzielącego ostatnią falę na pasek, który dzieli pierwszą falę.

Ponieważ mapowanie tworzy nową siatkę o tych samych właściwościach, procedurę można powtarzać do momentu, aż pojawi się krata z tylko jednym węzłem. Można to pokazać, ponieważ średnica kraty jest mniejsza, co najmniej 1, przy każdej iteracji. Jest tak dlatego, że minimalny węzeł M i N(M) jest w tym samym pasku, co zmniejsza średnicę sieci.

Teraz wykonywanie lub wyszukiwanie cięć jest zadaniem rekursywnym, rozpoczynaj od kratownicy jednej przed ostatnią za pomocą tylko jednego węzła i wykonuj cięcie na całej fali lub na sąsiednich falach w sposób schodowy. Dla węzłów w przekroju przyjmij podsieci, która jest w nim odwzorowana, i dokonaj cięcia tej podsieci. To samo robi się aż do osiągnięcia początkowej sieci.

Ta struktura jest czymś w rodzaju kompresji sieci. Myślę, że można go użyć do dynamicznego wyszukiwania cięć w kratach.

W moim przypadku nie używam go od innych ograniczeń projektu. Rozwiązałem początkowy problem bardzo prosto z tylko kilkoma liniami kodu, ale nie zdawałem sobie sprawy, że może to być zrobione wcześniej :-)

Answer 1

Czy istnieje gwarancja osiągnięcia sieci z jednym węzłem?

Jeśli Rozumiem Pseudokod poprawnie, nie: to niesie n -node liniowy porządek do n -node liniowym porządku.

Opisałbym twój kod jako akceptujący zamówienie częściowe i znajdujący series-parallel partial order, w którym ma on rozsądnie "wierne" osadzenie.

Jeśli interesuje Cię tylko wyszukiwanie maksymalnych przepływów/minów na wykresach planarnych, do tego jest O(n log n) algorithm.