COIN-OR::LEMON - Graph Library

Changeset 1781:dca4c8a54e0a in lemon-0.x for lemon


Ignore:
Timestamp:
11/09/05 13:07:00 (18 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2316
Message:

Path length limit for belmann_ford.h

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/belmann_ford.h

    r1765 r1781  
    204204    typedef typename Graph::NodeIt NodeIt;
    205205    typedef typename Graph::Edge Edge;
    206     typedef typename Graph::EdgeIt EdgeIt;
     206    typedef typename Graph::OutEdgeIt OutEdgeIt;
    207207   
    208208    /// \brief The type of the length of the edges.
     
    231231    bool local_dist;
    232232
     233    typedef typename Graph::template NodeMap<bool> MaskMap;
     234    MaskMap *_mask;
     235
     236    std::vector<Node> _process;
     237
    233238    /// Creates the maps if necessary.
    234239    void create_maps() {
     
    241246        _dist = Traits::createDistMap(*graph);
    242247      }
     248      _mask = new MaskMap(*graph, false);
    243249    }
    244250   
     
    325331      if(local_pred) delete _pred;
    326332      if(local_dist) delete _dist;
     333      delete _mask;
    327334    }
    328335
     
    389396        _dist->set(it, value);
    390397      }
     398      _process.clear();
     399      if (OperationTraits::less(value, OperationTraits::infinity())) {
     400        for (NodeIt it(*graph); it != INVALID; ++it) {
     401          _process.push_back(it);
     402        }
     403      }
    391404    }
    392405   
     
    397410    void addSource(Node source, Value dst = OperationTraits::zero()) {
    398411      _dist->set(source, dst);
     412      if (!(*_mask)[source]) {
     413        _process.push_back(source);
     414        _mask->set(source, true);
     415      }
     416    }
     417
     418    /// \brief Executes one round from the belmann ford algorithm.
     419    ///
     420    /// If the algoritm calculated the distances in the previous round
     421    /// strictly for all at most k length pathes then it will calculate the
     422    /// distances strictly for all at most k + 1 length pathes. With k
     423    /// iteration this function calculates the at most k length pathes.
     424    bool processNextRound() {
     425      for (int i = 0; i < (int)_process.size(); ++i) {
     426        _mask->set(_process[i], false);
     427      }
     428      std::vector<Node> nextProcess;
     429      std::vector<Value> values(_process.size());
     430      for (int i = 0; i < (int)_process.size(); ++i) {
     431        values[i] = _dist[_process[i]];
     432      }
     433      for (int i = 0; i < (int)_process.size(); ++i) {
     434        for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
     435          Node target = graph->target(it);
     436          Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
     437          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     438            _pred->set(target, it);
     439            _dist->set(target, relaxed);
     440            if (!(*_mask)[target]) {
     441              _mask->set(target, true);
     442              nextProcess.push_back(target);
     443            }
     444          }       
     445        }
     446      }
     447      _process.swap(nextProcess);
     448      return _process.empty();
     449    }
     450
     451    /// \brief Executes one weak round from the belmann ford algorithm.
     452    ///
     453    /// If the algorithm calculated the distances in the
     454    /// previous round at least for all at most k length pathes then it will
     455    /// calculate the distances at least for all at most k + 1 length pathes.
     456    /// This function does not make possible to calculate strictly the
     457    /// at most k length minimal pathes, this way it called just weak round.
     458    bool processNextWeakRound() {
     459      for (int i = 0; i < (int)_process.size(); ++i) {
     460        _mask->set(_process[i], false);
     461      }
     462      std::vector<Node> nextProcess;
     463      for (int i = 0; i < (int)_process.size(); ++i) {
     464        for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
     465          Node target = graph->target(it);
     466          Value relaxed =
     467            OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
     468          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     469            _pred->set(target, it);
     470            _dist->set(target, relaxed);
     471            if (!(*_mask)[target]) {
     472              _mask->set(target, true);
     473              nextProcess.push_back(target);
     474            }
     475          }       
     476        }
     477      }
     478      for (int i = 0; i < (int)nextProcess.size(); ++i) {
     479        _mask->set(nextProcess[i], false);
     480      }
     481      _process.swap(nextProcess);
     482      return _process.empty();
    399483    }
    400484
     
    412496      int num = countNodes(*graph) - 1;
    413497      for (int i = 0; i < num; ++i) {
    414         bool done = true;
    415         for (EdgeIt it(*graph); it != INVALID; ++it) {
    416           Node source = graph->source(it);
    417           Node target = graph->target(it);
    418           Value relaxed =
    419             OperationTraits::plus((*_dist)[source], (*length)[it]);
    420           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    421             _pred->set(target, it);
    422             _dist->set(target, relaxed);
    423             done = false;
    424           }
    425         }
    426         if (done) return;
     498        if (processNextWeakRound()) break;
    427499      }
    428500    }
     
    442514      int num = countNodes(*graph);
    443515      for (int i = 0; i < num; ++i) {
    444         bool done = true;
    445         for (EdgeIt it(*graph); it != INVALID; ++it) {
    446           Node source = graph->source(it);
    447           Node target = graph->target(it);
    448           Value relaxed =
    449             OperationTraits::plus((*_dist)[source], (*length)[it]);
    450           if (OperationTraits::less(relaxed, (*_dist)[target])) {
    451             _pred->set(target, it);
    452             _dist->set(target, relaxed);
    453             done = false;
    454           }
    455         }
    456         if (done) return true;
     516        if (processNextWeakRound()) return true;
    457517      }
    458518      return false;
     519    }
     520
     521    /// \brief Executes the algorithm with path length limit.
     522    ///
     523    /// \pre init() must be called and at least one node should be added
     524    /// with addSource() before using this function.
     525    ///
     526    /// This method runs the %BelmannFord algorithm from the root node(s)
     527    /// in order to compute the shortest path with at most \c length edge
     528    /// long pathes to each node. The algorithm computes
     529    /// - The shortest path tree.
     530    /// - The limited distance of each node from the root(s).
     531    void limitedStart(int length) {
     532      for (int i = 0; i < length; ++i) {
     533        if (processNextRound()) break;
     534      }
    459535    }
    460536   
Note: See TracChangeset for help on using the changeset viewer.