LEMON/LEMON-main Changeset - r788:c92296660262

Repositories » LEMON » LEMON-main

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

Changeset - r788:c92296660262

« 786:e20173
« 787:c22306

792:a2d5fd »

r788:c92296660262

Wed, 18 Nov 2009 14:38:02

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 22 0

merge default

9 files changed with 116 insertions and 115 deletions:

doc/min_cost_flow.dox

lemon/bellman_ford.h

lemon/bfs.h

lemon/circulation.h

lemon/concepts/digraph.h

lemon/concepts/graph.h

lemon/concepts/graph_components.h

lemon/concepts/path.h

lemon/counter.h

lemon/dfs.h

lemon/dijkstra.h

lemon/gomory_hu.h

lemon/graph_to_eps.h

lemon/hypercube_graph.h

lemon/lgf_reader.h

lemon/list_graph.h

lemon/lp_base.h

lemon/maps.h

lemon/network_simplex.h

lemon/preflow.h

lemon/time_measure.h

lemon/unionfind.h

↑ Collapse diff ↑

doc/min_cost_flow.dox

Show inline comments

@@ -49,65 +49,65 @@
 		The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
 		zero or negative in order to have a feasible solution (since the sum
 		of the expressions on the left-hand side of the inequalities is zero).
 		It means that the total demand must be greater or equal to the total
 		supply and all the supplies have to be carried out from the supply nodes,
 		but there could be demands that are not satisfied.
 		If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
 		constraints have to be satisfied with equality, i.e. all demands
 		have to be satisfied and all supplies have to be used.
 		\section mcf_algs Algorithms
 		LEMON contains several algorithms for solving this problem, for more
 		information see \ref min_cost_flow_algs "Minimum Cost Flow Algorithms".
 		A feasible solution for this problem can be found using \ref Circulation.
 		\section mcf_dual Dual Solution
 		The dual solution of the minimum cost flow problem is represented by
 		node potentials \f$\pi: V\rightarrow\mathbf{R}\f$.
 		An \f$f: A\rightarrow\mathbf{R}\f$ primal feasible solution is optimal
 		if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$ node potentials
 		the following \e complementary \e slackness optimality conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
-		   - \f$\pi(u)<=0\f$;
+		   - \f$\pi(u)\leq 0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
 		\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
 		\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
 		All algorithms provide dual solution (node potentials), as well,
 		if an optimal flow is found.
 		\section mcf_eq Equality Form
 		The above \ref mcf_def "definition" is actually more general than the
 		usual formulation of the minimum cost flow problem, in which strict
 		equalities are required in the supply/demand contraints.
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		However if the sum of the supply values is zero, then these two problems
 		are equivalent.
 		The \ref min_cost_flow_algs "algorithms" in LEMON support the general
 		form, so if you need the equality form, you have to ensure this additional
 		contraint manually.
 		\section mcf_leq Opposite Inequalites (LEQ Form)
 		Another possible definition of the minimum cost flow problem is
@@ -116,38 +116,38 @@
 		\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
 		\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		It means that the total demand must be less or equal to the
 		total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or
 		positive) and all the demands have to be satisfied, but there
 		could be supplies that are not carried out from the supply
 		nodes.
 		The equality form is also a special case of this form, of course.
 		You could easily transform this case to the \ref mcf_def "GEQ form"
 		of the problem by reversing the direction of the arcs and taking the
 		negative of the supply values (e.g. using \ref ReverseDigraph and
 		\ref NegMap adaptors).
 		However \ref NetworkSimplex algorithm also supports this form directly
 		for the sake of convenience.
 		Note that the optimality conditions for this supply constraint type are
 		slightly differ from the conditions that are discussed for the GEQ form,
 		namely the potentials have to be non-negative instead of non-positive.
 		An \f$f: A\rightarrow\mathbf{R}\f$ feasible solution of this problem
 		is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{R}\f$
 		node potentials the following conditions hold.
 		 - For all \f$uv\in A\f$ arcs:
 		   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
 		   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
 		   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
 		 - For all \f$u\in V\f$ nodes:
-		   - \f$\pi(u)>=0\f$;
+		   - \f$\pi(u)\geq 0\f$;
 		   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
 		     then \f$\pi(u)=0\f$.
 		*/
+		}

lemon/bellman_ford.h

Show inline comments

@@ -271,65 +271,65 @@
 		    template <class T>
 		    struct SetDistMapTraits : public Traits {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph&) {
 		        LEMON_ASSERT(false, "DistMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c DistMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c DistMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c OperationTraits type.
 		    /// For more information see \ref BellmanFordDefaultOperationTraits.
+		    /// For more information, see \ref BellmanFordDefaultOperationTraits.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    BellmanFord() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param length The length map used by the algorithm.
 		    BellmanFord(const Digraph& g, const LengthMap& length) :
 		      _gr(&g), _length(&length),
 		      _pred(0), _local_pred(false),
 		      _dist(0), _local_dist(false), _mask(0) {}
 		    ///Destructor.
 		    ~BellmanFord() {
 		      if(_local_pred) delete _pred;
 		      if(_local_dist) delete _dist;
 		      if(_mask) delete _mask;
+		    }
@@ -689,80 +689,80 @@
 		    ///
 		    /// Gives back the shortest path to the given node from the root(s).
 		    ///
 		    /// \warning \c t should be reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Path path(Node t) const
+		    {
 		      return Path(*_gr, *_pred, t);
+		    }
 		    /// \brief The distance of the given node from the root(s).
 		    ///
 		    /// Returns the distance of the given node from the root(s).
 		    ///
 		    /// \warning If node \c v is not reached from the root(s), then
 		    /// the return value of this function is undefined.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value dist(Node v) const { return (*_dist)[v]; }
 		    /// \brief Returns the 'previous arc' of the shortest path tree for
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous arc' of the shortest path
 		    /// tree for node \c v, i.e. it returns the last arc of a
 		    /// shortest path from a root to \c v. It is \c INVALID if \c v
 		    /// is not reached from the root(s) or if \c v is a root.
 		    ///
 		    /// The shortest path tree used here is equal to the shortest path
 		    /// tree used in \ref predNode() and \predMap().
+		    /// tree used in \ref predNode() and \ref predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v]; }
 		    /// \brief Returns the 'previous node' of the shortest path tree for
 		    /// the given node.
 		    ///
 		    /// This function returns the 'previous node' of the shortest path
 		    /// tree for node \c v, i.e. it returns the last but one node of
 		    /// a shortest path from a root to \c v. It is \c INVALID if \c v
 		    /// is not reached from the root(s) or if \c v is a root.
 		    ///
 		    /// The shortest path tree used here is equal to the shortest path
 		    /// tree used in \ref predArc() and \predMap().
+		    /// tree used in \ref predArc() and \ref predMap().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Node predNode(Node v) const {
 		      return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
+		    }
 		    /// \brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    /// Returns a const reference to the node map that stores the distances
 		    /// of the nodes calculated by the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    /// \brief Returns a const reference to the node map that stores the
 		    /// predecessor arcs.
 		    ///
 		    /// Returns a const reference to the node map that stores the predecessor
 		    /// arcs, which form the shortest path tree (forest).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const PredMap &predMap() const { return *_pred; }
 		    /// \brief Checks if a node is reached from the root(s).
 		    ///
 		    /// Returns \c true if \c v is reached from the root(s).
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before

lemon/bfs.h

Show inline comments

@@ -34,65 +34,65 @@
 		  ///Default traits class of Bfs class.
 		  ///Default traits class of Bfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
@@ -819,65 +819,65 @@
 		  ///Default traits class of bfs() function.
 		  ///Default traits class of bfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct BfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.

lemon/circulation.h

Show inline comments

@@ -277,65 +277,65 @@
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
+		    /// However, an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
 		    /// Constructor.
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    /// \param lower The lower bounds for the flow values on the arcs.
 		    /// \param upper The upper bounds (capacities) for the flow values
 		    /// on the arcs.
 		    /// \param supply The signed supply values of the nodes.
 		    Circulation(const Digraph &graph, const LowerMap &lower,
 		                const UpperMap &upper, const SupplyMap &supply)
 		      : _g(graph), _lo(&lower), _up(&upper), _supply(&supply),
 		        _flow(NULL), _local_flow(false), _level(NULL), _local_level(false),

lemon/concepts/digraph.h

Show inline comments

@@ -78,65 +78,65 @@
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are \c INVALID.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// Inequality operator.
 		        bool operator!=(Node) const { return true; }
 		        /// Artificial ordering operator.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only has to define some strict ordering of
 		        /// the nodes; this order has nothing to do with the iteration
 		        /// ordering of the nodes.
 		        bool operator<(Node) const { return false; }
 		      };
 		      /// Iterator class for the nodes.
 		      /// This iterator goes through each node of the digraph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of nodes in a digraph \c g of type \c %Digraph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
 		        /// Sets the iterator to the first node of the given digraph.
 		        ///
 		        explicit NodeIt(const Digraph&) { }
 		        /// Sets the iterator to the given node.
 		        /// Sets the iterator to the given node of the given digraph.
 		        ///
 		        NodeIt(const Digraph&, const Node&) { }
@@ -167,154 +167,154 @@
 		        Arc(const Arc&) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are \c INVALID.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// Inequality operator.
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only has to define some strict ordering of
 		        /// the arcs; this order has nothing to do with the iteration
 		        /// ordering of the arcs.
 		        bool operator<(Arc) const { return false; }
 		      };
 		      /// Iterator class for the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in a digraph \c g of type \c %Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        OutArcIt(Invalid) { }
 		        /// Sets the iterator to the first outgoing arc.
 		        /// Sets the iterator to the first outgoing arc of the given node.
 		        ///
 		        OutArcIt(const Digraph&, const Node&) { }
 		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        OutArcIt(const Digraph&, const Arc&) { }
 		        /// Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// Iterator class for the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of incoming arcs of a node \c n
 		      /// in a digraph \c g of type \c %Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        InArcIt(Invalid) { }
 		        /// Sets the iterator to the first incoming arc.
 		        /// Sets the iterator to the first incoming arc of the given node.
 		        ///
 		        InArcIt(const Digraph&, const Node&) { }
 		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        InArcIt(const Digraph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next
 		        /// incoming arc of the corresponding node.
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// Iterator class for the arcs.
 		      /// This iterator goes through each arc of the digraph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of arcs in a digraph \c g of type \c %Digraph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        ArcIt(Invalid) { }
 		        /// Sets the iterator to the first arc.
 		        /// Sets the iterator to the first arc of the given digraph.
 		        ///
 		        explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the given arc of the given digraph.
 		        ///
 		        ArcIt(const Digraph&, const Arc&) { }

lemon/concepts/graph.h

Show inline comments

@@ -111,65 +111,65 @@
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are \c INVALID.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// Inequality operator.
 		        bool operator!=(Node) const { return true; }
 		        /// Artificial ordering operator.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only has to define some strict ordering of
 		        /// the items; this order has nothing to do with the iteration
 		        /// ordering of the items.
 		        bool operator<(Node) const { return false; }
 		      };
 		      /// Iterator class for the nodes.
 		      /// This iterator goes through each node of the graph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of nodes in a graph \c g of type \c %Graph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
 		        /// Sets the iterator to the first node of the given digraph.
 		        ///
 		        explicit NodeIt(const Graph&) { }
 		        /// Sets the iterator to the given node.
 		        /// Sets the iterator to the given node of the given digraph.
 		        ///
 		        NodeIt(const Graph&, const Node&) { }
