"Beste Zuweisung" //EDIT: für ein Photomosaic

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

hallo leute :)

irgendwie steh ich momentan total auf dem schlauch. leider hab ich in den letzten tagen bissl schlaf versäumt und das schlägt sich momentan glaub ich nieder.

ich will eigentlich was ganz einfaches, bin aber zu verduddelt momentan ne lösung zu finden.

ums kurz zu machen: ich will die elemente(in dem beispiel einfach zahlen //edit: in wirklichkeit bilder//) zweier listen "am besten matchen"

dabei sollen immer zwei elemente "verbunden" werden. gut ist es wenn der betrag der differenz der beiden zahlen möglichst gering ist und die summe der beträge auch möglichst gering (best möglich) (//EDIT: im fall von bildern, halt bilder mit möglichst geringer differenz). klingt bissl durcheinander glaub ich .. ich mach mal ein beispiel:

Code: Alles auswählen

liste1: 10 50 13 25
liste2: 12 18 23 26

ich will jetzt, dass die differenz zweier zahlen möglichst gering ist und die summe aller differenzen auch, so dass sich sowas hier ergibt(abs(zahl_oben - zahl_unten) und das aufsummiert )

Code: Alles auswählen

10 13 25 50
12 18 23 26
---------------
2 +5 +2 +24 = 33
das will ich erreichen und zwar möglichst schnell ... also nicht alles permutieren und dann gucken welche permutation die beste ist ... ich sollte vielleicht noch sagen, das jede zahl einer liste genau einmal verwendet werden muss.

ich hab jetzt schon einige ansätze versuch mit "zurücklegen" .. differenzen speichern .. aber ich stell mich momentan zu blöde an

hoffe mir kann jemand helfen mein gehirn iss momentan nicht mehr dazu in der lage

//edit: um meinen post jetzt nicht ganz zu zerpflügen hab ich unten noch mal eine "nähere erläuterung" verfasst. da mein minimal beispiel den kern wohl doch etwas verfehlt.//


mfg lordnaikon
Zuletzt geändert von lordnaikon am Montag 17. Januar 2011, 22:57, insgesamt 5-mal geändert.
BlackJack

@lordnaikon: Ich mag da heute nicht mehr länger drüber nachdenken oder es gar zu beweisen versuchen, aber mein Gefühl und Dein Beispiel legen nahe, dass ``zip(sorted(list_a), sorted(list_b))`` eine Lösung sein könnte.
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

@BlackJack: witzig, daran hab ich noch gar nicht gedacht. wie es scheint hast du aber wohl wirklich recht. (habs jetzt auch nicht näher untersucht, aber augenscheinlich scheint es zu stimmen). das problem ist, dass sich das wohl nicht für mein richtiges projekt gebrauchen lässt, was wohl an meiner schlecht formulierten frage und dessen beispiel liegt. ich dachte dieses minimalbeispiel ist geeignet genug, scheinbar nicht.


ich sag einfach mal um was es geht:

ich will für eine erweiterung meines photoarchiv programms ein photomosaic aus einem album erstellen. nun soll das mosaic aus ALLEN bildern OHNE wiederhohlung erstellt werden. dabei soll eine vorlagebild gekachelt werden(in so viele wie es bilder im album gibt). nun nimmt man eine vorlagebild kachel und vergleicht diese(auf geeignete weise) mit den bildern aus dem album. dabei kann für jedes paar eine art "matching faktor" berechnet werden. das ist der wert, der in meinem beispiel ganz unten stand und addiert wurde(die "bildwerte" der kacheln und albumbilder stellen die oberen zahlen paare da).

Code: Alles auswählen

10 13 25 50                übertragen        kachelbild: [1,1]   [1,2]   [1,3]   [1,4]
12 18 23 26                =========>        albumbild :  ab1     ab2     ab3    ab4
---------------                               ---------------------------------------
2 +5 +2 +24 = 33                             fehler:       2    +   5    + 2    + 24      =  gesammtfehler 33   
im ergebnis soll halt, global, ein möglichst geringer "matching faktor" .. oder besser würde hier wohl fehler passen, erreicht weden. ich kann halt quantitativ sagen der fehler zwischen kachel[1,1] und albumbild1(ab1) ist ... 2(werte der unteren zeile im beispiel) ... die oberen werte sollen nur sinnbildlich für farbwerte oder so in den bildern stehen(dessen berechnung ich gerade noch ausknoble aber das ist ein anderes thema) ... ich kann also quasi nur die werte der unteren zeile berechnen, die oberen kann ich wohl nicht sortieren, das sind halt bilder, denen ich wohl absolut keinen quantitativen wert zuordnen kann.

wie bekomme ich nun, möglichst mit geringem aufwand, die "beste konstellation" der bilder hin?

ich hoffe das war ein wenig verständlicher; wie gesagt bin bissl unter mündigkeits erscheinungen. möchte das gerne noch fertig bekommen, bevor es wieder arbeiten geht :P
Zuletzt geändert von lordnaikon am Montag 17. Januar 2011, 23:15, insgesamt 2-mal geändert.
BlackJack

@lordnaikon: Ich denke mal für die beste Zuweisung unter diesen Bedingungen kommt man um ein Vergleichen mit allen Bildern und Kacheln nicht herum. Aber ich würde auch erst einmal recherchieren was es zum Thema Photomosaik schon an Literatur und Algorithmen gibt.

OT: "mündigkeits erscheinungen" ist auch nicht schlecht. Kommt bei den meisten Bürgern viel zu selten vor. :-D
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

@"mündigkeits erscheinungen".. den hab ich erst gar nicht verstanden :P, da kann man mal sehen wie weit es schon ist. war es ein "verschreiber" oder doch eher eine "freudsche fehlleistung"? wer weiß :)

@BlackJack: bissl literatur hab ich schon "gesichtet". dabei dreht es sich hauptsächlich aber um den "vergleich" der bilder und der "fehler"berechnung.

und ja um das vergleichen aller kacheln mit den albumbildern werde ich nicht herumkommen. aber mein trauriges problem ist jetzt, was mach ich dann wenn ich alle verglichen habe? ... wie bekomme ich den "globalen"fehler(die summe aller lokalen fehler) möglichst klein wo ich nur den "lokalen"fehler(alle bilder vergleiche) kenne. da hab ich im moment eine riesen blockade!

//EDIT: also wenn ich alles verglichen habe habe ich ja ein matrix/tabelle .. was auch immer (hier auf 3 bilder reduziert)
...|| 10 | 13 | 25 <-- bilder
--------------------
12|| 2 | 1 | 13
--------------------
18|| 8 | 5 | 7
--------------------
23|| 13 | 10 | 2
^
|
bilder
wie bekomm ich jetzt raus welche konstelation aus [10,13,25] und [12,18,23] den geringsten "fehler" hat?

also hier im beispiel wäre das bild 10 und bild 12 mit fehler 2, bild 13 und bild 18 mit fehler 5 und bild 25 und bild 23 mit fehler 2 und einem "globalen" fehler von 9
Rekrul
User
Beiträge: 78
Registriert: Dienstag 7. Dezember 2010, 16:23

Hi,

um es ganz genau zu machen wirst du vermutlich die 'Differenz' aller Bilder / Kacheln berechnen müssen. Vielleicht kannst du aber auch über den Mittelwert der Bilder alles wieder auf einfache Zahlen reduzieren und dann mittels Sortieren gute Matchings finden. Mit Graustufenbildern dürfte das sicherlich akzeptable Ergebnisse liefern, aber wenn du die Bilder im RGB vorliegen hast musst du vermutlich doch wieder alle 3 Mittelwerte (für R,G,B) einer Kachel mit den 3 Mittelwerten aller deiner Bilder vergleichen.
BlackJack

Das mit dem einfachen Sortieren dürfte nur funktionieren, wenn man eine Funktion findet, die den "Abstand" zwischen zwei beliebigen Bildern berechnet und die transitiv ist. Dann könnte man den Abstand zwischen allen Kacheln und allen Bildern zu zum Beispiel einem komplett mittelgrauen Bild berechnen und hätte wieder Werte die sich linear ordnen liessen.

Mit Graustufenbildern ginge das vielleicht sogar recht einfach, ich sehe aber im Moment nicht auf Anhieb, wie man bunte Bildern am besten auf einen Wert mit den geforderten Eigenschaften reduzieren kann.
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

Hallo, und guten Morgen :)

