82 |
82 |
83 // Augmenting value computation |
83 // Augmenting value computation |
84 aug_val = visited.get(t)==1 ? |
84 aug_val = visited.get(t)==1 ? |
85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
85 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
86 //FIXME: I would need 'G.opposite(e,n)' |
86 //FIXME: I would need 'G.opposite(e,n)' |
87 gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t)); |
87 gn = visited.get(t)==1 ? G.source(tree.get(t)) : G.target(tree.get(t)); |
88 while(gn!=s) if(visited.get(gn)==1) |
88 while(gn!=s) if(visited.get(gn)==1) |
89 { |
89 { |
90 //FIXME: nonstandard gcc extension! |
90 //FIXME: nonstandard gcc extension! |
91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
91 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
92 gn=G.tail(tree.get(gn)); |
92 gn=G.source(tree.get(gn)); |
93 } |
93 } |
94 else { |
94 else { |
95 //FIXME: nonstandard gcc extension! |
95 //FIXME: nonstandard gcc extension! |
96 aug_val <?= f.get(tree.get(gn)); |
96 aug_val <?= f.get(tree.get(gn)); |
97 gn=G.head(tree.get(gn)); |
97 gn=G.target(tree.get(gn)); |
98 } |
98 } |
99 |
99 |
100 // The augmentation itself |
100 // The augmentation itself |
101 gn = t; |
101 gn = t; |
102 while(gn!=s) if(visited.get(gn)==1) |
102 while(gn!=s) if(visited.get(gn)==1) |
103 { |
103 { |
104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
104 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
105 gn=G.tail(tree.get(gn)); |
105 gn=G.source(tree.get(gn)); |
106 } |
106 } |
107 else { |
107 else { |
108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
108 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
109 gn=G.head(tree.get(gn)); |
109 gn=G.target(tree.get(gn)); |
110 } |
110 } |
111 |
111 |
112 flow_val+=aug_val; |
112 flow_val+=aug_val; |
113 |
113 |
114 goto augment; // Vivat goto forever! |
114 goto augment; // Vivat goto forever! |