@@ -199,109 +199,109 @@
 		        ///
 		        Edge(const Edge&) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the object to be invalid.
 		        /// \sa Invalid for more details.
 		        Edge(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are \c INVALID.
 		        bool operator==(Edge) const { return true; }
 		        /// Inequality operator
 		        /// Inequality operator.
 		        bool operator!=(Edge) const { return true; }
 		        /// Artificial ordering operator.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only has to define some strict ordering of
 		        /// the edges; this order has nothing to do with the iteration
 		        /// ordering of the edges.
 		        bool operator<(Edge) const { return false; }
 		      };
 		      /// Iterator class for the edges.
 		      /// This iterator goes through each edge of the graph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of edges in a graph \c g of type \c %Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class EdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        EdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        EdgeIt(const EdgeIt& e) : Edge(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        EdgeIt(Invalid) { }
 		        /// Sets the iterator to the first edge.
 		        /// Sets the iterator to the first edge of the given graph.
 		        ///
 		        explicit EdgeIt(const Graph&) { }
 		        /// Sets the iterator to the given edge.
 		        /// Sets the iterator to the given edge of the given graph.
 		        ///
 		        EdgeIt(const Graph&, const Edge&) { }
 		        /// Next edge
 		        /// Assign the iterator to the next edge.
 		        ///
 		        EdgeIt& operator++() { return *this; }
 		      };
 		      /// Iterator class for the incident edges of a node.
 		      /// This iterator goes trough the incident undirected edges
 		      /// of a certain node of a graph.
 		      /// Its usage is quite simple, for example you can compute the
+		      /// Its usage is quite simple, for example, you can compute the
 		      /// degree (i.e. the number of incident edges) of a node \c n
 		      /// in a graph \c g of type \c %Graph as follows.
 		      ///
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      ///
 		      /// \warning Loop edges will be iterated twice.
 		      class IncEdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        IncEdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        IncEdgeIt(Invalid) { }
 		        /// Sets the iterator to the first incident edge.
 		        /// Sets the iterator to the first incident edge of the given node.
 		        ///
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Sets the iterator to the given edge.
@@ -340,157 +340,157 @@
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Equality operator.
 		        ///
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are \c INVALID.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// Inequality operator.
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// Artificial ordering operator.
 		        ///
 		        /// \note This operator only has to define some strict ordering of
 		        /// the arcs; this order has nothing to do with the iteration
 		        /// ordering of the arcs.
 		        bool operator<(Arc) const { return false; }
 		        /// Converison to \c Edge
 		        /// Converison to \c Edge.
 		        ///
 		        operator Edge() const { return Edge(); }
 		      };
 		      /// Iterator class for the arcs.
 		      /// This iterator goes through each directed arc of the graph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of arcs in a graph \c g of type \c %Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        ArcIt(Invalid) { }
 		        /// Sets the iterator to the first arc.
 		        /// Sets the iterator to the first arc of the given graph.
 		        ///
 		        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        ArcIt(const Graph&, const Arc&) { }
 		        /// Next arc
 		        /// Assign the iterator to the next arc.
 		        ///
 		        ArcIt& operator++() { return *this; }
 		      };
 		      /// Iterator class for the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing directed arcs of a
 		      /// certain node of a graph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in a graph \c g of type \c %Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        OutArcIt(Invalid) { }
 		        /// Sets the iterator to the first outgoing arc.
 		        /// Sets the iterator to the first outgoing arc of the given node.
 		        ///
 		        OutArcIt(const Graph& n, const Node& g) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
 		        /// Sets the iterator to the given arc.
 		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        OutArcIt(const Graph&, const Arc&) { }
 		        /// Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// Iterator class for the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming directed arcs of a
 		      /// certain node of a graph.
 		      /// Its usage is quite simple, for example you can count the number
+		      /// Its usage is quite simple, for example, you can count the number
 		      /// of incoming arcs of a node \c n
 		      /// in a graph \c g of type \c %Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the iterator to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// %Invalid constructor \& conversion.
 		        /// Initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        InArcIt(Invalid) { }
 		        /// Sets the iterator to the first incoming arc.
 		        /// Sets the iterator to the first incoming arc of the given node.
 		        ///
 		        InArcIt(const Graph& g, const Node& n) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
 		        /// Sets the iterator to the given arc.
@@ -558,78 +558,78 @@
 		      };
 		      /// \brief Standard graph map type for the edges.
 		      ///
 		      /// Standard graph map type for the edges.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
+		      {
 		      public:
 		        /// Constructor
 		        explicit EdgeMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        EdgeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        EdgeMap(const EdgeMap& em) :
 		          ReferenceMap<Edge, T, T&, const T&>(em) {}
 		        ///Assignment operator
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief The first node of the edge.
 		      ///
 		      /// Returns the first node of the given edge.
 		      ///
 		      /// Edges don't have source and target nodes, however methods
+		      /// Edges don't have source and target nodes, however, methods
 		      /// u() and v() are used to query the two end-nodes of an edge.
 		      /// The orientation of an edge that arises this way is called
 		      /// the inherent direction, it is used to define the default
 		      /// direction for the corresponding arcs.
 		      /// \sa v()
 		      /// \sa direction()
 		      Node u(Edge) const { return INVALID; }
 		      /// \brief The second node of the edge.
 		      ///
 		      /// Returns the second node of the given edge.
 		      ///
 		      /// Edges don't have source and target nodes, however methods
+		      /// Edges don't have source and target nodes, however, methods
 		      /// u() and v() are used to query the two end-nodes of an edge.
 		      /// The orientation of an edge that arises this way is called
 		      /// the inherent direction, it is used to define the default
 		      /// direction for the corresponding arcs.
 		      /// \sa u()
 		      /// \sa direction()
 		      Node v(Edge) const { return INVALID; }
 		      /// \brief The source node of the arc.
 		      ///
 		      /// Returns the source node of the given arc.
 		      Node source(Arc) const { return INVALID; }
 		      /// \brief The target node of the arc.
 		      ///
 		      /// Returns the target node of the given arc.
 		      Node target(Arc) const { return INVALID; }
 		      /// \brief The ID of the node.
 		      ///
 		      /// Returns the ID of the given node.
 		      int id(Node) const { return -1; }
 		      /// \brief The ID of the edge.
 		      ///
 		      /// Returns the ID of the given edge.
 		      int id(Edge) const { return -1; }
 		      /// \brief The ID of the arc.
 		      ///
 		      /// Returns the ID of the given arc.
 		      int id(Arc) const { return -1; }

lemon/concepts/graph_components.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-2009
 		 * 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 graph_concepts
 		///\file
-		///\brief The concept of graph components.
+		///\brief The concepts of graph components.
 		#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/bits/alteration_notifier.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
 		    ///
 		    /// This class describes the concept of \c Node, \c Arc and \c Edge
 		    /// subtypes of digraph and graph types.
 		    ///
 		    /// \note This class is a template class so that we can use it to
 		    /// create graph skeleton classes. The reason for this is that \c Node
 		    /// and \c Arc (or \c Edge) types should \e not derive from the same
 		    /// base class. For \c Node you should instantiate it with character
 		    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
 		#ifndef DOXYGEN
 		    template <char sel = '0'>
 		#endif
 		    class GraphItem {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the item to some well-defined value. So you should consider it

lemon/concepts/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-2009
 		 * 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 concept
 		///\file
-		///\brief Classes for representing paths in digraphs.
+		///\brief The concept of paths
 		///
 		#ifndef LEMON_CONCEPTS_PATH_H
 		#define LEMON_CONCEPTS_PATH_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \addtogroup concept
 		    /// @{
 		    /// \brief A skeleton structure for representing directed paths in
 		    /// a digraph.
 		    ///
 		    /// A skeleton structure for representing directed paths in a
 		    /// digraph.
 		    /// In a sense, a path can be treated as a list of arcs.
 		    /// LEMON path types just store this list. As a consequence, they cannot
 		    /// enumerate the nodes on the path directly and a zero length path
 		    /// cannot store its source node.
 		    ///
 		    /// The arcs of a path should be stored in the order of their directions,
 		    /// i.e. the target node of each arc should be the same as the source
 		    /// node of the next arc. This consistency could be checked using
 		    /// \ref checkPath().
 		    /// The source and target nodes of a (consistent) path can be obtained
 		    /// using \ref pathSource() and \ref pathTarget().
 		    ///
 		    /// A path can be constructed from another path of any type using the
 		    /// copy constructor or the assignment operator.
 		    ///
 		    /// \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
 		    /// cannot enumerate the nodes in the path and the zero length
 		    /// paths cannot store the source.
 		    ///
 		    template <typename GR>
 		    class Path {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
 		      class ArcIt;
 		      /// \brief Default constructor
 		      Path() {}
 		      /// \brief Template constructor
+		      /// \brief Template copy constructor
 		      template <typename CPath>
 		      Path(const CPath& cpath) {}
 		      /// \brief Template assigment
+		      /// \brief Template assigment operator
 		      template <typename CPath>
 		      Path& operator=(const CPath& cpath) {
 		        ignore_unused_variable_warning(cpath);
 		        return *this;
+		      }
-		      /// Length of the path ie. the number of arcs in the path.
+		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// Resets the path to an empty path.
 		      void clear() {}
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
-		      /// This class is used to iterate on the arcs of the paths.
+		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const Path &) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          Path<Digraph> pc;
 		          _Path p, pp(pc);
 		          int l = p.length();
 		          int e = p.empty();
 		          p.clear();
 		          p = pc;
 		          typename _Path::ArcIt id, ii(INVALID), i(p);
 		          ++i;
 		          typename Digraph::Arc ed = i;
 		          e = (i == ii);
 		          e = (i != ii);
@@ -163,145 +172,139 @@
 		      template <typename _Digraph, typename _Path>
 		      struct PathDumperConstraints<
 		        _Digraph, _Path,
 		        typename enable_if<typename _Path::RevPathTag, void>::type
 		      > {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::RevArcIt id, i(p);
 		          ++i;
 		          typename _Digraph::Arc ed = i;
 		          e = (i == INVALID);
 		          e = (i != INVALID);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ed);
+		        }
 		        _Path& p;
 		      };
