COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
3 added
3 deleted
4 edited

Legend:

Unmodified
Added
Removed

  • lemon/Makefile.am

    r888 r933  
    6161        lemon/bfs.h \
    6262        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
     63        lemon/binomial_heap.h \
    6464        lemon/bucket_heap.h \
    6565        lemon/capacity_scaling.h \
    … …  
    7676        lemon/cycle_canceling.h \
    7777        lemon/dfs.h \
     78        lemon/dheap.h \
    7879        lemon/dijkstra.h \
    7980        lemon/dim2.h \
    … …  
    8485        lemon/euler.h \
    8586        lemon/fib_heap.h \
    86         lemon/fourary_heap.h \
    8787        lemon/full_graph.h \
    8888        lemon/glpk.h \
    … …  
    9494        lemon/hypercube_graph.h \
    9595        lemon/karp.h \
    96         lemon/kary_heap.h \
    9796        lemon/kruskal.h \
    9897        lemon/hao_orlin.h \
    … …  
    113112        lemon/planarity.h \
    114113        lemon/preflow.h \
     114        lemon/quad_heap.h \
    115115        lemon/radix_heap.h \
    116116        lemon/radix_sort.h \

  • lemon/suurballe.h

    r670 r931  
    3030#include <lemon/path.h>
    3131#include <lemon/list_graph.h>
     32#include <lemon/dijkstra.h>
    3233#include <lemon/maps.h>
    3334
    3435namespace lemon {
     36
     37  /// \brief Default traits class of Suurballe algorithm.
     38  ///
     39  /// Default traits class of Suurballe algorithm.
     40  /// \tparam GR The digraph type the algorithm runs on.
     41  /// \tparam LEN The type of the length map.
     42  /// The default value is <tt>GR::ArcMap<int></tt>.
     43#ifdef DOXYGEN
     44  template <typename GR, typename LEN>
     45#else
     46  template < typename GR,
     47             typename LEN = typename GR::template ArcMap<int> >
     48#endif
     49  struct SuurballeDefaultTraits
     50  {
     51    /// The type of the digraph.
     52    typedef GR Digraph;
     53    /// The type of the length map.
     54    typedef LEN LengthMap;
     55    /// The type of the lengths.
     56    typedef typename LEN::Value Length;
     57    /// The type of the flow map.
     58    typedef typename GR::template ArcMap<int> FlowMap;
     59    /// The type of the potential map.
     60    typedef typename GR::template NodeMap<Length> PotentialMap;
     61
     62    /// \brief The path type
     63    ///
     64    /// The type used for storing the found arc-disjoint paths.
     65    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     66    /// and it must have an \c addBack() function.
     67    typedef lemon::Path<Digraph> Path;
     68   
     69    /// The cross reference type used for the heap.
     70    typedef typename GR::template NodeMap<int> HeapCrossRef;
     71
     72    /// \brief The heap type used for internal Dijkstra computations.
     73    ///
     74    /// The type of the heap used for internal Dijkstra computations.
     75    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept
     76    /// and its priority type must be \c Length.
     77    typedef BinHeap<Length, HeapCrossRef> Heap;
     78  };
    3579
    3680  /// \addtogroup shortest_path
    … …  
    4791  /// "minimum cost flow problem". This implementation is actually an
    4892  /// efficient specialized version of the \ref CapacityScaling
    49   /// "Successive Shortest Path" algorithm directly for this problem.
     93  /// "successive shortest path" algorithm directly for this problem.
    5094  /// Therefore this class provides query functions for flow values and
    5195  /// node potentials (the dual solution) just like the minimum cost flow
    … …  
    56100  /// The default value is <tt>GR::ArcMap<int></tt>.
    57101  ///
    58   /// \warning Length values should be \e non-negative \e integers.
     102  /// \warning Length values should be \e non-negative.
    59103  ///
    60   /// \note For finding node-disjoint paths this algorithm can be used
     104  /// \note For finding \e node-disjoint paths, this algorithm can be used
    61105  /// along with the \ref SplitNodes adaptor.
    62106#ifdef DOXYGEN
    63   template <typename GR, typename LEN>
     107  template <typename GR, typename LEN, typename TR>
    64108#else
    65109  template < typename GR,
    66              typename LEN = typename GR::template ArcMap<int> >
     110             typename LEN = typename GR::template ArcMap<int>,
     111             typename TR = SuurballeDefaultTraits<GR, LEN> >
    67112#endif
    68113  class Suurballe
    … …  
    75120  public:
    76121
    77     /// The type of the digraph the algorithm runs on.
    78     typedef GR Digraph;
     122    /// The type of the digraph.
     123    typedef typename TR::Digraph Digraph;
    79124    /// The type of the length map.
    80     typedef LEN LengthMap;
     125    typedef typename TR::LengthMap LengthMap;
    81126    /// The type of the lengths.
    82     typedef typename LengthMap::Value Length;
    83 #ifdef DOXYGEN
     127    typedef typename TR::Length Length;
     128
    84129    /// The type of the flow map.
    85     typedef GR::ArcMap<int> FlowMap;
     130    typedef typename TR::FlowMap FlowMap;
    86131    /// The type of the potential map.
    87     typedef GR::NodeMap<Length> PotentialMap;
    88 #else
    89     /// The type of the flow map.
    90     typedef typename Digraph::template ArcMap<int> FlowMap;
    91     /// The type of the potential map.
    92     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    93 #endif
    94 
     132    typedef typename TR::PotentialMap PotentialMap;
    95133    /// The type of the path structures.
    96     typedef SimplePath<GR> Path;
     134    typedef typename TR::Path Path;
     135    /// The cross reference type used for the heap.
     136    typedef typename TR::HeapCrossRef HeapCrossRef;
     137    /// The heap type used for internal Dijkstra computations.
     138    typedef typename TR::Heap Heap;
     139
     140    /// The \ref SuurballeDefaultTraits "traits class" of the algorithm.
     141    typedef TR Traits;
    97142
    98143  private:
    … …  
    105150    class ResidualDijkstra
    106151    {
    107       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    108       typedef BinHeap<Length, HeapCrossRef> Heap;
    109 
    110152    private:
    111153
    112       // The digraph the algorithm runs on
    113154      const Digraph &_graph;
    114 
    115       // The main maps
     155      const LengthMap &_length;
    116156      const FlowMap &_flow;
    117       const LengthMap &_length;
    118       PotentialMap &_potential;
    119 
    120       // The distance map
    121       PotentialMap _dist;
    122       // The pred arc map
     157      PotentialMap &_pi;
    123158      PredMap &_pred;
    124       // The processed (i.e. permanently labeled) nodes
    125       std::vector<Node> _proc_nodes;
    126 
    127159      Node _s;
    128160      Node _t;
     161     
     162      PotentialMap _dist;
     163      std::vector<Node> _proc_nodes;
    129164
    130165    public:
    131166
    132       /// Constructor.
    133       ResidualDijkstra( const Digraph &graph,
    134                         const FlowMap &flow,
    135                         const LengthMap &length,
    136                         PotentialMap &potential,
    137                         PredMap &pred,
    138                         Node s, Node t ) :
    139         _graph(graph), _flow(flow), _length(length), _potential(potential),
    140         _dist(graph), _pred(pred), _s(s), _t(t) {}
    141 
    142       /// \brief Run the algorithm. It returns \c true if a path is found
    143       /// from the source node to the target node.
    144       bool run() {
     167      // Constructor
     168      ResidualDijkstra(Suurballe &srb) :
     169        _graph(srb._graph), _length(srb._length),
     170        _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred),
     171        _s(srb._s), _t(srb._t), _dist(_graph) {}
     172       
     173      // Run the algorithm and return true if a path is found
     174      // from the source node to the target node.
     175      bool run(int cnt) {
     176        return cnt == 0 ? startFirst() : start();
     177      }
     178
     179    private:
     180   
     181      // Execute the algorithm for the first time (the flow and potential
     182      // functions have to be identically zero).
     183      bool startFirst() {
    145184        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
    146185        Heap heap(heap_cross_ref);
    … …  
    152191        while (!heap.empty() && heap.top() != _t) {
    153192          Node u = heap.top(), v;
    154           Length d = heap.prio() + _potential[u], nd;
     193          Length d = heap.prio(), dn;
    155194          _dist[u] = heap.prio();
     195          _proc_nodes.push_back(u);
    156196          heap.pop();
     197
     198          // Traverse outgoing arcs
     199          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
     200            v = _graph.target(e);
     201            switch(heap.state(v)) {
     202              case Heap::PRE_HEAP:
     203                heap.push(v, d + _length[e]);
     204                _pred[v] = e;
     205                break;
     206              case Heap::IN_HEAP:
     207                dn = d + _length[e];
     208                if (dn < heap[v]) {
     209                  heap.decrease(v, dn);
     210                  _pred[v] = e;
     211                }
     212                break;
     213              case Heap::POST_HEAP:
     214                break;
     215            }
     216          }
     217        }
     218        if (heap.empty()) return false;
     219
     220        // Update potentials of processed nodes
     221        Length t_dist = heap.prio();
     222        for (int i = 0; i < int(_proc_nodes.size()); ++i)
     223          _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]] - t_dist;
     224        return true;
     225      }
     226
     227      // Execute the algorithm.
     228      bool start() {
     229        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
     230        Heap heap(heap_cross_ref);
     231        heap.push(_s, 0);
     232        _pred[_s] = INVALID;
     233        _proc_nodes.clear();
     234
     235        // Process nodes
     236        while (!heap.empty() && heap.top() != _t) {
     237          Node u = heap.top(), v;
     238          Length d = heap.prio() + _pi[u], dn;
     239          _dist[u] = heap.prio();
    157240          _proc_nodes.push_back(u);
     241          heap.pop();
    158242
    159243          // Traverse outgoing arcs
    … …  
    162246              v = _graph.target(e);
    163247              switch(heap.state(v)) {
    164               case Heap::PRE_HEAP:
    165                 heap.push(v, d + _length[e] - _potential[v]);
    166                 _pred[v] = e;
    167                 break;
    168               case Heap::IN_HEAP:
    169                 nd = d + _length[e] - _potential[v];
    170                 if (nd < heap[v]) {
    171                   heap.decrease(v, nd);
     248                case Heap::PRE_HEAP:
     249                  heap.push(v, d + _length[e] - _pi[v]);
    172250                  _pred[v] = e;
    173                 }
    174                 break;
    175               case Heap::POST_HEAP:
    176                 break;
     251                  break;
     252                case Heap::IN_HEAP:
     253                  dn = d + _length[e] - _pi[v];
     254                  if (dn < heap[v]) {
     255                    heap.decrease(v, dn);
     256                    _pred[v] = e;
     257                  }
     258                  break;
     259                case Heap::POST_HEAP:
     260                  break;
    177261              }
    178262            }
    … …  
    184268              v = _graph.source(e);
    185269              switch(heap.state(v)) {
    186               case Heap::PRE_HEAP:
    187                 heap.push(v, d - _length[e] - _potential[v]);
    188                 _pred[v] = e;
    189                 break;
    190               case Heap::IN_HEAP:
    191                 nd = d - _length[e] - _potential[v];
    192                 if (nd < heap[v]) {
    193                   heap.decrease(v, nd);
     270                case Heap::PRE_HEAP:
     271                  heap.push(v, d - _length[e] - _pi[v]);
    194272                  _pred[v] = e;
    195                 }
    196                 break;
    197               case Heap::POST_HEAP:
    198                 break;
     273                  break;
     274                case Heap::IN_HEAP:
     275                  dn = d - _length[e] - _pi[v];
     276                  if (dn < heap[v]) {
     277                    heap.decrease(v, dn);
     278                    _pred[v] = e;
     279                  }
     280                  break;
     281                case Heap::POST_HEAP:
     282                  break;
    199283              }
    200284            }
    … …  
    206290        Length t_dist = heap.prio();
    207291        for (int i = 0; i < int(_proc_nodes.size()); ++i)
    208           _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
     292          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
    209293        return true;
    210294      }
    211295
    212296    }; //class ResidualDijkstra
     297
     298  public:
     299
     300    /// \name Named Template Parameters
     301    /// @{
     302
     303    template <typename T>
     304    struct SetFlowMapTraits : public Traits {
     305      typedef T FlowMap;
     306    };
     307
     308    /// \brief \ref named-templ-param "Named parameter" for setting
     309    /// \c FlowMap type.
     310    ///
     311    /// \ref named-templ-param "Named parameter" for setting
     312    /// \c FlowMap type.
     313    template <typename T>
     314    struct SetFlowMap
     315      : public Suurballe<GR, LEN, SetFlowMapTraits<T> > {
     316      typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create;
     317    };
     318
     319    template <typename T>
     320    struct SetPotentialMapTraits : public Traits {
     321      typedef T PotentialMap;
     322    };
     323
     324    /// \brief \ref named-templ-param "Named parameter" for setting
     325    /// \c PotentialMap type.
     326    ///
     327    /// \ref named-templ-param "Named parameter" for setting
     328    /// \c PotentialMap type.
     329    template <typename T>
     330    struct SetPotentialMap
     331      : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > {
     332      typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create;
     333    };
     334
     335    template <typename T>
     336    struct SetPathTraits : public Traits {
     337      typedef T Path;
     338    };
     339
     340    /// \brief \ref named-templ-param "Named parameter" for setting
     341    /// \c %Path type.
     342    ///
     343    /// \ref named-templ-param "Named parameter" for setting \c %Path type.
     344    /// It must conform to the \ref lemon::concepts::Path "Path" concept
     345    /// and it must have an \c addBack() function.
     346    template <typename T>
     347    struct SetPath
     348      : public Suurballe<GR, LEN, SetPathTraits<T> > {
     349      typedef Suurballe<GR, LEN, SetPathTraits<T> > Create;
     350    };
     351   
     352    template <typename H, typename CR>
     353    struct SetHeapTraits : public Traits {
     354      typedef H Heap;
     355      typedef CR HeapCrossRef;
     356    };
     357
     358    /// \brief \ref named-templ-param "Named parameter" for setting
     359    /// \c Heap and \c HeapCrossRef types.
     360    ///
     361    /// \ref named-templ-param "Named parameter" for setting \c Heap
     362    /// and \c HeapCrossRef types with automatic allocation.
     363    /// They will be used for internal Dijkstra computations.
     364    /// The heap type must conform to the \ref lemon::concepts::Heap "Heap"
     365    /// concept and its priority type must be \c Length.
     366    template <typename H,
     367              typename CR = typename Digraph::template NodeMap<int> >
     368    struct SetHeap
     369      : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > {
     370      typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create;
     371    };
     372
     373    /// @}
    213374
    214375  private:
    … …  
    227388
    228389    // The source node
    229     Node _source;
     390    Node _s;
    230391    // The target node
    231     Node _target;
     392    Node _t;
    232393
    233394    // Container to store the found paths
    234     std::vector< SimplePath<Digraph> > paths;
     395    std::vector<Path> _paths;
    235396    int _path_num;
    236397
    237398    // The pred arc map
    238399    PredMap _pred;
    239     // Implementation of the Dijkstra algorithm for finding augmenting
    240     // shortest paths in the residual network
    241     ResidualDijkstra *_dijkstra;
     400   
     401    // Data for full init
     402    PotentialMap *_init_dist;
     403    PredMap *_init_pred;
     404    bool _full_init;
    242405
    243406  public:
    … …  
    252415               const LengthMap &length ) :
    253416      _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     }
     417      _potential(0), _local_potential(false), _pred(graph),
     418      _init_dist(0), _init_pred(0)
     419    {}
    259420
    260421    /// Destructor.
    … …  
    262423      if (_local_flow) delete _flow;
    263424      if (_local_potential) delete _potential;
    264       delete _dijkstra;
     425      delete _init_dist;
     426      delete _init_pred;
    265427    }
    266428
    … …  
    307469    /// \name Execution Control
    308470    /// The simplest way to execute the algorithm is to call the run()
    309     /// function.
    310     /// \n
     471    /// function.\n
     472    /// If you need to execute the algorithm many times using the same
     473    /// source node, then you may call fullInit() once and start()
     474    /// for each target node.\n
    311475    /// If you only need the flow that is the union of the found
    312     /// arc-disjoint paths, you may call init() and findFlow().
     476    /// arc-disjoint paths, then you may call findFlow() instead of
     477    /// start().
    313478
    314479    /// @{
    … …  
    330495    /// \code
    331496    ///   s.init(s);
    332     ///   s.findFlow(t, k);
    333     ///   s.findPaths();
     497    ///   s.start(t, k);
    334498    /// \endcode
    335499    int run(const Node& s, const Node& t, int k = 2) {
    336500      init(s);
    337       findFlow(t, k);
    338       findPaths();
     501      start(t, k);
    339502      return _path_num;
    340503    }
    … …  
    342505    /// \brief Initialize the algorithm.
    343506    ///
    344     /// This function initializes the algorithm.
     507    /// This function initializes the algorithm with the given source node.
    345508    ///
    346509    /// \param s The source node.
    347510    void init(const Node& s) {
    348       _source = s;
     511      _s = s;
    349512
    350513      // Initialize maps
    … …  
    357520        _local_potential = true;
    358521      }
    359       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    360       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
     522      _full_init = false;
     523    }
     524
     525    /// \brief Initialize the algorithm and perform Dijkstra.
     526    ///
     527    /// This function initializes the algorithm and performs a full
     528    /// Dijkstra search from the given source node. It makes consecutive
     529    /// executions of \ref start() "start(t, k)" faster, since they
     530    /// have to perform %Dijkstra only k-1 times.
     531    ///
     532    /// This initialization is usually worth using instead of \ref init()
     533    /// if the algorithm is executed many times using the same source node.
     534    ///
     535    /// \param s The source node.
     536    void fullInit(const Node& s) {
     537      // Initialize maps
     538      init(s);
     539      if (!_init_dist) {
     540        _init_dist = new PotentialMap(_graph);
     541      }
     542      if (!_init_pred) {
     543        _init_pred = new PredMap(_graph);
     544      }
     545
     546      // Run a full Dijkstra
     547      typename Dijkstra<Digraph, LengthMap>
     548        ::template SetStandardHeap<Heap>
     549        ::template SetDistMap<PotentialMap>
     550        ::template SetPredMap<PredMap>
     551        ::Create dijk(_graph, _length);
     552      dijk.distMap(*_init_dist).predMap(*_init_pred);
     553      dijk.run(s);
     554     
     555      _full_init = true;
     556    }
     557
     558    /// \brief Execute the algorithm.
     559    ///
     560    /// This function executes the algorithm.
     561    ///
     562    /// \param t The target node.
     563    /// \param k The number of paths to be found.
     564    ///
     565    /// \return \c k if there are at least \c k arc-disjoint paths from
     566    /// \c s to \c t in the digraph. Otherwise it returns the number of
     567    /// arc-disjoint paths found.
     568    ///
     569    /// \note Apart from the return value, <tt>s.start(t, k)</tt> is
     570    /// just a shortcut of the following code.
     571    /// \code
     572    ///   s.findFlow(t, k);
     573    ///   s.findPaths();
     574    /// \endcode
     575    int start(const Node& t, int k = 2) {
     576      findFlow(t, k);
     577      findPaths();
     578      return _path_num;
    361579    }
    362580
    … …  
    376594    /// \pre \ref init() must be called before using this function.
    377595    int findFlow(const Node& t, int k = 2) {
    378       _target = t;
    379       _dijkstra =
    380         new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
    381                               _source, _target );
     596      _t = t;
     597      ResidualDijkstra dijkstra(*this);
     598     
     599      // Initialization
     600      for (ArcIt e(_graph); e != INVALID; ++e) {
     601        (*_flow)[e] = 0;
     602      }
     603      if (_full_init) {
     604        for (NodeIt n(_graph); n != INVALID; ++n) {
     605          (*_potential)[n] = (*_init_dist)[n];
     606        }
     607        Node u = _t;
     608        Arc e;
     609        while ((e = (*_init_pred)[u]) != INVALID) {
     610          (*_flow)[e] = 1;
     611          u = _graph.source(e);
     612        }       
     613        _path_num = 1;
     614      } else {
     615        for (NodeIt n(_graph); n != INVALID; ++n) {
     616          (*_potential)[n] = 0;
     617        }
     618        _path_num = 0;
     619      }
    382620
    383621      // Find shortest paths
    384       _path_num = 0;
    385622      while (_path_num < k) {
    386623        // Run Dijkstra
    387         if (!_dijkstra->run()) break;
     624        if (!dijkstra.run(_path_num)) break;
    388625        ++_path_num;
    389626
    390627        // Set the flow along the found shortest path
    391         Node u = _target;
     628        Node u = _t;
    392629        Arc e;
    393630        while ((e = _pred[u]) != INVALID) {
    … …  
    406643    /// \brief Compute the paths from the flow.
    407644    ///
    408     /// This function computes the paths from the found minimum cost flow,
    409     /// which is the union of some arc-disjoint paths.
     645    /// This function computes arc-disjoint paths from the found minimum
     646    /// cost flow, which is the union of them.
    410647    ///
    411648    /// \pre \ref init() and \ref findFlow() must be called before using
    … …  
    415652      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    416653
    417       paths.clear();
    418       paths.resize(_path_num);
     654      _paths.clear();
     655      _paths.resize(_path_num);
    419656      for (int i = 0; i < _path_num; ++i) {
    420         Node n = _source;
    421         while (n != _target) {
     657        Node n = _s;
     658        while (n != _t) {
    422659          OutArcIt e(_graph, n);
    423660          for ( ; res_flow[e] == 0; ++e) ;
    424661          n = _graph.target(e);
    425           paths[i].addBack(e);
     662          _paths[i].addBack(e);
    426663          res_flow[e] = 0;
    427664        }
    … …  
    521758    /// \pre \ref run() or \ref findPaths() must be called before using
    522759    /// this function.
    523     Path path(int i) const {
    524       return paths[i];
     760    const Path& path(int i) const {
     761      return _paths[i];
    525762    }
    526763

  • test/heap_test.cc

    r749 r929  
    3131
    3232#include <lemon/bin_heap.h>
    33 #include <lemon/fourary_heap.h>
    34 #include <lemon/kary_heap.h>
     33#include <lemon/quad_heap.h>
     34#include <lemon/dheap.h>
    3535#include <lemon/fib_heap.h>
    3636#include <lemon/pairing_heap.h>
    3737#include <lemon/radix_heap.h>
    38 #include <lemon/binom_heap.h>
     38#include <lemon/binomial_heap.h>
    3939#include <lemon/bucket_heap.h>
    4040
    … …  
    186186  }
    187187
    188   // FouraryHeap
    189   {
    190     typedef FouraryHeap<Prio, ItemIntMap> IntHeap;
    191     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    192     heapSortTest<IntHeap>();
    193     heapIncreaseTest<IntHeap>();
    194 
    195     typedef FouraryHeap<Prio, IntNodeMap > NodeHeap;
    196     checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    197     dijkstraHeapTest<NodeHeap>(digraph, length, source);
    198   }
    199 
    200   // KaryHeap
    201   {
    202     typedef KaryHeap<Prio, ItemIntMap> IntHeap;
    203     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    204     heapSortTest<IntHeap>();
    205     heapIncreaseTest<IntHeap>();
    206 
    207     typedef KaryHeap<Prio, IntNodeMap > NodeHeap;
     188  // QuadHeap
     189  {
     190    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
     191    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     192    heapSortTest<IntHeap>();
     193    heapIncreaseTest<IntHeap>();
     194
     195    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
     196    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     197    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     198  }
     199
     200  // DHeap
     201  {
     202    typedef DHeap<Prio, ItemIntMap> IntHeap;
     203    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     204    heapSortTest<IntHeap>();
     205    heapIncreaseTest<IntHeap>();
     206
     207    typedef DHeap<Prio, IntNodeMap > NodeHeap;
    208208    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    209209    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    … …  
    246246  }
    247247
    248   // BinomHeap
    249   {
    250     typedef BinomHeap<Prio, ItemIntMap> IntHeap;
    251     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    252     heapSortTest<IntHeap>();
    253     heapIncreaseTest<IntHeap>();
    254 
    255     typedef BinomHeap<Prio, IntNodeMap > NodeHeap;
     248  // BinomialHeap
     249  {
     250    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
     251    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
     252    heapSortTest<IntHeap>();
     253    heapIncreaseTest<IntHeap>();
     254
     255    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
    256256    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    257257    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  • test/suurballe_test.cc

    r670 r932  
    2424#include <lemon/suurballe.h>
    2525#include <lemon/concepts/digraph.h>
     26#include <lemon/concepts/heap.h>
    2627
    2728#include "test_tools.h"
    … …  
    8283  typedef concepts::ReadMap<Arc, VType> LengthMap;
    8384 
    84   typedef Suurballe<Digraph, LengthMap> SuurballeType;
     85  typedef Suurballe<Digraph, LengthMap> ST;
     86  typedef Suurballe<Digraph, LengthMap>
     87    ::SetFlowMap<ST::FlowMap>
     88    ::SetPotentialMap<ST::PotentialMap>
     89    ::SetPath<SimplePath<Digraph> >
     90    ::SetHeap<concepts::Heap<VType, Digraph::NodeMap<int> > >
     91    ::Create SuurballeType;
    8592
    8693  Digraph g;
    … …  
    102109  k = suurb_test.run(n, n, k);
    103110  suurb_test.init(n);
     111  suurb_test.fullInit(n);
     112  suurb_test.start(n);
     113  suurb_test.start(n, k);
    104114  k = suurb_test.findFlow(n);
    105115  k = suurb_test.findFlow(n, k);
    … …  
    196206    run();
    197207
    198   // Find 2 paths
     208  // Check run()
    199209  {
    200210    Suurballe<ListDigraph> suurballe(digraph, length);
     211   
     212    // Find 2 paths
    201213    check(suurballe.run(s, t) == 2, "Wrong number of paths");
    202214    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
    … …  
    208220    for (int i = 0; i < suurballe.pathNum(); ++i)
    209221      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    210   }
    211 
    212   // Find 3 paths
    213   {
    214     Suurballe<ListDigraph> suurballe(digraph, length);
     222   
     223    // Find 3 paths
    215224    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
    216225    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    … …  
    222231    for (int i = 0; i < suurballe.pathNum(); ++i)
    223232      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    224   }
    225 
    226   // Find 5 paths (only 3 can be found)
    227   {
    228     Suurballe<ListDigraph> suurballe(digraph, length);
     233   
     234    // Find 5 paths (only 3 can be found)
    229235    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
    230236    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
    … …  
    237243      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    238244  }
     245 
     246  // Check fullInit() + start()
     247  {
     248    Suurballe<ListDigraph> suurballe(digraph, length);
     249    suurballe.fullInit(s);
     250   
     251    // Find 2 paths
     252    check(suurballe.start(t) == 2, "Wrong number of paths");
     253    check(suurballe.totalLength() == 510, "The flow is not optimal");
     254
     255    // Find 3 paths
     256    check(suurballe.start(t, 3) == 3, "Wrong number of paths");
     257    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     258
     259    // Find 5 paths (only 3 can be found)
     260    check(suurballe.start(t, 5) == 3, "Wrong number of paths");
     261    check(suurballe.totalLength() == 1040, "The flow is not optimal");
     262  }
    239263
    240264  return 0;
Note: See TracChangeset for help on using the changeset viewer.