Python NetworkX Max_flow_min_cost Funktion läuft für immer

Ich versuche, die Max_flow_min_cost auf bestimmte Grafiken zu verwenden, aber es scheint wie manchmal der Algorithmus läuft für immer (oder zumindest für eine extrem lange Zeit), und ich verstehe nicht, warum dies ist der Fall. Hier ist ein Graph, der dazu führt, dass er so lange läuft. Sie alle haben die gleichen KnotenPython NetworkX Max_flow_min_cost Funktion läuft für immer

nodes = [ 
    ('1in', {'y': -1, 'x': -1, 'type': 'passenger in', 'number': 1}), 
    ('2out', {'y': 1, 'x': -1, 'type': 'passenger out', 'number': 2}), 
    ('destination', {'y': 0, 'x': 0, 'type': 'destination'}), 
    ('2in', {'y': 1, 'x': -1, 'type': 'passenger in', 'number': 2}), 
    ('source', {'type': 'meta'}), 
    ('4in', {'y': -1, 'x': 1, 'type': 'passenger in', 'number': 4}), 
    ('1out', {'y': -1, 'x': -1, 'type': 'passenger out', 'number': 1}), 
    ('4out', {'y': -1, 'x': 1, 'type': 'passenger out', 'number': 4}), 
    ('sink', {'type': 'meta'}), 
    ('3in', {'y': 1, 'x': 1, 'type': 'passenger in', 'number': 3}), 
    ('3out', {'y': 1, 'x': 1, 'type': 'passenger out', 'number': 3}) 
] 

edges = [ 
    ('1in', '1out', {'cost': 0, 'capacity': 1}), 
    ('2out', '4in', {'cost': -9.48, 'capacity': 1}), 
    ('2out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('2out', '3in', {'cost': -10.31, 'capacity': 1}), 
    ('destination', 'sink', {'cost': 0, 'capacity': 1}), 
    ('2in', '2out', {'cost': 0, 'capacity': 1}), 
    ('source', '2in', {'cost': 0, 'capacity': 1}), 
    ('source', '4in', {'cost': 0, 'capacity': 1}), 
    ('source', '1in', {'cost': 0, 'capacity': 1}), 
    ('source', '3in', {'cost': 0, 'capacity': 1}), 
    ('4in', '4out', {'cost': 0, 'capacity': 1}), 
    ('1out', '2in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', 'destination', {'cost':-10.9, 'capacity': 1}), 
    ('1out', '3in', {'cost': -9.48, 'capacity': 1}), 
    ('4out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('3in', '3out', {'cost': 0, 'capacity': 1}), 
    ('3out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('3out', 'destination', {'cost': -10.9, 'capacity': 1}) 
]

Wenn ich das obige Diagramm ändern, aber die Kapazität von Ziel machen zu versenken 2 oder 3, läuft es auch für immer. Wenn ich Kapazität gleich 4 mache, läuft der Algorithmus gut. Dies ist der genaue Anruf:

nx.max_flow_min_cost(G,'source','sink',weight='cost')

Vielen Dank! Jede Hilfe wird geschätzt. Es ist erwähnenswert, dass G ist ein gerichteter Graph (DiGraph)

Edit: I opened an issue auf dem NetworkX-Projekt, falls es ein Problem mit ihrem Code ist.

Quelle

2016-04-14 Arya

Für die Zukunft des Codes mit 4 Leerzeichen um tabellarisieren, um es wie Code aussehen: P. –

@imaluengo Danke! Im Editor zeigte es sich als eine Zeile, also habe ich Angst und habe es nicht gemacht. – Arya

Yep es war nur 1 Zeile, ich brach es in mehrere Zeilen (eine pro Knoten und Kante) und tabellieren Sie es mit 4 Leerzeichen. Die 1 Linie war gruselig! –

Es funktioniert gut für mich:

>>> G = nx.Graph() 
>>> G.add_edges_from([ 
    ('1in', '1out', {'cost': 0, 'capacity': 1}), 
    ('2out', '4in', {'cost': -9.48, 'capacity': 1}), 
    ('2out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('2out', '3in', {'cost': -10.31, 'capacity': 1}), 
    ('destination', 'sink', {'cost': 0, 'capacity': 1}), 
    ('2in', '2out', {'cost': 0, 'capacity': 1}), 
    ('source', '2in', {'cost': 0, 'capacity': 1}), 
    ('source', '4in', {'cost': 0, 'capacity': 1}), 
    ('source', '1in', {'cost': 0, 'capacity': 1}), 
    ('source', '3in', {'cost': 0, 'capacity': 1}), 
    ('4in', '4out', {'cost': 0, 'capacity': 1}), 
    ('1out', '2in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', 'destination', {'cost':-10.9, 'capacity': 1}), 
    ('1out', '3in', {'cost': -9.48, 'capacity': 1}), 
    ('4out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('3in', '3out', {'cost': 0, 'capacity': 1}), 
    ('3out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('3out', 'destination', {'cost': -10.9, 'capacity': 1}) 
]) 

>>> nx.max_flow_min_cost(G, 'source', 'sink', weight='cost') 
{'1in': {'1out': 0, 'source': 0}, 
'1out': {'1in': 0, '2in': 1, '3in': 1, '4in': 1, 'destination': 1}, 
'2in': {'1out': 1, '2out': 1, 'source': 0}, 
'2out': {'2in': 0, '3in': 1, '4in': 1, 'destination': 1}, 
'3in': {'1out': 1, '2out': 1, '3out': 0, 'source': 0}, 
'3out': {'3in': 0, '4in': 1, 'destination': 1}, 
'4in': {'1out': 1, '2out': 1, '3out': 1, '4out': 0, 'source': 0}, 
'4out': {'4in': 0, 'destination': 1}, 
'destination': {'1out': 1, '2out': 0, '3out': 1, '4out': 1, 'sink': 1}, 
'sink': {'destination': 0}, 
'source': {'1in': 0, '2in': 1, '3in': 0, '4in': 0}}

Quelle

2016-04-14 17:52:32

Entschuldigung! Ich habe vergessen zu erwähnen, dass G ist ein DiGraph – Arya

@Arya bearbeitet! Ohne die "Kapazität" der Kanten, die auf die Quelle und die Senke gerichtet sind, funktioniert es perfekt. Das Beispiel der Dokumentation von networkx hat diese Attribute auch nicht. –

Gibt es einen Grund dafür? Gemäß dem Algorithmus, den ich implementieren möchte, muss ich einen Graphen mit einer anderen Kapazität als dem Ziel erstellen, um zu sinken, und dann den mit den niedrigsten Kosten zurückgeben. Zum Beispiel funktioniert dieser gerichtete Graph perfekt für jede Kapazität zwischen 1 und 7 für das Ziel zu sinken: http://pastebin.com/J1tk5xCD – Arya

Der Algorithmus in networkx.max_flow_min_cost ist nicht garantiert werden, wenn die Gewichte Punktzahlen schweben. Siehe Frage die Original-Autoren auf der NetworkX Website beantwortet

https://github.com/networkx/networkx/issues/2076#issuecomment-210200259

Quelle

2016-04-15 23:52:53 Aric

Python NetworkX Max_flow_min_cost Funktion läuft für immer

Antwort

Verwandte Themen