COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 670:7c1324b35d89 in lemon for lemon/suurballe.h


Ignore:
Timestamp:
04/25/09 02:12:41 (16 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/suurballe.h

    r631 r670  
    2626
    2727#include <vector>
     28#include <limits>
    2829#include <lemon/bin_heap.h>
    2930#include <lemon/path.h>
    … …  
    4344  /// from a given source node to a given target node in a digraph.
    4445  ///
    45   /// In fact, this implementation is the specialization of the
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
     46  /// Note that this problem is a special case of the \ref min_cost_flow
     47  /// "minimum cost flow problem". This implementation is actually an
     48  /// efficient specialized version of the \ref CapacityScaling
     49  /// "Successive Shortest Path" algorithm directly for this problem.
     50  /// Therefore this class provides query functions for flow values and
     51  /// node potentials (the dual solution) just like the minimum cost flow
     52  /// algorithms.
    4753  ///
    4854  /// \tparam GR The digraph type the algorithm runs on.
    49   /// The default value is \c ListDigraph.
    50   /// \tparam LEN The type of the length (cost) map.
    51   /// The default value is <tt>Digraph::ArcMap<int></tt>.
     55  /// \tparam LEN The type of the length map.
     56  /// The default value is <tt>GR::ArcMap<int></tt>.
    5257  ///
    5358  /// \warning Length values should be \e non-negative \e integers.
    5459  ///
    5560  /// \note For finding node-disjoint paths this algorithm can be used
    56   /// with \ref SplitNodes.
     61  /// along with the \ref SplitNodes adaptor.
    5762#ifdef DOXYGEN
    5863  template <typename GR, typename LEN>
    5964#else
    60   template < typename GR = ListDigraph,
     65  template < typename GR,
    6166             typename LEN = typename GR::template ArcMap<int> >
    6267#endif
    … …  
    7681    /// The type of the lengths.
    7782    typedef typename LengthMap::Value Length;
     83#ifdef DOXYGEN
     84    /// The type of the flow map.
     85    typedef GR::ArcMap<int> FlowMap;
     86    /// The type of the potential map.
     87    typedef GR::NodeMap<Length> PotentialMap;
     88#else
    7889    /// The type of the flow map.
    7990    typedef typename Digraph::template ArcMap<int> FlowMap;
    8091    /// The type of the potential map.
    8192    typedef typename Digraph::template NodeMap<Length> PotentialMap;
     93#endif
     94
    8295    /// The type of the path structures.
    83     typedef SimplePath<Digraph> Path;
     96    typedef SimplePath<GR> Path;
    8497
    8598  private:
    8699
    87     /// \brief Special implementation of the Dijkstra algorithm
    88     /// for finding shortest paths in the residual network.
    89     ///
    90     /// \ref ResidualDijkstra is a special implementation of the
    91     /// \ref Dijkstra algorithm for finding shortest paths in the
    92     /// residual network of the digraph with respect to the reduced arc
    93     /// lengths and modifying the node potentials according to the
    94     /// distance of the nodes.
     100    // ResidualDijkstra is a special implementation of the
     101    // Dijkstra algorithm for finding shortest paths in the
     102    // residual network with respect to the reduced arc lengths
     103    // and modifying the node potentials according to the
     104    // distance of the nodes.
    95105    class ResidualDijkstra
    96106    {
    … …  
    121131
    122132      /// Constructor.
    123       ResidualDijkstra( const Digraph &digraph,
     133      ResidualDijkstra( const Digraph &graph,
    124134                        const FlowMap &flow,
    125135                        const LengthMap &length,
    … …  
    127137                        PredMap &pred,
    128138                        Node s, Node t ) :
    129         _graph(digraph), _flow(flow), _length(length), _potential(potential),
    130         _dist(digraph), _pred(pred), _s(s), _t(t) {}
     139        _graph(graph), _flow(flow), _length(length), _potential(potential),
     140        _dist(graph), _pred(pred), _s(s), _t(t) {}
    131141
    132142      /// \brief Run the algorithm. It returns \c true if a path is found
    … …  
    237247    /// Constructor.
    238248    ///
    239     /// \param digraph The digraph the algorithm runs on.
     249    /// \param graph The digraph the algorithm runs on.
    240250    /// \param length The length (cost) values of the arcs.
    241     /// \param s The source node.
    242     /// \param t The target node.
    243     Suurballe( const Digraph &digraph,
    244                const LengthMap &length,
    245                Node s, Node t ) :
    246       _graph(digraph), _length(length), _flow(0), _local_flow(false),
    247       _potential(0), _local_potential(false), _source(s), _target(t),
    248       _pred(digraph) {}
     251    Suurballe( const Digraph &graph,
     252               const LengthMap &length ) :
     253      _graph(graph), _length(length), _flow(0), _local_flow(false),
     254      _potential(0), _local_potential(false), _pred(graph)
     255    {
     256      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
     257        "The length type of Suurballe must be integer");
     258    }
    249259
    250260    /// Destructor.
    … …  
    258268    ///
    259269    /// This function sets the flow map.
    260     ///
    261     /// The found flow contains only 0 and 1 values. It is the union of
    262     /// the found arc-disjoint paths.
     270    /// If it is not used before calling \ref run() or \ref init(),
     271    /// an instance will be allocated automatically. The destructor
     272    /// deallocates this automatically allocated map, of course.
     273    ///
     274    /// The found flow contains only 0 and 1 values, since it is the
     275    /// union of the found arc-disjoint paths.
    263276    ///
    264277    /// \return <tt>(*this)</tt>
    … …  
    275288    ///
    276289    /// This function sets the potential map.
    277     ///
    278     /// The potentials provide the dual solution of the underlying
    279     /// minimum cost flow problem.
     290    /// If it is not used before calling \ref run() or \ref init(),
     291    /// an instance will be allocated automatically. The destructor
     292    /// deallocates this automatically allocated map, of course.
     293    ///
     294    /// The node potentials provide the dual solution of the underlying
     295    /// \ref min_cost_flow "minimum cost flow problem".
    280296    ///
    281297    /// \return <tt>(*this)</tt>
    … …  
    302318    /// This function runs the algorithm.
    303319    ///
     320    /// \param s The source node.
     321    /// \param t The target node.
    304322    /// \param k The number of paths to be found.
    305323    ///
    … …  
    308326    /// arc-disjoint paths found.
    309327    ///
    310     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
    311     /// shortcut of the following code.
     328    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
     329    /// just a shortcut of the following code.
    312330    /// \code
    313     ///   s.init();
    314     ///   s.findFlow(k);
     331    ///   s.init(s);
     332    ///   s.findFlow(t, k);
    315333    ///   s.findPaths();
    316334    /// \endcode
    317     int run(int k = 2) {
    318       init();
    319       findFlow(k);
     335    int run(const Node& s, const Node& t, int k = 2) {
     336      init(s);
     337      findFlow(t, k);
    320338      findPaths();
    321339      return _path_num;
    … …  
    325343    ///
    326344    /// This function initializes the algorithm.
    327     void init() {
     345    ///
     346    /// \param s The source node.
     347    void init(const Node& s) {
     348      _source = s;
     349
    328350      // Initialize maps
    329351      if (!_flow) {
    … …  
    337359      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    338360      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    339 
    340       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
    341                                         *_potential, _pred,
    342                                         _source, _target );
    343     }
    344 
    345     /// \brief Execute the successive shortest path algorithm to find
    346     /// an optimal flow.
     361    }
     362
     363    /// \brief Execute the algorithm to find an optimal flow.
    347364    ///
    348365    /// This function executes the successive shortest path algorithm to
    349     /// find a minimum cost flow, which is the union of \c k or less
     366    /// find a minimum cost flow, which is the union of \c k (or less)
    350367    /// arc-disjoint paths.
    351368    ///
     369    /// \param t The target node.
     370    /// \param k The number of paths to be found.
     371    ///
    352372    /// \return \c k if there are at least \c k arc-disjoint paths from
    353     /// \c s to \c t in the digraph. Otherwise it returns the number of
    354     /// arc-disjoint paths found.
     373    /// the source node to the given node \c t in the digraph.
     374    /// Otherwise it returns the number of arc-disjoint paths found.
    355375    ///
    356376    /// \pre \ref init() must be called before using this function.
    357     int findFlow(int k = 2) {
     377    int findFlow(const Node& t, int k = 2) {
     378      _target = t;
     379      _dijkstra =
     380        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
     381                              _source, _target );
     382
    358383      // Find shortest paths
    359384      _path_num = 0;
    … …  
    381406    /// \brief Compute the paths from the flow.
    382407    ///
    383     /// This function computes the paths from the flow.
     408    /// This function computes the paths from the found minimum cost flow,
     409    /// which is the union of some arc-disjoint paths.
    384410    ///
    385411    /// \pre \ref init() and \ref findFlow() must be called before using
    386412    /// this function.
    387413    void findPaths() {
    388       // Create the residual flow map (the union of the paths not found
    389       // so far)
    390414      FlowMap res_flow(_graph);
    391415      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    … …  
    414438    /// @{
    415439
    416     /// \brief Return a const reference to the arc map storing the
    417     /// found flow.
    418     ///
    419     /// This function returns a const reference to the arc map storing
    420     /// the flow that is the union of the found arc-disjoint paths.
    421     ///
    422     /// \pre \ref run() or \ref findFlow() must be called before using
    423     /// this function.
    424     const FlowMap& flowMap() const {
    425       return *_flow;
    426     }
    427 
    428     /// \brief Return a const reference to the node map storing the
    429     /// found potentials (the dual solution).
    430     ///
    431     /// This function returns a const reference to the node map storing
    432     /// the found potentials that provide the dual solution of the
    433     /// underlying minimum cost flow problem.
    434     ///
    435     /// \pre \ref run() or \ref findFlow() must be called before using
    436     /// this function.
    437     const PotentialMap& potentialMap() const {
    438       return *_potential;
    439     }
    440 
    441     /// \brief Return the flow on the given arc.
    442     ///
    443     /// This function returns the flow on the given arc.
    444     /// It is \c 1 if the arc is involved in one of the found paths,
    445     /// otherwise it is \c 0.
    446     ///
    447     /// \pre \ref run() or \ref findFlow() must be called before using
    448     /// this function.
    449     int flow(const Arc& arc) const {
    450       return (*_flow)[arc];
    451     }
    452 
    453     /// \brief Return the potential of the given node.
    454     ///
    455     /// This function returns the potential of the given node.
    456     ///
    457     /// \pre \ref run() or \ref findFlow() must be called before using
    458     /// this function.
    459     Length potential(const Node& node) const {
    460       return (*_potential)[node];
    461     }
    462 
    463     /// \brief Return the total length (cost) of the found paths (flow).
    464     ///
    465     /// This function returns the total length (cost) of the found paths
    466     /// (flow). The complexity of the function is O(e).
     440    /// \brief Return the total length of the found paths.
     441    ///
     442    /// This function returns the total length of the found paths, i.e.
     443    /// the total cost of the found flow.
     444    /// The complexity of the function is O(e).
    467445    ///
    468446    /// \pre \ref run() or \ref findFlow() must be called before using
    … …  
    475453    }
    476454
     455    /// \brief Return the flow value on the given arc.
     456    ///
     457    /// This function returns the flow value on the given arc.
     458    /// It is \c 1 if the arc is involved in one of the found arc-disjoint
     459    /// paths, otherwise it is \c 0.
     460    ///
     461    /// \pre \ref run() or \ref findFlow() must be called before using
     462    /// this function.
     463    int flow(const Arc& arc) const {
     464      return (*_flow)[arc];
     465    }
     466
     467    /// \brief Return a const reference to an arc map storing the
     468    /// found flow.
     469    ///
     470    /// This function returns a const reference to an arc map storing
     471    /// the flow that is the union of the found arc-disjoint paths.
     472    ///
     473    /// \pre \ref run() or \ref findFlow() must be called before using
     474    /// this function.
     475    const FlowMap& flowMap() const {
     476      return *_flow;
     477    }
     478
     479    /// \brief Return the potential of the given node.
     480    ///
     481    /// This function returns the potential of the given node.
     482    /// The node potentials provide the dual solution of the
     483    /// underlying \ref min_cost_flow "minimum cost flow problem".
     484    ///
     485    /// \pre \ref run() or \ref findFlow() must be called before using
     486    /// this function.
     487    Length potential(const Node& node) const {
     488      return (*_potential)[node];
     489    }
     490
     491    /// \brief Return a const reference to a node map storing the
     492    /// found potentials (the dual solution).
     493    ///
     494    /// This function returns a const reference to a node map storing
     495    /// the found potentials that provide the dual solution of the
     496    /// underlying \ref min_cost_flow "minimum cost flow problem".
     497    ///
     498    /// \pre \ref run() or \ref findFlow() must be called before using
     499    /// this function.
     500    const PotentialMap& potentialMap() const {
     501      return *_potential;
     502    }
     503
    477504    /// \brief Return the number of the found paths.
    478505    ///
    … …  
    489516    /// This function returns a const reference to the specified path.
    490517    ///
    491     /// \param i The function returns the \c i-th path.
     518    /// \param i The function returns the <tt>i</tt>-th path.
    492519    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
    493520    ///
Note: See TracChangeset for help on using the changeset viewer.