# HG changeset patch
# User athos
# Date 1083580040 0
# Node ID 325c9430723e13e10537cbf28308e2cb598f037b
# Parent  72143568cadcbfe48d5a5c021ad54093c621901c
getPath() function implemented.

diff -r 72143568cadc -r 325c9430723e src/work/athos/makefile
--- a/src/work/athos/makefile	Mon May 03 10:04:27 2004 +0000
+++ b/src/work/athos/makefile	Mon May 03 10:27:20 2004 +0000
@@ -1,29 +1,4 @@
-CXX2 = g++-2.95
-CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
-CXX=$(CXX3)
-CC=$(CXX)
-#LEDAROOT ?= /ledasrc/LEDA-4.1
-#BOOSTROOT ?= /home/marci/boost
-INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
-#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
-CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
+BINARIES = suurballe minlength_demo
+INCLUDEDIRS= -I../../include -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos} 
+include ../makefile
 
-#LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = suurballe
-#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
-
-all: $(BINARIES)
-
-.depend dep depend:
-	-$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
-#	-g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
-
-
-
-makefile: .depend
-sinclude .depend
-
-clean:
-	$(RM) *.o $(BINARIES) .depend
-
-.PHONY: all clean dep depend
diff -r 72143568cadc -r 325c9430723e src/work/athos/minlength_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/minlength_demo.cc	Mon May 03 10:27:20 2004 +0000
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.h>
+#include <dimacs.h>
+#include <minlengthpaths.h>
+//#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int argc, char ** argv) {
+  typedef ListGraph Graph;
+
+  typedef Graph::Node Node;
+  //typedef Graph::EachEdgeIt EachEdgeIt;
+
+  Graph G;
+  Node s, t;
+  Graph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow demo (ATHOS)..." << std::endl;
+  //Graph::EdgeMap<int> flow(G); //0 flow
+
+  //  double pre_time=currTime();
+
+  int k=1;
+  if (argc>1)
+    k = atoi(argv[1]);
+  MinLengthPaths<Graph, Graph::EdgeMap<int> >
+    surb_test(G,cap);
+  std::cout << surb_test.run(s,t,k) << std::endl;
+  std::cout << surb_test.totalLength() << std::endl;
+  //preflow_push<Graph, int> max_flow_test(G, s, t, cap);
+  //int flow_value=max_flow_test.run();
+
+  //double post_time=currTime();
+
+  //std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
+  //std::cout << "flow value: "<< flow_value << std::endl;
+
+  return 0;
+}
diff -r 72143568cadc -r 325c9430723e src/work/athos/minlengthpaths.h
--- a/src/work/athos/minlengthpaths.h	Mon May 03 10:04:27 2004 +0000
+++ b/src/work/athos/minlengthpaths.h	Mon May 03 10:27:20 2004 +0000
@@ -10,7 +10,7 @@
 #include <dijkstra.h>
 #include <graph_wrapper.h>
 #include <maps.h>
-#include <vector>
+#include <vector.h>
 
 
 namespace hugo {
@@ -31,20 +31,19 @@
   class MinLengthPaths {
 
     typedef typename LengthMap::ValueType Length;
-
+    
     typedef typename Graph::Node Node;
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::Edge Edge;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::EdgeMap<int> EdgeIntMap;
+    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
 
     typedef ConstMap<Edge,int> ConstMap;
 
     typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
 
-
     class ModLengthMap {   
-      typedef typename ResGraphType::NodeMap<Length> NodeMap;
+      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
       const ResGraphType& G;
       const EdgeIntMap& rev;
       const LengthMap &ol;
@@ -52,18 +51,20 @@
     public :
       typedef typename LengthMap::KeyType KeyType;
       typedef typename LengthMap::ValueType ValueType;
-
+	
       ValueType operator[](typename ResGraphType::Edge e) const {     
 	//if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
 	//  std::cout<<"Negative length!!"<<std::endl;
 	//}
 	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
       }     
-
+	
       ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev, 
 		   const LengthMap &o,  const NodeMap &p) : 
 	G(_G), rev(_rev), ol(o), pot(p){}; 
-    };
+    };//ModLengthMap
+
+
     
 
     const Graph& G;
@@ -78,6 +79,11 @@
     
     //Container to store found paths
     std::vector< std::vector<Edge> > paths;
+    //typedef DirPath<Graph> DPath;
+    //DPath paths;
+
+
+    Length total_length;
 
   public :
 
@@ -94,11 +100,12 @@
     int run(Node s, Node t, int k) {
       ConstMap const1map(1);
 
+
       //We need a residual graph, in which some of the edges are reversed
       ResGraphType res_graph(G, const1map, reversed);
 
       //Initialize the copy of the Dijkstra potential to zero
-      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
+      typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
       ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
 
       Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
@@ -133,10 +140,14 @@
       }
       
       //Let's find the paths
-      //We put the paths into vectors (just for now). In the meantime we lose 
-      //the information stored in 'reversed'
+      //We put the paths into stl vectors (as an inner representation). 
+      //In the meantime we lose the information stored in 'reversed'.
       //We suppose the lengths to be positive now.
+
+      //Meanwhile we put the total length of the found paths 
+      //in the member variable total_length
       paths.clear();
+      total_length=0;
       paths.resize(k);
       for (int j=0; j<i; ++j){
 	Node n=s;
@@ -152,6 +163,7 @@
 	  }
 	  n = G.head(e);
 	  paths[j].push_back(e);
+	  total_length += length[e];
 	  reversed[e] = 1-reversed[e];
 	}
 	
@@ -160,6 +172,26 @@
       return i;
     }
 
+    ///This function gives back the total length of the found paths.
+    ///Assumes that \c run() has been run and nothing changed since then.
+    Length totalLength(){
+      return total_length;
+    }
+
+    ///This function gives back the \c j-th path in argument p.
+    ///Assumes that \c run() has been run and nothing changed since then.
+    /// \warning It is assumed that \c p is constructed to be a path of graph \c G.
+    template<typename DirPath>
+    void getPath(DirPath& p, int j){
+      p.clear();
+      typename DirPath::Builder B(p);
+      for(typename std::vector<Edge>::iterator i=paths[j].begin(); 
+	  i!=paths[j].end(); ++i ){
+	B.pushBack(*j);
+      }
+
+      B.commit();
+    }
 
   }; //class MinLengthPaths