LEMON/LEMON-main Changeset - r922:9312d6c89d02

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r922:9312d6c89d02

« 920:745312
« 921:140c95

924:a80381 »

r922:9312d6c89d02

Mon, 10 Jan 2011 09:34:50

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 11 0

merge default

4 files changed with 271 insertions and 95 deletions:

doc/coding_style.dox

doc/groups.dox

lemon/capacity_scaling.h

lemon/core.h

lemon/cost_scaling.h

lemon/cycle_canceling.h

lemon/euler.h

lemon/grosso_locatelli_pullan_mc.h

194

lemon/network_simplex.h

lemon/path.h

test/max_clique_test.cc

↑ Collapse diff ↑

doc/coding_style.dox

Show inline comments

@@ -53,75 +53,75 @@
 		Note that all standard LEMON headers are located in the \c lemon subdirectory,
 		so you should include them from C++ source like this:
 		\code
 		#include <lemon/header_file.h>
 		\endcode
 		The source code files use the same style and they have '.cc' extension.
 		\code
 		source_code.cc
 		\endcode
 		\subsection cs-class Classes and other types
 		The name of a class or any type should look like the following.
 		\code
 		AllWordsCapitalizedWithoutUnderscores
 		\endcode
 		\subsection cs-func Methods and other functions
 		The name of a function should look like the following.
 		\code
 		firstWordLowerCaseRestCapitalizedWithoutUnderscores
 		\endcode
 		\subsection cs-funcs Constants, Macros
 		The names of constants and macros should look like the following.
 		\code
 		ALL_UPPER_CASE_WITH_UNDERSCORES
 		\endcode
 		\subsection cs-loc-var Class and instance member variables, auto variables
 		The names of class and instance member variables and auto variables
 		(=variables used locally in methods) should look like the following.
 		\code
 		all_lower_case_with_underscores
 		\endcode
 		\subsection pri-loc-var Private member variables
 		Private member variables should start with underscore
+		Private member variables should start with underscore.
 		\code
-		_start_with_underscores
+		_start_with_underscore
 		\endcode
 		\subsection cs-excep Exceptions
 		When writing exceptions please comply the following naming conventions.
 		\code
 		ClassNameEndsWithException
 		\endcode
 		or
 		\code
 		ClassNameEndsWithError
 		\endcode
 		\section header-template Template Header File
 		Each LEMON header file should look like this:
 		\include template.h
 		*/

doc/groups.dox

Show inline comments

