Algoritmul Ford Fulkerson

Algoritmul Ford-Fulkerson Sorin OSTAFIEV – grupa 331CA

Proiect la “Analiza Algoritmilor”

Sorin OSTAFIEV grupa 331CA


Page 1 of 49

Introducere

Algoritmul Ford-Fulkerson este unul din algoritmii cei mai simpli care rezolva problema “Debitului maxim”. Considerand un graf orientat in care exista un nod S (sursa) si un nod D (destinatie) si fie A si B doua noduri oarecare in graf. Daca exista muchie de la A la B atunci asociem debitul maxim care poate circula de la A la B cu costul muchiei A->B. Suma debitelor care intra intr-un nod este egala cu suma debitelor ce iesa din acel nod (cu exceptia nodului S si D). Problema debitului maxim este determinarea valorii maxime ce poate fi introdusa prin nodul de intrare (nodul S) si este obtinuta la iesire (nodul D) fara a se depasi insa pe parcurs de-a lungul unei munchii valoarea debitului maxim asociat acelei muchii.


Page 2 of 49

Prezentare

Fie dat un graf orientat. Daca exista un nod S cu proprietatea ca nu esista

muchie a grafului care sa fie orientata spre S (source) si un nod D (sink) astfel incat nu exista muchie dinspre D atunci se spune ca graful este o “retea de transport” (flow network).

Fig 1. O retea de transport; nodul sursa este nodul 1,

iar nodul destinatie este nodul 2 Algoritmul Ford-Fulkerson determina fluxul maxim care poate fi introdus

intr-o retea de transport si se mai cunoaste si sub denumirea de problema


Page 3 of 49

“debitului maxim” (max flow). Procedeul prin care se determina debitul maxim este relativ simplu:

fie costul initial egal cu 0 cat timp exista un drum de la S la P atunci fie d un drum de la S la P fie m muchia care este inclusa in d si are costul minim scade costul muchiei m din toate muchiile care apartin

lui d pentru fiecare muchie A->B inclusa in d adauga o

muchie B->A egala cu costul muchiei m adauga la costului total valoarea costului muchiei m

Fie f un flux introdus prin retea la un moment dat. Se numeste capacitatea reziduala a unei muchii in acel moment fluxul aditional care mai poate fi introdus prin acea muchie fara a depasi insa capacitatea acelei muchii. De exemplu daca capacitatea unei muchii (u,v) este c(u,v)=10 iar prin acea muchie a fost introdus un flux f(u,v)=7 atunci capacitatea reziduala a muchiei (u,v) este cf(u,v)=c(u,v)-f(u,v). Cand fluxul f(u,v) este negativ capacitatea reziduala cf(u,v) este mai mare decat capacitatea c(u,v). De exemplu daca c(u,v)=10 si f(u,v)=-4 atunci cf(u,v)=14 ceea ce poate fi interpretat in felul urmator: exista un flux de 4 unitati care de la v la u care poate fi anulat prin introducerea unui flux de 4 unitati de la u la v. Apoi mai putem introduce un flux de inca 10 unitati pana la atingerea maximului pentru muchia respectiva. Deci in total putem introduce 14 unitati pe flux pe o muchi de cost 10 incepand de la un flux de –4 fara a depasi capacitatea maxima a muchiei.

Fiind data o retea de transport G=(V,E), in care V este multimea varfurilor

(vertex) si E multimea muchiilor (edge), si un flux f numim retea reziduala a retelei G indusa de f o retea Gf(V,Ef) in care Ef={(u,v) ∈ VxV | cf(u,v)>0}. De observat ca (u,v) poate fi o muchie reziduala in Ef chiar daca nu este muchie in E. Reteaua reziduala Gf este si ea o retea de transport cu capacitatile date de cf.

Principala probleama care apare este alegerea unui drum (augmenting path) de la S la P si in aceast sens exista mai multe metode de alegere a lui. Fie p un drum de la S la P. Se numeste capacitate reziduala a lui p maximul de unitati de flux pe care le putem introduce pe drumul p, adica cf(p)=min(cf(u,v) | (u,v) ∈ p}. Sa presupunem ca avem reteaua de transport din figura 2 si ne propunem sa gasim fluxul maxim care poate traverseaza reteaua de la nodul 1 la nodul 6.


Page 4 of 49

Fig. 2

Pentru inceput stabilim fluxul maxim la valoarea 0 si alegem un drum de la

1 la 6. Sa zicem ca am gasit drumul 1-2-3-5-6 care are capacitatea reziduala 1 (datorita muchiei 2-3). Adaugam 1 la rezultat si continuam algoritmul. Alegem alt drum de exemplu 1-2-4-6 care are capacitatea reziduala 2 (datorita muchiei 2-6) pe care o adaugam fluxului total si actualizam costurile muchiilor. In acest moment nu mai exista decat un singur drum de la 1 la 6 si anume drumul 1-3-5-6 care are capacitatea reziduala 1 (datorita muchiei 3-5 care avea initial capacitatea 2, dar in urma alegerii drumului 1-2-3-5-6 a ramas doar cu o singura unitate de flux). Deci am obtinut un flux total de 4 unitati algortimul luand sfarsit deoarece nu se mai poate ajunge din nodul 1 in nodul 6. Dar acest rezultat nu este tocmai fluxul maxim deoarece dupa cum se vede in figura 3 in aceasta retea de transport se poate obtine un flux de 5 unitati.


Page 5 of 49

Fig 3. Fluxul maxim prin reteaua de transport din figura 2

