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:

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

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

doc/min_cost_flow.dox

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.
+		 *
 		 */
 		namespace lemon {
 		/**
 		\page min_cost_flow Minimum Cost Flow Problem
 		\section mcf_def Definition (GEQ form)
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints (lower and upper bounds)
 		and arc costs \ref amo93networkflows.
 		Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
 		\f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and
 		upper bounds for the flow values on the arcs, for which
 		\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
 		\f$cost: A\rightarrow\mathbf{R}\f$ denotes the cost per unit flow
 		on the arcs and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the
 		signed supply values of the nodes.
 		If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		\f$-sup(u)\f$ demand.
 		A minimum cost flow is an \f$f: A\rightarrow\mathbf{R}\f$ solution
 		of the following optimization problem.
 		\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) \geq
 		    sup(u) \quad \forall u\in V \f]
 		\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
 		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
 		when there are <em>"less or equal"</em> (LEQ) supply/demand constraints,
 		instead of the <em>"greater or equal"</em> (GEQ) constraints.
 		\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

@@ -47,946 +47,946 @@
 		  struct BellmanFordDefaultOperationTraits {
 		    /// \e
 		    typedef V Value;
 		    /// \brief Gives back the zero value of the type.
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    /// \brief Gives back the positive infinity value of the type.
 		    static Value infinity() {
 		      return std::numeric_limits<Value>::infinity();
+		    }
 		    /// \brief Gives back the sum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return left + right;
+		    }
 		    /// \brief Gives back \c true only if the first value is less than
 		    /// the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  template <typename V>
 		  struct BellmanFordDefaultOperationTraits<V, false> {
 		    typedef V Value;
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    static Value infinity() {
 		      return std::numeric_limits<Value>::max();
+		    }
 		    static Value plus(const Value& left, const Value& right) {
 		      if (left == infinity() || right == infinity()) return infinity();
 		      return left + right;
+		    }
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  /// \brief Default traits class of BellmanFord class.
 		  ///
 		  /// Default traits class of BellmanFord class.
 		  /// \param GR The type of the digraph.
 		  /// \param LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  struct BellmanFordDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc lengths.
 		    ///
 		    /// The type of the map that stores the arc lengths.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the
 		    /// given \c Value type.
 		    /// \see BellmanFordDefaultOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last arcs of the
 		    /// shortest paths.
 		    ///
 		    /// The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief 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 GR& g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief 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 GR::template NodeMap<typename LEN::Value> DistMap;
 		    /// \brief 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 GR& g) {
 		      return new DistMap(g);
+		    }
 		  };
 		  /// \brief %BellmanFord algorithm class.
 		  ///
 		  /// \ingroup shortest_path
 		  /// This class provides an efficient implementation of the Bellman-Ford
 		  /// algorithm. The maximum time complexity of the algorithm is
 		  /// <tt>O(ne)</tt>.
 		  ///
 		  /// The Bellman-Ford algorithm solves the single-source shortest path
 		  /// problem when the arcs can have negative lengths, but the digraph
 		  /// should not contain directed cycles with negative total length.
 		  /// If all arc costs are non-negative, consider to use the Dijkstra
 		  /// algorithm instead, since it is more efficient.
 		  ///
 		  /// The arc lengths are passed to the algorithm using a
 		  /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
 		  /// kind of length. The type of the length values is determined by the
 		  /// \ref concepts::ReadMap::Value "Value" type of the length map.
 		  ///
 		  /// There is also a \ref bellmanFord() "function-type interface" for the
 		  /// Bellman-Ford algorithm, which is convenient in the simplier cases and
 		  /// it can be used easier.
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// The default type is \ref ListDigraph.
 		  /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
 		  /// the lengths of the arcs. The default map type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=BellmanFordDefaultTraits<GR,LEN> >
 		#endif
 		  class BellmanFord {
 		  public:
 		    ///The type of the underlying digraph.
 		    typedef typename TR::Digraph Digraph;
 		    /// \brief The type of the arc lengths.
 		    typedef typename TR::LengthMap::Value Value;
 		    /// \brief The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    /// \brief The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    /// \brief The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    /// The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///\brief The \ref BellmanFordDefaultOperationTraits
 		    /// "operation traits class" of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    // Pointer to the underlying digraph.
 		    const Digraph *_gr;
 		    // Pointer to the length map
 		    const LengthMap *_length;
 		    // Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    // Indicates if _pred is locally allocated (true) or not.
 		    bool _local_pred;
 		    // Pointer to the map of distances.
 		    DistMap *_dist;
 		    // Indicates if _dist is locally allocated (true) or not.
 		    bool _local_dist;
 		    typedef typename Digraph::template NodeMap<bool> MaskMap;
 		    MaskMap *_mask;
 		    std::vector<Node> _process;
 		    // Creates the maps if necessary.
 		    void create_maps() {
 		      if(!_pred) {
 			_local_pred = true;
 			_pred = Traits::createPredMap(*_gr);
+		      }
 		      if(!_dist) {
 			_local_dist = true;
 			_dist = Traits::createDistMap(*_gr);
+		      }
 		      _mask = new MaskMap(*_gr, false);
+		    }
 		  public :
 		    typedef BellmanFord Create;
 		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph&) {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting
 		    /// \c PredMap type.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    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;
+		    }
 		    /// \brief Sets the length map.
 		    ///
 		    /// Sets the length map.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &lengthMap(const LengthMap &map) {
 		      _length = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the map that stores the predecessor arcs.
 		    ///
 		    /// Sets the map that stores the predecessor arcs.
 		    /// If you don't use this function before calling \ref run()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &predMap(PredMap &map) {
 		      if(_local_pred) {
 			delete _pred;
 			_local_pred=false;
+		      }
 		      _pred = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the map that stores the distances of the nodes.
 		    ///
 		    /// Sets the map that stores the distances of the nodes calculated
 		    /// by the algorithm.
 		    /// If you don't use this function before calling \ref run()
 		    /// or \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    BellmanFord &distMap(DistMap &map) {
 		      if(_local_dist) {
 			delete _dist;
 			_local_dist=false;
+		      }
 		      _dist = &map;
 		      return *this;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the Bellman-Ford algorithm is to use
 		    /// one of the member functions called \ref run().\n
 		    /// If you need better control on the execution, you have to call
 		    /// \ref init() first, then you can add several source nodes
 		    /// with \ref addSource(). Finally the actual path computation can be
 		    /// performed with \ref start(), \ref checkedStart() or
 		    /// \ref limitedStart().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures. The optional parameter
 		    /// is the initial distance of each node.
 		    void init(const Value value = OperationTraits::infinity()) {
 		      create_maps();
 		      for (NodeIt it(*_gr); it != INVALID; ++it) {
 			_pred->set(it, INVALID);
 			_dist->set(it, value);
+		      }
 		      _process.clear();
 		      if (OperationTraits::less(value, OperationTraits::infinity())) {
 			for (NodeIt it(*_gr); it != INVALID; ++it) {
 			  _process.push_back(it);
 			  _mask->set(it, true);
+			}
+		      }
+		    }
 		    /// \brief Adds a new source node.
 		    ///
 		    /// This function adds a new source node. The optional second parameter
 		    /// is the initial distance of the node.
 		    void addSource(Node source, Value dst = OperationTraits::zero()) {
 		      _dist->set(source, dst);
 		      if (!(*_mask)[source]) {
 			_process.push_back(source);
 			_mask->set(source, true);
+		      }
+		    }
 		    /// \brief Executes one round from the Bellman-Ford algorithm.
 		    ///
 		    /// If the algoritm calculated the distances in the previous round
 		    /// exactly for the paths of at most \c k arcs, then this function
 		    /// will calculate the distances exactly for the paths of at most
 		    /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
 		    /// calculates the shortest path distances exactly for the paths
 		    /// consisting of at most \c k arcs.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \return \c true when the algorithm have not found more shorter
 		    /// paths.
 		    ///
 		    /// \see ActiveIt
 		    bool processNextRound() {
 		      for (int i = 0; i < int(_process.size()); ++i) {
 			_mask->set(_process[i], false);
+		      }
 		      std::vector<Node> nextProcess;
 		      std::vector<Value> values(_process.size());
 		      for (int i = 0; i < int(_process.size()); ++i) {
 			values[i] = (*_dist)[_process[i]];
+		      }
 		      for (int i = 0; i < int(_process.size()); ++i) {
 			for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
 			  Node target = _gr->target(it);
 			  Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
 			  if (OperationTraits::less(relaxed, (*_dist)[target])) {
 			    _pred->set(target, it);
 			    _dist->set(target, relaxed);
 			    if (!(*_mask)[target]) {
 			      _mask->set(target, true);
 			      nextProcess.push_back(target);
+			    }
+			  }
+			}
+		      }
 		      _process.swap(nextProcess);
 		      return _process.empty();
+		    }
 		    /// \brief Executes one weak round from the Bellman-Ford algorithm.
 		    ///
 		    /// If the algorithm calculated the distances in the previous round
 		    /// at least for the paths of at most \c k arcs, then this function
 		    /// will calculate the distances at least for the paths of at most
 		    /// <tt>k+1</tt> arcs.
 		    /// This function does not make it possible to calculate the shortest
 		    /// path distances exactly for paths consisting of at most \c k arcs,
 		    /// this is why it is called weak round.
 		    ///
 		    /// \return \c true when the algorithm have not found more shorter
 		    /// paths.
 		    ///
 		    /// \see ActiveIt
 		    bool processNextWeakRound() {
 		      for (int i = 0; i < int(_process.size()); ++i) {
 			_mask->set(_process[i], false);
+		      }
 		      std::vector<Node> nextProcess;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 			for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
 			  Node target = _gr->target(it);
 			  Value relaxed =
 			    OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
 			  if (OperationTraits::less(relaxed, (*_dist)[target])) {
 			    _pred->set(target, it);
 			    _dist->set(target, relaxed);
 			    if (!(*_mask)[target]) {
 			      _mask->set(target, true);
 			      nextProcess.push_back(target);
+			    }
+			  }
+			}
+		      }
 		      _process.swap(nextProcess);
 		      return _process.empty();
+		    }
 		    /// \brief Executes the algorithm.
 		    ///
 		    /// Executes the algorithm.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    void start() {
 		      int num = countNodes(*_gr) - 1;
 		      for (int i = 0; i < num; ++i) {
 			if (processNextWeakRound()) break;
+		      }
+		    }
 		    /// \brief Executes the algorithm and checks the negative cycles.
 		    ///
 		    /// Executes the algorithm and checks the negative cycles.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path to each node and also checks
 		    /// if the digraph contains cycles with negative total length.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \return \c false if there is a negative cycle in the digraph.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    bool checkedStart() {
 		      int num = countNodes(*_gr);
 		      for (int i = 0; i < num; ++i) {
 			if (processNextWeakRound()) return true;
+		      }
 		      return _process.empty();
+		    }
 		    /// \brief Executes the algorithm with arc number limit.
 		    ///
 		    /// Executes the algorithm with arc number limit.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the root node(s)
 		    /// in order to compute the shortest path distance for each node
 		    /// using only the paths consisting of at most \c num arcs.
 		    ///
 		    /// The algorithm computes
 		    /// - the limited distance of each node from the root(s),
 		    /// - the predecessor arc for each node.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \pre init() must be called and at least one root node should be
 		    /// added with addSource() before using this function.
 		    void limitedStart(int num) {
 		      for (int i = 0; i < num; ++i) {
 			if (processNextRound()) break;
+		      }
+		    }
 		    /// \brief Runs the algorithm from the given root node.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given root
 		    /// node \c s in order to compute the shortest path to each node.
 		    ///
 		    /// The algorithm computes
 		    /// - the shortest path tree (forest),
 		    /// - the distance of each node from the root(s).
 		    ///
 		    /// \note bf.run(s) is just a shortcut of the following code.
 		    /// \code
 		    ///   bf.init();
 		    ///   bf.addSource(s);
 		    ///   bf.start();
 		    /// \endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    /// \brief Runs the algorithm from the given root node with arc
 		    /// number limit.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given root
 		    /// node \c s in order to compute the shortest path distance for each
 		    /// node using only the paths consisting of at most \c num arcs.
 		    ///
 		    /// The algorithm computes
 		    /// - the limited distance of each node from the root(s),
 		    /// - the predecessor arc for each node.
 		    ///
 		    /// \warning The paths with limited arc number cannot be retrieved
 		    /// easily with \ref path() or \ref predArc() functions. If you also
 		    /// need the shortest paths and not only the distances, you should
 		    /// store the \ref predMap() "predecessor map" after each iteration
 		    /// and build the path manually.
 		    ///
 		    /// \note bf.run(s, num) is just a shortcut of the following code.
 		    /// \code
 		    ///   bf.init();
 		    ///   bf.addSource(s);
 		    ///   bf.limitedStart(num);
 		    /// \endcode
 		    void run(Node s, int num) {
 		      init();
 		      addSource(s);
 		      limitedStart(num);
+		    }
 		    ///@}
 		    /// \brief LEMON iterator for getting the active nodes.
 		    ///
 		    /// This class provides a common style LEMON iterator that traverses
 		    /// the active nodes of the Bellman-Ford algorithm after the last
 		    /// phase. These nodes should be checked in the next phase to
 		    /// find augmenting arcs outgoing from them.
 		    class ActiveIt {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for getting the active nodes of the given BellmanFord
 		      /// instance.
 		      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+		      {
 		        _index = _algorithm->_process.size() - 1;
+		      }
 		      /// \brief Invalid constructor.
 		      ///
 		      /// Invalid constructor.
 		      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
 		      /// \brief Conversion to \c Node.
 		      ///
 		      /// Conversion to \c Node.
 		      operator Node() const {
 		        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      ActiveIt& operator++() {
 		        --_index;
 		        return *this;
+		      }
 		      bool operator==(const ActiveIt& it) const {
 		        return static_cast<Node>(*this) == static_cast<Node>(it);
+		      }
 		      bool operator!=(const ActiveIt& it) const {
 		        return static_cast<Node>(*this) != static_cast<Node>(it);
+		      }
 		      bool operator<(const ActiveIt& it) const {
 		        return static_cast<Node>(*this) < static_cast<Node>(it);
+		      }
 		    private:
 		      const BellmanFord* _algorithm;
 		      int _index;
 		    };
 		    /// \name Query Functions
 		    /// The result of the Bellman-Ford algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either \ref run() or \ref init() should be called before using them.
 		    ///@{
 		    /// \brief The shortest path to the given node.
 		    ///
 		    /// 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
 		    /// using this function.
 		    bool reached(Node v) const {
 		      return (*_dist)[v] != OperationTraits::infinity();
+		    }
 		    /// \brief Gives back a negative cycle.
 		    ///
 		    /// This function gives back a directed cycle with negative total
 		    /// length if the algorithm has already found one.
 		    /// Otherwise it gives back an empty path.
 		    lemon::Path<Digraph> negativeCycle() const {
 		      typename Digraph::template NodeMap<int> state(*_gr, -1);
 		      lemon::Path<Digraph> cycle;
 		      for (int i = 0; i < int(_process.size()); ++i) {
 		        if (state[_process[i]] != -1) continue;
 		        for (Node v = _process[i]; (*_pred)[v] != INVALID;
 		             v = _gr->source((*_pred)[v])) {
 		          if (state[v] == i) {
 		            cycle.addFront((*_pred)[v]);
 		            for (Node u = _gr->source((*_pred)[v]); u != v;
 		                 u = _gr->source((*_pred)[u])) {
 		              cycle.addFront((*_pred)[u]);
+		            }
 		            return cycle;
+		          }
 		          else if (state[v] >= 0) {
 		            break;
+		          }
 		          state[v] = i;
+		        }
+		      }
 		      return cycle;
+		    }
 		    ///@}
 		  };
 		  /// \brief Default traits class of bellmanFord() function.
 		  ///
 		  /// Default traits class of bellmanFord() function.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  struct BellmanFordWizardDefaultTraits {
 		    /// The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc lengths.
 		    ///
 		    /// The type of the map that stores the arc lengths.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    /// The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// \brief Operation traits for Bellman-Ford algorithm.
 		    ///
 		    /// It defines the used operations and the infinity value for the
 		    /// given \c Value type.
 		    /// \see BellmanFordDefaultOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last
 		    /// arcs of the shortest paths.
 		    ///
 		    /// The type of the map that stores the last arcs of the shortest paths.
 		    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
 		    /// \brief 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 GR &g) {
 		      return new PredMap(g);
+		    }
 		    /// \brief 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 GR::template NodeMap<Value> DistMap;
 		    /// \brief 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 GR &g) {
 		      return new DistMap(g);
+		    }
 		    ///The type of the shortest paths.
 		    ///The type of the shortest paths.
 		    ///It must meet the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// \brief Default traits class used by BellmanFordWizard.
 		  ///
 		  /// Default traits class used by BellmanFordWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template <typename GR, typename LEN>
 		  class BellmanFordWizardBase
 		    : public BellmanFordWizardDefaultTraits<GR, LEN> {
 		    typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
 		  protected:
 		    // Type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    // Pointer to the underlying digraph.
 		    void *_graph;
 		    // Pointer to the length map
 		    void *_length;
 		    // Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    // Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    void *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to default values \c 0.
 		    BellmanFordWizardBase() :
 		      _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizardBase(const GR& gr,
 					  const LEN& len) :
 		      _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
 		      _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
 		      _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// \brief Auxiliary class for the function-type interface of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  ///
 		  /// This auxiliary class is created to implement the
 		  /// \ref bellmanFord() "function-type interface" of the
 		  /// \ref BellmanFord "Bellman-Ford" algorithm.
 		  /// It does not have own \ref run() method, it uses the
 		  /// functions and features of the plain \ref BellmanFord.
 		  ///
 		  /// This class should only be used through the \ref bellmanFord()
 		  /// function, which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BellmanFordWizard : public TR {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt ArcIt;
 		    typedef typename TR::LengthMap LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BellmanFordWizard() : TR() {}
 		    /// \brief Constructor that requires parameters.
 		    ///
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param gr The digraph the algorithm runs on.
 		    /// \param len The length map.
 		    BellmanFordWizard(const Digraph& gr, const LengthMap& len)
 		      : TR(gr, len) {}
 		    /// \brief Copy constructor
 		    BellmanFordWizard(const TR &b) : TR(b) {}
 		    ~BellmanFordWizard() {}
 		    /// \brief Runs the Bellman-Ford algorithm from the given source node.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from the given source
 		    /// node in order to compute the shortest path to each node.
 		    void run(Node s) {
 		      BellmanFord<Digraph,LengthMap,TR>
 			bf(*reinterpret_cast<const Digraph*>(Base::_graph),
 		           *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      bf.run(s);
+		    }
 		    /// \brief Runs the Bellman-Ford algorithm to find the shortest path
 		    /// between \c s and \c t.
 		    ///
 		    /// This method runs the Bellman-Ford algorithm from node \c s
 		    /// in order to compute the shortest path to node \c t.
 		    /// Actually, it computes the shortest path to each node, but using
 		    /// this function you can retrieve the distance and the shortest path
 		    /// for a single target node easier.
 		    ///
 		    /// \return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t) {
 		      BellmanFord<Digraph,LengthMap,TR>
 		        bf(*reinterpret_cast<const Digraph*>(Base::_graph),
 		           *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));

lemon/bfs.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.
+		 *
 		 */
 		#ifndef LEMON_BFS_H
 		#define LEMON_BFS_H
 		///\ingroup search
 		///\file
 		///\brief BFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///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.
 		    ///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<int> 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);
+		    }
 		  };
 		  ///%BFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %BFS algorithm.
 		  ///
 		  ///There is also a \ref bfs() "function-type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
 		#endif
 		  class Bfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::Node> _queue;
 		    int _queue_head,_queue_tail,_queue_next_dist;
 		    int _curr_dist;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    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 Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Bfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Bfs(const Digraph &g) :