Also entschuldigt das hingerotze meines Postings gestern! Ich war echt ein wenig "abgespannt".

Also um es noch mal klar zu sagen: WIE man die "differenzen" der Bilder berechnet steht nicht zur Diskussion(noch nicht :P .. ich hab schon was und das geht auch recht gut, wie man sieht)
Angenommen ich könnte aus zwei Bildern eine konkrete "differenz" errechnen, wie erreiche ich die beste Position.

Um das Problem noch mal zu verdeutlichen. Ich habe ein Menge B von Bildern. Diese Soll nun auf eine Menge K (Kacheln des Vorgabebildes) abgebildet werden und zwar so, dass die addierten differenzen der Teilbilder möglichst gering ist. Warum?

Wenn ich einfach zu jedem elem. aus K (also einer Kachel) mir die zu Verfügung stehenden Bilder aus B nehme und nach dem passensten suche, muss ich es "weglegen", also für spätere vergleiche mit anderen Kachel nicht berücksichtigen, weil ich keine Dopplungen will. Wenn ich das aber mache, habe ich das Problem, dass ich zwar lokal das beste Bild gefunden habe, es könnte aber sein, dass es auf eine andere Kachel noch besser Passt. Dadurch erhöht sich der "Globale"-Fehler! Wenn nur noch wenige Bilder bei diesem Vorgang übrig sind, dann wird der Fehler immer höher; kaum ein Bild passt mehr gut.

