COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/suurballe.h

    r670 r631  
    2626
    2727#include <vector>
    28 #include <limits>
    2928#include <lemon/bin_heap.h>
    3029#include <lemon/path.h>
    … …  
    4443  /// from a given source node to a given target node in a digraph.
    4544  ///
    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.
     45  /// In fact, this implementation is the specialization of the
     46  /// \ref CapacityScaling "successive shortest path" algorithm.
    5347  ///
    5448  /// \tparam GR The digraph type the algorithm runs on.
    55   /// \tparam LEN The type of the length map.
    56   /// The default value is <tt>GR::ArcMap<int></tt>.
     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>.
    5752  ///
    5853  /// \warning Length values should be \e non-negative \e integers.
    5954  ///
    6055  /// \note For finding node-disjoint paths this algorithm can be used
    61   /// along with the \ref SplitNodes adaptor.
     56  /// with \ref SplitNodes.
    6257#ifdef DOXYGEN
    6358  template <typename GR, typename LEN>
    6459#else
    65   template < typename GR,
     60  template < typename GR = ListDigraph,
    6661             typename LEN = typename GR::template ArcMap<int> >
    6762#endif
    … …  
    8176    /// The type of the lengths.
    8277    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
    8978    /// The type of the flow map.
    9079    typedef typename Digraph::template ArcMap<int> FlowMap;
    9180    /// The type of the potential map.
    9281    typedef typename Digraph::template NodeMap<Length> PotentialMap;
    93 #endif
    94 
    9582    /// The type of the path structures.
    96     typedef SimplePath<GR> Path;
     83    typedef SimplePath<Digraph> Path;
    9784
    9885  private:
    9986
    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.
     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.
    10595    class ResidualDijkstra
    10696    {
    … …  
    131121
    132122      /// Constructor.
    133       ResidualDijkstra( const Digraph &graph,
     123      ResidualDijkstra( const Digraph &digraph,
    134124                        const FlowMap &flow,
    135125                        const LengthMap &length,
    … …  
    137127                        PredMap &pred,
    138128                        Node s, Node t ) :
    139         _graph(graph), _flow(flow), _length(length), _potential(potential),
    140         _dist(graph), _pred(pred), _s(s), _t(t) {}
     129        _graph(digraph), _flow(flow), _length(length), _potential(potential),
     130        _dist(digraph), _pred(pred), _s(s), _t(t) {}
    141131
    142132      /// \brief Run the algorithm. It returns \c true if a path is found
    … …  
    247237    /// Constructor.
    248238    ///
    249     /// \param graph The digraph the algorithm runs on.
     239    /// \param digraph The digraph the algorithm runs on.
    250240    /// \param length The length (cost) values of the arcs.
    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     }
     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) {}
    259249
    260250    /// Destructor.
    … …  
    268258    ///
    269259    /// This function sets the flow map.
    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.
     260    ///
     261    /// The found flow contains only 0 and 1 values. It is the union of
     262    /// the found arc-disjoint paths.
    276263    ///
    277264    /// \return <tt>(*this)</tt>
    … …  
    288275    ///
    289276    /// This function sets the potential map.
    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".
     277    ///
     278    /// The potentials provide the dual solution of the underlying
     279    /// minimum cost flow problem.
    296280    ///
    297281    /// \return <tt>(*this)</tt>
    … …  
    318302    /// This function runs the algorithm.
    319303    ///
    320     /// \param s The source node.
    321     /// \param t The target node.
    322304    /// \param k The number of paths to be found.
    323305    ///
    … …  
    326308    /// arc-disjoint paths found.
    327309    ///
    328     /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
    329     /// just a shortcut of the following code.
     310    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
     311    /// shortcut of the following code.
    330312    /// \code
    331     ///   s.init(s);
    332     ///   s.findFlow(t, k);
     313    ///   s.init();
     314    ///   s.findFlow(k);
    333315    ///   s.findPaths();
    334316    /// \endcode
    335     int run(const Node& s, const Node& t, int k = 2) {
    336       init(s);
    337       findFlow(t, k);
     317    int run(int k = 2) {
     318      init();
     319      findFlow(k);
    338320      findPaths();
    339321      return _path_num;
    … …  
    343325    ///
    344326    /// This function initializes the algorithm.
    345     ///
    346     /// \param s The source node.
    347     void init(const Node& s) {
    348       _source = s;
    349 
     327    void init() {
    350328      // Initialize maps
    351329      if (!_flow) {
    … …  
    359337      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    360338      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    361     }
    362 
    363     /// \brief Execute the algorithm to find an optimal flow.
     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.
    364347    ///
    365348    /// This function executes the successive shortest path algorithm to
    366     /// find a minimum cost flow, which is the union of \c k (or less)
     349    /// find a minimum cost flow, which is the union of \c k or less
    367350    /// arc-disjoint paths.
    368351    ///
    369     /// \param t The target node.
    370     /// \param k The number of paths to be found.
    371     ///
    372352    /// \return \c k if there are at least \c k arc-disjoint paths from
    373     /// the source node to the given node \c t in the digraph.
    374     /// Otherwise it returns the number of arc-disjoint paths found.
     353    /// \c s to \c t in the digraph. Otherwise it returns the number of
     354    /// arc-disjoint paths found.
    375355    ///
    376356    /// \pre \ref init() must be called before using this function.
    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 
     357    int findFlow(int k = 2) {
    383358      // Find shortest paths
    384359      _path_num = 0;
    … …  
    406381    /// \brief Compute the paths from the flow.
    407382    ///
    408     /// This function computes the paths from the found minimum cost flow,
    409     /// which is the union of some arc-disjoint paths.
     383    /// This function computes the paths from the flow.
    410384    ///
    411385    /// \pre \ref init() and \ref findFlow() must be called before using
    412386    /// this function.
    413387    void findPaths() {
     388      // Create the residual flow map (the union of the paths not found
     389      // so far)
    414390      FlowMap res_flow(_graph);
    415391      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    … …  
    438414    /// @{
    439415
    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).
     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).
    445467    ///
    446468    /// \pre \ref run() or \ref findFlow() must be called before using
    … …  
    453475    }
    454476
    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 
    504477    /// \brief Return the number of the found paths.
    505478    ///
    … …  
    516489    /// This function returns a const reference to the specified path.
    517490    ///
    518     /// \param i The function returns the <tt>i</tt>-th path.
     491    /// \param i The function returns the \c i-th path.
    519492    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
    520493    ///
Note: See TracChangeset for help on using the changeset viewer.