Pentru a vedea unde este problema sa presupunem ca in graful initial in loc sa alegem drumul 1-2-3-5-6 am alege drumul 1-2-4-6 care are o capacitate reziduala de 2 unitati, iar apoi drumurile 1-2-5-6 si 1-3-5-6. Aceasta alegere a drumurilor ne conduce la un flux total de 5 unitati. Dar obtinerea fluxului maxim n-ar trebui sa depinda de felul in care se aleg drumurile. Acesta este un exemplu de algoritm greedy care esueaza.

Ca algoritmul sa functioneze corect introducem pentru fiecare muchie (u,v) cu fluxul fu,v in reteaua de transport o muchie (v,u) in reteaua reziduala cu capacitatea fu,v. Prin aceasta metoda ii permitem algoritmului sa faca “undo” la propriile decizii trimitand inapoi un flux in directia opusa. Asadar in graful rezidual din exemplul nostru vor fi muchii in ambele directii intre varfurile 2 si 3. Algoritmul va putea astfel, dupa gasirea drumului 1-2-4-6 sa gaseasca drumul 1-3-2-5-6 care poate fi impins inapoi pe muchia 2-3 algoritmul, gasind astfel inca un flux de cost 1 ca apoi alegand si drumul 1-3-5-7 (de capacitate reziduala 1) sa ajunga la fluxul maxim egal cu 5.


Page 6 of 49

Tipuri de date abstracte

tip: Nod domeniu: int

operatori NewNod: → Nod IsSelected: Nod → boolean

IsMark:Nod → boolean

axiome selected(U)=IsSelected(U) mark(U)=IsMark(U)

tip: Edge domeniu: int, int

operatori: NewEdge: int x int → Edge GetCapacity: int x int → int GetFlow: int x int → int IsSelected: int x int → boolean IsMark → boolean SetCapacity: int x int x int → int

axiome

selected(U)=IsSelected(U) mark(U)=IsMark(U) Capacity(L)=GetCapacity(L) Flow(L)=GetFlow(L) Exist(L)=(Capacity(L)>0)


Page 7 of 49

Complexitate

Complexitatea algoritmului Ford-Fulkerson este la o prima vedere O(E * MF) unde E este numarul varfurilor iar MF este fluxul maxim gasit de algoritm. Drumul poate fi ales in mai multe moduri, iar complexitatea algoritmului poate fi diferita pentru moduri diferite de alegere a modului in care se alege drumul sau in functie de graful ales. Daca se face o explorare in adancime a grafului pornind din S s-ar putea ca pentru grafuri cu numar foarte mic de muchii dar fluxul total mare sa obtinem o complexitate neacceptabil de mare. De aceea cel mai des se utilizeaza algoritmul de explorare in largime a grafului. Drumul ales la un moment dat prin aceasta metoda la un moment dat este cel mai scurt drum de la S la D in reteaua reziduala considerand toate muchiile de cost 1. Acest mod de implementare a metodei Ford-Fulkerson se numeste “algoritmul Edmonds-Karp” si acesta are complexitatea O(V * E2).

O problema asemanatoare cu aceasta, dar putin mai compicata, este problema “min-cost flow” care pe langa fluxul maxim suportat de o muchie a retelei de transport mai apare si o valoare suplimentara asociata fiecarei muchii care este costul unei unitati de flux ce trece prin acea muchie si se incerca gasirea fluxului maxim prin graf astfel incat costul total sa fie minim. Pentru rezolvarea problemei fluxului maxim, din categoria problemelor de complexitate O(V3), exista si “algoritmul lui Golberg” denumit “preflow-push” care este la fel de simplu ca Ford-Fulkerson si ruleaza in timp O(V2 * E). Gasirea unui drum la un moment dat in reteaua reziduala este o problema greedy si ramane in continuare o problema deschisa existand diferite solutii care gasesc maximul in numar minim de pasi doar pentru anumite tipuri de retele de transport.


Page 8 of 49

Demonstrarea corectitudinii

In practica se utilizeaza capacitati care sunt numere intregi. Daca aceste ar fi rationale, atunci am face o scalare pentru a le aduce pe toate la valori intregi. Deci in cele ce urmeaza vom considera toate costurile din reteaua de transport initiala valori intregi si pozitive.

Demonstra complexitatii algoritmului este imediata:

gasirea unui drum de la S la D (in reteaua reziduala) are complexitatea in general (atat in cazul explorarii in adancime cat si in cazul explorarii in largime) O(E)

la un moment dat costul minim al unei muchii din drumul p este 1 ceea ce ne conduce la o executie a primului pas de maxim MF ori (unde MF este fluxul maxim gasit de algoritm)

Deci algoritmul Ford-Fulkerson ruleaza in timp O(E * MF) unde E este multimea muchiilor din reteaua de transport initiala si MF este fluxul maxim gasit de algoritm. Demonstrarea corectitudinii algoritmului: Lema: Fie G o retea de transport si f un flux in G, iar Gr graful rezidual al lui G in raport cu f. Atunci:

a) functia fr este un flux in Gr daca si numai daca f+fr este un flux in G b) valoarea functiei este aditiva: |f+fr| = |f| + |fr|


Page 9 of 49

Demonstratie:

a) fr flux echivalent cu:

orice u,v∈ V, fr (u,v)=-fr (v,u) si cum f(u,v)=-f(u,v) ⇔ (fr+f)(u,v)=(fr+f)(v,u) orice u∈ V-{S,D}, ∑fr (u,v)=0. Deoarece ∑f(u,v)=0 ⇔ ∑f(f+fr)(u,v)=0