+		    }
 		    /// \brief A skeleton structure for path dumpers.
 		    ///
 		    /// A skeleton structure for path dumpers. The path dumpers are
 		    /// the generalization of the paths. The path dumpers can
 		    /// enumerate the arcs of the path wheter in forward or in
 		    /// backward order.  In most time these classes are not used
 		    /// directly rather it used to assign a dumped class to a real
-		    /// path type.
+		    /// the generalization of the paths, they can enumerate the arcs
 		    /// of the path either in forward or in backward order.
 		    /// These classes are typically not used directly, they are rather
 		    /// used to be assigned to a real path type.
 		    ///
 		    /// The main purpose of this concept is that the shortest path
 		    /// algorithms can enumerate easily the arcs in reverse order.
 		    /// If we would like to give back a real path from these
 		    /// algorithms then we should create a temporarly path object. In
 		    /// LEMON such algorithms gives back a path dumper what can
-		    /// assigned to a real path and the dumpers can be implemented as
+		    /// algorithms can enumerate the arcs easily in reverse order.
 		    /// In LEMON, such algorithms give back a (reverse) path dumper that
 		    /// can be assigned to a real path. The dumpers can be implemented as
 		    /// an adaptor class to the predecessor map.
 		    ///
 		    /// \tparam GR The digraph type in which the path is.
 		    ///
 		    /// The paths can be constructed from any path type by a
 		    /// template constructor or a template assignment operator.
 		    template <typename GR>
 		    class PathDumper {
 		    public:
 		      /// Type of the underlying digraph.
 		      typedef GR Digraph;
 		      /// Arc type of the underlying digraph.
 		      typedef typename Digraph::Arc Arc;
-		      /// Length of the path ie. the number of arcs in the path.
+		      /// Length of the path, i.e. the number of arcs on the path.
 		      int length() const { return 0;}
 		      /// Returns whether the path is empty.
 		      bool empty() const { return true;}
 		      /// \brief Forward or reverse dumping
 		      ///
 		      /// If the RevPathTag is defined and true then reverse dumping
 		      /// is provided in the path dumper. In this case instead of the
 		      /// ArcIt the RevArcIt iterator should be implemented in the
 		      /// dumper.
 		      /// If this tag is defined to be \c True, then reverse dumping
 		      /// is provided in the path dumper. In this case, \c RevArcIt
 		      /// iterator should be implemented instead of \c ArcIt iterator.
 		      typedef False RevPathTag;
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path.
 		      ///
-		      /// This class is used to iterate on the arcs of the paths.
+		      /// LEMON style iterator class for enumerating the arcs of a path.
 		      class ArcIt {
 		      public:
 		        /// Default constructor
 		        ArcIt() {}
 		        /// Invalid constructor
 		        ArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the first arc of the given path
 		        ArcIt(const PathDumper&) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        ArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const ArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const ArcIt&) const {return false;}
 		      };
-		      /// \brief LEMON style iterator for path arcs
+		      /// \brief LEMON style iterator for enumerating the arcs of a path
 		      /// in reverse direction.
 		      ///
 		      /// This class is used to iterate on the arcs of the paths in
 		      /// reverse direction.
 		      /// LEMON style iterator class for enumerating the arcs of a path
 		      /// in reverse direction.
 		      class RevArcIt {
 		      public:
 		        /// Default constructor
 		        RevArcIt() {}
 		        /// Invalid constructor
 		        RevArcIt(Invalid) {}
-		        /// Constructor for first arc
+		        /// Sets the iterator to the last arc of the given path
 		        RevArcIt(const PathDumper &) {}
 		        /// Conversion to Arc
+		        /// Conversion to \c Arc
 		        operator Arc() const { return INVALID; }
 		        /// Next arc
 		        RevArcIt& operator++() {return *this;}
 		        /// Comparison operator
 		        bool operator==(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator!=(const RevArcIt&) const {return true;}
 		        /// Comparison operator
 		        bool operator<(const RevArcIt&) const {return false;}
 		      };
 		      template <typename _Path>
 		      struct Constraints {
 		        void constraints() {
 		          function_requires<_path_bits::
 		            PathDumperConstraints<Digraph, _Path> >();
+		        }
 		      };
 		    };
 		    ///@}
+		  }
 		} // namespace lemon
 		#endif

lemon/counter.h

Show inline comments

@@ -183,65 +183,65 @@
 		    /// Constructor.
 		    Counter(const char *title,std::ostream &os=std::cerr)
 		      : _title(title), _os(os), count(0) {}
 		    /// Destructor. Prints the given title and the value of the counter.
 		    ~Counter() {
 		      _os << _title << count <<std::endl;
+		    }
 		    ///\e
 		    Counter &operator++() { count++; return *this;}
 		    ///\e
 		    int operator++(int) { return count++;}
 		    ///\e
 		    Counter &operator--() { count--; return *this;}
 		    ///\e
 		    int operator--(int) { return count--;}
 		    ///\e
 		    Counter &operator+=(int c) { count+=c; return *this;}
 		    ///\e
 		    Counter &operator-=(int c) { count-=c; return *this;}
 		    /// Resets the counter to the given value.
 		    /// Resets the counter to the given value.
 		    /// \note This function does not reset the values of
 		    /// \ref SubCounter "SubCounter"s but it resets \ref NoSubCounter
 		    /// "NoSubCounter"s along with the main counter.
 		    void reset(int c=0) {count=c;}
 		    /// Returns the value of the counter.
 		    operator int() {return count;}
 		  };
 		  /// 'Do nothing' version of Counter.
-		  /// This class can be used in the same way as \ref Counter however it
+		  /// This class can be used in the same way as \ref Counter, but it
 		  /// does not count at all and does not print report on destruction.
 		  ///
 		  /// Replacing a \ref Counter with a \ref NoCounter makes it possible
 		  /// to turn off all counting and reporting (SubCounters should also
 		  /// be replaced with NoSubCounters), so it does not affect the
 		  /// efficiency of the program at all.
 		  ///
 		  /// \sa Counter
 		  class NoCounter
+		  {
 		  public:
 		    typedef _NoSubCounter<NoCounter> SubCounter;
 		    typedef _NoSubCounter<NoCounter> NoSubCounter;
 		    NoCounter() {}
 		    NoCounter(std::string,std::ostream &) {}
 		    NoCounter(const char *,std::ostream &) {}
 		    NoCounter(std::string) {}
 		    NoCounter(const char *) {}
 		    NoCounter &operator++() { return *this; }
 		    int operator++(int) { return 0; }
 		    NoCounter &operator--() { return *this; }
 		    int operator--(int) { return 0; }
 		    NoCounter &operator+=(int) { return *this;}
 		    NoCounter &operator-=(int) { return *this;}
 		    void reset(int) {}
 		    void reset() {}
 		    operator int() {return 0;}
 		  };
 		  ///@}
+		}

lemon/dfs.h

Show inline comments

@@ -34,65 +34,65 @@
 		  ///Default traits class of Dfs class.
 		  ///Default traits class of Dfs class.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a \c ReachedMap.
 		    ///This function instantiates a \ref ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.
@@ -749,65 +749,65 @@
 		  ///Default traits class of dfs() function.
 		  ///Default traits class of dfs() function.
 		  ///\tparam GR Digraph type.
 		  template<class GR>
 		  struct DfsWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the %DFS paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &g)
+		    {
 		      return new ReachedMap(g);
+		    }
 		    ///The type of the map that stores the distances of the nodes.

lemon/dijkstra.h

Show inline comments

@@ -103,65 +103,65 @@
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
 		    ///Instantiates a \c Heap.
 		    ///This function instantiates a \ref Heap.
 		    static Heap *createHeap(HeapCrossRef& r)
+		    {
 		      return new Heap(r);
+		    }
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a \c PredMap.
 		    ///This function instantiates a \ref PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///\ref PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a \c ProcessedMap.
 		    ///This function instantiates a \ref ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the \ref ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 		    ///Instantiates a \c DistMap.
 		    ///This function instantiates a \ref DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the \ref DistMap.
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		  };
 		  ///%Dijkstra algorithm class.
@@ -397,86 +397,86 @@
 		    ///reference types. If this named parameter is used, then external
 		    ///heap and cross reference objects must be passed to the algorithm
 		    ///using the \ref heap() function before calling \ref run(Node) "run()"
 		    ///or \ref init().
 		    ///\sa SetStandardHeap
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct SetHeap
 		      : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
 		    };
 		    template <class H, class CR>
 		    struct SetStandardHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
 		        return new HeapCrossRef(G);
+		      }
 		      static Heap *createHeap(HeapCrossRef &R)
