# source:lemon-0.x/src/hugo/minlengthpaths.h@786:d7b3b13b9df6

Last change on this file since 786:d7b3b13b9df6 was 776:f2994a2b10b2, checked in by Hegyi Péter, 16 years ago

minlengthpaths_test.cc is already hugo++ comform and is compilable

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