# HG changeset patch # User kpeter # Date 1204167456 0 # Node ID 7216b6a52ab902375682bb942fd507094f775464 # Parent 4f1ac622bb7aa01ba135960cc657f45edd7d3ec1 Small fixes and doc improvements in MinMeanCycle. diff -r 4f1ac622bb7a -r 7216b6a52ab9 lemon/min_mean_cycle.h --- a/lemon/min_mean_cycle.h Thu Feb 28 02:55:23 2008 +0000 +++ b/lemon/min_mean_cycle.h Thu Feb 28 02:57:36 2008 +0000 @@ -26,9 +26,9 @@ #include #include -#include #include #include +#include namespace lemon { @@ -41,8 +41,8 @@ /// \ref MinMeanCycle implements Howard's algorithm for finding a /// minimum mean directed cycle. /// - /// \param Graph The directed graph type the algorithm runs on. - /// \param LengthMap The type of the length (cost) map. + /// \tparam Graph The directed graph type the algorithm runs on. + /// \tparam LengthMap The type of the length (cost) map. /// /// \warning \c LengthMap::Value must be convertible to \c double. /// @@ -57,28 +57,28 @@ typedef typename LengthMap::Value Length; typedef Path Path; - protected: + private: - typename Graph::template NodeMap _reached; - typename Graph::template NodeMap _dist; - typename Graph::template NodeMap _policy; - - /// The directed graph the algorithm runs on. + // The directed graph the algorithm runs on const Graph &_graph; - /// The length of the edges. + // The length of the edges const LengthMap &_length; - /// The total length of the found cycle. + // The total length of the found cycle Length _cycle_length; - /// The number of edges on the found cycle. + // The number of edges on the found cycle int _cycle_size; - /// The found cycle. + // The found cycle Path *_cycle_path; bool _local_path; bool _cycle_found; Node _cycle_node; + typename Graph::template NodeMap _reached; + typename Graph::template NodeMap _dist; + typename Graph::template NodeMap _policy; + typename Graph::template NodeMap _component; int _component_num; @@ -96,171 +96,55 @@ /// \param length The length (cost) of the edges. MinMeanCycle( const Graph &graph, const LengthMap &length ) : - _graph(graph), _length(length), _dist(graph), _reached(graph), - _policy(graph), _component(graph), _cycle_length(0), - _cycle_size(-1), _cycle_path(NULL), _local_path(false) - { } + _graph(graph), _length(length), _cycle_length(0), _cycle_size(-1), + _cycle_path(NULL), _local_path(false), _reached(graph), + _dist(graph), _policy(graph), _component(graph) + {} /// The destructor of the class. ~MinMeanCycle() { if (_local_path) delete _cycle_path; } - protected: - - // Initializes the internal data structures for the current strongly - // connected component and creating the policy graph. - // The policy graph can be represented by the _policy map because - // the out degree of every node is 1. - bool initCurrentComponent(int comp) { - // Finding the nodes of the current component - _nodes.clear(); - for (NodeIt n(_graph); n != INVALID; ++n) { - if (_component[n] == comp) _nodes.push_back(n); + /// \brief Sets the \ref Path "path" structure for storing the found + /// cycle. + /// + /// Sets an external \ref Path "path" structure for storing the + /// found cycle. + /// + /// If you don't call this function before calling \ref run() or + /// \ref init(), it will allocate a local \ref Path "path" + /// structure. + /// The destuctor deallocates this automatically allocated map, + /// of course. + /// + /// \note The algorithm calls only the \ref lemon::Path::addBack() + /// "addBack()" function of the given \ref Path "path" structure. + /// + /// \return (*this) + /// + /// \sa cycle() + MinMeanCycle& cyclePath(Path &path) { + if (_local_path) { + delete _cycle_path; + _local_path = false; } - if (_nodes.size() <= 1) return false; - // Finding the edges of the current component - _edges.clear(); - for (EdgeIt e(_graph); e != INVALID; ++e) { - if ( _component[_graph.source(e)] == comp && - _component[_graph.target(e)] == comp ) - _edges.push_back(e); - } - // Initializing _reached, _dist, _policy maps - for (int i = 0; i < _nodes.size(); ++i) { - _reached[_nodes[i]] = false; - _policy[_nodes[i]] = INVALID; - } - Node u; Edge e; - for (int j = 0; j < _edges.size(); ++j) { - e = _edges[j]; - u = _graph.source(e); - if (!_reached[u] || _length[e] < _dist[u]) { - _dist[u] = _length[e]; - _policy[u] = e; - _reached[u] = true; - } - } - return true; + _cycle_path = &path; + return *this; } - // Finds all cycles in the policy graph. - // Sets _cycle_found to true if a cycle is found and sets - // _cycle_length, _cycle_size, _cycle_node to represent the minimum - // mean cycle in the policy graph. - bool findPolicyCycles(int comp) { - typename Graph::template NodeMap level(_graph, -1); - _cycle_found = false; - Length clength; - int csize; - int path_cnt = 0; - Node u, v; - // Searching for cycles - for (int i = 0; i < _nodes.size(); ++i) { - if (level[_nodes[i]] < 0) { - u = _nodes[i]; - level[u] = path_cnt; - while (level[u = _graph.target(_policy[u])] < 0) - level[u] = path_cnt; - if (level[u] == path_cnt) { - // A cycle is found - clength = _length[_policy[u]]; - csize = 1; - for (v = u; (v = _graph.target(_policy[v])) != u; ) { - clength += _length[_policy[v]]; - ++csize; - } - if ( !_cycle_found || - clength * _cycle_size < _cycle_length * csize ) { - _cycle_found = true; - _cycle_length = clength; - _cycle_size = csize; - _cycle_node = u; - } - } - ++path_cnt; - } - } - return _cycle_found; - } + /// \name Execution control + /// The simplest way to execute the algorithm is to call run(). + /// \n + /// If you only need the minimum mean value, you may call init() + /// and findMinMean(). + /// \n + /// If you would like to run the algorithm again (e.g. the + /// underlaying graph and/or the edge costs were modified), you may + /// not create a new instance of the class, rather call reset(), + /// findMinMean(), and findCycle() instead. - // Contracts the policy graph to be connected by cutting all cycles - // except for the main cycle (i.e. the minimum mean cycle). - void contractPolicyGraph(int comp) { - // Finding the component of the main cycle using - // reverse BFS search - typename Graph::template NodeMap found(_graph, false); - std::deque queue; - queue.push_back(_cycle_node); - found[_cycle_node] = true; - Node u, v; - while (!queue.empty()) { - v = queue.front(); queue.pop_front(); - for (InEdgeIt e(_graph, v); e != INVALID; ++e) { - u = _graph.source(e); - if (_component[u] == comp && !found[u] && _policy[u] == e) { - found[u] = true; - queue.push_back(u); - } - } - } - // Connecting all other nodes to this component using - // reverse BFS search - queue.clear(); - for (int i = 0; i < _nodes.size(); ++i) - if (found[_nodes[i]]) queue.push_back(_nodes[i]); - int found_cnt = queue.size(); - while (found_cnt < _nodes.size() && !queue.empty()) { - v = queue.front(); queue.pop_front(); - for (InEdgeIt e(_graph, v); e != INVALID; ++e) { - u = _graph.source(e); - if (_component[u] == comp && !found[u]) { - found[u] = true; - ++found_cnt; - _policy[u] = e; - queue.push_back(u); - } - } - } - } - - // Computes node distances in the policy graph and updates the - // policy graph if the node distances can be improved. - bool computeNodeDistances(int comp) { - // Computing node distances using reverse BFS search - double cycle_mean = (double)_cycle_length / _cycle_size; - typename Graph::template NodeMap found(_graph, false); - std::deque queue; - queue.push_back(_cycle_node); - found[_cycle_node] = true; - Node u, v; - while (!queue.empty()) { - v = queue.front(); queue.pop_front(); - for (InEdgeIt e(_graph, v); e != INVALID; ++e) { - u = _graph.source(e); - if (_component[u] == comp && !found[u] && _policy[u] == e) { - found[u] = true; - _dist[u] = _dist[v] + _length[e] - cycle_mean; - queue.push_back(u); - } - } - } - // Improving node distances - bool improved = false; - for (int j = 0; j < _edges.size(); ++j) { - Edge e = _edges[j]; - u = _graph.source(e); v = _graph.target(e); - double delta = _dist[v] + _length[e] - cycle_mean; - if (_tolerance.less(delta, _dist[u])) { - improved = true; - _dist[u] = delta; - _policy[u] = e; - } - } - return improved; - } - - public: + /// @{ /// \brief Runs the algorithm. /// @@ -286,7 +170,7 @@ /// /// \sa reset() void init() { - _tolerance.epsilon(1e-8); + _tolerance.epsilon(1e-6); if (!_cycle_path) { _local_path = true; _cycle_path = new Path; @@ -321,11 +205,12 @@ for (int comp = 0; comp < _component_num; ++comp) { if (!initCurrentComponent(comp)) continue; while (true) { - if (!findPolicyCycles(comp)) return false; + if (!findPolicyCycles()) break; contractPolicyGraph(comp); - if (!computeNodeDistances(comp)) return true; + if (!computeNodeDistances(comp)) break; } } + return _cycle_found; } /// \brief Finds a critical (minimum mean) directed cycle. @@ -346,7 +231,16 @@ } return true; } + + /// @} + /// \name Query Functions + /// The result of the algorithm can be obtained using these + /// functions. + /// \n run() must be called before using them. + + /// @{ + /// \brief Returns the total length of the found cycle. /// /// Returns the total length of the found cycle. @@ -380,7 +274,7 @@ /// return double(mmc.cycleLength()) / mmc.cycleEdgeNum(); /// \endcode double cycleMean() const { - return (double)_cycle_length / _cycle_size; + return double(_cycle_length) / _cycle_size; } /// \brief Returns a const reference to the \ref Path "path" @@ -396,32 +290,163 @@ const Path& cycle() const { return *_cycle_path; } + + ///@} + + private: - /// \brief Sets the \ref Path "path" structure for storing the found - /// cycle. - /// - /// Sets an external \ref Path "path" structure for storing the - /// found cycle. - /// - /// If you don't call this function before calling \ref run() or - /// \ref init(), it will allocate a local \ref Path "path" - /// structure. - /// The destuctor deallocates this automatically allocated map, - /// of course. - /// - /// \note The algorithm calls only the \ref lemon::Path::addBack() - /// "addBack()" function of the given \ref Path "path" structure. - /// - /// \return (*this) - /// - /// \sa cycle() - MinMeanCycle& cyclePath(Path &path) { - if (_local_path) { - delete _cycle_path; - _local_path = false; + // Initializes the internal data structures for the current strongly + // connected component and creating the policy graph. + // The policy graph can be represented by the _policy map because + // the out degree of every node is 1. + bool initCurrentComponent(int comp) { + // Finding the nodes of the current component + _nodes.clear(); + for (NodeIt n(_graph); n != INVALID; ++n) { + if (_component[n] == comp) _nodes.push_back(n); } - _cycle_path = &path; - return *this; + if (_nodes.size() <= 1) return false; + // Finding the edges of the current component + _edges.clear(); + for (EdgeIt e(_graph); e != INVALID; ++e) { + if ( _component[_graph.source(e)] == comp && + _component[_graph.target(e)] == comp ) + _edges.push_back(e); + } + // Initializing _reached, _dist, _policy maps + for (int i = 0; i < int(_nodes.size()); ++i) { + _reached[_nodes[i]] = false; + _policy[_nodes[i]] = INVALID; + } + Node u; Edge e; + for (int j = 0; j < int(_edges.size()); ++j) { + e = _edges[j]; + u = _graph.source(e); + if (!_reached[u] || _length[e] < _dist[u]) { + _dist[u] = _length[e]; + _policy[u] = e; + _reached[u] = true; + } + } + return true; + } + + // Finds all cycles in the policy graph. + // Sets _cycle_found to true if a cycle is found and sets + // _cycle_length, _cycle_size, _cycle_node to represent the minimum + // mean cycle in the policy graph. + bool findPolicyCycles() { + typename Graph::template NodeMap level(_graph, -1); + bool curr_cycle_found = false; + Length clength; + int csize; + int path_cnt = 0; + Node u, v; + // Searching for cycles + for (int i = 0; i < int(_nodes.size()); ++i) { + if (level[_nodes[i]] < 0) { + u = _nodes[i]; + level[u] = path_cnt; + while (level[u = _graph.target(_policy[u])] < 0) + level[u] = path_cnt; + if (level[u] == path_cnt) { + // A cycle is found + curr_cycle_found = true; + clength = _length[_policy[u]]; + csize = 1; + for (v = u; (v = _graph.target(_policy[v])) != u; ) { + clength += _length[_policy[v]]; + ++csize; + } + if ( !_cycle_found || + clength * _cycle_size < _cycle_length * csize ) { + _cycle_found = true; + _cycle_length = clength; + _cycle_size = csize; + _cycle_node = u; + } + } + ++path_cnt; + } + } + return curr_cycle_found; + } + + // Contracts the policy graph to be connected by cutting all cycles + // except for the main cycle (i.e. the minimum mean cycle). + void contractPolicyGraph(int comp) { + // Finding the component of the main cycle using + // reverse BFS search + typename Graph::template NodeMap found(_graph, false); + std::deque queue; + queue.push_back(_cycle_node); + found[_cycle_node] = true; + Node u, v; + while (!queue.empty()) { + v = queue.front(); queue.pop_front(); + for (InEdgeIt e(_graph, v); e != INVALID; ++e) { + u = _graph.source(e); + if (_component[u] == comp && !found[u] && _policy[u] == e) { + found[u] = true; + queue.push_back(u); + } + } + } + // Connecting all other nodes to this component using + // reverse BFS search + queue.clear(); + for (int i = 0; i < int(_nodes.size()); ++i) + if (found[_nodes[i]]) queue.push_back(_nodes[i]); + int found_cnt = queue.size(); + while (found_cnt < int(_nodes.size()) && !queue.empty()) { + v = queue.front(); queue.pop_front(); + for (InEdgeIt e(_graph, v); e != INVALID; ++e) { + u = _graph.source(e); + if (_component[u] == comp && !found[u]) { + found[u] = true; + ++found_cnt; + _policy[u] = e; + queue.push_back(u); + } + } + } + } + + // Computes node distances in the policy graph and updates the + // policy graph if the node distances can be improved. + bool computeNodeDistances(int comp) { + // Computing node distances using reverse BFS search + double cycle_mean = double(_cycle_length) / _cycle_size; + typename Graph::template NodeMap found(_graph, false); + std::deque queue; + queue.push_back(_cycle_node); + found[_cycle_node] = true; + _dist[_cycle_node] = 0; + Node u, v; + while (!queue.empty()) { + v = queue.front(); queue.pop_front(); + for (InEdgeIt e(_graph, v); e != INVALID; ++e) { + u = _graph.source(e); + if (_component[u] == comp && !found[u] && _policy[u] == e) { + found[u] = true; + _dist[u] = _dist[v] + _length[e] - cycle_mean; + queue.push_back(u); + } + } + } + // Improving node distances + bool improved = false; + for (int j = 0; j < int(_edges.size()); ++j) { + Edge e = _edges[j]; + u = _graph.source(e); v = _graph.target(e); + double delta = _dist[v] + _length[e] - cycle_mean; + if (_tolerance.less(delta, _dist[u])) { + improved = true; + _dist[u] = delta; + _policy[u] = e; + } + } + return improved; } }; //class MinMeanCycle