The default constructors are removed from the maps.
The ArrayMap is the map structure of the graphs.
2 #ifndef HUGO_MINCOSTFLOWS_H
3 #define HUGO_MINCOSTFLOWS_H
7 ///\brief An algorithm for finding a flow of value \c k (for small values of \c k) having minimal total cost
10 #include <hugo/dijkstra.h>
11 #include <hugo/graph_wrapper.h>
12 #include <hugo/maps.h>
17 /// \addtogroup flowalgs
20 ///\brief Implementation of an algorithm for finding a flow of value \c k
21 ///(for small values of \c k) having minimal total cost between 2 nodes
24 /// The class \ref hugo::MinCostFlows "MinCostFlows" implements
25 /// an algorithm for finding a flow of value \c k
26 /// having minimal total cost
27 /// from a given source node to a given target node in an
28 /// edge-weighted directed graph. To this end,
29 /// the edge-capacities and edge-weitghs have to be nonnegative.
30 /// The edge-capacities should be integers, but the edge-weights can be
31 /// integers, reals or of other comparable numeric type.
32 /// This algorithm is intended to use only for small values of \c k,
33 /// since it is only polynomial in k,
34 /// not in the length of k (which is log k).
35 /// In order to find the minimum cost flow of value \c k it
36 /// finds the minimum cost flow of value \c i for every
37 /// \c i between 0 and \c k.
39 ///\param Graph The directed graph type the algorithm runs on.
40 ///\param LengthMap The type of the length map.
41 ///\param CapacityMap The capacity map type.
43 ///\author Attila Bernath
44 template <typename Graph, typename LengthMap, typename CapacityMap>
47 typedef typename LengthMap::ValueType Length;
49 //Warning: this should be integer type
50 typedef typename CapacityMap::ValueType Capacity;
52 typedef typename Graph::Node Node;
53 typedef typename Graph::NodeIt NodeIt;
54 typedef typename Graph::Edge Edge;
55 typedef typename Graph::OutEdgeIt OutEdgeIt;
56 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
59 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
60 typedef typename ResGraphType::Edge ResGraphEdge;
63 typedef typename Graph::template NodeMap<Length> NodeMap;
64 const ResGraphType& G;
68 typedef typename LengthMap::KeyType KeyType;
69 typedef typename LengthMap::ValueType ValueType;
71 ValueType operator[](typename ResGraphType::Edge e) const {
73 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
75 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
78 ModLengthMap(const ResGraphType& _G,
79 const LengthMap &o, const NodeMap &p) :
80 G(_G), /*rev(_rev),*/ ol(o), pot(p){};
88 const LengthMap& length;
89 const CapacityMap& capacity;
96 //To store the potential (dual variables)
97 typedef typename Graph::template NodeMap<Length> PotentialMap;
98 PotentialMap potential;
106 /// The constructor of the class.
108 ///\param _G The directed graph the algorithm runs on.
109 ///\param _length The length (weight or cost) of the edges.
110 ///\param _cap The capacity of the edges.
111 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
112 length(_length), capacity(_cap), flow(_G), potential(_G){ }
115 ///Runs the algorithm.
117 ///Runs the algorithm.
118 ///Returns k if there is a flow of value at least k edge-disjoint
120 ///Otherwise it returns the maximum value of a flow from s to t.
122 ///\param s The source node.
123 ///\param t The target node.
124 ///\param k The value of the flow we are looking for.
126 ///\todo May be it does make sense to be able to start with a nonzero
127 /// feasible primal-dual solution pair as well.
128 int run(Node s, Node t, int k) {
130 //Resetting variables from previous runs
133 for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
135 //Initialize the potential to zero
136 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
139 //We need a residual graph
140 ResGraphType res_graph(G, capacity, flow);
143 ModLengthMap mod_length(res_graph, length, potential);
145 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
150 if (!dijkstra.reached(t)){
151 //There are no flow of value k from s to t
155 //We have to change the potential
156 for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
157 potential[n] += dijkstra.distMap()[n];
160 //Augmenting on the sortest path
164 e = dijkstra.pred(n);
165 n = dijkstra.predNode(n);
166 res_graph.augment(e,1);
167 //Let's update the total length
168 if (res_graph.forward(e))
169 total_length += length[e];
171 total_length -= length[e];
183 /// Gives back the total weight of the found flow.
185 ///This function gives back the total weight of the found flow.
186 ///Assumes that \c run() has been run and nothing changed since then.
187 Length totalLength(){
191 ///Returns a const reference to the EdgeMap \c flow.
193 ///Returns a const reference to the EdgeMap \c flow.
194 ///\pre \ref run() must
195 ///be called before using this function.
196 const EdgeIntMap &getFlow() const { return flow;}
198 ///Returns a const reference to the NodeMap \c potential (the dual solution).
200 ///Returns a const reference to the NodeMap \c potential (the dual solution).
201 /// \pre \ref run() must be called before using this function.
202 const PotentialMap &getPotential() const { return potential;}
204 /// Checking the complementary slackness optimality criteria
206 ///This function checks, whether the given solution is optimal
207 ///If executed after the call of \c run() then it should return with true.
208 ///This function only checks optimality, doesn't bother with feasibility.
209 ///It is meant for testing purposes.
211 bool checkComplementarySlackness(){
214 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
216 mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
218 if (0<fl_e && fl_e<capacity[e]) {
219 /// \todo better comparison is needed for real types, moreover,
220 /// this comparison here is superfluous.
225 if (mod_pot > 0 && fl_e != 0)
227 if (mod_pot < 0 && fl_e != capacity[e])
235 }; //class MinCostFlows
241 #endif //HUGO_MINCOSTFLOWS_H