include/GTL/maxflow_sap.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   maxflow_sap.h
0005 //
0006 //==========================================================================
0007 // $Id: maxflow_sap.h,v 1.4 2003/01/31 08:15:05 chris Exp $
0008
0009 #ifndef GTL_MAXFLOW_SAP_H
0010 #define GTL_MAXFLOW_SAP_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 with shortest augmenting paths
0024  *
0025  * This class implements a maximum flow algorithm with shortest augmenting
0026  * paths due to Ahuja and Orlin.
0027  *
0028  * <p> In the case V is the set of vertices and E is the set of edges of
0029  * the graph, the algorithm needs O(|V| * |V| * |E|) time to proceed.
0030  *
0031  * @see maxflow_ff
0032  * @see maxflow_pp
0033  */
0034 class GTL_EXTERN maxflow_sap : public algorithm
0035 {
0036 public:
0037     /**
0038      * Default constructor. Enables only the calculation of
0039      * maximum flow.
0040      *
0041      * @see algorithm#algorithm
0042      */
0043     maxflow_sap();
0044
0045     /**
0046      * Destructor.
0047      *
0048      * @see algorithm#~algorithm
0049      */
0050     virtual ~maxflow_sap();
0051
0052     /**
0053      * Sets capacity of every edge for maximum flow calculation
0054      * where artificial start-node and end_node will be computed
0055      * automatically.
0056      *
0057      * @param edge_capacity capacity of every edge
0058      */
0059     void set_vars(const edge_map<double>& edge_capacity);
0060
0061     /**
0062      * Sets capacity of every edge for maximum flow calculation
0063      *
0064      * @param edge_capacity capacity of every edge
0065      * @param net_source start-node
0066      * @param net_target end-node
0067      */
0068     void set_vars(const edge_map<double>& edge_capacity,
0069                   const node& net_source,
0070                   const node& net_target);
0071
0072     /**
0073      * Checks whether following preconditions are satisfied:
0074      * <ul>
0075      * <li> @ref maxflow_sap#set_vars has been executed before.
0076      * <li> only edge_capacities >= 0 are applied.
0077      * <li> <code>G</code> is directed.
0078      * <li> <code>G</code> is connected.
0079      * <li> <code>G</code> has at least one edge and two nodes.
0080      * <li> if not applied, start-nodes and end-nodes exists.
0081      * <li> if applied, start-node is not the same node as end-node.
0082      * </ul>
0083      *
0084      * @param G graph
0085      * @return <code>algorithm::GTL_OK</code> on success
0086      * <code>algorithm::GTL_ERROR</code> otherwise
0087      * @see algorithm#check
0088      */
0089     virtual int check(graph& G);
0090
0091     /**
0092      * Computes maximum flow of graph <code>G</code>.
0093      *
0094      * @param G graph
0095      * @return <code>algorithm::GTL_OK</code> on success
0096      * <code>algorithm::GTL_ERROR</code> otherwise
0097      * @see algorithm#run
0098      */
0099     int run(graph& G);
0100
0101     /**
0102      * Returns the maximum flow of an edge.
0103      *
0104      * @param e edge of a graph @c G
0105      * @return maximum flow value
0106      */
0107     double get_max_flow(const edge& e) const;
0108
0109     /**
0110      * Returns the maximum flow of the whole graph G.
0111      *
0112      * @return maximum flow value
0113      */
0114     double get_max_flow() const;
0115
0116     /**
0117      * Returns the remaining free capacity of an edge.
0118      *
0119      * @param e edge of a graph @c G
0120      * @return remaining capacity
0121      */
0122     double get_rem_cap(const edge& e) const;
0123
0124     /**
0125      * Resets maximum flow algorithm, i.e. prepares the
0126      * algorithm to be applied to another graph.
0127      *
0128      * @see algorithm#reset
0129      */
0130     virtual void reset();
0131 protected:
0132     /**
0133      * @internal
0134      */
0135     enum {AP_FOUND = 2, NO_AP_FOUND = 3};
0136
0137     /**
0138      * @internal
0139      */
0140     bool artif_source_target;
0141
0142     /**
0143      * @internal
0144      */
0145     bool set_vars_executed;
0146
0147     /**
0148      * @internal
0149      */
0150     double max_graph_flow;
0151
0152     /**
0153      * @internal
0154      */
0155     node net_source;
0156
0157     /**
0158      * @internal
0159      */
0160     node net_target;
0161
0162     /**
0163      * @internal edges to remove from G after run
0164      */
0165     list<edge> edges_not_org;
0166
0167     /**
0168      * @internal
0169      */
0170     node_map<int> dist_label;
0171
0172     /**
0173      * @internal original edge or inserted back edge
0174      */
0175     edge_map<bool> edge_org;
0176
0177     /**
0178      * @internal
0179      */
0180     edge_map<bool> back_edge_exists;
0181
0182     /**
0183      * @internal every edge knows its back edge
0184      */
0185     edge_map<edge> back_edge;
0186
0187     /**
0188      * @internal
0189      */
0190     edge_map<double> edge_capacity;
0191
0192     /**
0193      * @internal
0194      */
0195     edge_map<double> edge_max_flow;
0196
0197     /**
0198      * @internal
0199      */
0200     void create_artif_source_target(graph& G);
0201
0202     /**
0203      * @internal
0204      */
0205     void prepare_run(const graph& G);
0206
0207     /**
0208      * @internal
0209      */
0210     void comp_dist_labels(const graph& G, vector<int>& numb);
0211
0212     /**
0213      * @internal
0214      */
0215     bool has_an_admissible_arc(const node cur_node);
0216
0217     /**
0218      * @internal
0219      */
0220     void advance(node& cur_node, node_map<edge>& last_edge);
0221
0222     /**
0223      * @internal
0224      */
0225     void augment(graph& G, const node_map<edge>& last_edge);
0226
0227     /**
0228      * @internal
0229      */
0230     bool retreat(const int number_of_nodes,
0231                  node& cur_node,
0232                  const node_map<edge>& last_edge,
0233                  vector<int>& numb);
0234
0235     /**
0236      * @internal
0237      */
0238     int min_neighbour_label(const int number_of_nodes,
0239                             const node cur_node) const;
0240
0241     /**
0242      * @internal
0243      */
0244     double free_capacity(const node_map<edge>& last_edge) const;
0245
0246     /**
0247      * @internal
0248      */
0249     void create_back_edge(graph& G, const edge& org_edge);
0250
0251     /**
0252      * @internal
0253      */
0254     void comp_max_flow(const graph& G);
0255
0256     /**
0257      * @internal
0258      */
0259     void restore_graph(graph& G);
0260 };
0261
0262 __GTL_END_NAMESPACE
0263
0264 #endif // GTL_MAXFLOW_SAP_H
0265
0266 //--------------------------------------------------------------------------
0267 //   end of file
0268 //--------------------------------------------------------------------------