lemon/suurballe.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 440 88ed40ad0d4f
child 559 c5fd2d996909
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@440
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@345
     2
 *
alpar@440
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@345
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@345
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@345
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@345
     8
 *
alpar@345
     9
 * Permission to use, modify and distribute this software is granted
alpar@345
    10
 * provided that this copyright notice appears in all copies. For
alpar@345
    11
 * precise terms see the accompanying LICENSE file.
alpar@345
    12
 *
alpar@345
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@345
    14
 * express or implied, and with no claim as to its suitability for any
alpar@345
    15
 * purpose.
alpar@345
    16
 *
alpar@345
    17
 */
alpar@345
    18
alpar@345
    19
#ifndef LEMON_SUURBALLE_H
alpar@345
    20
#define LEMON_SUURBALLE_H
alpar@345
    21
alpar@345
    22
///\ingroup shortest_path
alpar@345
    23
///\file
alpar@345
    24
///\brief An algorithm for finding arc-disjoint paths between two
alpar@345
    25
/// nodes having minimum total length.
alpar@345
    26
alpar@345
    27
#include <vector>
alpar@345
    28
#include <lemon/bin_heap.h>
alpar@345
    29
#include <lemon/path.h>
deba@519
    30
#include <lemon/list_graph.h>
deba@519
    31
#include <lemon/maps.h>
alpar@345
    32
alpar@345
    33
