minlengthpaths is ready, but the paths are not yet determined: needs to canonize a flow
authorathos
Wed, 07 Apr 2004 17:42:05 +0000
changeset 314eabbe162e32e
parent 313 30c5179f296b
child 315 7b97540cd743
minlengthpaths is ready, but the paths are not yet determined: needs to canonize a flow
src/work/athos/makefile
src/work/athos/minlengthpaths.h
src/work/athos/munkaido
src/work/athos/suurballe.cc
     1.1 --- a/src/work/athos/makefile	Wed Apr 07 11:02:00 2004 +0000
     1.2 +++ b/src/work/athos/makefile	Wed Apr 07 17:42:05 2004 +0000
     1.3 @@ -4,7 +4,7 @@
     1.4  CC=$(CXX)
     1.5  #LEDAROOT ?= /ledasrc/LEDA-4.1
     1.6  #BOOSTROOT ?= /home/marci/boost
     1.7 -INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} #-I$(BOOSTROOT)
     1.8 +INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
     1.9  #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    1.10  CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
    1.11  
     2.1 --- a/src/work/athos/minlengthpaths.h	Wed Apr 07 11:02:00 2004 +0000
     2.2 +++ b/src/work/athos/minlengthpaths.h	Wed Apr 07 17:42:05 2004 +0000
     2.3 @@ -64,10 +64,11 @@
     2.4      const Graph& G;
     2.5      const LengthMap& length;
     2.6  
     2.7 -    //auxiliary variable
     2.8 -    //The value is 1 iff the edge is reversed
     2.9 +    //auxiliry variable
    2.10 +    //The value is 1 iff the edge is reversed. 
    2.11 +    //If the algorithm has finished, the edges of the seeked paths are 
    2.12 +    //exactly those that are reversed 
    2.13      EdgeIntMap reversed; 
    2.14 -
    2.15      
    2.16    public :
    2.17  
    2.18 @@ -83,6 +84,7 @@
    2.19      int run(Node s, Node t, int k) {
    2.20        ConstMap const1map(1);
    2.21  
    2.22 +      //We need a residual graph, in which some of the edges are reversed
    2.23        ResGraphType res_graph(G, reversed, const1map);
    2.24  
    2.25        //Initialize the copy of the Dijkstra potential to zero
    2.26 @@ -94,8 +96,7 @@
    2.27        for (int i=0; i<k; ++i){
    2.28  	dijkstra.run(s);
    2.29  	if (!dijkstra.reached(t)){
    2.30 -	  //There is no k path from s to t
    2.31 -	  /// \TODO mit keresett itt ez a ++?
    2.32 +	  //There are no k paths from s to t
    2.33  	  return i;
    2.34  	};
    2.35  	
     3.1 --- a/src/work/athos/munkaido	Wed Apr 07 11:02:00 2004 +0000
     3.2 +++ b/src/work/athos/munkaido	Wed Apr 07 17:42:05 2004 +0000
     3.3 @@ -1,7 +1,12 @@
     3.4 +III. - IV.1.
     3.5  pentek:	Megbeszélés	3 óra
     3.6 -	megbeszeltuk Alpárral, hogy működjön a Suurballe 	1 óra
     3.7 +	megbeszeltuk Alpárral, hogy hogyan működjön a Suurballe 	1 óra
     3.8  Hétfő: 	Suurballe 	4 óra
     3.9  Kedd: 	Suurballe 	5 óra
    3.10  Csüt.: 	Suurballe 	2 óra
    3.11  	Wiki beszámoló	1 óra
    3.12 -Eredmény: Félkész Suurballe
    3.13 \ No newline at end of file
    3.14 +Eredmény: Félkész Suurballe
    3.15 +
    3.16 +IV.2. - IV.9.
    3.17 +pentek:	Megbeszélés	3 óra
    3.18 +Hétfő: 	Suurballe	4 óra
     4.1 --- a/src/work/athos/suurballe.cc	Wed Apr 07 11:02:00 2004 +0000
     4.2 +++ b/src/work/athos/suurballe.cc	Wed Apr 07 17:42:05 2004 +0000
     4.3 @@ -123,5 +123,6 @@
     4.4      surb_test(graph, length);
     4.5    std::cout << surb_test.run(s,t,k) << std::endl;
     4.6  
     4.7 +
     4.8    return 0;
     4.9  }