include/GTL/maxflow_ff.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   maxflow_ff.h
0005 //
0006 //==========================================================================
0007 // $Id: maxflow_ff.h,v 1.5 2003/01/31 08:15:05 chris Exp $
0008
0009 #ifndef GTL_MAXFLOW_FF_H
0010 #define GTL_MAXFLOW_FF_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 (Edmonds-Karp).
0024  */
0025 class GTL_EXTERN maxflow_ff : 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_ff();
0035
0036     /**
0037      * Destructor.
0038      *
0039      * @see algorithm#~algorithm
0040      */
0041     virtual ~maxflow_ff();
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,
0062     const node& net_target);
0063
0064     /**
0065      * Checks whether following preconditions are satisfied:
0066      * <ul>
0067      * <li> @ref maxflow_ff#set_vars has been executed before.
0068      * <li> only edge_capacities >= 0 are applied.
0069      * <li> <code>G</code> is directed.
0070      * <li> <code>G</code> is connected.
0071      * <li> <code>G</code> has at least one edge and two nodes.
0072      * <li> if not applied, start-nodes and end-nodes exists.
0073      * <li> if applied, start-node is not the same node as end-node.
0074      * </ul>
0075      *
0076      * @param G graph
0077      * @return <code>algorithm::GTL_OK</code> on success
0078      * <code>algorithm::GTL_ERROR</code> 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 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 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      *
0120      * @see algorithm#reset
0121      */
0122     virtual void reset();
0123 protected:
0124     /**
0125      * @internal
0126      */
0127     enum {SP_FOUND = 2, NO_SP_FOUND = 3};
0128
0129     /**
0130      * @internal
0131      */
0132     bool artif_source_target;
0133
0134     /**
0135      * @internal
0136      */
0137     bool set_vars_executed;
0138
0139     /**
0140      * @internal
0141      */
0142     double max_graph_flow;
0143
0144     /**
0145      * @internal
0146      */
0147     node net_source;
0148
0149     /**
0150      * @internal
0151      */
0152     node net_target;
0153
0154     /**
0155      * @internal edges to remove from G after run
0156      */
0157     list<edge> edges_not_org;
0158
0159     /**
0160      * @internal original edge or inserted back edge
0161      */
0162     edge_map<bool> edge_org;
0163
0164     /**
0165      * @internal
0166      */
0167     edge_map<bool> back_edge_exists;
0168
0169     /**
0170      * @internal every edge knows its back edge
0171      */
0172     edge_map<edge> back_edge;
0173
0174     /**
0175      * @internal
0176      */
0177     edge_map<double> edge_capacity;
0178
0179     /**
0180      * @internal
0181      */
0182     edge_map<double> edge_max_flow;
0183
0184     /**
0185      * @internal
0186      */
0187     void create_artif_source_target(graph& G);
0188
0189     /**
0190      * @internal
0191      */
0192     void prepare_run(const graph& G);
0193
0194     /**
0195      * @internal
0196      */
0197     void comp_single_flow(graph& G, node_map<edge>& last_edge);
0198
0199     /**
0200      * @internal every node knows its predecessor then
0201      */
0202     int get_sp(const graph& G, node_map<edge>& last_edge);
0203
0204     /**
0205      * @internal
0206      */
0207     int comp_sp(
0208     const graph& G,
0209     queue<node>& next_nodes,
0210     node_map<bool>& visited,
0211     node_map<edge>& last_edge);
0212
0213     /**
0214      * @internal
0215      */
0216     double extra_charge(const node_map<edge>& last_edge) const;
0217
0218     /**
0219      * @internal
0220      */
0221     void create_back_edge(graph& G, const edge& org_edge);
0222
0223     /**
0224      * @internal
0225      */
0226     void comp_max_flow(const graph& G);
0227
0228     /**
0229      * @internal
0230      */
0231     void restore_graph(graph& G);
0232 };
0233
0234 __GTL_END_NAMESPACE
0235
0236 #endif // GTL_MAXFLOW_FF_H
0237
0238 //--------------------------------------------------------------------------
0239 //   end of file
0240 //--------------------------------------------------------------------------