1.1 --- a/src/work/athos/makefile Mon May 03 10:04:27 2004 +0000
1.2 +++ b/src/work/athos/makefile Mon May 03 10:27:20 2004 +0000
1.3 @@ -1,29 +1,4 @@
1.4 -CXX2 = g++-2.95
1.5 -CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
1.6 -CXX=$(CXX3)
1.7 -CC=$(CXX)
1.8 -#LEDAROOT ?= /ledasrc/LEDA-4.1
1.9 -#BOOSTROOT ?= /home/marci/boost
1.10 -INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
1.11 -#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
1.12 -CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.13 +BINARIES = suurballe minlength_demo
1.14 +INCLUDEDIRS= -I../../include -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
1.15 +include ../makefile
1.16
1.17 -#LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
1.18 -BINARIES = suurballe
1.19 -#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
1.20 -
1.21 -all: $(BINARIES)
1.22 -
1.23 -.depend dep depend:
1.24 - -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
1.25 -# -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
1.26 -
1.27 -
1.28 -
1.29 -makefile: .depend
1.30 -sinclude .depend
1.31 -
1.32 -clean:
1.33 - $(RM) *.o $(BINARIES) .depend
1.34 -
1.35 -.PHONY: all clean dep depend
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/athos/minlength_demo.cc Mon May 03 10:27:20 2004 +0000
2.3 @@ -0,0 +1,45 @@
2.4 +#include <iostream>
2.5 +#include <fstream>
2.6 +
2.7 +#include <list_graph.h>
2.8 +#include <dimacs.h>
2.9 +#include <minlengthpaths.h>
2.10 +//#include <time_measure.h>
2.11 +
2.12 +using namespace hugo;
2.13 +
2.14 +// Use a DIMACS max flow file as stdin.
2.15 +// read_dimacs_demo < dimacs_max_flow_file
2.16 +int main(int argc, char ** argv) {
2.17 + typedef ListGraph Graph;
2.18 +
2.19 + typedef Graph::Node Node;
2.20 + //typedef Graph::EachEdgeIt EachEdgeIt;
2.21 +
2.22 + Graph G;
2.23 + Node s, t;
2.24 + Graph::EdgeMap<int> cap(G);
2.25 + readDimacsMaxFlow(std::cin, G, s, t, cap);
2.26 +
2.27 + std::cout << "preflow demo (ATHOS)..." << std::endl;
2.28 + //Graph::EdgeMap<int> flow(G); //0 flow
2.29 +
2.30 + // double pre_time=currTime();
2.31 +
2.32 + int k=1;
2.33 + if (argc>1)
2.34 + k = atoi(argv[1]);
2.35 + MinLengthPaths<Graph, Graph::EdgeMap<int> >
2.36 + surb_test(G,cap);
2.37 + std::cout << surb_test.run(s,t,k) << std::endl;
2.38 + std::cout << surb_test.totalLength() << std::endl;
2.39 + //preflow_push<Graph, int> max_flow_test(G, s, t, cap);
2.40 + //int flow_value=max_flow_test.run();
2.41 +
2.42 + //double post_time=currTime();
2.43 +
2.44 + //std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
2.45 + //std::cout << "flow value: "<< flow_value << std::endl;
2.46 +
2.47 + return 0;
2.48 +}
3.1 --- a/src/work/athos/minlengthpaths.h Mon May 03 10:04:27 2004 +0000
3.2 +++ b/src/work/athos/minlengthpaths.h Mon May 03 10:27:20 2004 +0000
3.3 @@ -10,7 +10,7 @@
3.4 #include <dijkstra.h>
3.5 #include <graph_wrapper.h>
3.6 #include <maps.h>
3.7 -#include <vector>
3.8 +#include <vector.h>
3.9
3.10
3.11 namespace hugo {
3.12 @@ -31,20 +31,19 @@
3.13 class MinLengthPaths {
3.14
3.15 typedef typename LengthMap::ValueType Length;
3.16 -
3.17 +
3.18 typedef typename Graph::Node Node;
3.19 typedef typename Graph::NodeIt NodeIt;
3.20 typedef typename Graph::Edge Edge;
3.21 typedef typename Graph::OutEdgeIt OutEdgeIt;
3.22 - typedef typename Graph::EdgeMap<int> EdgeIntMap;
3.23 + typedef typename Graph::template EdgeMap<int> EdgeIntMap;
3.24
3.25 typedef ConstMap<Edge,int> ConstMap;
3.26
3.27 typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
3.28
3.29 -
3.30 class ModLengthMap {
3.31 - typedef typename ResGraphType::NodeMap<Length> NodeMap;
3.32 + typedef typename ResGraphType::template NodeMap<Length> NodeMap;
3.33 const ResGraphType& G;
3.34 const EdgeIntMap& rev;
3.35 const LengthMap &ol;
3.36 @@ -52,18 +51,20 @@
3.37 public :
3.38 typedef typename LengthMap::KeyType KeyType;
3.39 typedef typename LengthMap::ValueType ValueType;
3.40 -
3.41 +
3.42 ValueType operator[](typename ResGraphType::Edge e) const {
3.43 //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
3.44 // std::cout<<"Negative length!!"<<std::endl;
3.45 //}
3.46 return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
3.47 }
3.48 -
3.49 +
3.50 ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
3.51 const LengthMap &o, const NodeMap &p) :
3.52 G(_G), rev(_rev), ol(o), pot(p){};
3.53 - };
3.54 + };//ModLengthMap
3.55 +
3.56 +
3.57
3.58
3.59 const Graph& G;
3.60 @@ -78,6 +79,11 @@
3.61
3.62 //Container to store found paths
3.63 std::vector< std::vector<Edge> > paths;
3.64 + //typedef DirPath<Graph> DPath;
3.65 + //DPath paths;
3.66 +
3.67 +
3.68 + Length total_length;
3.69
3.70 public :
3.71
3.72 @@ -94,11 +100,12 @@
3.73 int run(Node s, Node t, int k) {
3.74 ConstMap const1map(1);
3.75
3.76 +
3.77 //We need a residual graph, in which some of the edges are reversed
3.78 ResGraphType res_graph(G, const1map, reversed);
3.79
3.80 //Initialize the copy of the Dijkstra potential to zero
3.81 - typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
3.82 + typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
3.83 ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
3.84
3.85 Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
3.86 @@ -133,10 +140,14 @@
3.87 }
3.88
3.89 //Let's find the paths
3.90 - //We put the paths into vectors (just for now). In the meantime we lose
3.91 - //the information stored in 'reversed'
3.92 + //We put the paths into stl vectors (as an inner representation).
3.93 + //In the meantime we lose the information stored in 'reversed'.
3.94 //We suppose the lengths to be positive now.
3.95 +
3.96 + //Meanwhile we put the total length of the found paths
3.97 + //in the member variable total_length
3.98 paths.clear();
3.99 + total_length=0;
3.100 paths.resize(k);
3.101 for (int j=0; j<i; ++j){
3.102 Node n=s;
3.103 @@ -152,6 +163,7 @@
3.104 }
3.105 n = G.head(e);
3.106 paths[j].push_back(e);
3.107 + total_length += length[e];
3.108 reversed[e] = 1-reversed[e];
3.109 }
3.110
3.111 @@ -160,6 +172,26 @@
3.112 return i;
3.113 }
3.114
3.115 + ///This function gives back the total length of the found paths.
3.116 + ///Assumes that \c run() has been run and nothing changed since then.
3.117 + Length totalLength(){
3.118 + return total_length;
3.119 + }
3.120 +
3.121 + ///This function gives back the \c j-th path in argument p.
3.122 + ///Assumes that \c run() has been run and nothing changed since then.
3.123 + /// \warning It is assumed that \c p is constructed to be a path of graph \c G.
3.124 + template<typename DirPath>
3.125 + void getPath(DirPath& p, int j){
3.126 + p.clear();
3.127 + typename DirPath::Builder B(p);
3.128 + for(typename std::vector<Edge>::iterator i=paths[j].begin();
3.129 + i!=paths[j].end(); ++i ){
3.130 + B.pushBack(*j);
3.131 + }
3.132 +
3.133 + B.commit();
3.134 + }
3.135
3.136 }; //class MinLengthPaths
3.137