v∈ V v∈ V v∈ V

orice u,v∈ V fr(u,v)<r(u,v) (r(u,v) este capacitatea reziduala a muchiei (u,v); costurile arcelor din Gr sunt de fapt fluxurile reziduale prin G) ⇒ (fr+f)(u,v)<(f+r)(u,v), adica (fr+f)(u,v)<c(u,v) Aceste trei afirmatii sunt echivalente cu faptul ca f+fr este flux in G.

b) Din definitia fluxului:

|f+fr|=∑ (f(s,v)+fr (s,v))= ∑f(s,v)+ ∑fr (s,v)=|f|+|fr|. v∈ V v∈ V v∈ V

Definitie: Fiind date un graf G si un flux f, numim cale marita un drum orientat de la S la D in graful rezidual Gr. Teorema: f este un flux maxim in G daca si numai daca nu exista o cale marita. Demonstratie:

“⇒ ” Presupunem ca avem p o cale marita s, u1, u2, …,

d si cp capacitatea sa reziduala. Definim urmatorul flux in graful G:

fr (ui,ui+1)=cp fr (ui+1,ui)=-cp, pentru 0<=i<n fr (u,v)=0, in rest Atunci fr este un flux in Gr; din lema avem ca f+fr

este un flux in G si, in plus, |f+fr|=|f|+|fr|>|f|, adica f nu este flux maxim, ceea ce este absurd.

“⇐ ”

Presupunem ca exista un alt flux fm cu |fm|>|f|. Atunci exista fr astfel incat fm=fr+f. Conform lemei,


Page 10 of 49

aceasta inseamna ca fr este un flux in Gr, deci exista un drum in Gr de la S la D, adica exista o cale marita, ceea ce este absurd.


Page 11 of 49

Pseudocod

FORD-FULKERSON(Graf G(V,E), Nod S, Nod D)

maxflow ⇐ 0 pentru fiecare muchie (u,v) ∈ E[G] executa

f[u,v] ⇐ 0 f[v,u] ⇐ 0

atat timp cat exista un drum p de la S la D in reteaua reziduala Gf executa cp ⇐ min { cf(u,v) | (u,v) ∈ p } maxflow ⇐ maxflow + cp pentru fiecare muchie (u,v) din p executa f[u,v] ⇐ f[u,v] + cp f[v,u] ⇐ f[u,v]

intoarce maxflow


Page 12 of 49


Page 13 of 49

Sursa JAVA

import java.util.*; import java.awt.*; import java.applet.Applet; //////////////// // class Node // //////////////// class Node { int x; int y; boolean selected = false; boolean mark = false; public void copy(Node n) { x = n.x; y = n.y; selected = n.selected; } } //////////////// // class Edge // //////////////// class Edge { int capacity = 0; boolean selected = false; final static int min = 1, max = 99; int flow = 0; boolean mark = false; boolean exist() { return (capacity > 0); } void set(int newcap) { if ((newcap > max) || (newcap < min)) { System.out.println("Capacity out of range");


Page 14 of 49

capacity = 1; } else capacity = newcap; if (flow > capacity) flow = capacity; } void set() { capacity = (int)(Math.random()*max); } int get() { return capacity; } void remove() { capacity = 0; } } //////////////// // class Mode // //////////////// class Mode { final static int run = 1; final static int edit = 2; final static int move = 1; final static int addnode = 2; final static int delnode = 3; final static int addedge = 4; final static int deledge = 5; final static int capacity = 6; } ////////////////////// // class GraphPanel // ////////////////////// class GraphPanel extends Panel { Graph parent; int nnodes=0; int MaxNode = 100; Node nodes[] = new Node[MaxNode]; int source = 1, sink = 2, maxflow=0; int nedges; Edge edges[][] = new Edge[MaxNode][MaxNode]; int mode = Mode.edit;


Page 15 of 49

int edit = Mode.move; GraphPanel(Graph parent) { this.parent = parent; int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) edges[i][j] = new Edge(); } void reset() { int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) { edges[i][j].capacity=0; edges[i][j].selected=false; edges[i][j].flow=0; edges[i][j].mark=false; } nnodes=0; } int addNode(int x, int y) { if (nnodes >= MaxNode -1) return -1; Node n = new Node(); n.x = x; n.y = y; nnodes++; nodes[nnodes] = n; sink = nnodes; return nnodes; } void addEdge(int from, int to) { edges[from][to].set(); } void addEdge(int from, int to, int cap) { edges[from][to].set(cap); } int FordFulkerson(int thesink, int u, int mont) { int v; int res=0;


Page 16 of 49

Edge e; if (u==thesink) return mont; nodes[u].mark = true; for (v=1; v<=nnodes && res==0; v++) if (!nodes[v].mark) { e = edges[u][v]; if (e.exist() && (e.flow < e.capacity)) { res = FordFulkerson(thesink, v, Math.min(mont, e.capacity - e.flow)); if (res>0) { e.mark = true; e.flow +=res; } } e = edges[v][u]; if (res==0 && e.exist() && e.flow > 0) { res = FordFulkerson(thesink, v, Math.min(mont, e.flow)); if (res>0) { e.mark = true; e.flow -=res; } } } nodes[u].mark = false; return res; } void initFlow() { maxflow=0; parent.flowlabel.setText(" maxflow:"+String.valueOf(maxflow)); for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j].flow = 0; } void removeEdgeMarks(){ for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j].mark = false; }


Page 17 of 49