+		      {
 		        return new Heap(R);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference types with automatic allocation
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///reference types with automatic allocation.
 		    ///They should have standard constructor interfaces to be able to
 		    ///automatically created by the algorithm (i.e. the digraph should be
 		    ///passed to the constructor of the cross reference and the cross
 		    ///reference should be passed to the constructor of the heap).
 		    ///However external heap and cross reference objects could also be
+		    ///However, external heap and cross reference objects could also be
 		    ///passed to the algorithm using the \ref heap() function before
 		    ///calling \ref run(Node) "run()" or \ref init().
 		    ///\sa SetHeap
 		    template <class H, class CR = typename Digraph::template NodeMap<int> >
 		    struct SetStandardHeap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
 		      Create;
 		    };
 		    template <class T>
 		    struct SetOperationTraitsTraits : public Traits {
 		      typedef T OperationTraits;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    ///\c OperationTraits type
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c OperationTraits type.
 		    /// For more information see \ref DijkstraDefaultOperationTraits.
+		    /// For more information, see \ref DijkstraDefaultOperationTraits.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    Dijkstra() {}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    ///\param length The length map used by the algorithm.
 		    Dijkstra(const Digraph& g, const LengthMap& length) :
 		      G(&g), _length(&length),
 		      _pred(NULL), local_pred(false),
 		      _dist(NULL), local_dist(false),
 		      _processed(NULL), local_processed(false),
 		      _heap_cross_ref(NULL), local_heap_cross_ref(false),
 		      _heap(NULL), local_heap(false)
 		    { }
 		    ///Destructor.
 		    ~Dijkstra()
+		    {
@@ -967,65 +967,65 @@
 		                    std::less<Value> > Heap;
 		    ///Instantiates a \ref Heap.
 		    ///This function instantiates a \ref Heap.
 		    /// \param r is the HeapCrossRef which is used.
 		    static Heap *createHeap(HeapCrossRef& r)
+		    {
 		      return new Heap(r);
+		    }
 		    ///\brief The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///
 		    ///The type of the map that stores the predecessor
 		    ///arcs of the shortest paths.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 		    ///Instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
 		    ///PredMap.
 		    static PredMap *createPredMap(const Digraph &g)
+		    {
 		      return new PredMap(g);
+		    }
 		    ///The type of the map that indicates which nodes are processed.
 		    ///The type of the map that indicates which nodes are processed.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    ///By default it is a NullMap.
+		    ///By default, it is a NullMap.
 		    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 		    ///Instantiates a ProcessedMap.
 		    ///This function instantiates a ProcessedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ProcessedMap.
 		#ifdef DOXYGEN
 		    static ProcessedMap *createProcessedMap(const Digraph &g)
 		#else
 		    static ProcessedMap *createProcessedMap(const Digraph &)
 		#endif
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that stores the distances of the nodes.
 		    ///The type of the map that stores the distances of the nodes.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 		    ///Instantiates a DistMap.
 		    ///This function instantiates a DistMap.
 		    ///\param g is the digraph, to which we would like to define
 		    ///the DistMap
 		    static DistMap *createDistMap(const Digraph &g)
+		    {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.

lemon/gomory_hu.h

Show inline comments

@@ -265,69 +265,67 @@
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
 			  sn = (*_pred)[sn];
+			}
+		      }
 		      return value;
+		    }
 		    /// \brief Return the minimum cut between two nodes
 		    ///
 		    /// This function returns the minimum cut between the nodes \c s and \c t
 		    /// in the \c cutMap parameter by setting the nodes in the component of
 		    /// \c s to \c true and the other nodes to \c false.
 		    ///
 		    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
 		    ///
 		    /// \param s The base node.
 		    /// \param t The node you want to separate from node \c s.
 		    /// \param cutMap The cut will be returned in this map.
 		    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
 		    /// "ReadWriteMap" on the graph nodes.
 		    ///
 		    /// \return The value of the minimum cut between \c s and \c t.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename CutMap>
-		    Value minCutMap(const Node& s, ///<
 		    Value minCutMap(const Node& s,
 		                    const Node& t,
 		                    ///<
 		                    CutMap& cutMap
 		                    ///<
 		                    ) const {
 		      Node sn = s, tn = t;
 		      bool s_root=false;
 		      Node rn = INVALID;
 		      Value value = std::numeric_limits<Value>::max();
 		      while (sn != tn) {
 			if ((*_order)[sn] < (*_order)[tn]) {
 			  if ((*_weight)[tn] <= value) {
 			    rn = tn;
 		            s_root = false;
 			    value = (*_weight)[tn];
+			  }
 			  tn = (*_pred)[tn];
 			} else {
 			  if ((*_weight)[sn] <= value) {
 			    rn = sn;
 		            s_root = true;
 			    value = (*_weight)[sn];
+			  }
 			  sn = (*_pred)[sn];
+			}
+		      }
 		      typename Graph::template NodeMap<bool> reached(_graph, false);
 		      reached[_root] = true;
 		      cutMap.set(_root, !s_root);
 		      reached[rn] = true;
 		      cutMap.set(rn, s_root);
 		      std::vector<Node> st;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
@@ -365,65 +363,65 @@
 		    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
 		    /// \endcode
 		    class MinCutNodeIt
+		    {
 		      bool _side;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutNodeIt(GomoryHu const &gomory,
 		                   ///< The GomoryHu class. You must call its
 		                   ///  run() method
 		                   ///  before initializing this iterator.
 		                   const Node& s, ///< The base node.
 		                   const Node& t,
 		                   ///< The node you want to separate from node \c s.
 		                   bool side=true
 		                   ///< If it is \c true (default) then the iterator lists
 		                   ///  the nodes of the component containing \c s,
 		                   ///  otherwise it lists the other component.
 		                   /// \note As the minimum cut is not always unique,
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, true);
 		                   /// \endcode
 		                   /// and
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, t, s, false);
 		                   /// \endcode
 		                   /// does not necessarily give the same set of nodes.
 		                   /// However it is ensured that
+		                   /// However, it is ensured that
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, true);
 		                   /// \endcode
 		                   /// and
 		                   /// \code
 		                   /// MinCutNodeIt(gomory, s, t, false);
 		                   /// \endcode
 		                   /// together list each node exactly once.
+		                   )
 		        : _side(side), _cut(gomory._graph)
+		      {
 		        gomory.minCutMap(s,t,_cut);
 		        for(_node_it=typename Graph::NodeIt(gomory._graph);
 		            _node_it!=INVALID && _cut[_node_it]!=_side;
 		            ++_node_it) {}
+		      }
 		      /// Conversion to \c Node
 		      /// Conversion to \c Node.
 		      ///
 		      operator typename Graph::Node() const
+		      {
 		        return _node_it;
+		      }
 		      bool operator==(Invalid) { return _node_it==INVALID; }
 		      bool operator!=(Invalid) { return _node_it!=INVALID; }
 		      /// Next node
 		      /// Next node.
 		      ///
 		      MinCutNodeIt &operator++()
+		      {

lemon/graph_to_eps.h

Show inline comments

@@ -113,65 +113,65 @@
 		  bool _showNodePsText;
 		  ConstMap<typename Graph::Node,bool > _nodePsTexts;
 		  char *_nodePsTextsPreamble;
 		  bool _undirected;
 		  bool _pleaseRemoveOsStream;
 		  bool _scaleToA4;
 		  std::string _title;
 		  std::string _copyright;
 		  enum NodeTextColorType
 		    { DIST_COL=0, DIST_BW=1, CUST_COL=2, SAME_COL=3 } _nodeTextColorType;
 		  ConstMap<typename Graph::Node,Color > _nodeTextColors;
 		  bool _autoNodeScale;
 		  bool _autoArcWidthScale;
 		  bool _absoluteNodeSizes;
 		  bool _absoluteArcWidths;
 		  bool _negY;
 		  bool _preScale;
 		  ///Constructor
 		  ///Constructor
 		  ///\param gr  Reference to the graph to be printed.
 		  ///\param ost Reference to the output stream.
 		  ///By default it is <tt>std::cout</tt>.
+		  ///By default, it is <tt>std::cout</tt>.
 		  ///\param pros If it is \c true, then the \c ostream referenced by \c os
 		  ///will be explicitly deallocated by the destructor.
 		  DefaultGraphToEpsTraits(const GR &gr, std::ostream& ost = std::cout,
 		                          bool pros = false) :
 		    g(gr), os(ost),
 		    _coords(dim2::Point<double>(1,1)), _nodeSizes(1), _nodeShapes(0),
 		    _nodeColors(WHITE), _arcColors(BLACK),
 		    _arcWidths(1.0), _arcWidthScale(0.003),
 		    _nodeScale(.01), _xBorder(10), _yBorder(10), _scale(1.0),
 		    _nodeBorderQuotient(.1),
 		    _drawArrows(false), _arrowLength(1), _arrowWidth(0.3),
 		    _showNodes(true), _showArcs(true),
 		    _enableParallel(false), _parArcDist(1),
 		    _showNodeText(false), _nodeTexts(false), _nodeTextSize(1),
 		    _showNodePsText(false), _nodePsTexts(false), _nodePsTextsPreamble(0),
 		    _undirected(lemon::UndirectedTagIndicator<GR>::value),
 		    _pleaseRemoveOsStream(pros), _scaleToA4(false),
 		    _nodeTextColorType(SAME_COL), _nodeTextColors(BLACK),
 		    _autoNodeScale(false),
 		    _autoArcWidthScale(false),
 		    _absoluteNodeSizes(false),
 		    _absoluteArcWidths(false),
 		    _negY(false),
 		    _preScale(true)
 		  {}
 		};
 		///Auxiliary class to implement the named parameters of \ref graphToEps()
 		///Auxiliary class to implement the named parameters of \ref graphToEps().
 		///
 		///For detailed examples see the \ref graph_to_eps_demo.cc demo file.
@@ -483,65 +483,65 @@
 		  /// node sizes will be scaled in such a way that the greatest size will be
 		  /// equal to \c d.
 		  /// \sa nodeSizes()
 		  /// \sa autoNodeScale()
 		  GraphToEps<T> &nodeScale(double d=.01) {_nodeScale=d;return *this;}
 		  ///Turns on/off the automatic node size scaling.
 		  ///Turns on/off the automatic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &autoNodeScale(bool b=true) {
 		    _autoNodeScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///Turns on/off the absolutematic node size scaling.
 		  ///
 		  ///\sa nodeScale()
 		  ///
 		  GraphToEps<T> &absoluteNodeSizes(bool b=true) {
 		    _absoluteNodeSizes=b;return *this;
+		  }
 		  ///Negates the Y coordinates.
 		  GraphToEps<T> &negateY(bool b=true) {
 		    _negY=b;return *this;
+		  }
 		  ///Turn on/off pre-scaling
 		  ///By default graphToEps() rescales the whole image in order to avoid
+		  ///By default, graphToEps() rescales the whole image in order to avoid
 		  ///very big or very small bounding boxes.
 		  ///
 		  ///This (p)rescaling can be turned off with this function.
 		  ///
 		  GraphToEps<T> &preScale(bool b=true) {
 		    _preScale=b;return *this;
+		  }
 		  ///Sets a global scale factor for arc widths
 		  /// Sets a global scale factor for arc widths.
 		  ///
 		  /// If arcWidths() is not given, this function simply sets the arc
 		  /// widths to \c d.  If arcWidths() is given, but
 		  /// autoArcWidthScale() is not, then the arc withs given by
 		  /// arcWidths() will be multiplied by the value \c d.
 		  /// If both arcWidths() and autoArcWidthScale() are used, then the
 		  /// arc withs will be scaled in such a way that the greatest width will be
 		  /// equal to \c d.
 		  GraphToEps<T> &arcWidthScale(double d=.003) {_arcWidthScale=d;return *this;}
 		  ///Turns on/off the automatic arc width scaling.
 		  ///Turns on/off the automatic arc width scaling.
 		  ///
 		  ///\sa arcWidthScale()
 		  ///
 		  GraphToEps<T> &autoArcWidthScale(bool b=true) {
 		    _autoArcWidthScale=b;return *this;
+		  }
 		  ///Turns on/off the absolutematic arc width scaling.
 		  ///Turns on/off the absolutematic arc width scaling.
