COIN-OR::LEMON - Graph Library

Changeset 927:9a7e4e606f83 in lemon


Ignore:
Timestamp:
10/16/09 02:32:30 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add a fullInit() function to Suurballe (#181, #323)
to provide faster handling of multiple targets.
A start() function is also added, just for the sake of
convenience.

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/suurballe.h

    r926 r927  
    3030#include <lemon/path.h>
    3131#include <lemon/list_graph.h>
     32#include <lemon/dijkstra.h>
    3233#include <lemon/maps.h>
    3334
     
    9899  private:
    99100
     101    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
     102    typedef BinHeap<Length, HeapCrossRef> Heap;
     103
    100104    // ResidualDijkstra is a special implementation of the
    101105    // Dijkstra algorithm for finding shortest paths in the
     
    105109    class ResidualDijkstra
    106110    {
    107       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    108       typedef BinHeap<Length, HeapCrossRef> Heap;
    109 
    110111    private:
    111112
     
    279280    // The pred arc map
    280281    PredMap _pred;
     282   
     283    // Data for full init
     284    PotentialMap *_init_dist;
     285    PredMap *_init_pred;
     286    bool _full_init;
    281287
    282288  public:
     
    291297               const LengthMap &length ) :
    292298      _graph(graph), _length(length), _flow(0), _local_flow(false),
    293       _potential(0), _local_potential(false), _pred(graph)
     299      _potential(0), _local_potential(false), _pred(graph),
     300      _init_dist(0), _init_pred(0)
    294301    {}
    295302
     
    298305      if (_local_flow) delete _flow;
    299306      if (_local_potential) delete _potential;
     307      delete _init_dist;
     308      delete _init_pred;
    300309    }
    301310
     
    342351    /// \name Execution Control
    343352    /// The simplest way to execute the algorithm is to call the run()
    344     /// function.
    345     /// \n
     353    /// function.\n
     354    /// If you need to execute the algorithm many times using the same
     355    /// source node, then you may call fullInit() once and start()
     356    /// for each target node.\n
    346357    /// If you only need the flow that is the union of the found
    347     /// arc-disjoint paths, you may call init() and findFlow().
     358    /// arc-disjoint paths, then you may call findFlow() instead of
     359    /// start().
    348360
    349361    /// @{
     
    365377    /// \code
    366378    ///   s.init(s);
    367     ///   s.findFlow(t, k);
    368     ///   s.findPaths();
     379    ///   s.start(t, k);
    369380    /// \endcode
    370381    int run(const Node& s, const Node& t, int k = 2) {
    371382      init(s);
    372       findFlow(t, k);
    373       findPaths();
     383      start(t, k);
    374384      return _path_num;
    375385    }
     
    377387    /// \brief Initialize the algorithm.
    378388    ///
    379     /// This function initializes the algorithm.
     389    /// This function initializes the algorithm with the given source node.
    380390    ///
    381391    /// \param s The source node.
     
    392402        _local_potential = true;
    393403      }
    394       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
    395       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
     404      _full_init = false;
     405    }
     406
     407    /// \brief Initialize the algorithm and perform Dijkstra.
     408    ///
     409    /// This function initializes the algorithm and performs a full
     410    /// Dijkstra search from the given source node. It makes consecutive
     411    /// executions of \ref start() "start(t, k)" faster, since they
     412    /// have to perform %Dijkstra only k-1 times.
     413    ///
     414    /// This initialization is usually worth using instead of \ref init()
     415    /// if the algorithm is executed many times using the same source node.
     416    ///
     417    /// \param s The source node.
     418    void fullInit(const Node& s) {
     419      // Initialize maps
     420      init(s);
     421      if (!_init_dist) {
     422        _init_dist = new PotentialMap(_graph);
     423      }
     424      if (!_init_pred) {
     425        _init_pred = new PredMap(_graph);
     426      }
     427
     428      // Run a full Dijkstra
     429      typename Dijkstra<Digraph, LengthMap>
     430        ::template SetStandardHeap<Heap>
     431        ::template SetDistMap<PotentialMap>
     432        ::template SetPredMap<PredMap>
     433        ::Create dijk(_graph, _length);
     434      dijk.distMap(*_init_dist).predMap(*_init_pred);
     435      dijk.run(s);
     436     
     437      _full_init = true;
     438    }
     439
     440    /// \brief Execute the algorithm.
     441    ///
     442    /// This function executes the algorithm.
     443    ///
     444    /// \param t The target node.
     445    /// \param k The number of paths to be found.
     446    ///
     447    /// \return \c k if there are at least \c k arc-disjoint paths from
     448    /// \c s to \c t in the digraph. Otherwise it returns the number of
     449    /// arc-disjoint paths found.
     450    ///
     451    /// \note Apart from the return value, <tt>s.start(t, k)</tt> is
     452    /// just a shortcut of the following code.
     453    /// \code
     454    ///   s.findFlow(t, k);
     455    ///   s.findPaths();
     456    /// \endcode
     457    int start(const Node& t, int k = 2) {
     458      findFlow(t, k);
     459      findPaths();
     460      return _path_num;
    396461    }
    397462
     
    413478      _t = t;
    414479      ResidualDijkstra dijkstra(*this);
     480     
     481      // Initialization
     482      for (ArcIt e(_graph); e != INVALID; ++e) {
     483        (*_flow)[e] = 0;
     484      }
     485      if (_full_init) {
     486        for (NodeIt n(_graph); n != INVALID; ++n) {
     487          (*_potential)[n] = (*_init_dist)[n];
     488        }
     489        Node u = _t;
     490        Arc e;
     491        while ((e = (*_init_pred)[u]) != INVALID) {
     492          (*_flow)[e] = 1;
     493          u = _graph.source(e);
     494        }       
     495        _path_num = 1;
     496      } else {
     497        for (NodeIt n(_graph); n != INVALID; ++n) {
     498          (*_potential)[n] = 0;
     499        }
     500        _path_num = 0;
     501      }
    415502
    416503      // Find shortest paths
    417       _path_num = 0;
    418504      while (_path_num < k) {
    419505        // Run Dijkstra
  • test/suurballe_test.cc

    r670 r927  
    102102  k = suurb_test.run(n, n, k);
    103103  suurb_test.init(n);
     104  suurb_test.fullInit(n);
     105  suurb_test.start(n);
     106  suurb_test.start(n, k);
    104107  k = suurb_test.findFlow(n);
    105108  k = suurb_test.findFlow(n, k);
Note: See TracChangeset for help on using the changeset viewer.