COIN-OR::LEMON - Graph Library

Changeset 1754:4bf5ceb49023 in lemon-0.x


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

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/belmann_ford.h

    r1741 r1754  
    142142  };
    143143 
    144   /// \brief BelmannFord algorithm class.
     144  /// \brief %BelmannFord algorithm class.
    145145  ///
    146146  /// \ingroup flowalgs
     
    152152  /// The Belmann-Ford algorithm solves the shortest path from one node
    153153  /// problem when the edges can have negative length but the graph should
    154   /// not contain circle with negative sum of length. If we can assume
     154  /// not contain cycles with negative sum of length. If we can assume
    155155  /// that all edge is non-negative in the graph then the dijkstra algorithm
    156156  /// should be used rather.
     
    429429    }
    430430
    431     /// \brief Executes the algorithm and checks the negative circles.
     431    /// \brief Executes the algorithm and checks the negative cycles.
    432432    ///
    433433    /// \pre init() must be called and at least one node should be added
    434434    /// with addSource() before using this function. If there is
    435     /// a negative circle in the graph it gives back false.
     435    /// a negative cycles in the graph it gives back false.
    436436    ///
    437437    /// This method runs the %BelmannFord algorithm from the root node(s)
  • lemon/floyd_warshall.h

    r1741 r1754  
    143143  };
    144144 
    145   /// \brief FloydWarshall algorithm class.
     145  /// \brief %FloydWarshall algorithm class.
    146146  ///
    147147  /// \ingroup flowalgs
    148   /// This class provides an efficient implementation of \c FloydWarshall
     148  /// This class provides an efficient implementation of \c Floyd-Warshall
    149149  /// algorithm. The edge lengths are passed to the algorithm using a
    150150  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
     
    153153  /// The algorithm solves the shortest path problem for each pairs
    154154  /// of node when the edges can have negative length but the graph should
    155   /// not contain circle with negative sum of length. If we can assume
     155  /// not contain cycles with negative sum of length. If we can assume
    156156  /// that all edge is non-negative in the graph then the dijkstra algorithm
    157157  /// should be used from each node rather and if the graph is sparse and
    158   /// there are negative circles then the johson algorithm.
     158  /// there are negative circles then the johnson algorithm.
    159159  ///
    160160  /// The complexity of this algorithm is O(n^3 + e).
     
    429429    }
    430430
    431     /// \brief Executes the algorithm and checks the negative circles.
     431    /// \brief Executes the algorithm and checks the negative cycles.
    432432    ///
    433433    /// This method runs the %FloydWarshall algorithm in order to compute
    434     /// the shortest path to each node pairs. If there is a negative circle
     434    /// the shortest path to each node pairs. If there is a negative cycle
    435435    /// in the graph it gives back false.
    436436    /// The algorithm computes
  • 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.