void flowMax(int thesource, int thesink) { int res; if (mode==Mode.edit) mode = Mode.run; removeEdgeMarks(); maxflow+=FordFulkerson(thesink, thesource, Edge.max); parent.flowlabel.setText(" maxflow:"+String.valueOf(maxflow)); repaint(); } void flowMax_go(int thesource, int thesink) { int res, flow1 = 1; if (mode==Mode.edit) mode = Mode.run; removeEdgeMarks(); maxflow=0; while (flow1!=0) { flow1=FordFulkerson(thesink, thesource, Edge.max); maxflow+=flow1; }; parent.flowlabel.setText(" maxflow:"+String.valueOf(maxflow)); repaint(); } Image offscreen; Dimension offscreensize; Graphics offgraphics; final Color edgeColor = Color.black; final Color nodeColor = Color.cyan; final Color augmColor = Color.red; final Color numColor = Color.black; final Color nodeSelectedColor = Color.pink; final Color edgeSelectedColor = Color.pink; final Color sourceColor = Color.magenta; final Color sinkColor = Color.orange; final Color capacityColor = Color.blue; public void paintNode(Graphics g, int n, FontMetrics fm) { int x = nodes[n].x; int y = nodes[n].y;


Page 18 of 49

int r = 20; g.setColor(nodeColor); if (n==source) g.setColor(sourceColor); if (n==sink) g.setColor(sinkColor); if (nodes[n].selected) g.setColor(nodeSelectedColor); int w = fm.stringWidth(String.valueOf(n)); int h = fm.charWidth('M'); r = h*2; g.fillOval(x-r/2,y-r/2,r,r); g.setColor(Color.black); g.drawOval(x-r/2,y-r/2,r-1,r-1); g.setColor(numColor); g.drawString(String.valueOf(n), x - w/2, y+h/2); } public void paintEdge(Graphics g, int from, int to, FontMetrics fm) { int orig_x[] = { 0, -10, -8, -10, 0}; int orig_y[] = { 0, 4, 0, -4, 0}; int new_x[] = new int[orig_x.length]; int new_y[] = new int[orig_x.length]; int x1 = nodes[from].x, y1 = nodes[from].y, x2 = nodes[to].x, y2 = nodes[to].y; if (edges[from][to].selected) g.setColor(edgeSelectedColor); else if (edges[from][to].mark && mode==Mode.run) g.setColor(augmColor); else g.setColor(edgeColor); g.drawLine(x1,y1,x2,y2); double d = Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); double cosa = 1, sina = 0; if (d != 0) { cosa = (x2-x1) / d; sina = (y2-y1) / d; } int r = 2*fm.charWidth('M'); int b_x = x2 - (int)(0.5+ r/2*cosa); int b_y = y2 - (int)(0.5+ r/2*sina);


Page 19 of 49

for (int i=0; i<new_x.length; i++) { new_x[i] = (int)(0.5+ cosa*orig_x[i] - sina*orig_y[i]) +b_x; new_y[i] = (int)(0.5+ sina*orig_x[i] + cosa*orig_y[i]) +b_y; } Polygon poly = new Polygon(new_x, new_y, new_x.length); g.fillPolygon(poly); g.setColor(capacityColor); g.drawString(String.valueOf(edges[from][to].flow)+"/"+String.valueOf(edges[from][to].get()),(x1+x2)/2,(y1+y2)/2); } public synchronized void update(Graphics g) { paint(g); } public synchronized void paint(Graphics g) { Dimension d = size(); if ((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) { offscreen = createImage(d.width, d.height); offscreensize = d; offgraphics = offscreen.getGraphics(); offgraphics.setFont(getFont()); } offgraphics.setColor(getBackground()); offgraphics.fillRect(0, 0, d.width, d.height); FontMetrics fm = offgraphics.getFontMetrics(); g.setColor(edgeColor); for (int i = 1 ; i <= nnodes ; i++) for (int j = 1 ; j <= nnodes ; j++) if (edges[i][j].exist()) paintEdge(offgraphics,i,j,fm); for (int i = 1 ; i <= nnodes ; i++) paintNode(offgraphics, i, fm); g.drawImage(offscreen, 0, 0, null); } Node pickNode; private boolean changePosition(int x, int y) { double bestdist = Double.MAX_VALUE; for (int i = 1 ; i <= nnodes ; i++) { Node n = nodes[i]; double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y); if (dist < bestdist) {


Page 20 of 49

pickNode = n; bestdist = dist; } } if (bestdist <= 12*12) { pickNode.x = x; pickNode.y = y; pickNode.selected = true; return true; } else { pickNode = null; return false; } } private boolean removeNode(int x, int y) { int i; if (nnodes < 3) return false; double bestdist = Double.MAX_VALUE; int nodeToRemove = 0; for (i = 1 ; i <= nnodes ; i++) { Node n = nodes[i]; double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y); if (dist < bestdist) { nodeToRemove = i; bestdist = dist; } } if (bestdist <= 12*12) { for (i=1; i<= nnodes; i++) { edges[nodeToRemove][i].remove(); edges[i][nodeToRemove].remove(); } Edge tmp[] = edges[nodeToRemove]; for (i=nodeToRemove; i<nnodes; i++) edges[i] = edges[i+1]; edges[i] = tmp; for (int j=1; j<=nnodes; j++) { Edge e = edges[j][nodeToRemove]; for (i=nodeToRemove; i<nnodes; i++) edges[j][i] = edges[j][i+1]; edges[j][i] = e; } Node n=nodes[nodeToRemove];


Page 21 of 49

for (i=nodeToRemove; i<nnodes; i++) nodes[i] = nodes[i+1]; nodes[i] = n; nnodes--; sink--; return true; } else { return false; } } int from =0, to = 0; private boolean add_Edge(int x, int y) { double bestdist = Double.MAX_VALUE; int pick=0; for (int i = 1 ; i <= nnodes ; i++) { Node n = nodes[i]; double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y); if (dist < bestdist) { pick = i; bestdist = dist; } } if (bestdist <= 12*12) { if (from == 0) { from = pick; nodes[pick].selected = true; return true; } else { to = pick; if (from != to) { nodes[from].selected = false; if (edges[to][from].exist()) edges[to][from].remove(); addEdge(from,to); from = to = 0; } return true; } } else return false; }