@@ -1085,77 +1085,77 @@
 		  ///An alias for absoluteArcWidths()
 		  GraphToEps<T> &absoluteEdgeWidths(bool b=true)
+		  {
 		    return absoluteArcWidths(b);
+		  }
 		  ///An alias for parArcDist()
 		  GraphToEps<T> &parEdgeDist(double d) {return parArcDist(d);}
 		  ///An alias for hideArcs()
 		  GraphToEps<T> &hideEdges(bool b=true) {return hideArcs(b);}
 		  ///@}
 		};
 		template<class T>
 		const int GraphToEps<T>::INTERPOL_PREC = 20;
 		template<class T>
 		const double GraphToEps<T>::A4HEIGHT = 841.8897637795276;
 		template<class T>
 		const double GraphToEps<T>::A4WIDTH  = 595.275590551181;
 		template<class T>
 		const double GraphToEps<T>::A4BORDER = 15;
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///Generates an EPS file from a graph.
 		///\param g Reference to the graph to be printed.
 		///\param os Reference to the output stream.
 		///By default it is <tt>std::cout</tt>.
+		///By default, it is <tt>std::cout</tt>.
 		///
 		///This function also has a lot of
 		///\ref named-templ-func-param "named parameters",
 		///they are declared as the members of class \ref GraphToEps. The following
 		///example shows how to use these parameters.
 		///\code
 		/// graphToEps(g,os).scale(10).coords(coords)
 		///              .nodeScale(2).nodeSizes(sizes)
 		///              .arcWidthScale(.4).run();
 		///\endcode
 		///
 		///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.
+		///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file.
 		///
 		///\warning Don't forget to put the \ref GraphToEps::run() "run()"
 		///to the end of the parameter list.
 		///\sa GraphToEps
 		///\sa graphToEps(GR &g, const char *file_name)
 		template<class GR>
 		GraphToEps<DefaultGraphToEpsTraits<GR> >
 		graphToEps(GR &g, std::ostream& os=std::cout)
+		{
 		  return
 		    GraphToEps<DefaultGraphToEpsTraits<GR> >(DefaultGraphToEpsTraits<GR>(g,os));
+		}
 		///Generates an EPS file from a graph
 		///\ingroup eps_io
 		///This function does the same as
 		///\ref graphToEps(GR &g,std::ostream& os)
 		///but it writes its output into the file \c file_name
 		///instead of a stream.
 		///\sa graphToEps(GR &g, std::ostream& os)
 		template<class GR>
 		GraphToEps<DefaultGraphToEpsTraits<GR> >
 		graphToEps(GR &g,const char *file_name)
+		{
 		  std::ostream* os = new std::ofstream(file_name);
 		  if (!(*os)) {
 		    delete os;
 		    throw IoError("Cannot write file", file_name);
+		  }
 		  return GraphToEps<DefaultGraphToEpsTraits<GR> >
 		    (DefaultGraphToEpsTraits<GR>(g,*os,true));

lemon/hypercube_graph.h

Show inline comments

@@ -258,65 +258,65 @@
 		      return edge._id >> (_dim-1);
+		    }
 		    int dimension(Arc arc) const {
 		      return arc._id >> _dim;
+		    }
 		    static int index(Node node) {
 		      return node._id;
+		    }
 		    Node operator()(int ix) const {
 		      return Node(ix);
+		    }
 		  private:
 		    int _dim;
 		    int _node_num, _edge_num;
 		  };
 		  typedef GraphExtender<HypercubeGraphBase> ExtendedHypercubeGraphBase;
 		  /// \ingroup graphs
 		  ///
 		  /// \brief Hypercube graph class
 		  ///
 		  /// HypercubeGraph implements a special graph type. The nodes of the
 		  /// graph are indexed with integers having at most \c dim binary digits.
 		  /// Two nodes are connected in the graph if and only if their indices
 		  /// differ only on one position in the binary form.
 		  /// This class is completely static and it needs constant memory space.