namespace lemon {
alpar@345
    34
alpar@345
    35
  /// \addtogroup shortest_path
alpar@345
    36
  /// @{
alpar@345
    37
kpeter@346
    38
  /// \brief Algorithm for finding arc-disjoint paths between two nodes
kpeter@346
    39
  /// having minimum total length.
alpar@345
    40
  ///
alpar@345
    41
  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
alpar@345
    42
  /// finding arc-disjoint paths having minimum total length (cost)
kpeter@346
    43
  /// from a given source node to a given target node in a digraph.
alpar@345
    44
  ///
alpar@345
    45
  /// In fact, this implementation is the specialization of the
alpar@345
    46
  /// \ref CapacityScaling "successive shortest path" algorithm.
alpar@345
    47
  ///
kpeter@346
    48
  /// \tparam Digraph The digraph type the algorithm runs on.
kpeter@346
    49
  /// The default value is \c ListDigraph.
alpar@345
    50
  /// \tparam LengthMap The type of the length (cost) map.
kpeter@346
    51
  /// The default value is <tt>Digraph::ArcMap<int></tt>.
alpar@345
    52
  ///
alpar@345
    53
  /// \warning Length values should be \e non-negative \e integers.
alpar@345
    54
  ///
alpar@345
    55
  /// \note For finding node-disjoint paths this algorithm can be used
deba@425
    56
  /// with \ref SplitNodes.
kpeter@346
    57
#ifdef DOXYGEN
kpeter@346
    58
  template <typename Digraph, typename LengthMap>
kpeter@346
    59
#else
kpeter@346
    60
  template < typename Digraph = ListDigraph,
alpar@345
    61
             typename LengthMap = typename Digraph::template ArcMap<int> >
kpeter@346
    62
#endif
alpar@345
    63
  class Suurballe
alpar@345
    64
  {
alpar@345
    65
    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
alpar@345
    66
alpar@345
    67
    typedef typename LengthMap::Value Length;
alpar@345
    68
    typedef ConstMap<Arc, int> ConstArcMap;
alpar@345
    69
    typedef typename Digraph::template NodeMap<Arc> PredMap;
alpar@345
    70
alpar@345
    71
  public:
alpar@345
    72
alpar@345
    73
    /// The type of the flow map.
alpar@345
    74
    typedef typename Digraph::template ArcMap<int> FlowMap;
alpar@345
    75
    /// The type of the potential map.
alpar@345
    76
    typedef typename Digraph::template NodeMap<Length> PotentialMap;
alpar@345
    77
    /// The type of the path structures.
alpar@345
    78
    typedef SimplePath<Digraph> Path;
alpar@345
    79
alpar@345
    80
  private:
alpar@440
    81
kpeter@346
    82
    /// \brief Special implementation of the Dijkstra algorithm
alpar@345
    83
    /// for finding shortest paths in the residual network.
alpar@345
    84
    ///
alpar@345
    85
    /// \ref ResidualDijkstra is a special implementation of the
alpar@345
    86
    /// \ref Dijkstra algorithm for finding shortest paths in the
alpar@345
    87
    /// residual network of the digraph with respect to the reduced arc
alpar@345
    88
    /// lengths and modifying the node potentials according to the
alpar@345
    89
    /// distance of the nodes.
alpar@345
    90
    class ResidualDijkstra
alpar@345
    91
    {
alpar@345
    92
      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
alpar@345
    93
      typedef BinHeap<Length, HeapCrossRef> Heap;
alpar@345
    94
alpar@345
    95
    private:
alpar@345
    96
kpeter@346
    97
      // The digraph the algorithm runs on
alpar@345
    98
      const Digraph &_graph;
alpar@345
    99
alpar@345
   100
      // The main maps
alpar@345
   101
      const FlowMap &_flow;
alpar@345
   102
      const LengthMap &_length;
alpar@345
   103
      PotentialMap &_potential;
alpar@345
   104
alpar@345
   105
      // The distance map
alpar@345
   106
      PotentialMap _dist;
alpar@345
   107
      // The pred arc map
alpar@345
   108
      PredMap &_pred;
alpar@345
   109
      // The processed (i.e. permanently labeled) nodes
alpar@345
   110
      std::vector<Node> _proc_nodes;
alpar@440
   111
alpar@345
   112
      Node _s;
alpar@345
   113
      Node _t;
alpar@345
   114
alpar@345
   115
    public:
alpar@345
   116
alpar@345
   117
      /// Constructor.
alpar@345
   118
      ResidualDijkstra( const Digraph &digraph,
alpar@345
   119
                        const FlowMap &flow,
alpar@345
   120
                        const LengthMap &length,
alpar@345
   121
                        PotentialMap &potential,
alpar@345
   122
                        PredMap &pred,
alpar@345
   123
                        Node s, Node t ) :
alpar@345
   124
        _graph(digraph), _flow(flow), _length(length), _potential(potential),
alpar@345
   125
        _dist(digraph), _pred(pred), _s(s), _t(t) {}
alpar@345
   126
kpeter@346
   127
      /// \brief Run the algorithm. It returns \c true if a path is found
alpar@345
   128
      /// from the source node to the target node.
alpar@345
   129
      bool run() {
alpar@345
   130
        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
alpar@345
   131
        Heap heap(heap_cross_ref);
alpar@345
   132
        heap.push(_s, 0);
alpar@345
   133
        _pred[_s] = INVALID;
alpar@345
   134
        _proc_nodes.clear();
alpar@345
   135
kpeter@346
   136
        // Process nodes
alpar@345
   137
        while (!heap.empty() && heap.top() != _t) {
alpar@345
   138
          Node u = heap.top(), v;
alpar@345
   139
          Length d = heap.prio() + _potential[u], nd;
alpar@345
   140
          _dist[u] = heap.prio();
alpar@345
   141
          heap.pop();
alpar@345
   142
          _proc_nodes.push_back(u);
alpar@345
   143
kpeter@346
   144
          // Traverse outgoing arcs
alpar@345
   145
          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
alpar@345
   146
            if (_flow[e] == 0) {
alpar@345
   147
              v = _graph.target(e);
alpar@345
   148
              switch(heap.state(v)) {
alpar@345
   149
              case Heap::PRE_HEAP:
alpar@345
   150
                heap.push(v, d + _length[e] - _potential[v]);
alpar@345
   151
                _pred[v] = e;
alpar@345
   152
                break;
alpar@345
   153
              case Heap::IN_HEAP:
alpar@345
   154
                nd = d + _length[e] - _potential[v];
alpar@345
   155
                if (nd < heap[v]) {
alpar@345
   156
                  heap.decrease(v, nd);
alpar@345
   157
                  _pred[v] = e;
alpar@345
   158
                }
alpar@345
   159
                break;
alpar@345
   160
              case Heap::POST_HEAP:
alpar@345
   161
                break;
alpar@345
   162
              }
alpar@345
   163
            }
alpar@345
   164
          }
alpar@345
   165
kpeter@346
   166
          // Traverse incoming arcs
alpar@345
   167
          for (InArcIt e(_graph, u); e != INVALID; ++e) {
alpar@345
   168
            if (_flow[e] == 1) {
alpar@345
   169
              v = _graph.source(e);
alpar@345
   170
              switch(heap.state(v)) {
alpar@345
   171
              case Heap::PRE_HEAP:
alpar@345
   172
                heap.push(v, d - _length[e] - _potential[v]);
alpar@345
   173
                _pred[v] = e;
alpar@345
   174
                break;
alpar@345
   175
              case Heap::IN_HEAP:
alpar@345
   176
                nd = d - _length[e] - _potential[v];
alpar@345
   177
                if (nd < heap[v]) {
alpar@345
   178
                  heap.decrease(v, nd);
alpar@345
   179
                  _pred[v] = e;
alpar@345
   180
                }
alpar@345
   181
                break;
alpar@345
   182
              case Heap::POST_HEAP:
alpar@345
   183
                break;
alpar@345
   184
              }
alpar@345
   185
            }
alpar@345
   186
          }
alpar@345
   187
        }
alpar@345
   188
        if (heap.empty()) return false;
alpar@345
   189
kpeter@346
   190
        // Update potentials of processed nodes
alpar@345
   191
        Length t_dist = heap.prio();
alpar@345
   192
        for (int i = 0; i < int(_proc_nodes.size()); ++i)
alpar@345
   193
          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
alpar@345
   194
        return true;
alpar@345
   195
      }
alpar@345
   196
alpar@345
   197
    }; //class ResidualDijkstra
alpar@345
   198
alpar@345
   199
  private:
alpar@345
   200
kpeter@346
   201
    // The digraph the algorithm runs on
alpar@345
   202
    const Digraph &_graph;
alpar@345
   203
    // The length map
alpar@345
   204
    const LengthMap &_length;
alpar@440
   205
alpar@345
   206
    // Arc map of the current flow
alpar@345
   207
    FlowMap *_flow;
alpar@345
   208
    bool _local_flow;
alpar@345
   209
    // Node map of the current potentials
alpar@345
   210
    PotentialMap *_potential;
alpar@345
   211
    bool _local_potential;
alpar@345
   212
alpar@345
   213
    // The source node
alpar@345
   214
    Node _source;
alpar@345
   215
    // The target node
alpar@345
   216
    Node _target;
alpar@345
   217
alpar@345
   218
    // Container to store the found paths
alpar@345
   219
    std::vector< SimplePath<Digraph> > paths;
alpar@345
   220
    int _path_num;
alpar@345
   221
alpar@345
   222
    // The pred arc map
alpar@345
   223
    PredMap _pred;
alpar@345
   224
    // Implementation of the Dijkstra algorithm for finding augmenting
alpar@345
   225
    // shortest paths in the residual network
alpar@345
   226
    ResidualDijkstra *_dijkstra;
alpar@345
   227
alpar@345
   228
  public:
alpar@345
   229
alpar@345
   230
    /// \brief Constructor.
alpar@345
   231
    ///
alpar@345
   232
    /// Constructor.
alpar@345
   233
    ///
kpeter@346
   234
    /// \param digraph The digraph the algorithm runs on.
alpar@345
   235
    /// \param length The length (cost) values of the arcs.
alpar@345
   236
    /// \param s The source node.
alpar@345
   237
    /// \param t The target node.
alpar@345
   238
    Suurballe( const Digraph &digraph,
alpar@345
   239
               const LengthMap &length,
alpar@345
   240
               Node s, Node t ) :
alpar@345
   241
      _graph(digraph), _length(length), _flow(0), _local_flow(false),
alpar@345
   242
      _potential(0), _local_potential(false), _source(s), _target(t),
alpar@345
   243
      _pred(digraph) {}
alpar@345
   244
alpar@345
   245
    /// Destructor.
alpar@345
   246
    ~Suurballe() {
alpar@345
   247
      if (_local_flow) delete _flow;
alpar@345
   248
      if (_local_potential) delete _potential;
alpar@345
   249
      delete _dijkstra;
alpar@345
   250
    }
alpar@345
   251
kpeter@346
   252
    /// \brief Set the flow map.
alpar@345
   253
    ///
kpeter@346
   254
    /// This function sets the flow map.
alpar@345
   255
    ///
alpar@345
   256
    /// The found flow contains only 0 and 1 values. It is the union of
alpar@345
   257
    /// the found arc-disjoint paths.
alpar@345
   258
    ///
alpar@345
   259
    /// \return \c (*this)
alpar@345
   260
    Suurballe& flowMap(FlowMap &map) {
alpar@345
   261
      if (_local_flow) {
alpar@345
   262
        delete _flow;
alpar@345
   263
        _local_flow = false;
alpar@345
   264
      }
alpar@345
   265
      _flow = &map;
alpar@345
   266
      return *this;
alpar@345
   267
    }
alpar@345
   268
kpeter@346
   269
    /// \brief Set the potential map.
alpar@345
   270
    ///
kpeter@346
   271
    /// This function sets the potential map.
alpar@345
   272
    ///
alpar@440
   273
    /// The potentials provide the dual solution of the underlying
alpar@345
   274
    /// minimum cost flow problem.
alpar@345
   275
    ///
alpar@345
   276
    /// \return \c (*this)
alpar@345
   277
    Suurballe& potentialMap(PotentialMap &map) {
alpar@345
   278
      if (_local_potential) {
alpar@345
   279
        delete _potential;
alpar@345
   280
        _local_potential = false;
alpar@345
   281
      }
alpar@345
   282
      _potential = &map;
alpar@345
   283
      return *this;
alpar@345
   284
    }
alpar@345
   285
alpar@345
   286
    /// \name Execution control
alpar@345
   287
    /// The simplest way to execute the algorithm is to call the run()
alpar@345
   288
    /// function.
alpar@345
   289
    /// \n
alpar@345
   290
    /// If you only need the flow that is the union of the found
alpar@345
   291
    /// arc-disjoint paths, you may call init() and findFlow().
alpar@345
   292
alpar@345
   293
    /// @{
alpar@345
   294
kpeter@346
   295
    /// \brief Run the algorithm.
alpar@345
   296
    ///
kpeter@346
   297
    /// This function runs the algorithm.
alpar@345
   298
    ///
alpar@345
   299
    /// \param k The number of paths to be found.
alpar@345
   300
    ///
kpeter@346
   301
    /// \return \c k if there are at least \c k arc-disjoint paths from
kpeter@346
   302
    /// \c s to \c t in the digraph. Otherwise it returns the number of
alpar@345
   303
    /// arc-disjoint paths found.
alpar@345
   304
    ///
alpar@345
   305
    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
alpar@345
   306
    /// shortcut of the following code.
alpar@345
   307
    /// \code
alpar@345
   308
    ///   s.init();
alpar@345
   309
    ///   s.findFlow(k);
alpar@345
   310
    ///   s.findPaths();
alpar@345
   311
    /// \endcode
alpar@345
   312
    int run(int k = 2) {
alpar@345
   313
      init();
alpar@345
   314
      findFlow(k);
alpar@345
   315
      findPaths();
alpar@345
   316
      return _path_num;
alpar@345
   317
    }
alpar@345
   318
kpeter@346
   319
    /// \brief Initialize the algorithm.
alpar@345
   320
    ///
kpeter@346
   321
    /// This function initializes the algorithm.
alpar@345
   322
    void init() {
kpeter@346
   323
      // Initialize maps
alpar@345
   324
      if (!_flow) {
alpar@345
   325
        _flow = new FlowMap(_graph);
alpar@345
   326
        _local_flow = true;
alpar@345
   327
      }
alpar@345
   328
      if (!_potential) {
alpar@345
   329
        _potential = new PotentialMap(_graph);
alpar@345
   330
        _local_potential = true;
alpar@345
   331
      }
alpar@345
   332
      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
alpar@345
   333
      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
alpar@345
   334
alpar@440
   335
      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
alpar@345
   336
                                        *_potential, _pred,
alpar@345
   337
                                        _source, _target );
alpar@345
   338
    }
