42 } else { |
42 } else { |
43 return (resG->flow.get(sym)); |
43 return (resG->flow.get(sym)); |
44 } |
44 } |
45 } |
45 } |
46 bool is_valid() { return sym.is_valid(); } |
46 bool is_valid() { return sym.is_valid(); } |
|
47 void make_invalid() { sym.make_invalid(); } |
47 void augment(T a) { |
48 void augment(T a) { |
48 if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
49 if (resG->G.a_node(sym)==resG->G.tail(sym)) { |
49 resG->flow.put(sym, resG->flow.get(sym)+a); |
50 resG->flow.put(sym, resG->flow.get(sym)+a); |
50 } else { |
51 } else { |
51 resG->flow.put(sym, resG->flow.get(sym)-a); |
52 resG->flow.put(sym, resG->flow.get(sym)-a); |
79 node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); } |
80 node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); } |
80 node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); } |
81 node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); } |
81 |
82 |
82 int id(const node_iterator& v) { return G.id(v); } |
83 int id(const node_iterator& v) { return G.id(v); } |
83 |
84 |
84 node_iterator invalid_node() { return G.invalid_node(); } |
85 //node_iterator invalid_node() { return G.invalid_node(); } |
85 res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } |
86 //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } |
86 |
87 |
87 }; |
88 }; |
88 |
89 |
89 template <typename graph_type, typename T> |
90 template <typename graph_type, typename T> |
90 struct graph_traits< res_graph_type<graph_type, T> > { |
91 struct graph_traits< res_graph_type<graph_type, T> > { |
125 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type; |
126 typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type; |
126 bfs_queue_type bfs_queue; |
127 bfs_queue_type bfs_queue; |
127 bfs_queue.push(res_graph.first_out_edge(s)); |
128 bfs_queue.push(res_graph.first_out_edge(s)); |
128 |
129 |
129 typedef node_property_vector<aug_graph_type, bool> reached_type; |
130 typedef node_property_vector<aug_graph_type, bool> reached_type; |
130 //reached_type reached(res_graph); |
|
131 //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); } |
|
132 reached_type reached(res_graph, false); |
131 reached_type reached(res_graph, false); |
133 reached.put(s, true); |
132 reached.put(s, true); |
134 |
133 |
135 bfs_iterator1< aug_graph_type, reached_type > |
134 bfs_iterator1< aug_graph_type, reached_type > |
136 res_bfs(res_graph, bfs_queue, reached); |
135 res_bfs(res_graph, bfs_queue, reached); |
137 |
136 |
138 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type; |
137 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type; |
139 pred_type pred(res_graph); |
138 pred_type pred(res_graph); |
140 pred.put(s, res_graph.invalid_edge()); |
139 graph_traits<aug_graph_type>::edge_iterator a; |
|
140 a.make_invalid(); |
|
141 pred.put(s, a); |
141 |
142 |
142 typedef node_property_vector<aug_graph_type, int> free_type; |
143 typedef node_property_vector<aug_graph_type, int> free_type; |
143 free_type free(res_graph); |
144 free_type free(res_graph); |
144 |
145 |
145 //searching for augmenting path |
146 //searching for augmenting path |