lemon-0.x: comparison lemon/min_mean

equal deleted inserted replaced

-:fd4d28f40a3b
+:8a33f22b8580
 #ifndef LEMON_MIN_MEAN_CYCLE_H
 #define LEMON_MIN_MEAN_CYCLE_H
 /// \ingroup min_cost_flow
 ///
 /// \file
 /// \brief Karp algorithm for finding a minimum mean cycle.
 #include <lemon/graph_utils.h>
 #include <lemon/topology.h>
 #include <lemon/path.h>
 /// \param Graph The directed graph type the algorithm runs on.
 /// \param LengthMap The type of the length (cost) map.
 ///
 /// \author Peter Kovacs
-#ifdef DOXYGEN
-template <typename Graph, typename LengthMap>
-#else
 template <typename Graph,
 typename LengthMap = typename Graph::template EdgeMap<int> >
-#endif
 class MinMeanCycle
 {
 typedef typename Graph::Node Node;
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
 typedef typename Graph::template NodeMap<int> IntNodeMap;
 typedef typename Graph::template NodeMap<Edge> PredNodeMap;
 typedef Path<Graph> Path;
 typedef std::vector<Node> NodeVector;
-typedef typename NodeVector::iterator NodeVectorIt;
 protected:
 /// \brief Data sturcture for path data.
 struct PathData
 PathDataNodeMap;
 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
 /// 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.
 Node cycle_node;
 /// \brief The found cycle.
 Path *cycle_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 number of strongly connected components.
 int comp_num;
 /// \brief Counter for identifying the current component.
 int comp_cnt;
 /// \brief Nodes of the current component.
 NodeVector nodes;
 /// \brief The processed nodes in the last round.
 NodeVector process;
 public :
 /// \brief The constructor of the class.
 ///
 /// The constructor of the class.
 ///
 /// \param _graph The directed graph the algorithm runs on.
 /// \param _length The length (cost) of the edges.
-MinMeanCycle( const Graph& _graph,
+MinMeanCycle( const Graph &_graph,
-		  const LengthMap& _length ) :
+		  const LengthMap &_length ) :
 graph(_graph), length(_length), dmap(_graph), comp(_graph),
 cycle_length(0), cycle_size(-1), cycle_node(INVALID),
 cycle_path(NULL), local_path(false)
 { }
 /// \brief The destructor of the class.
 ~MinMeanCycle() {
 if (local_path) delete cycle_path;
 }
 protected:
 for (NodeIt v(graph); v != INVALID; ++v) {
 	if (comp[v] == comp_cnt) nodes.push_back(v);
 }
 // Creating vectors for all nodes
 int n = nodes.size();
-for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
+for (int i = 0; i < nodes.size(); ++i) {
-	dmap[*vi].resize(n + 1);
+	dmap[nodes[i]].resize(n + 1);
 }
 }
 /// \brief Processes all rounds of computing required path data for
 /// the current component.
 void processRounds() {
 dmap[nodes[0]][0] = PathData(true, 0);
 process.clear();
 // Processing the first round
 	Node v = graph.target(e);
 	if (comp[v] != comp_cnt || v == nodes[0]) continue;
 	dmap[v][1] = PathData(true, length[e], e);
 	process.push_back(v);
 }
 // 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 (int i = 0; i < process.size(); ++i) {
-	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+	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) {
+	  else if (dmap[process[i]][k-1].dist + length[e] < dmap[v][k].dist) {
-	    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);
 	  }
 	}
 }
 process.swap(next);
 }
 /// \brief Processes one round of computing required path data
 /// using \ref nodes vector instead of \ref process vector.
 void processNextFullRound(int k) {
-for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {
+for (int i = 0; i < nodes.size(); ++i) {
-	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
+	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[nodes[i]][k-1].dist + length[e] < dmap[v][k].dist ) {
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
+	    dmap[v][k] = PathData(true, dmap[nodes[i]][k-1].dist + length[e], e);
 	  }
 	}
 }
 }
 /// \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;
+	  if (!dmap[nodes[i]][k].found) continue;
-	  Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;
+	  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;
 	    len = _len;
 	    size = _size;
 	  }
 	}
 	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:
 /// \brief Runs the algorithm.
 ///
 /// 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
 /// of the following code.
 /// \code
 ///   m.init();
 ///   m.findMinMean();
 ///   m.findCycle();
 bool run() {
 init();
 findMinMean();
 return findCycle();
 }
 /// \brief Initializes the internal data structures.
 void init() {
 comp_num = stronglyConnectedComponents(graph, comp);
 if (!cycle_path) {
 	local_path = true;
 ///
 /// Computes all the required path data and finds the minimum cycle
 /// mean value in the graph.
 ///
 /// \return \c true if a cycle exists in the graph.
 ///
 /// \pre \ref init() must be called before using this function.
 bool findMinMean() {
 cycle_node = INVALID;
 for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {
 	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 ||
 	     min_length * cycle_size < cycle_length * min_size) ) {
 	  cycle_length = min_length;
 	  cycle_size = min_size;
 	  cycle_node = min_node;
 	}
 }
 return (cycle_node != INVALID);
 }
 /// \brief Finds a critical (minimum mean) cycle.
 ///
 /// Finds a critical (minimum mean) cycle using the path data
 /// stored in \ref dmap.
 ///
 /// \return \c true if a cycle exists in the graph.
 ///
 /// \pre \ref init() and \ref findMinMean() must be called before
 /// using this function.
 bool findCycle() {
 if (cycle_node == INVALID) return false;
 cycle_length = 0;
 cycle_size = 0;
 return true;
 }
 /// \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
 /// underlaying graph has been modified).
 void reset() {
 for (NodeIt u(graph); u != INVALID; ++u)
 	dmap[u].clear();
 cycle_node = INVALID;
 if (cycle_path) cycle_path->clear();
 comp_num = stronglyConnectedComponents(graph, comp);
 }
 /// \brief Returns the total length of the found cycle.
 ///
 /// Returns the total length of the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 Length cycleLength() const {
 return cycle_length;
 }
 /// \brief Returns the number of edges in the found cycle.
 ///
 /// Returns the number of edges in the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 int cycleEdgeNum() const {
 return cycle_size;
 }
 /// \brief Returns the mean length of the found cycle.
 ///
 /// Returns the mean length of the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 ///
 /// \note m.minMean() is just a shortcut of the following code.
 /// \code
 ///   return m.cycleEdgeNum() / double(m.cycleLength());
 /// \endcode
 double minMean() const {
 return cycle_length / (double)cycle_size;
 }
 /// \brief Returns a const reference to the \ref lemon::Path "Path"
 /// structure of the found cycle.
 /// structure of the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 ///
 /// \sa \ref cyclePath()
-const Path &cycle() const {
+const Path& cycle() const {
 return *cycle_path;
 }
 /// \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
 /// 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"
 /// structure.
 ///
 /// \return \c (*this)
-MinMeanCycle &cyclePath(Path& path) {
+MinMeanCycle& cyclePath(Path &path) {
 if (local_path) {
 	delete cycle_path;
 	local_path = false;
 }
 cycle_path = &path;

changeset 2437	02c7076bf894
parent 2413	21eb3ccdc3df
child 2509	a8081c9cd96a