alpar@345
   339
kpeter@346
   340
    /// \brief Execute the successive shortest path algorithm to find
alpar@345
   341
    /// an optimal flow.
alpar@345
   342
    ///
kpeter@346
   343
    /// This function executes the successive shortest path algorithm to
kpeter@346
   344
    /// find a minimum cost flow, which is the union of \c k or less
alpar@345
   345
    /// arc-disjoint paths.
alpar@345
   346
    ///
kpeter@346
   347
    /// \return \c k if there are at least \c k arc-disjoint paths from
kpeter@346
   348
    /// \c s to \c t in the digraph. Otherwise it returns the number of
alpar@345
   349
    /// arc-disjoint paths found.
alpar@345
   350
    ///
alpar@345
   351
    /// \pre \ref init() must be called before using this function.
alpar@345
   352
    int findFlow(int k = 2) {
kpeter@346
   353
      // Find shortest paths
alpar@345
   354
      _path_num = 0;
alpar@345
   355
      while (_path_num < k) {
kpeter@346
   356
        // Run Dijkstra
alpar@345
   357
        if (!_dijkstra->run()) break;
alpar@345
   358
        ++_path_num;
alpar@345
   359
kpeter@346
   360
        // Set the flow along the found shortest path
alpar@345
   361
        Node u = _target;
alpar@345
   362
        Arc e;
alpar@345
   363
        while ((e = _pred[u]) != INVALID) {
alpar@345
   364
          if (u == _graph.target(e)) {
alpar@345
   365
            (*_flow)[e] = 1;
alpar@345
   366
            u = _graph.source(e);
alpar@345
   367
          } else {
alpar@345
   368
            (*_flow)[e] = 0;
alpar@345
   369
            u = _graph.target(e);
alpar@345
   370
          }
alpar@345
   371
        }
alpar@345
   372
      }
alpar@345
   373
      return _path_num;
alpar@345
   374
    }
