include/GTL/maxflow_pp.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   maxflow_pp.h
0005 //
0006 //==========================================================================
0007 // $Id: maxflow_pp.h,v 1.5 2003/01/31 08:15:05 chris Exp $
0008
0009 #ifndef GTL_MAXFLOW_PP_H
0010 #define GTL_MAXFLOW_PP_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/graph.h>
0014 #include <GTL/node_map.h>
0015 #include <GTL/edge_map.h>
0016 #include <GTL/algorithm.h>
0017
0018 #include <queue>
0019
0020 __GTL_BEGIN_NAMESPACE
0021
0022 /**
0023  * @short Maximum flow algorithm (Malhotra, Kumar, Maheshwari).
0024  */
0025 class GTL_EXTERN maxflow_pp : public algorithm
0026 {
0027 public:
0028     /**
0029      * Default constructor. Enables only the calculation of
0030      * maximum flow.
0031      *
0032      * @see algorithm#algorithm
0033      */
0034     maxflow_pp();
0035
0036     /**
0037      * Destructor.
0038      *
0039      * @see algorithm#~algorithm
0040      */
0041     virtual ~maxflow_pp();
0042
0043     /**
0044      * Sets capacity of every edge for maximum flow calculation
0045      * where artificial start-node and end_node will be computed
0046      * automatically.
0047      *
0048      * @param edge_capacity capacity of every edge
0049      */
0050     void set_vars(const edge_map<double>& edge_capacity);
0051
0052     /**
0053      * Sets capacity of every edge for maximum flow calculation
0054      *
0055      * @param edge_capacity capacity of every edge
0056      * @param net_source start-node
0057      * @param net_target end-node
0058      */
0059     void set_vars(
0060     const edge_map<double>& edge_capacity,
0061     const node& net_source, const node& net_target);
0062
0063     /**
0064      * Checks whether following preconditions are satisfied:
0065      * <ul>
0066      * <li> @ref maxflow_pp#set_vars has been executed before.
0067      * <li> only edge_capacities >= 0 are applied.
0068      * <li> <code>G</code> is directed.
0069      * <li> <code>G</code> is connected.
0070      * <li> <code>G</code> has at least one edge and two nodes.
0071      * <li> if not applied, start-nodes and end-nodes exists.
0072      * <li> if applied, start-node is not the same node as end-node.
0073      * </ul>
0074      *
0075      * @param G graph
0076      * @return <code>algorithm::GTL_OK</code> on success
0077      * <code>algorithm::GTL_ERROR</code>
0078      * otherwise
0079      * @see algorithm#check
0080      */
0081     virtual int check(graph& G);
0082
0083     /**
0084      * Computes maximum flow of graph <code>G</code>.
0085      *
0086      * @param G graph
0087      * @return <code>algorithm::GTL_OK</code> on success
0088      * <code>algorithm::GTL_ERROR</code> otherwise
0089      * @see algorithm#run
0090      */
0091     int run(graph& G);
0092
0093     /**
0094      * Returns the maximum flow of an edge.
0095      *
0096      * @param e edge of a graph @c G
0097      * @return maximum flow value
0098      */
0099     double get_max_flow(const edge& e) const;
0100
0101     /**
0102      * Returns the maximum flow of the whole graph @c G.
0103      *
0104      * @return maximum flow value
0105      */
0106     double get_max_flow() const;
0107
0108     /**
0109      * Returns the remaining free capacity of an edge.
0110      *
0111      * @param e edge of a graph G
0112      * @return remaining capacity
0113      */
0114     double get_rem_cap(const edge& e) const;
0115
0116     /**
0117      * Resets maximum flow algorithm, i.e. prepares the
0118      * algorithm to be applied to another graph.
0119      * @see algorithm#reset
0120      */
0121     virtual void reset();
0122 protected:
0123     /**
0124      * @internal
0125      */
0126     enum {TARGET_FROM_SOURCE_REACHABLE = 2, TARGET_FROM_SOURCE_NOT_REACHABLE = 3};
0127
0128     /**
0129      * @internal
0130      */
0131     bool artif_source_target;
0132
0133     /**
0134      * @internal
0135      */
0136     bool set_vars_executed;
0137
0138     /**
0139      * @internal
0140      */
0141     double max_graph_flow;
0142
0143     /**
0144      * @internal
0145      */
0146     node net_source;
0147
0148     /**
0149      * @internal
0150      */
0151     node net_target;
0152
0153     /**
0154      * @internal edges to remove from G after run
0155      */
0156     list<edge> edges_not_org;
0157
0158     /**
0159      * @internal original edge or inserted back edge
0160      */
0161     edge_map<bool> edge_org;
0162
0163     /**
0164      * @internal
0165      */
0166     edge_map<bool> back_edge_exists;
0167
0168     /**
0169      * @internal every edge knows its back edge
0170      */
0171     edge_map<edge> back_edge;
0172
0173     /**
0174      * @internal
0175      */
0176     edge_map<double> edge_capacity;
0177
0178     /**
0179      * @internal
0180      */
0181     edge_map<double> edge_max_flow;
0182
0183     /**
0184      * @internal
0185      */
0186     edge_map<double> flow_update;
0187
0188     /**
0189      * @internal
0190      */
0191     list<edge> full_edges;
0192
0193     /**
0194      * @internal
0195      */
0196     list<node> temp_unvisible_nodes;
0197
0198     /**
0199      * @internal
0200      */
0201     list<edge> temp_unvisible_edges;
0202
0203     /**
0204      * @internal
0205      */
0206     void create_artif_source_target(graph& G);
0207
0208     /**
0209      * @internal
0210      */
0211     void prepare_run(const graph& G);
0212
0213     /**
0214      * @internal
0215      */
0216     int leveling(graph& G);
0217
0218     /**
0219      * @internal
0220      */
0221     void hide_unreachable_nodes(graph& G);
0222
0223     /**
0224      * @internal
0225      */
0226     void store_temp_unvisible_edges(const node& cur_node);
0227
0228     /**
0229      * @internal
0230      */
0231     void min_throughput_node(const graph& G, node& min_tp_node, double& min_value);
0232
0233     /**
0234      * @internal
0235      */
0236     double comp_min_throughput(const node cur_node) const;
0237
0238     /**
0239      * @internal every node knows its predecessor then
0240      */
0241     void get_sp_ahead(const graph& G, const node& start_node,
0242     node_map<edge>& last_edge);
0243
0244     /**
0245      * @internal every node knows its successor then
0246      */
0247     void get_sp_backwards(const graph& G, const node& start_node,
0248     node_map<edge>& prev_edge);
0249
0250     /**
0251      * @internal
0252      */
0253     void push(graph& G, const node& start_node, const double flow_value);
0254
0255     /**
0256      * @internal
0257      */
0258     void pull(graph& G, const node& start_node, const double flow_value);
0259
0260     /**
0261      * @internal
0262      */
0263     void comp_rem_net(graph& G);
0264
0265     /**
0266      * @internal
0267      */
0268     void single_edge_update(graph& G, edge cur_edge);
0269
0270     /**
0271      * @internal
0272      */
0273     double extra_charge_ahead(const node& start_node, const
0274     node_map<edge>& last_edge) const;
0275
0276     /**
0277      * @internal
0278      */
0279     double extra_charge_backwards(const node& start_node,
0280     const node_map<edge>& prev_edge) const;
0281
0282     /**
0283      * @internal
0284      */
0285     void create_back_edge(graph& G, const edge& org_edge);
0286
0287     /**
0288      * @internal
0289      */
0290     void comp_max_flow(const graph& G);
0291
0292     /**
0293      * @internal
0294      */
0295     void restore_graph(graph& G);
0296 private:
0297 };
0298
0299 __GTL_END_NAMESPACE
0300
0301 #endif // GTL_MAXFLOW_PP_H
0302
0303 //--------------------------------------------------------------------------
0304 //   end of file
0305 //--------------------------------------------------------------------------