gtl/src/maxflow_ff.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   maxflow_ff.cpp
0005 //
0006 //==========================================================================
0007 // $Id: maxflow_ff.cpp,v 1.7 2001/11/07 13:58:10 pick Exp $
0008
0009 #include <GTL/maxflow_ff.h>
0010
0011 #include <cstdlib>
0012 #include <iostream>
0013 #include <cassert>
0014
0015 #ifdef __GTL_MSVCC
0016 #   ifdef _DEBUG
0017 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0018 #   error SEARCH NOT ENABLED
0019 #   endif
0020 #   define new DEBUG_NEW
0021 #   undef THIS_FILE
0022     static char THIS_FILE[] = __FILE__;
0023 #   endif   // _DEBUG
0024 #endif  // __GTL_MSVCC
0025
0026 __GTL_BEGIN_NAMESPACE
0027
0028 maxflow_ff::maxflow_ff()
0029 {
0030     max_graph_flow = 0.0;
0031     set_vars_executed = false;
0032 }
0033
0034
0035 maxflow_ff::~maxflow_ff()
0036 {
0037 }
0038
0039
0040 void maxflow_ff::set_vars(const edge_map<double>& edge_capacity)
0041 {
0042     this->edge_capacity = edge_capacity;
0043     artif_source_target = true;
0044     max_graph_flow = 0.0;
0045     set_vars_executed = true;
0046 }
0047
0048
0049 void maxflow_ff::set_vars(const edge_map<double>& edge_capacity,
0050     const node& net_source, const node& net_target)
0051 {
0052     this->edge_capacity = edge_capacity;
0053     this->net_source = net_source;
0054     this->net_target = net_target;
0055     artif_source_target = false;
0056     max_graph_flow = 0.0;
0057     set_vars_executed = true;
0058 }
0059
0060
0061 int maxflow_ff::check(graph& G)
0062 {
0063     if (!set_vars_executed)
0064     {
0065     return(GTL_ERROR);
0066     }
0067     graph::edge_iterator edge_it = G.edges_begin();
0068     graph::edge_iterator edges_end = G.edges_end();
0069     while (edge_it != edges_end)
0070     {
0071     if (edge_capacity[*edge_it] < 0)
0072     {
0073         return(GTL_ERROR);
0074     }
0075     ++edge_it;
0076     }
0077     // G.is_acyclic may be false
0078     if ((G.number_of_nodes() <= 1) || (!G.is_connected()) || (G.is_undirected()))
0079     {
0080     return(GTL_ERROR);
0081     }
0082     if (artif_source_target)
0083     {
0084     bool source_found = false;
0085     bool target_found = false;
0086     graph::node_iterator node_it = G.nodes_begin();
0087     graph::node_iterator nodes_end = G.nodes_end();
0088     while (node_it != nodes_end)
0089     {
0090         if ((*node_it).indeg() == 0)
0091         {
0092         source_found = true;
0093         }
0094         if ((*node_it).outdeg() == 0)
0095         {
0096         target_found = true;
0097         }
0098         ++node_it;
0099     }
0100     if (!(source_found && target_found))
0101     {
0102         return(GTL_ERROR);
0103     }
0104     }
0105     else
0106     {
0107     if (net_source == net_target)
0108     {
0109         return(GTL_ERROR);
0110     }
0111     }
0112     return(GTL_OK); // ok
0113 }
0114
0115
0116 int maxflow_ff::run(graph& G)
0117 {
0118     // init
0119     if (artif_source_target)
0120     {
0121     create_artif_source_target(G);
0122     }
0123     prepare_run(G);
0124
0125     node_map<edge> last_edge(G);
0126
0127     while (get_sp(G, last_edge) == SP_FOUND)
0128     {
0129     comp_single_flow(G, last_edge);
0130     }
0131
0132     restore_graph(G);
0133     return(GTL_OK);
0134 }
0135
0136
0137 double maxflow_ff::get_max_flow(const edge& e) const
0138 {
0139     return(edge_max_flow[e]);
0140 }
0141
0142
0143 double maxflow_ff::get_max_flow() const
0144 {
0145     return(max_graph_flow);
0146 }
0147
0148
0149 double maxflow_ff::get_rem_cap(const edge& e) const
0150 {
0151     return(edge_capacity[e] - edge_max_flow[e]);
0152 }
0153
0154
0155 void maxflow_ff::reset()
0156 {
0157 }
0158
0159
0160 void maxflow_ff::create_artif_source_target(graph& G)
0161 {
0162     net_source = G.new_node();
0163     net_target = G.new_node();
0164     edge e;
0165     graph::node_iterator node_it = G.nodes_begin();
0166     graph::node_iterator nodes_end = G.nodes_end();
0167     while (node_it != nodes_end)
0168     {
0169     if (*node_it != net_source && (*node_it).indeg() == 0)
0170     {
0171         e = G.new_edge(net_source, *node_it);
0172         edge_capacity[e] = 1.0; // 1.0 prevents e from hiding
0173         node::out_edges_iterator out_edge_it = (*node_it).out_edges_begin();
0174         node::out_edges_iterator out_edges_end = (*node_it).out_edges_end();
0175         while (out_edge_it != out_edges_end)
0176         {
0177         edge_capacity[e] += edge_capacity[*out_edge_it];
0178         ++out_edge_it;
0179         }
0180     }
0181     if (*node_it != net_target && (*node_it).outdeg() == 0)
0182     {
0183         e = G.new_edge(*node_it, net_target);
0184         edge_capacity[e] = 1.0; // 1.0 prevents e from hiding
0185         node::in_edges_iterator in_edge_it = (*node_it).in_edges_begin();
0186         node::in_edges_iterator in_edges_end = (*node_it).in_edges_end();
0187         while (in_edge_it != in_edges_end)
0188         {
0189         edge_capacity[e] += edge_capacity[*in_edge_it];
0190         ++in_edge_it;
0191         }
0192     }
0193     ++node_it;
0194     }
0195 }
0196
0197
0198 void maxflow_ff::prepare_run(const graph& G)
0199 {
0200     edge_max_flow.init(G, 0.0);
0201     edge_org.init(G, true);
0202     back_edge_exists.init(G, false);
0203     max_graph_flow = 0.0;
0204 }
0205
0206
0207 void maxflow_ff::comp_single_flow(graph& G, node_map<edge>& last_edge)
0208 {
0209     double min_value = extra_charge(last_edge);
0210
0211     node cur_node = net_target;
0212     do
0213     {
0214     if (edge_org[last_edge[cur_node]])  // shortest path runs over a org. edge
0215     {
0216         if (!back_edge_exists[last_edge[cur_node]]) // create back edge
0217         {
0218         create_back_edge(G, last_edge[cur_node]);
0219         }
0220         edge_max_flow[last_edge[cur_node]] += min_value;
0221         G.restore_edge(back_edge[last_edge[cur_node]]);
0222         edge_capacity[back_edge[last_edge[cur_node]]] += min_value;
0223     }
0224     else    // shortest path runs over a inserted back edge
0225     {
0226         edge oe = back_edge[last_edge[cur_node]];
0227         G.restore_edge(oe);
0228         edge_max_flow[oe] -= min_value;
0229         edge_capacity[last_edge[cur_node]] -= min_value;
0230     }
0231     if (edge_capacity[last_edge[cur_node]] <= edge_max_flow[last_edge[cur_node]])
0232     {
0233         G.hide_edge(last_edge[cur_node]);
0234     }
0235     cur_node = last_edge[cur_node].source();
0236     }
0237     while (cur_node != net_source);
0238 }
0239
0240
0241 int maxflow_ff::get_sp(const graph& G, node_map<edge>& last_edge)
0242 {
0243     queue<node> next_nodes;
0244     node_map<bool> visited(G, false);
0245     next_nodes.push(net_source);
0246     visited[net_source] = true;
0247
0248     if (comp_sp(G, next_nodes, visited, last_edge) == SP_FOUND)
0249     {
0250     return(SP_FOUND);
0251     }
0252     else
0253     {
0254     return(NO_SP_FOUND);
0255     }
0256 }
0257
0258
0259 int maxflow_ff::comp_sp(const graph& G, queue<node>& next_nodes,
0260     node_map<bool>& visited, node_map<edge>& last_edge)
0261 {
0262     node cur_node;
0263
0264     while (!next_nodes.empty())
0265     {
0266     cur_node = next_nodes.front();
0267     next_nodes.pop();
0268
0269     node::out_edges_iterator out_edge_it = cur_node.out_edges_begin();
0270     node::out_edges_iterator out_edges_end = cur_node.out_edges_end();
0271     while (out_edge_it != out_edges_end)
0272     {
0273         node next = (*out_edge_it).target();
0274         if (!visited[next])
0275         {
0276         last_edge[next] = *out_edge_it;
0277         if (next == net_target)
0278         {
0279             return(SP_FOUND);
0280         }
0281         else
0282         {
0283             next_nodes.push(next);
0284             visited[next] = true;
0285         }
0286         }
0287         ++out_edge_it;
0288     }
0289     }
0290     return(NO_SP_FOUND);
0291 }
0292
0293
0294 double maxflow_ff::extra_charge(const node_map<edge>& last_edge) const
0295 {
0296     node cur_node = net_target;
0297     double min_value =
0298     edge_capacity[last_edge[cur_node]] - edge_max_flow[last_edge[cur_node]];
0299     double cur_capacity;
0300
0301     do
0302     {
0303     cur_capacity =
0304         edge_capacity[last_edge[cur_node]] - edge_max_flow[last_edge[cur_node]];
0305
0306     if (cur_capacity < min_value) min_value = cur_capacity;
0307     cur_node = last_edge[cur_node].source();
0308     }
0309     while (cur_node != net_source);
0310     return(min_value);
0311 }
0312
0313
0314 void maxflow_ff::create_back_edge(graph& G, const edge& org_edge)
0315 {
0316     edge be = G.new_edge(org_edge.target(), org_edge.source());
0317     edge_org[be] = false;
0318     edges_not_org.push_back(be);
0319     back_edge[org_edge] = be;
0320     back_edge[be] = org_edge;
0321     edge_max_flow[be] = 0.0;
0322     edge_capacity[be] = 0.0;
0323     back_edge_exists[org_edge] = true;
0324     back_edge_exists[be] = true;    // a back edge always has a org. edge ;-)
0325 }
0326
0327
0328 void maxflow_ff::comp_max_flow(const graph& G)
0329 {
0330     max_graph_flow = 0.0;
0331
0332     node::out_edges_iterator out_edge_it = net_source.out_edges_begin();
0333     node::out_edges_iterator out_edges_end = net_source.out_edges_end();
0334     while (out_edge_it != out_edges_end)
0335     {
0336     max_graph_flow += edge_max_flow[*out_edge_it];
0337     ++out_edge_it;
0338     }
0339 }
0340
0341
0342 void maxflow_ff::restore_graph(graph& G)
0343 {
0344     G.restore_graph();  // hidden edges can not be deleted!
0345     while (!edges_not_org.empty())
0346     {
0347     G.del_edge(edges_not_org.front());
0348     edges_not_org.pop_front();
0349     }
0350     comp_max_flow(G);
0351     if (artif_source_target)
0352     {
0353     G.del_node(net_source);
0354     G.del_node(net_target);
0355     }
0356 }
0357
0358 __GTL_END_NAMESPACE
0359
0360 //--------------------------------------------------------------------------
0361 //   end of file
0362 //--------------------------------------------------------------------------