Wyliczanie cykli na wykresie przy użyciu algorytmu Tarjan za

Question

Próbuję określić cykli graf skierowany z wykorzystaniem algorytmu Tarjan za przedstawił w swojej pracy badawczej „wyliczenie elementarnych obwodów graf skierowany” od Septermber 1972.

Używam Pythona do kodowania algorytmu i listy sąsiedztwa, aby śledzić relacje między węzłami.

Tak więc w "G" poniżej, węzeł 0 punktów do węzła 1, węzeł 1 punktów do węzłów 4,6,7 ... itd

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 

Tarján algorytm wykrywa następujące cykle:

[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]

zostały również wykonane algorytm TIERNAN, a to (prawidłowo) znajduje 2 dodatkowe cykle:

[3,4]

[3,6,5]

będę wdzięczny za każdą pomoc w znalezieniu się dlaczego Tarjan pomija tych 2 cyklach. Może problem w moim kodzie?

Answer 1

W tych liniach:

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

jesteś iteracja listy i popping elementy z nim. Powoduje to, że iteracja nie działa zgodnie z oczekiwaniami.

W przypadku zmiany kodu, aby kopię listy produkuje dodatkowe cykle:

for w in G[v][:]: