Classificazione del bordo durante la ricerca di ampiezza su un grafico diretto

Question

Ho difficoltà a trovare un modo per classificare correttamente i bordi mentre una ricerca in ampiezza su un grafico diretto.

Durante una breadth-first o in profondità di ricerca, è possibile classificare i bordi sono incontrati con 4 classi:

• ALBERO
• INDIETRO
• CROSS
• AVANTI

Skiena [1] dà un'implementazione. Se ti sposti lungo un bordo da v1 a v2, ecco un modo per restituire la classe durante un DFS in java, come riferimento. La mappa dei genitori restituisce il vertice padre per la ricerca corrente e il metodo timeOf(), l'ora in cui il vertice è stato scoperto.

if (v1.equals(parents.get(v2))) { return EdgeClass.TREE; } 
    if (discovered.contains(v2) && !processed.contains(v2)) { return EdgeClass.BACK; } 
    if (processed.contains(v2)) 
    { 
     if (timeOf(v1) < timeOf(v2)) 
     { 
      return EdgeClass.FORWARD; 
     } 
     else 
     { 
      return EdgeClass.CROSS; 
     } 
    } 
    return EdgeClass.UNCLASSIFIED; 

Il mio problema è che non riesco a farlo bene per un ricerca in ampiezza su un grafo orientato. Per esempio:

Il grafico - che è un loop - è ok:

A -> B 
A -> C 
B -> C 

BFSing da A, B sarà scoperta, poi C. I bordi EAB e PAO sono archi d'albero, e quando eBC viene incrociato per ultimo, B e C vengono elaborati e scoperti e questo margine è correttamente classificato come CROCE.

Ma un ciclo semplice non funziona:

A -> B 
B -> C 
C -> A 

Quando il bordo ECA è attraversato ultimo, A viene elaborato e scoperto. Quindi questo bordo è etichettato erroneamente come CROCE, se dovrebbe essere un bordo posteriore.

Non c'è davvero alcuna differenza nel modo in cui i due casi vengono trattati, anche se i due bordi hanno classi diverse.

Come si implementa una corretta classificazione dei bordi per un BFS su un grafico diretto?

[1] http://www.algorist.com/

---

EDIT

Ecco un'implementazione derivato da @redtuna risposta. Ho appena aggiunto un controllo per non recuperare il genitore della radice. devo JUnits prove che dimostrano funziona per grafi orientati e non orientati, nel caso di un ciclo, una linea retta, una forchetta, un esempio standard, un singolo bordo, ecc ....

@Override 
public EdgeClass edgeClass(final V from, final V to) 
{ 
    if (!discovered.contains(to)) { return EdgeClass.TREE; } 

    int toDepth = depths.get(to); 
    int fromDepth = depths.get(from); 

    V b = to; 
    while (toDepth > 0 && fromDepth < toDepth) 
    { 
     b = parents.get(b); 
     toDepth = depths.get(b); 
    } 

    V a = from; 
    while (fromDepth > 0 && toDepth < fromDepth) 
    { 
     a = parents.get(a); 
     fromDepth = depths.get(a); 
    } 

    if (a.equals(b)) 
    { 
     return EdgeClass.BACK; 
    } 
    else 
    { 
     return EdgeClass.CROSS; 
    } 

} 

Answer 1

Come si implementa una corretta classificazione dei bordi per un BFS su un grafico diretto ?

Come già stabilito, la visualizzazione di un nodo per la prima volta crea un margine dell'albero. Il problema con BFS al posto di DFS, come ha detto David Eisenstat prima di me, è che i bordi posteriori non possono essere distinti da quelli incrociati solo in base all'ordine di attraversamento.

Invece, è necessario fare un po 'di lavoro extra per distinguerli. La chiave, come vedrai, è quella di usare la definizione di un cross-edge.

Il modo più semplice (ma a uso intensivo di memoria) è associare ogni nodo con il set dei suoi predecessori. Questo può essere banalmente quando si visitano i nodi. Quando si trova un margine non albero tra i nodi a e b, si considerino i rispettivi set predecessori. Se uno è un sottoinsieme appropriato dell'altro, allora hai un margine posteriore. Altrimenti, è un vantaggio. Questo deriva direttamente dalla definizione di un cross-edge: è un confine tra i nodi in cui né l'antenato né il discendente dell'altro sono sull'albero.

Un modo migliore è associare solo un numero "profondità" a ciascun nodo anziché a un set. Di nuovo, questo è fatto prontamente mentre visiti i nodi. Ora quando trovi un margine non albero tra a e b, inizia dal più profondo dei due nodi e segui i bordi dell'albero all'indietro finché non torni alla stessa profondità dell'altro. Quindi per esempio supponiamo che fosse più profondo. Quindi calcoli ripetutamente a = parent (a) fino a depth (a) = depth (b).

Se a questo punto a = b, allora è possibile classificare il bordo come un bordo posteriore poiché, come per la definizione, uno dei nodi è un antenato dell'altro sull'albero. Altrimenti puoi classificarlo come un cross-edge perché sappiamo che nessuno dei due nodi è un antenato o un discendente dell'altro.

pseudocodice:

foreach edge(a,b) in BFS order: 
    if !b.known then: 
     b.known = true 
     b.depth = a.depth+1 
     edge type is TREE 
     continue to next edge 
    while (b.depth > a.depth): b=parent(b) 
    while (a.depth > b.depth): a=parent(a) 
    if a==b then: 
     edge type is BACK 
    else: 
     edge type is CROSS 

Answer 2

L' la proprietà chiave di DFS è che, dato due nodi u e v, l'intervallo [u.discovered, u.processed] è un sottointervallo di [v.discovered, v.processed] se e solo se u è un discendente di v. I tempi in BFS non hanno questa proprietà; devi fare qualcos'altro, ad es. calcolare gli intervalli tramite DFS nell'albero prodotto da BFS. Quindi lo pseudocodice di classificazione è 1. controllare l'appartenenza all'albero (margine dell'albero) 2. controllare che l'intervallo della testa contenga la coda (bordo posteriore) 3. controllare che l'intervallo della coda contenga la testa (bordo in avanti) 4. altrimenti, dichiarare un bordo incrociato.

Answer 3

Invece di timeof(), avete bisogno di un altro bene vertice, che contiene la distanza dalla radice. Lascia che il nome sia distance.

Devi elaborazione un vertice v nel seguente modo:

for (v0 in v.neighbours) { 
    if (!v0.discovered) { 
     v0.discovered = true; 
     v0.parent = v; 
     v0.distance = v.distance + 1; 
    } 
} 
v.processed = true; 

Dopo aver elaborato un vertice un vertice v, è possibile eseguire il seguente algoritmo per ogni bordo (v1-v2) del v :

if (!v1.discovered) return EdgeClass.BACK; 
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS; 
else if (v1.distance > v2.distance) return EdgeClass.BACK; 
else { 
    if (v2.parent == v1) return EdgeClass.TREE; 
    else return EdgeClass.FORWARD; 
}