Aufzählen von Zyklen in einem Diagramm mit Tarjan Algorithmus

Ich versuche, die Zyklen in einem gerichteten Graphen zu bestimmen, in seiner Forschungsarbeit „Aufzählung der elementaren Schaltungen eines gerichteten Graphen“ von Septermber 1972Aufzählen von Zyklen in einem Diagramm mit Tarjan Algorithmus

mit Tarjan-Algorithmus, vorgestellt

Ich benutze Python, um den Algorithmus zu kodieren, und eine Adjazenzliste, um die Beziehungen zwischen Knoten zu verfolgen.

Graph visualisation

So in "G" unter der Knoten 0 Punkte an den Knoten 1, Knoten 1 zu Knoten Punkte 4,6,7 ... etc.

G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [5, 8], [5, 8], [], []] 
N = len(G) 

points = [] 
marked_stack = [] 
marked = [False for x in xrange(0,N)] 

g = None 
def tarjan(s, v, f): 
    global g 
    points.append(v) 
    marked_stack.append(v) 
    marked[v] = True 

    for w in G[v]: 
     if w < s:    
      G[v].pop(G[v].index(w)) 
     elif w == s: 
      print points 
      f = True 
     elif marked[w] == False: 
      if f == g and f == False: 
       f = False 
      else: 
       f = True 
      tarjan(s, w, g) 

    g = f 

    if f == True: 
     u = marked_stack.pop() 
     while (u != v): 
      marked[u] = False 
      u = marked_stack.pop() 
     #v is now deleted from mark stacked, and has been called u 
     #unmark v 
     marked[u] = False 
    points.pop(points.index(v)) 

for i in xrange(0,N): 
    marked[i] = False 

for i in xrange(0,N): 
    points = [] 
    tarjan(i,i, False) 
    while (len(marked_stack) > 0): 
     u = marked_stack.pop() 
     marked[u] = False

Tarjan Algorithmus detektiert die folgenden Zyklen:

[2, 4]

[2, 4, 3, 6, 5]

[2, 4, 3, 7, 5]

[2, 6, 5]

[2, 6, 5, 3, 4]

[2, 7, 5 ]

[2, 7, 5, 3, 4]

[3, 7, 5]

ich habe auch Tiernan-Algorithmus getan, und es (richtig) findet 2 zusätzliche Zyklen:

[3,4]

[3,6,5]

ich Hilfe bei der Suche nach schätzen würde, warum Tarjan über diese 2 Zyklen überspringt. Ein Problem in meinem Code vielleicht?

Quelle

2014-09-17 janvdl

Ist das dasselbe als Grafik-Intervall-Analyse? – paulm

Hallo Paul, ich bin mir nicht ganz sicher, aber nach dem Überprüfen der Wikipedia-Seite in Graphintervallen denke ich, die Antwort ist nein, sie sind nicht die gleichen. Es ist möglich (denke ich), dass die Zyklen innerhalb des Graphen als Intervalle des Graphen angesehen werden können, aber die Zyklen werden nur eine Teilmenge der Intervalle des Graphen sein. Ich sollte beachten, dass es einen Fehler in diesem Code gab, der aktualisierte Code ist verfügbar unter: https://github.com/janvdl/python_tarjan/blob/master/tarjan.py – janvdl

Für diejenigen, die an der Implementierung dieses Algorithmus interessiert sind, den obigen Code enthält einen Fehler. Ich habe sowohl eine Python (https://github.com/janvdl/python_tarjan/blob/master/tarjan.py) und Golang (https://github.com/janvdl/go_tarjan/blob/master/tarjan.Go) Implementierung von Tarjans auf meiner Github-Seite, zusammen mit einer Python-Implementierung von Tiernans Algorithmus (https://github.com/janvdl/python_tiernan/blob/master/tiernan.py). – janvdl

In diesen Zeilen:

for w in G[v]: 
    if w < s:    
     G[v].pop(G[v].index(w))

Sie durch eine Liste iterieren und Elemente aus es knallen. Dies verhindert, dass die Iteration wie erwartet funktioniert.

Wenn Sie den Code ändern, um eine Kopie der Liste zu machen, um die zusätzlichen Zyklen erzeugt:

for w in G[v][:]:

Quelle

2014-09-17 19:11:48

StackOverflow enttäuscht nie. Vielen Dank, du hast mir viele Kopfschmerzen erspart! – janvdl

Aufzählen von Zyklen in einem Diagramm mit Tarjan Algorithmus

Antwort

Verwandte Themen