-		  /// Thus you can neither add nor delete nodes or edges, however
+		  /// Thus you can neither add nor delete nodes or edges, however,
 		  /// the structure can be resized using resize().
 		  ///
 		  /// This type fully conforms to the \ref concepts::Graph "Graph concept".
 		  /// Most of its member functions and nested classes are documented
 		  /// only in the concept class.
 		  ///
 		  /// This class provides constant time counting for nodes, edges and arcs.
 		  ///
 		  /// \note The type of the indices is chosen to \c int for efficiency
 		  /// reasons. Thus the maximum dimension of this implementation is 26
 		  /// (assuming that the size of \c int is 32 bit).
 		  class HypercubeGraph : public ExtendedHypercubeGraphBase {
 		    typedef ExtendedHypercubeGraphBase Parent;
 		  public:
 		    /// \brief Constructs a hypercube graph with \c dim dimensions.
 		    ///
 		    /// Constructs a hypercube graph with \c dim dimensions.
 		    HypercubeGraph(int dim) { construct(dim); }
 		    /// \brief Resizes the graph
 		    ///
 		    /// This function resizes the graph. It fully destroys and
 		    /// rebuilds the structure, therefore the maps of the graph will be
 		    /// reallocated automatically and the previous values will be lost.
 		    void resize(int dim) {
 		      Parent::notifier(Arc()).clear();
 		      Parent::notifier(Edge()).clear();
 		      Parent::notifier(Node()).clear();
 		      construct(dim);
 		      Parent::notifier(Node()).build();

lemon/lgf_reader.h

Show inline comments

@@ -398,65 +398,65 @@
 		  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
 		  /// \ingroup lemon_io
 		  ///
 		  /// \brief \ref lgf-format "LGF" reader for directed graphs
 		  ///
 		  /// This utility reads an \ref lgf-format "LGF" file.
 		  ///
 		  /// The reading method does a batch processing. The user creates a
 		  /// reader object, then various reading rules can be added to the
 		  /// reader, and eventually the reading is executed with the \c run()
 		  /// member function. A map reading rule can be added to the reader
 		  /// with the \c nodeMap() or \c arcMap() members. An optional
 		  /// converter parameter can also be added as a standard functor
 		  /// converting from \c std::string to the value type of the map. If it
 		  /// is set, it will determine how the tokens in the file should be
 		  /// converted to the value type of the map. If the functor is not set,
 		  /// then a default conversion will be used. One map can be read into
 		  /// multiple map objects at the same time. The \c attribute(), \c
 		  /// node() and \c arc() functions are used to add attribute reading
 		  /// rules.
 		  ///
 		  ///\code
 		  /// DigraphReader<DGR>(digraph, std::cin).
 		  ///   nodeMap("coordinates", coord_map).
 		  ///   arcMap("capacity", cap_map).
 		  ///   node("source", src).
 		  ///   node("target", trg).
 		  ///   attribute("caption", caption).
 		  ///   run();
 		  ///\endcode
 		  ///
 		  /// By default the reader uses the first section in the file of the
+		  /// By default, the reader uses the first section in the file of the
 		  /// proper type. If a section has an optional name, then it can be
 		  /// selected for reading by giving an optional name parameter to the
 		  /// \c nodes(), \c arcs() or \c attributes() functions.
 		  ///
 		  /// The \c useNodes() and \c useArcs() functions are used to tell the reader
 		  /// that the nodes or arcs should not be constructed (added to the
 		  /// graph) during the reading, but instead the label map of the items
 		  /// are given as a parameter of these functions. An
 		  /// application of these functions is multipass reading, which is
 		  /// important if two \c \@arcs sections must be read from the
 		  /// file. In this case the first phase would read the node set and one
 		  /// of the arc sets, while the second phase would read the second arc
 		  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
 		  /// The previously read label node map should be passed to the \c
 		  /// useNodes() functions. Another application of multipass reading when
 		  /// paths are given as a node map or an arc map.
 		  /// It is impossible to read this in
 		  /// a single pass, because the arcs are not constructed when the node
 		  /// maps are read.
 		  template <typename DGR>
 		  class DigraphReader {
 		  public:
 		    typedef DGR Digraph;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
 		    std::istream* _is;
 		    bool local_is;
 		    std::string _filename;
@@ -2192,65 +2192,65 @@
 		  private:
 		    friend SectionReader sectionReader(std::istream& is);
 		    friend SectionReader sectionReader(const std::string& fn);
 		    friend SectionReader sectionReader(const char* fn);
 		    SectionReader(SectionReader& other)
 		      : _is(other._is), local_is(other.local_is) {
 		      other._is = 0;
 		      other.local_is = false;
 		      _sections.swap(other._sections);
+		    }
 		    SectionReader& operator=(const SectionReader&);
 		  public:
 		    /// \name Section Readers
 		    /// @{
 		    /// \brief Add a section processor with line oriented reading
 		    ///
 		    /// The first parameter is the type descriptor of the section, the
 		    /// second is a functor, which takes just one \c std::string
 		    /// parameter. At the reading process, each line of the section
 		    /// will be given to the functor object. However, the empty lines
 		    /// and the comment lines are filtered out, and the leading
 		    /// whitespaces are trimmed from each processed string.
 		    ///
 		    /// For example let's see a section, which contain several
+		    /// For example, let's see a section, which contain several
 		    /// integers, which should be inserted into a vector.
 		    ///\code
 		    ///  @numbers
 		    ///  12 45 23
 		    ///  4
 		    ///  23 6
 		    ///\endcode
 		    ///
 		    /// The functor is implemented as a struct:
 		    ///\code
 		    ///  struct NumberSection {
 		    ///    std::vector<int>& _data;
 		    ///    NumberSection(std::vector<int>& data) : _data(data) {}
 		    ///    void operator()(const std::string& line) {
 		    ///      std::istringstream ls(line);
 		    ///      int value;
 		    ///      while (ls >> value) _data.push_back(value);
 		    ///    }
 		    ///  };
 		    ///
 		    ///  // ...
 		    ///
 		    ///  reader.sectionLines("numbers", NumberSection(vec));
 		    ///\endcode
 		    template <typename Functor>
 		    SectionReader& sectionLines(const std::string& type, Functor functor) {
 		      LEMON_ASSERT(!type.empty(), "Type is empty.");
 		      LEMON_ASSERT(_sections.find(type) == _sections.end(),
 		                   "Multiple reading of section.");
 		      _sections.insert(std::make_pair(type,
 		        new _reader_bits::LineSection<Functor>(functor)));
 		      return *this;

lemon/list_graph.h

Show inline comments

@@ -371,77 +371,77 @@
 		    ///\brief Erase an arc from the digraph.
 		    ///
 		    ///This function erases the given arc from the digraph.
 		    ///
 		    ///\note All iterators referencing the removed arc are invalidated,
 		    ///of course.
 		    void erase(Arc a) { Parent::erase(a); }
 		    /// Node validity check
 		    /// This function gives back \c true if the given node is valid,
 		    /// i.e. it is a real node of the digraph.
 		    ///
 		    /// \warning A removed node could become valid again if new nodes are
 		    /// added to the digraph.
 		    bool valid(Node n) const { return Parent::valid(n); }
 		    /// Arc validity check
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. it is a real arc of the digraph.
 		    ///
 		    /// \warning A removed arc could become valid again if new arcs are
 		    /// added to the digraph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// Change the target node of an arc
 		    /// This function changes the target node of the given arc \c a to \c n.
 		    ///
 		    ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
-		    ///arc remain valid, however \c InArcIt iterators are invalidated.
+		    ///arc remain valid, but \c InArcIt iterators are invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeTarget(Arc a, Node n) {
 		      Parent::changeTarget(a,n);
+		    }
 		    /// Change the source node of an arc
 		    /// This function changes the source node of the given arc \c a to \c n.
 		    ///
 		    ///\note \c InArcIt iterators referencing the changed arc remain
-		    ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
+		    ///valid, but \c ArcIt and \c OutArcIt iterators are invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void changeSource(Arc a, Node n) {
 		      Parent::changeSource(a,n);
+		    }
 		    /// Reverse the direction of an arc.
 		    /// This function reverses the direction of the given arc.
 		    ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
 		    ///the changed arc are invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the Snapshot
 		    ///feature.
 		    void reverseArc(Arc a) {
 		      Node t=target(a);
 		      changeTarget(a,source(a));
 		      changeSource(a,t);
+		    }
 		    ///Contract two nodes.
 		    ///This function contracts the given two nodes.
 		    ///Node \c v is removed, but instead of deleting its
 		    ///incident arcs, they are joined to node \c u.
 		    ///If the last parameter \c r is \c true (this is the default value),
 		    ///then the newly created loops are removed.
 		    ///
 		    ///\note The moved arcs are joined to node \c u using changeSource()
 		    ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
 		    ///invalidated for the outgoing arcs of node \c v and \c InArcIt
@@ -530,65 +530,65 @@
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be large (e.g. it will contain millions of nodes and/or arcs),
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveArc()
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// Reserve memory for arcs.
 		    /// Using this function, it is possible to avoid superfluous memory
 		    /// allocation: if you know that the digraph you want to build will
 		    /// be large (e.g. it will contain millions of nodes and/or arcs),
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the digraph.
 		    /// \sa reserveNode()
 		    void reserveArc(int m) { arcs.reserve(m); };
 		    /// \brief Class to make a snapshot of the digraph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the digraph and restore it later.
 		    ///
 		    /// The newly added nodes and arcs can be removed using the
 		    /// restore() function.
 		    ///
 		    /// \note After a state is restored, you cannot restore a later state,
 		    /// i.e. you cannot add the removed nodes and arcs again using
 		    /// another Snapshot instance.
 		    ///
 		    /// \warning Node and arc deletions and other modifications (e.g.
 		    /// reversing, contracting, splitting arcs or nodes) cannot be
 		    /// restored. These events invalidate the snapshot.
 		    /// However the arcs and nodes that were added to the digraph after
+		    /// However, the arcs and nodes that were added to the digraph after
 		    /// making the current snapshot can be removed without invalidating it.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            snapshot.eraseNode(nodes[i]);
@@ -1257,65 +1257,65 @@
 		    /// i.e. it is a real edge of the graph.
 		    ///
 		    /// \warning A removed edge could become valid again if new edges are
 		    /// added to the graph.
 		    bool valid(Edge e) const { return Parent::valid(e); }
 		    /// Arc validity check
 		    /// This function gives back \c true if the given arc is valid,
 		    /// i.e. it is a real arc of the graph.
 		    ///
 		    /// \warning A removed arc could become valid again if new edges are
 		    /// added to the graph.
 		    bool valid(Arc a) const { return Parent::valid(a); }
 		    /// \brief Change the first node of an edge.
 		    ///
 		    /// This function changes the first node of the given edge \c e to \c n.
 		    ///
 		    ///\note \c EdgeIt and \c ArcIt iterators referencing the
 		    ///changed edge are invalidated and all other iterators whose
 		    ///base node is the changed node are also invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void changeU(Edge e, Node n) {
 		      Parent::changeU(e,n);
+		    }
 		    /// \brief Change the second node of an edge.
 		    ///
 		    /// This function changes the second node of the given edge \c e to \c n.
 		    ///
 		    ///\note \c EdgeIt iterators referencing the changed edge remain
-		    ///valid, however \c ArcIt iterators referencing the changed edge and
+		    ///valid, but \c ArcIt iterators referencing the changed edge and
 		    ///all other iterators whose base node is the changed node are also
 		    ///invalidated.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void changeV(Edge e, Node n) {
 		      Parent::changeV(e,n);
+		    }
 		    /// \brief Contract two nodes.
 		    ///
 		    /// This function contracts the given two nodes.
 		    /// Node \c b is removed, but instead of deleting
 		    /// its incident edges, they are joined to node \c a.
 		    /// If the last parameter \c r is \c true (this is the default value),
 		    /// then the newly created loops are removed.
 		    ///
 		    /// \note The moved edges are joined to node \c a using changeU()
 		    /// or changeV(), thus all edge and arc iterators whose base node is
 		    /// \c b are invalidated.
 		    /// Moreover all iterators referencing node \c b or the removed
 		    /// loops are also invalidated. Other iterators remain valid.
 		    ///
 		    ///\warning This functionality cannot be used together with the
 		    ///Snapshot feature.
 		    void contract(Node a, Node b, bool r = true) {
 		      for(IncEdgeIt e(*this, b); e!=INVALID;) {
 		        IncEdgeIt f = e; ++f;
 		        if (r && runningNode(e) == a) {
 		          erase(e);
 		        } else if (u(e) == b) {
 		          changeU(e, a);
@@ -1342,65 +1342,65 @@
 		    /// allocation: if you know that the graph you want to build will
 		    /// be large (e.g. it will contain millions of nodes and/or edges),
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the graph.
 		    /// \sa reserveEdge()
 		    void reserveNode(int n) { nodes.reserve(n); };
 		    /// Reserve memory for edges.
 		    /// Using this function, it is possible to avoid superfluous memory
 		    /// allocation: if you know that the graph you want to build will
 		    /// be large (e.g. it will contain millions of nodes and/or edges),
 		    /// then it is worth reserving space for this amount before starting
 		    /// to build the graph.
 		    /// \sa reserveNode()
 		    void reserveEdge(int m) { arcs.reserve(2 * m); };
 		    /// \brief Class to make a snapshot of the graph and restore
 		    /// it later.
 		    ///
 		    /// Class to make a snapshot of the graph and restore it later.
 		    ///
 		    /// The newly added nodes and edges can be removed
 		    /// using the restore() function.
 		    ///
 		    /// \note After a state is restored, you cannot restore a later state,
 		    /// i.e. you cannot add the removed nodes and edges again using
 		    /// another Snapshot instance.
 		    ///
 		    /// \warning Node and edge deletions and other modifications
 		    /// (e.g. changing the end-nodes of edges or contracting nodes)
 		    /// cannot be restored. These events invalidate the snapshot.
 		    /// However the edges and nodes that were added to the graph after
+		    /// However, the edges and nodes that were added to the graph after
 		    /// making the current snapshot can be removed without invalidating it.
 		    class Snapshot {
 		    protected:
 		      typedef Parent::NodeNotifier NodeNotifier;
 		      class NodeObserverProxy : public NodeNotifier::ObserverBase {
 		      public:
 		        NodeObserverProxy(Snapshot& _snapshot)
 		          : snapshot(_snapshot) {}
 		        using NodeNotifier::ObserverBase::attach;
 		        using NodeNotifier::ObserverBase::detach;
 		        using NodeNotifier::ObserverBase::attached;
 		      protected:
 		        virtual void add(const Node& node) {
 		          snapshot.addNode(node);
+		        }
 		        virtual void add(const std::vector<Node>& nodes) {
 		          for (int i = nodes.size() - 1; i >= 0; ++i) {
 		            snapshot.addNode(nodes[i]);
+		          }
+		        }
 		        virtual void erase(const Node& node) {
 		          snapshot.eraseNode(node);
+		        }
 		        virtual void erase(const std::vector<Node>& nodes) {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            snapshot.eraseNode(nodes[i]);

lemon/lp_base.h

Show inline comments

@@ -117,65 +117,65 @@
 		      /// \warning The default constructor sets the Col to an
 		      /// undefined value.
 		      Col() {}
 		      /// Invalid constructor \& conversion.
 		      /// This constructor initializes the Col to be invalid.
 		      /// \sa Invalid for more details.
 		      Col(const Invalid&) : _id(-1) {}
 		      /// Equality operator
 		      /// Two \ref Col "Col"s are equal if and only if they point to
 		      /// the same LP column or both are invalid.
 		      bool operator==(Col c) const  {return _id == c._id;}
 		      /// Inequality operator
 		      /// \sa operator==(Col c)
 		      ///
 		      bool operator!=(Col c) const  {return _id != c._id;}
 		      /// Artificial ordering operator.
 		      /// To allow the use of this object in std::map or similar
 		      /// associative container we require this.
 		      ///
 		      /// \note This operator only have to define some strict ordering of
 		      /// the items; this order has nothing to do with the iteration
 		      /// ordering of the items.
 		      bool operator<(Col c) const  {return _id < c._id;}
 		    };
 		    ///Iterator for iterate over the columns of an LP problem
 		    /// Its usage is quite simple, for example you can count the number
+		    /// Its usage is quite simple, for example, you can count the number
 		    /// of columns in an LP \c lp:
 		    ///\code
 		    /// int count=0;
 		    /// for (LpBase::ColIt c(lp); c!=INVALID; ++c) ++count;
 		    ///\endcode
 		    class ColIt : public Col {
 		      const LpBase *_solver;
 		    public:
 		      /// Default constructor
 		      /// \warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      ColIt() {}
 		      /// Sets the iterator to the first Col
 		      /// Sets the iterator to the first Col.
 		      ///
 		      ColIt(const LpBase &solver) : _solver(&solver)
+		      {
 		        _solver->cols.firstItem(_id);
+		      }
 		      /// Invalid constructor \& conversion
 		      /// Initialize the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      ColIt(const Invalid&) : Col(INVALID) {}
 		      /// Next column
 		      /// Assign the iterator to the next column.
 		      ///
 		      ColIt &operator++()
+		      {
@@ -212,65 +212,65 @@
 		      /// \warning The default constructor sets the Row to an
 		      /// undefined value.
 		      Row() {}
 		      /// Invalid constructor \& conversion.
 		      /// This constructor initializes the Row to be invalid.
 		      /// \sa Invalid for more details.
 		      Row(const Invalid&) : _id(-1) {}
 		      /// Equality operator
 		      /// Two \ref Row "Row"s are equal if and only if they point to
 		      /// the same LP row or both are invalid.
 		      bool operator==(Row r) const  {return _id == r._id;}
 		      /// Inequality operator
 		      /// \sa operator==(Row r)
 		      ///
 		      bool operator!=(Row r) const  {return _id != r._id;}
 		      /// Artificial ordering operator.
 		      /// To allow the use of this object in std::map or similar
 		      /// associative container we require this.
 		      ///
 		      /// \note This operator only have to define some strict ordering of
 		      /// the items; this order has nothing to do with the iteration
 		      /// ordering of the items.
 		      bool operator<(Row r) const  {return _id < r._id;}
 		    };
 		    ///Iterator for iterate over the rows of an LP problem
 		    /// Its usage is quite simple, for example you can count the number
+		    /// Its usage is quite simple, for example, you can count the number
 		    /// of rows in an LP \c lp:
 		    ///\code
 		    /// int count=0;
 		    /// for (LpBase::RowIt c(lp); c!=INVALID; ++c) ++count;
 		    ///\endcode
 		    class RowIt : public Row {
 		      const LpBase *_solver;
 		    public:
 		      /// Default constructor
 		      /// \warning The default constructor sets the iterator
 		      /// to an undefined value.
 		      RowIt() {}
 		      /// Sets the iterator to the first Row
 		      /// Sets the iterator to the first Row.
 		      ///
 		      RowIt(const LpBase &solver) : _solver(&solver)
+		      {
 		        _solver->rows.firstItem(_id);
+		      }
 		      /// Invalid constructor \& conversion
 		      /// Initialize the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      RowIt(const Invalid&) : Row(INVALID) {}
 		      /// Next row
 		      /// Assign the iterator to the next row.
 		      ///
 		      RowIt &operator++()
+		      {

lemon/maps.h

Show inline comments

@@ -201,68 +201,68 @@
 		  /// key as value without any modification.
 		  ///
 		  /// \sa ConstMap
 		  template <typename T>
 		  class IdentityMap : public MapBase<T, T> {
 		  public:
 		    ///\e
 		    typedef T Key;
 		    ///\e
 		    typedef T Value;
 		    /// Gives back the given value without any modification.
 		    Value operator[](const Key &k) const {
 		      return k;
+		    }
 		  };
 		  /// Returns an \c IdentityMap class
 		  /// This function just returns an \c IdentityMap class.
 		  /// \relates IdentityMap
 		  template<typename T>
 		  inline IdentityMap<T> identityMap() {
 		    return IdentityMap<T>();
+		  }
 		  /// \brief Map for storing values for integer keys from the range
 		  /// <tt>[0..size-1]</tt>.
 		  ///
 		  /// This map is essentially a wrapper for \c std::vector. It assigns
 		  /// values to integer keys from the range <tt>[0..size-1]</tt>.
 		  /// It can be used with some data structures, for example
 		  /// \c UnionFind, \c BinHeap, when the used items are small
 		  /// It can be used together with some data structures, e.g.
 		  /// heap types and \c UnionFind, when the used items are small
 		  /// integers. This map conforms to the \ref concepts::ReferenceMap
 		  /// "ReferenceMap" concept.
+		  /// "ReferenceMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the rangeMap()
 		  /// function.
 		  template <typename V>
 		  class RangeMap : public MapBase<int, V> {
 		    template <typename V1>
 		    friend class RangeMap;
 		  private:
 		    typedef std::vector<V> Vector;
 		    Vector _vector;
 		  public:
 		    /// Key type
 		    typedef int Key;
 		    /// Value type
 		    typedef V Value;
 		    /// Reference type
 		    typedef typename Vector::reference Reference;
 		    /// Const reference type
 		    typedef typename Vector::const_reference ConstReference;
 		    typedef True ReferenceMapTag;
 		  public:
 		    /// Constructor with specified default value.
 		    RangeMap(int size = 0, const Value &value = Value())
 		      : _vector(size, value) {}
 		    /// Constructs the map from an appropriate \c std::vector.
@@ -319,67 +319,67 @@
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
 		    return RangeMap<V>(size, value);
+		  }
 		  /// \brief Returns a \c RangeMap class created from an appropriate
 		  /// \c std::vector
 		  /// This function just returns a \c RangeMap class created from an
 		  /// appropriate \c std::vector.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
 		    return RangeMap<V>(vector);
+		  }
 		  /// Map type based on \c std::map
 		  /// This map is essentially a wrapper for \c std::map with addition
 		  /// that you can specify a default value for the keys that are not
 		  /// stored actually. This value can be different from the default
 		  /// contructed value (i.e. \c %Value()).
 		  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
 		  /// concept.
 		  ///
 		  /// This map is useful if a default value should be assigned to most of
 		  /// the keys and different values should be assigned only to a few
 		  /// keys (i.e. the map is "sparse").
 		  /// The name of this type also refers to this important usage.
 		  ///
 		  /// Apart form that this map can be used in many other cases since it
+		  /// Apart form that, this map can be used in many other cases since it
 		  /// is based on \c std::map, which is a general associative container.
 		  /// However keep in mind that it is usually not as efficient as other
+		  /// However, keep in mind that it is usually not as efficient as other
 		  /// maps.
 		  ///
 		  /// The simplest way of using this map is through the sparseMap()
 		  /// function.
 		  template <typename K, typename V, typename Comp = std::less<K> >
 		  class SparseMap : public MapBase<K, V> {
 		    template <typename K1, typename V1, typename C1>
 		    friend class SparseMap;
 		  public:
 		    /// Key type
 		    typedef K Key;
 		    /// Value type
 		    typedef V Value;
 		    /// Reference type
 		    typedef Value& Reference;
 		    /// Const reference type
 		    typedef const Value& ConstReference;
 		    typedef True ReferenceMapTag;
 		  private:
 		    typedef std::map<K, V, Comp> Map;
 		    Map _map;
 		    Value _value;
 		  public:
 		    /// \brief Constructor with specified default value.
 		    SparseMap(const Value &value = Value()) : _value(value) {}
 		    /// \brief Constructs the map from an appropriate \c std::map, and
@@ -1756,80 +1756,80 @@
 		    /// Constructor
 		    LoggerBoolMap(Iterator it)
 		      : _begin(it), _end(it) {}
 		    /// Gives back the given iterator set for the first key
 		    Iterator begin() const {
 		      return _begin;
+		    }
 		    /// Gives back the the 'after the last' iterator
 		    Iterator end() const {
 		      return _end;
+		    }
 		    /// The set function of the map
 		    void set(const Key& key, Value value) {
 		      if (value) {
 		        *_end++ = key;
+		      }
+		    }
 		  private:
 		    Iterator _begin;
 		    Iterator _end;
 		  };
 		  /// Returns a \c LoggerBoolMap class
 		  /// This function just returns a \c LoggerBoolMap class.
 		  ///
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  /// For example it makes easier to store the nodes in the processing
+		  /// For example, it makes easier to store the nodes in the processing
 		  /// order of Dfs algorithm, as the following examples show.
 		  /// \code
 		  ///   std::vector<Node> v;
 		  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
 		  /// \endcode
 		  /// \code
 		  ///   std::vector<Node> v(countNodes(g));
 		  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
 		  /// \endcode
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		  ///
 		  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
 		  /// it cannot be used when a readable map is needed, for example as
+		  /// it cannot be used when a readable map is needed, for example, as
 		  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
 		  ///
 		  /// \relates LoggerBoolMap
 		  template<typename Iterator>
 		  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
 		    return LoggerBoolMap<Iterator>(it);
+		  }
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// \brief Provides an immutable and unique id for each item in a graph.
 		  ///
 		  /// IdMap provides a unique and immutable id for each item of the
 		  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
 		  ///  - \b unique: different items get different ids,
 		  ///  - \b immutable: the id of an item does not change (even if you
 		  ///    delete other nodes).
 		  ///
 		  /// Using this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph, which is returned by the \c id()
 		  /// function of the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator()() member.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see RangeIdMap
 		  template <typename GR, typename K>
@@ -1893,65 +1893,65 @@
 		      const Graph* _graph;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the IdMap.
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief Returns an \c IdMap class.
 		  ///
 		  /// This function just returns an \c IdMap class.
 		  /// \relates IdMap
 		  template <typename K, typename GR>
 		  inline IdMap<GR, K> idMap(const GR& graph) {
 		    return IdMap<GR, K>(graph);
+		  }
 		  /// \brief General cross reference graph map type.
 		  /// This class provides simple invertable graph maps.
 		  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
 		  /// and if a key is set to a new value, then stores it in the inverse map.
 		  /// The graph items can be accessed by their values either using
 		  /// \c InverseMap or \c operator()(), and the values of the map can be
 		  /// accessed with an STL compatible forward iterator (\c ValueIt).
 		  ///
 		  /// This map is intended to be used when all associated values are
 		  /// different (the map is actually invertable) or there are only a few
 		  /// items with the same value.
 		  /// Otherwise consider to use \c IterableValueMap, which is more
 		  /// suitable and more efficient for such cases. It provides iterators
-		  /// to traverse the items with the same associated value, however
+		  /// to traverse the items with the same associated value, but
 		  /// it does not have \c InverseMap.
 		  ///
 		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscript operator.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  /// \tparam V The value type of the map.
 		  ///
 		  /// \see IterableValueMap
 		  template <typename GR, typename K, typename V>
 		  class CrossRefMap
 		    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
 		  private:
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<V>::Type Map;
 		    typedef std::multimap<V, K> Container;
 		    Container _inv_map;
 		  public:
 		    /// The graph type of CrossRefMap.
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Item;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Key;
 		    /// The value type of CrossRefMap.
@@ -3437,65 +3437,65 @@
 		    explicit BackwardMap(const GR& graph) : _graph(graph) {}
 		    /// \brief Returns the "backward" directed arc view of the given edge.
 		    ///
 		    /// Returns the "backward" directed arc view of the given edge.
 		    Value operator[](const Key& key) const {
 		      return _graph.direct(key, false);
+		    }
 		  private:
 		    const GR& _graph;
 		  };
 		  /// \brief Returns a \c BackwardMap class
 		  /// This function just returns a \c BackwardMap class.
 		  /// \relates BackwardMap
 		  template <typename GR>
 		  inline BackwardMap<GR> backwardMap(const GR& graph) {
 		    return BackwardMap<GR>(graph);
+		  }
 		  /// \brief Map of the in-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the in-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// may provide alternative ways to modify the digraph.
 		  /// The correct behavior of InDegMap is not guarantied if these additional
 		  /// features are used. For example the functions
+		  /// features are used. For example, the functions
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa OutDegMap
 		  template <typename GR>
 		  class InDegMap
 		    : protected ItemSetTraits<GR, typename GR::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    /// The graph type of InDegMap
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type
 		    typedef typename Digraph::Node Key;
 		    /// The value type
 		    typedef int Value;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap
 		      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
 		    public:
 		      typedef typename ItemSetTraits<Digraph, Key>::
 		      template Map<int>::Type Parent;
@@ -3567,65 +3567,65 @@
 		      for (int i = 0; i < int(arcs.size()); ++i) {
 		        --_deg[_digraph.target(arcs[i])];
+		      }
+		    }
 		    virtual void build() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = countInArcs(_digraph, it);
+		      }
+		    }
 		    virtual void clear() {
 		      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
 		        _deg[it] = 0;
+		      }
+		    }
 		  private:
 		    const Digraph& _digraph;
 		    AutoNodeMap _deg;
 		  };
 		  /// \brief Map of the out-degrees of nodes in a digraph.
 		  ///
 		  /// This map returns the out-degree of a node. Once it is constructed,
 		  /// the degrees are stored in a standard \c NodeMap, so each query is done
 		  /// in constant time. On the other hand, the values are updated automatically
 		  /// whenever the digraph changes.
 		  ///
 		  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
 		  /// may provide alternative ways to modify the digraph.
 		  /// The correct behavior of OutDegMap is not guarantied if these additional
 		  /// features are used. For example the functions
