lemon-0.x: lemon/min_mean_cycle.h@ef13597d249a

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2007

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_MIN_MEAN_CYCLE_H

    20 #define LEMON_MIN_MEAN_CYCLE_H

    22 /// \ingroup min_cost_flow

    23 ///

    24 /// \file

    25 /// \brief Karp algorithm for finding a minimum mean cycle.

    27 #include <lemon/graph_utils.h>

    28 #include <lemon/topology.h>

    29 #include <lemon/path.h>

    31 namespace lemon {

    33   /// \addtogroup min_cost_flow

    34   /// @{

    36   /// \brief Implementation of Karp's algorithm for finding a

    37   /// minimum mean (directed) cycle.

    38   ///

    39   /// The \ref lemon::MinMeanCycle "MinMeanCycle" implements Karp's

    40   /// algorithm for finding a minimum mean (directed) cycle.

    41   ///

    42   /// \param Graph The directed graph type the algorithm runs on.

    43   /// \param LengthMap The type of the length (cost) map.

    44   ///

    45   /// \author Peter Kovacs

    47 #ifdef DOXYGEN

    48   template <typename Graph, typename LengthMap>

    49 #else

    50   template <typename Graph,

    51     typename LengthMap = typename Graph::template EdgeMap<int> >

    52 #endif

    54   class MinMeanCycle

    55   {

    56     typedef typename Graph::Node Node;

    57     typedef typename Graph::NodeIt NodeIt;

    58     typedef typename Graph::Edge Edge;

    59     typedef typename Graph::EdgeIt EdgeIt;

    60     typedef typename Graph::OutEdgeIt OutEdgeIt;

    62     typedef typename LengthMap::Value Length;

    64     typedef typename Graph::template NodeMap<int> IntNodeMap;

    65     typedef typename Graph::template NodeMap<Edge> PredNodeMap;

    66     typedef Path<Graph> Path;

    67     typedef std::vector<Node> NodeVector;

    68     typedef typename NodeVector::iterator NodeVectorIt;

    70   protected:

    72     /// \brief Data sturcture for path data.

    73     struct PathData

    74     {

    75       bool found;

    76       Length dist;

    77       Edge pred;

    78       PathData(bool _found = false, Length _dist = 0) :

    79 	found(_found), dist(_dist), pred(INVALID) {}

    80       PathData(bool _found, Length _dist, Edge _pred) :

    81 	found(_found), dist(_dist), pred(_pred) {}

    82     };

    84   private:

    86     typedef typename Graph::template NodeMap<std::vector<PathData> >

    87       PathDataNodeMap;

    89   protected:

    91     /// \brief Node map for storing path data.

    92     ///

    93     /// Node map for storing path data of all nodes in the current

    94     /// component. dmap[v][k] is the length of a shortest directed walk

    95     /// to node v from the starting node containing exactly k edges.

    96     PathDataNodeMap dmap;

    98     /// \brief The directed graph the algorithm runs on.

    99     const Graph& graph;

   100     /// \brief The length of the edges.

   101     const LengthMap& length;

   103     /// \brief The total length of the found cycle.

   104     Length cycle_length;

   105     /// \brief The number of edges in the found cycle.

   106     int cycle_size;

   107     /// \brief A node for obtaining a minimum mean cycle.

   108     Node cycle_node;

   110     /// \brief The found cycle.

   111     Path *cycle_path;

   112     /// \brief The algorithm uses local \ref lemon::Path "Path"

   113     /// structure to store the found cycle.

   114     bool local_path;

   116     /// \brief Node map for identifying strongly connected components.

   117     IntNodeMap comp;

   118     /// \brief The number of strongly connected components.

   119     int comp_num;

   120     /// \brief Counter for identifying the current component.

   121     int comp_cnt;

   122     /// \brief Nodes of the current component.

   123     NodeVector nodes;

   124     /// \brief The processed nodes in the last round.

   125     NodeVector process;

   127   public :

   129     /// \brief The constructor of the class.

   130     ///

   131     /// The constructor of the class.

   132     ///

   133     /// \param _graph The directed graph the algorithm runs on.

   134     /// \param _length The length (cost) of the edges.

   135     MinMeanCycle( const Graph& _graph,

   136 		  const LengthMap& _length ) :

   137       graph(_graph), length(_length), dmap(_graph), comp(_graph),

   138       cycle_length(0), cycle_size(-1), cycle_node(INVALID),

   139       cycle_path(NULL), local_path(false)

   140     { }

   142     /// \brief The destructor of the class.

   143     ~MinMeanCycle() {

   144       if (local_path) delete cycle_path;

   145     }

   147   protected:

   149     /// \brief Initializes the internal data structures for the current

   150     /// component.

   151     void initCurrent() {

   152       nodes.clear();

   153       // Finding the nodes of the current component

   154       for (NodeIt v(graph); v != INVALID; ++v) {

   155 	if (comp[v] == comp_cnt) nodes.push_back(v);

   156       }

   157       // Creating vectors for all nodes

   158       int n = nodes.size();

   159       for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {

   160 	dmap[*vi].resize(n + 1);

   161       }

   162     }

   164     /// \brief Processes all rounds of computing required path data for

   165     /// the current component.

   166     void processRounds() {

   167       dmap[nodes[0]][0] = PathData(true, 0);

   168       process.clear();

   169       // Processing the first round

   170       for (OutEdgeIt e(graph, nodes[0]); e != INVALID; ++e) {

   171 	Node v = graph.target(e);

   172 	if (comp[v] != comp_cnt || v == nodes[0]) continue;

   173 	dmap[v][1] = PathData(true, length[e], e);

   174 	process.push_back(v);

   175       }

   176       // Processing other rounds

   177       int n = nodes.size(), k;

   178       for (k = 2; k <= n && process.size() < n; ++k) {

   179 	processNextBuildRound(k);

   180       }

   181       for ( ; k <= n; ++k) {

   182 	processNextFullRound(k);

   183       }

   184     }

   186     /// \brief Processes one round of computing required path data and

   187     /// rebuilds \ref process vector.

   188     void processNextBuildRound(int k) {

   189       NodeVector next;

   190       for (NodeVectorIt ui = process.begin(); ui != process.end(); ++ui) {

   191 	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {

   192 	  Node v = graph.target(e);

   193 	  if (comp[v] != comp_cnt) continue;

   194 	  if (!dmap[v][k].found) {

   195 	    next.push_back(v);

   196 	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);

   197 	  }

   198 	  else if (dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist) {

   199 	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);

   200 	  }

   201 	}

   202       }

   203       process.swap(next);

   204     }

   206     /// \brief Processes one round of computing required path data

   207     /// using \ref nodes vector instead of \ref process vector.

   208     void processNextFullRound(int k) {

   209       for (NodeVectorIt ui = nodes.begin(); ui != nodes.end(); ++ui) {

   210 	for (OutEdgeIt e(graph, *ui); e != INVALID; ++e) {

   211 	  Node v = graph.target(e);

   212 	  if (comp[v] != comp_cnt) continue;

   213 	  if ( !dmap[v][k].found ||

   214 	       dmap[*ui][k-1].dist + length[e] < dmap[v][k].dist ) {

   215 	    dmap[v][k] = PathData(true, dmap[*ui][k-1].dist + length[e], e);

   216 	  }

   217 	}

   218       }

   219     }

   221     /// \brief Finds the minimum cycle mean value in the current

   222     /// component.

   223     bool findCurrentMin(Length &min_length, int &min_size, Node &min_node) {

   224       bool found_min = false;

   225       for (NodeVectorIt vi = nodes.begin(); vi != nodes.end(); ++vi) {

   226 	int n = nodes.size();

   227 	if (!dmap[*vi][n].found) continue;

   228 	Length len;

   229 	int size;

   230 	bool found_one = false;

   231 	for (int k = 0; k < n; ++k) {

   232 	  if (!dmap[*vi][k].found) continue;

   233 	  Length _len = dmap[*vi][n].dist - dmap[*vi][k].dist;

   234 	  int _size = n - k;

   235 	  if (!found_one || len * _size < _len * size) {

   236 	    found_one = true;

   237 	    len = _len;

   238 	    size = _size;

   239 	  }

   240 	}

   241 	if ( found_one &&

   242 	     (!found_min || len * min_size < min_length * size) ) {

   243 	  found_min = true;

   244 	  min_length = len;

   245 	  min_size = size;

   246 	  min_node = *vi;

   247 	}

   248       }

   249       return found_min;

   250     }

   252   public:

   254     /// \brief Runs the algorithm.

   255     ///

   256     /// Runs the algorithm.

   257     ///

   258     /// \return \c true if a cycle exists in the graph.

   259     ///

   260     /// \note Apart from the return value, m.run() is just a shortcut

   261     /// of the following code.

   262     /// \code

   263     ///   m.init();

   264     ///   m.findMinMean();

   265     ///   m.findCycle();

   266     /// \endcode

   267     bool run() {

   268       init();

   269       findMinMean();

   270       return findCycle();

   271     }

   273     /// \brief Initializes the internal data structures.

   274     void init() {

   275       comp_num = stronglyConnectedComponents(graph, comp);

   276       if (!cycle_path) {

   277 	local_path = true;

   278 	cycle_path = new Path;

   279       }

   280     }

   282     /// \brief Finds the minimum cycle mean value in the graph.

   283     ///

   284     /// Computes all the required path data and finds the minimum cycle

   285     /// mean value in the graph.

   286     ///

   287     /// \return \c true if a cycle exists in the graph.

   288     ///

   289     /// \pre \ref init() must be called before using this function.

   290     bool findMinMean() {

   291       cycle_node = INVALID;

   292       for (comp_cnt = 0; comp_cnt < comp_num; ++comp_cnt) {

   293 	initCurrent();

   294 	processRounds();

   296 	Length min_length;

   297 	int min_size;

   298 	Node min_node;

   299 	bool found_min = findCurrentMin(min_length, min_size, min_node);

   301 	if ( found_min && (cycle_node == INVALID ||

   302 	     min_length * cycle_size < cycle_length * min_size) ) {

   303 	  cycle_length = min_length;

   304 	  cycle_size = min_size;

   305 	  cycle_node = min_node;

   306 	}

   307       }

   308       return (cycle_node != INVALID);

   309     }

   311     /// \brief Finds a critical (minimum mean) cycle.

   312     ///

   313     /// Finds a critical (minimum mean) cycle using the path data

   314     /// stored in \ref dmap.

   315     ///

   316     /// \return \c true if a cycle exists in the graph.

   317     ///

   318     /// \pre \ref init() and \ref findMinMean() must be called before

   319     /// using this function.

   320     bool findCycle() {

   321       if (cycle_node == INVALID) return false;

   322       cycle_length = 0;

   323       cycle_size = 0;

   324       IntNodeMap reached(graph, -1);

   325       int r = reached[cycle_node] = dmap[cycle_node].size() - 1;

   326       Node u = graph.source(dmap[cycle_node][r].pred);

   327       while (reached[u] < 0) {

   328 	reached[u] = --r;

   329 	u = graph.source(dmap[u][r].pred);

   330       }

   331       r = reached[u];

   332       Edge e = dmap[u][r].pred;

   333       cycle_path->addFront(e);

   334       cycle_length = cycle_length + length[e];

   335       ++cycle_size;

   336       Node v;

   337       while ((v = graph.source(e)) != u) {

   338 	e = dmap[v][--r].pred;

   339 	cycle_path->addFront(e);

   340 	cycle_length = cycle_length + length[e];

   341 	++cycle_size;

   342       }

   343       return true;

   344     }

   346     /// \brief Resets the internal data structures.

   347     ///

   348     /// Resets the internal data structures so that \ref findMinMean()

   349     /// and \ref findCycle() can be called again (e.g. when the

   350     /// underlaying graph has been modified).

   351     void reset() {

   352       for (NodeIt u(graph); u != INVALID; ++u)

   353 	dmap[u].clear();

   354       cycle_node = INVALID;

   355       if (cycle_path) cycle_path->clear();

   356       comp_num = stronglyConnectedComponents(graph, comp);

   357     }

   359     /// \brief Returns the total length of the found cycle.

   360     ///

   361     /// Returns the total length of the found cycle.

   362     ///

   363     /// \pre \ref run() must be called before using this function.

   364     Length cycleLength() const {

   365       return cycle_length;

   366     }

   368     /// \brief Returns the number of edges in the found cycle.

   369     ///

   370     /// Returns the number of edges in the found cycle.

   371     ///

   372     /// \pre \ref run() must be called before using this function.

   373     int cycleEdgeNum() const {

   374       return cycle_size;

   375     }

   377     /// \brief Returns the mean length of the found cycle.

   378     ///

   379     /// Returns the mean length of the found cycle.

   380     ///

   381     /// \pre \ref run() must be called before using this function.

   382     ///

   383     /// \warning LengthMap::Value must be convertible to double.

   384     ///

   385     /// \note m.minMean() is just a shortcut of the following code.

   386     /// \code

   387     ///   return m.cycleEdgeNum() / double(m.cycleLength());

   388     /// \endcode

   389     double minMean() const {

   390       return cycle_length / (double)cycle_size;

   391     }

   393     /// \brief Returns a const reference to the \ref lemon::Path "Path"

   394     /// structure of the found cycle.

   395     ///

   396     /// Returns a const reference to the \ref lemon::Path "Path"

   397     /// structure of the found cycle.

   398     ///

   399     /// \pre \ref run() must be called before using this function.

   400     ///

   401     /// \sa \ref cyclePath()

   402     const Path &cycle() const {

   403       return *cycle_path;

   404     }

   406     /// \brief Sets the \ref lemon::Path "Path" structure storing the

   407     /// found cycle.

   408     ///

   409     /// Sets the \ref lemon::Path "Path" structure storing the found

   410     /// cycle. If you don't use this function before calling

   411     /// \ref run(), it will allocate one. The destuctor deallocates

   412     /// this automatically allocated map, of course.

   413     ///

   414     /// \note The algorithm calls only the \ref lemon::Path::addFront()

   415     /// "addFront()" method of the given \ref lemon::Path "Path"

   416     /// structure.

   417     ///

   418     /// \return \c (*this)

   419     MinMeanCycle &cyclePath(Path& path) {

   420       if (local_path) {

   421 	delete cycle_path;

   422 	local_path = false;

   423       }

   424       cycle_path = &path;

   425       return *this;

   426     }

   428   }; //class MinMeanCycle

   430   ///@}

   432 } //namespace lemon

   434 #endif //LEMON_MIN_MEAN_CYCLE_H

author	athos
	Tue, 27 Mar 2007 09:23:33 +0000
changeset 2415	ef13597d249a
parent 2409	fe0a8fe16271
child 2437	02c7076bf894
permissions	-rw-r--r--