COIN-OR::LEMON - Graph Library

Ignore:
Files:
3 added
3 deleted
4 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r933 r888  
    6161        lemon/bfs.h \
    6262        lemon/bin_heap.h \
    63         lemon/binomial_heap.h \
     63        lemon/binom_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 \
    7978        lemon/dijkstra.h \
    8079        lemon/dim2.h \
     
    8584        lemon/euler.h \
    8685        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 \
    9697        lemon/kruskal.h \
    9798        lemon/hao_orlin.h \
     
    112113        lemon/planarity.h \
    113114        lemon/preflow.h \
    114         lemon/quad_heap.h \
    115115        lemon/radix_heap.h \
    116116        lemon/radix_sort.h \
  • lemon/suurballe.h

    r931 r670  
    3030#include <lemon/path.h>
    3131#include <lemon/list_graph.h>
    32 #include <lemon/dijkstra.h>
    3332#include <lemon/maps.h>
    3433
    3534namespace 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   };
    7935
    8036  /// \addtogroup shortest_path
     
    9147  /// "minimum cost flow problem". This implementation is actually an
    9248  /// efficient specialized version of the \ref CapacityScaling
    93   /// "successive shortest path" algorithm directly for this problem.
     49  /// "Successive Shortest Path" algorithm directly for this problem.
    9450  /// Therefore this class provides query functions for flow values and
    9551  /// node potentials (the dual solution) just like the minimum cost flow
     
    10056  /// The default value is <tt>GR::ArcMap<int></tt>.
    10157  ///
    102   /// \warning Length values should be \e non-negative.
     58  /// \warning Length values should be \e non-negative \e integers.
    10359  ///
    104   /// \note For finding \e node-disjoint paths, this algorithm can be used
     60  /// \note For finding node-disjoint paths this algorithm can be used
    10561  /// along with the \ref SplitNodes adaptor.
    10662#ifdef DOXYGEN
    107   template <typename GR, typename LEN, typename TR>
     63  template <typename GR, typename LEN>
    10864#else
    10965  template < typename GR,
    110              typename LEN = typename GR::template ArcMap<int>,
    111              typename TR = SuurballeDefaultTraits<GR, LEN> >
     66             typename LEN = typename GR::template ArcMap<int> >
    11267#endif
    11368  class Suurballe
     
    12075  public:
    12176
    122     /// The type of the digraph.
    123     typedef typename TR::Digraph Digraph;
     77    /// The type of the digraph the algorithm runs on.
     78    typedef GR Digraph;
    12479    /// The type of the length map.
    125     typedef typename TR::LengthMap LengthMap;
     80    typedef LEN LengthMap;
    12681    /// The type of the lengths.
    127     typedef typename TR::Length Length;
    128 
     82    typedef typename LengthMap::Value Length;
     83#ifdef DOXYGEN
    12984    /// The type of the flow map.
    130     typedef typename TR::FlowMap FlowMap;
     85    typedef GR::ArcMap<int> FlowMap;
    13186    /// The type of the potential map.
    132     typedef typename TR::PotentialMap PotentialMap;
     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
    13395    /// The type of the path structures.
    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;
     96    typedef SimplePath<GR> Path;
    14297
    14398  private:
     
    150105    class ResidualDijkstra
    151106    {
     107      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
     108      typedef BinHeap<Length, HeapCrossRef> Heap;
     109
    152110    private:
    153111
     112      // The digraph the algorithm runs on
    154113      const Digraph &_graph;
     114
     115      // The main maps
     116      const FlowMap &_flow;
    155117      const LengthMap &_length;
    156       const FlowMap &_flow;
    157       PotentialMap &_pi;
     118      PotentialMap &_potential;
     119
     120      // The distance map
     121      PotentialMap _dist;
     122      // The pred arc map
    158123      PredMap &_pred;
     124      // The processed (i.e. permanently labeled) nodes
     125      std::vector<Node> _proc_nodes;
     126
    159127      Node _s;
    160128      Node _t;
    161      
    162       PotentialMap _dist;
    163       std::vector<Node> _proc_nodes;
    164129
    165130    public:
    166131
    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() {
     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() {
    184145        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
    185146        Heap heap(heap_cross_ref);
     
    191152        while (!heap.empty() && heap.top() != _t) {
    192153          Node u = heap.top(), v;
    193           Length d = heap.prio(), dn;
     154          Length d = heap.prio() + _potential[u], nd;
    194155          _dist[u] = heap.prio();
     156          heap.pop();
    195157          _proc_nodes.push_back(u);
    196           heap.pop();
    197158
    198159          // Traverse outgoing arcs
    199160          for (OutArcIt e(_graph, u); e != INVALID; ++e) {
    200             v = _graph.target(e);
    201             switch(heap.state(v)) {
     161            if (_flow[e] == 0) {
     162              v = _graph.target(e);
     163              switch(heap.state(v)) {
    202164              case Heap::PRE_HEAP:
    203                 heap.push(v, d + _length[e]);
     165                heap.push(v, d + _length[e] - _potential[v]);
    204166                _pred[v] = e;
    205167                break;
    206168              case Heap::IN_HEAP:
    207                 dn = d + _length[e];
    208                 if (dn < heap[v]) {
    209                   heap.decrease(v, dn);
     169                nd = d + _length[e] - _potential[v];
     170                if (nd < heap[v]) {
     171                  heap.decrease(v, nd);
    210172                  _pred[v] = e;
    211173                }
     
    213175              case Heap::POST_HEAP:
    214176                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();
    240           _proc_nodes.push_back(u);
    241           heap.pop();
    242 
    243           // Traverse outgoing arcs
    244           for (OutArcIt e(_graph, u); e != INVALID; ++e) {
    245             if (_flow[e] == 0) {
    246               v = _graph.target(e);
    247               switch(heap.state(v)) {
    248                 case Heap::PRE_HEAP:
    249                   heap.push(v, d + _length[e] - _pi[v]);
    250                   _pred[v] = e;
    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;
    261177              }
    262178            }
     
    268184              v = _graph.source(e);
    269185              switch(heap.state(v)) {
    270                 case Heap::PRE_HEAP:
    271                   heap.push(v, d - _length[e] - _pi[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);
    272194                  _pred[v] = e;
    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;
     195                }
     196                break;
     197              case Heap::POST_HEAP:
     198                break;
    283199              }
    284200            }
     
    290206        Length t_dist = heap.prio();
    291207        for (int i = 0; i < int(_proc_nodes.size()); ++i)
    292           _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
     208          _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
    293209        return true;
    294210      }
    295211
    296212    }; //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     /// @}
    374213
    375214  private:
     
    388227
    389228    // The source node
    390     Node _s;
     229    Node _source;
    391230    // The target node
    392     Node _t;
     231    Node _target;
    393232
    394233    // Container to store the found paths
    395     std::vector<Path> _paths;
     234    std::vector< SimplePath<Digraph> > paths;
    396235    int _path_num;
    397236
    398237    // The pred arc map
    399238    PredMap _pred;
    400    
    401     // Data for full init
    402     PotentialMap *_init_dist;
    403     PredMap *_init_pred;
    404     bool _full_init;
     239    // Implementation of the Dijkstra algorithm for finding augmenting
     240    // shortest paths in the residual network
     241    ResidualDijkstra *_dijkstra;
    405242
    406243  public:
     
    415252               const LengthMap &length ) :
    416253      _graph(graph), _length(length), _flow(0), _local_flow(false),
    417       _potential(0), _local_potential(false), _pred(graph),
    418       _init_dist(0), _init_pred(0)
    419     {}
     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    }
    420259
    421260    /// Destructor.
     
    423262      if (_local_flow) delete _flow;
    424263      if (_local_potential) delete _potential;
    425       delete _init_dist;
    426       delete _init_pred;
     264      delete _dijkstra;
    427265    }
    428266
     
    469307    /// \name Execution Control
    470308    /// The simplest way to execute the algorithm is to call the run()
    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
     309    /// function.
     310    /// \n
    475311    /// If you only need the flow that is the union of the found
    476     /// arc-disjoint paths, then you may call findFlow() instead of
    477     /// start().
     312    /// arc-disjoint paths, you may call init() and findFlow().
    478313
    479314    /// @{
     
    495330    /// \code
    496331    ///   s.init(s);
    497     ///   s.start(t, k);
     332    ///   s.findFlow(t, k);
     333    ///   s.findPaths();
    498334    /// \endcode
    499335    int run(const Node& s, const Node& t, int k = 2) {
    500336      init(s);
    501       start(t, k);
     337      findFlow(t, k);
     338      findPaths();
    502339      return _path_num;
    503340    }
     
    505342    /// \brief Initialize the algorithm.
    506343    ///
    507     /// This function initializes the algorithm with the given source node.
     344    /// This function initializes the algorithm.
    508345    ///
    509346    /// \param s The source node.
    510347    void init(const Node& s) {
    511       _s = s;
     348      _source = s;
    512349
    513350      // Initialize maps
     
    520357        _local_potential = true;
    521358      }
    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;
     359      for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
     360      for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
    579361    }
    580362
     
    594376    /// \pre \ref init() must be called before using this function.
    595377    int findFlow(const Node& t, int k = 2) {
    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       }
     378      _target = t;
     379      _dijkstra =
     380        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
     381                              _source, _target );
    620382
    621383      // Find shortest paths
     384      _path_num = 0;
    622385      while (_path_num < k) {
    623386        // Run Dijkstra
    624         if (!dijkstra.run(_path_num)) break;
     387        if (!_dijkstra->run()) break;
    625388        ++_path_num;
    626389
    627390        // Set the flow along the found shortest path
    628         Node u = _t;
     391        Node u = _target;
    629392        Arc e;
    630393        while ((e = _pred[u]) != INVALID) {
     
    643406    /// \brief Compute the paths from the flow.
    644407    ///
    645     /// This function computes arc-disjoint paths from the found minimum
    646     /// cost flow, which is the union of them.
     408    /// This function computes the paths from the found minimum cost flow,
     409    /// which is the union of some arc-disjoint paths.
    647410    ///
    648411    /// \pre \ref init() and \ref findFlow() must be called before using
     
    652415      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
    653416
    654       _paths.clear();
    655       _paths.resize(_path_num);
     417      paths.clear();
     418      paths.resize(_path_num);
    656419      for (int i = 0; i < _path_num; ++i) {
    657         Node n = _s;
    658         while (n != _t) {
     420        Node n = _source;
     421        while (n != _target) {
    659422          OutArcIt e(_graph, n);
    660423          for ( ; res_flow[e] == 0; ++e) ;
    661424          n = _graph.target(e);
    662           _paths[i].addBack(e);
     425          paths[i].addBack(e);
    663426          res_flow[e] = 0;
    664427        }
     
    758521    /// \pre \ref run() or \ref findPaths() must be called before using
    759522    /// this function.
    760     const Path& path(int i) const {
    761       return _paths[i];
     523    Path path(int i) const {
     524      return paths[i];
    762525    }
    763526
  • test/heap_test.cc

    r929 r749  
    3131
    3232#include <lemon/bin_heap.h>
    33 #include <lemon/quad_heap.h>
    34 #include <lemon/dheap.h>
     33#include <lemon/fourary_heap.h>
     34#include <lemon/kary_heap.h>
    3535#include <lemon/fib_heap.h>
    3636#include <lemon/pairing_heap.h>
    3737#include <lemon/radix_heap.h>
    38 #include <lemon/binomial_heap.h>
     38#include <lemon/binom_heap.h>
    3939#include <lemon/bucket_heap.h>
    4040
     
    186186  }
    187187
    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;
     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;
    208208    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    209209    dijkstraHeapTest<NodeHeap>(digraph, length, source);
     
    246246  }
    247247
    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;
     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;
    256256    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
    257257    dijkstraHeapTest<NodeHeap>(digraph, length, source);
  • test/suurballe_test.cc

    r932 r670  
    2424#include <lemon/suurballe.h>
    2525#include <lemon/concepts/digraph.h>
    26 #include <lemon/concepts/heap.h>
    2726
    2827#include "test_tools.h"
     
    8382  typedef concepts::ReadMap<Arc, VType> LengthMap;
    8483 
    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;
     84  typedef Suurballe<Digraph, LengthMap> SuurballeType;
    9285
    9386  Digraph g;
     
    109102  k = suurb_test.run(n, n, k);
    110103  suurb_test.init(n);
    111   suurb_test.fullInit(n);
    112   suurb_test.start(n);
    113   suurb_test.start(n, k);
    114104  k = suurb_test.findFlow(n);
    115105  k = suurb_test.findFlow(n, k);
     
    206196    run();
    207197
    208   // Check run()
     198  // Find 2 paths
    209199  {
    210200    Suurballe<ListDigraph> suurballe(digraph, length);
    211    
    212     // Find 2 paths
    213201    check(suurballe.run(s, t) == 2, "Wrong number of paths");
    214202    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
     
    220208    for (int i = 0; i < suurballe.pathNum(); ++i)
    221209      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    222    
    223     // Find 3 paths
     210  }
     211
     212  // Find 3 paths
     213  {
     214    Suurballe<ListDigraph> suurballe(digraph, length);
    224215    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
    225216    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    231222    for (int i = 0; i < suurballe.pathNum(); ++i)
    232223      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    233    
    234     // Find 5 paths (only 3 can be found)
     224  }
     225
     226  // Find 5 paths (only 3 can be found)
     227  {
     228    Suurballe<ListDigraph> suurballe(digraph, length);
    235229    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
    236230    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
     
    243237      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
    244238  }
    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   }
    263239
    264240  return 0;
Note: See TracChangeset for help on using the changeset viewer.