Add a cost scaling min cost flow algorithm.
Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
1 %!PS-Adobe-2.0 EPSF-2.0
3 %%Creator: gnuplot 4.0 patchlevel 0
4 %%CreationDate: Sat May 13 18:29:57 2006
5 %%DocumentFonts: (atend)
6 %%BoundingBox: 50 50 338 251
7 %%Orientation: Portrait
13 /gnulinewidth 5.000 def
14 /userlinewidth gnulinewidth def
26 /N {newpath moveto} bind def
27 /C {setrgbcolor} bind def
28 /f {rlineto fill} bind def
31 /Lshow { currentpoint stroke M
33 /Rshow { currentpoint stroke M
34 dup stringwidth pop neg vshift R show } def
35 /Cshow { currentpoint stroke M
36 dup stringwidth pop -2 div vshift R show } def
37 /UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def
38 /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def
39 /DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
40 {pop pop pop 0 setgray Solid {pop []} if 0 setdash} ifelse } def
41 /BL { stroke userlinewidth 2 mul setlinewidth
42 Rounded { 1 setlinejoin 1 setlinecap } if } def
43 /AL { stroke userlinewidth 2 div setlinewidth
44 Rounded { 1 setlinejoin 1 setlinecap } if } def
45 /UL { dup gnulinewidth mul /userlinewidth exch def
46 dup 1 lt {pop 1} if 10 mul /udl exch def } def
47 /PL { stroke userlinewidth setlinewidth
48 Rounded { 1 setlinejoin 1 setlinecap } if } def
49 /LTw { PL [] 1 setgray } def
50 /LTb { BL [] 0 0 0 DL } def
51 /LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def
52 /LT0 { PL [] 1 0 0 DL } def
53 /LT1 { PL [4 dl 2 dl] 0 1 0 DL } def
54 /LT2 { PL [2 dl 3 dl] 0 0 1 DL } def
55 /LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
56 /LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
57 /LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
58 /LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
59 /LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
60 /LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def
61 /Pnt { stroke [] 0 setdash
62 gsave 1 setlinecap M 0 0 V stroke grestore } def
63 /Dia { stroke [] 0 setdash 2 copy vpt add M
64 hpt neg vpt neg V hpt vpt neg V
65 hpt vpt V hpt neg vpt V closepath stroke
67 /Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V
69 hpt neg vpt neg R hpt2 0 V stroke
71 /Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
72 0 vpt2 neg V hpt2 0 V 0 vpt2 V
73 hpt2 neg 0 V closepath stroke
75 /Crs { stroke [] 0 setdash exch hpt sub exch vpt add M
76 hpt2 vpt2 neg V currentpoint stroke M
77 hpt2 neg 0 R hpt2 vpt2 V stroke } def
78 /TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
79 hpt neg vpt -1.62 mul V
81 hpt neg vpt 1.62 mul V closepath stroke
83 /Star { 2 copy Pls Crs } def
84 /BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M
85 0 vpt2 neg V hpt2 0 V 0 vpt2 V
86 hpt2 neg 0 V closepath fill } def
87 /TriUF { stroke [] 0 setdash vpt 1.12 mul add M
88 hpt neg vpt -1.62 mul V
90 hpt neg vpt 1.62 mul V closepath fill } def
91 /TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M
92 hpt neg vpt 1.62 mul V
94 hpt neg vpt -1.62 mul V closepath stroke
96 /TriDF { stroke [] 0 setdash vpt 1.12 mul sub M
97 hpt neg vpt 1.62 mul V
99 hpt neg vpt -1.62 mul V closepath fill} def
100 /DiaF { stroke [] 0 setdash vpt add M
101 hpt neg vpt neg V hpt vpt neg V
102 hpt vpt V hpt neg vpt V closepath fill } def
103 /Pent { stroke [] 0 setdash 2 copy gsave
104 translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
105 closepath stroke grestore Pnt } def
106 /PentF { stroke [] 0 setdash gsave
107 translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
108 closepath fill grestore } def
109 /Circle { stroke [] 0 setdash 2 copy
110 hpt 0 360 arc stroke Pnt } def
111 /CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def
112 /C0 { BL [] 0 setdash 2 copy moveto vpt 90 450 arc } bind def
113 /C1 { BL [] 0 setdash 2 copy moveto
114 2 copy vpt 0 90 arc closepath fill
115 vpt 0 360 arc closepath } bind def
116 /C2 { BL [] 0 setdash 2 copy moveto
117 2 copy vpt 90 180 arc closepath fill
118 vpt 0 360 arc closepath } bind def
119 /C3 { BL [] 0 setdash 2 copy moveto
120 2 copy vpt 0 180 arc closepath fill
121 vpt 0 360 arc closepath } bind def
122 /C4 { BL [] 0 setdash 2 copy moveto
123 2 copy vpt 180 270 arc closepath fill
124 vpt 0 360 arc closepath } bind def
125 /C5 { BL [] 0 setdash 2 copy moveto
128 2 copy vpt 180 270 arc closepath fill
129 vpt 0 360 arc } bind def
130 /C6 { BL [] 0 setdash 2 copy moveto
131 2 copy vpt 90 270 arc closepath fill
132 vpt 0 360 arc closepath } bind def
133 /C7 { BL [] 0 setdash 2 copy moveto
134 2 copy vpt 0 270 arc closepath fill
135 vpt 0 360 arc closepath } bind def
136 /C8 { BL [] 0 setdash 2 copy moveto
137 2 copy vpt 270 360 arc closepath fill
138 vpt 0 360 arc closepath } bind def
139 /C9 { BL [] 0 setdash 2 copy moveto
140 2 copy vpt 270 450 arc closepath fill
141 vpt 0 360 arc closepath } bind def
142 /C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill
144 2 copy vpt 90 180 arc closepath fill
145 vpt 0 360 arc closepath } bind def
146 /C11 { BL [] 0 setdash 2 copy moveto
147 2 copy vpt 0 180 arc closepath fill
149 2 copy vpt 270 360 arc closepath fill
150 vpt 0 360 arc closepath } bind def
151 /C12 { BL [] 0 setdash 2 copy moveto
152 2 copy vpt 180 360 arc closepath fill
153 vpt 0 360 arc closepath } bind def
154 /C13 { BL [] 0 setdash 2 copy moveto
155 2 copy vpt 0 90 arc closepath fill
157 2 copy vpt 180 360 arc closepath fill
158 vpt 0 360 arc closepath } bind def
159 /C14 { BL [] 0 setdash 2 copy moveto
160 2 copy vpt 90 360 arc closepath fill
161 vpt 0 360 arc } bind def
162 /C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill
163 vpt 0 360 arc closepath } bind def
164 /Rec { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto
165 neg 0 rlineto closepath } bind def
166 /Square { dup Rec } bind def
167 /Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def
168 /S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def
169 /S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def
170 /S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
171 /S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def
172 /S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
173 /S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill
174 exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
175 /S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def
176 /S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill
177 2 copy vpt Square fill
179 /S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def
180 /S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def
181 /S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill
183 /S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill
185 /S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def
186 /S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
187 2 copy vpt Square fill Bsquare } bind def
188 /S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
189 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
190 /S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def
191 /D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def
192 /D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def
193 /D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def
194 /D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def
195 /D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def
196 /D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def
197 /D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def
198 /D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def
199 /D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def
200 /D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def
201 /D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def
202 /D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def
203 /D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def
204 /D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def
205 /D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def
206 /D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def
207 /DiaE { stroke [] 0 setdash vpt add M
208 hpt neg vpt neg V hpt vpt neg V
209 hpt vpt V hpt neg vpt V closepath stroke } def
210 /BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M
211 0 vpt2 neg V hpt2 0 V 0 vpt2 V
212 hpt2 neg 0 V closepath stroke } def
213 /TriUE { stroke [] 0 setdash vpt 1.12 mul add M
214 hpt neg vpt -1.62 mul V
216 hpt neg vpt 1.62 mul V closepath stroke } def
217 /TriDE { stroke [] 0 setdash vpt 1.12 mul sub M
218 hpt neg vpt 1.62 mul V
220 hpt neg vpt -1.62 mul V closepath stroke } def
221 /PentE { stroke [] 0 setdash gsave
222 translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
223 closepath stroke grestore } def
224 /CircE { stroke [] 0 setdash
225 hpt 0 360 arc stroke } def
226 /Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def
227 /DiaW { stroke [] 0 setdash vpt add M
228 hpt neg vpt neg V hpt vpt neg V
229 hpt vpt V hpt neg vpt V Opaque stroke } def
230 /BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M
231 0 vpt2 neg V hpt2 0 V 0 vpt2 V
232 hpt2 neg 0 V Opaque stroke } def
233 /TriUW { stroke [] 0 setdash vpt 1.12 mul add M
234 hpt neg vpt -1.62 mul V
236 hpt neg vpt 1.62 mul V Opaque stroke } def
237 /TriDW { stroke [] 0 setdash vpt 1.12 mul sub M
238 hpt neg vpt 1.62 mul V
240 hpt neg vpt -1.62 mul V Opaque stroke } def
241 /PentW { stroke [] 0 setdash gsave
242 translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
243 Opaque stroke grestore } def
244 /CircW { stroke [] 0 setdash
245 hpt 0 360 arc Opaque stroke } def
246 /BoxFill { gsave Rec 1 setgray fill grestore } def
251 /ColB exch def /ColG exch def /ColR exch def
252 /ColR ColR Fillden mul Fillden sub 1 add def
253 /ColG ColG Fillden mul Fillden sub 1 add def
254 /ColB ColB Fillden mul Fillden sub 1 add def
255 ColR ColG ColB setrgbcolor
258 % PostScript Level 1 Pattern Fill routine
259 % Usage: x y w h s a XX PatternFill
260 % x,y = lower left corner of box to be filled
261 % w,h = width and height of box
262 % a = angle in degrees between lines and x-axis
263 % XX = 0/1 for no/yes cross-hatch
265 /PatternFill { gsave /PFa [ 9 2 roll ] def
266 PFa 0 get PFa 2 get 2 div add PFa 1 get PFa 3 get 2 div add translate
267 PFa 2 get -2 div PFa 3 get -2 div PFa 2 get PFa 3 get Rec
268 gsave 1 setgray fill grestore clip
269 currentlinewidth 0.5 mul setlinewidth
270 /PFs PFa 2 get dup mul PFa 3 get dup mul add sqrt def
271 0 0 M PFa 5 get rotate PFs -2 div dup translate
272 0 1 PFs PFa 4 get div 1 add floor cvi
273 { PFa 4 get mul 0 M 0 PFs V } for
275 0 1 PFs PFa 4 get div 1 add floor cvi
276 { PFa 4 get mul 0 2 1 roll M PFs 0 V } for
278 stroke grestore } def
280 /Symbol-Oblique /Symbol findfont [1 0 .167 1 0 0] makefont
281 dup length dict begin {1 index /FID eq {pop pop} {def} ifelse} forall
282 currentdict end definefont pop
291 (Helvetica) findfont 140 scalefont setfont
763 %%DocumentFonts: Helvetica