source:lemon-0.x/src/hugo/minlengthpaths.h@610:4ce8c695e748

Last change on this file since 610:4ce8c695e748 was 610:4ce8c695e748, checked in by athos, 17 years ago

Sorry, the other half of the move comes here.

File size: 4.6 KB
Line
1// -*- c++ -*-
2#ifndef HUGO_MINLENGTHPATHS_H
3#define HUGO_MINLENGTHPATHS_H
4
5///\ingroup galgs
6///\file
7///\brief An algorithm for finding k paths of minimal total length.
8
9#include <iostream>
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
19/// \addtogroup galgs
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        reversed[e] = mincost_flow.getFlow()[e];
88      }
89
90      paths.clear();
91      //total_length=0;
92      paths.resize(k);
93      for (int j=0; j<i; ++j){
94        Node n=s;
95        OutEdgeIt e;
96
97        while (n!=t){
98
99
100          G.first(e,n);
101
102          while (!reversed[e]){
103            G.next(e);
104          }
105          n = G.head(e);
106          paths[j].push_back(e);
107          //total_length += length[e];
108          reversed[e] = 1-reversed[e];
109        }
110
111      }
112      return i;
113    }
114
115
116    ///This function gives back the total length of the found paths.
117    ///Assumes that \c run() has been run and nothing changed since then.
118    Length totalLength(){
119      return mincost_flow.totalLength();
120    }
121
122    ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
123    ///be called before using this function.
124    const EdgeIntMap &getFlow() const { return mincost_flow.flow;}
125
126  ///Returns a const reference to the NodeMap \c potential (the dual solution).
127    /// \pre \ref run() must be called before using this function.
128    const EdgeIntMap &getPotential() const { return mincost_flow.potential;}
129
130    ///This function checks, whether the given solution is optimal
131    ///Running after a \c run() should return with true
132    ///In this "state of the art" this only checks optimality, doesn't bother with feasibility
133    ///
134    ///\todo Is this OK here?
135    bool checkComplementarySlackness(){
136      return mincost_flow.checkComplementarySlackness();
137    }
138
139    ///This function gives back the \c j-th path in argument p.
140    ///Assumes that \c run() has been run and nothing changed since then.
141    /// \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).
142    template<typename DirPath>
143    void getPath(DirPath& p, size_t j){
144
145      p.clear();
146      if (j>paths.size()-1){
147        return;
148      }
149      typename DirPath::Builder B(p);
150      for(typename std::vector<Edge>::iterator i=paths[j].begin();
151          i!=paths[j].end(); ++i ){
152        B.pushBack(*i);
153      }
154
155      B.commit();
156    }
157
158  }; //class MinLengthPaths
159
160  ///@}
161
162} //namespace hugo
163
164#endif //HUGO_MINLENGTHPATHS_H
Note: See TracBrowser for help on using the repository browser.