COIN-OR::LEMON - Graph Library

Changeset 322:a42dacfd0e3e in lemon-0.x


Ignore:
Timestamp:
04/14/04 15:30:05 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@440
Message:

The paths are stored in vectors, assumed there is no circle of length 0

Location:
src/work/athos
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/makefile

    r314 r322  
    77INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
    88#LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    9 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     9CXXFLAGS = -g -W -Wall $(INCLUDEDIRS) -ansi -pedantic
    1010
    1111#LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
  • src/work/athos/minlengthpaths.h

    r314 r322  
    1010#include <graph_wrapper.h>
    1111#include <maps.h>
     12#include <vector>
     13
    1214
    1315namespace hugo {
     16
    1417
    1518
     
    4952
    5053      ValueType operator[](typename ResGraphType::Edge e) const {     
    51         if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    52           ///\TODO This has to be removed
    53           std::cout<<"Negative length!!"<<std::endl;
    54         }
     54        //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
     55        //  std::cout<<"Negative length!!"<<std::endl;
     56        //}
    5557        return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    5658      }     
     
    6567    const LengthMap& length;
    6668
    67     //auxiliry variable
     69    //auxiliry variables
     70
    6871    //The value is 1 iff the edge is reversed.
    6972    //If the algorithm has finished, the edges of the seeked paths are
     
    7174    EdgeIntMap reversed;
    7275   
     76    //Container to store found paths
     77    std::vector< std::vector<Edge> > paths;
     78
    7379  public :
    7480
     
    7783      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    7884
    79     ///Runs the algorithm
    8085   
    8186    ///Runs the algorithm
     
    9398
    9499      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
    95      
    96       for (int i=0; i<k; ++i){
     100
     101      int i;
     102      for (i=0; i<k; ++i){
    97103        dijkstra.run(s);
    98104        if (!dijkstra.reached(t)){
    99105          //There are no k paths from s to t
    100           return i;
     106          break;
    101107        };
    102108       
     
    121127         
    122128      }
    123       return k;
    124     }
     129     
     130      //Let's find the paths
     131      //We put the paths into vectors (just for now). In the meantime we lose
     132      //the information stored in 'reversed'
     133      //We suppose the lengths to be positive now.
     134      paths.clear();
     135      paths.resize(k);
     136      for (int j=0; j<i; ++j){
     137        Node n=s;
     138        OutEdgeIt e;
     139
     140        while (n!=t){
    125141
    126142
     143          G.first(e,n);
     144         
     145          while (!reversed[e]){
     146            G.next(e);
     147          }
     148          n = G.head(e);
     149          paths[j].push_back(e);
     150          reversed[e] = 1-reversed[e];
     151        }
     152       
     153      }
    127154
     155      return i;
     156    }
    128157
    129158
Note: See TracChangeset for help on using the changeset viewer.