Semplificazione grafico/reticolare

Question

Sto lavorando sulla struttura dei dati per l'algoritmo di taglio grafico. Il problema è fare tagli diversi sui percorsi più brevi. Ho creato una struttura dati per la quale non sono sicuro delle proprietà.

L'input è il grafico diretto dei percorsi più brevi, che è reticolo limitato, parzialmente ordinato impostato con l'elemento minimo e massimo.

Definire nodo successivo N (n) del nodo n come un insieme di nodi b per cui un < b e non c'è c con un < c < b. Definizione simile nodo precedente P (n). Estendere le definizioni sui set, unione N (S) di N (n) per n in S, simile per P (S).

È facile eseguire diversi tagli nell'elenco di set di nodi L, N (L), N (N (L)), ... dove per ciascuna coppia di gruppi vicini A, N (A) = B sostiene che non v'è nessuna partizione:

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. 

con questa proprietà creare nuova lattice con la mappatura:

• sub-reticolo a un nodo
• se la partizione superiore è trovato che creare bordi (numero cardinalità di partizione).

In semplice, algoritmo per lattice -> mappatura reticolo è:

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 

Questo algoritmo può essere chiamato più volte sui nuovi reticoli. Sono preoccupato per:

• Esiste la garanzia di raggiungere un reticolo a un nodo?
• Esiste una misura del numero di iterazioni per raggiungere il reticolo di un nodo? Mi sembra che il limite sia il diametro del grafico di input.

Apprezzo il collegamento a qualsiasi struttura di dati simile.

Tnx

Background:

Ho avuto l'idea di utilizzare rete Portata massima problema interdizione in cose su cui stavo lavorando. Stavo pensando alla versione di interdizione dei vertici in cui un determinato numero di vertici può essere rimosso dalla rete per ridurre al minimo il flusso massimo. La rete su cui stavo lavorando era un grafico diretto planare molto regolare (piano diviso in esagoni, ciascun vertice è collegato a 6 vertici). Volevo tagliare (interdetto) solo i percorsi più brevi da source a sink. Per fare ciò ho usato la semplificazione del grafico diretto, il bordo (a,b) si trova nel grafico semplificato se si trova sul percorso più breve da a a sink. Se il peso del fronte è positivo, il grafico diretto semplificato è reticolo. Questo è ciò che ho chiamato "grafico diretto dei percorsi più brevi".

Volevo avere tagli di vertici che siano belli (paralleli, di propagazione, ...), cosa è più semplice su un reticolo (molto strutturato).

I tagli nativi sono "onde", ad es. un bel taglio C produce anche N(C) che è bello.Per questo motivo ho cercato di semplificare il reticolo con le operazioni descritte sopra. Ho provato a descrivere 2 sottoinsiemi di vertici che sono interessanti per i tagli e utilizzati nella mappatura: - wave - serie di nodi paralleli. Se C è un'onda, allora la N(C) è un'altra. - stripe - serie di onde senza intersezione con altre strisce. 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. 

Mappatura delle mappe striscia dal reticolo iniziale al nodo del nuovo reticolo. I nodi nel nuovo reticolo sono connessi se condividono l'onda. La direzione del bordo proviene da strisce che condividono l'ultima onda con le strisce che condividono la prima ondata.

Poiché la mappatura produce un nuovo reticolo con le stesse proprietà, la procedura può essere ripetuta finché non c'è un reticolo con un solo nodo. Questo può essere mostrato perché il diametro del reticolo è più piccolo, almeno per 1, con ogni iterazione. Questo perché i nodi minimi M e N(M) sono nella stessa striscia e questo riduce il diametro del reticolo.

Ora, eseguire o cercare i tagli è un'attività ricorsiva, iniziare con reticolo uno prima dell'ultimo con un solo nodo e tagliare su un'onda intera o su onde vicine in scala. Per i nodi in cut prendi il sub-lattice che è mappato in esso e fai il taglio su quel sub-reticolo. Lo stesso è fatto fino a raggiungere il reticolo iniziale.

Questa struttura è di qualche tipo sulla compressione del reticolo. Penso che possa essere usato per la ricerca di tagli reticolari dinamici.

Nel mio caso, non lo utilizzo poiché alcune altre restrizioni del progetto. Ho risolto il problema iniziale in modo molto semplice con solo poche righe di codice, ma non mi ero reso conto che è possibile farlo prima :-)

Answer 1

Esiste una garanzia per raggiungere un reticolo di un nodo?

Se ho capito bene il vostro pseudocodice, no: si porta un ordine lineare -node n a un ordine lineare -node n.

Descriverei il tuo codice come se accettassi un ordine parziale e trovassi uno series-parallel partial order in cui ha un'incorporazione ragionevolmente "fedele".

Se sei solo interessato a trovare i flussi massimi/min tagli nei grafici planari, c'è uno O(n log n) algorithm per quello.