Modify the interface of Suurballe (#266, #181)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sat, 25 Apr 2009 02:12:41 +0200
changeset 6157c1324b35d89
parent 614 28f58740b6f8
child 616 1f631044c290
Modify the interface of Suurballe (#266, #181)

- Move the parameters s and t from the constructor to the run()
function. It makes the interface capable for multiple run(s,t,k)
calls (possible improvement in the future) and it is more similar
to Dijkstra.
- Simliarly init() and findFlow(k) were replaced by init(s) and
findFlow(t,k). The separation of parameters s and t is for the
future plans of supporting multiple targets with one source node.
For more information see #181.
- LEMON_ASSERT for the Length type (check if it is integer).
- Doc improvements.
- Rearrange query functions.
- Extend test file.
lemon/suurballe.h
test/suurballe_test.cc
tools/lgf-gen.cc
     1.1 --- a/lemon/suurballe.h	Sat Apr 25 18:25:59 2009 +0200
     1.2 +++ b/lemon/suurballe.h	Sat Apr 25 02:12:41 2009 +0200
     1.3 @@ -25,6 +25,7 @@
     1.4  /// nodes having minimum total length.
     1.5  
     1.6  #include <vector>
     1.7 +#include <limits>
     1.8  #include <lemon/bin_heap.h>
     1.9  #include <lemon/path.h>
    1.10  #include <lemon/list_graph.h>
    1.11 @@ -42,22 +43,26 @@
    1.12    /// finding arc-disjoint paths having minimum total length (cost)
    1.13    /// from a given source node to a given target node in a digraph.
    1.14    ///
    1.15 -  /// In fact, this implementation is the specialization of the
    1.16 -  /// \ref CapacityScaling "successive shortest path" algorithm.
    1.17 +  /// Note that this problem is a special case of the \ref min_cost_flow
    1.18 +  /// "minimum cost flow problem". This implementation is actually an
    1.19 +  /// efficient specialized version of the \ref CapacityScaling
    1.20 +  /// "Successive Shortest Path" algorithm directly for this problem.
    1.21 +  /// Therefore this class provides query functions for flow values and
    1.22 +  /// node potentials (the dual solution) just like the minimum cost flow
    1.23 +  /// algorithms.
    1.24    ///
    1.25    /// \tparam GR The digraph type the algorithm runs on.
    1.26 -  /// The default value is \c ListDigraph.
    1.27 -  /// \tparam LEN The type of the length (cost) map.
    1.28 -  /// The default value is <tt>Digraph::ArcMap<int></tt>.
    1.29 +  /// \tparam LEN The type of the length map.
    1.30 +  /// The default value is <tt>GR::ArcMap<int></tt>.
    1.31    ///
    1.32    /// \warning Length values should be \e non-negative \e integers.
    1.33    ///
    1.34    /// \note For finding node-disjoint paths this algorithm can be used
    1.35 -  /// with \ref SplitNodes.
    1.36 +  /// along with the \ref SplitNodes adaptor.
    1.37  #ifdef DOXYGEN
    1.38    template <typename GR, typename LEN>
    1.39  #else
    1.40 -  template < typename GR = ListDigraph,
    1.41 +  template < typename GR,
    1.42               typename LEN = typename GR::template ArcMap<int> >
    1.43  #endif
    1.44    class Suurballe
    1.45 @@ -75,23 +80,28 @@
    1.46      typedef LEN LengthMap;
    1.47      /// The type of the lengths.
    1.48      typedef typename LengthMap::Value Length;
    1.49 +#ifdef DOXYGEN
    1.50 +    /// The type of the flow map.
    1.51 +    typedef GR::ArcMap<int> FlowMap;
    1.52 +    /// The type of the potential map.
    1.53 +    typedef GR::NodeMap<Length> PotentialMap;
    1.54 +#else
    1.55      /// The type of the flow map.
    1.56      typedef typename Digraph::template ArcMap<int> FlowMap;
    1.57      /// The type of the potential map.
    1.58      typedef typename Digraph::template NodeMap<Length> PotentialMap;
    1.59 +#endif
    1.60 +
    1.61      /// The type of the path structures.
    1.62 -    typedef SimplePath<Digraph> Path;
    1.63 +    typedef SimplePath<GR> Path;
    1.64  
    1.65    private:
    1.66  
    1.67 -    /// \brief Special implementation of the Dijkstra algorithm
    1.68 -    /// for finding shortest paths in the residual network.
    1.69 -    ///
    1.70 -    /// \ref ResidualDijkstra is a special implementation of the
    1.71 -    /// \ref Dijkstra algorithm for finding shortest paths in the
    1.72 -    /// residual network of the digraph with respect to the reduced arc
    1.73 -    /// lengths and modifying the node potentials according to the
    1.74 -    /// distance of the nodes.
    1.75 +    // ResidualDijkstra is a special implementation of the
    1.76 +    // Dijkstra algorithm for finding shortest paths in the
    1.77 +    // residual network with respect to the reduced arc lengths
    1.78 +    // and modifying the node potentials according to the
    1.79 +    // distance of the nodes.
    1.80      class ResidualDijkstra
    1.81      {
    1.82        typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    1.83 @@ -120,14 +130,14 @@
    1.84      public:
    1.85  
    1.86        /// Constructor.
    1.87 -      ResidualDijkstra( const Digraph &digraph,
    1.88 +      ResidualDijkstra( const Digraph &graph,
    1.89                          const FlowMap &flow,
    1.90                          const LengthMap &length,
    1.91                          PotentialMap &potential,
    1.92                          PredMap &pred,
    1.93                          Node s, Node t ) :
    1.94 -        _graph(digraph), _flow(flow), _length(length), _potential(potential),
    1.95 -        _dist(digraph), _pred(pred), _s(s), _t(t) {}
    1.96 +        _graph(graph), _flow(flow), _length(length), _potential(potential),
    1.97 +        _dist(graph), _pred(pred), _s(s), _t(t) {}
    1.98  
    1.99        /// \brief Run the algorithm. It returns \c true if a path is found
   1.100        /// from the source node to the target node.
   1.101 @@ -236,16 +246,16 @@
   1.102      ///
   1.103      /// Constructor.
   1.104      ///
   1.105 -    /// \param digraph The digraph the algorithm runs on.
   1.106 +    /// \param graph The digraph the algorithm runs on.
   1.107      /// \param length The length (cost) values of the arcs.
   1.108 -    /// \param s The source node.
   1.109 -    /// \param t The target node.
   1.110 -    Suurballe( const Digraph &digraph,
   1.111 -               const LengthMap &length,
   1.112 -               Node s, Node t ) :
   1.113 -      _graph(digraph), _length(length), _flow(0), _local_flow(false),
   1.114 -      _potential(0), _local_potential(false), _source(s), _target(t),
   1.115 -      _pred(digraph) {}
   1.116 +    Suurballe( const Digraph &graph,
   1.117 +               const LengthMap &length ) :
   1.118 +      _graph(graph), _length(length), _flow(0), _local_flow(false),
   1.119 +      _potential(0), _local_potential(false), _pred(graph)
   1.120 +    {
   1.121 +      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
   1.122 +        "The length type of Suurballe must be integer");
   1.123 +    }
   1.124  
   1.125      /// Destructor.
   1.126      ~Suurballe() {
   1.127 @@ -257,9 +267,12 @@
   1.128      /// \brief Set the flow map.
   1.129      ///
   1.130      /// This function sets the flow map.
   1.131 +    /// If it is not used before calling \ref run() or \ref init(),
   1.132 +    /// an instance will be allocated automatically. The destructor
   1.133 +    /// deallocates this automatically allocated map, of course.
   1.134      ///
   1.135 -    /// The found flow contains only 0 and 1 values. It is the union of
   1.136 -    /// the found arc-disjoint paths.
   1.137 +    /// The found flow contains only 0 and 1 values, since it is the
   1.138 +    /// union of the found arc-disjoint paths.
   1.139      ///
   1.140      /// \return <tt>(*this)</tt>
   1.141      Suurballe& flowMap(FlowMap &map) {
   1.142 @@ -274,9 +287,12 @@
   1.143      /// \brief Set the potential map.
   1.144      ///
   1.145      /// This function sets the potential map.
   1.146 +    /// If it is not used before calling \ref run() or \ref init(),
   1.147 +    /// an instance will be allocated automatically. The destructor
   1.148 +    /// deallocates this automatically allocated map, of course.
   1.149      ///
   1.150 -    /// The potentials provide the dual solution of the underlying
   1.151 -    /// minimum cost flow problem.
   1.152 +    /// The node potentials provide the dual solution of the underlying
   1.153 +    /// \ref min_cost_flow "minimum cost flow problem".
   1.154      ///
   1.155      /// \return <tt>(*this)</tt>
   1.156      Suurballe& potentialMap(PotentialMap &map) {
   1.157 @@ -301,22 +317,24 @@
   1.158      ///
   1.159      /// This function runs the algorithm.
   1.160      ///
   1.161 +    /// \param s The source node.
   1.162 +    /// \param t The target node.
   1.163      /// \param k The number of paths to be found.
   1.164      ///
   1.165      /// \return \c k if there are at least \c k arc-disjoint paths from
   1.166      /// \c s to \c t in the digraph. Otherwise it returns the number of
   1.167      /// arc-disjoint paths found.
   1.168      ///
   1.169 -    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
   1.170 -    /// shortcut of the following code.
   1.171 +    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
   1.172 +    /// just a shortcut of the following code.
   1.173      /// \code
   1.174 -    ///   s.init();
   1.175 -    ///   s.findFlow(k);
   1.176 +    ///   s.init(s);
   1.177 +    ///   s.findFlow(t, k);
   1.178      ///   s.findPaths();
   1.179      /// \endcode
   1.180 -    int run(int k = 2) {
   1.181 -      init();
   1.182 -      findFlow(k);
   1.183 +    int run(const Node& s, const Node& t, int k = 2) {
   1.184 +      init(s);
   1.185 +      findFlow(t, k);
   1.186        findPaths();
   1.187        return _path_num;
   1.188      }
   1.189 @@ -324,7 +342,11 @@
   1.190      /// \brief Initialize the algorithm.
   1.191      ///
   1.192      /// This function initializes the algorithm.
   1.193 -    void init() {
   1.194 +    ///
   1.195 +    /// \param s The source node.
   1.196 +    void init(const Node& s) {
   1.197 +      _source = s;
   1.198 +
   1.199        // Initialize maps
   1.200        if (!_flow) {
   1.201          _flow = new FlowMap(_graph);
   1.202 @@ -336,25 +358,28 @@
   1.203        }
   1.204        for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   1.205        for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   1.206 -
   1.207 -      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
   1.208 -                                        *_potential, _pred,
   1.209 -                                        _source, _target );
   1.210      }
   1.211  
   1.212 -    /// \brief Execute the successive shortest path algorithm to find
   1.213 -    /// an optimal flow.
   1.214 +    /// \brief Execute the algorithm to find an optimal flow.
   1.215      ///
   1.216      /// This function executes the successive shortest path algorithm to
   1.217 -    /// find a minimum cost flow, which is the union of \c k or less
   1.218 +    /// find a minimum cost flow, which is the union of \c k (or less)
   1.219      /// arc-disjoint paths.
   1.220      ///
   1.221 +    /// \param t The target node.
   1.222 +    /// \param k The number of paths to be found.
   1.223 +    ///
   1.224      /// \return \c k if there are at least \c k arc-disjoint paths from
   1.225 -    /// \c s to \c t in the digraph. Otherwise it returns the number of
   1.226 -    /// arc-disjoint paths found.
   1.227 +    /// the source node to the given node \c t in the digraph.
   1.228 +    /// Otherwise it returns the number of arc-disjoint paths found.
   1.229      ///
   1.230      /// \pre \ref init() must be called before using this function.
   1.231 -    int findFlow(int k = 2) {
   1.232 +    int findFlow(const Node& t, int k = 2) {
   1.233 +      _target = t;
   1.234 +      _dijkstra =
   1.235 +        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
   1.236 +                              _source, _target );
   1.237 +
   1.238        // Find shortest paths
   1.239        _path_num = 0;
   1.240        while (_path_num < k) {
   1.241 @@ -380,13 +405,12 @@
   1.242  
   1.243      /// \brief Compute the paths from the flow.
   1.244      ///
   1.245 -    /// This function computes the paths from the flow.
   1.246 +    /// This function computes the paths from the found minimum cost flow,
   1.247 +    /// which is the union of some arc-disjoint paths.
   1.248      ///
   1.249      /// \pre \ref init() and \ref findFlow() must be called before using
   1.250      /// this function.
   1.251      void findPaths() {
   1.252 -      // Create the residual flow map (the union of the paths not found
   1.253 -      // so far)
   1.254        FlowMap res_flow(_graph);
   1.255        for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
   1.256  
   1.257 @@ -413,10 +437,37 @@
   1.258  
   1.259      /// @{
   1.260  
   1.261 -    /// \brief Return a const reference to the arc map storing the
   1.262 +    /// \brief Return the total length of the found paths.
   1.263 +    ///
   1.264 +    /// This function returns the total length of the found paths, i.e.
   1.265 +    /// the total cost of the found flow.
   1.266 +    /// The complexity of the function is O(e).
   1.267 +    ///
   1.268 +    /// \pre \ref run() or \ref findFlow() must be called before using
   1.269 +    /// this function.
   1.270 +    Length totalLength() const {
   1.271 +      Length c = 0;
   1.272 +      for (ArcIt e(_graph); e != INVALID; ++e)
   1.273 +        c += (*_flow)[e] * _length[e];
   1.274 +      return c;
   1.275 +    }
   1.276 +
   1.277 +    /// \brief Return the flow value on the given arc.
   1.278 +    ///
   1.279 +    /// This function returns the flow value on the given arc.
   1.280 +    /// It is \c 1 if the arc is involved in one of the found arc-disjoint
   1.281 +    /// paths, otherwise it is \c 0.
   1.282 +    ///
   1.283 +    /// \pre \ref run() or \ref findFlow() must be called before using
   1.284 +    /// this function.
   1.285 +    int flow(const Arc& arc) const {
   1.286 +      return (*_flow)[arc];
   1.287 +    }
   1.288 +
   1.289 +    /// \brief Return a const reference to an arc map storing the
   1.290      /// found flow.
   1.291      ///
   1.292 -    /// This function returns a const reference to the arc map storing
   1.293 +    /// This function returns a const reference to an arc map storing
   1.294      /// the flow that is the union of the found arc-disjoint paths.
   1.295      ///
   1.296      /// \pre \ref run() or \ref findFlow() must be called before using
   1.297 @@ -425,34 +476,11 @@
   1.298        return *_flow;
   1.299      }
   1.300  
   1.301 -    /// \brief Return a const reference to the node map storing the
   1.302 -    /// found potentials (the dual solution).
   1.303 -    ///
   1.304 -    /// This function returns a const reference to the node map storing
   1.305 -    /// the found potentials that provide the dual solution of the
   1.306 -    /// underlying minimum cost flow problem.
   1.307 -    ///
   1.308 -    /// \pre \ref run() or \ref findFlow() must be called before using
   1.309 -    /// this function.
   1.310 -    const PotentialMap& potentialMap() const {
   1.311 -      return *_potential;
   1.312 -    }
   1.313 -
   1.314 -    /// \brief Return the flow on the given arc.
   1.315 -    ///
   1.316 -    /// This function returns the flow on the given arc.
   1.317 -    /// It is \c 1 if the arc is involved in one of the found paths,
   1.318 -    /// otherwise it is \c 0.
   1.319 -    ///
   1.320 -    /// \pre \ref run() or \ref findFlow() must be called before using
   1.321 -    /// this function.
   1.322 -    int flow(const Arc& arc) const {
   1.323 -      return (*_flow)[arc];
   1.324 -    }
   1.325 -
   1.326      /// \brief Return the potential of the given node.
   1.327      ///
   1.328      /// This function returns the potential of the given node.
   1.329 +    /// The node potentials provide the dual solution of the
   1.330 +    /// underlying \ref min_cost_flow "minimum cost flow problem".
   1.331      ///
   1.332      /// \pre \ref run() or \ref findFlow() must be called before using
   1.333      /// this function.
   1.334 @@ -460,18 +488,17 @@
   1.335        return (*_potential)[node];
   1.336      }
   1.337  
   1.338 -    /// \brief Return the total length (cost) of the found paths (flow).
   1.339 +    /// \brief Return a const reference to a node map storing the
   1.340 +    /// found potentials (the dual solution).
   1.341      ///
   1.342 -    /// This function returns the total length (cost) of the found paths
   1.343 -    /// (flow). The complexity of the function is O(e).
   1.344 +    /// This function returns a const reference to a node map storing
   1.345 +    /// the found potentials that provide the dual solution of the
   1.346 +    /// underlying \ref min_cost_flow "minimum cost flow problem".
   1.347      ///
   1.348      /// \pre \ref run() or \ref findFlow() must be called before using
   1.349      /// this function.
   1.350 -    Length totalLength() const {
   1.351 -      Length c = 0;
   1.352 -      for (ArcIt e(_graph); e != INVALID; ++e)
   1.353 -        c += (*_flow)[e] * _length[e];
   1.354 -      return c;
   1.355 +    const PotentialMap& potentialMap() const {
   1.356 +      return *_potential;
   1.357      }
   1.358  
   1.359      /// \brief Return the number of the found paths.
   1.360 @@ -488,7 +515,7 @@
   1.361      ///
   1.362      /// This function returns a const reference to the specified path.
   1.363      ///
   1.364 -    /// \param i The function returns the \c i-th path.
   1.365 +    /// \param i The function returns the <tt>i</tt>-th path.
   1.366      /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   1.367      ///
   1.368      /// \pre \ref run() or \ref findPaths() must be called before using
     2.1 --- a/test/suurballe_test.cc	Sat Apr 25 18:25:59 2009 +0200
     2.2 +++ b/test/suurballe_test.cc	Sat Apr 25 02:12:41 2009 +0200
     2.3 @@ -22,6 +22,7 @@
     2.4  #include <lemon/lgf_reader.h>
     2.5  #include <lemon/path.h>
     2.6  #include <lemon/suurballe.h>
     2.7 +#include <lemon/concepts/digraph.h>
     2.8  
     2.9  #include "test_tools.h"
    2.10  
    2.11 @@ -29,47 +30,97 @@
    2.12  
    2.13  char test_lgf[] =
    2.14    "@nodes\n"
    2.15 -  "label supply1 supply2 supply3\n"
    2.16 -  "1     0        20      27\n"
    2.17 -  "2     0       -4        0\n"
    2.18 -  "3     0        0        0\n"
    2.19 -  "4     0        0        0\n"
    2.20 -  "5     0        9        0\n"
    2.21 -  "6     0       -6        0\n"
    2.22 -  "7     0        0        0\n"
    2.23 -  "8     0        0        0\n"
    2.24 -  "9     0        3        0\n"
    2.25 -  "10    0       -2        0\n"
    2.26 -  "11    0        0        0\n"
    2.27 -  "12    0       -20     -27\n"
    2.28 +  "label\n"
    2.29 +  "1\n"
    2.30 +  "2\n"
    2.31 +  "3\n"
    2.32 +  "4\n"
    2.33 +  "5\n"
    2.34 +  "6\n"
    2.35 +  "7\n"
    2.36 +  "8\n"
    2.37 +  "9\n"
    2.38 +  "10\n"
    2.39 +  "11\n"
    2.40 +  "12\n"
    2.41    "@arcs\n"
    2.42 -  "      cost capacity lower1 lower2\n"
    2.43 -  " 1  2  70  11       0      8\n"
    2.44 -  " 1  3 150   3       0      1\n"
    2.45 -  " 1  4  80  15       0      2\n"
    2.46 -  " 2  8  80  12       0      0\n"
    2.47 -  " 3  5 140   5       0      3\n"
    2.48 -  " 4  6  60  10       0      1\n"
    2.49 -  " 4  7  80   2       0      0\n"
    2.50 -  " 4  8 110   3       0      0\n"
    2.51 -  " 5  7  60  14       0      0\n"
    2.52 -  " 5 11 120  12       0      0\n"
    2.53 -  " 6  3   0   3       0      0\n"
    2.54 -  " 6  9 140   4       0      0\n"
    2.55 -  " 6 10  90   8       0      0\n"
    2.56 -  " 7  1  30   5       0      0\n"
    2.57 -  " 8 12  60  16       0      4\n"
    2.58 -  " 9 12  50   6       0      0\n"
    2.59 -  "10 12  70  13       0      5\n"
    2.60 -  "10  2 100   7       0      0\n"
    2.61 -  "10  7  60  10       0      0\n"
    2.62 -  "11 10  20  14       0      6\n"
    2.63 -  "12 11  30  10       0      0\n"
    2.64 +  "      length\n"
    2.65 +  " 1  2  70\n"
    2.66 +  " 1  3 150\n"
    2.67 +  " 1  4  80\n"
    2.68 +  " 2  8  80\n"
    2.69 +  " 3  5 140\n"
    2.70 +  " 4  6  60\n"
    2.71 +  " 4  7  80\n"
    2.72 +  " 4  8 110\n"
    2.73 +  " 5  7  60\n"
    2.74 +  " 5 11 120\n"
    2.75 +  " 6  3   0\n"
    2.76 +  " 6  9 140\n"
    2.77 +  " 6 10  90\n"
    2.78 +  " 7  1  30\n"
    2.79 +  " 8 12  60\n"
    2.80 +  " 9 12  50\n"
    2.81 +  "10 12  70\n"
    2.82 +  "10  2 100\n"
    2.83 +  "10  7  60\n"
    2.84 +  "11 10  20\n"
    2.85 +  "12 11  30\n"
    2.86    "@attributes\n"
    2.87    "source  1\n"
    2.88    "target 12\n"
    2.89    "@end\n";
    2.90  
    2.91 +// Check the interface of Suurballe
    2.92 +void checkSuurballeCompile()
    2.93 +{
    2.94 +  typedef int VType;
    2.95 +  typedef concepts::Digraph Digraph;
    2.96 +
    2.97 +  typedef Digraph::Node Node;
    2.98 +  typedef Digraph::Arc Arc;
    2.99 +  typedef concepts::ReadMap<Arc, VType> LengthMap;
   2.100 +  
   2.101 +  typedef Suurballe<Digraph, LengthMap> SuurballeType;
   2.102 +
   2.103 +  Digraph g;
   2.104 +  Node n;
   2.105 +  Arc e;
   2.106 +  LengthMap len;
   2.107 +  SuurballeType::FlowMap flow(g);
   2.108 +  SuurballeType::PotentialMap pi(g);
   2.109 +
   2.110 +  SuurballeType suurb_test(g, len);
   2.111 +  const SuurballeType& const_suurb_test = suurb_test;
   2.112 +
   2.113 +  suurb_test
   2.114 +    .flowMap(flow)
   2.115 +    .potentialMap(pi);
   2.116 +
   2.117 +  int k;
   2.118 +  k = suurb_test.run(n, n);
   2.119 +  k = suurb_test.run(n, n, k);
   2.120 +  suurb_test.init(n);
   2.121 +  k = suurb_test.findFlow(n);
   2.122 +  k = suurb_test.findFlow(n, k);
   2.123 +  suurb_test.findPaths();
   2.124 +  
   2.125 +  int f;
   2.126 +  VType c;
   2.127 +  c = const_suurb_test.totalLength();
   2.128 +  f = const_suurb_test.flow(e);
   2.129 +  const SuurballeType::FlowMap& fm =
   2.130 +    const_suurb_test.flowMap();
   2.131 +  c = const_suurb_test.potential(n);
   2.132 +  const SuurballeType::PotentialMap& pm =
   2.133 +    const_suurb_test.potentialMap();
   2.134 +  k = const_suurb_test.pathNum();
   2.135 +  Path<Digraph> p = const_suurb_test.path(k);
   2.136 +  
   2.137 +  ignore_unused_variable_warning(fm);
   2.138 +  ignore_unused_variable_warning(pm);
   2.139 +}
   2.140 +
   2.141  // Check the feasibility of the flow
   2.142  template <typename Digraph, typename FlowMap>
   2.143  bool checkFlow( const Digraph& gr, const FlowMap& flow,
   2.144 @@ -118,7 +169,6 @@
   2.145  bool checkPath( const Digraph& gr, const Path& path,
   2.146                  typename Digraph::Node s, typename Digraph::Node t)
   2.147  {
   2.148 -  // Check the "Complementary Slackness" optimality condition
   2.149    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   2.150    Node n = s;
   2.151    for (int i = 0; i < path.length(); ++i) {
   2.152 @@ -136,58 +186,55 @@
   2.153    // Read the test digraph
   2.154    ListDigraph digraph;
   2.155    ListDigraph::ArcMap<int> length(digraph);
   2.156 -  Node source, target;
   2.157 +  Node s, t;
   2.158  
   2.159    std::istringstream input(test_lgf);
   2.160    DigraphReader<ListDigraph>(digraph, input).
   2.161 -    arcMap("cost", length).
   2.162 -    node("source", source).
   2.163 -    node("target", target).
   2.164 +    arcMap("length", length).
   2.165 +    node("source", s).
   2.166 +    node("target", t).
   2.167      run();
   2.168  
   2.169    // Find 2 paths
   2.170    {
   2.171 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   2.172 -    check(suurballe.run(2) == 2, "Wrong number of paths");
   2.173 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
   2.174 +    Suurballe<ListDigraph> suurballe(digraph, length);
   2.175 +    check(suurballe.run(s, t) == 2, "Wrong number of paths");
   2.176 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
   2.177            "The flow is not feasible");
   2.178      check(suurballe.totalLength() == 510, "The flow is not optimal");
   2.179      check(checkOptimality(digraph, length, suurballe.flowMap(),
   2.180                            suurballe.potentialMap()),
   2.181            "Wrong potentials");
   2.182      for (int i = 0; i < suurballe.pathNum(); ++i)
   2.183 -      check(checkPath(digraph, suurballe.path(i), source, target),
   2.184 -            "Wrong path");
   2.185 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   2.186    }
   2.187  
   2.188    // Find 3 paths
   2.189    {
   2.190 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   2.191 -    check(suurballe.run(3) == 3, "Wrong number of paths");
   2.192 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   2.193 +    Suurballe<ListDigraph> suurballe(digraph, length);
   2.194 +    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
   2.195 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   2.196            "The flow is not feasible");
   2.197      check(suurballe.totalLength() == 1040, "The flow is not optimal");
   2.198      check(checkOptimality(digraph, length, suurballe.flowMap(),
   2.199                            suurballe.potentialMap()),
   2.200            "Wrong potentials");
   2.201      for (int i = 0; i < suurballe.pathNum(); ++i)
   2.202 -      check(checkPath(digraph, suurballe.path(i), source, target),
   2.203 -            "Wrong path");
   2.204 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   2.205    }
   2.206  
   2.207    // Find 5 paths (only 3 can be found)
   2.208    {
   2.209 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
   2.210 -    check(suurballe.run(5) == 3, "Wrong number of paths");
   2.211 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
   2.212 +    Suurballe<ListDigraph> suurballe(digraph, length);
   2.213 +    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
   2.214 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
   2.215            "The flow is not feasible");
   2.216      check(suurballe.totalLength() == 1040, "The flow is not optimal");
   2.217      check(checkOptimality(digraph, length, suurballe.flowMap(),
   2.218                            suurballe.potentialMap()),
   2.219            "Wrong potentials");
   2.220      for (int i = 0; i < suurballe.pathNum(); ++i)
   2.221 -      check(checkPath(digraph, suurballe.path(i), source, target),
   2.222 -            "Wrong path");
   2.223 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
   2.224    }
   2.225  
   2.226    return 0;
     3.1 --- a/tools/lgf-gen.cc	Sat Apr 25 18:25:59 2009 +0200
     3.2 +++ b/tools/lgf-gen.cc	Sat Apr 25 02:12:41 2009 +0200
     3.3 @@ -480,8 +480,8 @@
     3.4        Node b=g.v(*ei);
     3.5        g.erase(*ei);
     3.6        ConstMap<Arc,int> cegy(1);
     3.7 -      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
     3.8 -      int k=sur.run(2);
     3.9 +      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
    3.10 +      int k=sur.run(a,b,2);
    3.11        if(k<2 || sur.totalLength()>d)
    3.12          g.addEdge(a,b);
    3.13        else cnt++;
    3.14 @@ -511,9 +511,8 @@
    3.15        Edge ne;
    3.16        if(e==INVALID) {
    3.17          ConstMap<Arc,int> cegy(1);
    3.18 -        Suurballe<ListGraph,ConstMap<Arc,int> >
    3.19 -          sur(g,cegy,pi->a,pi->b);
    3.20 -        int k=sur.run(2);
    3.21 +        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
    3.22 +        int k=sur.run(pi->a,pi->b,2);
    3.23          if(k<2 || sur.totalLength()>d)
    3.24            {
    3.25              ne=g.addEdge(pi->a,pi->b);