1.1 --- a/src/work/athos/makefile Tue May 11 14:58:09 2004 +0000
1.2 +++ b/src/work/athos/makefile Tue May 11 15:42:11 2004 +0000
1.3 @@ -1,4 +1,4 @@
1.4 -BINARIES = suurballe minlength_demo mincostflows_test
1.5 +BINARIES = minlengthpaths_test minlength_demo
1.6 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
1.7 include ../makefile
1.8
2.1 --- a/src/work/athos/mincostflows.h Tue May 11 14:58:09 2004 +0000
2.2 +++ b/src/work/athos/mincostflows.h Tue May 11 15:42:11 2004 +0000
2.3 @@ -8,7 +8,7 @@
2.4
2.5 #include <iostream>
2.6 #include <hugo/dijkstra.h>
2.7 -#include <graph_wrapper.h>
2.8 +#include <hugo/graph_wrapper.h>
2.9 #include <hugo/maps.h>
2.10 #include <vector>
2.11 #include <for_each_macros.h>
2.12 @@ -77,12 +77,14 @@
2.13 };//ModLengthMap
2.14
2.15
2.16 + protected:
2.17
2.18 //Input
2.19 const Graph& G;
2.20 const LengthMap& length;
2.21 const CapacityMap& capacity;
2.22
2.23 +
2.24 //auxiliary variables
2.25
2.26 //To store the flow
2.27 @@ -98,6 +100,7 @@
2.28
2.29 Length total_length;
2.30
2.31 +
2.32 public :
2.33
2.34
2.35 @@ -110,6 +113,8 @@
2.36 ///Runs the algorithm.
2.37 ///Returns k if there are at least k edge-disjoint paths from s to t.
2.38 ///Otherwise it returns the number of found edge-disjoint paths from s to t.
2.39 + ///\todo May be it does make sense to be able to start with a nonzero
2.40 + /// feasible primal-dual solution pair as well.
2.41 int run(Node s, Node t, int k) {
2.42
2.43 //Resetting variables from previous runs
2.44 @@ -185,10 +190,20 @@
2.45 return total_length;
2.46 }
2.47
2.48 - //This function checks, whether the given solution is optimal
2.49 - //Running after a \c run() should return with true
2.50 - //In this "state of the art" this only check optimality, doesn't bother with feasibility
2.51 - bool checkSolution(){
2.52 + ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
2.53 + ///be called before using this function.
2.54 + const EdgeIntMap &getFlow() const { return flow;}
2.55 +
2.56 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
2.57 + /// \pre \ref run() must be called before using this function.
2.58 + const EdgeIntMap &getPotential() const { return potential;}
2.59 +
2.60 + ///This function checks, whether the given solution is optimal
2.61 + ///Running after a \c run() should return with true
2.62 + ///In this "state of the art" this only check optimality, doesn't bother with feasibility
2.63 + ///
2.64 + ///\todo Is this OK here?
2.65 + bool checkComplementarySlackness(){
2.66 Length mod_pot;
2.67 Length fl_e;
2.68 FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
3.1 --- a/src/work/athos/minlength_demo.cc Tue May 11 14:58:09 2004 +0000
3.2 +++ b/src/work/athos/minlength_demo.cc Tue May 11 15:42:11 2004 +0000
3.3 @@ -2,8 +2,9 @@
3.4 #include <fstream>
3.5
3.6 #include <list_graph.h>
3.7 -#include <dimacs.h>
3.8 -#include <minlengthpaths.h>
3.9 +#include <hugo/dimacs.h>
3.10 +#include <hugo/time_measure.h>
3.11 +#include "minlengthpaths.h"
3.12 //#include <time_measure.h>
3.13
3.14 using namespace hugo;
3.15 @@ -19,9 +20,9 @@
3.16 Graph G;
3.17 Node s, t;
3.18 Graph::EdgeMap<int> cap(G);
3.19 - readDimacsMaxFlow(std::cin, G, s, t, cap);
3.20 + readDimacs(std::cin, G, cap, s, t);
3.21
3.22 - std::cout << "preflow demo (ATHOS)..." << std::endl;
3.23 + std::cout << "Minlengthpaths demo (ATHOS)..." << std::endl;
3.24 //Graph::EdgeMap<int> flow(G); //0 flow
3.25
3.26 // double pre_time=currTime();
3.27 @@ -31,8 +32,14 @@
3.28 k = atoi(argv[1]);
3.29 MinLengthPaths<Graph, Graph::EdgeMap<int> >
3.30 surb_test(G,cap);
3.31 - std::cout << surb_test.run(s,t,k) << std::endl;
3.32 - std::cout << surb_test.totalLength() << std::endl;
3.33 + Timer ts;
3.34 + ts.reset();
3.35 + std::cout << "Number of found paths: " << surb_test.run(s,t,k) << std::endl;
3.36 + std::cout << "elapsed time: " << ts << std::endl;
3.37 +
3.38 + std::cout << "Total length of found paths: " << surb_test.totalLength() << std::endl;
3.39 + //std::cout << (surb_test.checkComplementarySlackness() ? "OK (compl. slackn.)." : "Problem (compl. slackn.)!!!") << std::endl;
3.40 +
3.41 //preflow_push<Graph, int> max_flow_test(G, s, t, cap);
3.42 //int flow_value=max_flow_test.run();
3.43
4.1 --- a/src/work/athos/minlengthpaths.h Tue May 11 14:58:09 2004 +0000
4.2 +++ b/src/work/athos/minlengthpaths.h Tue May 11 15:42:11 2004 +0000
4.3 @@ -7,11 +7,12 @@
4.4 ///\brief An algorithm for finding k paths of minimal total length.
4.5
4.6 #include <iostream>
4.7 -#include <dijkstra.h>
4.8 -#include <graph_wrapper.h>
4.9 -#include <maps.h>
4.10 -#include <vector.h>
4.11 -
4.12 +//#include <hugo/dijkstra.h>
4.13 +//#include <hugo/graph_wrapper.h>
4.14 +#include <hugo/maps.h>
4.15 +#include <vector>
4.16 +#include <mincostflows.h>
4.17 +#include <for_each_macros.h>
4.18
4.19 namespace hugo {
4.20
4.21 @@ -26,9 +27,13 @@
4.22 /// from a given source node to a given target node in an
4.23 /// edge-weighted directed graph having minimal total weigth (length).
4.24 ///
4.25 + ///\warning It is assumed that the lengths are positive, since the
4.26 + /// general flow-decomposition is not implemented yet.
4.27 + ///
4.28 ///\author Attila Bernath
4.29 template <typename Graph, typename LengthMap>
4.30 - class MinLengthPaths {
4.31 + class MinLengthPaths{
4.32 +
4.33
4.34 typedef typename LengthMap::ValueType Length;
4.35
4.36 @@ -40,114 +45,50 @@
4.37
4.38 typedef ConstMap<Edge,int> ConstMap;
4.39
4.40 - typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
4.41 + //Input
4.42 + const Graph& G;
4.43
4.44 - class ModLengthMap {
4.45 - typedef typename ResGraphType::template NodeMap<Length> NodeMap;
4.46 - const ResGraphType& G;
4.47 - const EdgeIntMap& rev;
4.48 - const LengthMap &ol;
4.49 - const NodeMap &pot;
4.50 - public :
4.51 - typedef typename LengthMap::KeyType KeyType;
4.52 - typedef typename LengthMap::ValueType ValueType;
4.53 -
4.54 - ValueType operator[](typename ResGraphType::Edge e) const {
4.55 - //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
4.56 - // std::cout<<"Negative length!!"<<std::endl;
4.57 - //}
4.58 - return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
4.59 - }
4.60 -
4.61 - ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
4.62 - const LengthMap &o, const NodeMap &p) :
4.63 - G(_G), rev(_rev), ol(o), pot(p){};
4.64 - };//ModLengthMap
4.65 + //Auxiliary variables
4.66 + //This is the capacity map for the mincostflow problem
4.67 + ConstMap const1map;
4.68 + //This MinCostFlows instance will actually solve the problem
4.69 + MinCostFlows<Graph, LengthMap, ConstMap> mincost_flow;
4.70
4.71 -
4.72 -
4.73 -
4.74 - const Graph& G;
4.75 - const LengthMap& length;
4.76 -
4.77 - //auxiliary variables
4.78 -
4.79 - //The value is 1 iff the edge is reversed.
4.80 - //If the algorithm has finished, the edges of the seeked paths are
4.81 - //exactly those that are reversed
4.82 - EdgeIntMap reversed;
4.83 -
4.84 //Container to store found paths
4.85 std::vector< std::vector<Edge> > paths;
4.86 - //typedef DirPath<Graph> DPath;
4.87 - //DPath paths;
4.88 -
4.89 -
4.90 - Length total_length;
4.91
4.92 public :
4.93
4.94
4.95 - MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
4.96 - length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
4.97 + MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
4.98 + const1map(1), mincost_flow(_G, _length, const1map){}
4.99
4.100 -
4.101 ///Runs the algorithm.
4.102
4.103 ///Runs the algorithm.
4.104 ///Returns k if there are at least k edge-disjoint paths from s to t.
4.105 - ///Otherwise it returns the number of found edge-disjoint paths from s to t.
4.106 + ///Otherwise it returns the number of found edge-disjoint paths from s to t.
4.107 int run(Node s, Node t, int k) {
4.108 - ConstMap const1map(1);
4.109
4.110 + int i = mincost_flow.run(s,t,k);
4.111 +
4.112
4.113 - //We need a residual graph, in which some of the edges are reversed
4.114 - ResGraphType res_graph(G, const1map, reversed);
4.115
4.116 - //Initialize the copy of the Dijkstra potential to zero
4.117 - typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
4.118 - ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
4.119 -
4.120 - Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
4.121 -
4.122 - int i;
4.123 - for (i=0; i<k; ++i){
4.124 - dijkstra.run(s);
4.125 - if (!dijkstra.reached(t)){
4.126 - //There are no k paths from s to t
4.127 - break;
4.128 - };
4.129 -
4.130 - {
4.131 - //We have to copy the potential
4.132 - typename ResGraphType::NodeIt n;
4.133 - for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
4.134 - dijkstra_dist[n] += dijkstra.distMap()[n];
4.135 - }
4.136 - }
4.137 -
4.138 -
4.139 - //Reversing the sortest path
4.140 - Node n=t;
4.141 - Edge e;
4.142 - while (n!=s){
4.143 - e = dijkstra.pred(n);
4.144 - n = dijkstra.predNode(n);
4.145 - reversed[e] = 1-reversed[e];
4.146 - }
4.147 -
4.148 -
4.149 - }
4.150 -
4.151 //Let's find the paths
4.152 //We put the paths into stl vectors (as an inner representation).
4.153 //In the meantime we lose the information stored in 'reversed'.
4.154 //We suppose the lengths to be positive now.
4.155
4.156 - //Meanwhile we put the total length of the found paths
4.157 - //in the member variable total_length
4.158 + //We don't want to change the flow of mincost_flow, so we make a copy
4.159 + //The name here suggests that the flow has only 0/1 values.
4.160 + EdgeIntMap reversed(G);
4.161 +
4.162 + FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
4.163 + reversed[e] = mincost_flow.getFlow()[e];
4.164 + }
4.165 +
4.166 paths.clear();
4.167 - total_length=0;
4.168 + //total_length=0;
4.169 paths.resize(k);
4.170 for (int j=0; j<i; ++j){
4.171 Node n=s;
4.172 @@ -163,27 +104,48 @@
4.173 }
4.174 n = G.head(e);
4.175 paths[j].push_back(e);
4.176 - total_length += length[e];
4.177 + //total_length += length[e];
4.178 reversed[e] = 1-reversed[e];
4.179 }
4.180
4.181 }
4.182 -
4.183 return i;
4.184 }
4.185
4.186 +
4.187 ///This function gives back the total length of the found paths.
4.188 ///Assumes that \c run() has been run and nothing changed since then.
4.189 Length totalLength(){
4.190 - return total_length;
4.191 + return mincost_flow.totalLength();
4.192 + }
4.193 +
4.194 + ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
4.195 + ///be called before using this function.
4.196 + const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
4.197 +
4.198 + ///Returns a const reference to the NodeMap \c potential (the dual solution).
4.199 + /// \pre \ref run() must be called before using this function.
4.200 + const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
4.201 +
4.202 + ///This function checks, whether the given solution is optimal
4.203 + ///Running after a \c run() should return with true
4.204 + ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
4.205 + ///
4.206 + ///\todo Is this OK here?
4.207 + bool checkComplementarySlackness(){
4.208 + return mincost_flow.checkComplementarySlackness();
4.209 }
4.210
4.211 ///This function gives back the \c j-th path in argument p.
4.212 ///Assumes that \c run() has been run and nothing changed since then.
4.213 - /// \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.
4.214 + /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is not less than the result of previous \c run, then the result here will be an empty path (\c j can be 0 as well).
4.215 template<typename DirPath>
4.216 - void getPath(DirPath& p, int j){
4.217 + void getPath(DirPath& p, size_t j){
4.218 +
4.219 p.clear();
4.220 + if (j>paths.size()-1){
4.221 + return;
4.222 + }
4.223 typename DirPath::Builder B(p);
4.224 for(typename std::vector<Edge>::iterator i=paths[j].begin();
4.225 i!=paths[j].end(); ++i ){
5.1 --- a/src/work/athos/minlengthpaths_test.cc Tue May 11 14:58:09 2004 +0000
5.2 +++ b/src/work/athos/minlengthpaths_test.cc Tue May 11 15:42:11 2004 +0000
5.3 @@ -69,6 +69,8 @@
5.4
5.5 check( surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
5.6
5.7 + check( surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");
5.8 +
5.9 typedef DirPath<ListGraph> DPath;
5.10 DPath P(graph);
5.11
5.12 @@ -80,6 +82,8 @@
5.13
5.14 k=1;
5.15 check( surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
5.16 +
5.17 + check( surb_test.checkComplementarySlackness(), "Complementary slackness conditions are not met.");
5.18
5.19 surb_test.getPath(P,0);
5.20 check(P.length() == 4, "First path should contain 4 edges.");
6.1 --- a/src/work/athos/old/minlengthpaths.h Tue May 11 14:58:09 2004 +0000
6.2 +++ b/src/work/athos/old/minlengthpaths.h Tue May 11 15:42:11 2004 +0000
6.3 @@ -7,10 +7,10 @@
6.4 ///\brief An algorithm for finding k paths of minimal total length.
6.5
6.6 #include <iostream>
6.7 -#include <dijkstra.h>
6.8 -#include <graph_wrapper.h>
6.9 -#include <maps.h>
6.10 -#include <vector.h>
6.11 +#include <hugo/dijkstra.h>
6.12 +#include <hugo/graph_wrapper.h>
6.13 +#include <hugo/maps.h>
6.14 +#include <vector>
6.15
6.16
6.17 namespace hugo {
7.1 --- a/src/work/klao/path.h Tue May 11 14:58:09 2004 +0000
7.2 +++ b/src/work/klao/path.h Tue May 11 15:42:11 2004 +0000
7.3 @@ -11,8 +11,8 @@
7.4 #include <vector>
7.5 #include <algorithm>
7.6
7.7 -#include <invalid.h>
7.8 -#include <error.h>
7.9 +#include <hugo/invalid.h>
7.10 +#include <hugo/error.h>
7.11 #include <debug.h>
7.12
7.13 namespace hugo {