@@ -595,513 +595,513 @@
+		    }
 		    ///Executes the algorithm until the given target node is reached.
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s)
 		    ///in order to compute the shortest path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path to \c t,
 		    ///- the distance of \c t from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  bool reach = false;
 		    ///  while ( !b.emptyQueue() && !reach ) {
 		    ///    b.processNextNode(t, reach);
 		    ///  }
 		    ///\endcode
 		    void start(Node t)
+		    {
 		      bool reach = false;
 		      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %BFS algorithm from the root node(s) in
 		    ///order to compute the shortest path to a node \c v with
 		    /// <tt>nm[v]</tt> true, if such a node can be found.
 		    ///
 		    ///\param nm A \c bool (or convertible) node map. The algorithm
 		    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
 		    ///
 		    ///\return The reached node \c v with <tt>nm[v]</tt> true or
 		    ///\c INVALID if no such node was found.
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  Node rnode = INVALID;
 		    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
 		    ///    b.processNextNode(nm, rnode);
 		    ///  }
 		    ///  return rnode;
 		    ///\endcode
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      Node rnode = INVALID;
 		      while ( !emptyQueue() && rnode == INVALID ) {
 		        processNextNode(nm, rnode);
+		      }
 		      return rnode;
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  b.addSource(s);
 		    ///  b.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    ///
 		    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  b.init();
 		    ///  for (NodeIt n(gr); n != INVALID; ++n) {
 		    ///    if (!b.reached(n)) {
 		    ///      b.addSource(n);
 		    ///      b.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt n(*G); n != INVALID; ++n) {
 		        if (!reached(n)) {
 		          addSource(n);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the BFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref start() should be called
 		    ///before using them.
 		    ///@{
 		    ///The shortest path to the given node.
 		    ///Returns 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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    int 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 the 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 \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "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 the 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 \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->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(Node) "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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///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.
 		    ///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<int> 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.
 		    ///The type of the shortest paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by BfsWizard
 		  /// Default traits class used by BfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+		  {
 		    typedef BfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Bfs.
 		  ///
 		  /// This class should only be used through the \ref bfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    BfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    BfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    BfsWizard(const TR &b) : TR(b) {}
 		    ~BfsWizard() {}
 		    ///Runs BFS algorithm from the given source node.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs BFS algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		    }
 		    ///Runs BFS algorithm to visit all nodes in the digraph.
 		    ///This method runs BFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    BfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BfsWizard<SetDistMapBase<T> >(*this);

lemon/circulation.h

Show inline comments

@@ -53,513 +53,513 @@
 		    /// \brief The type of the upper bound (capacity) map.
 		    ///
 		    /// The type of the map that stores the upper bounds (capacities)
 		    /// on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef UM UpperMap;
 		    /// \brief The type of supply map.
 		    ///
 		    /// The type of the map that stores the signed supply values of the
 		    /// nodes.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef SM SupplyMap;
 		    /// \brief The type of the flow and supply values.
 		    typedef typename SupplyMap::Value Value;
 		    /// \brief The type of the map that stores the flow values.
 		    ///
 		    /// The type of the map that stores the flow values.
 		    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		    /// concept.
 		#ifdef DOXYGEN
 		    typedef GR::ArcMap<Value> FlowMap;
 		#else
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		#endif
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator, LinkedElevator
 		#ifdef DOXYGEN
 		    typedef lemon::Elevator<GR, GR::Node> Elevator;
 		#else
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		#endif
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the \e network
 		     \e circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds are
 		     given for the difference between the outgoing and incoming flow
 		     at the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
 		     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
 		     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
 		     holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
 		     denotes the signed supply values of the nodes.
 		     If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
 		     supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
 		     \f$-sup(u)\f$ demand.
 		     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
 		     solution of the following problem.
 		     \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
 		     \geq sup(u) \quad \forall u\in V, \f]
 		     \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f]
 		     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.
 		     If you need the opposite inequalities in the supply/demand constraints
 		     (i.e. the total demand is less than the total supply and all the demands
 		     have to be satisfied while there could be supplies that are not used),
 		     then you could easily transform the problem to the above form by reversing
 		     the direction of the arcs and taking the negative of the supply values
 		     (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
 		     This algorithm either calculates a feasible circulation, or provides
 		     a \ref barrier() "barrier", which prooves that a feasible soultion
 		     cannot exist.
 		     Note that this algorithm also provides a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow problem".
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound (capacity) map.
 		     The default map type is \c LM.
 		     \tparam SM The type of the supply map. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename SM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename SM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, SM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow and supply values.
 		    typedef typename Traits::Value Value;
 		    ///The type of the lower bound map.
 		    typedef typename Traits::LowerMap LowerMap;
 		    ///The type of the upper bound (capacity) map.
 		    typedef typename Traits::UpperMap UpperMap;
 		    ///The type of the supply map.
 		    typedef typename Traits::SupplyMap SupplyMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LowerMap *_lo;
 		    const UpperMap *_up;
 		    const SupplyMap *_supply;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LowerMap, UpperMap, SupplyMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \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 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),
 		        _excess(NULL) {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    bool checkBoundMaps() {
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (_tol.less((*_up)[e], (*_lo)[e])) return false;
+		      }
 		      return true;
+		    }
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    /// Sets the lower bound map.
 		    /// Sets the lower bound map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& lowerMap(const LowerMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound (capacity) map.
 		    /// Sets the upper bound (capacity) map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& upperMap(const UpperMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
 		    /// Sets the supply map.
 		    /// Sets the supply map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& supplyMap(const SupplyMap& map) {
 		      _supply = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by the algorithm.
 		    ///
 		    /// Sets the tolerance object used by the algorithm.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& tolerance(const Tolerance& tolerance) {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance object used by
 		    /// the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tol;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need better control on the initial solution or the execution,
 		    /// you have to call one of the \ref init() functions first, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      LEMON_DEBUG(checkBoundMaps(),
 		        "Upper bounds must be greater or equal to the lower bounds");
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        _flow->set(e, (*_lo)[e]);
 		        (*_excess)[_g.target(e)] += (*_flow)[e];
 		        (*_excess)[_g.source(e)] -= (*_flow)[e];
