Adaptation de Ford-Fulkerson pour l'optimalite
1 """
2 Algorithm of Ford-Fulkerson serialiser modified for minimal cost
3
4 Copyright 20040526 STRASSER Michel
5 """
6
7 from GrhWriter import GrhWriter
8 from BFForFF import BFForFF
9
10 class FFMinimalCost:
11
12 def __init__(self, graph):
13 self.graph=graph
14 self.Y=0
15 self.CPlus=[]
16 self.CMin=[]
17 self.s=self.graph.verticesHash["SOURCE"]
18 self.p=self.graph.verticesHash["SINK"]
19 self.n=0 # iteration
20
21 def findWay(self):
22 print "finding way"
23 bellman=BFForFF(self.graph)
24 return bellman.do()
25
26 def exhibFoundWay(self):
27 self.CPlus=[] # ignore u_r
28 self.CMin=[]
29 self.delta=100000000000 # infinite
30
31 print "exhibFoundWay"
32 x=self.s
33
34 while(x != self.p):
35 print "Way2"
36 if(x.bfNextArcType==2): # A normal arc
37 print "-> ", x.id
38 cdelta=x.bfNextArc.cUPlus()
39 self.CPlus.append(x.bfNextArc)
40 elif(x.bfNextArcType==1): # A come back arc
41 print "<- ", x.id
42 cdelta=x.bfNextArc.cUMin()
43 self.CMin.append(x.bfNextArc)
44 else:
45 print "arcType is ", str(x.bfNextArcType)
46 self.delta=min(self.delta, cdelta)
47 x=x.bfNext
48
49 def adjustFlow(self):
50 epsilon=self.delta
51 print "epsilon : ", epsilon
52 print "self.CPlus : ", self.CPlus
53 print "self.CMin : ", self.CMin
54 for u in self.CPlus:
55 u.flow+=epsilon
56 for u in self.CMin:
57 u.flow-=epsilon
58
59 def apply(self):
60 writer=GrhWriter(self.graph)
61 writer.write("serial_" + str(self.n) + ".grh")
62 self.n=self.n + 1
63 self.Y=[self.s]
64
65 if(not self.findWay()):
66 print "found optimal flow (or error)"
67 else:
68 print "Continuing ..."
69 self.exhibFoundWay()
70 if self.delta==0:
71 return
72 self.adjustFlow()
73 self.apply()
74
L'étape de marquage se trouve contenu dans Bellman pour FF.
index
