Algorithme de Ford-Fulkerson
Graph.py
1 """
2 Structure of a graph
3
4 Copyright 20040525 STRASSER Michel
5 """
6
7 from Vertex import Vertex
8 from Arc import Arc
9
10 class Graph:
11
12 def __init__(self):
13 self.verticesList=[]
14 self.verticesHash={}
15 self.arcsList=[]
16
17 def addVertex(self, vertexId, vertexX, vertexY):
18 vertex=Vertex(vertexId, vertexX, vertexY)
19 self.verticesList.append(vertex)
20 self.verticesHash[vertex.id]=vertex
21
22 def addArc(self, fromId, toId, flow, capacity, cost):
23 fromV=self.verticesHash[fromId]
24 toV=self.verticesHash[toId]
25 arc=Arc(fromV, toV, flow, capacity, cost)
26 self.arcsList.append(arc)
27 fromV.outgoingArcs.append(arc)
28 toV.incomingArcs.append(arc)
29
30 def __repr__(self):
31 return "Graph .arcsList=" + str(self.arcsList)
32
Vertex.py
1 class Vertex:
2 def __init__(self, id, x, y):
3 self.id=id
4 self.x=x
5 self.y=y
6 self.incomingArcs=[]
7 self.outgoingArcs=[]
8 self.delta=10L**9L # infinite, Python supports very long numbers but we don't need here them 10**4 may be sufficient
9 self.markedArc=0
10
11 def __repr__(self):
12 return "Vertex .id='" + self.id + "' .delta='" + str(self.delta) + "' .markedArc='" + str(self.markedArc) + "'"
13
14
Arc_old.py
1 """
2 Structure of an arc
3
4 Copyright 20040525 STRASSER Michel
5 """
6
7 class Arc:
8 def __init__(self, fromV, toV, flow, capacity, cost):
9 self.fromV=fromV
10 self.toV=toV
11 self.flow=flow
12 self.capacity=capacity
13 self.cost=cost
14
15 def __repr__(self):
16 return "Arc .fromV='" + self.fromV.id + "' .toV='" + self.toV.id + "' .flow='" + str(self.flow) + "' .capacity='" + str(self.capacity) + "' .cost='" + str(self.cost) + "'"
17
Maximum Flow.py
1 """
2 Algorithm of Ford-Fulkerson
3
4 Copyright 20040525 STRASSER Michel
5 """
6
7 class MaximumFlow:
8
9 def __init__(self, graph):
10 self.graph=graph
11 self.Y=0
12 self.CPlus=[]
13 self.CMin=[]
14 self.s=self.graph.verticesHash["SOURCE"]
15 self.p=self.graph.verticesHash["SINK"]
16
17
18 def directMarking(self):
19
20 # searching u=(x, y) in U (different of u_r) with x in Y, y not in Y and f(u)<C(u)
21 found=0
22 for x in self.Y:
23 for u in x.outgoingArcs:
24 y=u.toV
25 if y not in self.Y and u.flow<u.capacity:
26 found=1
27 self.Y.append(y)
28 y.delta=min(x.delta, u.capacity - u.flow)
29 y.markedArc=u # FIXME ?
30 print "x: ", x.id, "x.delta", x.delta
31 print "y: ", y.id, "y.delta", y.delta
32 print self.Y
33 print u
34 break
35 if(found):
36 break
37 return found
38
39
40 def indirectMarking(self):
41 # searching u=(y, x) in U with x in Y, y not in Y and f(u)>0
42 found=0
43 for x in self.Y:
44 for u in x.incomingArcs:
45 y=u.fromV
46 if y not in self.Y and u.flow>0:
47 found=1
48 self.Y.append(y)
49 y.delta=min(x.delta, u.flow)
50 y.markedArc=u
51 print "x: ", x
52 print "y: ", y
53 print self.Y
54 print u
55 break
56 if(found):
57 break
58 return found
59
60 def exhibFoundWay(self):
61 self.CPlus=[] # ignore u_r
62 self.CMin=[]
63
64 print "exhibFoundWay"
65 x=self.p
66
67 while(x != self.s):
68 print "in while"
69 u=x.markedArc
70 if(not u):
71 print "This should not happen"
72 break # this should not happen
73 if(x==u.toV):
74 self.CPlus.append(u)
75 x=u.fromV
76 else:
77 self.CMin.append(u)
78 x=u.toV
79
80 def adjustFlow(self):
81 epsilon=self.p.delta
82 print "epsilon : ", epsilon
83 print "self.CPlus : ", self.CPlus
84 print "self.CMin : ", self.CMin
85 for u in self.CPlus:
86 u.flow+=epsilon
87 for u in self.CMin:
88 u.flow-=epsilon
89
90 def apply(self):
91 self.Y=[self.s]
92
93 while((self.p not in self.Y) and (self.directMarking() or self.indirectMarking())):
94 pass
95
96 print "Continuing ..."
97
98 if(self.p not in self.Y):
99 print "found optimal flow"
100 else:
101 self.exhibFoundWay()
102 self.adjustFlow()
103 self.apply()
104
105
106
index
