Changeset 2437:02c7076bf894 in lemon-0.x

Ignore:
Timestamp:
05/07/07 10:47:38 (12 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3274
Message:

Small improvements in MinMeanCycle? class.

Patch from Peter Kovacs

File:
1 edited

Unmodified
Removed
• lemon/min_mean_cycle.h

 r2413 /// \ingroup min_cost_flow /// /// \file /// \file /// \brief Karp algorithm for finding a minimum mean cycle. /// \author Peter Kovacs #ifdef DOXYGEN template #else template > #endif class MinMeanCycle { typedef Path Path; typedef std::vector NodeVector; typedef typename NodeVector::iterator NodeVectorIt; protected: /// \brief Node map for storing path data. /// /// /// Node map for storing path data of all nodes in the current /// component. dmap[v][k] is the length of a shortest directed walk /// component. dmap[v][k] is the length of a shortest directed walk /// to node v from the starting node containing exactly k edges. PathDataNodeMap dmap; /// \brief The directed graph the algorithm runs on. const Graph& graph; const Graph &graph; /// \brief The length of the edges. const LengthMap& length; const LengthMap &length; /// \brief The total length of the found cycle. Length cycle_length; /// \brief The number of edges in the found cycle. int cycle_size; /// \brief A node for obtaining a minimum mean cycle. /// \brief A node for obtaining a minimum mean cycle. Node cycle_node; /// \brief The found cycle. Path *cycle_path; /// \brief The algorithm uses local \ref lemon::Path "Path" /// \brief The algorithm uses local \ref lemon::Path "Path" /// structure to store the found cycle. bool local_path; /// \brief Node map for identifying strongly connected components. IntNodeMap comp; /// \brief The processed nodes in the last round. NodeVector process; public : /// \param _graph The directed graph the algorithm runs on. /// \param _length The length (cost) of the edges. MinMeanCycle( const Graph& _graph, const LengthMap& _length ) : MinMeanCycle( const Graph &_graph, const LengthMap &_length ) : graph(_graph), length(_length), dmap(_graph), comp(_graph), cycle_length(0), cycle_size(-1), cycle_node(INVALID), /// \brief The destructor of the class. ~MinMeanCycle() { ~MinMeanCycle() { if (local_path) delete cycle_path; } // Creating vectors for all nodes int n = nodes.size(); for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) { dmap[*vi].resize(n + 1); } } /// \brief Processes all rounds of computing required path data for for (int i = 0; i < nodes.size(); ++i) { dmap[nodes[i]].resize(n + 1); } } /// \brief Processes all rounds of computing required path data for /// the current component. void processRounds() { process.push_back(v); } // Processing other rounds // Processing other rounds int n = nodes.size(), k; for (k = 2; k <= n && process.size() < n; ++k) { for (k = 2; k <= n && process.size() < n; ++k) processNextBuildRound(k); } for ( ; k <= n; ++k) { for ( ; k <= n; ++k) processNextFullRound(k); } } } /// \brief Processes one round of computing required path data and /// rebuilds \ref process vector. void processNextBuildRound(int k) { NodeVector next; for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) { for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) { for (int i = 0; i < process.size(); ++i) { for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) { Node v = graph.target(e); if (comp[v] != comp_cnt) continue; if (!dmap[v][k].found) { next.push_back(v); dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e); } else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) { dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) { dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e); } } /// using \ref nodes vector instead of \ref process vector. void processNextFullRound(int k) { for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) { for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) { for (int i = 0; i < nodes.size(); ++i) { for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) { Node v = graph.target(e); if (comp[v] != comp_cnt) continue; if ( !dmap[v][k].found || dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) { dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e); if ( !dmap[v][k].found || dmap[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) { dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e); } } } } /// \brief Finds the minimum cycle mean value in the current /// \brief Finds the minimum cycle mean value in the current /// component. bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) { bool found_min = false; for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) { for (int i = 0; i < nodes.size(); ++i) { int n = nodes.size(); if (!dmap[*vi][n].found) continue; if (!dmap[nodes[i]][n].found) continue; Length len; int size; bool found_one = false; for (int k = 0; k < n; ++k) { if (!dmap[*vi][k].found) continue; Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist; int _size = n - k; if (!dmap[nodes[i]][k].found) continue; Length _len = dmap[nodes[i]][n].dist - dmap[nodes[i]][k].dist; int _size = n - k; if (!found_one || len * _size < _len * size) { found_one = true; } } if ( found_one && if ( found_one && (!found_min || len * min_size < min_length * size) ) { found_min = true; min_length = len; min_size = size; min_node = *vi; min_node = nodes[i]; } } return found_min; } public: public: /// \brief Runs the algorithm. /// /// \return \c true if a cycle exists in the graph. /// /// \note Apart from the return value, m.run() is just a shortcut /// \note Apart from the return value, m.run() is just a shortcut /// of the following code. /// \code return findCycle(); } /// \brief Initializes the internal data structures. void init() { /// /// \return \c true if a cycle exists in the graph. /// /// /// \pre \ref init() must be called before using this function. bool findMinMean() { initCurrent(); processRounds(); Length min_length; int min_size; Node min_node; bool found_min = findCurrentMin(min_length, min_size, min_node); if ( found_min && (cycle_node == INVALID || if ( found_min && (cycle_node == INVALID || min_length * cycle_size < cycle_length * min_size) ) { cycle_length = min_length; return (cycle_node != INVALID); } /// \brief Finds a critical (minimum mean) cycle. /// /// /// \return \c true if a cycle exists in the graph. /// /// \pre \ref init() and \ref findMinMean() must be called before /// /// \pre \ref init() and \ref findMinMean() must be called before /// using this function. bool findCycle() { /// \brief Resets the internal data structures. /// /// Resets the internal data structures so that \ref findMinMean() /// and \ref findCycle() can be called again (e.g. when the /// Resets the internal data structures so that \ref findMinMean() /// and \ref findCycle() can be called again (e.g. when the /// underlaying graph has been modified). void reset() { comp_num = stronglyConnectedComponents(graph, comp); } /// \brief Returns the total length of the found cycle. /// /// /// \pre \ref run() must be called before using this function. Length cycleLength() const { Length cycleLength() const { return cycle_length; } /// \brief Returns the number of edges in the found cycle. /// /// /// \pre \ref run() must be called before using this function. int cycleEdgeNum() const { int cycleEdgeNum() const { return cycle_size; } /// \brief Returns the mean length of the found cycle. /// ///   return m.cycleEdgeNum() / double(m.cycleLength()); /// \endcode double minMean() const { double minMean() const { return cycle_length / (double)cycle_size; } /// /// \sa \ref cyclePath() const Path &cycle() const { const Path& cycle() const { return *cycle_path; } /// \brief Sets the \ref lemon::Path "Path" structure storing the /// \brief Sets the \ref lemon::Path "Path" structure storing the /// found cycle. /// /// Sets the \ref lemon::Path "Path" structure storing the found /// cycle. If you don't use this function before calling /// \ref run(), it will allocate one. The destuctor deallocates /// /// Sets the \ref lemon::Path "Path" structure storing the found /// cycle. If you don't use this function before calling /// \ref run(), it will allocate one. The destuctor deallocates /// this automatically allocated map, of course. /// /// \note The algorithm calls only the \ref lemon::Path::addFront() /// "addFront()" method of the given \ref lemon::Path "Path" /// "addFront()" method of the given \ref lemon::Path "Path" /// structure. /// /// /// \return \c (*this) MinMeanCycle &cyclePath(Path& path) { MinMeanCycle& cyclePath(Path &path) { if (local_path) { delete cycle_path;
Note: See TracChangeset for help on using the changeset viewer.