Page 22 of 49

boolean inner(int x1, int x2, int y1, int y2, int x, int y) { return (((x-x1)*(x-x2) <= 0 ) && ((y-y1)*(y-y2) <= 0)); } private boolean removeEdge(int x, int y) { double bestdist = Double.MAX_VALUE; int picki = 0, pickj = 0; double x1=0, y1=0, x2=0, y2=0, a=0, b=0, c=0; for (int i = 1 ; i <= nnodes ; i++) for (int j = 1; j<= nnodes ; j++) { x1 = nodes[i].x; y1 = nodes[i].y; x2 = nodes[j].x; y2 = nodes[j].y; a = y1 - y2; b = x2 - x1; c = x1*y2 - x2*y1; if ((edges[i][j].exist()) && (a*a +b*b != 0) && inner((int)x1, (int)x2, (int)y1, (int)y2, x, y)) { double dist = Math.abs(a*x + b*y +c)/Math.sqrt(a*a+b*b); if (dist < bestdist) { picki = i; pickj = j; bestdist = dist; } } } if (bestdist <= 5) { edges[picki][pickj].remove(); return true; } else return false; } Edge pickEdge = null; int picki = 1, pickj = 1; private boolean changeCapacity(int x, int y) { double bestdist = Double.MAX_VALUE; double x1=0, y1=0, x2=0, y2=0, a=0, b=0, c=0; Edge oldPickEdge = pickEdge; for (int i = 1 ; i <= nnodes ; i++) for (int j = 1; j<= nnodes ; j++) { x1 = nodes[i].x;


Page 23 of 49

y1 = nodes[i].y; x2 = nodes[j].x; y2 = nodes[j].y; a = y1 - y2; b = x2 - x1; c = x1*y2 - x2*y1; if ((edges[i][j].exist()) && (a*a +b*b != 0) && inner((int)x1, (int)x2, (int)y1, (int)y2, x, y)) { double dist = Math.abs(a*x + b*y +c)/Math.sqrt(a*a+b*b); if (dist < bestdist) { picki = i; pickj = j; bestdist = dist; pickEdge = edges[picki][pickj]; } } } if (bestdist <= 5) { if (oldPickEdge != null) oldPickEdge.selected = false; pickEdge.selected = true; parent.cap.setValue(pickEdge.get()); parent.caplabel.setText(String.valueOf(pickEdge.get())); return true; } else return false; } public synchronized boolean mouseDown(Event evt, int x, int y) { mode = Mode.edit; switch (edit) { case Mode.move: if (changePosition(x,y)) repaint(); return true; case Mode.addnode: addNode(x,y); repaint(); return true; case Mode.delnode: if (removeNode(x,y)) repaint(); return true; case Mode.addedge: if (add_Edge(x,y)) repaint(); return true; case Mode.deledge: if (removeEdge(x,y)) repaint();


Page 24 of 49

return true; case Mode.capacity: if (changeCapacity(x,y)) repaint(); return true; default: System.out.println("Mad mode in MouseDown"); } return true; } public synchronized boolean mouseDrag(Event evt, int x, int y) { if (pickNode == null) return true; if (!inside(x,y)) return true; pickNode.x = x; pickNode.y = y; repaint(); return true; } public synchronized boolean mouseUp(Event evt, int x, int y) { if (pickNode == null) return true; pickNode.x = x; pickNode.y = y; pickNode.selected = false; pickNode = null; repaint(); return true; } public void demo(int demono) { nnodes=0; switch (demono){ case 0: addNode(200,50); addNode(50,150); addNode(350,150); addNode(200,250); addEdge(1,2,50); addEdge(1,3,50); addEdge(2,4,50); addEdge(3,4,50); addEdge(2,3,1);


Page 25 of 49

source=1; sink=4; break; case 1: addNode(50,200); addNode(100,80); addNode(200,40); addNode(250,300); addNode(350,170); addEdge(1,2,5); addEdge(2,3,4); addEdge(3,5,9); addEdge(1,5,6); addEdge(1,4,5); addEdge(4,5,7); addEdge(3,4,8); source=1; sink=5; break; case 2: addNode(200,25); addNode(100,125); addNode(300,125); addNode(100,225); addNode(300,225); addNode(200,325); addEdge(1,2,3); addEdge(1,3,2); addEdge(2,3,1); addEdge(2,5,4); addEdge(2,4,3); addEdge(3,5,2); addEdge(4,6,2); addEdge(5,6,3); source=1; sink=6; break; case 3: addNode(10,200); addNode(55,100); addNode(55,300); addNode(100,200);


Page 26 of 49

addNode(145,100); addNode(145,300); addNode(190,200); addNode(235,100); addNode(235,300); addNode(280,200); addNode(360,200); addEdge(1,2,1); addEdge(1,3,6); addEdge(1,4,4); addEdge(4,2,3); addEdge(3,4,2); addEdge(2,7,2); addEdge(4,7,3); addEdge(3,7,1); addEdge(2,5,2); addEdge(3,6,6); addEdge(6,7,2); addEdge(5,8,2); addEdge(6,9,6); addEdge(7,8,2); addEdge(7,10,3); addEdge(7,9,3); addEdge(9,10,1); addEdge(10,8,1); addEdge(8,11,4); addEdge(10,11,3); addEdge(9,11,4); source=1; sink=11; break; case 4: addNode(10,200); addNode(100,100); addNode(100,300); addNode(190,200); addNode(275,100); addNode(275,300); addNode(360,200); addEdge(1,2,5); addEdge(1,4,3);


Page 27 of 49

addEdge(1,3,2); addEdge(2,4,2); addEdge(2,7,3); addEdge(2,5,1); addEdge(5,7,1); addEdge(4,7,7); addEdge(4,3,7); addEdge(3,7,2); addEdge(3,6,6); addEdge(6,7,1); source=1; sink=7; break; case 5: addNode(20,185); addNode(90,25); addNode(90,105); addNode(90,185); addNode(90,265); addNode(90,345); addNode(300,40); addNode(160,10); addNode(230,360); addNode(300,330); addNode(370,185); addEdge(1,2,3); addEdge(1,3,6); addEdge(1,4,9); addEdge(1,5,6); addEdge(1,6,3); addEdge(2,7,5); addEdge(8,2,3); addEdge(2,9,5); addEdge(10,2,3); addEdge(7,3,3); addEdge(3,8,4); addEdge(9,3,3); addEdge(3,10,4); addEdge(4,7,2); addEdge(8,4,1); addEdge(4,9,2);


Page 28 of 49

addEdge(10,4,1); addEdge(7,5,4); addEdge(5,8,3); addEdge(9,5,4); addEdge(5,10,3); addEdge(6,7,3); addEdge(8,6,5); addEdge(6,9,3); addEdge(10,6,5); addEdge(7,11,10); addEdge(8,11,5); addEdge(9,11,5); addEdge(10,11,10); source=1; sink=11; break; case 6: addNode(170,150); addNode(85,100); addNode(30,200); addNode(85,300); addNode(305,100); addNode(360,200); addNode(305,300); addNode(195,80); addNode(195,320); addNode(220,250); addEdge(1,2,6); addEdge(1,3,10); addEdge(1,4,6); addEdge(2,4,1); addEdge(3,8,6); addEdge(9,3,4); addEdge(3,2,8); addEdge(8,2,4); addEdge(3,4,3); addEdge(4,9,6); addEdge(5,10,5); addEdge(6,10,10);


Page 29 of 49

addEdge(7,10,5); addEdge(7,5,1); addEdge(5,6,4); addEdge(7,6,6); addEdge(8,6,3); addEdge(6,9,5); addEdge(9,7,7); addEdge(5,8,7); addEdge(8,9,10); source=1; sink=10; break; case 7: addNode(10,10); addNode(380,10); addNode(10,360); addNode(380,360); source=1; sink=4; break; } } } ///////////////// // class Graph // ///////////////// public class Graph extends Applet { GraphPanel panelGraph; Scrollbar cap = new Scrollbar(Scrollbar.HORIZONTAL,1,0,Edge.min, Edge.max); Label caplabel = new Label("1 "); Label flowlabel = new Label(" maxflow:0"); Choice cbg=new Choice(); Choice demono=new Choice(); Panel panelControl1 = new Panel();