+		      }
 		      // global relabeling tested, but in general case it provides
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      LEMON_DEBUG(checkBoundMaps(),
 		        "Upper bounds must be greater or equal to the lower bounds");
 		      createStructures();
 		      for(NodeIt n(_g);n!=INVALID;++n) {
 		        (*_excess)[n] = (*_supply)[n];
+		      }
 		      for (ArcIt e(_g);e!=INVALID;++e) {
 		        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
 		          _flow->set(e, (*_up)[e]);
 		          (*_excess)[_g.target(e)] += (*_up)[e];
 		          (*_excess)[_g.source(e)] -= (*_up)[e];
 		        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
 		          _flow->set(e, (*_lo)[e]);
 		          (*_excess)[_g.target(e)] += (*_lo)[e];
 		          (*_excess)[_g.source(e)] -= (*_lo)[e];
 		        } else {
 		          Value fc = -(*_excess)[_g.target(e)];
 		          _flow->set(e, fc);
 		          (*_excess)[_g.target(e)] = 0;
 		          (*_excess)[_g.source(e)] -= fc;
+		        }
+		      }
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()

lemon/concepts/digraph.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.
+		 *
 		 */
 		#ifndef LEMON_CONCEPTS_DIGRAPH_H
 		#define LEMON_CONCEPTS_DIGRAPH_H
 		///\ingroup graph_concepts
 		///\file
 		///\brief The concept of directed graphs.
 		#include <lemon/core.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/graph_components.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \ingroup graph_concepts
 		    ///
 		    /// \brief Class describing the concept of directed graphs.
 		    ///
 		    /// This class describes the common interface of all directed
 		    /// graphs (digraphs).
 		    ///
 		    /// Like all concept classes, it only provides an interface
 		    /// without any sensible implementation. So any general algorithm for
 		    /// directed graphs should compile with this class, but it will not
 		    /// run properly, of course.
 		    /// An actual digraph implementation like \ref ListDigraph or
 		    /// \ref SmartDigraph may have additional functionality.
 		    ///
 		    /// \sa Graph
 		    class Digraph {
 		    private:
 		      /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
 		      Digraph(const Digraph &) {}
 		      /// \brief Assignment of a digraph to another one is \e not allowed.
 		      /// Use DigraphCopy instead.
 		      void operator=(const Digraph &) {}
 		    public:
 		      /// Default constructor.
 		      Digraph() { }
 		      /// The node type of the digraph
 		      /// This class identifies a node of the digraph. It also serves
 		      /// as a base class of the node iterators,
 		      /// thus they convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// %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&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
 		      /// The arc type of the digraph
 		      /// This class identifies an arc of the digraph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        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&) { }
 		        /// Next arc
 		        /// Assign the iterator to the next arc.
 		        ///
 		        ArcIt& operator++() { return *this; }
 		      };
 		      /// \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 arc.
 		      ///
 		      /// Returns the ID of the given arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief The node with the given ID.
 		      ///
 		      /// Returns the node with the given ID.
 		      /// \pre The argument should be a valid node ID in the digraph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief The arc with the given ID.
 		      ///
 		      /// Returns the arc with the given ID.
 		      /// \pre The argument should be a valid arc ID in the digraph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief An upper bound on the node IDs.
 		      ///
 		      /// Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief An upper bound on the arc IDs.
 		      ///
 		      /// Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstIn(Arc&, const Node&) const {}
 		      void nextIn(Arc&) const {}
 		      void firstOut(Arc&, const Node&) const {}
 		      void nextOut(Arc&) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief The opposite node on the arc.
 		      ///
 		      /// Returns the opposite node on the given arc.
 		      Node oppositeNode(Node, Arc) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the given outgoing arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node baseNode(OutArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the given outgoing arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node runningNode(OutArcIt) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the given incomming arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node baseNode(InArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the given incomming arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node runningNode(InArcIt) const { return INVALID; }
 		      /// \brief Standard graph map type for the nodes.
 		      ///
 		      /// Standard graph map type for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
 		      public:
 		        /// Constructor
 		        explicit NodeMap(const Digraph&) { }
 		        /// Constructor with given initial value
 		        NodeMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Standard graph map type for the arcs.
 		      ///
 		      /// Standard graph map type for the arcs.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
 		      public:
 		        /// Constructor
 		        explicit ArcMap(const Digraph&) { }
 		        /// Constructor with given initial value
 		        ArcMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Digraph>();
 		          checkConcept<IterableDigraphComponent<>, _Digraph>();
 		          checkConcept<IDableDigraphComponent<>, _Digraph>();
 		          checkConcept<MappableDigraphComponent<>, _Digraph>();
+		        }
 		      };
 		    };
 		  } //namespace concepts
 		} //namespace lemon
 		#endif

