COIN-OR::LEMON - Graph Library

Changeset 1754:4bf5ceb49023 in lemon-0.x for lemon/johnson.h


Ignore:
Timestamp:
11/02/05 16:27:38 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2283
Message:

Documentation modified

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/johnson.h

    r1747 r1754  
    176176  };
    177177
    178   /// \brief Johnson algorithm class.
     178  /// \brief %Johnson algorithm class.
    179179  ///
    180180  /// \ingroup flowalgs
    181   /// This class provides an efficient implementation of \c Johnson
     181  /// This class provides an efficient implementation of \c %Johnson
    182182  /// algorithm. The edge lengths are passed to the algorithm using a
    183183  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
     
    186186  /// The algorithm solves the shortest path problem for each pairs
    187187  /// of node when the edges can have negative length but the graph should
    188   /// not contain circle with negative sum of length. If we can assume
     188  /// not contain cycles with negative sum of length. If we can assume
    189189  /// that all edge is non-negative in the graph then the dijkstra algorithm
    190190  /// should be used from each node.
     
    378378      }
    379379    };
    380     ///\ref named-templ-param "Named parameter" for setting heap and cross
    381     ///reference type
     380    ///\brief \ref named-templ-param "Named parameter" for setting heap and
     381    ///cross reference type
    382382
    383383    ///\ref named-templ-param "Named parameter" for setting heap and cross
     
    488488  protected:
    489489   
    490     typedef typename BelmannFord<Graph, LengthMap>::
    491     template DefOperationTraits<OperationTraits>::
    492     template DefPredMap<NullMap<Node, Edge> >::
    493     Create BelmannFordType;
    494 
    495     void shiftedRun(const BelmannFordType& belmannford) {
     490    template <typename PotentialMap>
     491    void shiftedRun(const PotentialMap& potential) {
    496492     
    497493      typename Graph::template EdgeMap<Value> shiftlen(*graph);
    498494      for (EdgeIt it(*graph);  it != INVALID; ++it) {
    499495        shiftlen[it] = (*length)[it]
    500           + belmannford.dist(graph->source(it))
    501           - belmannford.dist(graph->target(it));
     496          + potential[graph->source(it)]
     497          - potential[graph->target(it)];
    502498      }
    503499     
     
    513509          if (dijkstra.reached(jt)) {
    514510            _dist->set(it, jt, dijkstra.dist(jt) +
    515                        belmannford.dist(jt) - belmannford.dist(it));
     511                       potential[jt] - potential[it]);
    516512            _pred->set(it, jt, dijkstra.pred(jt));
    517513          } else {
     
    551547    void start() {
    552548
     549      typedef typename BelmannFord<Graph, LengthMap>::
     550      template DefOperationTraits<OperationTraits>::
     551      template DefPredMap<NullMap<Node, Edge> >::
     552      Create BelmannFordType;
     553     
    553554      BelmannFordType belmannford(*graph, *length);
    554555
     
    560561      belmannford.start();
    561562
    562       shiftedRun(belmannford);
    563     }
    564 
    565     /// \brief Executes the algorithm and checks the negatvie circles.
     563      shiftedRun(belmannford.distMap());
     564    }
     565
     566    /// \brief Executes the algorithm and checks the negatvie cycles.
    566567    ///
    567568    /// This method runs the %Johnson algorithm in order to compute
    568569    /// the shortest path to each node pairs. If the graph contains
    569     /// negative circle it gives back false. The algorithm
     570    /// negative cycle it gives back false. The algorithm
    570571    /// computes
    571572    /// - The shortest path tree for each node.
    572573    /// - The distance between each node pairs.
    573574    bool checkedStart() {
     575     
     576      typedef typename BelmannFord<Graph, LengthMap>::
     577      template DefOperationTraits<OperationTraits>::
     578      template DefPredMap<NullMap<Node, Edge> >::
     579      Create BelmannFordType;
    574580
    575581      BelmannFordType belmannford(*graph, *length);
     
    582588      if (!belmannford.checkedStart()) return false;
    583589
    584       shiftedRun(belmannford);
     590      shiftedRun(belmannford.distMap());
    585591      return true;
    586592    }
Note: See TracChangeset for help on using the changeset viewer.