alpar@440
   375
kpeter@346
   376
    /// \brief Compute the paths from the flow.
alpar@345
   377
    ///
kpeter@346
   378
    /// This function computes the paths from the flow.
alpar@345
   379
    ///
alpar@345
   380
    /// \pre \ref init() and \ref findFlow() must be called before using
alpar@345
   381
    /// this function.
alpar@345
   382
    void findPaths() {
kpeter@346
   383
      // Create the residual flow map (the union of the paths not found
kpeter@346
   384
      // so far)
alpar@345
   385
      FlowMap res_flow(_graph);
kpeter@346
   386
      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
alpar@345
   387
alpar@345
   388
      paths.clear();
alpar@345
   389
      paths.resize(_path_num);
alpar@345
   390
      for (int i = 0; i < _path_num; ++i) {
alpar@345
   391
        Node n = _source;
alpar@345
   392
        while (n != _target) {
alpar@345
   393
          OutArcIt e(_graph, n);
alpar@345
   394
          for ( ; res_flow[e] == 0; ++e) ;
alpar@345
   395
          n = _graph.target(e);
alpar@345
   396
          paths[i].addBack(e);
alpar@345
   397
          res_flow[e] = 0;
alpar@345
   398
        }
alpar@345
   399
      }
alpar@345
   400
    }
alpar@345
   401
alpar@345
   402
    /// @}
alpar@345
   403
alpar@345
   404
    /// \name Query Functions
kpeter@346
   405
    /// The results of the algorithm can be obtained using these
alpar@345
   406
    /// functions.
alpar@345
   407
    /// \n The algorithm should be executed before using them.
alpar@345
   408
alpar@345
   409
    /// @{
alpar@345
   410
kpeter@346
   411
    /// \brief Return a const reference to the arc map storing the
alpar@345
   412
    /// found flow.
alpar@345
   413
    ///
kpeter@346
   414
    /// This function returns a const reference to the arc map storing
kpeter@346
   415
    /// the flow that is the union of the found arc-disjoint paths.
alpar@345
   416
    ///
kpeter@346
   417
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   418
    /// this function.
alpar@345
   419
    const FlowMap& flowMap() const {
alpar@345
   420
      return *_flow;
alpar@345
   421
    }
alpar@345
   422
kpeter@346
   423
    /// \brief Return a const reference to the node map storing the
alpar@345
   424
    /// found potentials (the dual solution).
alpar@345
   425
    ///
kpeter@346
   426
    /// This function returns a const reference to the node map storing
kpeter@346
   427
    /// the found potentials that provide the dual solution of the
kpeter@346
   428
    /// underlying minimum cost flow problem.
