COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 623:7c1324b35d89 in lemon-main


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.
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • lemon/suurballe.h

    r584 r623  
    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    ///

  • test/suurballe_test.cc

    r440 r623  
    2323#include <lemon/path.h>
    2424#include <lemon/suurballe.h>
     25#include <lemon/concepts/digraph.h>
    2526
    2627#include "test_tools.h"
    … …  
    3031char test_lgf[] =
    3132  "@nodes\n"
    32   "label supply1 supply2 supply3\n"
    33   "1     0        20      27\n"
    34   "2     0       -4        0\n"
    35   "3     0        0        0\n"
    36   "4     0        0        0\n"
    37   "5     0        9        0\n"
    38   "6     0       -6        0\n"
    39   "7     0        0        0\n"
    40   "8     0        0        0\n"
    41   "9     0        3        0\n"
    42   "10    0       -2        0\n"
    43   "11    0        0        0\n"
    44   "12    0       -20     -27\n"
     33  "label\n"
     34  "1\n"
     35  "2\n"
     36  "3\n"
     37  "4\n"
     38  "5\n"
     39  "6\n"
     40  "7\n"
     41  "8\n"
     42  "9\n"
     43  "10\n"
     44  "11\n"
     45  "12\n"
    4546  "@arcs\n"
    46   "      cost capacity lower1 lower2\n"
    47   " 1  2  70  11       0      8\n"
    48   " 1  3 150   3       0      1\n"
    49   " 1  4  80  15       0      2\n"
    50   " 2  8  80  12       0      0\n"
    51   " 3  5 140   5       0      3\n"
    52   " 4  6  60  10       0      1\n"
    53   " 4  7  80   2       0      0\n"
    54   " 4  8 110   3       0      0\n"
    55   " 5  7  60  14       0      0\n"
    56   " 5 11 120  12       0      0\n"
    57   " 6  3   0   3       0      0\n"
    58   " 6  9 140   4       0      0\n"
    59   " 6 10  90   8       0      0\n"
    60   " 7  1  30   5       0      0\n"
    61   " 8 12  60  16       0      4\n"
    62   " 9 12  50   6       0      0\n"
    63   "10 12  70  13       0      5\n"
    64   "10  2 100   7       0      0\n"
    65   "10  7  60  10       0      0\n"
    66   "11 10  20  14       0      6\n"
    67   "12 11  30  10       0      0\n"
     47  "      length\n"
     48  " 1  2  70\n"
     49  " 1  3 150\n"
     50  " 1  4  80\n"
     51  " 2  8  80\n"
     52  " 3  5 140\n"
     53  " 4  6  60\n"
     54  " 4  7  80\n"
     55  " 4  8 110\n"
     56  " 5  7  60\n"
     57  " 5 11 120\n"
     58  " 6  3   0\n"
     59  " 6  9 140\n"
     60  " 6 10  90\n"
     61  " 7  1  30\n"
     62  " 8 12  60\n"
     63  " 9 12  50\n"
     64  "10 12  70\n"
     65  "10  2 100\n"
     66  "10  7  60\n"
     67  "11 10  20\n"
     68  "12 11  30\n"
    6869  "@attributes\n"
    6970  "source  1\n"
    7071  "target 12\n"
    7172  "@end\n";
     73
     74// Check the interface of Suurballe
     75void checkSuurballeCompile()
     76{
     77  typedef int VType;
     78  typedef concepts::Digraph Digraph;
     79
     80  typedef Digraph::Node Node;
     81  typedef Digraph::Arc Arc;
     82  typedef concepts::ReadMap<Arc, VType> LengthMap;
     83 
     84  typedef Suurballe<Digraph, LengthMap> SuurballeType;
     85
     86  Digraph g;
     87  Node n;
     88  Arc e;
     89  LengthMap len;
     90  SuurballeType::FlowMap flow(g);
     91  SuurballeType::PotentialMap pi(g);
     92
     93  SuurballeType suurb_test(g, len);
     94  const SuurballeType& const_suurb_test = suurb_test;
     95
     96  suurb_test
     97    .flowMap(flow)
     98    .potentialMap(pi);
     99
     100  int k;
     101  k = suurb_test.run(n, n);
     102  k = suurb_test.run(n, n, k);
     103  suurb_test.init(n);
     104  k = suurb_test.findFlow(n);
     105  k = suurb_test.findFlow(n, k);
     106  suurb_test.findPaths();
     107 
     108  int f;
     109  VType c;
     110  c = const_suurb_test.totalLength();
     111  f = const_suurb_test.flow(e);
     112  const SuurballeType::FlowMap& fm =
     113    const_suurb_test.flowMap();
     114  c = const_suurb_test.potential(n);
     115  const SuurballeType::PotentialMap& pm =
     116    const_suurb_test.potentialMap();
     117  k = const_suurb_test.pathNum();
     118  Path<Digraph> p = const_suurb_test.path(k);
     119 
     120  ignore_unused_variable_warning(fm);
     121  ignore_unused_variable_warning(pm);
     122}
    72123
    73124// Check the feasibility of the flow
    … …  
    119170                typename Digraph::Node s, typename Digraph::Node t)
    120171{
    121   // Check the "Complementary Slackness" optimality condition
    122172  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    123173  Node n = s;
    … …  
    137187  ListDigraph digraph;
    138188  ListDigraph::ArcMap<int> length(digraph);
    139   Node source, target;
     189  Node s, t;
    140190
    141191  std::istringstream input(test_lgf);
    142192  DigraphReader<ListDigraph>(digraph, input).
    143     arcMap("cost", length).
    144     node("source", source).
    145     node("target", target).
     193    arcMap("length", length).
     194    node("source", s).
     195    node("target", t).
    146196    run();
    147197
    148198  // Find 2 paths
    149199  {
    150     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    151     check(suurballe.run(2) == 2, "Wrong number of paths");
    152     check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
     200    Suurballe<ListDigraph> suurballe(digraph, length);
     201    check(suurballe.run(s, t) == 2, "Wrong number of paths");
     202    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
    153203          "The flow is not feasible");
    154204    check(suurballe.totalLength() == 510, "The flow is not optimal");
    … …  
    157207          "Wrong potentials");
    158208    for (int i = 0; i < suurballe.pathNum(); ++i)
    159       check(checkPath(digraph, suurballe.path(i), source, target),
    160             "Wrong path");
     209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    161210  }
    162211
    163212  // Find 3 paths
    164213  {
    165     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    166     check(suurballe.run(3) == 3, "Wrong number of paths");
    167     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     214    Suurballe<ListDigraph> suurballe(digraph, length);
     215    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
     216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    168217          "The flow is not feasible");
    169218    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    172221          "Wrong potentials");
    173222    for (int i = 0; i < suurballe.pathNum(); ++i)
    174       check(checkPath(digraph, suurballe.path(i), source, target),
    175             "Wrong path");
     223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    176224  }
    177225
    178226  // Find 5 paths (only 3 can be found)
    179227  {
    180     Suurballe<ListDigraph> suurballe(digraph, length, source, target);
    181     check(suurballe.run(5) == 3, "Wrong number of paths");
    182     check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
     228    Suurballe<ListDigraph> suurballe(digraph, length);
     229    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
     230    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    183231          "The flow is not feasible");
    184232    check(suurballe.totalLength() == 1040, "The flow is not optimal");
    … …  
    187235          "Wrong potentials");
    188236    for (int i = 0; i < suurballe.pathNum(); ++i)
    189       check(checkPath(digraph, suurballe.path(i), source, target),
    190             "Wrong path");
     237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    191238  }
    192239

  • tools/lgf-gen.cc

    r616 r623  
    481481      g.erase(*ei);
    482482      ConstMap<Arc,int> cegy(1);
    483       Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
    484       int k=sur.run(2);
     483      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     484      int k=sur.run(a,b,2);
    485485      if(k<2 || sur.totalLength()>d)
    486486        g.addEdge(a,b);
    … …  
    512512      if(e==INVALID) {
    513513        ConstMap<Arc,int> cegy(1);
    514         Suurballe<ListGraph,ConstMap<Arc,int> >
    515           sur(g,cegy,pi->a,pi->b);
    516         int k=sur.run(2);
     514        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
     515        int k=sur.run(pi->a,pi->b,2);
    517516        if(k<2 || sur.totalLength()>d)
    518517          {
Note: See TracChangeset for help on using the changeset viewer.