COIN-OR::LEMON - Graph Library

Changeset 511:325c9430723e in lemon-0.x


Ignore:
Timestamp:
05/03/04 12:27:20 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@671
Message:

getPath() function implemented.

Location:
src/work/athos
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/makefile

    r331 r511  
    1 CXX2 = g++-2.95
    2 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
    3 CXX=$(CXX3)
    4 CC=$(CXX)
    5 #LEDAROOT ?= /ledasrc/LEDA-4.1
    6 #BOOSTROOT ?= /home/marci/boost
    7 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,athos,akos,klao} #-I$(BOOSTROOT)
    8 #LEDAINCLUDE ?= -I$(LEDAROOT)/incl
    9 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic
     1BINARIES = suurballe minlength_demo
     2INCLUDEDIRS= -I../../include -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
     3include ../makefile
    104
    11 #LEDABINARIES = lg_vs_sg leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    12 BINARIES = suurballe
    13 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    14 
    15 all: $(BINARIES)
    16 
    17 .depend dep depend:
    18         -$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
    19 #       -g++ $(INCLUDEDIRS) $(LEDAINCLUDE) -M $(LEDABINARIES:=.cc) >> .depend #2>/dev/null
    20 
    21 
    22 
    23 makefile: .depend
    24 sinclude .depend
    25 
    26 clean:
    27         $(RM) *.o $(BINARIES) .depend
    28 
    29 .PHONY: all clean dep depend
  • src/work/athos/minlengthpaths.h

    r491 r511  
    1111#include <graph_wrapper.h>
    1212#include <maps.h>
    13 #include <vector>
     13#include <vector.h>
    1414
    1515
     
    3232
    3333    typedef typename LengthMap::ValueType Length;
    34 
     34   
    3535    typedef typename Graph::Node Node;
    3636    typedef typename Graph::NodeIt NodeIt;
    3737    typedef typename Graph::Edge Edge;
    3838    typedef typename Graph::OutEdgeIt OutEdgeIt;
    39     typedef typename Graph::EdgeMap<int> EdgeIntMap;
     39    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    4040
    4141    typedef ConstMap<Edge,int> ConstMap;
     
    4343    typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
    4444
    45 
    4645    class ModLengthMap {   
    47       typedef typename ResGraphType::NodeMap<Length> NodeMap;
     46      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    4847      const ResGraphType& G;
    4948      const EdgeIntMap& rev;
     
    5352      typedef typename LengthMap::KeyType KeyType;
    5453      typedef typename LengthMap::ValueType ValueType;
    55 
     54       
    5655      ValueType operator[](typename ResGraphType::Edge e) const {     
    5756        //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
     
    6059        return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    6160      }     
    62 
     61       
    6362      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
    6463                   const LengthMap &o,  const NodeMap &p) :
    6564        G(_G), rev(_rev), ol(o), pot(p){};
    66     };
     65    };//ModLengthMap
     66
     67
    6768   
    6869
     
    7980    //Container to store found paths
    8081    std::vector< std::vector<Edge> > paths;
     82    //typedef DirPath<Graph> DPath;
     83    //DPath paths;
     84
     85
     86    Length total_length;
    8187
    8288  public :
     
    95101      ConstMap const1map(1);
    96102
     103
    97104      //We need a residual graph, in which some of the edges are reversed
    98105      ResGraphType res_graph(G, const1map, reversed);
    99106
    100107      //Initialize the copy of the Dijkstra potential to zero
    101       typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
     108      typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
    102109      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
    103110
     
    134141     
    135142      //Let's find the paths
    136       //We put the paths into vectors (just for now). In the meantime we lose
    137       //the information stored in 'reversed'
     143      //We put the paths into stl vectors (as an inner representation).
     144      //In the meantime we lose the information stored in 'reversed'.
    138145      //We suppose the lengths to be positive now.
     146
     147      //Meanwhile we put the total length of the found paths
     148      //in the member variable total_length
    139149      paths.clear();
     150      total_length=0;
    140151      paths.resize(k);
    141152      for (int j=0; j<i; ++j){
     
    153164          n = G.head(e);
    154165          paths[j].push_back(e);
     166          total_length += length[e];
    155167          reversed[e] = 1-reversed[e];
    156168        }
     
    161173    }
    162174
     175    ///This function gives back the total length of the found paths.
     176    ///Assumes that \c run() has been run and nothing changed since then.
     177    Length totalLength(){
     178      return total_length;
     179    }
     180
     181    ///This function gives back the \c j-th path in argument p.
     182    ///Assumes that \c run() has been run and nothing changed since then.
     183    /// \warning It is assumed that \c p is constructed to be a path of graph \c G.
     184    template<typename DirPath>
     185    void getPath(DirPath& p, int j){
     186      p.clear();
     187      typename DirPath::Builder B(p);
     188      for(typename std::vector<Edge>::iterator i=paths[j].begin();
     189          i!=paths[j].end(); ++i ){
     190        B.pushBack(*j);
     191      }
     192
     193      B.commit();
     194    }
    163195
    164196  }; //class MinLengthPaths
Note: See TracChangeset for help on using the changeset viewer.