alpar@345
   429
    ///
kpeter@346
   430
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   431
    /// this function.
alpar@345
   432
    const PotentialMap& potentialMap() const {
alpar@345
   433
      return *_potential;
alpar@345
   434
    }
alpar@345
   435
kpeter@346
   436
    /// \brief Return the flow on the given arc.
alpar@345
   437
    ///
kpeter@346
   438
    /// This function returns the flow on the given arc.
alpar@345
   439
    /// It is \c 1 if the arc is involved in one of the found paths,
alpar@345
   440
    /// otherwise it is \c 0.
alpar@345
   441
    ///
kpeter@346
   442
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   443
    /// this function.
alpar@345
   444
    int flow(const Arc& arc) const {
alpar@345
   445
      return (*_flow)[arc];
alpar@345
   446
    }
alpar@345
   447
kpeter@346
   448
    /// \brief Return the potential of the given node.
alpar@345
   449
    ///
kpeter@346
   450
    /// This function returns the potential of the given node.
alpar@345
   451
    ///
kpeter@346
   452
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   453
    /// this function.
alpar@345
   454
    Length potential(const Node& node) const {
alpar@345
   455
      return (*_potential)[node];
alpar@345
   456
    }
alpar@345
   457
kpeter@346
   458
    /// \brief Return the total length (cost) of the found paths (flow).
alpar@345
   459
    ///
kpeter@346
   460
    /// This function returns the total length (cost) of the found paths
kpeter@346
   461
    /// (flow). The complexity of the function is \f$ O(e) \f$.
alpar@345
   462
    ///
kpeter@346
   463
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   464
    /// this function.
alpar@345
   465
    Length totalLength() const {
alpar@345
   466
      Length c = 0;
alpar@345
   467
      for (ArcIt e(_graph); e != INVALID; ++e)
alpar@345
   468
        c += (*_flow)[e] * _length[e];
alpar@345
   469
      return c;
alpar@345
   470
    }
alpar@345
   471
kpeter@346
   472
    /// \brief Return the number of the found paths.
alpar@345
   473
    ///
kpeter@346
   474
    /// This function returns the number of the found paths.
alpar@345
   475
    ///
kpeter@346
   476
    /// \pre \ref run() or \ref findFlow() must be called before using
kpeter@346
   477
    /// this function.
alpar@345
   478
    int pathNum() const {
alpar@345
   479
      return _path_num;
alpar@345
   480
    }
alpar@345
   481
kpeter@346
   482
    /// \brief Return a const reference to the specified path.
alpar@345
   483
    ///
kpeter@346
   484
    /// This function returns a const reference to the specified path.
alpar@345
   485
    ///
alpar@345
   486
    /// \param i The function returns the \c i-th path.
alpar@345
   487
    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
alpar@345
   488
    ///
kpeter@346
   489
    /// \pre \ref run() or \ref findPaths() must be called before using
kpeter@346
   490
    /// this function.
alpar@345
   491
    Path path(int i) const {
alpar@345
   492
      return paths[i];
alpar@345
   493
    }
alpar@345
   494
alpar@345
   495
    /// @}
alpar@345
   496
alpar@345
   497
  }; //class Suurballe
alpar@345
   498
alpar@345
   499
  ///@}
alpar@345
   500
alpar@345
   501
} //namespace lemon
alpar@345
   502
alpar@345
   503
#endif //LEMON_SUURBALLE_H