Page 30 of 49

Panel panelControl2 = new Panel(); int demo=0; public void init() { setLayout(new BorderLayout(5,5)); panelGraph = new GraphPanel(this); add("Center", panelGraph); add("North", panelControl1); add("South", panelControl2); cbg.add("Change Position"); cbg.add("Add Node"); cbg.add("Remove Node"); cbg.add("Add Edge"); cbg.add("Remove Edge"); cbg.add("Change Capacity"); demono.add("Demo1"); demono.add("Demo2"); demono.add("Demo3"); demono.add("Demo4"); demono.add("Demo5"); demono.add("Demo6"); demono.add("Demo7"); panelControl1.add(cbg); panelControl1.add(new Label(" ")); panelControl1.add(demono); panelControl1.add(new Button("Schimba")); panelControl2.add(caplabel); panelControl2.add(cap); panelControl2.add(new Label(" ")); panelControl2.add(new Button("Step")); panelControl2.add(new Label("")); panelControl2.add(new Button("Go")); panelControl2.add(new Label(" ")); panelControl2.add(new Button("Init")); panelControl2.add(flowlabel); panelGraph.demo(0); repaint(); } public boolean handleEvent(Event evt) {


Page 31 of 49

if (evt.target instanceof Scrollbar) { int v = cap.getValue(); caplabel.setText(String.valueOf(v)); if (panelGraph.pickEdge != null) { panelGraph.pickEdge.set(v); panelGraph.repaint(); } return false; } else { if ((evt.target instanceof Checkbox) || (evt.target instanceof Button)) { if (panelGraph.pickEdge != null) panelGraph.pickEdge.selected = false; panelGraph.pickEdge = null; panelGraph.repaint(); } return super.handleEvent(evt); } } public boolean action(Event evt, Object arg) { switch (cbg.getSelectedIndex()){ case 0: panelGraph.edit=Mode.move;break; case 1: panelGraph.edit=Mode.addnode;break; case 2: panelGraph.edit=Mode.delnode;break; case 3: panelGraph.edit=Mode.addedge;break; case 4: panelGraph.edit=Mode.deledge;break; case 5: panelGraph.edit=Mode.capacity;break; }; demo=demono.getSelectedIndex(); if ("Schimba".equals(arg)) { panelGraph.reset(); panelGraph.initFlow(); panelGraph.mode = Mode.edit; switch(demo){ case 0:panelGraph.demo(0);break; case 1:panelGraph.demo(1);break; case 2:panelGraph.demo(2);break; case 3:panelGraph.demo(3);break; case 4:panelGraph.demo(4);break; case 5:panelGraph.demo(5);break; case 6:panelGraph.demo(6);break; }; repaint(); };


Page 32 of 49

if (panelGraph.edit != Mode.addedge) if (panelGraph.from != 0) { panelGraph.nodes[panelGraph.from].selected = false; panelGraph.from = 0; panelGraph.repaint(); } if ("Init".equals(arg)) { panelGraph.initFlow(); panelGraph.mode = Mode.edit; panelGraph.repaint(); return true; } if ("Step".equals(arg)) { panelGraph.flowMax(panelGraph.source, panelGraph.sink); return true; } if ("Go".equals(arg)) { panelGraph.flowMax_go(panelGraph.source, panelGraph.sink); return true; } return false; } }


Page 33 of 49


Page 34 of 49

Sursa C++

#include <stdio.h> #include <values.h> #include <math.h> #define boolean int #define false 0 #define true 1 #define MaxNode 50 #define EDGE_MAX 99 #define min(x,y) ((x>y)?y:x) //////////////// // class Mode // //////////////// struct { int run; int edit; int move; int addnode; int delnode; int addedge; int deledge; int capacity; } Mode; //////////////// // class Color // //////////////// struct { int black; int cyan; int red; int pink; int magenta; int orange; int blue; } Color;


Page 35 of 49

//////////////// // class Node // //////////////// class Node { friend FF; boolean selected; boolean mark; Node() { selected=false; mark=false; }; }; //////////////// // class Edge // //////////////// class Edge { public: friend FF; int capacity; boolean selected; int min, max; int flow; boolean mark; boolean exist() { return (capacity > 0); } Edge(){ capacity = 0; selected = false; min=1;max=EDGE_MAX; flow=0; mark=false; } void set(int newcap) { if ((newcap > max) || (newcap < min)) { printf("Capacity out of range"); capacity = 1; } else capacity = newcap; if (flow > capacity) flow = capacity;


Page 36 of 49

} }; ////////////// // class FF // ////////////// class FF { public: int nnodes; Node *nodes[MaxNode]; int source, sink, maxflow; Edge *edges[MaxNode][MaxNode]; int mode; int edit; void reset(); int addNode() { if (nnodes >= MaxNode -1) return -1; Node *n = new Node(); nnodes++; nodes[nnodes] = n; sink = nnodes; return nnodes; }; void addEdge(int from, int to, int cap) { edges[from][to]->set(cap); } FF(); int FF::FordFulkerson(int thesink, int u, int mont); void initFlow(); void removeEdgeMarks(); void flowMax_go(int thesource, int thesink); void display(); }; FF::FF() {


Page 37 of 49

nnodes=0; source = 1; sink = 2; maxflow=0;mode = Mode.edit;edit = Mode.move;

int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) edges[i][j] = new Edge(); }; void FF::reset() { int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) { edges[i][j]->capacity=0; edges[i][j]->selected=false; edges[i][j]->flow=0; edges[i][j]->mark=false; } nnodes=0; }; int FF::FordFulkerson(int thesink, int u, int mont) { int v; int res=0; Edge *e; if (u==thesink) return mont; nodes[u]->mark = true; for (v=1; v<=nnodes && res==0; v++) if (!nodes[v]->mark) { e = edges[u][v]; if (e->exist() && (e->flow < e->capacity)) { res = FordFulkerson(thesink, v, min(mont, e->capacity - e->flow)); if (res>0) { e->mark = true; e->flow +=res; } } e = edges[v][u]; if (res==0 && e->exist() && e->flow > 0) { res = FordFulkerson(thesink, v,min(mont, e->flow)); if (res>0) { e->mark = true; e->flow -=res; } }


Page 38 of 49

} nodes[u]->mark = false; return res; }; void FF::initFlow() { maxflow=0; for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j]->flow = 0; }; void FF::removeEdgeMarks(){ for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j]->mark = false; }; void FF::flowMax_go(int thesource, int thesink) { int flow1 = 1; if (mode==Mode.edit) mode = Mode.run; removeEdgeMarks(); maxflow=0; while (flow1!=0) { flow1=FordFulkerson(thesink, thesource, EDGE_MAX); maxflow+=flow1; }; }; void FF::display(){ for (int i=1;i<=nnodes;i++){ for (int k=1;k<=nnodes;k++) printf("%d/%d ",edges[i][k]->flow,edges[i][k]-

>capacity); printf("\n"); }; printf("\n"); }; ////////// // Demo // ////////// class Demo{ public: Demo(); };


Page 39 of 49

void Demo::Demo(){ FF myGraph; myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addEdge(1,2,3); myGraph.addEdge(1,3,3); myGraph.addEdge(2,4,2); myGraph.addEdge(3,4,2); myGraph.addEdge(2,3,1); myGraph.addEdge(5,2,1); myGraph.addEdge(3,5,1); myGraph.addEdge(5,4,1); myGraph.addEdge(5,6,3); myGraph.addEdge(4,6,4); myGraph.source=1; myGraph.sink=6; myGraph.initFlow(); myGraph.flowMax_go(myGraph.source, myGraph.sink); myGraph.display(); }; void main(){ Demo demo; };