lemon/concepts/graph.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 undirected graphs.
 		#ifndef LEMON_CONCEPTS_GRAPH_H
 		#define LEMON_CONCEPTS_GRAPH_H
 		#include <lemon/concepts/graph_components.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/core.h>
 		namespace lemon {
 		  namespace concepts {
 		    /// \ingroup graph_concepts
 		    ///
 		    /// \brief Class describing the concept of undirected graphs.
 		    ///
 		    /// This class describes the common interface of all undirected
 		    /// graphs.
 		    ///
 		    /// Like all concept classes, it only provides an interface
 		    /// without any sensible implementation. So any general algorithm for
 		    /// undirected graphs should compile with this class, but it will not
 		    /// run properly, of course.
 		    /// An actual graph implementation like \ref ListGraph or
 		    /// \ref SmartGraph may have additional functionality.
 		    ///
 		    /// The undirected graphs also fulfill the concept of \ref Digraph
 		    /// "directed graphs", since each edge can also be regarded as two
 		    /// oppositely directed arcs.
 		    /// Undirected graphs provide an Edge type for the undirected edges and
 		    /// an Arc type for the directed arcs. The Arc type is convertible to
 		    /// Edge or inherited from it, i.e. the corresponding edge can be
 		    /// obtained from an arc.
 		    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
 		    /// and ArcMap classes can be used for the arcs (just like in digraphs).
 		    /// Both InArcIt and OutArcIt iterates on the same edges but with
 		    /// opposite direction. IncEdgeIt also iterates on the same edges
 		    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
 		    /// only to Edge.
 		    ///
 		    /// In LEMON, each undirected edge has an inherent orientation.
 		    /// Thus it can defined if an arc is forward or backward oriented in
 		    /// an undirected graph with respect to this default oriantation of
 		    /// the represented edge.
 		    /// With the direction() and direct() functions the direction
 		    /// of an arc can be obtained and set, respectively.
 		    ///
 		    /// Only nodes and edges can be added to or removed from an undirected
 		    /// graph and the corresponding arcs are added or removed automatically.
 		    ///
 		    /// \sa Digraph
 		    class Graph {
 		    private:
 		      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
 		      Graph(const Graph&) {}
 		      /// \brief Assignment of a graph to another one is \e not allowed.
 		      /// Use DigraphCopy instead.
 		      void operator=(const Graph&) {}
 		    public:
 		      /// Default constructor.
 		      Graph() {}
 		      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
 		      ///
 		      /// Undirected graphs should be tagged with \c UndirectedTag.
 		      ///
 		      /// This tag helps the \c enable_if technics to make compile time
 		      /// specializations for undirected graphs.
 		      typedef True UndirectedTag;
 		      /// The node type of the graph
 		      /// This class identifies a node of the graph. It also serves
 		      /// as a base class of the node iterators,
 		      /// thus they convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// %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&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
 		      /// The edge type of the graph
 		      /// This class identifies an edge of the graph. It also serves
 		      /// as a base class of the edge iterators,
 		      /// thus they will convert to this type.
 		      class Edge {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Edge() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        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.
 		        /// Sets the iterator to the given edge of the given graph.
 		        ///
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident edge
 		        /// Assign the iterator to the next incident edge
 		        /// of the corresponding node.
 		        IncEdgeIt& operator++() { return *this; }
 		      };
 		      /// The arc type of the graph
 		      /// This class identifies a directed arc of the graph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// Default constructor.
 		        /// \warning It sets the object to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        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; }
 		        /// 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.
 		        /// Sets the iterator to the given arc of the given graph.
 		        ///
 		        InArcIt(const Graph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next
 		        /// incoming arc of the corresponding node.
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// \brief Standard graph map type for the nodes.
 		      ///
 		      /// Standard graph map type for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
+		      {
 		      public:
 		        /// Constructor
 		        explicit NodeMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        NodeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Standard graph map type for the arcs.
 		      ///
 		      /// Standard graph map type for the arcs.
 		      /// It conforms to the ReferenceMap concept.
 		      template<class T>
 		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
+		      {
 		      public:
 		        /// Constructor
 		        explicit ArcMap(const Graph&) { }
 		        /// Constructor with given initial value
 		        ArcMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \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; }
 		      /// \brief The node with the given ID.
 		      ///
 		      /// Returns the node with the given ID.
 		      /// \pre The argument should be a valid node ID in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief The edge with the given ID.
 		      ///
 		      /// Returns the edge with the given ID.
 		      /// \pre The argument should be a valid edge ID in the graph.
 		      Edge edgeFromId(int) const { return INVALID; }
 		      /// \brief The arc with the given ID.
 		      ///
 		      /// Returns the arc with the given ID.
 		      /// \pre The argument should be a valid arc ID in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief An upper bound on the node IDs.
 		      ///
 		      /// Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief An upper bound on the edge IDs.
 		      ///
 		      /// Returns an upper bound on the edge IDs.
 		      int maxEdgeId() const { return -1; }
 		      /// \brief An upper bound on the arc IDs.
 		      ///
 		      /// Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      /// \brief The direction of the arc.
 		      ///
 		      /// Returns \c true if the direction of the given arc is the same as
 		      /// the inherent orientation of the represented edge.
 		      bool direction(Arc) const { return true; }
 		      /// \brief Direct the edge.
 		      ///
 		      /// Direct the given edge. The returned arc
 		      /// represents the given edge and its direction comes
 		      /// from the bool parameter. If it is \c true, then the direction
 		      /// of the arc is the same as the inherent orientation of the edge.
 		      Arc direct(Edge, bool) const {
 		        return INVALID;
+		      }
 		      /// \brief Direct the edge.
 		      ///
 		      /// Direct the given edge. The returned arc represents the given
 		      /// edge and its source node is the given node.
 		      Arc direct(Edge, Node) const {
 		        return INVALID;
+		      }
 		      /// \brief The oppositely directed arc.
 		      ///
 		      /// Returns the oppositely directed arc representing the same edge.
 		      Arc oppositeArc(Arc) const { return INVALID; }
 		      /// \brief The opposite node on the edge.
 		      ///
 		      /// Returns the opposite node on the given edge.
 		      Node oppositeNode(Node, Edge) const { return INVALID; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Edge&) const {}
 		      void next(Edge&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstOut(Arc&, Node) const {}
 		      void nextOut(Arc&) const {}
 		      void firstIn(Arc&, Node) const {}
 		      void nextIn(Arc&) const {}
 		      void firstInc(Edge &, bool &, const Node &) const {}
 		      void nextInc(Edge &, bool &) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Edge fromId(int, Edge) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Edge) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the given incident edge iterator.
 		      Node baseNode(IncEdgeIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the given incident edge iterator.
 		      Node runningNode(IncEdgeIt) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the given outgoing arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node baseNode(OutArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the given outgoing arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node runningNode(OutArcIt) const { return INVALID; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Returns the base node of the given incomming arc iterator
 		      /// (i.e. the target node of the corresponding arc).
 		      Node baseNode(InArcIt) const { return INVALID; }
 		      /// \brief The running node of the iterator.
 		      ///
 		      /// Returns the running node of the given incomming arc iterator
 		      /// (i.e. the source node of the corresponding arc).
 		      Node runningNode(InArcIt) const { return INVALID; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseGraphComponent, _Graph>();
 		          checkConcept<IterableGraphComponent<>, _Graph>();
 		          checkConcept<IDableGraphComponent<>, _Graph>();
 		          checkConcept<MappableGraphComponent<>, _Graph>();
+		        }
 		      };
 		    };
+		  }
+		}
 		#endif

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
 		      /// as uninitialized.
 		      GraphItem() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphItem(const GraphItem &) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the item to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItem(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the item.
 		      GraphItem& operator=(const GraphItem&) { return *this; }
 		      /// \brief Assignment operator for INVALID.
 		      ///
 		      /// This operator makes the item invalid.
 		      GraphItem& operator=(Invalid) { return *this; }
 		      /// \brief Equality operator.
 		      ///
 		      /// Equality operator.
 		      bool operator==(const GraphItem&) const { return false; }
 		      /// \brief Inequality operator.
 		      ///
 		      /// Inequality operator.
 		      bool operator!=(const GraphItem&) const { return false; }
 		      /// \brief Ordering operator.
 		      ///
 		      /// This operator defines an ordering of the items.
 		      /// It makes possible to use graph item types as key types in
 		      /// associative containers (e.g. \c std::map).
 		      ///
 		      /// \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<(const GraphItem&) const { return false; }
 		      template<typename _GraphItem>
 		      struct Constraints {
 		        void constraints() {
 		          _GraphItem i1;
 		          i1=INVALID;
 		          _GraphItem i2 = i1;
 		          _GraphItem i3 = INVALID;
 		          i1 = i2 = i3;
 		          bool b;
 		          b = (ia == ib) && (ia != ib);
 		          b = (ia == INVALID) && (ib != INVALID);
 		          b = (ia < ib);
+		        }
 		        const _GraphItem &ia;
 		        const _GraphItem &ib;
 		      };
 		    };
 		    /// \brief Base skeleton class for directed graphs.
 		    ///
 		    /// This class describes the base interface of directed graph types.
 		    /// All digraph %concepts have to conform to this class.
 		    /// It just provides types for nodes and arcs and functions
 		    /// to get the source and the target nodes of arcs.
 		    class BaseDigraphComponent {
 		    public:
 		      typedef BaseDigraphComponent Digraph;
 		      /// \brief Node class of the digraph.
 		      ///
 		      /// This class represents the nodes of the digraph.
 		      typedef GraphItem<'n'> Node;
 		      /// \brief Arc class of the digraph.
 		      ///
 		      /// This class represents the arcs of the digraph.
 		      typedef GraphItem<'a'> Arc;
 		      /// \brief Return the source node of an arc.
 		      ///
 		      /// This function returns the source node of an arc.
 		      Node source(const Arc&) const { return INVALID; }
 		      /// \brief Return the target node of an arc.
 		      ///
 		      /// This function returns the target node of an arc.
 		      Node target(const Arc&) const { return INVALID; }
 		      /// \brief Return the opposite node on the given arc.
 		      ///
 		      /// This function returns the opposite node on the given arc.
 		      Node oppositeNode(const Node&, const Arc&) const {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        typedef typename _Digraph::Node Node;
 		        typedef typename _Digraph::Arc Arc;
 		        void constraints() {
 		          checkConcept<GraphItem<'n'>, Node>();
 		          checkConcept<GraphItem<'a'>, Arc>();
+		          {
 		            Node n;
 		            Arc e(INVALID);
 		            n = digraph.source(e);
 		            n = digraph.target(e);
 		            n = digraph.oppositeNode(n, e);
+		          }
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Base skeleton class for undirected graphs.
 		    ///
 		    /// This class describes the base interface of undirected graph types.
 		    /// All graph %concepts have to conform to this class.
 		    /// It extends the interface of \ref BaseDigraphComponent with an
 		    /// \c Edge type and functions to get the end nodes of edges,
 		    /// to convert from arcs to edges and to get both direction of edges.
 		    class BaseGraphComponent : public BaseDigraphComponent {
 		    public:
 		      typedef BaseGraphComponent Graph;
 		      typedef BaseDigraphComponent::Node Node;
 		      typedef BaseDigraphComponent::Arc Arc;
 		      /// \brief Undirected edge class of the graph.
 		      ///
 		      /// This class represents the undirected edges of the graph.
 		      /// Undirected graphs can be used as directed graphs, each edge is
 		      /// represented by two opposite directed arcs.
 		      class Edge : public GraphItem<'e'> {
 		        typedef GraphItem<'e'> Parent;
 		      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
 		        /// as uninitialized.
 		        Edge() {}
 		        /// \brief Copy constructor.
 		        ///
 		        /// Copy constructor.
 		        Edge(const Edge &) : Parent() {}
 		        /// \brief Constructor for conversion from \c INVALID.
 		        ///
 		        /// Constructor for conversion from \c INVALID.
 		        /// It initializes the item to be invalid.
 		        /// \sa Invalid for more details.
 		        Edge(Invalid) {}
 		        /// \brief Constructor for conversion from an arc.
 		        ///
 		        /// Constructor for conversion from an arc.
 		        /// Besides the core graph item functionality each arc should
 		        /// be convertible to the represented edge.
 		        Edge(const Arc&) {}
 		     };
 		      /// \brief Return one end node of an edge.
 		      ///
 		      /// This function returns one end node of an edge.
 		      Node u(const Edge&) const { return INVALID; }
 		      /// \brief Return the other end node of an edge.
 		      ///
 		      /// This function returns the other end node of an edge.
 		      Node v(const Edge&) const { return INVALID; }
 		      /// \brief Return a directed arc related to an edge.
 		      ///
 		      /// This function returns a directed arc from its direction and the
 		      /// represented edge.
 		      Arc direct(const Edge&, bool) const { return INVALID; }
 		      /// \brief Return a directed arc related to an edge.
 		      ///
 		      /// This function returns a directed arc from its source node and the
 		      /// represented edge.
 		      Arc direct(const Edge&, const Node&) const { return INVALID; }
 		      /// \brief Return the direction of the arc.
 		      ///
 		      /// Returns the direction of the arc. Each arc represents an
 		      /// edge with a direction. It gives back the
 		      /// direction.
 		      bool direction(const Arc&) const { return true; }
 		      /// \brief Return the opposite arc.
 		      ///
 		      /// This function returns the opposite arc, i.e. the arc representing
 		      /// the same edge and has opposite direction.
 		      Arc oppositeArc(const Arc&) const { return INVALID; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        typedef typename _Graph::Node Node;
 		        typedef typename _Graph::Arc Arc;
 		        typedef typename _Graph::Edge Edge;
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Graph>();
 		          checkConcept<GraphItem<'e'>, Edge>();
+		          {
 		            Node n;

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);
 		          e = (i < ii);
 		          ignore_unused_variable_warning(l);
 		          ignore_unused_variable_warning(pp);
 		          ignore_unused_variable_warning(e);
 		          ignore_unused_variable_warning(id);
 		          ignore_unused_variable_warning(ii);
 		          ignore_unused_variable_warning(ed);
+		        }
 		      };
 		    };
 		    namespace _path_bits {
 		      template <typename _Digraph, typename _Path, typename RevPathTag = void>
 		      struct PathDumperConstraints {
 		        void constraints() {
 		          int l = p.length();
 		          int e = p.empty();
 		          typename _Path::ArcIt 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;
 		      };
 		      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

 		/* -*- 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.
+		 *
 		 */
 		#ifndef LEMON_COUNTER_H
 		#define LEMON_COUNTER_H
 		#include <string>
 		#include <iostream>
 		///\ingroup timecount
 		///\file
 		///\brief Tools for counting steps and events
 		namespace lemon
+		{
 		  template<class P> class _NoSubCounter;
 		  template<class P>
 		  class _SubCounter
+		  {
 		    P &_parent;
 		    std::string _title;
 		    std::ostream &_os;
 		    int count;
 		  public:
 		    typedef _SubCounter<_SubCounter<P> > SubCounter;
 		    typedef _NoSubCounter<_SubCounter<P> > NoSubCounter;
 		    _SubCounter(P &parent)
 		      : _parent(parent), _title(), _os(std::cerr), count(0) {}
 		    _SubCounter(P &parent,std::string title,std::ostream &os=std::cerr)
 		      : _parent(parent), _title(title), _os(os), count(0) {}
 		    _SubCounter(P &parent,const char *title,std::ostream &os=std::cerr)
 		      : _parent(parent), _title(title), _os(os), count(0) {}
 		    ~_SubCounter() {
 		      _os << _title << count <<std::endl;
 		      _parent+=count;
+		    }
 		    _SubCounter &operator++() { count++; return *this;}
 		    int operator++(int) { return count++; }
 		    _SubCounter &operator--() { count--; return *this;}
 		    int operator--(int) { return count--; }
 		    _SubCounter &operator+=(int c) { count+=c; return *this;}
 		    _SubCounter &operator-=(int c) { count-=c; return *this;}
 		    operator int() {return count;}
 		  };
 		  template<class P>
 		  class _NoSubCounter
+		  {
 		    P &_parent;
 		  public:
 		    typedef _NoSubCounter<_NoSubCounter<P> > SubCounter;
 		    typedef _NoSubCounter<_NoSubCounter<P> > NoSubCounter;
 		    _NoSubCounter(P &parent) :_parent(parent) {}
 		    _NoSubCounter(P &parent,std::string,std::ostream &)
 		      :_parent(parent) {}
 		    _NoSubCounter(P &parent,std::string)
 		      :_parent(parent) {}
 		    _NoSubCounter(P &parent,const char *,std::ostream &)
 		      :_parent(parent) {}
 		    _NoSubCounter(P &parent,const char *)
 		      :_parent(parent) {}
 		    ~_NoSubCounter() {}
 		    _NoSubCounter &operator++() { ++_parent; return *this;}
 		    int operator++(int) { _parent++; return 0;}
 		    _NoSubCounter &operator--() { --_parent; return *this;}
 		    int operator--(int) { _parent--; return 0;}
 		    _NoSubCounter &operator+=(int c) { _parent+=c; return *this;}
 		    _NoSubCounter &operator-=(int c) { _parent-=c; return *this;}
 		    operator int() {return 0;}
 		  };
 		  /// \addtogroup timecount
 		  /// @{
 		  /// A counter class
 		  /// This class makes it easier to count certain events (e.g. for debug
 		  /// reasons).
 		  /// You can increment or decrement the counter using \c operator++,
 		  /// \c operator--, \c operator+= and \c operator-=. You can also
 		  /// define subcounters for the different phases of the algorithm or
 		  /// for different types of operations.
 		  /// A report containing the given title and the value of the counter
 		  /// is automatically printed on destruction.
 		  ///
 		  /// The following example shows the usage of counters and subcounters.
 		  /// \code
 		  /// // Bubble sort
 		  /// std::vector<T> v;
 		  /// ...
 		  /// Counter op("Operations: ");
 		  /// Counter::SubCounter as(op, "Assignments: ");
 		  /// Counter::SubCounter co(op, "Comparisons: ");
 		  /// for (int i = v.size()-1; i > 0; --i) {
 		  ///   for (int j = 0; j < i; ++j) {
 		  ///     if (v[j] > v[j+1]) {
 		  ///       T tmp = v[j];
 		  ///       v[j] = v[j+1];
 		  ///       v[j+1] = tmp;
 		  ///       as += 3;          // three assignments
 		  ///     }
 		  ///     ++co;               // one comparison
 		  ///   }
 		  /// }
 		  /// \endcode
 		  ///
 		  /// This code prints out something like that:
 		  /// \code
 		  /// Comparisons: 45
 		  /// Assignments: 57
 		  /// Operations: 102
 		  /// \endcode
 		  ///
 		  /// \sa NoCounter
 		  class Counter
+		  {
 		    std::string _title;
 		    std::ostream &_os;
 		    int count;
 		  public:
 		    /// SubCounter class
 		    /// This class can be used to setup subcounters for a \ref Counter
 		    /// to have finer reports. A subcounter provides exactly the same
 		    /// operations as the main \ref Counter, but it also increments and
 		    /// decrements the value of its parent.
 		    /// Subcounters can also have subcounters.
 		    ///
 		    /// The parent counter must be given as the first parameter of the
 		    /// constructor. Apart from that a title and an \c ostream object
 		    /// can also be given just like for the main \ref Counter.
 		    ///
 		    /// A report containing the given title and the value of the
 		    /// subcounter is automatically printed on destruction. If you
 		    /// would like to turn off this report, use \ref NoSubCounter
 		    /// instead.
 		    ///
 		    /// \sa NoSubCounter
 		    typedef _SubCounter<Counter> SubCounter;
 		    /// SubCounter class without printing report on destruction
 		    /// This class can be used to setup subcounters for a \ref Counter.
 		    /// It is the same as \ref SubCounter but it does not print report
 		    /// on destruction. (It modifies the value of its parent, so 'No'
 		    /// only means 'do not print'.)
 		    ///
 		    /// Replacing \ref SubCounter "SubCounter"s with \ref NoSubCounter
 		    /// "NoSubCounter"s makes it possible to turn off reporting
 		    /// subcounter values without actually removing the definitions
 		    /// and the increment or decrement operators.
 		    ///
 		    /// \sa SubCounter
 		    typedef _NoSubCounter<Counter> NoSubCounter;
 		    /// Constructor.
 		    Counter() : _title(), _os(std::cerr), count(0) {}
 		    /// Constructor.
 		    Counter(std::string title,std::ostream &os=std::cerr)
 		      : _title(title), _os(os), count(0) {}
 		    /// 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;}
 		  };
 		  ///@}
+		}
 		#endif

lemon/dfs.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.
+		 *
 		 */
 		#ifndef LEMON_DFS_H
 		#define LEMON_DFS_H
 		///\ingroup search
 		///\file
 		///\brief DFS algorithm.
 		#include <lemon/list_graph.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  ///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.
 		    ///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<int> 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);
+		    }
 		  };
 		  ///%DFS algorithm class.
 		  ///\ingroup search
 		  ///This class provides an efficient implementation of the %DFS algorithm.
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		#ifdef DOXYGEN
 		  template <typename GR,
 		            typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
 		#endif
 		  class Dfs {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///DFS paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are reached.
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the map of predecessor arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of reached status of the nodes.
 		    ReachedMap *_reached;
 		    //Indicates if _reached is locally allocated (true) or not.
 		    bool local_reached;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    std::vector<typename Digraph::OutArcIt> _stack;
 		    int _stack_head;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_reached) {
 		        local_reached = true;
 		        _reached = Traits::createReachedMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
+		    }
 		  protected:
 		    Dfs() {}
 		  public:
 		    typedef Dfs Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    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 Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ReachedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ReachedMap type.
 		    ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap :
 		      public Dfs< Digraph, SetStandardProcessedMapTraits > {
 		      typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
 		    };
 		    ///@}
 		  public:
 		    ///Constructor.
 		    ///Constructor.
 		    ///\param g The digraph the algorithm runs on.
 		    Dfs(const Digraph &g) :
 		      G(&g),
 		      _pred(NULL), local_pred(false),
@@ -525,513 +525,513 @@
 		    ///This method runs the %DFS algorithm from the root node
 		    ///in order to compute the DFS path to each node.
 		    ///
 		    /// The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  while ( !d.emptyQueue() ) {
 		    ///    d.processNextArc();
 		    ///  }
 		    ///\endcode
 		    void start()
+		    {
 		      while ( !emptyQueue() ) processNextArc();
+		    }
 		    ///Executes the algorithm until the given target node is reached.
 		    ///Executes the algorithm until the given target node is reached.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
 		    ///in order to compute the DFS path to \c t.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS path to \c t,
 		    ///- the distance of \c t from the root in the %DFS tree.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    void start(Node t)
+		    {
 		      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
 		        processNextArc();
+		    }
 		    ///Executes the algorithm until a condition is met.
 		    ///Executes the algorithm until a condition is met.
 		    ///
 		    ///This method runs the %DFS algorithm from the root node
 		    ///until an arc \c a with <tt>am[a]</tt> true is found.
 		    ///
 		    ///\param am A \c bool (or convertible) arc map. The algorithm
 		    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
 		    ///
 		    ///\return The reached arc \c a with <tt>am[a]</tt> true or
 		    ///\c INVALID if no such arc was found.
 		    ///
 		    ///\pre init() must be called and a root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
 		    ///not a node map.
 		    template<class ArcBoolMap>
 		    Arc start(const ArcBoolMap &am)
+		    {
 		      while ( !emptyQueue() && !am[_stack[_stack_head]] )
 		        processNextArc();
 		      return emptyQueue() ? INVALID : _stack[_stack_head];
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the %DFS tree,
 		    ///- the distance of each node from the root in the %DFS tree.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the %DFS path between \c s and \c t.
 		    ///This method runs the %DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed)
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
 		    ///just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return reached(t);
+		    }
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %DFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    ///
 		    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///    if (!d.reached(n)) {
 		    ///      d.addSource(n);
 		    ///      d.start();
 		    ///    }
 		    ///  }
 		    ///\endcode
 		    void run() {
 		      init();
 		      for (NodeIt it(*G); it != INVALID; ++it) {
 		        if (!reached(it)) {
 		          addSource(it);
 		          start();
+		        }
+		      }
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the DFS algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref start() should be called
 		    ///before using them.
 		    ///@{
 		    ///The DFS path to the given node.
 		    ///Returns the DFS path to the given node from the root(s).
 		    ///
 		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    int dist(Node v) const { return (*_dist)[v]; }
 		    ///Returns the 'previous arc' of the %DFS tree for the given node.
 		    ///This function returns the 'previous arc' of the %DFS tree for the
 		    ///node \c v, i.e. it returns the last arc of a %DFS 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 %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predNode() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Arc predArc(Node v) const { return (*_pred)[v];}
 		    ///Returns the 'previous node' of the %DFS tree for the given node.
 		    ///This function returns the 'previous node' of the %DFS
 		    ///tree for the node \c v, i.e. it returns the last but one node
 		    ///of a %DFS 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 %DFS tree used here is equal to the %DFS tree used in
 		    ///\ref predArc() and \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->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(Node) "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 DFS tree (forest).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if the given node. node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_reached)[v]; }
 		    ///@}
 		  };
 		  ///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.
 		    ///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<int> 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 DFS paths.
 		    ///The type of the DFS paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DfsWizard
 		  /// Default traits class used by DfsWizard.
 		  /// \tparam GR The type of the digraph.
 		  template<class GR>
 		  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+		  {
 		    typedef DfsWizardDefaultTraits<GR> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the map of reached nodes.
 		    void *_reached;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the DFS path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    int *_di;
 		    public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, it initiates
 		    /// all of the attributes to \c 0.
 		    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
 		                      _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires one parameter,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizardBase(const GR &g) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _reached(0), _processed(0), _pred(0), _dist(0),  _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of DFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Dfs.
 		  ///
 		  /// This class should only be used through the \ref dfs() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ReachedMap ReachedMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		  public:
 		    /// Constructor.
 		    DfsWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    DfsWizard(const Digraph &g) :
 		      TR(g) {}
 		    ///Copy constructor
 		    DfsWizard(const TR &b) : TR(b) {}
 		    ~DfsWizard() {}
 		    ///Runs DFS algorithm from the given source node.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to each node.
 		    void run(Node s)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      if (s!=INVALID)
 		        alg.run(s);
 		      else
 		        alg.run();
+		    }
 		    ///Finds the DFS path between \c s and \c t.
 		    ///This method runs DFS algorithm from node \c s
 		    ///in order to compute the DFS path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
 		      if (Base::_pred)
 		        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_reached)
 		        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
 		      if (Base::_processed)
 		        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      alg.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
 		      if (Base::_di)
 		        *Base::_di = alg.dist(t);
 		      return alg.reached(t);
+		      }
 		    ///Runs DFS algorithm to visit all nodes in the digraph.
 		    ///This method runs DFS algorithm in order to visit all nodes
 		    ///in the digraph.
 		    void run()
+		    {
 		      run(INVALID);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    DfsWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetReachedMapBase : public Base {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
 		      SetReachedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the reached map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are reached.
 		    template<class T>
 		    DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
+		    {
 		      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetReachedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    DfsWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DfsWizard<SetDistMapBase<T> >(*this);

lemon/dijkstra.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.
+		 *
 		 */
 		#ifndef LEMON_DIJKSTRA_H
 		#define LEMON_DIJKSTRA_H
 		///\ingroup shortest_path
 		///\file
 		///\brief Dijkstra algorithm.
 		#include <limits>
 		#include <lemon/list_graph.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/bits/path_dump.h>
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/maps.h>
 		#include <lemon/path.h>
 		namespace lemon {
 		  /// \brief Default operation traits for the Dijkstra algorithm class.
 		  ///
 		  /// This operation traits class defines all computational operations and
 		  /// constants which are used in the Dijkstra algorithm.
 		  template <typename V>
 		  struct DijkstraDefaultOperationTraits {
 		    /// \e
 		    typedef V Value;
 		    /// \brief Gives back the zero value of the type.
 		    static Value zero() {
 		      return static_cast<Value>(0);
+		    }
 		    /// \brief Gives back the sum of the given two elements.
 		    static Value plus(const Value& left, const Value& right) {
 		      return left + right;
+		    }
 		    /// \brief Gives back true only if the first value is less than the second.
 		    static bool less(const Value& left, const Value& right) {
 		      return left < right;
+		    }
 		  };
 		  ///Default traits class of Dijkstra class.
 		  ///Default traits class of Dijkstra class.
 		  ///\tparam GR The type of the digraph.
 		  ///\tparam LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  struct DijkstraDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
 		    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    ///The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// Operation traits for %Dijkstra algorithm.
 		    /// This class defines the operations that are used in the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by the heap.
 		    /// The cross reference type used by the heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a \c HeapCrossRef.
 		    ///This function instantiates a \ref HeapCrossRef.
 		    /// \param g is the digraph, to which we would like to define the
 		    /// \ref HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
+		    {
 		      return new HeapCrossRef(g);
+		    }
 		    ///The heap type used by the %Dijkstra algorithm.
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///
 		    ///\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.
 		  /// \ingroup shortest_path
 		  ///This class provides an efficient implementation of the %Dijkstra algorithm.
 		  ///
 		  ///The %Dijkstra algorithm solves the single-source shortest path problem
 		  ///when all arc lengths are non-negative. If there are negative lengths,
 		  ///the BellmanFord algorithm should be used instead.
 		  ///
 		  ///The arc lengths are passed to the algorithm using a
 		  ///\ref concepts::ReadMap "ReadMap",
 		  ///so it is easy to change it to any kind of length.
 		  ///The type of the length is determined by the
 		  ///\ref concepts::ReadMap::Value "Value" of the length map.
 		  ///It is also possible to change the underlying priority heap.
 		  ///
 		  ///There is also a \ref dijkstra() "function-type interface" for the
 		  ///%Dijkstra algorithm, which is convenient in the simplier cases and
 		  ///it can be used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default type is \ref ListDigraph.
 		  ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
 		  ///the lengths of the arcs.
 		  ///It is read once for each arc, so the map may involve in
 		  ///relatively time consuming process to compute the arc lengths if
 		  ///it is necessary. The default map type is \ref
 		  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename LEN=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LEN> >
 		#endif
 		  class Dijkstra {
 		  public:
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename TR::Digraph Digraph;
 		    ///The type of the arc lengths.
 		    typedef typename TR::Value Value;
 		    ///The type of the map that stores the arc lengths.
 		    typedef typename TR::LengthMap LengthMap;
 		    ///\brief The type of the map that stores the predecessor arcs of the
 		    ///shortest paths.
 		    typedef typename TR::PredMap PredMap;
 		    ///The type of the map that stores the distances of the nodes.
 		    typedef typename TR::DistMap DistMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The cross reference type used for the current heap.
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
 		    ///of the algorithm.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    //Pointer to the underlying digraph.
 		    const Digraph *G;
 		    //Pointer to the length map.
 		    const LengthMap *_length;
 		    //Pointer to the map of predecessors arcs.
 		    PredMap *_pred;
 		    //Indicates if _pred is locally allocated (true) or not.
 		    bool local_pred;
 		    //Pointer to the map of distances.
 		    DistMap *_dist;
 		    //Indicates if _dist is locally allocated (true) or not.
 		    bool local_dist;
 		    //Pointer to the map of processed status of the nodes.
 		    ProcessedMap *_processed;
 		    //Indicates if _processed is locally allocated (true) or not.
 		    bool local_processed;
 		    //Pointer to the heap cross references.
 		    HeapCrossRef *_heap_cross_ref;
 		    //Indicates if _heap_cross_ref is locally allocated (true) or not.
 		    bool local_heap_cross_ref;
 		    //Pointer to the heap.
 		    Heap *_heap;
 		    //Indicates if _heap is locally allocated (true) or not.
 		    bool local_heap;
 		    //Creates the maps if necessary.
 		    void create_maps()
+		    {
 		      if(!_pred) {
 		        local_pred = true;
 		        _pred = Traits::createPredMap(*G);
+		      }
 		      if(!_dist) {
 		        local_dist = true;
 		        _dist = Traits::createDistMap(*G);
+		      }
 		      if(!_processed) {
 		        local_processed = true;
 		        _processed = Traits::createProcessedMap(*G);
+		      }
 		      if (!_heap_cross_ref) {
 		        local_heap_cross_ref = true;
 		        _heap_cross_ref = Traits::createHeapCrossRef(*G);
+		      }
 		      if (!_heap) {
 		        local_heap = true;
 		        _heap = Traits::createHeap(*_heap_cross_ref);
+		      }
+		    }
 		  public:
 		    typedef Dijkstra Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "PredMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c PredMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
 		    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 Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
 		    struct SetProcessedMapTraits : public Traits {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &)
+		      {
 		        LEMON_ASSERT(false, "ProcessedMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type.
 		    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
 		      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &g)
+		      {
 		        return new ProcessedMap(g);
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
 		    ///If you don't set it explicitly, it will be automatically allocated.
 		    struct SetStandardProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits >
 		      Create;
 		    };
 		    template <class H, class CR>
 		    struct SetHeapTraits : public Traits {
 		      typedef CR HeapCrossRef;
 		      typedef H Heap;
 		      static HeapCrossRef *createHeapCrossRef(const Digraph &) {
 		        LEMON_ASSERT(false, "HeapCrossRef is not initialized");
 		        return 0; // ignore warnings
+		      }
 		      static Heap *createHeap(HeapCrossRef &)
+		      {
 		        LEMON_ASSERT(false, "Heap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///heap and cross reference types
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting heap and cross
 		    ///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()
+		    {
 		      if(local_pred) delete _pred;
 		      if(local_dist) delete _dist;
 		      if(local_processed) delete _processed;
 		      if(local_heap_cross_ref) delete _heap_cross_ref;
 		      if(local_heap) delete _heap;
+		    }
 		    ///Sets the length map.
 		    ///Sets the length map.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &lengthMap(const LengthMap &m)
+		    {
 		      _length = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the predecessor arcs.
 		    ///Sets the map that stores the predecessor arcs.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &predMap(PredMap &m)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
+		      }
 		      _pred = &m;
 		      return *this;
+		    }
 		    ///Sets the map that indicates which nodes are processed.
 		    ///Sets the map that indicates which nodes are processed.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &processedMap(ProcessedMap &m)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
+		      }
 		      _processed = &m;
 		      return *this;
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by the
 		    ///algorithm.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), an instance will be allocated automatically.
 		    ///The destructor deallocates this automatically allocated map,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &distMap(DistMap &m)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
+		      }
 		      _dist = &m;
 		      return *this;
+		    }
 		    ///Sets the heap and the cross reference used by algorithm.
 		    ///Sets the heap and the cross reference used by algorithm.
 		    ///If you don't use this function before calling \ref run(Node) "run()"
 		    ///or \ref init(), heap and cross reference instances will be
 		    ///allocated automatically.
 		    ///The destructor deallocates these automatically allocated objects,
 		    ///of course.
 		    ///\return <tt> (*this) </tt>
 		    Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
+		    {
 		      if(local_heap_cross_ref) {
 		        delete _heap_cross_ref;
 		        local_heap_cross_ref=false;
+		      }
 		      _heap_cross_ref = &cr;
 		      if(local_heap) {
 		        delete _heap;
 		        local_heap=false;
+		      }
 		      _heap = &hp;
 		      return *this;
+		    }
 		  private:
 		    void finalizeNodeData(Node v,Value dst)
+		    {
 		      _processed->set(v,true);
 		      _dist->set(v, dst);
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///The simplest way to execute the %Dijkstra algorithm is to use
 		    ///one of the member functions called \ref run(Node) "run()".\n
 		    ///If you need better control on the execution, you have to call
 		    ///\ref init() first, then you can add several source nodes with
 		    ///\ref addSource(). Finally the actual path computation can be
 		    ///performed with one of the \ref start() functions.
 		    ///@{
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    void init()
+		    {
 		      create_maps();
 		      _heap->clear();
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
 		        _processed->set(u,false);
 		        _heap_cross_ref->set(u,Heap::PRE_HEAP);
+		      }
+		    }
 		    ///Adds a new source node.
 		    ///Adds a new source node to the priority heap.
 		    ///The optional second parameter is the initial distance of the node.
 		    ///
 		    ///The function checks if the node has already been added to the heap and
 		    ///it is pushed to the heap only if either it was not in the heap
 		    ///or the shortest path found till then is shorter than \c dst.
 		    void addSource(Node s,Value dst=OperationTraits::zero())
+		    {
 		      if(_heap->state(s) != Heap::IN_HEAP) {
 		        _heap->push(s,dst);
 		      } else if(OperationTraits::less((*_heap)[s], dst)) {
 		        _heap->set(s,dst);
 		        _pred->set(s,INVALID);
+		      }
+		    }
 		    ///Processes the next node in the priority heap
 		    ///Processes the next node in the priority heap.
 		    ///
 		    ///\return The processed node.
 		    ///
 		    ///\warning The priority heap must not be empty.
 		    Node processNextNode()
+		    {
 		      Node v=_heap->top();
 		      Value oldvalue=_heap->prio();
 		      _heap->pop();
 		      finalizeNodeData(v,oldvalue);
 		      for(OutArcIt e(*G,v); e!=INVALID; ++e) {
 		        Node w=G->target(e);
 		        switch(_heap->state(w)) {
 		        case Heap::PRE_HEAP:
 		          _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
 		          _pred->set(w,e);
 		          break;
 		        case Heap::IN_HEAP:
+		          {
 		            Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
 		            if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
 		              _heap->decrease(w, newvalue);
 		              _pred->set(w,e);
+		            }
+		          }
 		          break;
 		        case Heap::POST_HEAP:
 		          break;
+		        }
+		      }
 		      return v;
+		    }
 		    ///The next node to be processed.
 		    ///Returns the next node to be processed or \c INVALID if the
 		    ///priority heap is empty.
 		    Node nextNode() const
+		    {
 		      return !_heap->empty()?_heap->top():INVALID;
+		    }
 		    ///Returns \c false if there are nodes to be processed.
 		    ///Returns \c false if there are nodes to be processed
 		    ///in the priority heap.
 		    bool emptyQueue() const { return _heap->empty(); }
 		    ///Returns the number of the nodes to be processed.
 		    ///Returns the number of the nodes to be processed
 		    ///in the priority heap.
 		    int queueSize() const { return _heap->size(); }
 		    ///Executes the algorithm.
 		    ///Executes the algorithm.
 		    ///
 		    ///This method runs the %Dijkstra algorithm from the root node(s)
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree (forest),
 		    ///- the distance of each node from the root(s).
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    ///
 		    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  while ( !d.emptyQueue() ) {
 		    ///    d.processNextNode();
@@ -743,513 +743,513 @@
 		    ///
 		    ///\param nm A \c bool (or convertible) node map. The algorithm
 		    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
 		    ///
 		    ///\return The reached node \c v with <tt>nm[v]</tt> true or
 		    ///\c INVALID if no such node was found.
 		    ///
 		    ///\pre init() must be called and at least one root node should be
 		    ///added with addSource() before using this function.
 		    template<class NodeBoolMap>
 		    Node start(const NodeBoolMap &nm)
+		    {
 		      while ( !_heap->empty() && !nm[_heap->top()] ) processNextNode();
 		      if ( _heap->empty() ) return INVALID;
 		      finalizeNodeData(_heap->top(),_heap->prio());
 		      return _heap->top();
+		    }
 		    ///Runs the algorithm from the given source node.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to each node.
 		    ///
 		    ///The algorithm computes
 		    ///- the shortest path tree,
 		    ///- the distance of each node from the root.
 		    ///
 		    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start();
 		    ///\endcode
 		    void run(Node s) {
 		      init();
 		      addSource(s);
 		      start();
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    ///
 		    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
 		    ///shortcut of the following code.
 		    ///\code
 		    ///  d.init();
 		    ///  d.addSource(s);
 		    ///  d.start(t);
 		    ///\endcode
 		    bool run(Node s,Node t) {
 		      init();
 		      addSource(s);
 		      start(t);
 		      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
+		    }
 		    ///@}
 		    ///\name Query Functions
 		    ///The results of the %Dijkstra algorithm can be obtained using these
 		    ///functions.\n
 		    ///Either \ref run(Node) "run()" or \ref init() should be called
 		    ///before using them.
 		    ///@{
 		    ///The shortest path to the given node.
 		    ///Returns 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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Path path(Node t) const { return Path(*G, *_pred, t); }
 		    ///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(Node) "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 the 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 \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "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 the 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 \ref predMap().
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 		                                  G->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(Node) "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(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
 		    ///Checks if the given node is reached from the root(s).
 		    ///Returns \c true if \c v is reached from the root(s).
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
 		                                        Heap::PRE_HEAP; }
 		    ///Checks if a node is processed.
 		    ///Returns \c true if \c v is processed, i.e. the shortest
 		    ///path to \c v has already found.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
 		                                          Heap::POST_HEAP; }
 		    ///The current distance of the given node from the root(s).
 		    ///Returns the current distance of the given node from the root(s).
 		    ///It may be decreased in the following processes.
 		    ///
 		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function and
 		    ///node \c v must be reached but not necessarily processed.
 		    Value currentDist(Node v) const {
 		      return processed(v) ? (*_dist)[v] : (*_heap)[v];
+		    }
 		    ///@}
 		  };
 		  ///Default traits class of dijkstra() function.
 		  ///Default traits class of dijkstra() function.
 		  ///\tparam GR The type of the digraph.
 		  ///\tparam LEN The type of the length map.
 		  template<class GR, class LEN>
 		  struct DijkstraWizardDefaultTraits
+		  {
 		    ///The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    ///The type of the map that stores the arc lengths.
 		    ///The type of the map that stores the arc lengths.
 		    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LEN LengthMap;
 		    ///The type of the arc lengths.
 		    typedef typename LEN::Value Value;
 		    /// Operation traits for Dijkstra algorithm.
 		    /// This class defines the operations that are used in the algorithm.
 		    /// \see DijkstraDefaultOperationTraits
 		    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
 		    /// The cross reference type used by the heap.
 		    /// The cross reference type used by the heap.
 		    /// Usually it is \c Digraph::NodeMap<int>.
 		    typedef typename Digraph::template NodeMap<int> HeapCrossRef;
 		    ///Instantiates a \ref HeapCrossRef.
 		    ///This function instantiates a \ref HeapCrossRef.
 		    /// \param g is the digraph, to which we would like to define the
 		    /// HeapCrossRef.
 		    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
+		    {
 		      return new HeapCrossRef(g);
+		    }
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///The heap type used by the Dijkstra algorithm.
 		    ///
 		    ///\sa BinHeap
 		    ///\sa Dijkstra
 		    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
 		                    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.
 		    ///The type of the shortest paths.
 		    ///It must conform to the \ref concepts::Path "Path" concept.
 		    typedef lemon::Path<Digraph> Path;
 		  };
 		  /// Default traits class used by DijkstraWizard
 		  /// Default traits class used by DijkstraWizard.
 		  /// \tparam GR The type of the digraph.
 		  /// \tparam LEN The type of the length map.
 		  template<typename GR, typename LEN>
 		  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
+		  {
 		    typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
 		  protected:
 		    //The type of the nodes in the digraph.
 		    typedef typename Base::Digraph::Node Node;
 		    //Pointer to the digraph the algorithm runs on.
 		    void *_g;
 		    //Pointer to the length map.
 		    void *_length;
 		    //Pointer to the map of processed nodes.
 		    void *_processed;
 		    //Pointer to the map of predecessors arcs.
 		    void *_pred;
 		    //Pointer to the map of distances.
 		    void *_dist;
 		    //Pointer to the shortest path to the target node.
 		    void *_path;
 		    //Pointer to the distance of the target node.
 		    void *_di;
 		  public:
 		    /// Constructor.
 		    /// This constructor does not require parameters, therefore it initiates
 		    /// all of the attributes to \c 0.
 		    DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
 		                           _dist(0), _path(0), _di(0) {}
 		    /// Constructor.
 		    /// This constructor requires two parameters,
 		    /// others are initiated to \c 0.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    DijkstraWizardBase(const GR &g,const LEN &l) :
 		      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 		      _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
 		      _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
 		  };
 		  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
 		  /// It does not have own \ref run(Node) "run()" method, it uses the
 		  /// functions and features of the plain \ref Dijkstra.
 		  ///
 		  /// This class should only be used through the \ref dijkstra() function,
 		  /// which makes it easier to use the algorithm.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
 		    typedef TR Base;
 		    typedef typename TR::Digraph Digraph;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::OutArcIt OutArcIt;
 		    typedef typename TR::LengthMap LengthMap;
 		    typedef typename LengthMap::Value Value;
 		    typedef typename TR::PredMap PredMap;
 		    typedef typename TR::DistMap DistMap;
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    typedef typename TR::Path Path;
 		    typedef typename TR::Heap Heap;
 		  public:
 		    /// Constructor.
 		    DijkstraWizard() : TR() {}
 		    /// Constructor that requires parameters.
 		    /// Constructor that requires parameters.
 		    /// These parameters will be the default values for the traits class.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param l The length map.
 		    DijkstraWizard(const Digraph &g, const LengthMap &l) :
 		      TR(g,l) {}
 		    ///Copy constructor
 		    DijkstraWizard(const TR &b) : TR(b) {}
 		    ~DijkstraWizard() {}
 		    ///Runs Dijkstra algorithm from the given source node.
 		    ///This method runs %Dijkstra algorithm from the given source node
 		    ///in order to compute the shortest path to each node.
 		    void run(Node s)
+		    {
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 		             *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_processed)
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      dijk.run(s);
+		    }
 		    ///Finds the shortest path between \c s and \c t.
 		    ///This method runs the %Dijkstra algorithm from node \c s
 		    ///in order to compute the shortest path to node \c t
 		    ///(it stops searching when \c t is processed).
 		    ///
 		    ///\return \c true if \c t is reachable form \c s.
 		    bool run(Node s, Node t)
+		    {
 		      Dijkstra<Digraph,LengthMap,TR>
 		        dijk(*reinterpret_cast<const Digraph*>(Base::_g),
 		             *reinterpret_cast<const LengthMap*>(Base::_length));
 		      if (Base::_pred)
 		        dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
 		      if (Base::_dist)
 		        dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      if (Base::_processed)
 		        dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
 		      dijk.run(s,t);
 		      if (Base::_path)
 		        *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
 		      if (Base::_di)
 		        *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
 		      return dijk.reached(t);
+		    }
 		    template<class T>
 		    struct SetPredMapBase : public Base {
 		      typedef T PredMap;
 		      static PredMap *createPredMap(const Digraph &) { return 0; };
 		      SetPredMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the predecessor map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
+		    {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetPredMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetDistMapBase : public Base {
 		      typedef T DistMap;
 		      static DistMap *createDistMap(const Digraph &) { return 0; };
 		      SetDistMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///the distance map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that stores the distances of the nodes calculated
 		    ///by the algorithm.
 		    template<class T>
 		    DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
+		    {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetDistMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetProcessedMapBase : public Base {
 		      typedef T ProcessedMap;
 		      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 		      SetProcessedMapBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter" for setting
 		    ///the processed map.
 		    ///
 		    ///\ref named-templ-param "Named parameter" function for setting
 		    ///the map that indicates which nodes are processed.
 		    template<class T>
 		    DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
+		    {
 		      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetProcessedMapBase<T> >(*this);
+		    }
 		    template<class T>
 		    struct SetPathBase : public Base {
 		      typedef T Path;
 		      SetPathBase(const TR &b) : TR(b) {}
 		    };
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    ///
 		    ///\ref named-func-param "Named parameter"
 		    ///for getting the shortest path to the target node.
 		    template<class T>
 		    DijkstraWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return DijkstraWizard<SetPathBase<T> >(*this);
+		    }
 		    ///\brief \ref named-func-param "Named parameter"
 		    ///for getting the distance of the target node.

lemon/gomory_hu.h

Show inline comments

@@ -41,530 +41,528 @@
 		  /// property that the minimum capacity edge of the path between two nodes
 		  /// in this tree has the same weight as the minimum cut in the graph
 		  /// between these nodes. Moreover the components obtained by removing
 		  /// this edge from the tree determine the corresponding minimum cut.
 		  /// Therefore once this tree is computed, the minimum cut between any pair
 		  /// of nodes can easily be obtained.
 		  ///
 		  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
 		  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
 		  /// time complexity. It calculates a rooted Gomory-Hu tree.
 		  /// The structure of the tree and the edge weights can be
 		  /// obtained using \c predNode(), \c predValue() and \c rootDist().
 		  /// The functions \c minCutMap() and \c minCutValue() calculate
 		  /// the minimum cut and the minimum cut value between any two nodes
 		  /// in the graph. You can also list (iterate on) the nodes and the
 		  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
 		  ///
 		  /// \tparam GR The type of the undirected graph the algorithm runs on.
 		  /// \tparam CAP The type of the edge map containing the capacities.
 		  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR,
 			    typename CAP>
 		#else
 		  template <typename GR,
 			    typename CAP = typename GR::template EdgeMap<int> >
 		#endif
 		  class GomoryHu {
 		  public:
 		    /// The graph type of the algorithm
 		    typedef GR Graph;
 		    /// The capacity map type of the algorithm
 		    typedef CAP Capacity;
 		    /// The value type of capacities
 		    typedef typename Capacity::Value Value;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    const Graph& _graph;
 		    const Capacity& _capacity;
 		    Node _root;
 		    typename Graph::template NodeMap<Node>* _pred;
 		    typename Graph::template NodeMap<Value>* _weight;
 		    typename Graph::template NodeMap<int>* _order;
 		    void createStructures() {
 		      if (!_pred) {
 			_pred = new typename Graph::template NodeMap<Node>(_graph);
+		      }
 		      if (!_weight) {
 			_weight = new typename Graph::template NodeMap<Value>(_graph);
+		      }
 		      if (!_order) {
 			_order = new typename Graph::template NodeMap<int>(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_pred) {
 			delete _pred;
+		      }
 		      if (_weight) {
 			delete _weight;
+		      }
 		      if (_order) {
 			delete _order;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    /// \param graph The undirected graph the algorithm runs on.
 		    /// \param capacity The edge capacity map.
 		    GomoryHu(const Graph& graph, const Capacity& capacity)
 		      : _graph(graph), _capacity(capacity),
 			_pred(0), _weight(0), _order(0)
+		    {
 		      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
+		    }
 		    /// \brief Destructor
 		    ///
 		    /// Destructor.
 		    ~GomoryHu() {
 		      destroyStructures();
+		    }
 		  private:
 		    // Initialize the internal data structures
 		    void init() {
 		      createStructures();
 		      _root = NodeIt(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_pred)[n] = _root;
 		        (*_order)[n] = -1;
+		      }
 		      (*_pred)[_root] = INVALID;
 		      (*_weight)[_root] = std::numeric_limits<Value>::max();
+		    }
 		    // Start the algorithm
 		    void start() {
 		      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			if (n == _root) continue;
 			Node pn = (*_pred)[n];
 			fa.source(n);
 			fa.target(pn);
 			fa.runMinCut();
 			(*_weight)[n] = fa.flowValue();
 			for (NodeIt nn(_graph); nn != INVALID; ++nn) {
 			  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
 			    (*_pred)[nn] = n;
+			  }
+			}
 			if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
 			  (*_pred)[n] = (*_pred)[pn];
 			  (*_pred)[pn] = n;
 			  (*_weight)[n] = (*_weight)[pn];
 			  (*_weight)[pn] = fa.flowValue();
+			}
+		      }
 		      (*_order)[_root] = 0;
 		      int index = 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 			std::vector<Node> st;
 			Node nn = n;
 			while ((*_order)[nn] == -1) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
 			  (*_order)[st.back()] = index++;
 			  st.pop_back();
+			}
+		      }
+		    }
 		  public:
 		    ///\name Execution Control
 		    ///@{
 		    /// \brief Run the Gomory-Hu algorithm.
 		    ///
 		    /// This function runs the Gomory-Hu algorithm.
 		    void run() {
 		      init();
 		      start();
+		    }
 		    /// @}
 		    ///\name Query Functions
 		    ///The results of the algorithm can be obtained using these
 		    ///functions.\n
 		    ///\ref run() should be called before using them.\n
 		    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
 		    ///@{
 		    /// \brief Return the predecessor node in the Gomory-Hu tree.
 		    ///
 		    /// This function returns the predecessor node of the given node
 		    /// in the Gomory-Hu tree.
 		    /// If \c node is the root of the tree, then it returns \c INVALID.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Node predNode(const Node& node) const {
 		      return (*_pred)[node];
+		    }
 		    /// \brief Return the weight of the predecessor edge in the
 		    /// Gomory-Hu tree.
 		    ///
 		    /// This function returns the weight of the predecessor edge of the
 		    /// given node in the Gomory-Hu tree.
 		    /// If \c node is the root of the tree, the result is undefined.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value predValue(const Node& node) const {
 		      return (*_weight)[node];
+		    }
 		    /// \brief Return the distance from the root node in the Gomory-Hu tree.
 		    ///
 		    /// This function returns the distance of the given node from the root
 		    /// node in the Gomory-Hu tree.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    int rootDist(const Node& node) const {
 		      return (*_order)[node];
+		    }
 		    /// \brief Return the minimum cut value between two nodes
 		    ///
 		    /// This function returns the minimum cut value between the nodes
 		    /// \c s and \c t.
 		    /// It finds the nearest common ancestor of the given nodes in the
 		    /// Gomory-Hu tree and calculates the minimum weight edge on the
 		    /// paths to the ancestor.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value minCutValue(const Node& s, const Node& t) const {
 		      Node sn = s, tn = t;
 		      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) {
 			st.clear();
 		        Node nn = n;
 			while (!reached[nn]) {
 			  st.push_back(nn);
 			  nn = (*_pred)[nn];
+			}
 			while (!st.empty()) {
 			  cutMap.set(st.back(), cutMap[nn]);
 			  st.pop_back();
+			}
+		      }
 		      return value;
+		    }
 		    ///@}
 		    friend class MinCutNodeIt;
 		    /// Iterate on the nodes of a minimum cut
 		    /// This iterator class lists the nodes of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example counts the nodes in the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoryHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int cnt=0;
 		    /// 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++()
+		      {
 		        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation
 		      /// returns a \c Node, not a \c MinCutNodeIt, as one may
 		      /// expect.
 		      typename Graph::Node operator++(int)
+		      {
 		        typename Graph::Node n=*this;
 		        ++(*this);
 		        return n;
+		      }
 		    };
 		    friend class MinCutEdgeIt;
 		    /// Iterate on the edges of a minimum cut
 		    /// This iterator class lists the edges of a minimum cut found by
 		    /// GomoryHu. Before using it, you must allocate a GomoryHu class
 		    /// and call its \ref GomoryHu::run() "run()" method.
 		    ///
 		    /// This example computes the value of the minimum cut separating \c s from
 		    /// \c t.
 		    /// \code
 		    /// GomoryHu<Graph> gom(g, capacities);
 		    /// gom.run();
 		    /// int value=0;
 		    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
 		    ///   value+=capacities[e];
 		    /// \endcode
 		    /// The result will be the same as the value returned by
 		    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
 		    class MinCutEdgeIt
+		    {
 		      bool _side;
 		      const Graph &_graph;
 		      typename Graph::NodeIt _node_it;
 		      typename Graph::OutArcIt _arc_it;
 		      typename Graph::template NodeMap<bool> _cut;
 		      void step()
+		      {
 		        ++_arc_it;
 		        while(_node_it!=INVALID && _arc_it==INVALID)
+		          {
 		            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
 		            if(_node_it!=INVALID)
 		              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
+		          }
+		      }
 		    public:
 		      /// Constructor
 		      /// Constructor.
 		      ///
 		      MinCutEdgeIt(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 listed arcs
 		                   ///  will be oriented from the
 		                   ///  nodes of the component containing \c s,
 		                   ///  otherwise they will be oriented in the opposite
 		                   ///  direction.
+		                   )
 		        : _graph(gomory._graph), _cut(_graph)
+		      {
 		        gomory.minCutMap(s,t,_cut);
 		        if(!side)
 		          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
 		            _cut[n]=!_cut[n];
 		        for(_node_it=typename Graph::NodeIt(_graph);
 		            _node_it!=INVALID && !_cut[_node_it];
 		            ++_node_it) {}
 		        _arc_it = _node_it!=INVALID ?
 		          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
 		        while(_node_it!=INVALID && _arc_it == INVALID)
+		          {
 		            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
 		            if(_node_it!=INVALID)
 		              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
+		          }
 		        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
+		      }
 		      /// Conversion to \c Arc
 		      /// Conversion to \c Arc.
 		      ///
 		      operator typename Graph::Arc() const
+		      {
 		        return _arc_it;
+		      }
 		      /// Conversion to \c Edge
 		      /// Conversion to \c Edge.
 		      ///
 		      operator typename Graph::Edge() const
+		      {
 		        return _arc_it;
+		      }
 		      bool operator==(Invalid) { return _node_it==INVALID; }
 		      bool operator!=(Invalid) { return _node_it!=INVALID; }
 		      /// Next edge
 		      /// Next edge.
 		      ///
 		      MinCutEdgeIt &operator++()
+		      {
 		        step();
 		        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
 		        return *this;
+		      }
 		      /// Postfix incrementation
 		      /// Postfix incrementation.
 		      ///
 		      /// \warning This incrementation
 		      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
 		      typename Graph::Arc operator++(int)
+		      {
 		        typename Graph::Arc e=*this;
 		        ++(*this);
 		        return e;
+		      }
 		    };
 		  };
+		}
 		#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff