# Changeset 1754:4bf5ceb49023 in lemon-0.x for lemon

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

Documentation modified

Location:
lemon
Files:
3 edited

Unmodified
Removed
• ## lemon/belmann_ford.h

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

 r1741 }; /// \brief FloydWarshall algorithm class. /// \brief %FloydWarshall algorithm class. /// /// \ingroup flowalgs /// This class provides an efficient implementation of \c FloydWarshall /// This class provides an efficient implementation of \c Floyd-Warshall /// algorithm. The edge lengths are passed to the algorithm using a /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any /// The algorithm solves the shortest path problem for each pairs /// of node when the edges can have negative length but the graph should /// not contain circle with negative sum of length. If we can assume /// not contain cycles with negative sum of length. If we can assume /// that all edge is non-negative in the graph then the dijkstra algorithm /// should be used from each node rather and if the graph is sparse and /// there are negative circles then the johson algorithm. /// there are negative circles then the johnson algorithm. /// /// The complexity of this algorithm is O(n^3 + e). } /// \brief Executes the algorithm and checks the negative circles. /// \brief Executes the algorithm and checks the negative cycles. /// /// This method runs the %FloydWarshall algorithm in order to compute /// the shortest path to each node pairs. If there is a negative circle /// the shortest path to each node pairs. If there is a negative cycle /// in the graph it gives back false. /// The algorithm computes
• ## lemon/johnson.h

 r1747 }; /// \brief Johnson algorithm class. /// \brief %Johnson algorithm class. /// /// \ingroup flowalgs /// This class provides an efficient implementation of \c Johnson /// This class provides an efficient implementation of \c %Johnson /// algorithm. The edge lengths are passed to the algorithm using a /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any /// The algorithm solves the shortest path problem for each pairs /// of node when the edges can have negative length but the graph should /// not contain circle with negative sum of length. If we can assume /// not contain cycles with negative sum of length. If we can assume /// that all edge is non-negative in the graph then the dijkstra algorithm /// should be used from each node. } }; ///\ref named-templ-param "Named parameter" for setting heap and cross ///reference type ///\brief \ref named-templ-param "Named parameter" for setting heap and ///cross reference type ///\ref named-templ-param "Named parameter" for setting heap and cross protected: typedef typename BelmannFord:: template DefOperationTraits:: template DefPredMap >:: Create BelmannFordType; void shiftedRun(const BelmannFordType& belmannford) { template void shiftedRun(const PotentialMap& potential) { typename Graph::template EdgeMap shiftlen(*graph); for (EdgeIt it(*graph);  it != INVALID; ++it) { shiftlen[it] = (*length)[it] + belmannford.dist(graph->source(it)) - belmannford.dist(graph->target(it)); + potential[graph->source(it)] - potential[graph->target(it)]; } if (dijkstra.reached(jt)) { _dist->set(it, jt, dijkstra.dist(jt) + belmannford.dist(jt) - belmannford.dist(it)); potential[jt] - potential[it]); _pred->set(it, jt, dijkstra.pred(jt)); } else { void start() { typedef typename BelmannFord:: template DefOperationTraits:: template DefPredMap >:: Create BelmannFordType; BelmannFordType belmannford(*graph, *length); belmannford.start(); shiftedRun(belmannford); } /// \brief Executes the algorithm and checks the negatvie circles. shiftedRun(belmannford.distMap()); } /// \brief Executes the algorithm and checks the negatvie cycles. /// /// This method runs the %Johnson algorithm in order to compute /// the shortest path to each node pairs. If the graph contains /// negative circle it gives back false. The algorithm /// negative cycle it gives back false. The algorithm /// computes /// - The shortest path tree for each node. /// - The distance between each node pairs. bool checkedStart() { typedef typename BelmannFord:: template DefOperationTraits:: template DefPredMap >:: Create BelmannFordType; BelmannFordType belmannford(*graph, *length); if (!belmannford.checkedStart()) return false; shiftedRun(belmannford); shiftedRun(belmannford.distMap()); return true; }
Note: See TracChangeset for help on using the changeset viewer.