1.1 --- a/lemon/min_mean_cycle.h	Tue Apr 24 09:39:01 2007 +0000
     1.2 +++ b/lemon/min_mean_cycle.h	Mon May 07 08:47:38 2007 +0000
     1.3 @@ -21,7 +21,7 @@
     1.4  
     1.5  /// \ingroup min_cost_flow
     1.6  ///
     1.7 -/// \file 
     1.8 +/// \file
     1.9  /// \brief Karp algorithm for finding a minimum mean cycle.
    1.10  
    1.11  #include <lemon/graph_utils.h>
    1.12 @@ -44,13 +44,8 @@
    1.13    ///
    1.14    /// \author Peter Kovacs
    1.15  
    1.16 -#ifdef DOXYGEN
    1.17 -  template <typename Graph, typename LengthMap>
    1.18 -#else
    1.19    template <typename Graph,
    1.20      typename LengthMap = typename Graph::template EdgeMap<int> >
    1.21 -#endif
    1.22 -
    1.23    class MinMeanCycle
    1.24    {
    1.25      typedef typename Graph::Node Node;
    1.26 @@ -65,7 +60,6 @@
    1.27      typedef typename Graph::template NodeMap<Edge> PredNodeMap;
    1.28      typedef Path<Graph> Path;
    1.29      typedef std::vector<Node> NodeVector;
    1.30 -    typedef typename NodeVector::iterator NodeVectorIt;
    1.31  
    1.32    protected:
    1.33  
    1.34 @@ -89,30 +83,30 @@
    1.35    protected:
    1.36  
    1.37      /// \brief Node map for storing path data.
    1.38 -    /// 
    1.39 +    ///
    1.40      /// Node map for storing path data of all nodes in the current
    1.41 -    /// component. dmap[v][k] is the length of a shortest directed walk 
    1.42 +    /// component. dmap[v][k] is the length of a shortest directed walk
    1.43      /// to node v from the starting node containing exactly k edges.
    1.44      PathDataNodeMap dmap;
    1.45 -    
    1.46 +
    1.47      /// \brief The directed graph the algorithm runs on.
    1.48 -    const Graph& graph;
    1.49 +    const Graph &graph;
    1.50      /// \brief The length of the edges.
    1.51 -    const LengthMap& length;
    1.52 -    
    1.53 +    const LengthMap &length;
    1.54 +
    1.55      /// \brief The total length of the found cycle.
    1.56      Length cycle_length;
    1.57      /// \brief The number of edges in the found cycle.
    1.58      int cycle_size;
    1.59 -    /// \brief A node for obtaining a minimum mean cycle. 
    1.60 +    /// \brief A node for obtaining a minimum mean cycle.
    1.61      Node cycle_node;
    1.62  
    1.63      /// \brief The found cycle.
    1.64      Path *cycle_path;
    1.65 -    /// \brief The algorithm uses local \ref lemon::Path "Path" 
    1.66 +    /// \brief The algorithm uses local \ref lemon::Path "Path"
    1.67      /// structure to store the found cycle.
    1.68      bool local_path;
    1.69 -    
    1.70 +
    1.71      /// \brief Node map for identifying strongly connected components.
    1.72      IntNodeMap comp;
    1.73      /// \brief The number of strongly connected components.
    1.74 @@ -123,7 +117,7 @@
    1.75      NodeVector nodes;
    1.76      /// \brief The processed nodes in the last round.
    1.77      NodeVector process;
    1.78 -    
    1.79 +
    1.80    public :
    1.81  
    1.82      /// \brief The constructor of the class.
    1.83 @@ -132,15 +126,15 @@
    1.84      ///
    1.85      /// \param _graph The directed graph the algorithm runs on.
    1.86      /// \param _length The length (cost) of the edges.
    1.87 -    MinMeanCycle( const Graph& _graph,
    1.88 -		  const LengthMap& _length ) :
    1.89 +    MinMeanCycle( const Graph &_graph,
    1.90 +		  const LengthMap &_length ) :
    1.91        graph(_graph), length(_length), dmap(_graph), comp(_graph),
    1.92        cycle_length(0), cycle_size(-1), cycle_node(INVALID),
    1.93        cycle_path(NULL), local_path(false)
    1.94      { }
    1.95  
    1.96      /// \brief The destructor of the class.
    1.97 -    ~MinMeanCycle() { 
    1.98 +    ~MinMeanCycle() {
    1.99        if (local_path) delete cycle_path;
   1.100      }
   1.101  
   1.102 @@ -156,12 +150,12 @@
   1.103        }
   1.104        // Creating vectors for all nodes
   1.105        int n = nodes.size();
   1.106 -      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
   1.107 -	dmap[*vi].resize(n + 1);
   1.108 +      for (int i = 0; i < nodes.size(); ++i) {
   1.109 +	dmap[nodes[i]].resize(n + 1);
   1.110        }
   1.111      }
   1.112 -    
   1.113 -    /// \brief Processes all rounds of computing required path data for 
   1.114 +
   1.115 +    /// \brief Processes all rounds of computing required path data for
   1.116      /// the current component.
   1.117      void processRounds() {
   1.118        dmap[nodes[0]][0] = PathData(true, 0);
   1.119 @@ -173,30 +167,28 @@
   1.120  	dmap[v][1] = PathData(true, length[e], e);
   1.121  	process.push_back(v);
   1.122        }
   1.123 -      // Processing other rounds 
   1.124 +      // Processing other rounds
   1.125        int n = nodes.size(), k;
   1.126 -      for (k = 2; k <= n && process.size() < n; ++k) {
   1.127 +      for (k = 2; k <= n && process.size() < n; ++k)
   1.128  	processNextBuildRound(k);
   1.129 -      }
   1.130 -      for ( ; k <= n; ++k) {
   1.131 +      for ( ; k <= n; ++k)
   1.132  	processNextFullRound(k);
   1.133 -      }
   1.134      }
   1.135 -    
   1.136 +
   1.137      /// \brief Processes one round of computing required path data and
   1.138      /// rebuilds \ref process vector.
   1.139      void processNextBuildRound(int k) {
   1.140        NodeVector next;
   1.141 -      for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {
   1.142 -	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
   1.143 +      for (int i = 0; i < process.size(); ++i) {
   1.144 +	for (OutEdgeIt e(graph, process[i]); e != INVALID; ++e) {
   1.145  	  Node v = graph.target(e);
   1.146  	  if (comp[v] != comp_cnt) continue;
   1.147  	  if (!dmap[v][k].found) {
   1.148  	    next.push_back(v);
   1.149 -	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
   1.150 +	    dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
   1.151  	  }
   1.152 -	  else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {
   1.153 -	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
   1.154 +	  else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) {
   1.155 +	    dmap[v][k] = PathData(true, dmap[process[i]][k-1].dist + length[e], e);
   1.156  	  }
   1.157  	}
   1.158        }
   1.159 @@ -206,58 +198,58 @@
   1.160      /// \brief Processes one round of computing required path data
   1.161      /// using \ref nodes vector instead of \ref process vector.
   1.162      void processNextFullRound(int k) {
   1.163 -      for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
   1.164 -	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
   1.165 +      for (int i = 0; i < nodes.size(); ++i) {
   1.166 +	for (OutEdgeIt e(graph, nodes[i]); e != INVALID; ++e) {
   1.167  	  Node v = graph.target(e);
   1.168  	  if (comp[v] != comp_cnt) continue;
   1.169 -	  if ( !dmap[v][k].found || 
   1.170 -	       dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
   1.171 -	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
   1.172 +	  if ( !dmap[v][k].found ||
   1.173 +	       dmap[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) {
   1.174 +	    dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e);
   1.175  	  }
   1.176  	}
   1.177        }
   1.178      }
   1.179 -    
   1.180 -    /// \brief Finds the minimum cycle mean value in the current 
   1.181 +
   1.182 +    /// \brief Finds the minimum cycle mean value in the current
   1.183      /// component.
   1.184      bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
   1.185        bool found_min = false;
   1.186 -      for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
   1.187 +      for (int i = 0; i < nodes.size(); ++i) {
   1.188  	int n = nodes.size();
   1.189 -	if (!dmap[*vi][n].found) continue;
   1.190 +	if (!dmap[nodes[i]][n].found) continue;
   1.191  	Length len;
   1.192  	int size;
   1.193  	bool found_one = false;
   1.194  	for (int k = 0; k < n; ++k) {
   1.195 -	  if (!dmap[*vi][k].found) continue;
   1.196 -	  Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
   1.197 -	  int _size = n - k; 
   1.198 +	  if (!dmap[nodes[i]][k].found) continue;
   1.199 +	  Length _len = dmap[nodes[i]][n].dist - dmap[nodes[i]][k].dist;
   1.200 +	  int _size = n - k;
   1.201  	  if (!found_one || len * _size < _len * size) {
   1.202  	    found_one = true;
   1.203  	    len = _len;
   1.204  	    size = _size;
   1.205  	  }
   1.206  	}
   1.207 -	if ( found_one && 
   1.208 +	if ( found_one &&
   1.209  	     (!found_min || len * min_size < min_length * size) ) {
   1.210  	  found_min = true;
   1.211  	  min_length = len;
   1.212  	  min_size = size;
   1.213 -	  min_node = *vi;
   1.214 +	  min_node = nodes[i];
   1.215  	}
   1.216        }
   1.217        return found_min;
   1.218      }
   1.219 -    
   1.220 -  public:  
   1.221 -    
   1.222 +
   1.223 +  public:
   1.224 +
   1.225      /// \brief Runs the algorithm.
   1.226      ///
   1.227      /// Runs the algorithm.
   1.228      ///
   1.229      /// \return \c true if a cycle exists in the graph.
   1.230      ///
   1.231 -    /// \note Apart from the return value, m.run() is just a shortcut 
   1.232 +    /// \note Apart from the return value, m.run() is just a shortcut
   1.233      /// of the following code.
   1.234      /// \code
   1.235      ///   m.init();
   1.236 @@ -269,7 +261,7 @@
   1.237        findMinMean();
   1.238        return findCycle();
   1.239      }
   1.240 -    
   1.241 +
   1.242      /// \brief Initializes the internal data structures.
   1.243      void init() {
   1.244        comp_num = stronglyConnectedComponents(graph, comp);
   1.245 @@ -285,20 +277,20 @@
   1.246      /// mean value in the graph.
   1.247      ///
   1.248      /// \return \c true if a cycle exists in the graph.
   1.249 -    /// 
   1.250 +    ///
   1.251      /// \pre \ref init() must be called before using this function.
   1.252      bool findMinMean() {
   1.253        cycle_node = INVALID;
   1.254        for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
   1.255  	initCurrent();
   1.256  	processRounds();
   1.257 -	
   1.258 +
   1.259  	Length min_length;
   1.260  	int min_size;
   1.261  	Node min_node;
   1.262  	bool found_min = findCurrentMin(min_length, min_size, min_node);
   1.263 -	
   1.264 -	if ( found_min && (cycle_node == INVALID || 
   1.265 +
   1.266 +	if ( found_min && (cycle_node == INVALID ||
   1.267  	     min_length * cycle_size < cycle_length * min_size) ) {
   1.268  	  cycle_length = min_length;
   1.269  	  cycle_size = min_size;
   1.270 @@ -307,15 +299,15 @@
   1.271        }
   1.272        return (cycle_node != INVALID);
   1.273      }
   1.274 -    
   1.275 +
   1.276      /// \brief Finds a critical (minimum mean) cycle.
   1.277      ///
   1.278      /// Finds a critical (minimum mean) cycle using the path data
   1.279      /// stored in \ref dmap.
   1.280      ///
   1.281      /// \return \c true if a cycle exists in the graph.
   1.282 -    /// 
   1.283 -    /// \pre \ref init() and \ref findMinMean() must be called before 
   1.284 +    ///
   1.285 +    /// \pre \ref init() and \ref findMinMean() must be called before
   1.286      /// using this function.
   1.287      bool findCycle() {
   1.288        if (cycle_node == INVALID) return false;
   1.289 @@ -345,8 +337,8 @@
   1.290  
   1.291      /// \brief Resets the internal data structures.
   1.292      ///
   1.293 -    /// Resets the internal data structures so that \ref findMinMean() 
   1.294 -    /// and \ref findCycle() can be called again (e.g. when the 
   1.295 +    /// Resets the internal data structures so that \ref findMinMean()
   1.296 +    /// and \ref findCycle() can be called again (e.g. when the
   1.297      /// underlaying graph has been modified).
   1.298      void reset() {
   1.299        for (NodeIt u(graph); u != INVALID; ++u)
   1.300 @@ -355,25 +347,25 @@
   1.301        if (cycle_path) cycle_path->clear();
   1.302        comp_num = stronglyConnectedComponents(graph, comp);
   1.303      }
   1.304 -    
   1.305 +
   1.306      /// \brief Returns the total length of the found cycle.
   1.307      ///
   1.308      /// Returns the total length of the found cycle.
   1.309      ///
   1.310      /// \pre \ref run() must be called before using this function.
   1.311 -    Length cycleLength() const { 
   1.312 +    Length cycleLength() const {
   1.313        return cycle_length;
   1.314      }
   1.315 -    
   1.316 +
   1.317      /// \brief Returns the number of edges in the found cycle.
   1.318      ///
   1.319      /// Returns the number of edges in the found cycle.
   1.320      ///
   1.321      /// \pre \ref run() must be called before using this function.
   1.322 -    int cycleEdgeNum() const { 
   1.323 +    int cycleEdgeNum() const {
   1.324        return cycle_size;
   1.325      }
   1.326 -    
   1.327 +
   1.328      /// \brief Returns the mean length of the found cycle.
   1.329      ///
   1.330      /// Returns the mean length of the found cycle.
   1.331 @@ -386,7 +378,7 @@
   1.332      /// \code
   1.333      ///   return m.cycleEdgeNum() / double(m.cycleLength());
   1.334      /// \endcode
   1.335 -    double minMean() const { 
   1.336 +    double minMean() const {
   1.337        return cycle_length / (double)cycle_size;
   1.338      }
   1.339  
   1.340 @@ -399,24 +391,24 @@
   1.341      /// \pre \ref run() must be called before using this function.
   1.342      ///
   1.343      /// \sa \ref cyclePath()
   1.344 -    const Path &cycle() const {
   1.345 +    const Path& cycle() const {
   1.346        return *cycle_path;
   1.347      }
   1.348 -    
   1.349 -    /// \brief Sets the \ref lemon::Path "Path" structure storing the 
   1.350 +
   1.351 +    /// \brief Sets the \ref lemon::Path "Path" structure storing the
   1.352      /// found cycle.
   1.353 -    /// 
   1.354 -    /// Sets the \ref lemon::Path "Path" structure storing the found 
   1.355 -    /// cycle. If you don't use this function before calling 
   1.356 -    /// \ref run(), it will allocate one. The destuctor deallocates 
   1.357 +    ///
   1.358 +    /// Sets the \ref lemon::Path "Path" structure storing the found
   1.359 +    /// cycle. If you don't use this function before calling
   1.360 +    /// \ref run(), it will allocate one. The destuctor deallocates
   1.361      /// this automatically allocated map, of course.
   1.362      ///
   1.363      /// \note The algorithm calls only the \ref lemon::Path::addFront()
   1.364 -    /// "addFront()" method of the given \ref lemon::Path "Path" 
   1.365 +    /// "addFront()" method of the given \ref lemon::Path "Path"
   1.366      /// structure.
   1.367 -    /// 
   1.368 +    ///
   1.369      /// \return \c (*this)
   1.370 -    MinMeanCycle &cyclePath(Path& path) {
   1.371 +    MinMeanCycle& cyclePath(Path &path) {
   1.372        if (local_path) {
   1.373  	delete cycle_path;
   1.374  	local_path = false;