COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/suurballe.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

File size: 6.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_SUURBALLE_H
20#define LEMON_SUURBALLE_H
21
22///\ingroup shortest_path
23///\file
24///\brief An algorithm for finding k paths of minimal total length.
25
26
27#include <lemon/maps.h>
28#include <vector>
29#include <lemon/path.h>
30#include <lemon/ssp_min_cost_flow.h>
31
32namespace lemon {
33
34/// \addtogroup shortest_path
35/// @{
36
37  ///\brief Implementation of an algorithm for finding k edge-disjoint
38  /// paths between 2 nodes of minimal total length
39  ///
40  /// The class \ref lemon::Suurballe implements
41  /// an algorithm for finding k edge-disjoint paths
42  /// from a given source node to a given target node in an
43  /// edge-weighted directed graph having minimal total weight (length).
44  ///
45  ///\warning Length values should be nonnegative!
46  ///
47  ///\param Graph The directed graph type the algorithm runs on.
48  ///\param LengthMap The type of the length map (values should be nonnegative).
49  ///
50  ///\note It it questionable whether it is correct to call this method after
51  ///%Suurballe for it is just a special case of Edmonds' and Karp's algorithm
52  ///for finding minimum cost flows. In fact, this implementation just
53  ///wraps the SspMinCostFlow algorithms. The paper of both %Suurballe and
54  ///Edmonds-Karp published in 1972, therefore it is possibly right to
55  ///state that they are
56  ///independent results. Most frequently this special case is referred as
57  ///%Suurballe method in the literature, especially in communication
58  ///network context.
59  ///\author Attila Bernath
60  template <typename Graph, typename LengthMap>
61  class Suurballe{
62
63
64    typedef typename LengthMap::Value Length;
65   
66    typedef typename Graph::Node Node;
67    typedef typename Graph::NodeIt NodeIt;
68    typedef typename Graph::Edge Edge;
69    typedef typename Graph::OutEdgeIt OutEdgeIt;
70    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
71
72    typedef ConstMap<Edge,int> ConstMap;
73
74    const Graph& G;
75
76    Node s;
77    Node t;
78
79    //Auxiliary variables
80    //This is the capacity map for the mincostflow problem
81    ConstMap const1map;
82    //This MinCostFlow instance will actually solve the problem
83    SspMinCostFlow<Graph, LengthMap, ConstMap> min_cost_flow;
84
85    //Container to store found paths
86    std::vector<SimplePath<Graph> > paths;
87
88  public :
89
90
91    /// \brief The constructor of the class.
92    ///
93    /// \param _G The directed graph the algorithm runs on.
94    /// \param _length The length (weight or cost) of the edges.
95    /// \param _s Source node.
96    /// \param _t Target node.
97    Suurballe(Graph& _G, LengthMap& _length, Node _s, Node _t) :
98      G(_G), s(_s), t(_t), const1map(1),
99      min_cost_flow(_G, _length, const1map, _s, _t) { }
100
101    /// \brief Runs the algorithm.
102    ///
103    /// Runs the algorithm.
104    /// Returns k if there are at least k edge-disjoint paths from s to t.
105    /// Otherwise it returns the number of edge-disjoint paths found
106    /// from s to t.
107    ///
108    /// \param k How many paths are we looking for?
109    ///
110    int run(int k) {
111      int i = min_cost_flow.run(k);
112
113      //Let's find the paths
114      //We put the paths into stl vectors (as an inner representation).
115      //In the meantime we lose the information stored in 'reversed'.
116      //We suppose the lengths to be positive now.
117
118      //We don't want to change the flow of min_cost_flow, so we make a copy
119      //The name here suggests that the flow has only 0/1 values.
120      EdgeIntMap reversed(G);
121
122      for(typename Graph::EdgeIt e(G); e!=INVALID; ++e)
123        reversed[e] = min_cost_flow.getFlow()[e];
124     
125      paths.clear();
126      paths.resize(k);
127      for (int j=0; j<i; ++j){
128        Node n=s;
129
130        while (n!=t){
131
132          OutEdgeIt e(G, n);
133         
134          while (!reversed[e]){
135            ++e;
136          }
137          n = G.target(e);
138          paths[j].addBack(e);
139          reversed[e] = 1-reversed[e];
140        }
141       
142      }
143      return i;
144    }
145
146   
147    /// \brief Returns the total length of the paths.
148    ///
149    /// This function gives back the total length of the found paths.
150    Length totalLength(){
151      return min_cost_flow.totalLength();
152    }
153
154    /// \brief Returns the found flow.
155    ///
156    /// This function returns a const reference to the EdgeMap \c flow.
157    const EdgeIntMap &getFlow() const { return min_cost_flow.flow;}
158
159    /// \brief Returns the optimal dual solution
160    ///
161    /// This function returns a const reference to the NodeMap \c
162    /// potential (the dual solution).
163    const EdgeIntMap &getPotential() const { return min_cost_flow.potential;}
164
165    /// \brief Checks whether the complementary slackness holds.
166    ///
167    /// This function checks, whether the given solution is optimal.
168    /// Currently this function only checks optimality, doesn't bother
169    /// with feasibility.  It is meant for testing purposes.
170    bool checkComplementarySlackness(){
171      return min_cost_flow.checkComplementarySlackness();
172    }
173
174    typedef SimplePath<Graph> Path;
175
176    /// \brief Read the found paths.
177    ///
178    /// This function gives back the \c j-th path in argument p.
179    /// Assumes that \c run() has been run and nothing has changed
180    /// since then.
181    ///
182    /// \warning It is assumed that \c p is constructed to be a path
183    /// of graph \c G.  If \c j is not less than the result of
184    /// previous \c run, then the result here will be an empty path
185    /// (\c j can be 0 as well).
186    ///
187    /// \param j Which path you want to get from the found paths (in a
188    /// real application you would get the found paths iteratively).
189    Path path(int j) const {
190      return paths[j];
191    }
192
193    /// \brief Gives back the number of the paths.
194    ///
195    /// Gives back the number of the constructed paths.
196    int pathNum() const {
197      return paths.size();
198    }
199
200  }; //class Suurballe
201
202  ///@}
203
204} //namespace lemon
205
206#endif //LEMON_SUURBALLE_H
Note: See TracBrowser for help on using the repository browser.