Page 40 of 49


Page 41 of 49

Sursa C++ parametrizat

#include <stdio.h> #include <values.h> #include <math.h> #define boolean int #define false 0 #define true 1 #define MaxNode 50 #define min 1 #define max 99 #define minim(x,y) ((x>y)?y:x) //////////////// // class Mode // //////////////// struct { int run; int edit; int move; int addnode; int delnode; int addedge; int deledge; int capacity; } Mode; //////////////// // class Color // //////////////// struct { int black; int cyan;


Page 42 of 49

int red; int pink; int magenta; int orange; int blue; } Color; //////////////// // class Node // //////////////// template <class B> class Node { friend FF; B selected; B mark; Node() { selected=false; mark=false; }; }; //////////////// // class Edge // //////////////// template <class T,class B> class Edge { public: friend FF; T capacity; T flow; B selected; B mark; boolean exist() { return (capacity > 0); } Edge(){ capacity = 0; selected = false; flow=0;


Page 43 of 49

mark=false; } void set(int newcap) { if ((newcap > max) || (newcap < min)) { printf("Capacity out of range"); capacity = 1; } else capacity = newcap; if (flow > capacity) flow = capacity; } }; ////////////// // class FF // ////////////// class FF { public: int nnodes; Node<boolean> *nodes[MaxNode]; int source, sink, maxflow; Edge<int,boolean> *edges[MaxNode][MaxNode]; int mode; int edit; void reset(); int addNode() { if (nnodes >= MaxNode -1) return -1; Node<boolean> *n = new Node<boolean>(); nnodes++; nodes[nnodes] = n; sink = nnodes; return nnodes; }; void addEdge(int from, int to, int cap) { edges[from][to]->set(cap); } FF(); int FF::FordFulkerson(int thesink, int u, int mont);


Page 44 of 49

void initFlow(); void removeEdgeMarks(); void flowMax_go(int thesource, int thesink); void display(); }; FF::FF() { nnodes=0; source = 1; sink = 2; maxflow=0;mode =

Mode.edit;edit = Mode.move; int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) edges[i][j] = new Edge<int,boolean>(); }; void FF::reset() { int i, j; for (i=1;i<MaxNode;i++) for (j=1;j<MaxNode;j++) { edges[i][j]->capacity=0; edges[i][j]->selected=false; edges[i][j]->flow=0; edges[i][j]->mark=false; } nnodes=0; }; int FF::FordFulkerson(int thesink, int u, int mont) { int v; int res=0; Edge<int,boolean> *e; if (u==thesink) return mont; nodes[u]->mark = true; for (v=1; v<=nnodes && res==0; v++) if (!nodes[v]->mark) { e = edges[u][v]; if (e->exist() && (e->flow < e->capacity)) { res = FordFulkerson(thesink, v, minim(mont, e-

>capacity - e->flow));


Page 45 of 49

if (res>0) { e->mark = true; e->flow +=res; } } e = edges[v][u]; if (res==0 && e->exist() && e->flow > 0) { res = FordFulkerson(thesink, v,minim(mont, e-

>flow)); if (res>0) { e->mark = true; e->flow -=res; } } } nodes[u]->mark = false; return res; }; void FF::initFlow() { maxflow=0; for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j]->flow = 0; }; void FF::removeEdgeMarks(){ for (int i = 1; i<= nnodes; i++) for (int j = 1; j <= nnodes; j++) edges[i][j]->mark = false; }; void FF::flowMax_go(int thesource, int thesink) { int flow1 = 1; if (mode==Mode.edit) mode = Mode.run; removeEdgeMarks(); maxflow=0; while (flow1!=0) { flow1=FordFulkerson(thesink, thesource, max); maxflow+=flow1; }; }; void FF::display(){


Page 46 of 49

for (int i=1;i<=nnodes;i++){ for (int k=1;k<=nnodes;k++) printf("%d/%d

",edges[i][k]->flow,edges[i][k]->capacity); printf("\n"); }; printf("\n"); }; ////////// // Demo // ////////// class Demo{ public: Demo(); }; Demo::Demo(){ FF myGraph; myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addNode(); myGraph.addEdge(1,2,3); myGraph.addEdge(1,3,3); myGraph.addEdge(2,4,2); myGraph.addEdge(3,4,2); myGraph.addEdge(2,3,1); myGraph.addEdge(5,2,1); myGraph.addEdge(3,5,1); myGraph.addEdge(5,4,1); myGraph.addEdge(5,6,3); myGraph.addEdge(4,6,4); myGraph.source=1; myGraph.sink=6; myGraph.initFlow(); myGraph.flowMax_go(myGraph.source, myGraph.sink); myGraph.display();


Page 47 of 49

}; void main(){ Demo demo; };


Page 48 of 49

Referinte

T. Cormen, C. Leiserson and R. Rivest, Introduction to Algorithms, The MIT Press, 1990

Dorit S.Hochbaum and Dr Olivier Goldschmidt, Algorithms,

1997

B. V. Cherkassky and A. V. Goldberg, On Implementing the Push-Relabel Method for the Maximum Flow Problem, Algorithmica, 1997

Algorithmic Solutions Software GmbH, Saarbrücken, 1999


Page 49 of 49

Algoritmul Ford Fulkerson

Documents

Transcript of Algoritmul Ford Fulkerson