COIN-OR::LEMON - Graph Library

Changeset 927:9a7e4e606f83 in lemon


Ignore:
Timestamp:
10/16/09 02:32:30 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
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.