Dieses Verhalten kann man auch sehr schön sehen, man kann richtig den Algorithmus im Bild sehen und welchen Weg er genommen hat.
Bild

um das zu umgehen will ich nun die permutation der Bilder auf den Kachel, so dass der Gesammtfehler(Globale) aller Teilbilder(lokale Fehler) möglichst gering ist. wenn ich nun alle Bilder mit allen Kachel verglichen habe und die lokalen Fehler kenne .. was mach ich dann?

Code: Alles auswählen

...|| 10 | 13 | 25 <-- bilder
--------------------
12 || 2  | 1  | 13 
--------------------
18 || 8  | 5  | 7 
--------------------
23 || 13 | 10 | 2 
^
|
kacheln
wie gesagt bei den "bilder" und "kacheln" der zeilen und spalten Beschriftung handelt es sich um Bilder! Ich habe hier halt Zahlen genommen, so dass man nachvollziehen kann, wie auf die Fehlerwerte gekommen bin. Es könnte genauso auch so aussehen(entspricht wohl eher der Realität)

Code: Alles auswählen

...|| b1 | b2 | b3 <-- bilder
--------------------                übertragen        kachelbild: k1   k2   k3 
k1 || 2  | 1  | 13                  =========>        albumbild : b1   b2   b3    
--------------------                            --------------------------------
k2 || 8  | 5  | 7                                         fehler: 2  +  5  + 2    =  gesammtfehler 9  
--------------------
k3 || 13 | 10 | 2 
^
|
kacheln
hier ist nun das "beste" ergebnis mit k1,b1 ; k2,b2 ; k3,b3 ... anderen permutationen ergeben ein schlechteren globalen Gesammtfehler
Zuletzt geändert von lordnaikon am Mittwoch 19. Januar 2011, 23:06, insgesamt 1-mal geändert.
BlackJack

@lordnaikon: Hm, man könnte das ja als Graph auffassen mit den Knoten `k_1` bis `k_n` und `b_1` bis `b_n`, wobei jeder `k_i` mit jedem `b_i` durch eine Kante verbunden ist, dessen Gewicht dem Abstand entspricht. Und dann kannst Du einen Algorithmus darauf loslassen, der einen Weg sucht, bei dem das Gesamtgewicht minimal ist, jeder Knoten besucht wird, und eine Kante maximal einmal beschritten wird.

Das dürfte letztlich auf rekursiv durchprobieren mit "branch and bound" als einizige mögliche Optimierung hinauslaufen.
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

