Minimum cost flows of small values: algorithm from Andras Frank's lecture notes (approximately)
1.1 --- a/src/work/athos/mincostflows.h Tue May 04 16:17:17 2004 +0000
1.2 +++ b/src/work/athos/mincostflows.h Tue May 04 16:52:15 2004 +0000
1.3 @@ -11,7 +11,7 @@
1.4 #include <graph_wrapper.h>
1.5 #include <maps.h>
1.6 #include <vector.h>
1.7 -
1.8 +#include <for_each_macros.h>
1.9
1.10 namespace hugo {
1.11
1.12 @@ -34,12 +34,13 @@
1.13 /// where \c M is the value of the maximal flow.
1.14 ///
1.15 ///\author Attila Bernath
1.16 - template <typename Graph, typename LengthMap>
1.17 + template <typename Graph, typename LengthMap, typename CapacityMap>
1.18 class MinCostFlows {
1.19
1.20 typedef typename LengthMap::ValueType Length;
1.21
1.22 - typedef typename LengthMap::ValueType Length;
1.23 + //Warning: this should be integer type
1.24 + typedef typename CapacityMap::ValueType Capacity;
1.25
1.26 typedef typename Graph::Node Node;
1.27 typedef typename Graph::NodeIt NodeIt;
1.28 @@ -49,8 +50,8 @@
1.29
1.30 // typedef ConstMap<Edge,int> ConstMap;
1.31
1.32 - typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType;
1.33 -
1.34 + typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
1.35 + typedef typename ResGraphType::Edge ResGraphEdge;
1.36 class ModLengthMap {
1.37 typedef typename ResGraphType::template NodeMap<Length> NodeMap;
1.38 const ResGraphType& G;
1.39 @@ -68,7 +69,7 @@
1.40 return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
1.41 }
1.42
1.43 - ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
1.44 + ModLengthMap(const ResGraphType& _G,
1.45 const LengthMap &o, const NodeMap &p) :
1.46 G(_G), /*rev(_rev),*/ ol(o), pot(p){};
1.47 };//ModLengthMap
1.48 @@ -78,7 +79,7 @@
1.49 //Input
1.50 const Graph& G;
1.51 const LengthMap& length;
1.52 - const EdgeIntMap& capacity;
1.53 + const CapacityMap& capacity;
1.54
1.55 //auxiliary variables
1.56
1.57 @@ -98,7 +99,7 @@
1.58 public :
1.59
1.60
1.61 - MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G),
1.62 + MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
1.63 length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ }
1.64
1.65
1.66 @@ -109,7 +110,13 @@
1.67 ///Otherwise it returns the number of found edge-disjoint paths from s to t.
1.68 int run(Node s, Node t, int k) {
1.69
1.70 + //Resetting variables from previous runs
1.71 + total_length = 0;
1.72 + FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
1.73 + flow.set(e,0);
1.74 + }
1.75
1.76 +
1.77 //We need a residual graph
1.78 ResGraphType res_graph(G, capacity, flow);
1.79
1.80 @@ -138,59 +145,36 @@
1.81
1.82 //Augmenting on the sortest path
1.83 Node n=t;
1.84 - Edge e;
1.85 + ResGraphEdge e;
1.86 while (n!=s){
1.87 e = dijkstra.pred(n);
1.88 n = dijkstra.predNode(n);
1.89 - G.augment(e,1);
1.90 + res_graph.augment(e,1);
1.91 + //Let's update the total length
1.92 + if (res_graph.forward(e))
1.93 + total_length += length[e];
1.94 + else
1.95 + total_length -= length[e];
1.96 }
1.97
1.98
1.99 }
1.100
1.101 - /*
1.102 - ///\TODO To be implemented later
1.103 -
1.104 - //Let's find the paths
1.105 - //We put the paths into stl vectors (as an inner representation).
1.106 - //In the meantime we lose the information stored in 'reversed'.
1.107 - //We suppose the lengths to be positive now.
1.108 -
1.109 - //Meanwhile we put the total length of the found paths
1.110 - //in the member variable total_length
1.111 - paths.clear();
1.112 - total_length=0;
1.113 - paths.resize(k);
1.114 - for (int j=0; j<i; ++j){
1.115 - Node n=s;
1.116 - OutEdgeIt e;
1.117 -
1.118 - while (n!=t){
1.119 -
1.120 -
1.121 - G.first(e,n);
1.122 -
1.123 - while (!reversed[e]){
1.124 - G.next(e);
1.125 - }
1.126 - n = G.head(e);
1.127 - paths[j].push_back(e);
1.128 - total_length += length[e];
1.129 - reversed[e] = 1-reversed[e];
1.130 - }
1.131 -
1.132 - }
1.133 - */
1.134
1.135 return i;
1.136 }
1.137
1.138 +
1.139 +
1.140 ///This function gives back the total length of the found paths.
1.141 ///Assumes that \c run() has been run and nothing changed since then.
1.142 Length totalLength(){
1.143 return total_length;
1.144 }
1.145
1.146 + /*
1.147 + ///\todo To be implemented later
1.148 +
1.149 ///This function gives back the \c j-th path in argument p.
1.150 ///Assumes that \c run() has been run and nothing changed since then.
1.151 /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is greater than the result of previous \c run, then the result here will be an empty path.
1.152 @@ -206,7 +190,9 @@
1.153 B.commit();
1.154 }
1.155
1.156 - }; //class MinLengthPaths
1.157 + */
1.158 +
1.159 + }; //class MinCostFlows
1.160
1.161 ///@}
1.162
2.1 --- a/src/work/athos/mincostflows_test.cc Tue May 04 16:17:17 2004 +0000
2.2 +++ b/src/work/athos/mincostflows_test.cc Tue May 04 16:52:15 2004 +0000
2.3 @@ -61,16 +61,21 @@
2.4 length.set(v4_t, 8);
2.5 length.set(v5_t, 8);
2.6
2.7 - ConstMap const1map(1);
2.8 - std::cout << "Minlengthpaths algorithm test..." << std::endl;
2.9 + ConstMap<Edge, int> const1map(1);
2.10 + std::cout << "Mincostflows algorithm test..." << std::endl;
2.11
2.12
2.13 int k=3;
2.14 - MinCostFlows< ListGraph, ListGraph::EdgeMap<int> >
2.15 + MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
2.16 surb_test(graph, length, const1map);
2.17
2.18 check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
2.19
2.20 + k=1;
2.21 + check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
2.22 +
2.23 + //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;
2.24 + /*
2.25 typedef DirPath<ListGraph> DPath;
2.26 DPath P(graph);
2.27
2.28 @@ -85,7 +90,7 @@
2.29
2.30 surb_test.getPath(P,0);
2.31 check(P.length() == 4, "First path should contain 4 edges.");
2.32 -
2.33 + */
2.34 cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
2.35 << endl;
2.36