+		  /// features are used. For example, the functions
 		  /// \ref ListDigraph::changeSource() "changeSource()",
 		  /// \ref ListDigraph::changeTarget() "changeTarget()" and
 		  /// \ref ListDigraph::reverseArc() "reverseArc()"
 		  /// of \ref ListDigraph will \e not update the degree values correctly.
 		  ///
 		  /// \sa InDegMap
 		  template <typename GR>
 		  class OutDegMap
 		    : protected ItemSetTraits<GR, typename GR::Arc>
 		      ::ItemNotifier::ObserverBase {
 		  public:
 		    /// The graph type of OutDegMap
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type
 		    typedef typename Digraph::Node Key;
 		    /// The value type
 		    typedef int Value;
 		    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		  private:
 		    class AutoNodeMap
 		      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
 		    public:
 		      typedef typename ItemSetTraits<Digraph, Key>::
 		      template Map<int>::Type Parent;

lemon/network_simplex.h

Show inline comments

@@ -21,167 +21,167 @@
 		/// \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 specialized version of the linear programming
 		  /// simplex method directly for the minimum cost flow problem.
 		  /// It is one of the most efficient solution methods.
 		  ///
 		  /// In general this class is the fastest implementation available
 		  /// in LEMON for the minimum cost flow problem.
 		  /// Moreover it supports both directions of the supply/demand inequality
 		  /// constraints. For more information see \ref SupplyType.
+		  /// 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 value type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default it is \c int.
+		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The value type used for costs and potentials in the
 		  /// algorithm. By default it is the same as \c V.
+		  /// algorithm. By default, it is the same as \c V.
 		  ///
 		  /// \warning Both value types must be signed and all input data 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.
+		  /// 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
+		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
 		    /// proved to be the most efficient and the most robust on various
 		    /// test inputs according to our benchmark tests.
 		    /// However another pivot rule can be selected using the \ref run()
+		    /// However, another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum PivotRule {
 		      /// The First Eligible pivot rule.
+		      /// The \e First \e Eligible pivot rule.
 		      /// The next eligible arc is selected in a wraparound fashion
 		      /// in every iteration.
 		      FIRST_ELIGIBLE,
 		      /// The Best Eligible pivot rule.
+		      /// The \e Best \e Eligible pivot rule.
 		      /// The best eligible arc is selected in every iteration.
 		      BEST_ELIGIBLE,
 		      /// The Block Search pivot rule.
+		      /// 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 Candidate List pivot rule.
+		      /// 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 Altering Candidate List pivot rule.
+		      /// 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<bool> BoolVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    // State constants for arcs
 		    enum ArcStateEnum {
 		      STATE_UPPER = -1,
 		      STATE_TREE  =  0,
 		      STATE_LOWER =  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
@@ -783,126 +783,126 @@
 		    /// \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
 		    /// 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.
+		    /// 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)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the parameters
 		    /// that have been given are kept for the next call, unless
 		    /// \ref reset() is called, thus only the modified parameters
 		    /// have to be set again. See \ref reset() for examples.
 		    /// However the underlying digraph must not be modified after this
+		    /// However, the underlying digraph must not be modified after this
 		    /// class have been constructed, since it copies and extends the graph.
 		    ///
 		    /// \param pivot_rule The pivot rule that will be used during the
 		    /// algorithm. For more information see \ref PivotRule.
+		    /// algorithm. For more information, see \ref PivotRule.
 		    ///
 		    /// \return \c INFEASIBLE if no feasible flow exists,
 		    /// \n \c OPTIMAL if 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),
 		    /// \n \c UNBOUNDED if the objective function of the problem is
 		    /// unbounded, i.e. there is a directed cycle having negative total
 		    /// cost and infinite upper bound.
 		    ///
 		    /// \see ProblemType, PivotRule
 		    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
 		      if (!init()) return INFEASIBLE;
 		      return start(pivot_rule);
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
 		    ///
 		    /// It is useful for multiple run() calls. If this function is not
 		    /// used, all the parameters given before are kept for the next
 		    /// \ref run() call.
 		    /// However the underlying digraph must not be modified after this
+		    /// However, the underlying digraph must not be modified after this
 		    /// class have been constructed, since it copies and extends the graph.
 		    ///
 		    /// For example,
 		    /// \code
 		    ///   NetworkSimplex<ListDigraph> ns(graph);
 		    ///
 		    ///   // First run
 		    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
 		    ///   // Run again with modified cost map (reset() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   ns.costMap(cost).run();
 		    ///
 		    ///   // Run again from scratch using reset()
 		    ///   // (the lower bounds will be set to zero on all arcs)
 		    ///   ns.reset();
 		    ///   ns.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    NetworkSimplex& reset() {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      for (int i = 0; i != _arc_num; ++i) {
 		        _lower[i] = 0;
 		        _upper[i] = INF;
 		        _cost[i] = 1;
+		      }

lemon/preflow.h

Show inline comments

@@ -236,65 +236,65 @@
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
+		    /// However, an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Preflow<Digraph, CapacityMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Preflow() {}
 		  public:
 		    /// \brief The constructor of the class.
 		    ///
 		    /// The constructor of the class.
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param capacity The capacity of the arcs.
 		    /// \param source The source node.
 		    /// \param target The target node.
 		    Preflow(const Digraph& digraph, const CapacityMap& capacity,
 		            Node source, Node target)
 		      : _graph(digraph), _capacity(&capacity),
 		        _node_num(0), _source(source), _target(target),
 		        _flow(0), _local_flow(false),

lemon/time_measure.h

Show inline comments

@@ -346,65 +346,65 @@
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Halt (i.e stop immediately) the time counters
 		    ///This function stops immediately the time counters, i.e. <tt>t.halt()</tt>
 		    ///is a faster
 		    ///equivalent of the following.
 		    ///\code
 		    ///  while(t.running()) t.stop()
 		    ///\endcode
 		    ///
 		    ///
 		    ///\sa stop()
 		    ///\sa restart()
 		    ///\sa reset()
 		    void halt()
+		    {
 		      if(_running) {
 		        _running=0;
 		        TimeStamp t;
 		        t.stamp();
 		        start_time=t-start_time;
+		      }
+		    }
 		    ///Returns the running state of the timer
 		    ///This function returns the number of stop() exections that is
 		    ///necessary to really stop the timer.
 		    ///For example the timer
+		    ///For example, the timer
 		    ///is running if and only if the return value is \c true
 		    ///(i.e. greater than
 		    ///zero).
 		    int running()  { return _running; }
 		    ///Restart the time counters
 		    ///This function is a shorthand for
 		    ///a reset() and a start() calls.
 		    ///
 		    void restart()
+		    {
 		      reset();
 		      start();
+		    }
 		    ///@}
 		    ///\name Query Functions for the Ellapsed Time
 		    ///@{
 		    ///Gives back the ellapsed user time of the process
 		    double userTime() const
+		    {
 		      return operator TimeStamp().userTime();
+		    }
 		    ///Gives back the ellapsed system time of the process
 		    double systemTime() const
+		    {
 		      return operator TimeStamp().systemTime();

lemon/unionfind.h

Show inline comments

@@ -14,65 +14,65 @@
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_UNION_FIND_H
 		#define LEMON_UNION_FIND_H
 		//!\ingroup auxdat
 		//!\file
 		//!\brief Union-Find data structures.
 		//!
 		#include <vector>
 		#include <list>
 		#include <utility>
 		#include <algorithm>
 		#include <functional>
 		#include <lemon/core.h>
 		namespace lemon {
 		  /// \ingroup auxdat
 		  ///
 		  /// \brief A \e Union-Find data structure implementation
 		  ///
 		  /// The class implements the \e Union-Find data structure.
 		  /// The union operation uses rank heuristic, while
 		  /// the find operation uses path compression.
 		  /// This is a very simple but efficient implementation, providing
 		  /// only four methods: join (union), find, insert and size.
 		  /// For more features see the \ref UnionFindEnum class.
+		  /// For more features, see the \ref UnionFindEnum class.
 		  ///
 		  /// It is primarily used in Kruskal algorithm for finding minimal
 		  /// cost spanning tree in a graph.
 		  /// \sa kruskal()
 		  ///
 		  /// \pre You need to add all the elements by the \ref insert()
 		  /// method.
 		  template <typename IM>
 		  class UnionFind {
 		  public:
 		    ///\e
 		    typedef IM ItemIntMap;
 		    ///\e
 		    typedef typename ItemIntMap::Key Item;
 		  private:
 		    // If the items vector stores negative value for an item then
 		    // that item is root item and it has -items[it] component size.
 		    // Else the items[it] contains the index of the parent.
 		    std::vector<int> items;
 		    ItemIntMap& index;
 		    bool rep(int idx) const {
 		      return items[idx] < 0;
+		    }
 		    int repIndex(int idx) const {
 		      int k = idx;
 		      while (!rep(k)) {
 		        k = items[k] ;
+		      }

0 comments (0 inline)

RhodeCode

Login to your account