lemon-0.x: comparison lemon/min_mean

equal deleted inserted replaced

-:982fbeb22e1d
+:fd4d28f40a3b
 namespace lemon {
 /// \addtogroup min_cost_flow
 /// @{
 /// \brief Implementation of Karp's algorithm for finding a
-/// minimum mean cycle.
+/// minimum mean (directed) cycle.
 ///
 /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's
-/// algorithm for finding a minimum mean cycle.
+/// 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.
 ///
 /// \author Peter Kovacs
 {
 typedef typename Graph::Node Node;
 typedef typename Graph::NodeIt NodeIt;
 typedef typename Graph::Edge Edge;
 typedef typename Graph::EdgeIt EdgeIt;
-typedef typename Graph::InEdgeIt InEdgeIt;
 typedef typename Graph::OutEdgeIt OutEdgeIt;
 typedef typename LengthMap::Value Length;
 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 {
+struct PathData
+{
 bool found;
 Length dist;
 Edge pred;
 PathData(bool _found = false, Length _dist = 0) :
 	found(_found), dist(_dist), pred(INVALID) {}
 PathData(bool _found, Length _dist, Edge _pred) :
 	found(_found), dist(_dist), pred(_pred) {}
 };
 private:
-typedef typename Graph::template NodeMap<std::vector<PathData> > PathVectorNodeMap;
+typedef typename Graph::template NodeMap<std::vector<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.
-PathVectorNodeMap dmap;
+PathDataNodeMap dmap;
 /// \brief The directed graph the algorithm runs on.
 const Graph& graph;
 /// \brief The length of the edges.
 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 found cycle.
+/// \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.
+/// \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;
 ///
 /// \param _graph The directed graph the algorithm runs on.
 /// \param _length The length (cost) of the edges.
 MinMeanCycle( const Graph& _graph,
 		  const LengthMap& _length ) :
-graph(_graph), length(_length), dmap(_graph),
+graph(_graph), length(_length), dmap(_graph), comp(_graph),
-cycle_length(0), cycle_size(-1), 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:
-/// \brief Initializes the internal data structures.
-void init() {
-comp_num = stronglyConnectedComponents(graph, comp);
-if (!cycle_path) {
-	local_path = true;
-	cycle_path = new Path;
-}
-}
 /// \brief Initializes the internal data structures for the current
 /// component.
 void initCurrent() {
 nodes.clear();
 // Finding the nodes of the current component
 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) {
 	dmap[*vi].resize(n + 1);
 }
 }
-/// \brief Processes all rounds of computing required path data.
+/// \brief Processes all rounds of computing required path data for
+/// the current component.
 void processRounds() {
 dmap[nodes[0]][0] = PathData(true, 0);
 process.clear();
-for (OutEdgeIt oe(graph, nodes[0]); oe != INVALID; ++oe) {
+// Processing the first round
-	Node v = graph.target(oe);
+for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {
+	Node v = graph.target(e);
 	if (comp[v] != comp_cnt || v == nodes[0]) continue;
-	dmap[v][1] = PathData(true, length[oe], oe);
+	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) {
 	processNextBuildRound(k);
 }
 for ( ; k <= n; ++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 oe(graph, *ui); oe != INVALID; ++oe) {
+	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
-	  Node v = graph.target(oe);
+	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
-	  if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
+	  if (!dmap[v][k].found) {
-	    if (!dmap[v][k].found) next.push_back(v);
+	    next.push_back(v);
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
+	    dmap[v][k] = PathData(true, dmap[*ui][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);
 	  }
 	}
 }
 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 (OutEdgeIt oe(graph, *ui); oe != INVALID; ++oe) {
+	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {
-	  Node v = graph.target(oe);
+	  Node v = graph.target(e);
 	  if (comp[v] != comp_cnt) continue;
-	  if ( !dmap[v][k].found || (dmap[v][k].dist > dmap[*ui][k-1].dist + length[oe]) ) {
+	  if ( !dmap[v][k].found ||
-	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[oe], oe);
+	       dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {
+	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);
 	  }
 	}
 }
 }
-/// \brief Finds the minimum cycle mean value according to the path
+/// \brief Finds the minimum cycle mean value in the current
-/// data stored in \ref dmap.
+/// component.
-///
+bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {
-/// Finds the minimum cycle mean value according to the path data
-/// stored in \ref dmap.
-///
-/// \retval min_length The total length of the found cycle.
-/// \retval min_size The number of edges in the found cycle.
-/// \retval min_node A node for obtaining a critical cycle.
-///
-/// \return \c true if a cycle exists in the graph.
-bool findMinCycleMean(Length &min_length, int &min_size, Node &min_node) {
 bool found_min = false;
 for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {
+	int n = nodes.size();
+	if (!dmap[*vi][n].found) continue;
 	Length len;
 	int size;
 	bool found_one = false;
-	int n = nodes.size();
 	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[*vi][n].found && dmap[*vi][k].found && (!found_one || len * _size < _len * size) ) {
+	  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)) {
+	if ( found_one &&
+	     (!found_min || len * min_size < min_length * size) ) {
 	  found_min = true;
 	  min_length = len;
 	  min_size = size;
 	  min_node = *vi;
 	}
 }
 return found_min;
 }
-/// \brief Finds a critical (minimum mean) cycle according to the
+public:
-/// path data stored in \ref dmap.
-void findCycle(const Node &min_n) {
-IntNodeMap reached(graph, -1);
-int r = reached[min_n] = dmap[min_n].size() - 1;
-Node u = graph.source(dmap[min_n][r].pred);
-while (reached[u] < 0) {
-	reached[u] = --r;
-	u = graph.source(dmap[u][r].pred);
-}
-r = reached[u];
-Edge ce = dmap[u][r].pred;
-cycle_path->addFront(ce);
-Node v;
-while ((v = graph.source(ce)) != u) {
-	ce = dmap[v][--r].pred;
-	cycle_path->addFront(ce);
-}
-}
-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();
+/// \endcode
 bool run() {
 init();
-// Searching for the minimum mean cycle in all components
+findMinMean();
-bool found_cycle = false;
+return findCycle();
-Node cycle_node;
+}
+/// \brief Initializes the internal data structures.
+void init() {
+comp_num = stronglyConnectedComponents(graph, comp);
+if (!cycle_path) {
+	local_path = true;
+	cycle_path = new Path;
+}
+}
+/// \brief Finds the minimum cycle mean value in the graph.
+///
+/// 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 = findMinCycleMean(min_length, min_size, min_node);
+	bool found_min = findCurrentMin(min_length, min_size, min_node);
-	if ( found_min && (!found_cycle || min_length * cycle_size  < cycle_length * min_size) ) {
+	if ( found_min && (cycle_node == INVALID ||
-	  found_cycle = true;
+	     min_length * cycle_size < cycle_length * min_size) ) {
 	  cycle_length = min_length;
 	  cycle_size = min_size;
 	  cycle_node = min_node;
 	}
 }
-if (found_cycle) findCycle(cycle_node);
+return (cycle_node != INVALID);
-return found_cycle;
+}
-}
+/// \brief Finds a critical (minimum mean) cycle.
-/// \brief Returns the total length of the found critical cycle.
+///
-///
+/// Finds a critical (minimum mean) cycle using the path data
-/// Returns the total length of the found critical cycle.
+/// 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;
+IntNodeMap reached(graph, -1);
+int r = reached[cycle_node] = dmap[cycle_node].size() - 1;
+Node u = graph.source(dmap[cycle_node][r].pred);
+while (reached[u] < 0) {
+	reached[u] = --r;
+	u = graph.source(dmap[u][r].pred);
+}
+r = reached[u];
+Edge e = dmap[u][r].pred;
+cycle_path->addFront(e);
+cycle_length = cycle_length + length[e];
+++cycle_size;
+Node v;
+while ((v = graph.source(e)) != u) {
+	e = dmap[v][--r].pred;
+	cycle_path->addFront(e);
+	cycle_length = cycle_length + length[e];
+	++cycle_size;
+}
+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 critical
+/// \brief Returns the number of edges in the found cycle.
-/// cycle.
+///
-///
+/// Returns the number of edges in the found cycle.
-/// Returns the number of edges in the found critical 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 critical cycle.
+/// \brief Returns the mean length of the found cycle.
 ///
-/// Returns the mean length of the found critical cycle.
+/// Returns the mean length of the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 ///
 /// \warning LengthMap::Value must be convertible to double.
+///
+/// \note m.minMean() is just a shortcut of the following code.
+/// \code
+///   return m.cycleEdgeNum() / double(m.cycleLength());
+/// \endcode
 double minMean() const {
-return (double)cycle_length / (double)cycle_size;
+return cycle_length / (double)cycle_size;
 }
 /// \brief Returns a const reference to the \ref lemon::Path "Path"
-/// structure of the found flow.
+/// structure of the found cycle.
 ///
 /// Returns a const reference to the \ref lemon::Path "Path"
-/// structure of the found flow.
+/// structure of the found cycle.
 ///
 /// \pre \ref run() must be called before using this function.
 ///
 /// \sa \ref cyclePath()
 const Path &cycle() const {

changeset 2418	89cbf0a2ed57
parent 2409	fe0a8fe16271
child 2437	02c7076bf894