Longest Path problem

[nooby]

Hallo Leute

Ich bins mal wieder.
Und zwar habe ich Probleme beim Verstehen eines longest Path Algorithmus. Siehe: http://stackoverflow.com/questions/1798 ... in-digraph

Code: Alles auswählen

def longest_path(G):
    dist = {} # stores [node, distance] pair
    for node in nx.topological_sort(G):
        # pairs of dist,node for all incoming edges
        pairs = [(dist[v][0]+1,v) for v in G.pred[node]] 
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node,(length,_)  = max(dist.items(), key=lambda x:x[1])
    path = []
    while length > 0:
        path.append(node)
        length,node = dist[node]
    return list(reversed(path))

Genauer gesagt, ist mir alles verständlich bis auf eine gewisse Zeile.

Code: Alles auswählen

pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs

So wie ich das verstehe, ist das eine List Comprehension, richtig?
Doch wie funktioniert der Zugriff auf das Dictionary Dist, wenn dieses noch leer ist?
Wie wird der Zähler genau erhöht.
Ich dachte das ganze sei eine kurze Version von diesem Code:

Code: Alles auswählen

pairs = []
for v in graph.pred[node]:
    distance += 1
    pairs.append((distance,v))

Jedoch lierfert das nicht das selbe Resultat...

Vielen Dank für eure Hilfe beim lernen

[BlackJack]

@nooby: Natürlich nicht, denn in dem ersten Code kommt `distance` überhaupt gar nicht vor. Dort ist der Wert an der Stelle ja auch abhängig vom `v`, in Deiner ``for``-Schleife nicht. Du musst das schon 1:1 von einer „list comprehension” (LC) in eine Schleife überführen und nicht die Berechnung selbst verändern.

[cofi]

Die Langform von

Code: Alles auswählen

pairs = [[dist[v][0]+1,v] for v in G.pred[node]]

ist

Code: Alles auswählen

pairs = []
for v in G.pred[node]:
    pairs.append((dist[v][0] + 1, v))

oder noch laenger:

Code: Alles auswählen

pairs = []
for v in G.pred[node]:
    distance = dist[v][0] + 1
    pairs.append((distance, v))

Mit anderen Worten: Du machst eine komplett andere Distanzberechnung.

Zu deinem urspruenglichen Problem kann ich aber nichts genaueres sagen ohne den Code laufen zu lassen.
Ich befuerchte aber du hast Recht und du wirst bei der Erstellung der Paare einen `KeyError` sehen.

[nooby]

Vielen Dank für deine Antwort!
Das scheint mir logisch, was mir jedoch nicht logisch ist, wieso bei der List Comprehension kein KeyError kommt.
Der Code funktioniert tadellos...
Das von dir geschickte Beispiel jedoch nicht, dort kommt der KeyError.

:K

[nooby]

//Edit: Es kommt doch zu keinem KeyError.
Muss ich wohl etwas falsch abgeschrieben haben.
Sorry dafür..
Aber die Funktionsweise ist mir leider nicht klar.

Code: Alles auswählen

distance = dist[v][0] + 1

Da dist ja Leer ist, dachte ich mir, das dies wie ein Null gilt, aber dann wäre ja distance einfach immer 1, was ja nicht der Fall ist.
Kann mich da einer der Python Profis über den hier angewandten Trick aufklären?

[BlackJack]

@nooby: Wenn `dist` leer ist, dann gibt das einen `KeyError`.

[nooby]

Dann verstehe ich etwas anderes nicht...

Code: Alles auswählen

def longest_path(G):
   [b] dist = {} # stores [node, distance] pair[/b]
    for node in nx.topological_sort(G):
        pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node, max_dist  = max(dist.items())
    path = [node]
    while node in dist:
        node, length = dist[node]
        path.append(node)
    return list(reversed(path))

'dist' wird doch beim fettgedruckten Teil erstellt.
Zwei Zeilen weiter unten wird bereits auf Werte zugegriffen, obwohl nichts hinzugefügt wurde..
Und der Code funktioniert bei mir..

[BlackJack]

@nooby: Das lässt dann nur einen Schluss zu: Im ersten Durchlauf der ``for``-Schleife wird eben *nicht* lesend darauf zugegriffen, also ist `pairs` leer, also wird der ``else``-Zweig ausgeführt in dem ein Wert hinzugefügt wird. Womit `dist` dann nicht mehr leer ist.

[nooby]

Vielen Dank, BlackJack!
Jetzt ist mir alles klar.