17 # ifndef SEARCH_MEMORY_LEAKS_ENABLED
18 # error SEARCH NOT ENABLED
20 # define new DEBUG_NEW
22 static char THIS_FILE[] = __FILE__;
50 const node& net_source,
const node& net_target)
69 while (edge_it != edges_end)
84 bool source_found =
false;
85 bool target_found =
false;
88 while (node_it != nodes_end)
90 if ((*node_it).indeg() == 0)
94 if ((*node_it).outdeg() == 0)
100 if (!(source_found && target_found))
125 double flow_value = 0;
131 push(G, min_tp_node, flow_value);
132 pull(G, min_tp_node, flow_value);
171 while (node_it != nodes_end)
179 while (out_edge_it != out_edges_end)
191 while (in_edge_it != in_edges_end)
217 bool source_target_con =
false;
219 queue<node> next_nodes;
223 while (!next_nodes.empty())
225 cur_node = next_nodes.front();
229 while (out_edge_it != out_edges_end)
231 if (level[(*out_edge_it).target()] == -1)
235 source_target_con =
true;
237 level[(*out_edge_it).target()] = level[cur_node] + 1;
238 next_nodes.push((*out_edge_it).target());
241 else if (level[(*out_edge_it).target()] <= level[cur_node])
254 if (source_target_con)
269 queue<node> next_nodes;
274 while (!next_nodes.empty())
276 cur_node = next_nodes.front();
280 while (out_edge_it != out_edges_end)
282 node next = (*out_edge_it).target();
283 if (!reachable_from_net_source[next])
285 next_nodes.push(next);
286 reachable_from_net_source[
next] =
true;
294 while (!next_nodes.empty())
296 cur_node = next_nodes.front();
300 while (in_edge_it != in_edges_end)
303 if (!reachable_from_net_target[next])
305 next_nodes.push(next);
306 reachable_from_net_target[
next] =
true;
314 while (node_it != nodes_end)
316 if ((!reachable_from_net_source[*node_it]) ||
317 (!reachable_from_net_target[*node_it]))
337 while (in_it != in_edges_end)
344 while (out_it != out_edges_end)
361 while (node_it != nodes_end)
364 if (cur_tp < flow_value)
366 min_tp_node = *node_it;
376 double in_flow = 0.0;
377 double out_flow = 0.0;
380 while (in_it != in_edges_end)
387 while (out_it != out_edges_end)
400 return(in_flow < out_flow ? in_flow : out_flow);
407 queue<node> next_nodes;
409 next_nodes.push(start_node);
410 visited[start_node] =
true;
413 while (!next_nodes.empty())
415 cur_node = next_nodes.front();
420 while (out_edge_it != out_edges_end)
422 node next = (*out_edge_it).target();
425 last_edge[
next] = *out_edge_it;
430 next_nodes.push(next);
431 visited[
next] =
true;
442 queue<node> next_nodes;
444 next_nodes.push(start_node);
445 visited[start_node] =
true;
448 while (!next_nodes.empty())
450 cur_node = next_nodes.front();
455 while (in_edge_it != in_edges_end)
460 prev_edge[
next] = *in_edge_it;
465 next_nodes.push(next);
466 visited[
next] =
true;
477 double cur_flow = flow_value;
478 double min_value = 0.0;
488 if (min_value > cur_flow)
490 min_value = cur_flow;
514 cur_node = last_edge[cur_node].source();
516 while (cur_node != start_node);
517 cur_flow -= min_value;
518 if (cur_flow < 1
e-015)
522 }
while (cur_flow > 0.0);
529 double cur_flow = flow_value;
530 double min_value = 0.0;
540 if (min_value > cur_flow)
542 min_value = cur_flow;
566 cur_node = prev_edge[cur_node].target();
568 while (cur_node != start_node);
569 cur_flow -= min_value;
570 if (cur_flow < 1
e-015)
574 }
while (cur_flow > 0.0);
583 while (edge_it != edges_end)
588 list<edge>::iterator list_it =
full_edges.begin();
589 list<edge>::iterator list_end =
full_edges.end();
590 while (list_it != list_end)
596 list<edge>::iterator temp_it = list_it;
616 while (temp_un_node_it != temp_un_nodes_end)
623 while (temp_un_edge_it != temp_un_edges_end)
672 if (cur_capacity < min_value) min_value = cur_capacity;
673 cur_node = last_edge[cur_node].source();
675 while (cur_node != start_node);
691 if (cur_capacity < min_value) min_value = cur_capacity;
692 cur_node = prev_edge[cur_node].target();
694 while (cur_node != start_node);
720 while (out_edge_it != out_edges_end)