Nicer and more documented graph_wrapper.h file.
These are only the first steps for making this file more beautiful.
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 ///(for small values of \c k) having minimal total cost
27 /// from a given source node to a given target node in an
28 /// edge-weighted directed graph having nonnegative integer capacities.
29 /// The range of the length (weight) function is nonnegative reals but
30 /// the range of capacity function is the set of nonnegative integers.
31 /// It is not a polinomial time algorithm for counting the minimum cost
32 /// maximal flow, since it counts the minimum cost flow for every value 0..M
33 /// where \c M is the value of the maximal flow.
35 ///\author Attila Bernath
36 template <typename Graph, typename LengthMap, typename CapacityMap>
39 typedef typename LengthMap::ValueType Length;
41 //Warning: this should be integer type
42 typedef typename CapacityMap::ValueType Capacity;
44 typedef typename Graph::Node Node;
45 typedef typename Graph::NodeIt NodeIt;
46 typedef typename Graph::Edge Edge;
47 typedef typename Graph::OutEdgeIt OutEdgeIt;
48 typedef typename Graph::template EdgeMap<int> EdgeIntMap;
50 // typedef ConstMap<Edge,int> ConstMap;
52 typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
53 typedef typename ResGraphType::Edge ResGraphEdge;
56 //typedef typename ResGraphType::template NodeMap<Length> NodeMap;
57 typedef typename Graph::template NodeMap<Length> NodeMap;
58 const ResGraphType& G;
59 // const EdgeIntMap& rev;
63 typedef typename LengthMap::KeyType KeyType;
64 typedef typename LengthMap::ValueType ValueType;
66 ValueType operator[](typename ResGraphType::Edge e) const {
68 return ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
70 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
73 ModLengthMap(const ResGraphType& _G,
74 const LengthMap &o, const NodeMap &p) :
75 G(_G), /*rev(_rev),*/ ol(o), pot(p){};
83 const LengthMap& length;
84 const CapacityMap& capacity;
91 //To store the potential (dual variables)
92 typedef typename Graph::template NodeMap<Length> PotentialMap;
93 PotentialMap potential;
102 MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
103 length(_length), capacity(_cap), flow(_G), potential(_G){ }
106 ///Runs the algorithm.
108 ///Runs the algorithm.
109 ///Returns k if there are at least k edge-disjoint paths from s to t.
110 ///Otherwise it returns the number of found edge-disjoint paths from s to t.
111 ///\todo May be it does make sense to be able to start with a nonzero
112 /// feasible primal-dual solution pair as well.
113 int run(Node s, Node t, int k) {
115 //Resetting variables from previous runs
118 for (typename Graph::EdgeIt e(G); e!=INVALID; ++e) flow.set(e, 0);
120 //Initialize the potential to zero
121 for (typename Graph::NodeIt n(G); n!=INVALID; ++n) potential.set(n, 0);
124 //We need a residual graph
125 ResGraphType res_graph(G, capacity, flow);
128 ModLengthMap mod_length(res_graph, length, potential);
130 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
135 if (!dijkstra.reached(t)){
136 //There are no k paths from s to t
140 //We have to change the potential
141 for(typename ResGraphType::NodeIt n(res_graph); n!=INVALID; ++n)
142 potential[n] += dijkstra.distMap()[n];
145 //Augmenting on the sortest path
149 e = dijkstra.pred(n);
150 n = dijkstra.predNode(n);
151 res_graph.augment(e,1);
152 //Let's update the total length
153 if (res_graph.forward(e))
154 total_length += length[e];
156 total_length -= length[e];
169 ///This function gives back the total length of the found paths.
170 ///Assumes that \c run() has been run and nothing changed since then.
171 Length totalLength(){
175 ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
176 ///be called before using this function.
177 const EdgeIntMap &getFlow() const { return flow;}
179 ///Returns a const reference to the NodeMap \c potential (the dual solution).
180 /// \pre \ref run() must be called before using this function.
181 const PotentialMap &getPotential() const { return potential;}
183 ///This function checks, whether the given solution is optimal
184 ///Running after a \c run() should return with true
185 ///In this "state of the art" this only check optimality, doesn't bother with feasibility
187 ///\todo Is this OK here?
188 bool checkComplementarySlackness(){
191 for(typename Graph::EdgeIt e(G); e!=INVALID; ++e) {
193 mod_pot = length[e]-potential[G.head(e)]+potential[G.tail(e)];
195 // std::cout << fl_e << std::endl;
196 if (0<fl_e && fl_e<capacity[e]){
201 if (mod_pot > 0 && fl_e != 0)
203 if (mod_pot < 0 && fl_e != capacity[e])
211 }; //class MinCostFlows
217 #endif //HUGO_MINCOSTFLOWS_H