73 } |
73 } |
74 |
74 |
75 if(!visited.get(t)) return flow_val; |
75 if(!visited.get(t)) return flow_val; |
76 |
76 |
77 // Augmenting value computation |
77 // Augmenting value computation |
78 aug_val = visited.get(t)==2 ? |
78 aug_val = visited.get(t)==1 ? |
79 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
79 c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t)); |
80 //FIXME: I would need 'G.opposite(e,n)' |
80 //FIXME: I would need 'G.opposite(e,n)' |
81 gn = visited.get(t)==2 ? G.from(tree.get(t)) : G.to(tree.get(t)); |
81 gn = visited.get(t)==1 ? G.tail(tree.get(t)) : G.head(tree.get(t)); |
82 while(gn!=s) if(visited.get(gn)==2) |
82 while(gn!=s) if(visited.get(gn)==1) |
83 { |
83 { |
84 //FIXME: nonstandars. gcc extension! |
84 //FIXME: nonstandars. gcc extension! |
85 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
85 aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn)); |
86 gn=G.from(tree.get(gn)); |
86 gn=G.tail(tree.get(gn)); |
87 } |
87 } |
88 else { |
88 else { |
89 //FIXME: nonstandars. gcc extension! |
89 //FIXME: nonstandars. gcc extension! |
90 aug_val <?= f.get(tree.get(gn)); |
90 aug_val <?= f.get(tree.get(gn)); |
91 gn=G.from(tree.get(gn)); |
91 gn=G.head(tree.get(gn)); |
92 } |
92 } |
93 |
93 |
94 // The augmentation itself |
94 // The augmentation itself |
95 gn = t; |
95 gn = t; |
96 while(gn!=s) if(visited.get(gn)==2) |
96 while(gn!=s) if(visited.get(gn)==1) |
97 { |
97 { |
98 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
98 f.set(tree.get(gn),f.get(tree.get(gn))+aug_val); |
99 gn=G.from(tree.get(gn)); |
99 gn=G.tail(tree.get(gn)); |
100 } |
100 } |
101 else { |
101 else { |
102 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
102 f.set(tree.get(gn),f.get(tree.get(gn))-aug_val); |
103 gn=G.from(tree.get(gn)); |
103 gn=G.head(tree.get(gn)); |
104 } |
104 } |
105 |
105 |
106 flow_val+=aug_val; |
106 flow_val+=aug_val; |
107 |
107 |
108 goto augment; // Vivat goto forever! |
108 goto augment; // Vivat goto forever! |