Fix many doxygen command bugs.
2 * src/hugo/min_cost_flow.h - Part of HUGOlib, a generic C++ optimization library
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef HUGO_MIN_COST_FLOW_H
18 #define HUGO_MIN_COST_FLOW_H
22 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
25 #include <hugo/dijkstra.h>
26 #include <hugo/graph_wrapper.h>
27 #include <hugo/maps.h>
32 /// \addtogroup flowalgs
35 ///\brief Implementation of an algorithm for finding a flow of value \c k
36 ///(for small values of \c k) having minimal total cost between 2 nodes
39 /// The class \ref hugo::MinCostFlow "MinCostFlow" implements
40 /// an algorithm for finding a flow of value \c k
41 /// having minimal total cost
42 /// from a given source node to a given target node in an
43 /// edge-weighted directed graph. To this end,
44 /// the edge-capacities and edge-weitghs have to be nonnegative.
45 /// The edge-capacities should be integers, but the edge-weights can be
46 /// integers, reals or of other comparable numeric type.
47 /// This algorithm is intended to use only for small values of \c k,
48 /// since it is only polynomial in k,
49 /// not in the length of k (which is log k).
50 /// In order to find the minimum cost flow of value \c k it
51 /// finds the minimum cost flow of value \c i for every
52 /// \c i between 0 and \c k.
54 ///\param Graph The directed graph type the algorithm runs on.
55 ///\param LengthMap The type of the length map.
56 ///\param CapacityMap The capacity map type.
58 ///\author Attila Bernath
59 template <typename Graph, typename LengthMap, typename CapacityMap>
62 typedef typename LengthMap::ValueType Length;
64 //Warning: this should be integer type
65 typedef typename CapacityMap::ValueType Capacity;
67 typedef typename Graph::Node Node;
68 typedef typename Graph::NodeIt NodeIt;
69 typedef typename Graph::Edge Edge;
70 typedef typename Graph::OutEdgeIt OutEdgeIt;
71 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
74 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGW;
75 typedef typename ResGW::Edge ResGraphEdge;
78 typedef typename Graph::template NodeMap<Length> NodeMap;
83 typedef typename LengthMap::KeyType KeyType;
84 typedef typename LengthMap::ValueType ValueType;
86 ValueType operator[](typename ResGW::Edge e) const {
88 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
90 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
93 ModLengthMap(const ResGW& _G,
94 const LengthMap &o, const NodeMap &p) :
95 G(_G), /*rev(_rev),*/ ol(o), pot(p){};
103 const LengthMap& length;
104 const CapacityMap& capacity;
107 //auxiliary variables
111 //To store the potential (dual variables)
112 typedef typename Graph::template NodeMap<Length> PotentialMap;
113 PotentialMap potential;
121 /// The constructor of the class.
123 ///\param _G The directed graph the algorithm runs on.
124 ///\param _length The length (weight or cost) of the edges.
125 ///\param _cap The capacity of the edges.
126 MinCostFlow(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
127 length(_length), capacity(_cap), flow(_G), potential(_G){ }
130 ///Runs the algorithm.
132 ///Runs the algorithm.
133 ///Returns k if there is a flow of value at least k edge-disjoint
135 ///Otherwise it returns the maximum value of a flow from s to t.
137 ///\param s The source node.
138 ///\param t The target node.
139 ///\param k The value of the flow we are looking for.
141 ///\todo May be it does make sense to be able to start with a nonzero
142 /// feasible primal-dual solution pair as well.
143 int run(Node s, Node t, int k) {
145 //Resetting variables from previous runs
148 for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
150 //Initialize the potential to zero
151 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
154 //We need a residual graph
155 ResGW res_graph(G, capacity, flow);
158 ModLengthMap mod_length(res_graph, length, potential);
160 Dijkstra<ResGW, ModLengthMap> dijkstra(res_graph, mod_length);
165 if (!dijkstra.reached(t)){
166 //There are no flow of value k from s to t
170 //We have to change the potential
171 for(typename ResGW::NodeIt n(res_graph); n!=INVALID; ++n)
172 potential[n] += dijkstra.distMap()[n];
175 //Augmenting on the sortest path
179 e = dijkstra.pred(n);
180 n = dijkstra.predNode(n);
181 res_graph.augment(e,1);
182 //Let's update the total length
183 if (res_graph.forward(e))
184 total_length += length[e];
186 total_length -= length[e];
198 /// Gives back the total weight of the found flow.
200 ///This function gives back the total weight of the found flow.
201 ///Assumes that \c run() has been run and nothing changed since then.
202 Length totalLength(){
206 ///Returns a const reference to the EdgeMap \c flow.
208 ///Returns a const reference to the EdgeMap \c flow.
209 ///\pre \ref run() must
210 ///be called before using this function.
211 const EdgeIntMap &getFlow() const { return flow;}
213 ///Returns a const reference to the NodeMap \c potential (the dual solution).
215 ///Returns a const reference to the NodeMap \c potential (the dual solution).
216 /// \pre \ref run() must be called before using this function.
217 const PotentialMap &getPotential() const { return potential;}
219 /// Checking the complementary slackness optimality criteria
221 ///This function checks, whether the given solution is optimal
222 ///If executed after the call of \c run() then it should return with true.
223 ///This function only checks optimality, doesn't bother with feasibility.
224 ///It is meant for testing purposes.
226 bool checkComplementarySlackness(){
229 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
231 mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
233 if (0<fl_e && fl_e<capacity[e]) {
234 /// \todo better comparison is needed for real types, moreover,
235 /// this comparison here is superfluous.
240 if (mod_pot > 0 && fl_e != 0)
242 if (mod_pot < 0 && fl_e != capacity[e])
250 }; //class MinCostFlow
256 #endif //HUGO_MIN_COST_FLOW_H