@@ -361,230 +361,230 @@
 		\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
 		\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
 		    \quad \forall u\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm
 		  \ref edmondskarp72theoretical.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
 		  \ref goldberg88newapproach.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
 		  \ref dinic70algorithm, \ref sleator83dynamic.
 		- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
 		  \ref goldberg88newapproach, \ref sleator83dynamic.
 		In most cases the \ref Preflow algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		also provide functions to query the minimum cut, which is the dual
 		problem of maximum flow.
 		\ref Circulation is a preflow push-relabel algorithm implemented directly
 		for finding feasible circulations, which is a somewhat different problem,
 		but it is strongly related to maximum flow.
 		For more information, see \ref Circulation.
 		*/
 		/**
 		@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations \ref amo93networkflows. For more information about this
 		problem and its dual solution, see \ref min_cost_flow
 		"Minimum Cost Flow Problem".
 		LEMON contains several algorithms for this problem.
 		 - \ref NetworkSimplex Primal Network Simplex algorithm with various
 		   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
 		 - \ref CostScaling Cost Scaling algorithm based on push/augment and
 		   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
 		   \ref bunnagel98efficient.
 		 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
 		   shortest path method \ref edmondskarp72theoretical.
 		 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
 		   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
 		implementations, but the other two algorithms could be faster in special cases.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
+		\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum mean cycles.
 		This group contains the algorithms for finding minimum mean cycles
 		\ref clrs01algorithms, \ref amo93networkflows.
 		The \e minimum \e mean \e cycle \e problem is to find a directed cycle
 		of minimum mean length (cost) in a digraph.
 		The mean length of a cycle is the average length of its arcs, i.e. the
 		ratio between the total length of the cycle and the number of arcs on it.
 		This problem has an important connection to \e conservative \e length
 		\e functions, too. A length function on the arcs of a digraph is called
 		conservative if and only if there is no directed cycle of negative total
 		length. For an arbitrary length function, the negative of the minimum
 		cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
 		arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
 		function.
 		LEMON contains three algorithms for solving the minimum mean cycle problem:
 		- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
 		  \ref dasdan98minmeancycle.
 		- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
 		  version of Karp's algorithm \ref dasdan98minmeancycle.
 		- \ref HowardMmc Howard's policy iteration algorithm
 		  \ref dasdan98minmeancycle.
-		In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+		In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
 		most efficient one, though the best known theoretical bound on its running
 		time is exponential.
 		Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
 		run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
 		typically faster due to the applied early termination scheme.
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains the algorithms for calculating
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the edges for which each node has at most one incident
 		edge.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		- \ref MaxFractionalMatching Push-relabel algorithm for calculating
 		  maximum cardinality fractional matching in general graphs.
 		- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
 		  maximum weighted fractional matching in general graphs.
 		- \ref MaxWeightedPerfectFractionalMatching
 		  Augmenting path algorithm for calculating maximum weighted
 		  perfect fractional matching in general graphs.
 		\image html matching.png
 		\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
 		*/
 		/**
 		@defgroup graph_properties Connectivity and Other Graph Properties
 		@ingroup algs
 		\brief Algorithms for discovering the graph properties
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html connected_components.png
 		\image latex connected_components.eps "Connected components" width=\textwidth
 		*/
 		/**
-		@defgroup planar Planarity Embedding and Drawing
+		@defgroup planar Planar Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup approx_algs Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		<b>Maximum Clique Problem</b>
 		  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
 		    Grosso, Locatelli, and Pullan.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group LP and MIP Solvers
 		@ingroup gen_opt_group
 		\brief LP and MIP solver interfaces for LEMON.
 		This group contains LP and MIP solver interfaces for LEMON.
 		Various LP solvers could be used in the same manner with this

lemon/capacity_scaling.h

Show inline comments

@@ -44,98 +44,98 @@
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The type of the heap used for internal Dijkstra computations.
 		    ///
 		    /// The type of the heap used for internal Dijkstra computations.
 		    /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
 		    /// its priority type must be \c Cost and its cross reference type
 		    /// must be \ref RangeMap "RangeMap<int>".
 		    typedef BinHeap<Cost, RangeMap<int> > Heap;
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Capacity Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CapacityScaling implements the capacity scaling version
 		  /// of the successive shortest path algorithm for finding a
 		  /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
 		  /// \ref edmondskarp72theoretical. It is an efficient dual
 		  /// solution method.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
 		  /// "CapacityScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  /// \warning This algorithm does not support negative costs for
 		  /// arcs having infinite upper bound.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CapacityScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CapacityScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// The type of the heap used for internal Dijkstra computations
 		    typedef typename TR::Heap Heap;
 		    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
@@ -378,97 +378,97 @@
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CapacityScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_idf[a]] =  map[a];
 		        _cost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CapacityScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CapacityScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param factor The capacity scaling factor. It must be larger than
 		    /// one to use scaling. If it is less or equal to one, then scaling
 		    /// will be disabled.
 		    ///
 		    /// \return \c INFEASIBLE if no feasible flow exists,

lemon/core.h

Show inline comments

@@ -402,97 +402,97 @@
 		          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
 		                                    nodeRefMap[from.target(it)]);
+		        }
+		      }
 		    };
 		    template <typename Digraph>
 		    struct DigraphCopySelector<
 		      Digraph,
 		      typename enable_if<typename Digraph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename ArcRefMap>
 		      static void copy(const From& from, Digraph &to,
 		                       NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
 		        to.build(from, nodeRefMap, arcRefMap);
+		      }
 		    };
 		    template <typename Graph, typename Enable = void>
 		    struct GraphCopySelector {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
 		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        to.clear();
 		        for (typename From::NodeIt it(from); it != INVALID; ++it) {
 		          nodeRefMap[it] = to.addNode();
+		        }
 		        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
 		          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
 		                                      nodeRefMap[from.v(it)]);
+		        }
+		      }
 		    };
 		    template <typename Graph>
 		    struct GraphCopySelector<
 		      Graph,
 		      typename enable_if<typename Graph::BuildTag, void>::type>
+		    {
 		      template <typename From, typename NodeRefMap, typename EdgeRefMap>
 		      static void copy(const From& from, Graph &to,
 		                       NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
 		        to.build(from, nodeRefMap, edgeRefMap);
+		      }
 		    };
+		  }
 		  /// Check whether a graph is undirected.
+		  /// \brief Check whether a graph is undirected.
 		  ///
 		  /// This function returns \c true if the given graph is undirected.
 		#ifdef DOXYGEN
 		  template <typename GR>
 		  bool undirected(const GR& g) { return false; }
 		#else
 		  template <typename GR>
 		  typename enable_if<UndirectedTagIndicator<GR>, bool>::type
 		  undirected(const GR&) {
 		    return true;
+		  }
 		  template <typename GR>
 		  typename disable_if<UndirectedTagIndicator<GR>, bool>::type
 		  undirected(const GR&) {
 		    return false;
+		  }
 		#endif
 		  /// \brief Class to copy a digraph.
 		  ///
 		  /// Class to copy a digraph to another digraph (duplicate a digraph). The
 		  /// simplest way of using it is through the \c digraphCopy() function.
 		  ///
 		  /// This class not only make a copy of a digraph, but it can create
 		  /// references and cross references between the nodes and arcs of
 		  /// the two digraphs, and it can copy maps to use with the newly created
 		  /// digraph.
 		  ///
 		  /// To make a copy from a digraph, first an instance of DigraphCopy
 		  /// should be created, then the data belongs to the digraph should
 		  /// assigned to copy. In the end, the \c run() member should be
 		  /// called.
 		  ///
 		  /// The next code copies a digraph with several data:
 		  ///\code
 		  ///  DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
 		  ///  // Create references for the nodes
 		  ///  OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
 		  ///  cg.nodeRef(nr);
 		  ///  // Create cross references (inverse) for the arcs
 		  ///  NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
 		  ///  cg.arcCrossRef(acr);
 		  ///  // Copy an arc map
 		  ///  OrigGraph::ArcMap<double> oamap(orig_graph);
 		  ///  NewGraph::ArcMap<double> namap(new_graph);
 		  ///  cg.arcMap(oamap, namap);
 		  ///  // Copy a node
 		  ///  OrigGraph::Node on;

lemon/cost_scaling.h

Show inline comments

@@ -52,179 +52,182 @@
 		#endif
 		  struct CostScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The large cost type used for internal computations
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		  };
 		  // Default traits class for integer cost types
 		  template <typename GR, typename V, typename C>
 		  struct CostScalingDefaultTraits<GR, V, C, true>
+		  {
 		    typedef GR Digraph;
 		    typedef V Value;
 		    typedef C Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeCost;
 		#else
 		    typedef long LargeCost;
 		#endif
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Cost Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CostScaling implements a cost scaling algorithm that performs
 		  /// push/augment and relabel operations for finding a \ref min_cost_flow
 		  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
 		  /// \ref goldberg97efficient, \ref bunnagel98efficient.
 		  /// It is a highly efficient primal-dual solution method, which
 		  /// can be viewed as the generalization of the \ref Preflow
 		  /// "preflow push-relabel" algorithm for the maximum flow problem.
 		  ///
 		  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
 		  /// implementations available in LEMON for this problem.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CostScalingDefaultTraits
 		  /// "CostScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  /// \warning This algorithm does not support negative costs for
 		  /// arcs having infinite upper bound.
 		  ///
 		  /// \note %CostScaling provides three different internal methods,
 		  /// from which the most efficient one is used by default.
 		  /// For more information, see \ref Method.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CostScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CostScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// \brief The large cost type
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeCost LargeCost;
 		    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the internal method.
 		    ///
 		    /// Enum type containing constants for selecting the internal method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CostScaling provides three internal methods that differ mainly
 		    /// in their base operations, which are used in conjunction with the
 		    /// relabel operation.
 		    /// By default, the so called \ref PARTIAL_AUGMENT
-		    /// "Partial Augment-Relabel" method is used, which proved to be
+		    /// "Partial Augment-Relabel" method is used, which turned out to be
 		    /// the most efficient and the most robust on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// Local push operations are used, i.e. flow is moved only on one
 		      /// admissible arc at once.
 		      PUSH,
 		      /// Augment operations are used, i.e. flow is moved on admissible
 		      /// paths from a node with excess to a node with deficit.
 		      AUGMENT,
 		      /// Partial augment operations are used, i.e. flow is moved on
 		      /// admissible paths started from a node with excess, but the
 		      /// lengths of these paths are limited. This method can be viewed
 		      /// as a combined version of the previous two operations.
 		      PARTIAL_AUGMENT
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<LargeCost> LargeCostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
@@ -403,97 +406,97 @@
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CostScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _scost[_arc_idf[a]] =  map[a];
 		        _scost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CostScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CostScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param method The internal method that will be used in the
 		    /// algorithm. For more information, see \ref Method.
 		    /// \param factor The cost scaling factor. It must be larger than one.
 		    ///
 		    /// \return \c INFEASIBLE if no feasible flow exists,

lemon/cycle_canceling.h

Show inline comments

@@ -23,147 +23,146 @@
 		/// \file
 		/// \brief Cycle-canceling algorithms for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		#include <lemon/math.h>
 		#include <lemon/static_graph.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/circulation.h>
 		#include <lemon/bellman_ford.h>
 		#include <lemon/howard_mmc.h>
 		namespace lemon {
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of cycle-canceling algorithms for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CycleCanceling implements three different cycle-canceling
 		  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
 		  /// \ref amo93networkflows, \ref klein67primal,
 		  /// \ref goldberg89cyclecanceling.
 		  /// The most efficent one (both theoretically and practically)
 		  /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
 		  /// thus it is the default method.
 		  /// It is strongly polynomial, but in practice, it is typically much
 		  /// slower than the scaling algorithms and NetworkSimplex.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  ///
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  /// \warning This algorithm does not support negative costs for
 		  /// arcs having infinite upper bound.
 		  ///
 		  /// \note For more information about the three available methods,
 		  /// see \ref Method.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C>
 		#else
 		  template <typename GR, typename V = int, typename C = V>
 		#endif
 		  class CycleCanceling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the used method.
 		    ///
 		    /// Enum type containing constants for selecting the used method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CycleCanceling provides three different cycle-canceling
 		    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
 		    /// is used, which proved to be the most efficient and the most robust
 		    /// on various test inputs.
 		    /// is used, which is by far the most efficient and the most robust.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// A simple cycle-canceling method, which uses the
 		      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
 		      /// number for detecting negative cycles in the residual network.
 		      SIMPLE_CYCLE_CANCELING,
 		      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
 		      /// well-known strongly polynomial method
 		      /// \ref goldberg89cyclecanceling. It improves along a
 		      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
 		      /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
 		      MINIMUM_MEAN_CYCLE_CANCELING,
 		      /// The "Cancel And Tighten" algorithm, which can be viewed as an
 		      /// improved version of the previous method
 		      /// \ref goldberg89cyclecanceling.
 		      /// It is faster both in theory and in practice, its running time
 		      /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
 		      CANCEL_AND_TIGHTEN
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<double> DoubleVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
@@ -305,97 +304,97 @@
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CycleCanceling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_idf[a]] =  map[a];
 		        _cost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CycleCanceling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CycleCanceling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CycleCanceling<ListDigraph> cc(graph);
 		    ///   cc.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param method The cycle-canceling method that will be used.
 		    /// For more information, see \ref Method.
 		    ///
 		    /// \return \c INFEASIBLE if no feasible flow exists,
 		    /// \n \c OPTIMAL if the problem has optimal solution

lemon/euler.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_EULER_H
 		#define LEMON_EULER_H
 		#include<lemon/core.h>
 		#include<lemon/adaptors.h>
 		#include<lemon/connectivity.h>
 		#include <list>
 		/// \ingroup graph_properties
 		/// \file
 		/// \brief Euler tour iterators and a function for checking the \e Eulerian
 		/// property.
 		///
 		///This file provides Euler tour iterators and a function to check
 		///if a (di)graph is \e Eulerian.
 		namespace lemon {
 		  ///Euler tour iterator for digraphs.
-		  /// \ingroup graph_prop
+		  /// \ingroup graph_properties
 		  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
 		  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
 		  ///
 		  ///For example, if the given digraph has an Euler tour (i.e it has only one
 		  ///non-trivial component and the in-degree is equal to the out-degree
 		  ///for all nodes), then the following code will put the arcs of \c g
 		  ///to the vector \c et according to an Euler tour of \c g.
 		  ///\code
 		  ///  std::vector<ListDigraph::Arc> et;
 		  ///  for(DiEulerIt<ListDigraph> e(g); e!=INVALID; ++e)
 		  ///    et.push_back(e);
 		  ///\endcode
 		  ///If \c g has no Euler tour, then the resulted walk will not be closed
 		  ///or not contain all arcs.
 		  ///\sa EulerIt
 		  template<typename GR>
 		  class DiEulerIt
+		  {
 		    typedef typename GR::Node Node;
 		    typedef typename GR::NodeIt NodeIt;
 		    typedef typename GR::Arc Arc;
 		    typedef typename GR::ArcIt ArcIt;
 		    typedef typename GR::OutArcIt OutArcIt;
 		    typedef typename GR::InArcIt InArcIt;
 		    const GR &g;
 		    typename GR::template NodeMap<OutArcIt> narc;
 		    std::list<Arc> euler;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///\param gr A digraph.
 		    ///\param start The starting point of the tour. If it is not given,
 		    ///the tour will start from the first node that has an outgoing arc.
 		    DiEulerIt(const GR &gr, typename GR::Node start = INVALID)
 		      : g(gr), narc(g)
+		    {
 		      if (start==INVALID) {
 		        NodeIt n(g);
 		        while (n!=INVALID && OutArcIt(g,n)==INVALID) ++n;
 		        start=n;
+		      }
 		      if (start!=INVALID) {
 		        for (NodeIt n(g); n!=INVALID; ++n) narc[n]=OutArcIt(g,n);
 		        while (narc[start]!=INVALID) {

lemon/grosso_locatelli_pullan_mc.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
 		#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
 		/// \ingroup approx_algs
 		///
 		/// \file
 		/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
 		/// for the maximum clique problem
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/random.h>
 		namespace lemon {
 		  /// \addtogroup approx_algs
 		  /// @{
 		  /// \brief Implementation of the iterated local search algorithm of Grosso,
 		  /// Locatelli, and Pullan for the maximum clique problem
 		  ///
 		  /// \ref GrossoLocatelliPullanMc implements the iterated local search
 		  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
 		  /// \e clique \e problem \ref grosso08maxclique.
 		  /// It is to find the largest complete subgraph (\e clique) in an
 		  /// undirected graph, i.e., the largest set of nodes where each
 		  /// pair of nodes is connected.
 		  ///
 		  /// This class provides a simple but highly efficient and robust heuristic
 		  /// method that quickly finds a large clique, but not necessarily the
+		  /// method that quickly finds a quite large clique, but not necessarily the
 		  /// largest one.
 		  /// The algorithm performs a certain number of iterations to find several
 		  /// cliques and selects the largest one among them. Various limits can be
 		  /// specified to control the running time and the effectiveness of the
 		  /// search process.
 		  ///
 		  /// \tparam GR The undirected graph type the algorithm runs on.
 		  ///
 		  /// \note %GrossoLocatelliPullanMc provides three different node selection
 		  /// rules, from which the most powerful one is used by default.
 		  /// For more information, see \ref SelectionRule.
 		  template <typename GR>
 		  class GrossoLocatelliPullanMc
+		  {
 		  public:
 		    /// \brief Constants for specifying the node selection rule.
 		    ///
 		    /// Enum type containing constants for specifying the node selection rule
 		    /// for the \ref run() function.
 		    ///
 		    /// During the algorithm, nodes are selected for addition to the current
 		    /// clique according to the applied rule.
 		    /// In general, the PENALTY_BASED rule turned out to be the most powerful
 		    /// and the most robust, thus it is the default option.
 		    /// However, another selection rule can be specified using the \ref run()
 		    /// function with the proper parameter.
 		    enum SelectionRule {
 		      /// A node is selected randomly without any evaluation at each step.
 		      RANDOM,
 		      /// A node of maximum degree is selected randomly at each step.
 		      DEGREE_BASED,
 		      /// A node of minimum penalty is selected randomly at each step.
 		      /// The node penalties are updated adaptively after each stage of the
 		      /// search process.
 		      PENALTY_BASED
 		    };
 		    /// \brief Constants for the causes of search termination.
 		    ///
 		    /// Enum type containing constants for the different causes of search
 		    /// termination. The \ref run() function returns one of these values.
 		    enum TerminationCause {
 		      /// The iteration count limit is reached.
 		      ITERATION_LIMIT,
 		      /// The step count limit is reached.
 		      STEP_LIMIT,
 		      /// The clique size limit is reached.
 		      SIZE_LIMIT
 		    };
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<char> BoolVector;
 		    typedef std::vector<BoolVector> BoolMatrix;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		    // The underlying graph
 		    const GR &_graph;
 		    IntNodeMap _id;
 		    // Internal matrix representation of the graph
 		    BoolMatrix _gr;
 		    int _n;
 		    // Search options
 		    bool _delta_based_restart;
 		    int _restart_delta_limit;
 		    // Search limits
 		    int _iteration_limit;
 		    int _step_limit;
 		    int _size_limit;
 		    // The current clique
 		    BoolVector _clique;
 		    int _size;
 		    // The best clique found so far
 		    BoolVector _best_clique;
 		    int _best_size;
 		    // The "distances" of the nodes from the current clique.
 		    // _delta[u] is the number of nodes in the clique that are
 		    // not connected with u.
 		    IntVector _delta;
 		    // The current tabu set
 		    BoolVector _tabu;
 		    // Random number generator
 		    Random _rnd;
 		  private:
 		    // Implementation of the RANDOM node selection rule.
 		    class RandomSelectionRule
+		    {
 		    private:
 		      // References to the algorithm instance
 		      const BoolVector &_clique;
 		      const IntVector  &_delta;
 		      const BoolVector &_tabu;
 		      Random &_rnd;
 		      // Pivot rule data
 		      int _n;
 		    public:
 		      // Constructor
 		      RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
 		        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
 		        _rnd(mc._rnd), _n(mc._n)
 		      {}
 		      // Return a node index for a feasible add move or -1 if no one exists
 		      int nextFeasibleAddNode() const {
 		        int start_node = _rnd[_n];
 		        for (int i = start_node; i != _n; i++) {
@@ -335,346 +365,476 @@
 		            min_p = _penalty[i];
+		          }
+		        }
 		        for (int i = 0; i != start_node; i++) {
 		          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
 		              _penalty[i] < min_p) {
 		            node = i;
 		            min_p = _penalty[i];
+		          }
+		        }
 		        return node;
+		      }
 		      // Return a node index for an add move or -1 if no one exists
 		      int nextAddNode() const {
 		        int start_node = _rnd[_n];
 		        int node = -1, min_p = std::numeric_limits<int>::max();
 		        for (int i = start_node; i != _n; i++) {
 		          if (_delta[i] == 0 && _penalty[i] < min_p) {
 		            node = i;
 		            min_p = _penalty[i];
+		          }
+		        }
 		        for (int i = 0; i != start_node; i++) {
 		          if (_delta[i] == 0 && _penalty[i] < min_p) {
 		            node = i;
 		            min_p = _penalty[i];
+		          }
+		        }
 		        return node;
+		      }
 		      // Update internal data structures between stages (if necessary)
 		      void update() {}
 		    }; //class PenaltyBasedSelectionRule
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// The global \ref rnd "random number generator instance" is used
 		    /// during the algorithm.
 		    ///
 		    /// \param graph The undirected graph the algorithm runs on.
 		    GrossoLocatelliPullanMc(const GR& graph) :
 		      _graph(graph), _id(_graph), _rnd(rnd)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \brief Constructor with random seed.
 		    ///
 		    /// Constructor with random seed.
 		    ///
 		    /// \param graph The undirected graph the algorithm runs on.
 		    /// \param seed Seed value for the internal random number generator
 		    /// that is used during the algorithm.
 		    GrossoLocatelliPullanMc(const GR& graph, int seed) :
 		      _graph(graph), _id(_graph), _rnd(seed)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \brief Constructor with random number generator.
 		    ///
 		    /// Constructor with random number generator.
 		    ///
 		    /// \param graph The undirected graph the algorithm runs on.
 		    /// \param random A random number generator that is used during the
 		    /// algorithm.
 		    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
 		      _graph(graph), _id(_graph), _rnd(random)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \name Execution Control
 		    /// The \ref run() function can be used to execute the algorithm.\n
 		    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
 		    /// \ref sizeLimit(int) can be used to specify various limits for the
 		    /// search process.
 		    /// @{
 		    /// \brief Sets the maximum number of iterations.
 		    ///
 		    /// This function sets the maximum number of iterations.
 		    /// Each iteration of the algorithm finds a maximal clique (but not
 		    /// necessarily the largest one) by performing several search steps
 		    /// (node selections).
 		    ///
 		    /// This limit controls the running time and the success of the
 		    /// algorithm. For larger values, the algorithm runs slower, but it more
 		    /// likely finds larger cliques. For smaller values, the algorithm is
 		    /// faster but probably gives worse results.
 		    ///
 		    /// The default value is \c 1000.
 		    /// \c -1 means that number of iterations is not limited.
 		    ///
 		    /// \warning You should specify a reasonable limit for the number of
 		    /// iterations and/or the number of search steps.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa stepLimit(int)
 		    /// \sa sizeLimit(int)
 		    GrossoLocatelliPullanMc& iterationLimit(int limit) {
 		      _iteration_limit = limit;
 		      return *this;
+		    }
 		    /// \brief Sets the maximum number of search steps.
 		    ///
 		    /// This function sets the maximum number of elementary search steps.
 		    /// Each iteration of the algorithm finds a maximal clique (but not
 		    /// necessarily the largest one) by performing several search steps
 		    /// (node selections).
 		    ///
 		    /// This limit controls the running time and the success of the
 		    /// algorithm. For larger values, the algorithm runs slower, but it more
 		    /// likely finds larger cliques. For smaller values, the algorithm is
 		    /// faster but probably gives worse results.
 		    ///
 		    /// The default value is \c -1, which means that number of steps
 		    /// is not limited explicitly. However, the number of iterations is
 		    /// limited and each iteration performs a finite number of search steps.
 		    ///
 		    /// \warning You should specify a reasonable limit for the number of
 		    /// iterations and/or the number of search steps.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa iterationLimit(int)
 		    /// \sa sizeLimit(int)
 		    GrossoLocatelliPullanMc& stepLimit(int limit) {
 		      _step_limit = limit;
 		      return *this;
+		    }
 		    /// \brief Sets the desired clique size.
 		    ///
 		    /// This function sets the desired clique size that serves as a search
 		    /// limit. If a clique of this size (or a larger one) is found, then the
 		    /// algorithm terminates.
 		    ///
 		    /// This function is especially useful if you know an exact upper bound
 		    /// for the size of the cliques in the graph or if any clique above
 		    /// a certain size limit is sufficient for your application.
 		    ///
 		    /// The default value is \c -1, which means that the size limit is set to
 		    /// the number of nodes in the graph.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa iterationLimit(int)
 		    /// \sa stepLimit(int)
 		    GrossoLocatelliPullanMc& sizeLimit(int limit) {
 		      _size_limit = limit;
 		      return *this;
+		    }
 		    /// \brief The maximum number of iterations.
 		    ///
 		    /// This function gives back the maximum number of iterations.
 		    /// \c -1 means that no limit is specified.
 		    ///
 		    /// \sa iterationLimit(int)
 		    int iterationLimit() const {
 		      return _iteration_limit;
+		    }
 		    /// \brief The maximum number of search steps.
 		    ///
 		    /// This function gives back the maximum number of search steps.
 		    /// \c -1 means that no limit is specified.
 		    ///
 		    /// \sa stepLimit(int)
 		    int stepLimit() const {
 		      return _step_limit;
+		    }
 		    /// \brief The desired clique size.
 		    ///
 		    /// This function gives back the desired clique size that serves as a
 		    /// search limit. \c -1 means that this limit is set to the number of
 		    /// nodes in the graph.
 		    ///
 		    /// \sa sizeLimit(int)
 		    int sizeLimit() const {
 		      return _size_limit;
+		    }
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// This function runs the algorithm.
+		    /// This function runs the algorithm. If one of the specified limits
 		    /// is reached, the search process terminates.
 		    ///
 		    /// \param step_num The maximum number of node selections (steps)
 		    /// during the search process.
 		    /// This parameter controls the running time and the success of the
 		    /// algorithm. For larger values, the algorithm runs slower but it more
 		    /// likely finds larger cliques. For smaller values, the algorithm is
 		    /// faster but probably gives worse results.
 		    /// \param rule The node selection rule. For more information, see
 		    /// \ref SelectionRule.
 		    ///
 		    /// \return The size of the found clique.
 		    int run(int step_num = 100000,
-		            SelectionRule rule = PENALTY_BASED)
+		    /// \return The termination cause of the search. For more information,
 		    /// see \ref TerminationCause.
 		    TerminationCause run(SelectionRule rule = PENALTY_BASED)
+		    {
 		      init();
 		      switch (rule) {
 		        case RANDOM:
-		          return start<RandomSelectionRule>(step_num);
 		          return start<RandomSelectionRule>();
 		        case DEGREE_BASED:
 		          return start<DegreeBasedSelectionRule>(step_num);
 		        case PENALTY_BASED:
-		          return start<PenaltyBasedSelectionRule>(step_num);
+		          return start<DegreeBasedSelectionRule>();
 		        default:
 		          return start<PenaltyBasedSelectionRule>();
+		      }
 		      return 0; // avoid warning
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these functions.\n
 		    /// The run() function must be called before using them.
 		    /// @{
 		    /// \brief The size of the found clique
 		    ///
 		    /// This function returns the size of the found clique.
 		    ///
 		    /// \pre run() must be called before using this function.
 		    int cliqueSize() const {
 		      return _best_size;
+		    }
 		    /// \brief Gives back the found clique in a \c bool node map
 		    ///
 		    /// This function gives back the characteristic vector of the found
 		    /// clique in the given node map.
 		    /// It must be a \ref concepts::WriteMap "writable" node map with
 		    /// \c bool (or convertible) value type.
 		    ///
 		    /// \pre run() must be called before using this function.
 		    template <typename CliqueMap>
 		    void cliqueMap(CliqueMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map[n] = static_cast<bool>(_best_clique[_id[n]]);
+		      }
+		    }
 		    /// \brief Iterator to list the nodes of the found clique
 		    ///
 		    /// This iterator class lists the nodes of the found clique.
 		    /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
 		    /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
 		    ///
 		    /// The following example prints out the IDs of the nodes in the found
 		    /// clique.
 		    /// \code
 		    ///   GrossoLocatelliPullanMc<Graph> mc(g);
 		    ///   mc.run();
 		    ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
 		    ///        n != INVALID; ++n)
 		    ///   {
 		    ///     std::cout << g.id(n) << std::endl;
 		    ///   }
 		    /// \endcode
 		    class CliqueNodeIt
+		    {
 		    private:
 		      NodeIt _it;
 		      BoolNodeMap _map;
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      /// \param mc The algorithm instance.
 		      CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
 		       : _map(mc._graph)
+		      {
 		        mc.cliqueMap(_map);
 		        for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
+		      }
 		      /// Conversion to \c Node
 		      operator Node() const { return _it; }
 		      bool operator==(Invalid) const { return _it == INVALID; }
 		      bool operator!=(Invalid) const { return _it != INVALID; }
 		      /// Next node
 		      CliqueNodeIt &operator++() {
 		        for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation returns a \c Node, not a
 		      /// \c CliqueNodeIt as one may expect.
 		      typename GR::Node operator++(int) {
 		        Node n=*this;
 		        ++(*this);
 		        return n;
+		      }
 		    };
 		    /// @}
 		  private:
 		    // Initialize search options and limits
 		    void initOptions() {
 		      // Search options
 		      _delta_based_restart = true;
 		      _restart_delta_limit = 4;
 		      // Search limits
 		      _iteration_limit = 1000;
 		      _step_limit = -1;             // this is disabled by default
 		      _size_limit = -1;             // this is disabled by default
+		    }
 		    // Adds a node to the current clique
 		    void addCliqueNode(int u) {
 		      if (_clique[u]) return;
 		      _clique[u] = true;
 		      _size++;
 		      BoolVector &row = _gr[u];
 		      for (int i = 0; i != _n; i++) {
 		        if (!row[i]) _delta[i]++;
+		      }
+		    }
 		    // Removes a node from the current clique
 		    void delCliqueNode(int u) {
 		      if (!_clique[u]) return;
 		      _clique[u] = false;
 		      _size--;
 		      BoolVector &row = _gr[u];
 		      for (int i = 0; i != _n; i++) {
 		        if (!row[i]) _delta[i]--;
+		      }
+		    }
 		    // Initialize data structures
 		    void init() {
 		      _n = countNodes(_graph);
 		      int ui = 0;
 		      for (NodeIt u(_graph); u != INVALID; ++u) {
 		        _id[u] = ui++;
+		      }
 		      _gr.clear();
 		      _gr.resize(_n, BoolVector(_n, false));
 		      ui = 0;
 		      for (NodeIt u(_graph); u != INVALID; ++u) {
 		        for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
 		          int vi = _id[_graph.runningNode(e)];
 		          _gr[ui][vi] = true;
 		          _gr[vi][ui] = true;
+		        }
 		        ++ui;
+		      }
 		      _clique.clear();
 		      _clique.resize(_n, false);
 		      _size = 0;
 		      _best_clique.clear();
 		      _best_clique.resize(_n, false);
 		      _best_size = 0;
 		      _delta.clear();
 		      _delta.resize(_n, 0);
 		      _tabu.clear();
 		      _tabu.resize(_n, false);
+		    }
 		    // Executes the algorithm
 		    template <typename SelectionRuleImpl>
 		    int start(int max_select) {
 		      // Options for the restart rule
 		      const bool delta_based_restart = true;
 		      const int restart_delta_limit = 4;
 		      if (_n == 0) return 0;
 		    TerminationCause start() {
 		      if (_n == 0) return SIZE_LIMIT;
 		      if (_n == 1) {
 		        _best_clique[0] = true;
 		        _best_size = 1;
-		        return _best_size;
+		        return SIZE_LIMIT;
+		      }
 		      // Iterated local search
+		      // Iterated local search algorithm
 		      const int max_size = _size_limit >= 0 ? _size_limit : _n;
 		      const int max_restart = _iteration_limit >= 0 ?
 		        _iteration_limit : std::numeric_limits<int>::max();
 		      const int max_select = _step_limit >= 0 ?
 		        _step_limit : std::numeric_limits<int>::max();
 		      SelectionRuleImpl sel_method(*this);
 		      int select = 0;
+		      int select = 0, restart = 0;
 		      IntVector restart_nodes;
 		      while (select < max_select) {
 		      while (select < max_select && restart < max_restart) {
 		        // Perturbation/restart
-		        if (delta_based_restart) {
+		        restart++;
 		        if (_delta_based_restart) {
 		          restart_nodes.clear();
 		          for (int i = 0; i != _n; i++) {
-		            if (_delta[i] >= restart_delta_limit)
+		            if (_delta[i] >= _restart_delta_limit)
 		              restart_nodes.push_back(i);
+		          }
+		        }
 		        int rs_node = -1;
 		        if (restart_nodes.size() > 0) {
 		          rs_node = restart_nodes[_rnd[restart_nodes.size()]];
 		        } else {
 		          rs_node = _rnd[_n];
+		        }
 		        BoolVector &row = _gr[rs_node];
 		        for (int i = 0; i != _n; i++) {
 		          if (_clique[i] && !row[i]) delCliqueNode(i);
+		        }
 		        addCliqueNode(rs_node);
 		        // Local search
 		        _tabu.clear();
 		        _tabu.resize(_n, false);
 		        bool tabu_empty = true;
 		        int max_swap = _size;
 		        while (select < max_select) {
 		          select++;
 		          int u;
 		          if ((u = sel_method.nextFeasibleAddNode()) != -1) {
 		            // Feasible add move
 		            addCliqueNode(u);
 		            if (tabu_empty) max_swap = _size;
+		          }
 		          else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
 		            // Feasible swap move
 		            int v = -1;
 		            BoolVector &row = _gr[u];
 		            for (int i = 0; i != _n; i++) {
 		              if (_clique[i] && !row[i]) {
 		                v = i;
 		                break;
+		              }
+		            }
 		            addCliqueNode(u);
 		            delCliqueNode(v);
 		            _tabu[v] = true;
 		            tabu_empty = false;
 		            if (--max_swap <= 0) break;
+		          }
 		          else if ((u = sel_method.nextAddNode()) != -1) {
 		            // Non-feasible add move
 		            addCliqueNode(u);
+		          }
 		          else break;
+		        }
 		        if (_size > _best_size) {
 		          _best_clique = _clique;
 		          _best_size = _size;
-		          if (_best_size == _n) return _best_size;
+		          if (_best_size >= max_size) return SIZE_LIMIT;
+		        }
 		        sel_method.update();
+		      }
-		      return _best_size;
+		      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
+		    }
 		  }; //class GrossoLocatelliPullanMc
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H

lemon/network_simplex.h

Show inline comments

@@ -2,218 +2,218 @@
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_NETWORK_SIMPLEX_H
 		#define LEMON_NETWORK_SIMPLEX_H
 		/// \ingroup min_cost_flow_algs
 		///
 		/// \file
 		/// \brief Network Simplex algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <algorithm>
 		#include <lemon/core.h>
 		#include <lemon/math.h>
 		namespace lemon {
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
 		  /// for finding a \ref min_cost_flow "minimum cost flow"
 		  /// \ref amo93networkflows, \ref dantzig63linearprog,
 		  /// \ref kellyoneill91netsimplex.
 		  /// This algorithm is a highly efficient specialized version of the
 		  /// linear programming simplex method directly for the minimum cost
 		  /// flow problem.
 		  ///
 		  /// In general, %NetworkSimplex is the fastest implementation available
 		  /// in LEMON for this problem.
 		  /// Moreover, it supports both directions of the supply/demand inequality
 		  /// constraints. For more information, see \ref SupplyType.
 		  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
 		  /// implementations available in LEMON for this problem.
 		  /// Furthermore, this class supports both directions of the supply/demand
 		  /// inequality constraints. For more information, see \ref SupplyType.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  ///
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  ///
 		  /// \note %NetworkSimplex provides five different pivot rule
 		  /// implementations, from which the most efficient one is used
 		  /// by default. For more information, see \ref PivotRule.
 		  template <typename GR, typename V = int, typename C = V>
 		  class NetworkSimplex
+		  {
 		  public:
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The objective function of the problem is unbounded, i.e.
 		      /// there is a directed cycle having negative total cost and
 		      /// infinite upper bound.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the type of the supply constraints.
 		    ///
 		    /// Enum type containing constants for selecting the supply type,
 		    /// i.e. the direction of the inequalities in the supply/demand
 		    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
 		    ///
 		    /// The default supply type is \c GEQ, the \c LEQ type can be
 		    /// selected using \ref supplyType().
 		    /// The equality form is a special case of both supply types.
 		    enum SupplyType {
 		      /// This option means that there are <em>"greater or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      GEQ,
 		      /// This option means that there are <em>"less or equal"</em>
 		      /// supply/demand constraints in the definition of the problem.
 		      LEQ
 		    };
 		    /// \brief Constants for selecting the pivot rule.
 		    ///
 		    /// Enum type containing constants for selecting the pivot rule for
 		    /// the \ref run() function.
 		    ///
 		    /// \ref NetworkSimplex provides five different pivot rule
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
 		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
-		    /// proved to be the most efficient and the most robust on various
+		    /// turend out to be the most efficient and the most robust on various
 		    /// test inputs.
 		    /// However, another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The \e First \e Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The \e Best \e Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The \e Block \e Search pivot rule.
 		      /// A specified number of arcs are examined in every iteration
 		      /// in a wraparound fashion and the best eligible arc is selected
 		      /// from this block.
 		      BLOCK_SEARCH,
 		      /// The \e Candidate \e List pivot rule.
 		      /// In a major iteration a candidate list is built from eligible arcs
 		      /// in a wraparound fashion and in the following minor iterations
 		      /// the best eligible arc is selected from this list.
 		      CANDIDATE_LIST,
 		      /// The \e Altering \e Candidate \e List pivot rule.
 		      /// It is a modified version of the Candidate List method.
 		      /// It keeps only the several best eligible arcs from the former
 		      /// candidate list and extends this list in every iteration.
 		      ALTERING_LIST
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<signed char> CharVector;
-		    // Note: vector<signed char> is used instead of vector<ArcState> and
 		    // Note: vector<signed char> is used instead of vector<ArcState> and
 		    // vector<ArcDirection> for efficiency reasons
 		    // State constants for arcs
 		    enum ArcState {
 		      STATE_UPPER = -1,
 		      STATE_TREE  =  0,
 		      STATE_LOWER =  1
 		    };
 		    // Direction constants for tree arcs
 		    enum ArcDirection {
 		      DIR_DOWN = -1,
 		      DIR_UP   =  1
 		    };
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _all_arc_num;
 		    int _search_arc_num;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    SupplyType _stype;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_id;
 		    IntVector _source;
 		    IntVector _target;
 		    bool _arc_mixing;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    ValueVector _cap;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _flow;
 		    CostVector _pi;
 		    // Data for storing the spanning tree structure
 		    IntVector _parent;
 		    IntVector _pred;
@@ -690,113 +690,115 @@
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// If it is not used before calling \ref run(), the upper bounds
 		    /// will be set to \ref INF on all arcs (i.e. the flow value will be
 		    /// unbounded from above).
 		    ///
 		    /// \param map An arc map storing the upper bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename UpperMap>
 		    NetworkSimplex& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_id[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    NetworkSimplex& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _cost[_arc_id[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa supplyType()
 		    template<typename SupplyMap>
 		    NetworkSimplex& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// \brief Set the type of the supply constraints.
 		    ///
 		    /// This function sets the type of the supply/demand constraints.
 		    /// If it is not used before calling \ref run(), the \ref GEQ supply
 		    /// type will be used.
 		    ///
 		    /// For more information, see \ref SupplyType.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& supplyType(SupplyType supply_type) {
 		      _stype = supply_type;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution Control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
 		    /// \ref supplyType().
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)

lemon/path.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup paths
 		///\file
 		///\brief Classes for representing paths in digraphs.
 		///
 		#ifndef LEMON_PATH_H
 		#define LEMON_PATH_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/error.h>
 		#include <lemon/core.h>
 		#include <lemon/concepts/path.h>
 		namespace lemon {
 		  /// \addtogroup paths
 		  /// @{
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence, it
+		  /// LEMON path type stores just this list. As a consequence, it
 		  /// cannot enumerate the nodes of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(1) time. The front and back
 		  /// insertion and erase is done in O(1) (amortized) time. The
 		  /// implementation uses two vectors for storing the front and back
 		  /// insertions.
 		  template <typename GR>
 		  class Path {
 		  public:
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    Path() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This constuctor initializes the path from any other path type.
 		    /// It simply makes a copy of the given path.
 		    template <typename CPath>
 		    Path(const CPath& cpath) {
 		      pathCopy(cpath, *this);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This operator makes a copy of a path of any other type.
 		    template <typename CPath>
 		    Path& operator=(const CPath& cpath) {
 		      pathCopy(cpath, *this);
 		      return *this;
+		    }
 		    /// \brief LEMON style iterator for path arcs
 		    ///
 		    /// This class is used to iterate on the arcs of the paths.
 		    class ArcIt {
 		      friend class Path;
 		    public:
 		      /// \brief Default constructor
 		      ArcIt() {}
 		      /// \brief Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the iterator to the first arc of path
 		      ArcIt(const Path &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      ArcIt(const Path &_path, int _idx)
 		        : path(&_path), idx(_idx) {}
 		    public:
 		      /// \brief Conversion to Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// \brief Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// \brief Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// \brief Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// \brief Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const Path *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return head.size() + tail.size(); }
 		    /// \brief Return whether the path is empty.
 		    bool empty() const { return head.empty() && tail.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      return n < int(head.size()) ? *(head.rbegin() + n) :
 		        *(tail.begin() + (n - head.size()));
+		    }
-		    /// \brief Initialize arc iterator to point to the nth arc
+		    /// \brief Initialize arc iterator to point to the n-th arc
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return head.empty() ? tail.front() : head.back();
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      head.push_back(arc);
+		    }
 		    /// \brief Erase the first arc of the path
 		    void eraseFront() {
 		      if (!head.empty()) {
 		        head.pop_back();
 		      } else {
 		        head.clear();
 		        int halfsize = tail.size() / 2;
 		        head.resize(halfsize);
 		        std::copy(tail.begin() + 1, tail.begin() + halfsize + 1,
 		                  head.rbegin());
 		        std::copy(tail.begin() + halfsize + 1, tail.end(), tail.begin());
 		        tail.resize(tail.size() - halfsize - 1);
+		      }
+		    }
 		    /// \brief The last arc of the path
 		    const Arc& back() const {
 		      return tail.empty() ? head.front() : tail.back();
+		    }
 		    /// \brief Add a new arc behind the current path
 		    void addBack(const Arc& arc) {
 		      tail.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      if (!tail.empty()) {
 		        tail.pop_back();
 		      } else {
 		        int halfsize = head.size() / 2;
 		        tail.resize(halfsize);
 		        std::copy(head.begin() + 1, head.begin() + halfsize + 1,
 		                  tail.rbegin());
 		        std::copy(head.begin() + halfsize + 1, head.end(), head.begin());
 		        head.resize(head.size() - halfsize - 1);
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      tail.reserve(len);
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        tail.push_back(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      head.reserve(len);
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        head.push_back(it);
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container head, tail;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
 		  /// This implementation is a just back insertable and erasable path
 		  /// type. It can be indexed in O(1) time. The back insertion and
 		  /// erasure is amortized O(1) time. This implementation is faster
 		  /// then the \c Path type because it use just one vector for the
 		  /// arcs.
 		  template <typename GR>
 		  class SimplePath {
 		  public:
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    SimplePath() {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath(const CPath& cpath) {
 		      pathCopy(cpath, *this);
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    SimplePath& operator=(const CPath& cpath) {
 		      pathCopy(cpath, *this);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class SimplePath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const SimplePath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const SimplePath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const SimplePath *path;
 		      int idx;
 		    };
 		    /// \brief Length of the path.
 		    int length() const { return data.size(); }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return data.empty(); }
 		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
-		    /// \brief  Initializes arc iterator to point to the nth arc.
+		    /// \brief  Initializes arc iterator to point to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return data.front();
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return data.back();
+		    }
 		    /// \brief Add a new arc behind the current path.
 		    void addBack(const Arc& arc) {
 		      data.push_back(arc);
+		    }
 		    /// \brief Erase the last arc of the path
 		    void eraseBack() {
 		      data.pop_back();
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        data[index] = it;;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      int len = path.length();
 		      data.resize(len);
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
 		        data[index] = it;;
+		      }
+		    }
 		  protected:
 		    typedef std::vector<Arc> Container;
 		    Container data;
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
 		  /// This implementation is a back and front insertable and erasable
 		  /// path type. It can be indexed in O(k) time, where k is the rank
 		  /// of the arc in the path. The length can be computed in O(n)
 		  /// time. The front and back insertion and erasure is O(1) time
 		  /// and it can be splited and spliced in O(1) time.
 		  template <typename GR>
 		  class ListPath {
 		  public:
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		  protected:
 		    // the std::list<> is incompatible
 		    // hard to create invalid iterator
 		    struct Node {
 		      Arc arc;
 		      Node *next, *prev;
 		    };
 		    Node *first, *last;
 		    std::allocator<Node> alloc;
 		  public:
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    ListPath() : first(0), last(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized with any other path type. It just
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    ListPath(const CPath& cpath) : first(0), last(0) {
 		      pathCopy(cpath, *this);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~ListPath() {
@@ -459,109 +459,109 @@
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class ListPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), node(0) {}
 		      /// \brief Initializate the constructor to the first arc of path
 		      ArcIt(const ListPath &_path)
 		        : path(&_path), node(_path.first) {}
 		    protected:
 		      ArcIt(const ListPath &_path, Node *_node)
 		        : path(&_path), node(_node) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return node->arc;
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        node = node->next;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return node==e.node; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return node!=e.node; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return node<e.node; }
 		    private:
 		      const ListPath *path;
 		      Node *node;
 		    };
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
-		    /// This function looks for the nth arc in O(n) time.
+		    /// This function looks for the n-th arc in O(n) time.
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return node->arc;
+		    }
-		    /// \brief Initializes arc iterator to point to the nth arc.
+		    /// \brief Initializes arc iterator to point to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
 		        node = node->next;
+		      }
 		      return ArcIt(*this, node);
+		    }
 		    /// \brief Length of the path.
 		    int length() const {
 		      int len = 0;
 		      Node *node = first;
 		      while (node != 0) {
 		        node = node->next;
 		        ++len;
+		      }
 		      return len;
+		    }
 		    /// \brief Return true if the path is empty.
 		    bool empty() const { return first == 0; }
 		    /// \brief Reset the path to an empty one.
 		    void clear() {
 		      while (first != 0) {
 		        last = first->next;
 		        alloc.destroy(first);
 		        alloc.deallocate(first, 1);
 		        first = last;
+		      }
+		    }
 		    /// \brief The first arc of the path
 		    const Arc& front() const {
 		      return first->arc;
+		    }
 		    /// \brief Add a new arc before the current path
 		    void addFront(const Arc& arc) {
 		      Node *node = alloc.allocate(1);
 		      alloc.construct(node, Node());
 		      node->prev = 0;
 		      node->next = first;
 		      node->arc = arc;
 		      if (first) {
 		        first->prev = node;
 		        first = node;
 		      } else {
@@ -690,200 +690,200 @@
 		    ///
 		    /// It splits the current path into two parts. The part before
 		    /// the iterator \c it will remain in the current path and the part
 		    /// starting with
 		    /// \c it will put into \c tpath. If \c tpath have arcs
 		    /// before the operation they are removed first.  The time
 		    /// complexity of this function is O(1) plus the the time of emtying
 		    /// \c tpath. If \c it is \c INVALID then it just clears \c tpath
 		    void split(ArcIt it, ListPath& tpath) {
 		      tpath.clear();
 		      if (it.node) {
 		        tpath.first = it.node;
 		        tpath.last = last;
 		        if (it.node->prev) {
 		          last = it.node->prev;
 		          last->next = 0;
 		        } else {
 		          first = last = 0;
+		        }
 		        it.node->prev = 0;
+		      }
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        addBack(it);
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        addFront(it);
+		      }
+		    }
 		  };
 		  /// \brief A structure for representing directed paths in a digraph.
 		  ///
 		  /// A structure for representing directed path in a digraph.
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
 		  /// This implementation is completly static, i.e. it can be copy constucted
 		  /// or copy assigned from another path, but otherwise it cannot be
 		  /// modified.
 		  ///
 		  /// Being the the most memory efficient path type in LEMON,
 		  /// it is intented to be
 		  /// used when you want to store a large number of paths.
 		  template <typename GR>
 		  class StaticPath {
 		  public:
 		    typedef GR Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    /// \brief Default constructor
 		    ///
 		    /// Default constructor
 		    StaticPath() : len(0), arcs(0) {}
 		    /// \brief Template copy constructor
 		    ///
 		    /// This path can be initialized from any other path type.
 		    template <typename CPath>
 		    StaticPath(const CPath& cpath) : arcs(0) {
 		      pathCopy(cpath, *this);
+		    }
 		    /// \brief Destructor of the path
 		    ///
 		    /// Destructor of the path
 		    ~StaticPath() {
 		      if (arcs) delete[] arcs;
+		    }
 		    /// \brief Template copy assignment
 		    ///
 		    /// This path can be made equal to any other path type. It simply
 		    /// makes a copy of the given path.
 		    template <typename CPath>
 		    StaticPath& operator=(const CPath& cpath) {
 		      pathCopy(cpath, *this);
 		      return *this;
+		    }
 		    /// \brief Iterator class to iterate on the arcs of the paths
 		    ///
 		    /// This class is used to iterate on the arcs of the paths
 		    ///
 		    /// Of course it converts to Digraph::Arc
 		    class ArcIt {
 		      friend class StaticPath;
 		    public:
 		      /// Default constructor
 		      ArcIt() {}
 		      /// Invalid constructor
 		      ArcIt(Invalid) : path(0), idx(-1) {}
 		      /// Initializate the constructor to the first arc of path
 		      ArcIt(const StaticPath &_path)
 		        : path(&_path), idx(_path.empty() ? -1 : 0) {}
 		    private:
 		      /// Constructor with starting point
 		      ArcIt(const StaticPath &_path, int _idx)
 		        : idx(_idx), path(&_path) {}
 		    public:
 		      ///Conversion to Digraph::Arc
 		      operator const Arc&() const {
 		        return path->nth(idx);
+		      }
 		      /// Next arc
 		      ArcIt& operator++() {
 		        ++idx;
 		        if (idx >= path->length()) idx = -1;
 		        return *this;
+		      }
 		      /// Comparison operator
 		      bool operator==(const ArcIt& e) const { return idx==e.idx; }
 		      /// Comparison operator
 		      bool operator!=(const ArcIt& e) const { return idx!=e.idx; }
 		      /// Comparison operator
 		      bool operator<(const ArcIt& e) const { return idx<e.idx; }
 		    private:
 		      const StaticPath *path;
 		      int idx;
 		    };
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      return arcs[n];
+		    }
-		    /// \brief The arc iterator pointing to the nth arc.
+		    /// \brief The arc iterator pointing to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
 		    /// \brief The length of the path.
 		    int length() const { return len; }
 		    /// \brief Return true when the path is empty.
 		    int empty() const { return len == 0; }
 		    /// \brief Erase all arcs in the digraph.
 		    void clear() {
 		      len = 0;
 		      if (arcs) delete[] arcs;
 		      arcs = 0;
+		    }
 		    /// \brief The first arc of the path.
 		    const Arc& front() const {
 		      return arcs[0];
+		    }
 		    /// \brief The last arc of the path.
 		    const Arc& back() const {
 		      return arcs[len - 1];
+		    }
 		    typedef True BuildTag;
 		    template <typename CPath>
 		    void build(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = 0;
 		      for (typename CPath::ArcIt it(path); it != INVALID; ++it) {
 		        arcs[index] = it;
 		        ++index;
+		      }
+		    }
 		    template <typename CPath>
 		    void buildRev(const CPath& path) {
 		      len = path.length();
 		      arcs = new Arc[len];
 		      int index = len;
 		      for (typename CPath::RevArcIt it(path); it != INVALID; ++it) {
 		        --index;
@@ -997,97 +997,97 @@
 		  /// \brief Deprecated version of \ref pathCopy().
 		  ///
 		  /// Deprecated version of \ref pathCopy() (only for reverse compatibility).
 		  template <typename To, typename From>
 		  void copyPath(To& to, const From& from) {
 		    pathCopy(from, to);
+		  }
 		  /// \brief Check the consistency of a path.
 		  ///
 		  /// This function checks that the target of each arc is the same
 		  /// as the source of the next one.
 		  ///
 		  template <typename Digraph, typename Path>
 		  bool checkPath(const Digraph& digraph, const Path& path) {
 		    typename Path::ArcIt it(path);
 		    if (it == INVALID) return true;
 		    typename Digraph::Node node = digraph.target(it);
 		    ++it;
 		    while (it != INVALID) {
 		      if (digraph.source(it) != node) return false;
 		      node = digraph.target(it);
 		      ++it;
+		    }
 		    return true;
+		  }
 		  /// \brief The source of a path
 		  ///
 		  /// This function returns the source node of the given path.
 		  /// If the path is empty, then it returns \c INVALID.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathSource(const Digraph& digraph, const Path& path) {
 		    return path.empty() ? INVALID : digraph.source(path.front());
+		  }
 		  /// \brief The target of a path
 		  ///
 		  /// This function returns the target node of the given path.
 		  /// If the path is empty, then it returns \c INVALID.
 		  template <typename Digraph, typename Path>
 		  typename Digraph::Node pathTarget(const Digraph& digraph, const Path& path) {
 		    return path.empty() ? INVALID : digraph.target(path.back());
+		  }
 		  /// \brief Class which helps to iterate through the nodes of a path
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores only this list. As a consequence, it
+		  /// LEMON path type stores only this list. As a consequence, it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot have a source node.
 		  ///
 		  /// This class implements the node iterator of a path structure. To
 		  /// provide this feature, the underlying digraph should be passed to
 		  /// the constructor of the iterator.
 		  template <typename Path>
 		  class PathNodeIt {
 		  private:
 		    const typename Path::Digraph *_digraph;
 		    typename Path::ArcIt _it;
 		    typename Path::Digraph::Node _nd;
 		  public:
 		    typedef typename Path::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    /// Default constructor
 		    PathNodeIt() {}
 		    /// Invalid constructor
 		    PathNodeIt(Invalid)
 		      : _digraph(0), _it(INVALID), _nd(INVALID) {}
 		    /// Constructor
 		    PathNodeIt(const Digraph& digraph, const Path& path)
 		      : _digraph(&digraph), _it(path) {
 		      _nd = (_it != INVALID ? _digraph->source(_it) : INVALID);
+		    }
 		    /// Constructor
 		    PathNodeIt(const Digraph& digraph, const Path& path, const Node& src)
 		      : _digraph(&digraph), _it(path), _nd(src) {}
 		    ///Conversion to Digraph::Node
 		    operator Node() const {
 		      return _nd;
+		    }
 		    /// Next node
 		    PathNodeIt& operator++() {
 		      if (_it == INVALID) _nd = INVALID;
 		      else {
 		        _nd = _digraph->target(_it);
 		        ++_it;
+		      }
 		      return *this;
+		    }
 		    /// Comparison operator

test/max_clique_test.cc

Show inline comments

@@ -13,164 +13,176 @@
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#include <sstream>
 		#include <lemon/list_graph.h>
 		#include <lemon/full_graph.h>
 		#include <lemon/grid_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/grosso_locatelli_pullan_mc.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label max_clique\n"
 		  "1     0\n"
 		  "2     0\n"
 		  "3     0\n"
 		  "4     1\n"
 		  "5     1\n"
 		  "6     1\n"
 		  "7     1\n"
 		  "@edges\n"
 		  "    label\n"
 		  "1 2     1\n"
 		  "1 3     2\n"
 		  "1 4     3\n"
 		  "1 6     4\n"
 		  "2 3     5\n"
 		  "2 5     6\n"
 		  "2 7     7\n"
 		  "3 4     8\n"
 		  "3 5     9\n"
 		  "4 5    10\n"
 		  "4 6    11\n"
 		  "4 7    12\n"
 		  "5 6    13\n"
 		  "5 7    14\n"
 		  "6 7    15\n";
 		// Check with general graphs
 		template <typename Param>
-		void checkMaxCliqueGeneral(int max_sel, Param rule) {
 		void checkMaxCliqueGeneral(Param rule) {
 		  typedef ListGraph GR;
 		  typedef GrossoLocatelliPullanMc<GR> McAlg;
 		  typedef McAlg::CliqueNodeIt CliqueIt;
 		  // Basic tests
+		  {
 		    GR g;
 		    GR::NodeMap<bool> map(g);
 		    McAlg mc(g);
-		    check(mc.run(max_sel, rule) == 0, "Wrong clique size");
+		    mc.iterationLimit(50);
 		    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == 0, "Wrong clique size");
 		    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
 		    GR::Node u = g.addNode();
-		    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
+		    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == 1, "Wrong clique size");
 		    mc.cliqueMap(map);
 		    check(map[u], "Wrong clique map");
 		    CliqueIt it1(mc);
 		    check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
 		          "Wrong CliqueNodeIt");
 		    GR::Node v = g.addNode();
-		    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
+		    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == 1, "Wrong clique size");
 		    mc.cliqueMap(map);
 		    check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
 		    CliqueIt it2(mc);
 		    check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
 		    g.addEdge(u, v);
-		    check(mc.run(max_sel, rule) == 2, "Wrong clique size");
+		    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == 2, "Wrong clique size");
 		    mc.cliqueMap(map);
 		    check(map[u] && map[v], "Wrong clique map");
 		    CliqueIt it3(mc);
 		    check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
 		          "Wrong CliqueNodeIt");
+		  }
 		  // Test graph
+		  {
 		    GR g;
 		    GR::NodeMap<bool> max_clique(g);
 		    GR::NodeMap<bool> map(g);
 		    std::istringstream input(test_lgf);
 		    graphReader(g, input)
 		      .nodeMap("max_clique", max_clique)
 		      .run();
 		    McAlg mc(g);
-		    check(mc.run(max_sel, rule) == 4, "Wrong clique size");
+		    mc.iterationLimit(50);
 		    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == 4, "Wrong clique size");
 		    mc.cliqueMap(map);
 		    for (GR::NodeIt n(g); n != INVALID; ++n) {
 		      check(map[n] == max_clique[n], "Wrong clique map");
+		    }
 		    int cnt = 0;
 		    for (CliqueIt n(mc); n != INVALID; ++n) {
 		      cnt++;
 		      check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
+		    }
 		    check(cnt == 4, "Wrong CliqueNodeIt");
+		  }
+		}
 		// Check with full graphs
 		template <typename Param>
-		void checkMaxCliqueFullGraph(int max_sel, Param rule) {
 		void checkMaxCliqueFullGraph(Param rule) {
 		  typedef FullGraph GR;
 		  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
 		  typedef McAlg::CliqueNodeIt CliqueIt;
 		  for (int size = 0; size <= 40; size = size * 3 + 1) {
 		    GR g(size);
 		    GR::NodeMap<bool> map(g);
 		    McAlg mc(g);
-		    check(mc.run(max_sel, rule) == size, "Wrong clique size");
+		    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    check(mc.cliqueSize() == size, "Wrong clique size");
 		    mc.cliqueMap(map);
 		    for (GR::NodeIt n(g); n != INVALID; ++n) {
 		      check(map[n], "Wrong clique map");
+		    }
 		    int cnt = 0;
 		    for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
 		    check(cnt == size, "Wrong CliqueNodeIt");
+		  }
+		}
 		// Check with grid graphs
 		template <typename Param>
-		void checkMaxCliqueGridGraph(int max_sel, Param rule) {
 		void checkMaxCliqueGridGraph(Param rule) {
 		  GridGraph g(5, 7);
 		  GridGraph::NodeMap<char> map(g);
 		  GrossoLocatelliPullanMc<GridGraph> mc(g);
-		  check(mc.run(max_sel, rule) == 2, "Wrong clique size");
 		  mc.iterationLimit(100);
 		  check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
 		  check(mc.cliqueSize() == 2, "Wrong clique size");
 		  mc.stepLimit(100);
 		  check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
 		  check(mc.cliqueSize() == 2, "Wrong clique size");
 		  mc.sizeLimit(2);
 		  check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
 		  check(mc.cliqueSize() == 2, "Wrong clique size");
+		}
 		int main() {
 		  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
 		  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
-		  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
+		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
 		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
 		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
 		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
 		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
-		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
+		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
 		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
 		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
 		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
 		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
-		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
+		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
 		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
 		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account