Kantenklassifikation während der Breite-zuerst-Suche auf einem gerichteten Graph

Question

Ich habe Schwierigkeiten, einen Weg zu finden, um die Kanten richtig zu klassifizieren, während eine Breitensuche in einem gerichteten Graphen durchgeführt wird.

• TREE
• BACK
• CROSS

FORWARD:

Während einer Breiten ersten oder Tiefensuche, können Sie die Ränder mit 4 Klassen erfüllt klassifizieren Skiena [1] gibt eine Implementierung. Wenn Sie sich entlang einer Kante von v1 nach v2 bewegen, können Sie die Klasse während eines DFS in Java als Referenz zurückgeben. Die Eltern-Map gibt den übergeordneten Vertex für die aktuelle Suche und die timeOf()-Methode den Zeitpunkt zurück, zu dem der Vertex erkannt wurde.

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; 

Mein Problem ist, dass ich es nicht richtig für einen Breitensuche auf einem gerichteten Graphen erhalten können. Zum Beispiel:

Das folgende Diagramm - dass eine Schleife - ist ok:

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

BFSing von A, B wird festgestellt werden, dann C. Die Kanten EAB und eAC sind TREE Kanten und wenn eBC wird zuletzt überquert, B und C werden verarbeitet und entdeckt, und diese Kante wird korrekt als CROSS klassifiziert.

Aber eine einfache Schleife funktioniert nicht:

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

Wenn der Rand eCA letzten gekreuzt wird, wird verarbeitet und A entdeckt. Diese Kante wird also fälschlicherweise als CROSS bezeichnet, unabhängig davon, ob es sich um eine BACK-Kante handelt.

Es gibt tatsächlich keinen Unterschied in der Art, wie die beiden Fälle behandelt werden, selbst wenn die beiden Kanten unterschiedliche Klassen haben.

Wie implementieren Sie eine geeignete Kantenklassifizierung für ein BFS auf einem gerichteten Graphen?

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

---

EDIT

Hier eine Implementierung von @redtuna Antwort abgeleitet. Ich habe gerade einen Check hinzugefügt, um den Eltern des Stammes nicht zu holen. Ich habe JUnits Tests, die es für gerichtete und ungerichtete Graphen, in dem Fall einer Schleife zeigen arbeitet, wird eine gerade Linie, eine Gabel, ein Standard beispielsweise eine einzige Kante, etc ....

@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

Wie implementieren Sie eine geeignete Kantenklassifizierung für ein BFS auf einem gerichteten Graphen?

Wie Sie bereits festgestellt haben, erstellt ein Knoten zum ersten Mal eine Baumkante. Das Problem mit BFS anstelle von DFS, wie David Eisenstat vor mir sagte, ist, dass Backkanten nicht von Cross unterschieden werden können, nur basierend auf der Traversierungsordnung.

Stattdessen müssen Sie etwas mehr Arbeit leisten, um sie zu unterscheiden. Der Schlüssel ist, wie Sie sehen werden, die Definition einer Kreuzkante.

Die einfachste (aber speicherintensive) Methode besteht darin, jeden Knoten mit der Menge seiner Vorgänger zu verknüpfen. Dies kann bei Besuchen von Knoten trivial erfolgen. Wenn Sie eine Nicht-Baum-Kante zwischen den Knoten a und b finden, betrachten Sie deren Vorgänger-Sets. Wenn man eine richtige Teilmenge der anderen ist, dann hat man eine hintere Kante. Ansonsten ist es eine Cross Edge. Dies ergibt sich direkt aus der Definition einer Kreuzkante: Es ist eine Kante zwischen Knoten, wo weder der Vorfahr noch der Nachkomme des anderen auf dem Baum ist.

Ein besserer Weg besteht darin, jedem Knoten nur eine "depth" -Nummer zuzuordnen anstatt einer Menge. Auch dies ist problemlos möglich, wenn Sie Knoten besuchen. Wenn Sie nun eine Nicht-Baum-Kante zwischen a und b finden, beginnen Sie mit dem tieferen der beiden Knoten und folgen Sie den Baumkanten nach hinten, bis Sie in die gleiche Tiefe wie die andere zurückkehren. Nehmen wir zum Beispiel an, ein war tiefer. Dann berechnen Sie wiederholt a = Eltern (a) bis zur Tiefe (a) = Tiefe (b).

Wenn an diesem Punkt a = b, dann können Sie die Kante als eine hintere Kante klassifizieren, da gemäß der Definition einer der Knoten ein Vorfahre der anderen auf dem Baum ist. Andernfalls können Sie es als eine Kreuzkante klassifizieren, weil wir wissen, dass keiner der Knoten ein Vorfahr oder ein Nachkomme des anderen ist.

Pseudo-Code:

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

The Die Schlüsseleigenschaft von DFS ist hier, dass das Intervall [u.entdeckt, u.prozediert] bei zwei Knoten u und v genau dann ein Subintervall ist, wenn v ein Nachkomme von v ist. Die Zeiten in BFS haben diese Eigenschaft nicht; Sie müssen etwas anderes tun, z. B. die Intervalle über DFS in dem von BFS erstellten Baum berechnen. Dann ist der Klassifizierungs-Pseudocode 1. Prüfe auf Mitgliedschaft im Baum (Baumkante) 2. überprüfe, ob Kopfintervall Schwanz enthält (Hinterkante) 3. Prüfe auf Schwanzintervall enthält Kopf (Vorderkante) 4. andernfalls deklariere eine Kreuzkante.

Answer 3

Statt timeof(), benötigen Sie eine andere Vertex-Eigenschaft, die den Abstand von der Wurzel enthält. Nenne das distance.

Sie haben einen v Vertex in der folgenden Art und Weise zu verarbeiten:

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

Nachdem Sie einen Eckpunkt eines v Vertex verarbeitet werden, können Sie den folgenden Algorithmus für jede Kante laufen (v1-v2) des 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; 
}