1.1 --- a/src/work/athos/makefile	Wed Apr 14 12:24:55 2004 +0000
     1.2 +++ b/src/work/athos/makefile	Wed Apr 14 13:30:05 2004 +0000
     1.3 @@ -6,7 +6,7 @@
     1.4  #BOOSTROOT ?= /home/marci/boost
     1.5  INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
     1.6  #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
     1.7 -CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     1.8 +CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     1.9  
    1.10  #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    1.11  BINARIES = suurballe

     2.1 --- a/src/work/athos/minlengthpaths.h	Wed Apr 14 12:24:55 2004 +0000
     2.2 +++ b/src/work/athos/minlengthpaths.h	Wed Apr 14 13:30:05 2004 +0000
     2.3 @@ -9,10 +9,13 @@
     2.4  #include <dijkstra.h>
     2.5  #include <graph_wrapper.h>
     2.6  #include <maps.h>
     2.7 +#include <vector>
     2.8 +
     2.9  
    2.10  namespace hugo {
    2.11  
    2.12  
    2.13 +
    2.14    ///\brief Implementation of an algorithm for finding k paths between 2 nodes 
    2.15    /// of minimal total length 
    2.16    ///
    2.17 @@ -48,10 +51,9 @@
    2.18        typedef typename LengthMap::ValueType ValueType;
    2.19  
    2.20        ValueType operator[](typename ResGraphType::Edge e) const {     
    2.21 -	if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    2.22 -	  ///\TODO This has to be removed
    2.23 -	  std::cout<<"Negative length!!"<<std::endl;
    2.24 -	}
    2.25 +	//if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    2.26 +	//  std::cout<<"Negative length!!"<<std::endl;
    2.27 +	//}
    2.28  	return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    2.29        }     
    2.30  
    2.31 @@ -64,19 +66,22 @@
    2.32      const Graph& G;
    2.33      const LengthMap& length;
    2.34  
    2.35 -    //auxiliry variable
    2.36 +    //auxiliry variables
    2.37 +
    2.38      //The value is 1 iff the edge is reversed. 
    2.39      //If the algorithm has finished, the edges of the seeked paths are 
    2.40      //exactly those that are reversed 
    2.41      EdgeIntMap reversed; 
    2.42      
    2.43 +    //Container to store found paths
    2.44 +    std::vector< std::vector<Edge> > paths;
    2.45 +
    2.46    public :
    2.47  
    2.48  
    2.49      MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G), 
    2.50        length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    2.51  
    2.52 -    ///Runs the algorithm
    2.53      
    2.54      ///Runs the algorithm
    2.55      ///Returns k if there are at least k edge-disjoint paths from s to t.
    2.56 @@ -92,12 +97,13 @@
    2.57        ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
    2.58  
    2.59        Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
    2.60 -      
    2.61 -      for (int i=0; i<k; ++i){
    2.62 +
    2.63 +      int i;
    2.64 +      for (i=0; i<k; ++i){
    2.65  	dijkstra.run(s);
    2.66  	if (!dijkstra.reached(t)){
    2.67  	  //There are no k paths from s to t
    2.68 -	  return i;
    2.69 +	  break;
    2.70  	};
    2.71  	
    2.72  	{
    2.73 @@ -120,13 +126,36 @@
    2.74  
    2.75  	  
    2.76        }
    2.77 -      return k;
    2.78 +      
    2.79 +      //Let's find the paths
    2.80 +      //We put the paths into vectors (just for now). In the meantime we lose 
    2.81 +      //the information stored in 'reversed'
    2.82 +      //We suppose the lengths to be positive now.
    2.83 +      paths.clear();
    2.84 +      paths.resize(k);
    2.85 +      for (int j=0; j<i; ++j){
    2.86 +	Node n=s;
    2.87 +	OutEdgeIt e;
    2.88 +
    2.89 +	while (n!=t){
    2.90 +
    2.91 +
    2.92 +	  G.first(e,n);
    2.93 +	  
    2.94 +	  while (!reversed[e]){
    2.95 +	    G.next(e);
    2.96 +	  }
    2.97 +	  n = G.head(e);
    2.98 +	  paths[j].push_back(e);
    2.99 +	  reversed[e] = 1-reversed[e];
   2.100 +	}
   2.101 +	
   2.102 +      }
   2.103 +
   2.104 +      return i;
   2.105      }
   2.106  
   2.107  
   2.108 -
   2.109 -
   2.110 -
   2.111    }; //class MinLengthPaths
   2.112  
   2.113