@BlackJack: Das hatte ich befürchtet :? :(

Das Problem an der Sache ist, dass sich die Bildmenge so bei 50.000 - 200.000 Bilder bewegt. Allein der Vergleich aller Bilder um den "Graph" zu erstellen würde dann 2.500.000.000 Vergleiche bedeuten. Das ist ja noch nicht allzuschlimm. Schlimm wird es dann wenn ich, wie du gesagt hast, den "Graph" ablaufen muss für den "besten"-Pfad. Ich hatte eh vor das ganze in der Amazon Cloud aufnen paar EC2's laufen zu lassen, aber ich glaube das sprengt den Ramen komplett, oder?

Vielleicht müsste man jetzt den Ansatzt gehen zu sagen, ich will nicht "das Beste" sondern ein hinreichend gutes Ergebnis. Eventuell könnte man wirklich mal den Ansatz versuchen, die Bilder nach den Luminazwerten "vorzusortieren" (wie ihr beide weiter oben vorgeschlagen habt) ... und dann ja ... weiß noch nicht so recht :? :?:
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

Wie gesagt hatte ich wenig Zeit, leider bleibt das auch erstmal so bis zum Ende der Woche.

Aber ich wollte doch noch ein paar kleine Überlegungen machen. Zu dem von dir (BlackJack) gemachten Vorschlag des Graphen. Hast du dir dabei so etwas vogestellt? (klicken zum vergrößern, sollte aber auch so erkennbar sein)
Bild

Dann müsste ich also bei k1 starten(weil es meine erste Kachel ist) und mir einen Weg zu einem Bild suchen, sagen wir einfach mal b1. Hier nun angekommen, macht es natürlich keinen sinn, auf den vorhandenen Kanten "weiter" zur nächsten Kachel zu wandern. Also müsste man dann eventuell mit Null(0) gewichtete Kanten zurück zu den Kacheln einbauen, oder?
Leider ist die Graphentheorie schon bissl bei mir her und ich fühl mich einfach nicht mehr ganz so sicher auf dem Gebiet. Ich weiß zum einen nicht genau, wie der Graph auszusehen hat, der mein Problem abbildet; zum anderen weiß ich auch gerade nicht welcher algorithmischen Problematik ich hier gegenüber stehen. Könnte es der minimale Spannbaum sein oder ist es doch schon das Problem des Handelsreisenden, dessen exakte Lösung wir hier praktisch ausschließen können, es aber gute Annäherungen zu geben scheint (max 2x schlechter als die beste Route).
BlackJack

lordnaikon: Der Graph war schon so gemeint, aber die Idee für den Algorithmus war natürlich nicht so toll. Ich war wohl zu müde.

Aber jetzt habe ich mal im Cormen nachgeschlagen und das Problemgebiet heisst "maximum flow" und das konkrete fällt unter "maximum bipartite matching". Da werden zwar die Paare mit den maximalen Kantengewichten gesucht, aber Du kannst bei den Gewichten ja einfach das Vorzeichen umdrehen oder den Algorithmus entsprechend anpassen. Der im Buch vorgestellte Algorithmus schimpft sich Ford-Fulkerson-Method.
Trichter
User
Beiträge: 45
Registriert: Montag 20. April 2009, 10:21

Was hältst du von folgender Zuweisungsmethode:

Angenommen du hast ein Bild, das in n Kacheln unterteilt wurde und kennst auch die Differenzwerte zwischen jedem Bild deines Bildervorrats und jeder Kachel. Du hast also die komplette Tabelle mit Differenzwerten, die du oben erwähnt hast.
Für jede Kachel legst du nun eine Liste von x Bildern an, die die kleinsten Differenzwerte aufweisen. Das sind quasi die Vorschläge für die Belegung der Kachel im fertigen Mosaik. Gleichzeitig zählst du für jedes Bild, wie oft es in einer solchen Vorschlagsliste gelandet ist.
Anschließend weist du jeder Kachel ein Bild aus der zugehörigen Liste zu, wobei du die Bilder, die am seltensten vorgeschlagen wurden bevorzugst. Du entfernst damit diejenigen Bilder aus deinem Vorrat (da du ja keine Bilder doppelt verwenden willst), die für möglichst wenige Vorschlagslisten anderer Kacheln relevant sind.
Natürlich kann es bei den letzten Mosaikteilchen vorkommen, dass nur noch wenige oder gar keine Bilder aus der Vorschlagsliste übrig sind. Dann müsste man die Zuweisung evt. mit einem größeren Wert für x wiederholen. So findet man zwar kaum die optimale Lösung, doch es könnte ein passables Ergebnis in relativ kurzer Zeit produzieren. Wenn man zusätzlich noch die Kacheln in zufälliger Reihenfolge abarbeitet, verhindert man auch das Entstehen von sichtbaren Mosaikbereichen mit großen oder kleinen Fehlern.
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

@BlackJack: Super! echt vielen dank für die Mühe; mensch da kommen gleich alte Erinnerungen von damals wieder hoch; nur leider so lückenhaft. Hab mir das mal angesehen und so wie ich das verstehe, geht es gar nicht um die, von mir gesuchten, Kantengewichte oder? Geht es dabei nicht darum eine hohe(max.) quantitative Paarung zu finden, also die max. Kardinalität von M (aus Teilmenge E von G=(V,E)) bei der gilt (Def. von Paarung) das zwei belibige Kanten e1,e2 elem. M disjunkt sind?
Cormen hat geschrieben: Given an undirected graph G = (V, E), a matching is a subset of edges M elem. E such that for all
vertices v elem. V, at most one edge of M is incident on v. We say that a vertex v elem. V is matched
by matching M if some edge in M is incident on v; otherwise, v is unmatched. A maximum matching is a matching of maximum cardinality, that is, a matching M such that for any
matching M', we have |M| ≥ |M'|. In this section, we shall restrict our attention to finding
maximum matchings in bipartite graphs. We assume that the vertex set can be partitioned into
V = L R, where L and R are disjoint and all edges in E go between L and R. We further
assume that every vertex in V has at least one incident edge.
Es also darum geht, möglichst viele Paarungen zu finden, so dass Ein Knoten max. eine Kante hat ...
Bild
BlackJack

@lordnaikon: Verdammt, Du hast Recht. Aber der Algoritmus für das "bipartite matching" macht das in dem er jeder Kante das Gewicht 1 zuordnet; und damit sozusagen die Kanten zählt, die im Ergebnis vorkommen. Da die Kantenanzahl bei Dir aber immer fest steht -- je eine Kante pro (k_i, b_i) Paar, müsstest Du doch statt 1 Deine (negativen) Differenzen als Gewichte für die Kanten nehmen können. Denn die Summe dieser Werte zu maximieren ist ja die Aufgabe vom Algorithmus.
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

@Trichter: Danke für den Vorschlag, an sowas ähnliches hab ich auch schon gedacht, nur auf das Zählen wie oft ein Bild vorgeschlagen wurde (also sich in einer Vorschlagsliste befindet) bin ich noch nicht gekommen, vielleicht klappt das ja wirklich.. muss ich nochmal drüber grübeln. Irgendwie klingt es intuitiv als wäre das ne brauchbare Lösung, kann jetzt aber noch nicht sagen warum; das mit dem zufällig verteilen muss ich erstmal außen vor stellen, ganz einfach deshalb: sollte ich nun auch mal die Zeit haben es zu implementieren, muss ich es visuell vergleichen können, also wie der "Sichtbare"fehler linear zunimmt. Vielleicht zählt man den Fehler ja mal.
Aber dazu muss ich mein kleines Script erstmal komplett neu machen ..(und immer die gute alte Zeit :cry: )
Ich denke ich werde höchstwahrscheinlich auf "solche" Ansätze zurück kommen müssen. Die Laufzeitkomplexität macht mir bei meiner Zielgröße von 50k -200k schon sehr zu schaffen. Welchen Wert hatte ich hier mal in den Raum gestellt für die Anzahl der lokalen Fehler ich glaube 2.500.000.000. Das macht bei einer Laufzeit von O(n²) schon beachtliche 6,25 Trillionen! ... grr :shock: ... :cry:

@BlackJack: Ich glaube ich versteh jetzt deinen Gedankengang. Ich hab wohl einfach den Fehler gemacht den Worten von Cormen bild zu vertrauen und den Sinn Deiner Erweiterung nicht verstanden habe. Ich fasse das nochmal zusammen um hier keine Missverständnisse meiner seits aufkommen zu lassen. Cormen "missbraucht" Ford-Fulkerson um einfach zu zählen. Den Bipa. Graph wandelt er in ein Netzwerk dessen Kanten alle auf eins gesetzt werden. Dies tut er aus dem einzigen Grunde um die Vorraussetzungen für die "Paarung" zu erfüllen (e1,e2 elem. M disjunkt). So ist es nämlich nicht möglich zwei Kanten an einem Knoten aufzubauen, denn der Fluss ist schon auf eins beschränkt. Ford-Fulkerson versucht nun den Maximalen-Fluss zu finden und der entspricht dann auch der Anzahl an "Paarungs"kanten. Diejenigen Kanten mit dem "meisten" Fluss ... oder besser die nicht Teil des Residualgraphen sind und den Fluss "eins" haben (also überhaupt fluss) sind nun Teil der Paarung.
Bild

Jetzt kommst Du und "missbrauchst" Cormen in dem du den Zu- und Abfluss der Quelle und Senke bei "eins" lässt(das stellt die Bedingung der Paarung sicher) und suchst nun mit Ford-Fulkerson nach dem maximalem Fluss in dem Bipat. Graphen.
Bild

Und jetzt kommt Der Clou: Ich habe jetzt die Paarungen(wegen des auf eins begrenzten Flusses der Quelle und Senke) mit dem Maximalen Fluss .. dem globalen Fehler!! :shock: :lol:

Code: Alles auswählen

k1 {'b1': 0, 'b2': 0, 'b3': 1}          k1,b3 = 13
k3 {'b1': 1, 'b2': 0, 'b3': 0}  ==>     k3,b1 = 13   ==>  maximal möglicher gesammt Fehler von 31
k2 {'b1': 0, 'b2': 1, 'b3': 0}          k2,b2 = 5
jetzt sollte ich (wie du schon sagtest) den Fehler anders interpretieren (negieren .. oder invers ich denk mir da was aus) und dann sollte das gehen!!

Jetzt kommt noch das dicke Ende, die Laufzeitkomplexität :| so richtig hab ich da nix gefunden nur bei Wiki. O(E*f) wobei f der maximale Fluss sein soll oder aber O(V + E²) wobei ich wieder bei meinen 6,25 Trillionen wäre. Lässt sich auch Push-Relabel hier anwenden der O(V² + E) hat wären dann nur 2,5 Milliarden (und das mein 50K Bildern)
lordnaikon
User
Beiträge: 58
Registriert: Dienstag 9. Februar 2010, 13:41

Ich muss meine Euphorie leider wieder zurück nehmen :K

Wie es der Zufall so will, hat der olle Murphy mal wieder zugeschlagen. Eben beim Nudeln kochen lassen gemerkt, als ich es mal drauf ankommen lassen wollte den "min"fehler zu bekommen, das ich immer das gleiche Ergebnis bekomme :x. Damit will ich sagen: egal welche Gewichte die Kanten haben, es kommt immer die gleiche Reihenfolge oder Paarung bei raus also immer k1,b3; k2,b2; k3,b1. ZUFÄLLIG war das aber bei meiner Konstallation das richtige Ergebnis ... verdammich noch mal :evil:

Anschienend benutzt der Ford-Fulkerson algo von networkx eine nicht ganz so zufällige Auswahl der Pfade.

Mach ich vielleicht etwas falsch?

hier mal der code:

Code: Alles auswählen

import networkx as nx
import matplotlib.pyplot as plt

G=nx.DiGraph()
#die Bipat. Knoten
G.add_nodes_from(["k1","k2","k3","b1","b2","b3"])
G.add_nodes_from(["s","t"])
#hier kann man gerne die kapazitaeten tauschen, immer drei geben eine zeile ... 
capacities = [{'capacity':x} for x in [2,1,13,8,5,7,13,10,2]]
#capacities = [{'capacity':x} for x in [9,8,7,6,5,4,3,2,1]]
ks = [ "k%s" % str(x) for x in [1,1,1,2,2,2,3,3,3]]
bs = [ "b%s" % str(x) for x in [1,2,3,1,2,3,1,2,3]]
G.add_edges_from(zip(ks,bs,capacities))

capacities2 = [{'capacity':x} for x in [1,1,1,1,1,1]]
st = [ "s" if x<3 else "b%s" % str(x-2) for x in range(6)]
kb = [ "k%s" % str(x+1) if x<3 else "t"  for x in range(6)]
G.add_edges_from(zip(st,kb,capacities2))

#setze position der Knoten
pos=nx.spring_layout(G)
ik = 0
ib = 0
for edge, e_pos in pos.iteritems():
    if "k" in edge: 
        e_pos[0] = 0.1
        e_pos[1] = ik * 0.1
        ik = ik+1
    if "b" in edge: 
        e_pos[0] = 0.3
        e_pos[1] = ib * 0.1
        ib = ib+1
    if "s" in edge:
        e_pos[0] = -0.03
        e_pos[1] = 0.1
    if "t" in edge:
        e_pos[0] = 0.43
        e_pos[1] = 0.1

flow,F=nx.ford_fulkerson(G, 's', 't')

print "max_flow:",flow
print "F","xxx","\n\n\n"

for el, val in F.iteritems():
    print el, val,
    if "k" in el:
        for pic, flow in val.iteritems():
            if flow > 0:
                print pic,
                print "= ",G[el][pic]["capacity"]
                pass				
nx.draw(G,pos)

nx.draw_networkx_edge_labels(G,pos) 

plt.show()
#plt.savefig("path2.png")
Antworten