COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/minlengthpaths.h @ 840:10002fa8847a

Last change on this file since 840:10002fa8847a was 788:c3187cafcabf, checked in by marci, 20 years ago

mincostflow_test is ok.

File size: 4.6 KB
Line 
1// -*- c++ -*-
2#ifndef HUGO_MINLENGTHPATHS_H
3#define HUGO_MINLENGTHPATHS_H
4
5///\ingroup flowalgs
6///\file
7///\brief An algorithm for finding k paths of minimal total length.
8
9
10//#include <hugo/dijkstra.h>
11//#include <hugo/graph_wrapper.h>
12#include <hugo/maps.h>
13#include <vector>
14#include <hugo/mincostflows.h>
15
16namespace hugo {
17
18/// \addtogroup flowalgs
19/// @{
20
21  ///\brief Implementation of an algorithm for finding k paths between 2 nodes
22  /// of minimal total length
23  ///
24  /// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
25  /// an algorithm for finding k edge-disjoint paths
26  /// from a given source node to a given target node in an
27  /// edge-weighted directed graph having minimal total weigth (length).
28  ///
29  ///\warning It is assumed that the lengths are positive, since the
30  /// general flow-decomposition is not implemented yet.
31  ///
32  ///\author Attila Bernath
33  template <typename Graph, typename LengthMap>
34  class MinLengthPaths{
35
36
37    typedef typename LengthMap::ValueType Length;
38   
39    typedef typename Graph::Node Node;
40    typedef typename Graph::NodeIt NodeIt;
41    typedef typename Graph::Edge Edge;
42    typedef typename Graph::OutEdgeIt OutEdgeIt;
43    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
44
45    typedef ConstMap<Edge,int> ConstMap;
46
47    //Input
48    const Graph& G;
49
50    //Auxiliary variables
51    //This is the capacity map for the mincostflow problem
52    ConstMap const1map;
53    //This MinCostFlows instance will actually solve the problem
54    MinCostFlows<Graph, LengthMap, ConstMap> mincost_flow;
55
56    //Container to store found paths
57    std::vector< std::vector<Edge> > paths;
58
59  public :
60
61
62    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
63      const1map(1), mincost_flow(_G, _length, const1map){}
64
65    ///Runs the algorithm.
66
67    ///Runs the algorithm.
68    ///Returns k if there are at least k edge-disjoint paths from s to t.
69   ///Otherwise it returns the number of found edge-disjoint paths from s to t.
70    int run(Node s, Node t, int k) {
71
72      int i = mincost_flow.run(s,t,k);
73     
74
75
76      //Let's find the paths
77      //We put the paths into stl vectors (as an inner representation).
78      //In the meantime we lose the information stored in 'reversed'.
79      //We suppose the lengths to be positive now.
80
81      //We don't want to change the flow of mincost_flow, so we make a copy
82      //The name here suggests that the flow has only 0/1 values.
83      EdgeIntMap reversed(G);
84
85      for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
86        reversed[e] = mincost_flow.getFlow()[e];
87     
88      paths.clear();
89      //total_length=0;
90      paths.resize(k);
91      for (int j=0; j<i; ++j){
92        Node n=s;
93        OutEdgeIt e;
94
95        while (n!=t){
96
97
98          G.first(e,n);
99         
100          while (!reversed[e]){
101            ++e;
102          }
103          n = G.head(e);
104          paths[j].push_back(e);
105          //total_length += length[e];
106          reversed[e] = 1-reversed[e];
107        }
108       
109      }
110      return i;
111    }
112
113   
114    ///This function gives back the total length of the found paths.
115    ///Assumes that \c run() has been run and nothing changed since then.
116    Length totalLength(){
117      return mincost_flow.totalLength();
118    }
119
120    ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
121    ///be called before using this function.
122    const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
123
124  ///Returns a const reference to the NodeMap \c potential (the dual solution).
125    /// \pre \ref run() must be called before using this function.
126    const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
127
128    ///This function checks, whether the given solution is optimal
129    ///Running after a \c run() should return with true
130    ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
131    ///
132    ///\todo Is this OK here?
133    bool checkComplementarySlackness(){
134      return mincost_flow.checkComplementarySlackness();
135    }
136
137    ///This function gives back the \c j-th path in argument p.
138    ///Assumes that \c run() has been run and nothing changed since then.
139    /// \warning It is assumed that \c p is constructed to be a path of graph \c G. If \c j is not less than the result of previous \c run, then the result here will be an empty path (\c j can be 0 as well).
140    template<typename DirPath>
141    void getPath(DirPath& p, size_t j){
142     
143      p.clear();
144      if (j>paths.size()-1){
145        return;
146      }
147      typename DirPath::Builder B(p);
148      for(typename std::vector<Edge>::iterator i=paths[j].begin();
149          i!=paths[j].end(); ++i ){
150        B.pushBack(*i);
151      }
152
153      B.commit();
154    }
155
156  }; //class MinLengthPaths
157
158  ///@}
159
160} //namespace hugo
161
162#endif //HUGO_MINLENGTHPATHS_H
Note: See TracBrowser for help on using the repository browser.