LEMON/LEMON-official Changeset - r964:141f9c0db4a3

Repositories » LEMON » LEMON-official

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

Changeset - r964:141f9c0db4a3

« 963:7f6e2b

1041:f112c1 »
967:38213a »
965:f80243 »

r964:141f9c0db4a3

Sat, 06 Mar 2010 15:35:12

[Not Reviewed]

0 comments (0 inline)

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

Unify the sources (#339)

! ! !

default

89 files changed:

demo/arg_parser_demo.cc

doc/groups.dox

doc/mainpage.dox

doc/min_cost_flow.dox

lemon/adaptors.h

lemon/arg_parser.cc

lemon/arg_parser.h

lemon/bellman_ford.h

139

lemon/bfs.h

lemon/binomial_heap.h

lemon/bits/array_map.h

lemon/bits/default_map.h

lemon/bits/edge_set_extender.h

111

lemon/bits/solver_bits.h

lemon/bits/windows.cc

lemon/bucket_heap.h

lemon/capacity_scaling.h

lemon/cbc.h

lemon/circulation.h

lemon/clp.cc

lemon/clp.h

lemon/concepts/digraph.h

lemon/concepts/graph.h

lemon/concepts/graph_components.h

lemon/concepts/heap.h

lemon/connectivity.h

lemon/core.h

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

↑ Collapse diff ↑

demo/arg_parser_demo.cc

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup demos
 		///\file
 		///\brief Argument parser demo
 		///
 		/// This example shows how the argument parser can be used.
 		///
 		/// \include arg_parser_demo.cc
 		#include <lemon/arg_parser.h>
 		using namespace lemon;
@@ -48,49 +48,49 @@
 		  // Add a string option
 		  ap.refOption("name", "A string input.", s);
 		  // Add bool options
 		  ap.refOption("f", "A switch.", b)
 		    .refOption("nohelp", "", nh)
 		    .refOption("gra", "Choice A", g1)
 		    .refOption("grb", "Choice B", g2)
 		    .refOption("grc", "Choice C", g3);
 		  // Bundle -gr* options into a group
 		  ap.optionGroup("gr", "gra")
 		    .optionGroup("gr", "grb")
 		    .optionGroup("gr", "grc");
 		  // Set the group mandatory
 		  ap.mandatoryGroup("gr");
 		  // Set the options of the group exclusive (only one option can be given)
 		  ap.onlyOneGroup("gr");
 		  // Add non-parsed arguments (e.g. input files)
 		  ap.other("infile", "The input file.")
 		    .other("...");
 		  // Throw an exception when problems occurs. The default behavior is to
 		  // exit(1) on these cases, but this makes Valgrind falsely warn
 		  // about memory leaks.
 		  ap.throwOnProblems();
 		  // Perform the parsing process
 		  // (in case of any error it terminates the program)
 		  // The try {} construct is necessary only if the ap.trowOnProblems()
 		  // setting is in use.
 		  try {
 		    ap.parse();
 		  } catch (ArgParserException &) { return 1; }
 		  // Check each option if it has been given and print its value
 		  std::cout << "Parameters of '" << ap.commandName() << "':\n";
 		  std::cout << "  Value of -n: " << i << std::endl;
 		  if(ap.given("val")) std::cout << "  Value of -val: " << d << std::endl;
 		  if(ap.given("val2")) {
 		    d = ap["val2"];
 		    std::cout << "  Value of -val2: " << d << std::endl;
+		  }
 		  if(ap.given("name")) std::cout << "  Value of -name: " << s << std::endl;
 		  if(ap.given("f")) std::cout << "  -f is given\n";
 		  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << nh << std::endl;
 		  if(ap.given("gra")) std::cout << "  -gra is given\n";
 		  if(ap.given("grb")) std::cout << "  -grb is given\n";
 		  if(ap.given("grc")) std::cout << "  -grc is given\n";

doc/groups.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		namespace lemon {
 		/**
 		@defgroup datas Data Structures
 		This group contains the several data structures implemented in LEMON.
 		*/
 		/**
 		@defgroup graphs Graph Structures
 		@ingroup datas
 		\brief Graph structures implemented in LEMON.

doc/mainpage.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		/**
 		\mainpage LEMON Documentation
 		\section intro Introduction
 		<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
 		and <b>O</b>ptimization in <b>N</b>etworks</i>.
 		It is a C++ template library providing efficient implementations of common
 		data structures and algorithms with focus on combinatorial optimization
-		tasks connected mainly with graphs and networks.
 		tasks connected mainly with graphs and networks.
 		<b>
 		LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>
 		project.
 		You are free to use it in your commercial or
 		non-commercial applications under very permissive
 		\ref license "license terms".
 		</b>
-		The project is maintained by the
 		The project is maintained by the
 		<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
 		Combinatorial Optimization</a> \ref egres
 		at the Operations Research Department of the
 		<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,
 		Budapest, Hungary.
 		LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
 		initiative \ref coinor.
 		\section howtoread How to Read the Documentation
 		If you would like to get to know the library, see
 		<a class="el" href="http://lemon.cs.elte.hu/pub/tutorial/">LEMON Tutorial</a>.
 		If you are interested in starting to use the library, see the <a class="el"
 		href="http://lemon.cs.elte.hu/trac/lemon/wiki/InstallGuide/">Installation
 		Guide</a>.
 		If you know what you are looking for, then try to find it under the
 		<a class="el" href="modules.html">Modules</a> section.
 		If you are a user of the old (0.x) series of LEMON, please check out the
 		\ref migration "Migration Guide" for the backward incompatibilities.
 		*/

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		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.
@@ -60,87 +60,87 @@
 		\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)\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
 		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$.

lemon/adaptors.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ADAPTORS_H
 		#define LEMON_ADAPTORS_H
 		/// \ingroup graph_adaptors
 		/// \file
 		/// \brief Adaptor classes for digraphs and graphs
 		///
 		/// This file contains several useful adaptors for digraphs and graphs.
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
@@ -400,49 +400,49 @@
 		  template<typename DGR>
 		  ReverseDigraph<const DGR> reverseDigraph(const DGR& digraph) {
 		    return ReverseDigraph<const DGR>(digraph);
+		  }
 		  template <typename DGR, typename NF, typename AF, bool ch = true>
 		  class SubDigraphBase : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
-		      _arc_filter = &arc_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]
 		                              || !(*_node_filter)[Parent::target(i)]))
 		        Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i != INVALID && (!(*_arc_filter)[i]
 		                              || !(*_node_filter)[Parent::source(i)]))
@@ -487,123 +487,123 @@
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		  public:
 		    template <typename V>
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
+		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
+		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
-			      LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
+		              LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename DGR, typename NF, typename AF>
 		  class SubDigraphBase<DGR, NF, AF, false>
 		    : public DigraphAdaptorBase<DGR> {
 		    typedef DigraphAdaptorBase<DGR> Parent;
 		  public:
 		    typedef DGR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef AF ArcFilterMap;
 		    typedef SubDigraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    AF* _arc_filter;
 		    SubDigraphBase()
 		      : Parent(), _node_filter(0), _arc_filter(0) { }
 		    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {
 		      Parent::initialize(digraph);
 		      _node_filter = &node_filter;
-		      _arc_filter = &arc_filter;
 		      _arc_filter = &arc_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::next(i);
+		    }
 		    void firstIn(Arc& i, const Node& n) const {
 		      Parent::firstIn(i, n);
 		      while (i!=INVALID && !(*_arc_filter)[i]) Parent::nextIn(i);
+		    }
 		    void firstOut(Arc& i, const Node& n) const {
 		      Parent::firstOut(i, n);
@@ -630,76 +630,76 @@
 		    void status(const Node& n, bool v) const { _node_filter->set(n, v); }
 		    void status(const Arc& a, bool v) const { _arc_filter->set(a, v); }
 		    bool status(const Node& n) const { return (*_node_filter)[n]; }
 		    bool status(const Arc& a) const { return (*_arc_filter)[a]; }
 		    typedef False NodeNumTag;
 		    typedef False ArcNumTag;
 		    typedef FindArcTagIndicator<DGR> FindArcTag;
 		    Arc findArc(const Node& source, const Node& target,
 		                const Arc& prev = INVALID) const {
 		      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(source, target, prev);
 		      while (arc != INVALID && !(*_arc_filter)[arc]) {
 		        arc = Parent::findArc(source, target, arc);
+		      }
 		      return arc;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {
 		      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,
 		        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
@@ -1000,146 +1000,146 @@
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      if (!(*_node_filter)[u] || !(*_node_filter)[v]) {
 		        return INVALID;
+		      }
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class EdgeMap
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, ch>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  template <typename GR, typename NF, typename EF>
 		  class SubGraphBase<GR, NF, EF, false>
 		    : public GraphAdaptorBase<GR> {
 		    typedef GraphAdaptorBase<GR> Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef EF EdgeFilterMap;
 		    typedef SubGraphBase Adaptor;
 		  protected:
 		    NF* _node_filter;
 		    EF* _edge_filter;
 		    SubGraphBase()
 			  : Parent(), _node_filter(0), _edge_filter(0) { }
 		    SubGraphBase()
 		          : Parent(), _node_filter(0), _edge_filter(0) { }
 		    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {
 		      Parent::initialize(graph);
 		      _node_filter = &node_filter;
 		      _edge_filter = &edge_filter;
+		    }
 		  public:
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    void first(Node& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_node_filter)[i]) Parent::next(i);
+		    }
 		    void first(Arc& i) const {
 		      Parent::first(i);
 		      while (i!=INVALID && !(*_edge_filter)[i]) Parent::next(i);
+		    }
 		    void first(Edge& i) const {
@@ -1198,107 +1198,107 @@
 		    typedef False ArcNumTag;
 		    typedef False EdgeNumTag;
 		    typedef FindArcTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      Arc arc = Parent::findArc(u, v, prev);
 		      while (arc != INVALID && !(*_edge_filter)[arc]) {
 		        arc = Parent::findArc(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
 		    Edge findEdge(const Node& u, const Node& v,
 		                  const Edge& prev = INVALID) const {
 		      Edge edge = Parent::findEdge(u, v, prev);
 		      while (edge != INVALID && !(*_edge_filter)[edge]) {
 		        edge = Parent::findEdge(u, v, edge);
+		      }
 		      return edge;
+		    }
 		    template <typename V>
-		    class NodeMap
 		    class NodeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class ArcMap
 		    class ArcMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {
-		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
-		    class EdgeMap
 		    class EdgeMap
 		      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 			LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		      typedef SubMapExtender<SubGraphBase<GR, NF, EF, false>,
 		        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;
 		    public:
 		      typedef V Value;
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)
 		        : Parent(adaptor) {}
 		      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
@@ -1483,112 +1483,112 @@
 		  /// \tparam GR The type of the adapted digraph or graph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept
 		  /// or the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam NF The type of the node filter map.
 		  /// It must be a \c bool (or convertible) node map of the
 		  /// adapted (di)graph. The default type is
 		  /// \ref concepts::Graph::NodeMap "GR::NodeMap<bool>".
 		  ///
 		  /// \note The \c Node and <tt>Arc/Edge</tt> types of this adaptor and the
 		  /// adapted (di)graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR, typename NF>
 		  class FilterNodes {
 		#else
 		  template<typename GR,
 		           typename NF = typename GR::template NodeMap<bool>,
 		           typename Enable = void>
 		  class FilterNodes :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
-		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,
 		                     true> > Parent;
 		  public:
 		    typedef GR Digraph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename Digraph::Arc, Const<bool, true> > const_true_map;
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given digraph or graph with the
 		    /// given node filter map.
-		    FilterNodes(GR& graph, NF& node_filter)
 		    FilterNodes(GR& graph, NF& node_filter)
 		      : Parent(), const_true_map()
+		    {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    /// \brief Sets the status of the given node
 		    ///
 		    /// This function sets the status of the given node.
 		    /// It is done by simply setting the assigned value of \c n
 		    /// to \c v in the node filter map.
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    /// \brief Returns the status of the given node
 		    ///
 		    /// This function returns the status of the given node.
 		    /// It is \c true if the given node is enabled (i.e. not hidden).
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    /// \brief Disables the given node
 		    ///
 		    /// This function disables the given node, so the iteration
 		    /// jumps over it.
 		    /// It is the same as \ref status() "status(n, false)".
 		    void disable(const Node& n) const { Parent::status(n, false); }
 		    /// \brief Enables the given node
 		    ///
 		    /// This function enables the given node.
 		    /// It is the same as \ref status() "status(n, true)".
 		    void enable(const Node& n) const { Parent::status(n, true); }
 		  };
 		  template<typename GR, typename NF>
 		  class FilterNodes<GR, NF,
 		                    typename enable_if<UndirectedTagIndicator<GR> >::type> :
 		    public GraphAdaptorExtender<
-		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > {
 		    typedef GraphAdaptorExtender<
-		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		      SubGraphBase<GR, NF, ConstMap<typename GR::Edge, Const<bool, true> >,
 		                   true> > Parent;
 		  public:
 		    typedef GR Graph;
 		    typedef NF NodeFilterMap;
 		    typedef typename Parent::Node Node;
 		  protected:
 		    ConstMap<typename GR::Edge, Const<bool, true> > const_true_map;
 		    FilterNodes() : const_true_map() {}
 		  public:
 		    FilterNodes(GR& graph, NodeFilterMap& node_filter) :
 		      Parent(), const_true_map() {
 		      Parent::initialize(graph, node_filter, const_true_map);
+		    }
 		    void status(const Node& n, bool v) const { Parent::status(n, v); }
 		    bool status(const Node& n) const { return Parent::status(n); }
 		    void disable(const Node& n) const { Parent::status(n, false); }
@@ -1632,49 +1632,49 @@
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam AF The type of the arc filter map.
 		  /// It must be a \c bool (or convertible) arc map of the
 		  /// adapted digraph. The default type is
 		  /// \ref concepts::Digraph::ArcMap "DGR::ArcMap<bool>".
 		  ///
 		  /// \note The \c Node and \c Arc types of this adaptor and the adapted
 		  /// digraph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename DGR,
 		           typename AF>
 		  class FilterArcs {
 		#else
 		  template<typename DGR,
 		           typename AF = typename DGR::template ArcMap<bool> >
 		  class FilterArcs :
 		    public DigraphAdaptorExtender<
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > {
 		#endif
 		    typedef DigraphAdaptorExtender<
-		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,
 		                     AF, false> > Parent;
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    /// The type of the arc filter map.
 		    typedef AF ArcFilterMap;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    ConstMap<typename DGR::Node, Const<bool, true> > const_true_map;
 		    FilterArcs() : const_true_map() {}
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subdigraph for the given digraph with the given arc
 		    /// filter map.
 		    FilterArcs(DGR& digraph, ArcFilterMap& arc_filter)
 		      : Parent(), const_true_map() {
@@ -1740,78 +1740,78 @@
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// This class provides only linear time counting for nodes, edges and arcs.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam EF The type of the edge filter map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node, \c Edge and \c Arc types of this adaptor and the
 		  /// adapted graph are convertible to each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename EF>
 		  class FilterEdges {
 		#else
 		  template<typename GR,
 		           typename EF = typename GR::template EdgeMap<bool> >
 		  class FilterEdges :
 		    public GraphAdaptorExtender<
-		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true> >,
 		                   EF, false> > {
 		#endif
 		    typedef GraphAdaptorExtender<
-		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		      SubGraphBase<GR, ConstMap<typename GR::Node, Const<bool, true > >,
 		                   EF, false> > Parent;
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the edge filter map.
 		    typedef EF EdgeFilterMap;
 		    typedef typename Parent::Edge Edge;
 		  protected:
 		    ConstMap<typename GR::Node, Const<bool, true> > const_true_map;
 		    FilterEdges() : const_true_map(true) {
 		      Parent::setNodeFilterMap(const_true_map);
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates a subgraph for the given graph with the given edge
 		    /// filter map.
-		    FilterEdges(GR& graph, EF& edge_filter)
 		    FilterEdges(GR& graph, EF& edge_filter)
 		      : Parent(), const_true_map() {
 		      Parent::initialize(graph, const_true_map, edge_filter);
+		    }
 		    /// \brief Sets the status of the given edge
 		    ///
 		    /// This function sets the status of the given edge.
 		    /// It is done by simply setting the assigned value of \c e
 		    /// to \c v in the edge filter map.
 		    void status(const Edge& e, bool v) const { Parent::status(e, v); }
 		    /// \brief Returns the status of the given edge
 		    ///
 		    /// This function returns the status of the given edge.
 		    /// It is \c true if the given edge is enabled (i.e. not hidden).
 		    bool status(const Edge& e) const { return Parent::status(e); }
 		    /// \brief Disables the given edge
 		    ///
 		    /// This function disables the given edge in the subgraph,
 		    /// so the iteration jumps over it.
 		    /// It is the same as \ref status() "status(e, false)".
 		    void disable(const Edge& e) const { Parent::status(e, false); }
@@ -1837,49 +1837,49 @@
 		  template<typename GR, typename EF>
 		  FilterEdges<const GR, const EF>
 		  filterEdges(const GR& graph, const EF& edge_filter) {
 		    return FilterEdges<const GR, const EF>(graph, edge_filter);
+		  }
 		  template <typename DGR>
 		  class UndirectorBase {
 		  public:
 		    typedef DGR Digraph;
 		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
 		    class Arc {
 		      friend class UndirectorBase;
 		    protected:
 		      Edge _edge;
 		      bool _forward;
-		      Arc(const Edge& edge, bool forward)
 		      Arc(const Edge& edge, bool forward)
 		        : _edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : _edge(INVALID), _forward(true) {}
 		      operator const Edge&() const { return _edge; }
 		      bool operator==(const Arc &other) const {
 		        return _forward == other._forward && _edge == other._edge;
+		      }
 		      bool operator!=(const Arc &other) const {
 		        return _forward != other._forward || _edge != other._edge;
+		      }
 		      bool operator<(const Arc &other) const {
 		        return _forward < other._forward ||
 		          (_forward == other._forward && _edge < other._edge);
+		      }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
+		    }
@@ -2077,49 +2077,49 @@
 		  private:
 		    template <typename V>
 		    class ArcMapBase {
 		    private:
 		      typedef typename DGR::template ArcMap<V> MapImpl;
 		    public:
 		      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef V Value;
 		      typedef Arc Key;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
 		      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
 		        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
-		        : _forward(*adaptor._digraph, value),
 		        : _forward(*adaptor._digraph, value),
 		          _backward(*adaptor._digraph, value) {}
 		      void set(const Arc& a, const V& value) {
 		        if (direction(a)) {
 		          _forward.set(a, value);
 		        } else {
 		          _backward.set(a, value);
+		        }
+		      }
 		      ConstReturnValue operator[](const Arc& a) const {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		      ReturnValue operator[](const Arc& a) {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
@@ -2195,49 +2195,49 @@
 		      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
 		    typedef EdgeNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 		  protected:
 		    UndirectorBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(DGR& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for viewing a digraph as an undirected graph.
 		  ///
 		  /// Undirector adaptor can be used for viewing a digraph as an undirected
 		  /// graph. All arcs of the underlying digraph are showed in the
 		  /// adaptor as an edge (and also as a pair of arcs, of course).
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
@@ -2707,49 +2707,49 @@
 		  /// the capacities in the flow problem. It is implicitly \c const.
 		  /// The default type is
 		  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		  /// \tparam FM The type of the flow map.
 		  /// It must be an arc map of some numerical type, which defines
 		  /// the flow values in the flow problem. The default type is \c CM.
 		  /// \tparam TL The tolerance type for handling inexact computation.
 		  /// The default tolerance type depends on the value type of the
 		  /// capacity map.
 		  ///
 		  /// \note This adaptor is implemented using Undirector and FilterArcs
 		  /// adaptors.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// is convertible to the \c Arc type of the adapted digraph.
 		#ifdef DOXYGEN
 		  template<typename DGR, typename CM, typename FM, typename TL>
 		  class ResidualDigraph
 		#else
 		  template<typename DGR,
 		           typename CM = typename DGR::template ArcMap<int>,
 		           typename FM = CM,
 		           typename TL = Tolerance<typename CM::Value> >
-		  class ResidualDigraph
 		  class ResidualDigraph
 		    : public SubDigraph<
 		        Undirector<const DGR>,
 		        ConstMap<typename DGR::Node, Const<bool, true> >,
 		        typename Undirector<const DGR>::template CombinedArcMap<
 		          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,
 		          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >
 		#endif
+		  {
 		  public:
 		    /// The type of the underlying digraph.
 		    typedef DGR Digraph;
 		    /// The type of the capacity map.
 		    typedef CM CapacityMap;
 		    /// The type of the flow map.
 		    typedef FM FlowMap;
 		    /// The tolerance type.
 		    typedef TL Tolerance;
 		    typedef typename CapacityMap::Value Value;
 		    typedef ResidualDigraph Adaptor;
 		  protected:
@@ -2764,49 +2764,49 @@
 		                                             FM, TL> BackwardFilter;
 		    typedef typename Undirected::
 		      template CombinedArcMap<ForwardFilter, BackwardFilter> ArcFilter;
 		    typedef SubDigraph<Undirected, NodeFilter, ArcFilter> Parent;
 		    const CapacityMap* _capacity;
 		    FlowMap* _flow;
 		    Undirected _graph;
 		    NodeFilter _node_filter;
 		    ForwardFilter _forward_filter;
 		    BackwardFilter _backward_filter;
 		    ArcFilter _arc_filter;
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the residual digraph adaptor. The parameters are the
 		    /// digraph, the capacity map, the flow map, and a tolerance object.
 		    ResidualDigraph(const DGR& digraph, const CM& capacity,
 		                    FM& flow, const TL& tolerance = Tolerance())
-		      : Parent(), _capacity(&capacity), _flow(&flow),
 		      : Parent(), _capacity(&capacity), _flow(&flow),
 		        _graph(digraph), _node_filter(),
 		        _forward_filter(capacity, flow, tolerance),
 		        _backward_filter(capacity, flow, tolerance),
 		        _arc_filter(_forward_filter, _backward_filter)
+		    {
 		      Parent::initialize(_graph, _node_filter, _arc_filter);
+		    }
 		    typedef typename Parent::Arc Arc;
 		    /// \brief Returns the residual capacity of the given arc.
 		    ///
 		    /// Returns the residual capacity of the given arc.
 		    Value residualCapacity(const Arc& a) const {
 		      if (Undirected::direction(a)) {
 		        return (*_capacity)[a] - (*_flow)[a];
 		      } else {
 		        return (*_flow)[a];
+		      }
+		    }
 		    /// \brief Augments on the given arc in the residual digraph.
 		    ///
 		    /// Augments on the given arc in the residual digraph. It increases
@@ -2846,49 +2846,49 @@
 		    /// \brief Returns the backward oriented residual arc.
 		    ///
 		    /// Returns the backward oriented residual arc related to the given
 		    /// arc of the underlying digraph.
 		    static Arc backward(const typename Digraph::Arc& a) {
 		      return Undirected::direct(a, false);
+		    }
 		    /// \brief Residual capacity map.
 		    ///
 		    /// This map adaptor class can be used for obtaining the residual
 		    /// capacities as an arc map of the residual digraph.
 		    /// Its value type is inherited from the capacity map.
 		    class ResidualCapacity {
 		    protected:
 		      const Adaptor* _adaptor;
 		    public:
 		      /// The key type of the map
 		      typedef Arc Key;
 		      /// The value type of the map
 		      typedef typename CapacityMap::Value Value;
 		      /// Constructor
-		      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
 		      ResidualCapacity(const ResidualDigraph<DGR, CM, FM, TL>& adaptor)
 		        : _adaptor(&adaptor) {}
 		      /// Returns the value associated with the given residual arc
 		      Value operator[](const Arc& a) const {
 		        return _adaptor->residualCapacity(a);
+		      }
 		    };
 		    /// \brief Returns a residual capacity map
 		    ///
 		    /// This function just returns a residual capacity map.
 		    ResidualCapacity residualCapacity() const {
 		      return ResidualCapacity(*this);
+		    }
 		  };
 		  /// \brief Returns a (read-only) Residual adaptor
 		  ///
 		  /// This function just returns a (read-only) \ref ResidualDigraph adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates ResidualDigraph
 		    template<typename DGR, typename CM, typename FM>
@@ -3426,49 +3426,49 @@
 		    /// \brief Returns the bind arc that corresponds to the given
 		    /// original node.
 		    ///
 		    /// Returns the bind arc in the adaptor that corresponds to the given
 		    /// original node, i.e. the arc connecting the in-node and out-node
 		    /// of \c n.
 		    static Arc arc(const DigraphNode& n) {
 		      return Parent::arc(n);
+		    }
 		    /// \brief Returns the arc that corresponds to the given original arc.
 		    ///
 		    /// Returns the arc in the adaptor that corresponds to the given
 		    /// original arc.
 		    static Arc arc(const DigraphArc& a) {
 		      return Parent::arc(a);
+		    }
 		    /// \brief Node map combined from two original node maps
 		    ///
 		    /// This map adaptor class adapts two node maps of the original digraph
 		    /// to get a node map of the split digraph.
 		    /// Its value type is inherited from the first node map type (\c IN).
-		    /// \tparam IN The type of the node map for the in-nodes.
 		    /// \tparam IN The type of the node map for the in-nodes.
 		    /// \tparam OUT The type of the node map for the out-nodes.
 		    template <typename IN, typename OUT>
 		    class CombinedNodeMap {
 		    public:
 		      /// The key type of the map
 		      typedef Node Key;
 		      /// The value type of the map
 		      typedef typename IN::Value Value;
 		      typedef typename MapTraits<IN>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<IN>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<IN>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<IN>::ReturnValue Reference;
 		      typedef typename MapTraits<IN>::ConstReturnValue ConstReference;
 		      /// Constructor
 		      CombinedNodeMap(IN& in_map, OUT& out_map)
 		        : _in_map(in_map), _out_map(out_map) {}
 		      /// Returns the value associated with the given key.
 		      Value operator[](const Key& key) const {
 		        if (SplitNodesBase<const DGR>::inNode(key)) {
 		          return _in_map[key];

lemon/arg_parser.cc

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
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/arg_parser.h>

namespace lemon {

  void ArgParser::_terminate(ArgParserException::Reason reason) const
  {
    if(_exit_on_problems)
      exit(1);
    else throw(ArgParserException(reason));
  }
  
  


  void ArgParser::_showHelp(void *p)
  {
    (static_cast<ArgParser*>(p))->showHelp();
    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
  }

  ArgParser::ArgParser(int argc, const char * const *argv)
    :_argc(argc), _argv(argv), _command_name(argv[0]),
    _exit_on_problems(true) {
    funcOption("-help","Print a short help message",_showHelp,this);
    synonym("help","-help");
    synonym("h","-help");
  }

  ArgParser::~ArgParser()
  {
    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
      if(i->second.self_delete)
        switch(i->second.type) {
        case BOOL:
          delete i->second.bool_p;
          break;
        case STRING:
          delete i->second.string_p;

lemon/arg_parser.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_ARG_PARSER_H
 		#define LEMON_ARG_PARSER_H
 		#include <vector>
 		#include <map>
 		#include <list>
 		#include <string>
 		#include <iostream>
 		#include <sstream>
 		#include <algorithm>
 		#include <lemon/assert.h>
 		///\ingroup misc
 		///\file
 		///\brief A tool to parse command line arguments.
 		namespace lemon {
 		  ///Exception used by ArgParser
 		  class ArgParserException : public Exception {
 		  public:
 		    enum Reason {
 		      HELP,         /// <tt>--help</tt> option was given
 		      UNKNOWN_OPT,  /// Unknown option was given
 		      INVALID_OPT   /// Invalid combination of options
 		    };
 		  private:
 		    Reason _reason;
 		  public:
 		    ///Constructor
 		    ArgParserException(Reason r) throw() : _reason(r) {}
 		    ///Virtual destructor
 		    virtual ~ArgParserException() throw() {}
 		    ///A short description of the exception
 		    virtual const char* what() const throw() {
 		      switch(_reason)
+		        {
 		        case HELP:
 		          return "lemon::ArgParseException: ask for help";
 		          break;
 		        case UNKNOWN_OPT:
 		          return "lemon::ArgParseException: unknown option";
 		          break;
 		        case INVALID_OPT:
 		          return "lemon::ArgParseException: invalid combination of options";
 		          break;
+		        }
 		      return "";
+		    }
 		    ///Return the reason for the failure
 		    Reason reason() const {return _reason; }
 		  };
@@ -120,63 +120,63 @@
+		    {
 		    public:
 		      typedef std::list<std::string> Opts;
 		      Opts opts;
 		      bool only_one;
 		      bool mandatory;
 		      GroupData() :only_one(false), mandatory(false) {}
 		    };
 		    typedef std::map<std::string,GroupData> Groups;
 		    Groups _groups;
 		    struct OtherArg
+		    {
 		      std::string name;
 		      std::string help;
 		      OtherArg(std::string n, std::string h) :name(n), help(h) {}
 		    };
 		    std::vector<OtherArg> _others_help;
 		    std::vector<std::string> _file_args;
 		    std::string _command_name;
 		  private:
 		    //Bind a function to an option.
 		    //\param name The name of the option. The leading '-' must be omitted.
 		    //\param help A help string.
 		    //\retval func The function to be called when the option is given. It
 		    //  must be of type "void f(void *)"
 		    //\param data Data to be passed to \c func
 		    ArgParser &funcOption(const std::string &name,
 		                    const std::string &help,
 		                    void (*func)(void *),void *data);
 		    bool _exit_on_problems;
 		    void _terminate(ArgParserException::Reason reason) const;
 		  public:
 		    ///Constructor
 		    ArgParser(int argc, const char * const *argv);
 		    ~ArgParser();
 		    ///\name Options
 		    ///
 		    ///@{
 		    ///Add a new integer type option
 		    ///Add a new integer type option.
 		    ///\param name The name of the option. The leading '-' must be omitted.
 		    ///\param help A help string.
 		    ///\param value A default value for the option.
 		    ///\param obl Indicate if the option is mandatory.
 		    ArgParser &intOption(const std::string &name,
 		                    const std::string &help,
 		                    int value=0, bool obl=false);
@@ -402,32 +402,32 @@
 		                     std::string()+"Unkown option: '"+_name+"'");
 		        LEMON_ASSERT(i->second.type==ArgParser::INTEGER,
 		                     std::string()+"'"+_name+"' is an integer option");
 		        return *(i->second.int_p);
+		      }
 		    };
 		    ///Give back the value of an option
 		    ///Give back the value of an option.
 		    ///\sa RefType
 		    RefType operator[](const std::string &n) const
+		    {
 		      return RefType(*this, n);
+		    }
 		    ///Give back the non-option type arguments.
 		    ///Give back a reference to a vector consisting of the program arguments
 		    ///not starting with a '-' character.
 		    const std::vector<std::string> &files() const { return _file_args; }
 		    ///Throw instead of exit in case of problems
-		    void throwOnProblems()
 		    void throwOnProblems()
+		    {
 		      _exit_on_problems=false;
+		    }
 		  };
+		}
 		#endif // LEMON_ARG_PARSER_H

lemon/bellman_ford.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BELLMAN_FORD_H
 		#define LEMON_BELLMAN_FORD_H
 		/// \ingroup shortest_path
 		/// \file
 		/// \brief Bellman-Ford 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/tolerance.h>
 		#include <lemon/path.h>
 		#include <limits>
 		namespace lemon {
 		  /// \brief Default operation traits for the BellmanFord algorithm class.
-		  ///
 		  ///
 		  /// This operation traits class defines all computational operations
 		  /// and constants that are used in the Bellman-Ford algorithm.
 		  /// The default implementation is based on the \c numeric_limits class.
 		  /// If the numeric type does not have infinity value, then the maximum
 		  /// value is used as extremal infinity value.
 		  ///
 		  /// \see BellmanFordToleranceOperationTraits
 		  template <
-		    typename V,
 		    typename V,
 		    bool has_inf = std::numeric_limits<V>::has_infinity>
 		  struct BellmanFordDefaultOperationTraits {
 		    /// \brief Value type for the algorithm.
 		    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 Operation traits for the BellmanFord algorithm class
 		  /// using tolerance.
 		  ///
 		  /// This operation traits class defines all computational operations
 		  /// and constants that are used in the Bellman-Ford algorithm.
 		  /// The only difference between this implementation and
 		  /// \ref BellmanFordDefaultOperationTraits is that this class uses
 		  /// the \ref Tolerance "tolerance technique" in its \ref less()
 		  /// function.
 		  ///
 		  /// \tparam V The value type.
 		  /// \tparam eps The epsilon value for the \ref less() function.
 		  /// By default, it is the epsilon value used by \ref Tolerance
 		  /// "Tolerance<V>".
 		  ///
 		  /// \see BellmanFordDefaultOperationTraits
 		#ifdef DOXYGEN
 		  template <typename V, V eps>
 		#else
 		  template <
 		    typename V,
 		    V eps = Tolerance<V>::def_epsilon>
 		#endif
 		  struct BellmanFordToleranceOperationTraits {
@@ -118,1048 +118,1048 @@
 		      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 + eps < 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.
 		    /// 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,
 		    /// BellmanFordToleranceOperationTraits
 		    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
 		    /// \brief The type of the map that stores the last arcs of the
 		    /// \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.
 		    ///
 		    /// 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
 		    /// 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
 		  /// 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
 		  /// \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>".
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
 		  /// "BellmanFordDefaultTraits<GR, LEN>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#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);
 		        _local_pred = true;
 		        _pred = Traits::createPredMap(*_gr);
+		      }
 		      if(!_dist) {
 			_local_dist = true;
 			_dist = Traits::createDistMap(*_gr);
 		        _local_dist = true;
 		        _dist = Traits::createDistMap(*_gr);
+		      }
 		      if(!_mask) {
 		        _mask = new MaskMap(*_gr);
+		      }
+		    }
 		  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
 		    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
 		    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
 		    /// \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.
 		    template <class T>
 		    struct SetOperationTraits
 		      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 		      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
 		      Create;
 		    };
 		    ///@}
 		  protected:
 		    BellmanFord() {}
 		  public:
 		  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;
 		        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;
 		        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);
 		        _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);
+			}
 		        for (NodeIt it(*_gr); it != INVALID; ++it) {
 		          _process.push_back(it);
 		          _mask->set(it, true);
+		        }
 		      } else {
 			for (NodeIt it(*_gr); it != INVALID; ++it) {
 			  _mask->set(it, false);
+			}
+		        for (NodeIt it(*_gr); it != INVALID; ++it) {
 		          _mask->set(it, false);
+		        }
+		      }
+		    }
 		    /// \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);
 		        _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);
+		        _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]];
+		        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);
+			    }
+			  }
+			}
 		        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);
+		        _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);
+			    }
+			  }
+			}
+		        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;
+		        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 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.
 		    /// added with addSource() before using this function.
 		    bool checkedStart() {
 		      int num = countNodes(*_gr);
 		      for (int i = 0; i < num; ++i) {
-			if (processNextWeakRound()) return true;
+		        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.
 		    /// added with addSource() before using this function.
 		    void limitedStart(int num) {
 		      for (int i = 0; i < num; ++i) {
-			if (processNextRound()) break;
+		        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.
 		      /// 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 {
 		      operator Node() const {
 		        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+		      }
 		      /// \brief Increment operator.
 		      ///
 		      /// Increment operator.
 		      ActiveIt& operator++() {
 		        --_index;
-		        return *this;
 		        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);
 		      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 \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 \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]);
 		    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.
 		    /// 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,
 		    /// BellmanFordToleranceOperationTraits
 		    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.
 		    /// 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
 		  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))),
 		    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.
 		  ///
 		  /// \tparam TR The traits class that defines various types used by 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)
 		    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),
 		      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));
 		      if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
 		      bf.run(s);
 		      if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
 		      if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
 		      return bf.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" for setting
 		    /// the map that stores the predecessor arcs of the nodes.
 		    template<class T>
 		    BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
 		      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<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" for setting
 		    /// the map that stores the distances of the nodes calculated
 		    /// by the algorithm.
 		    template<class T>
 		    BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
 		      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetDistMapBase<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>
 		    BellmanFordWizard<SetPathBase<T> > path(const T &t)
+		    {
 		      Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
 		      return BellmanFordWizard<SetPathBase<T> >(*this);
+		    }
 		    /// \brief \ref named-func-param "Named parameter" for getting
 		    /// the distance of the target node.
 		    ///
 		    /// \ref named-func-param "Named parameter" for getting
 		    /// the distance of the target node.
 		    BellmanFordWizard dist(const Value &d)
+		    {
 		      Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
 		      return *this;
+		    }
 		  };
 		  /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
 		  /// algorithm.
 		  ///
 		  /// \ingroup shortest_path
 		  /// Function type interface for the \ref BellmanFord "Bellman-Ford"
 		  /// algorithm.
 		  ///
 		  /// This function also has several \ref named-templ-func-param
 		  /// "named parameters", they are declared as the members of class
 		  /// This function also has several \ref named-templ-func-param
 		  /// "named parameters", they are declared as the members of class
 		  /// \ref BellmanFordWizard.
 		  /// The following examples show how to use these parameters.
 		  /// \code
 		  ///   // Compute shortest path from node s to each node
 		  ///   bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///   // Compute shortest path from s to t
 		  ///   bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
 		  /// \endcode
 		  /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
 		  /// to the end of the parameter list.
 		  /// \sa BellmanFordWizard
 		  /// \sa BellmanFord
 		  template<typename GR, typename LEN>
 		  BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
 		  bellmanFord(const GR& digraph,
-			      const LEN& length)
+		              const LEN& length)
+		  {
 		    return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
+		  }
 		} //END OF NAMESPACE LEMON
 		#endif

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_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>
@@ -61,49 +61,50 @@
 		    ///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.
 		    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.
 		    ///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);
@@ -250,49 +251,50 @@
 		    ///\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.
 		    ///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;
 		    };
@@ -851,49 +853,50 @@
 		    ///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.
 		    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.
 		    ///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);
@@ -1244,49 +1247,50 @@
 		        visitor.start(node);
 		        visitor.reach(node);
 		        visitor.process(node);
 		        visitor.discover(arc);
 		        visitor.examine(arc);
+		      }
 		      _Visitor& visitor;
 		    };
 		  };
 		#endif
 		  /// \brief Default traits class of BfsVisit class.
 		  ///
 		  /// Default traits class of BfsVisit class.
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  template<class GR>
 		  struct BfsVisitDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief 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.
 		    /// It must conform to
 		    ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    /// \brief Instantiates a ReachedMap.
 		    ///
 		    /// This function instantiates a ReachedMap.
 		    /// \param digraph is the digraph, to which
 		    /// we would like to define the ReachedMap.
 		    static ReachedMap *createReachedMap(const Digraph &digraph) {
 		      return new ReachedMap(digraph);
+		    }
 		  };
 		  /// \ingroup search
 		  ///
 		  /// \brief BFS algorithm class with visitor interface.
 		  ///
 		  /// This class provides an efficient implementation of the BFS algorithm
 		  /// with visitor interface.
 		  ///
 		  /// The BfsVisit class provides an alternative interface to the Bfs
 		  /// class. It works with callback mechanism, the BfsVisit object calls
 		  /// the member functions of the \c Visitor class on every BFS event.
 		  ///

lemon/binomial_heap.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BINOMIAL_HEAP_H
 		#define LEMON_BINOMIAL_HEAP_H
 		///\file
 		///\ingroup heaps
 		///\brief Binomial Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		#include <lemon/math.h>
@@ -237,49 +237,49 @@
 		    /// \brief Remove the given item from the heap.
 		    ///
 		    /// This function removes the given item from the heap if it is
 		    /// already stored.
 		    /// \param item The item to delete.
 		    /// \pre \e item must be in the heap.
 		    void erase (const Item& item) {
 		      int i=_iim[item];
 		      if ( i >= 0 && _data[i].in ) {
 		        decrease( item, _data[_min].prio-1 );
 		        pop();
+		      }
+		    }
 		    /// \brief Decrease the priority of an item to the given value.
 		    ///
 		    /// This function decreases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param value The priority.
 		    /// \pre \e item must be stored in the heap with priority at least \e value.
 		    void decrease (Item item, const Prio& value) {
 		      int i=_iim[item];
 		      int p=_data[i].parent;
 		      _data[i].prio=value;
 		      while( p!=-1 && _comp(value, _data[p].prio) ) {
 		        _data[i].name=_data[p].name;
 		        _data[i].prio=_data[p].prio;
 		        _data[p].name=item;
 		        _data[p].prio=value;
 		        _iim[_data[i].name]=i;
 		        i=p;
 		        p=_data[p].parent;
+		      }
 		      _iim[item]=i;
 		      if ( _comp(value, _data[_min].prio) ) _min=i;
+		    }
 		    /// \brief Increase the priority of an item to the given value.
 		    ///
 		    /// This function increases the priority of an item to the given value.
 		    /// \param item The item.
 		    /// \param value The priority.
 		    /// \pre \e item must be stored in the heap with priority at most \e value.
 		    void increase (Item item, const Prio& value) {
 		      erase(item);
 		      push(item, value);
+		    }
@@ -301,124 +301,124 @@
+		    }
 		    /// \brief Set the state of an item in the heap.
 		    ///
 		    /// This function sets the state of the given item in the heap.
 		    /// It can be used to manually clear the heap when it is important
 		    /// to achive better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		  private:
 		    // Find the minimum of the roots
 		    int findMin() {
 		      if( _head!=-1 ) {
 		        int min_loc=_head, min_val=_data[_head].prio;
 		        for( int x=_data[_head].right_neighbor; x!=-1;
 		             x=_data[x].right_neighbor ) {
 		          if( _comp( _data[x].prio,min_val ) ) {
 		            min_val=_data[x].prio;
 		            min_loc=x;
+		          }
+		        }
 		        return min_loc;
+		      }
 		      else return -1;
+		    }
 		    // Merge the heap with another heap starting at the given position
 		    void merge(int a) {
 		      if( _head==-1 || a==-1 ) return;
 		      if( _data[a].right_neighbor==-1 &&
 		          _data[a].degree<=_data[_head].degree ) {
 		        _data[a].right_neighbor=_head;
 		        _head=a;
 		      } else {
 		        interleave(a);
+		      }
 		      if( _data[_head].right_neighbor==-1 ) return;
 		      int x=_head;
 		      int x_prev=-1, x_next=_data[x].right_neighbor;
 		      while( x_next!=-1 ) {
 		        if( _data[x].degree!=_data[x_next].degree ||
 		            ( _data[x_next].right_neighbor!=-1 &&
 		              _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
 		          x_prev=x;
 		          x=x_next;
+		        }
 		        else {
 		          if( _comp(_data[x_next].prio,_data[x].prio) ) {
 		            if( x_prev==-1 ) {
 		              _head=x_next;
 		            } else {
 		              _data[x_prev].right_neighbor=x_next;
+		            }
 		            fuse(x,x_next);
 		            x=x_next;
+		          }
 		          else {
 		            _data[x].right_neighbor=_data[x_next].right_neighbor;
 		            fuse(x_next,x);
+		          }
+		        }
 		        x_next=_data[x].right_neighbor;
+		      }
+		    }
 		    // Interleave the elements of the given list into the list of the roots
 		    void interleave(int a) {
 		      int p=_head, q=a;
 		      int curr=_data.size();
 		      _data.push_back(Store());
 		      while( p!=-1 || q!=-1 ) {
 		        if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
 		          _data[curr].right_neighbor=p;
 		          curr=p;
 		          p=_data[p].right_neighbor;
+		        }
 		        else {
 		          _data[curr].right_neighbor=q;
 		          curr=q;
 		          q=_data[q].right_neighbor;
+		        }
+		      }
 		      _head=_data.back().right_neighbor;
 		      _data.pop_back();
+		    }
 		    // Lace node a under node b
 		    void fuse(int a, int b) {
 		      _data[a].parent=b;
 		      _data[a].right_neighbor=_data[b].child;
 		      _data[b].child=a;
 		      ++_data[b].degree;
+		    }
 		    // Unlace node a (if it has siblings)
 		    void unlace(int a) {
 		      int neighb=_data[a].right_neighbor;
 		      int other=_head;
 		      while( _data[other].right_neighbor!=a )
 		        other=_data[other].right_neighbor;
 		      _data[other].right_neighbor=neighb;
+		    }
 		  private:

lemon/bits/array_map.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_ARRAY_MAP_H
 		#define LEMON_BITS_ARRAY_MAP_H
 		#include <memory>
 		#include <lemon/bits/traits.h>
 		#include <lemon/bits/alteration_notifier.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		// \ingroup graphbits
@@ -49,49 +49,49 @@
 		    // The graph type.
 		    typedef _Graph GraphType;
 		    // The item type.
 		    typedef _Item Item;
 		    // The reference map tag.
 		    typedef True ReferenceMapTag;
 		    // The key type of the map.
 		    typedef _Item Key;
 		    // The value type of the map.
 		    typedef _Value Value;
 		    // The const reference type of the map.
 		    typedef const _Value& ConstReference;
 		    // The reference type of the map.
 		    typedef _Value& Reference;
 		    // The map type.
 		    typedef ArrayMap Map;
 		    // The notifier type.
 		    typedef typename ItemSetTraits<_Graph, _Item>::ItemNotifier Notifier;
 		  private:
 		    // The MapBase of the Map which imlements the core regisitry function.
 		    typedef typename Notifier::ObserverBase Parent;
 		    typedef std::allocator<Value> Allocator;
 		  public:
 		    // \brief Graph initialized map constructor.
 		    //
 		    // Graph initialized map constructor.
 		    explicit ArrayMap(const GraphType& graph) {
 		      Parent::attach(graph.notifier(Item()));
 		      allocate_memory();
 		      Notifier* nf = Parent::notifier();
 		      Item it;
 		      for (nf->first(it); it != INVALID; nf->next(it)) {
 		        int id = nf->id(it);;
 		        allocator.construct(&(values[id]), Value());
+		      }
+		    }
 		    // \brief Constructor to use default value to initialize the map.
 		    //
 		    // It constructs a map and initialize all of the the map.

lemon/bits/default_map.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_DEFAULT_MAP_H
 		#define LEMON_BITS_DEFAULT_MAP_H
 		#include <lemon/config.h>
 		#include <lemon/bits/array_map.h>
 		#include <lemon/bits/vector_map.h>
 		//#include <lemon/bits/debug_map.h>
 		//\ingroup graphbits
 		//\file
 		//\brief Graph maps that construct and destruct their elements dynamically.
@@ -136,47 +136,47 @@
 		  // pointer
 		  template <typename _Graph, typename _Item, typename _Ptr>
 		  struct DefaultMapSelector<_Graph, _Item, _Ptr*> {
 		    typedef VectorMap<_Graph, _Item, _Ptr*> Map;
 		  };
 		// #else
 		//   template <typename _Graph, typename _Item, typename _Value>
 		//   struct DefaultMapSelector {
 		//     typedef DebugMap<_Graph, _Item, _Value> Map;
 		//   };
 		// #endif
 		  // DefaultMap class
 		  template <typename _Graph, typename _Item, typename _Value>
 		  class DefaultMap
 		    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
 		    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
 		  public:
 		    typedef DefaultMap<_Graph, _Item, _Value> Map;
 		    typedef typename Parent::GraphType GraphType;
 		    typedef typename Parent::Value Value;
 		    explicit DefaultMap(const GraphType& graph) : Parent(graph) {}
 		    DefaultMap(const GraphType& graph, const Value& value)
 		      : Parent(graph, value) {}
 		    DefaultMap& operator=(const DefaultMap& cmap) {
 		      return operator=<DefaultMap>(cmap);
+		    }
 		    template <typename CMap>
 		    DefaultMap& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  };
+		}
 		#endif

lemon/bits/edge_set_extender.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
 		#define LEMON_BITS_EDGE_SET_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/default_map.h>
 		#include <lemon/bits/map_extender.h>
 		//\ingroup digraphbits
 		//\file
 		//\brief Extenders for the arc set types
@@ -42,233 +42,233 @@
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
-			return Parent::target(e);
+		        return Parent::target(e);
 		      else if(n==Parent::target(e))
-			return Parent::source(e);
+		        return Parent::source(e);
 		      else
-			return INVALID;
+		        return INVALID;
+		    }
 		    // Alteration notifier extensions
 		    // The arc observer registry.
 		    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		  public:
 		    using Parent::notifier;
 		    // Gives back the arc alteration notifier.
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    // Iterable extensions
-		    class NodeIt : public Node {
 		    class NodeIt : public Node {
 		      const Digraph* digraph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
-			_graph.first(static_cast<Node&>(*this));
+		        _graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Digraph& _graph, const Node& node)
 			: Node(node), digraph(&_graph) {}
 		      NodeIt(const Digraph& _graph, const Node& node)
 		        : Node(node), digraph(&_graph) {}
 		      NodeIt& operator++() {
 			digraph->next(*this);
-			return *this;
+		      NodeIt& operator++() {
 		        digraph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class ArcIt : public Arc {
 		    class ArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
-			_graph.first(static_cast<Arc&>(*this));
+		        _graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 			Arc(e), digraph(&_graph) { }
 		      ArcIt(const Digraph& _graph, const Arc& e) :
 		        Arc(e), digraph(&_graph) { }
 		      ArcIt& operator++() {
 			digraph->next(*this);
-			return *this;
+		      ArcIt& operator++() {
 		        digraph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class OutArcIt : public Arc {
 		    class OutArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
-			_graph.firstOut(*this, node);
+		      OutArcIt(const Digraph& _graph, const Node& node)
 		        : digraph(&_graph) {
 		        _graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 			: Arc(arc), digraph(&_graph) {}
 		      OutArcIt(const Digraph& _graph, const Arc& arc)
 		        : Arc(arc), digraph(&_graph) {}
 		      OutArcIt& operator++() {
 			digraph->nextOut(*this);
-			return *this;
+		      OutArcIt& operator++() {
 		        digraph->nextOut(*this);
 		        return *this;
+		      }
 		    };
-		    class InArcIt : public Arc {
 		    class InArcIt : public Arc {
 		      const Digraph* digraph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Digraph& _graph, const Node& node)
 			: digraph(&_graph) {
-			_graph.firstIn(*this, node);
+		      InArcIt(const Digraph& _graph, const Node& node)
 		        : digraph(&_graph) {
 		        _graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 			Arc(arc), digraph(&_graph) {}
 		      InArcIt(const Digraph& _graph, const Arc& arc) :
 		        Arc(arc), digraph(&_graph) {}
 		      InArcIt& operator++() {
 			digraph->nextIn(*this);
-			return *this;
+		      InArcIt& operator++() {
 		        digraph->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the target in this case) of the
 		    // iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the source in this case) of the
 		    // iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    using Parent::first;
 		    // Mappable extension
 		    template <typename _Value>
-		    class ArcMap
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
 		    public:
 		      explicit ArcMap(const Digraph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      explicit ArcMap(const Digraph& _g)
 		        : Parent(_g) {}
 		      ArcMap(const Digraph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
-			return operator=<ArcMap>(cmap);
+		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Arc addArc(const Node& from, const Node& to) {
 		      Arc arc = Parent::addArc(from, to);
 		      notifier(Arc()).add(arc);
 		      return arc;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Arc& arc) {
 		      notifier(Arc()).erase(arc);
 		      Parent::erase(arc);
+		    }
 		    ArcSetExtender() {
 		      arc_notifier.setContainer(*this);
+		    }
 		    ~ArcSetExtender() {
 		      arc_notifier.clear();
+		    }
 		  };
 		  // \ingroup digraphbits
 		  //
 		  // \brief Extender for the EdgeSets
@@ -289,337 +289,337 @@
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
-			return Parent::v(e);
+		        return Parent::v(e);
 		      else if( n == Parent::v(e))
-			return Parent::u(e);
+		        return Parent::u(e);
 		      else
-			return INVALID;
+		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &e) const {
 		      return Parent::direct(e, !Parent::direction(e));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
 		    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
 		  protected:
 		    mutable ArcNotifier arc_notifier;
 		    mutable EdgeNotifier edge_notifier;
 		  public:
 		    using Parent::notifier;
 		    ArcNotifier& notifier(Arc) const {
 		      return arc_notifier;
+		    }
 		    EdgeNotifier& notifier(Edge) const {
 		      return edge_notifier;
+		    }
-		    class NodeIt : public Node {
 		    class NodeIt : public Node {
 		      const Graph* graph;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Node&>(*this));
+		        _graph.first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Graph& _graph, const Node& node)
 			: Node(node), graph(&_graph) {}
 		      NodeIt(const Graph& _graph, const Node& node)
 		        : Node(node), graph(&_graph) {}
 		      NodeIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      NodeIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class ArcIt : public Arc {
 		    class ArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Arc&>(*this));
+		        _graph.first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Graph& _graph, const Arc& e) :
 			Arc(e), graph(&_graph) { }
 		      ArcIt(const Graph& _graph, const Arc& e) :
 		        Arc(e), graph(&_graph) { }
 		      ArcIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      ArcIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
-		    class OutArcIt : public Arc {
 		    class OutArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Graph& _graph, const Node& node)
 			: graph(&_graph) {
-			_graph.firstOut(*this, node);
+		      OutArcIt(const Graph& _graph, const Node& node)
 		        : graph(&_graph) {
 		        _graph.firstOut(*this, node);
+		      }
 		      OutArcIt(const Graph& _graph, const Arc& arc)
 			: Arc(arc), graph(&_graph) {}
 		      OutArcIt(const Graph& _graph, const Arc& arc)
 		        : Arc(arc), graph(&_graph) {}
 		      OutArcIt& operator++() {
 			graph->nextOut(*this);
-			return *this;
+		      OutArcIt& operator++() {
 		        graph->nextOut(*this);
 		        return *this;
+		      }
 		    };
-		    class InArcIt : public Arc {
 		    class InArcIt : public Arc {
 		      const Graph* graph;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Graph& _graph, const Node& node)
 			: graph(&_graph) {
-			_graph.firstIn(*this, node);
+		      InArcIt(const Graph& _graph, const Node& node)
 		        : graph(&_graph) {
 		        _graph.firstIn(*this, node);
+		      }
 		      InArcIt(const Graph& _graph, const Arc& arc) :
 			Arc(arc), graph(&_graph) {}
 		      InArcIt(const Graph& _graph, const Arc& arc) :
 		        Arc(arc), graph(&_graph) {}
 		      InArcIt& operator++() {
 			graph->nextIn(*this);
-			return *this;
+		      InArcIt& operator++() {
 		        graph->nextIn(*this);
 		        return *this;
+		      }
 		    };
-		    class EdgeIt : public Parent::Edge {
 		    class EdgeIt : public Parent::Edge {
 		      const Graph* graph;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
-			_graph.first(static_cast<Edge&>(*this));
+		        _graph.first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Graph& _graph, const Edge& e) :
 			Edge(e), graph(&_graph) { }
 		      EdgeIt(const Graph& _graph, const Edge& e) :
 		        Edge(e), graph(&_graph) { }
 		      EdgeIt& operator++() {
 			graph->next(*this);
-			return *this;
+		      EdgeIt& operator++() {
 		        graph->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Parent::Edge {
 		      friend class EdgeSetExtender;
 		      const Graph* graph;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
-			_graph.firstInc(*this, direction, n);
+		        _graph.firstInc(*this, direction, n);
+		      }
 		      IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
 			: graph(&_graph), Edge(ue) {
 			direction = (_graph.source(ue) == n);
 		        : graph(&_graph), Edge(ue) {
 		        direction = (_graph.source(ue) == n);
+		      }
 		      IncEdgeIt& operator++() {
 			graph->nextInc(*this, direction);
 			return *this;
 		        graph->nextInc(*this, direction);
 		        return *this;
+		      }
 		    };
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the source in this case) of the iterator
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the target in this case) of the
 		    // iterator
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    // \brief Base node of the iterator
 		    //
 		    // Returns the base node (ie. the target in this case) of the iterator
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(static_cast<const Arc&>(e));
+		    }
 		    // \brief Running node of the iterator
 		    //
 		    // Returns the running node (ie. the source in this case) of the
 		    // iterator
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(static_cast<const Arc&>(e));
+		    }
 		    // Base node of the iterator
 		    //
 		    // Returns the base node of the iterator
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? u(e) : v(e);
+		    }
 		    // Running node of the iterator
 		    //
 		    // Returns the running node of the iterator
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? v(e) : u(e);
+		    }
 		    template <typename _Value>
-		    class ArcMap
 		    class ArcMap
 		      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
 		    public:
 		      explicit ArcMap(const Graph& _g)
 			: Parent(_g) {}
 		      ArcMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      explicit ArcMap(const Graph& _g)
 		        : Parent(_g) {}
 		      ArcMap(const Graph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      ArcMap& operator=(const ArcMap& cmap) {
-			return operator=<ArcMap>(cmap);
+		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    template <typename _Value>
-		    class EdgeMap
 		    class EdgeMap
 		      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
 		      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
 		    public:
 		      explicit EdgeMap(const Graph& _g)
 			: Parent(_g) {}
 		      explicit EdgeMap(const Graph& _g)
 		        : Parent(_g) {}
 		      EdgeMap(const Graph& _g, const _Value& _v)
 			: Parent(_g, _v) {}
 		      EdgeMap(const Graph& _g, const _Value& _v)
 		        : Parent(_g, _v) {}
 		      EdgeMap& operator=(const EdgeMap& cmap) {
-			return operator=<EdgeMap>(cmap);
+		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
-			return *this;
+		        return *this;
+		      }
 		    };
 		    // Alteration extension
 		    Edge addEdge(const Node& from, const Node& to) {
 		      Edge edge = Parent::addEdge(from, to);
 		      notifier(Edge()).add(edge);
 		      std::vector<Arc> arcs;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).add(arcs);
 		      return edge;
+		    }
 		    void clear() {
 		      notifier(Arc()).clear();
 		      notifier(Edge()).clear();
 		      Parent::clear();
+		    }
 		    void erase(const Edge& edge) {
 		      std::vector<Arc> arcs;
 		      arcs.push_back(Parent::direct(edge, true));
 		      arcs.push_back(Parent::direct(edge, false));
 		      notifier(Arc()).erase(arcs);
 		      notifier(Edge()).erase(edge);
 		      Parent::erase(edge);
+		    }
 		    EdgeSetExtender() {
 		      arc_notifier.setContainer(*this);
 		      edge_notifier.setContainer(*this);
+		    }
 		    ~EdgeSetExtender() {
 		      edge_notifier.clear();
 		      arc_notifier.clear();
+		    }
 		  };
+		}
 		#endif

lemon/bits/solver_bits.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-2008
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_SOLVER_BITS_H
 		#define LEMON_BITS_SOLVER_BITS_H
 		#include <vector>
 		namespace lemon {
 		  namespace _solver_bits {
 		    class VarIndex {
 		    private:

lemon/bits/windows.cc

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\file
 		///\brief Some basic non-inline functions and static global data.
 		#include<lemon/bits/windows.h>
 		#ifdef WIN32
 		#ifndef WIN32_LEAN_AND_MEAN
 		#define WIN32_LEAN_AND_MEAN
 		#endif
 		#ifndef NOMINMAX
 		#define NOMINMAX
@@ -75,49 +75,49 @@
 		        cstime = 0;
+		      }
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      rtime=tv.tv_sec+double(tv.tv_usec)/1e6;
 		      tms ts;
 		      double tck=sysconf(_SC_CLK_TCK);
 		      times(&ts);
 		      utime=ts.tms_utime/tck;
 		      stime=ts.tms_stime/tck;
 		      cutime=ts.tms_cutime/tck;
 		      cstime=ts.tms_cstime/tck;
 		#endif
+		    }
 		    std::string getWinFormattedDate()
+		    {
 		      std::ostringstream os;
 		#ifdef WIN32
 		      SYSTEMTIME time;
 		      GetSystemTime(&time);
 		      char buf1[11], buf2[9], buf3[5];
-			  if (GetDateFormat(MY_LOCALE, 0, &time,
+		          if (GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("ddd MMM dd"), buf1, 11) &&
 		          GetTimeFormat(MY_LOCALE, 0, &time,
 		                        ("HH':'mm':'ss"), buf2, 9) &&
 		          GetDateFormat(MY_LOCALE, 0, &time,
 		                        ("yyyy"), buf3, 5)) {
 		        os << buf1 << ' ' << buf2 << ' ' << buf3;
+		      }
 		      else os << "unknown";
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      char cbuf[26];
 		      ctime_r(&tv.tv_sec,cbuf);
 		      os << cbuf;
 		#endif
 		      return os.str();
+		    }
 		    int getWinRndSeed()
+		    {
 		#ifdef WIN32
 		      FILETIME time;
 		      GetSystemTimeAsFileTime(&time);

lemon/bucket_heap.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BUCKET_HEAP_H
 		#define LEMON_BUCKET_HEAP_H
 		///\ingroup heaps
 		///\file
 		///\brief Bucket heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
@@ -363,49 +363,49 @@
 		      int prev, next;
 		    };
 		    ItemIntMap& _iim;
 		    std::vector<int> _first;
 		    std::vector<BucketItem> _data;
 		    mutable int _minimum;
 		  }; // class BucketHeap
 		  /// \ingroup heaps
 		  ///
 		  /// \brief Simplified bucket heap data structure.
 		  ///
 		  /// This class implements a simplified \e bucket \e heap data
 		  /// structure. It does not provide some functionality, but it is
 		  /// faster and simpler than BucketHeap. The main difference is
 		  /// that BucketHeap stores a doubly-linked list for each key while
 		  /// this class stores only simply-linked lists. It supports erasing
 		  /// only for the item having minimum priority and it does not support
 		  /// key increasing and decreasing.
 		  ///
 		  /// Note that this implementation does not conform to the
-		  /// \ref concepts::Heap "heap concept" due to the lack of some
 		  /// \ref concepts::Heap "heap concept" due to the lack of some
 		  /// functionality.
 		  ///
 		  /// \tparam IM A read-writable item map with \c int values, used
 		  /// internally to handle the cross references.
 		  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
 		  /// The default is \e min-heap. If this parameter is set to \c false,
 		  /// then the comparison is reversed, so the top(), prio() and pop()
 		  /// functions deal with the item having maximum priority instead of the
 		  /// minimum.
 		  ///
 		  /// \sa BucketHeap
 		  template <typename IM, bool MIN = true >
 		  class SimpleBucketHeap {
 		  public:
 		    /// Type of the item-int map.
 		    typedef IM ItemIntMap;
 		    /// Type of the priorities.
 		    typedef int Prio;
 		    /// Type of the items stored in the heap.
 		    typedef typename ItemIntMap::Key Item;
 		    /// Type of the item-priority pairs.
 		    typedef std::pair<Item,Prio> Pair;

lemon/capacity_scaling.h

Show inline comments

 		/* -*- C++ -*-
+		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library
+		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2008
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CAPACITY_SCALING_H
 		#define LEMON_CAPACITY_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		///
 		/// \file
 		/// \brief Capacity Scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
@@ -112,49 +112,49 @@
 		    /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    // Data structures for storing the digraph
@@ -163,79 +163,79 @@
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _cost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    CostVector _pi;
 		    ValueVector _excess;
 		    IntVector _excess_nodes;
 		    IntVector _deficit_nodes;
 		    Value _delta;
 		    int _factor;
 		    IntVector _pred;
 		  public:
 		    /// \brief Constant for infinite upper bounds (capacities).
 		    ///
 		    /// Constant for infinite upper bounds (capacities).
 		    /// It is \c std::numeric_limits<Value>::infinity() if available,
 		    /// \c std::numeric_limits<Value>::max() otherwise.
 		    const Value INF;
 		  private:
 		    // Special implementation of the Dijkstra algorithm for finding
 		    // shortest paths in the residual network of the digraph with
 		    // respect to the reduced arc costs and modifying the node
 		    // potentials according to the found distance labels.
 		    class ResidualDijkstra
+		    {
 		    private:
 		      int _node_num;
 		      bool _geq;
 		      const IntVector &_first_out;
 		      const IntVector &_target;
 		      const CostVector &_cost;
 		      const ValueVector &_res_cap;
 		      const ValueVector &_excess;
 		      CostVector &_pi;
 		      IntVector &_pred;
 		      IntVector _proc_nodes;
 		      CostVector _dist;
 		    public:
 		      ResidualDijkstra(CapacityScaling& cs) :
 		        _node_num(cs._node_num), _geq(cs._sum_supply < 0),
 		        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
 		        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
 		        _pred(cs._pred), _dist(cs._node_num)
 		      {}
 		      int run(int s, Value delta = 1) {
 		        RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
 		        Heap heap(heap_cross_ref);
 		        heap.push(s, 0);
 		        _pred[s] = -1;
 		        _proc_nodes.clear();
 		        // Process nodes
 		        while (!heap.empty() && _excess[heap.top()] > -delta) {
 		          int u = heap.top(), v;
 		          Cost d = heap.prio() + _pi[u], dn;
 		          _dist[u] = heap.prio();
 		          _proc_nodes.push_back(u);
 		          heap.pop();
@@ -418,49 +418,49 @@
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CapacityScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
@@ -554,93 +554,93 @@
 		    ///
 		    /// See \ref resetParams() for examples.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \see resetParams(), run()
 		    CapacityScaling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      ++_node_num;
 		      _first_out.resize(_node_num + 1);
 		      _forward.resize(_res_arc_num);
 		      _source.resize(_res_arc_num);
 		      _target.resize(_res_arc_num);
 		      _reverse.resize(_res_arc_num);
 		      _lower.resize(_res_arc_num);
 		      _upper.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _supply.resize(_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _pi.resize(_node_num);
 		      _excess.resize(_node_num);
 		      _pred.resize(_node_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _node_id[n] = i;
+		      }
 		      i = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
 		        _first_out[i] = j;
 		        for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idf[a] = j;
 		          _forward[j] = true;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
 		          _arc_idb[a] = j;
 		          _forward[j] = false;
 		          _source[j] = i;
 		          _target[j] = _node_id[_graph.runningNode(a)];
+		        }
 		        _forward[j] = false;
 		        _source[j] = i;
 		        _target[j] = _root;
 		        _reverse[j] = k;
 		        _forward[k] = true;
 		        _source[k] = _root;
 		        _target[k] = i;
 		        _reverse[k] = j;
 		        ++j; ++k;
+		      }
 		      _first_out[i] = j;
 		      _first_out[_node_num] = k;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int fi = _arc_idf[a];
 		        int bi = _arc_idb[a];
 		        _reverse[fi] = bi;
 		        _reverse[bi] = fi;
+		      }
 		      // Reset parameters
 		      resetParams();
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these
 		    /// functions.\n
 		    /// The \ref run() function must be called before using them.
 		    /// @{
 		    /// \brief Return the total cost of the found flow.
 		    ///
 		    /// This function returns the total cost of the found flow.
 		    /// Its complexity is O(e).
 		    ///
 		    /// \note The return type of the function can be specified as a
 		    /// template parameter. For example,
 		    /// \code
 		    ///   cs.totalCost<double>();
 		    /// \endcode
@@ -707,97 +707,97 @@
 		    /// \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename PotentialMap>
 		    void potentialMap(PotentialMap &map) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        map.set(n, _pi[_node_id[n]]);
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize the algorithm
 		    ProblemType init() {
 		      if (_node_num <= 1) return INFEASIBLE;
 		      // Check the sum of supply values
 		      _sum_supply = 0;
 		      for (int i = 0; i != _root; ++i) {
 		        _sum_supply += _supply[i];
+		      }
 		      if (_sum_supply > 0) return INFEASIBLE;
 		      // Initialize vectors
 		      for (int i = 0; i != _root; ++i) {
 		        _pi[i] = 0;
 		        _excess[i] = _supply[i];
+		      }
 		      // Remove non-zero lower bounds
 		      const Value MAX = std::numeric_limits<Value>::max();
 		      int last_out;
 		      if (_have_lower) {
 		        for (int i = 0; i != _root; ++i) {
 		          last_out = _first_out[i+1];
 		          for (int j = _first_out[i]; j != last_out; ++j) {
 		            if (_forward[j]) {
 		              Value c = _lower[j];
 		              if (c >= 0) {
 		                _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
 		              } else {
 		                _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
+		              }
 		              _excess[i] -= c;
 		              _excess[_target[j]] += c;
 		            } else {
 		              _res_cap[j] = 0;
+		            }
+		          }
+		        }
 		      } else {
 		        for (int j = 0; j != _res_arc_num; ++j) {
 		          _res_cap[j] = _forward[j] ? _upper[j] : 0;
+		        }
+		      }
 		      // Handle negative costs
 		      for (int i = 0; i != _root; ++i) {
 		        last_out = _first_out[i+1] - 1;
 		        for (int j = _first_out[i]; j != last_out; ++j) {
 		          Value rc = _res_cap[j];
 		          if (_cost[j] < 0 && rc > 0) {
 		            if (rc >= MAX) return UNBOUNDED;
 		            _excess[i] -= rc;
 		            _excess[_target[j]] += rc;
 		            _res_cap[j] = 0;
 		            _res_cap[_reverse[j]] += rc;
+		          }
+		        }
+		      }
 		      // Handle GEQ supply type
 		      if (_sum_supply < 0) {
 		        _pi[_root] = 0;
 		        _excess[_root] = -_sum_supply;
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
 		          _res_cap[a] = -_sum_supply + 1;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
 		      } else {
 		        _pi[_root] = 0;
 		        _excess[_root] = 0;
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
 		          _res_cap[a] = 1;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
+		      }
 		      // Initialize delta value
@@ -823,51 +823,51 @@
 		      return OPTIMAL;
+		    }
 		    ProblemType start() {
 		      // Execute the algorithm
 		      ProblemType pt;
 		      if (_delta > 1)
 		        pt = startWithScaling();
 		      else
 		        pt = startWithoutScaling();
 		      // Handle non-zero lower bounds
 		      if (_have_lower) {
 		        int limit = _first_out[_root];
 		        for (int j = 0; j != limit; ++j) {
 		          if (!_forward[j]) _res_cap[j] += _lower[j];
+		        }
+		      }
 		      // Shift potentials if necessary
 		      Cost pr = _pi[_root];
 		      if (_sum_supply < 0 || pr > 0) {
 		        for (int i = 0; i != _node_num; ++i) {
 		          _pi[i] -= pr;
+		        }
+		        }
+		      }
 		      return pt;
+		    }
 		    // Execute the capacity scaling algorithm
 		    ProblemType startWithScaling() {
 		      // Perform capacity scaling phases
 		      int s, t;
 		      ResidualDijkstra _dijkstra(*this);
 		      while (true) {
 		        // Saturate all arcs not satisfying the optimality condition
 		        int last_out;
 		        for (int u = 0; u != _node_num; ++u) {
 		          last_out = _sum_supply < 0 ?
 		            _first_out[u+1] : _first_out[u+1] - 1;
 		          for (int a = _first_out[u]; a != last_out; ++a) {
 		            int v = _target[a];
 		            Cost c = _cost[a] + _pi[u] - _pi[v];
 		            Value rc = _res_cap[a];
 		            if (c < 0 && rc >= _delta) {
 		              _excess[u] -= rc;
 		              _excess[v] += rc;
 		              _res_cap[a] = 0;
 		              _res_cap[_reverse[a]] += rc;
+		            }

lemon/cbc.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// -*- C++ -*-
 		#ifndef LEMON_CBC_H
 		#define LEMON_CBC_H
 		///\file
 		///\brief Header of the LEMON-CBC mip solver interface.
 		///\ingroup lp_group
 		#include <lemon/lp_base.h>
 		class CoinModel;
@@ -100,31 +100,31 @@
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
 		    virtual void _getObjCoeffs(InsertIterator b) const;
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual ColTypes _getColType(int col) const;
 		    virtual void _setColType(int col, ColTypes col_type);
 		    virtual SolveExitStatus _solve();
 		    virtual ProblemType _getType() const;
 		    virtual Value _getSol(int i) const;
 		    virtual Value _getSolValue() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel level);
 		    void _applyMessageLevel();
 		    int _message_level;
 		  };
+		}
 		#endif

lemon/circulation.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CIRCULATION_H
 		#define LEMON_CIRCULATION_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		#include <limits>
 		///\ingroup max_flow
 		///\file
 		///\brief Push-relabel algorithm for finding a feasible circulation.
 		///
@@ -38,50 +38,50 @@
 		  /// \tparam UM The type of the upper bound (capacity) map.
 		  /// \tparam SM The type of the supply map.
 		  template <typename GR, typename LM,
 		            typename UM, typename SM>
 		  struct CirculationDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the lower bound map.
 		    ///
 		    /// The type of the map that stores the lower bounds on the arcs.
 		    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef LM LowerMap;
 		    /// \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.
 		    /// 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);
@@ -120,59 +120,59 @@
 		     \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>".
 		     \tparam TR The traits class that defines various types used by the
 		     algorithm. By default, it is \ref CirculationDefaultTraits
 		     "CirculationDefaultTraits<GR, LM, UM, SM>".
@@ -316,49 +316,49 @@
 		    /// 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
 		    /// \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() {

lemon/clp.cc

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/clp.h>
#include <coin/ClpSimplex.hpp>

namespace lemon {

  ClpLp::ClpLp() {
    _prob = new ClpSimplex();
    _init_temporals();
    messageLevel(MESSAGE_NOTHING);
  }


lemon/clp.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-2008
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CLP_H
 		#define LEMON_CLP_H
 		///\file
 		///\brief Header of the LEMON-CLP lp solver interface.
 		#include <vector>
 		#include <string>
 		#include <lemon/lp_base.h>
@@ -117,48 +117,48 @@
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel);
 		  public:
 		    ///Solves LP with primal simplex method.
 		    SolveExitStatus solvePrimal();
 		    ///Solves LP with dual simplex method.
 		    SolveExitStatus solveDual();
 		    ///Solves LP with barrier method.
 		    SolveExitStatus solveBarrier();
 		    ///Returns the constraint identifier understood by CLP.
 		    int clpRow(Row r) const { return rows(id(r)); }
 		    ///Returns the variable identifier understood by CLP.
 		    int clpCol(Col c) const { return cols(id(c)); }
 		  };
 		} //END OF NAMESPACE LEMON
 		#endif //LEMON_CLP_H

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_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>
@@ -413,49 +413,49 @@
 		      /// (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) :
 		        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

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup 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.
 		    /// \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.
@@ -339,49 +339,49 @@
 		        /// \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
 		      /// 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.

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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\ingroup graph_concepts
 		///\file
 		///\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
 		    /// 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.
@@ -68,82 +68,82 @@
 		      /// \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
 		      /// 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
 		    /// 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.
@@ -405,156 +405,156 @@
 		      ///
 		      /// This function returns an integer greater or equal to the
 		      /// maximum edge id.
 		      int maxEdgeId() const { return -1; }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<IDableDigraphComponent<Base>, _Graph >();
 		          typename _Graph::Edge edge;
 		          int ueid = graph.id(edge);
 		          ueid = graph.id(edge);
 		          edge = graph.edgeFromId(ueid);
 		          ueid = graph.maxEdgeId();
 		          ignore_unused_variable_warning(ueid);
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
 		    ///
-		    /// This class describes the concept of \c NodeIt, \c ArcIt and
 		    /// This class describes the concept of \c NodeIt, \c ArcIt and
 		    /// \c EdgeIt subtypes of digraph and graph types.
 		    template <typename GR, typename Item>
 		    class GraphItemIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the iterator to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphItemIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphItemIt(const GraphItemIt& it) : Item(it) {}
 		      /// \brief Constructor that sets the iterator to the first item.
 		      ///
 		      /// Constructor that sets the iterator to the first item.
 		      explicit GraphItemIt(const GR&) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphItemIt(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the iterator.
 		      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next item.
 		      GraphItemIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator==(const GraphItemIt&) const { return true;}
 		      /// \brief Inequality operator
 		      ///
 		      /// Inequality operator.
 		      /// Two iterators are equal if and only if they point to the
 		      /// same object or both are invalid.
 		      bool operator!=(const GraphItemIt&) const { return true;}
 		      template<typename _GraphItemIt>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<GraphItem<>, _GraphItemIt>();
 		          _GraphItemIt it1(g);
 		          _GraphItemIt it2;
 		          _GraphItemIt it3 = it1;
 		          _GraphItemIt it4 = INVALID;
 		          it2 = ++it1;
 		          ++it2 = it1;
 		          ++(++it1);
 		          Item bi = it1;
 		          bi = it2;
+		        }
 		        const GR& g;
 		      };
 		    };
-		    /// \brief Concept class for \c InArcIt, \c OutArcIt and
 		    /// \brief Concept class for \c InArcIt, \c OutArcIt and
 		    /// \c IncEdgeIt types.
 		    ///
-		    /// This class describes the concept of \c InArcIt, \c OutArcIt
 		    /// This class describes the concept of \c InArcIt, \c OutArcIt
 		    /// and \c IncEdgeIt subtypes of digraph and graph types.
 		    ///
 		    /// \note Since these iterator classes do not inherit from the same
 		    /// base class, there is an additional template parameter (selector)
-		    /// \c sel. For \c InArcIt you should instantiate it with character
 		    /// \c sel. For \c InArcIt you should instantiate it with character
 		    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
 		    template <typename GR,
 		              typename Item = typename GR::Arc,
 		              typename Base = typename GR::Node,
 		              char sel = '0'>
 		    class GraphIncIt : public Item {
 		    public:
 		      /// \brief Default constructor.
 		      ///
 		      /// Default constructor.
 		      /// \warning The default constructor is not required to set
 		      /// the iterator to some well-defined value. So you should consider it
 		      /// as uninitialized.
 		      GraphIncIt() {}
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy constructor.
 		      GraphIncIt(const GraphIncIt& it) : Item(it) {}
-		      /// \brief Constructor that sets the iterator to the first
 		      /// \brief Constructor that sets the iterator to the first
 		      /// incoming or outgoing arc.
 		      ///
-		      /// Constructor that sets the iterator to the first arc
 		      /// Constructor that sets the iterator to the first arc
 		      /// incoming to or outgoing from the given node.
 		      explicit GraphIncIt(const GR&, const Base&) {}
 		      /// \brief Constructor for conversion from \c INVALID.
 		      ///
 		      /// Constructor for conversion from \c INVALID.
 		      /// It initializes the iterator to be invalid.
 		      /// \sa Invalid for more details.
 		      GraphIncIt(Invalid) {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator for the iterator.
 		      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
 		      /// \brief Increment the iterator.
 		      ///
 		      /// This operator increments the iterator, i.e. assigns it to the
 		      /// next arc incoming to or outgoing from the given node.
 		      GraphIncIt& operator++() { return *this; }
 		      /// \brief Equality operator
 		      ///
 		      /// Equality operator.
@@ -783,58 +783,58 @@
 		      typedef IterableGraphComponent Graph;
 		      /// \name Base Iteration
 		      ///
 		      /// This interface provides functions for iteration on edges.
 		      ///
 		      /// @{
 		      using IterableDigraphComponent<Base>::first;
 		      using IterableDigraphComponent<Base>::next;
 		      /// \brief Return the first edge.
 		      ///
 		      /// This function gives back the first edge in the iteration order.
 		      void first(Edge&) const {}
 		      /// \brief Return the next edge.
 		      ///
 		      /// This function gives back the next edge in the iteration order.
 		      void next(Edge&) const {}
 		      /// \brief Return the first edge incident to the given node.
 		      ///
-		      /// This function gives back the first edge incident to the given
 		      /// This function gives back the first edge incident to the given
 		      /// node. The bool parameter gives back the direction for which the
-		      /// source node of the directed arc representing the edge is the
 		      /// source node of the directed arc representing the edge is the
 		      /// given node.
 		      void firstInc(Edge&, bool&, const Node&) const {}
 		      /// \brief Gives back the next of the edges from the
 		      /// given node.
 		      ///
-		      /// This function gives back the next edge incident to the given
 		      /// This function gives back the next edge incident to the given
 		      /// node. The bool parameter should be used as \c firstInc() use it.
 		      void nextInc(Edge&, bool&) const {}
 		      using IterableDigraphComponent<Base>::baseNode;
 		      using IterableDigraphComponent<Base>::runningNode;
 		      /// @}
 		      /// \name Class Based Iteration
 		      ///
 		      /// This interface provides iterator classes for edges.
 		      ///
 		      /// @{
 		      /// \brief This iterator goes through each edge.
 		      ///
 		      /// This iterator goes through each edge.
 		      typedef GraphItemIt<Graph, Edge> EdgeIt;
 		      /// \brief This iterator goes trough the incident edges of a
 		      /// node.
 		      ///
 		      /// This iterator goes trough the incident edges of a certain
 		      /// node of a graph.
@@ -969,49 +969,49 @@
 		      /// \brief Return the edge alteration notifier.
 		      ///
 		      /// This function gives back the edge alteration notifier.
 		      EdgeNotifier& notifier(Edge) const {
 		        return EdgeNotifier();
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
 		          typename _Graph::EdgeNotifier& uen
 		            = graph.notifier(typename _Graph::Edge());
 		          ignore_unused_variable_warning(uen);
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Concept class for standard graph maps.
 		    ///
 		    /// This class describes the concept of standard graph maps, i.e.
-		    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 		    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
 		    /// graph types, which can be used for associating data to graph items.
 		    /// The standard graph maps must conform to the ReferenceMap concept.
 		    template <typename GR, typename K, typename V>
 		    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
 		      typedef ReferenceMap<K, V, V&, const V&> Parent;
 		    public:
 		      /// The key type of the map.
 		      typedef K Key;
 		      /// The value type of the map.
 		      typedef V Value;
 		      /// The reference type of the map.
 		      typedef Value& Reference;
 		      /// The const reference type of the map.
 		      typedef const Value& ConstReference;
 		      // The reference map tag.
 		      typedef True ReferenceMapTag;
 		      /// \brief Construct a new map.
 		      ///
 		      /// Construct a new map for the graph.
 		      explicit GraphMap(const GR&) {}
@@ -1024,72 +1024,72 @@
 		      /// \brief Copy constructor.
 		      ///
 		      /// Copy Constructor.
 		      GraphMap(const GraphMap&) : Parent() {}
 		      /// \brief Assignment operator.
 		      ///
 		      /// Assignment operator. It does not mofify the underlying graph,
 		      /// it just iterates on the current item set and set the  map
 		      /// with the value returned by the assigned map.
 		      template <typename CMap>
 		      GraphMap& operator=(const CMap&) {
 		        checkConcept<ReadMap<Key, Value>, CMap>();
 		        return *this;
+		      }
 		    public:
 		      template<typename _Map>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept
 		            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
 		          _Map m1(g);
 		          _Map m2(g,t);
 		          // Copy constructor
 		          // _Map m3(m);
 		          // Assignment operator
 		          // ReadMap<Key, Value> cmap;
 		          // m3 = cmap;
 		          ignore_unused_variable_warning(m1);
 		          ignore_unused_variable_warning(m2);
 		          // ignore_unused_variable_warning(m3);
+		        }
 		        const _Map &m;
 		        const GR &g;
 		        const typename GraphMap::Value &t;
 		      };
 		    };
 		    /// \brief Skeleton class for mappable directed graphs.
 		    ///
 		    /// This class describes the interface of mappable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with the standard digraph
 		    /// It extends \ref BaseDigraphComponent with the standard digraph
 		    /// map classes, namely \c NodeMap and \c ArcMap.
 		    /// This concept is part of the Digraph concept.
 		    template <typename BAS = BaseDigraphComponent>
 		    class MappableDigraphComponent : public BAS  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      typedef MappableDigraphComponent Digraph;
 		      /// \brief Standard graph map for the nodes.
 		      ///
 		      /// Standard graph map for the nodes.
 		      /// It conforms to the ReferenceMap concept.
 		      template <typename V>
 		      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
 		        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
 		      public:
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the digraph.
@@ -1184,49 +1184,49 @@
+		          }
 		          { // int map test
 		            typedef typename _Digraph::template ArcMap<int> IntArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
 		              IntArcMap >();
 		          } { // bool map test
 		            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
 		              BoolArcMap >();
 		          } { // Dummy map test
 		            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
 		            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
 		              DummyArcMap >();
+		          }
+		        }
 		        const _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for mappable undirected graphs.
 		    ///
 		    /// This class describes the interface of mappable undirected graphs.
-		    /// It extends \ref MappableDigraphComponent with the standard graph
 		    /// It extends \ref MappableDigraphComponent with the standard graph
 		    /// map class for edges (\c EdgeMap).
 		    /// This concept is part of the Graph concept.
 		    template <typename BAS = BaseGraphComponent>
 		    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Edge Edge;
 		      typedef MappableGraphComponent Graph;
 		      /// \brief Standard graph map for the edges.
 		      ///
 		      /// Standard graph map for the edges.
 		      /// It conforms to the ReferenceMap concept.
 		      template <typename V>
 		      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
 		        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
 		      public:
 		        /// \brief Construct a new map.
 		        ///
 		        /// Construct a new map for the graph.
 		        explicit EdgeMap(const MappableGraphComponent& graph)
@@ -1269,176 +1269,176 @@
 		          checkConcept<MappableDigraphComponent<Base>, _Graph>();
 		          { // int map test
 		            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
 		              IntEdgeMap >();
 		          } { // bool map test
 		            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
 		              BoolEdgeMap >();
 		          } { // Dummy map test
 		            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
 		            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
 		              DummyEdgeMap >();
+		          }
+		        }
 		        const _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for extendable directed graphs.
 		    ///
 		    /// This class describes the interface of extendable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with functions for adding
 		    /// It extends \ref BaseDigraphComponent with functions for adding
 		    /// nodes and arcs to the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ExtendableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Add a new node to the digraph.
 		      ///
 		      /// This function adds a new node to the digraph.
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Add a new arc connecting the given two nodes.
 		      ///
 		      /// This function adds a new arc connecting the given two nodes
 		      /// of the digraph.
 		      Arc addArc(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          typename _Digraph::Node node_a, node_b;
 		          node_a = digraph.addNode();
 		          node_b = digraph.addNode();
 		          typename _Digraph::Arc arc;
 		          arc = digraph.addArc(node_a, node_b);
+		        }
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for extendable undirected graphs.
 		    ///
 		    /// This class describes the interface of extendable undirected graphs.
-		    /// It extends \ref BaseGraphComponent with functions for adding
 		    /// It extends \ref BaseGraphComponent with functions for adding
 		    /// nodes and edges to the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ExtendableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Add a new node to the digraph.
 		      ///
 		      /// This function adds a new node to the digraph.
 		      Node addNode() {
 		        return INVALID;
+		      }
 		      /// \brief Add a new edge connecting the given two nodes.
 		      ///
 		      /// This function adds a new edge connecting the given two nodes
 		      /// of the graph.
 		      Edge addEdge(const Node&, const Node&) {
 		        return INVALID;
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Graph>();
 		          typename _Graph::Node node_a, node_b;
 		          node_a = graph.addNode();
 		          node_b = graph.addNode();
 		          typename _Graph::Edge edge;
 		          edge = graph.addEdge(node_a, node_b);
+		        }
 		        _Graph& graph;
 		      };
 		    };
 		    /// \brief Skeleton class for erasable directed graphs.
 		    ///
 		    /// This class describes the interface of erasable directed graphs.
-		    /// It extends \ref BaseDigraphComponent with functions for removing
 		    /// It extends \ref BaseDigraphComponent with functions for removing
 		    /// nodes and arcs from the digraph.
 		    /// This concept requires \ref AlterableDigraphComponent.
 		    template <typename BAS = BaseDigraphComponent>
 		    class ErasableDigraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Arc Arc;
 		      /// \brief Erase a node from the digraph.
 		      ///
-		      /// This function erases the given node from the digraph and all arcs
 		      /// This function erases the given node from the digraph and all arcs
 		      /// connected to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an arc from the digraph.
 		      ///
 		      /// This function erases the given arc from the digraph.
 		      void erase(const Arc&) {}
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<Base, _Digraph>();
 		          const typename _Digraph::Node node(INVALID);
 		          digraph.erase(node);
 		          const typename _Digraph::Arc arc(INVALID);
 		          digraph.erase(arc);
+		        }
 		        _Digraph& digraph;
 		      };
 		    };
 		    /// \brief Skeleton class for erasable undirected graphs.
 		    ///
 		    /// This class describes the interface of erasable undirected graphs.
-		    /// It extends \ref BaseGraphComponent with functions for removing
 		    /// It extends \ref BaseGraphComponent with functions for removing
 		    /// nodes and edges from the graph.
 		    /// This concept requires \ref AlterableGraphComponent.
 		    template <typename BAS = BaseGraphComponent>
 		    class ErasableGraphComponent : public BAS {
 		    public:
 		      typedef BAS Base;
 		      typedef typename Base::Node Node;
 		      typedef typename Base::Edge Edge;
 		      /// \brief Erase a node from the graph.
 		      ///
 		      /// This function erases the given node from the graph and all edges
 		      /// connected to the node.
 		      void erase(const Node&) {}
 		      /// \brief Erase an edge from the digraph.
 		      ///
 		      /// This function erases the given edge from the digraph.
 		      void erase(const Edge&) {}
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {

lemon/concepts/heap.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONCEPTS_HEAP_H
 		#define LEMON_CONCEPTS_HEAP_H
 		///\ingroup concept
 		///\file
 		///\brief The concept of heaps.
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
@@ -71,202 +71,202 @@
 		      ///
 		      /// Each item has a state associated to it. It can be "in heap",
 		      /// "pre-heap" or "post-heap". The latter two are indifferent from the
 		      /// heap's point of view, but may be useful to the user.
 		      ///
 		      /// The item-int map must be initialized in such way that it assigns
 		      /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
 		      enum State {
 		        IN_HEAP = 0,    ///< = 0. The "in heap" state constant.
 		        PRE_HEAP = -1,  ///< = -1. The "pre-heap" state constant.
 		        POST_HEAP = -2  ///< = -2. The "post-heap" state constant.
 		      };
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		#ifdef DOXYGEN
 		      explicit Heap(ItemIntMap &map) {}
 		#else
 		      explicit Heap(ItemIntMap&) {}
-		#endif
 		#endif
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor.
 		      /// \param map A map that assigns \c int values to keys of type
 		      /// \c Item. It is used internally by the heap implementations to
 		      /// handle the cross references. The assigned value must be
 		      /// \c PRE_HEAP (<tt>-1</tt>) for each item.
 		      /// \param comp The function object used for comparing the priorities.
 		#ifdef DOXYGEN
 		      explicit Heap(ItemIntMap &map, const CMP &comp) {}
 		#else
 		      explicit Heap(ItemIntMap&, const CMP&) {}
-		#endif
 		#endif
 		      /// \brief The number of items stored in the heap.
 		      ///
 		      /// This function returns the number of items stored in the heap.
 		      int size() const { return 0; }
 		      /// \brief Check if the heap is empty.
 		      ///
 		      /// This function returns \c true if the heap is empty.
 		      bool empty() const { return false; }
 		      /// \brief Make the heap empty.
 		      ///
 		      /// This functon makes the heap empty.
 		      /// It does not change the cross reference map. If you want to reuse
 		      /// a heap that is not surely empty, you should first clear it and
 		      /// then you should set the cross reference map to \c PRE_HEAP
 		      /// for each item.
 		      void clear() {}
 		      /// \brief Insert an item into the heap with the given priority.
 		      ///
 		      /// This function inserts the given item into the heap with the
 		      /// given priority.
 		      /// \param i The item to insert.
 		      /// \param p The priority of the item.
 		      /// \pre \e i must not be stored in the heap.
 		#ifdef DOXYGEN
 		      void push(const Item &i, const Prio &p) {}
 		#else
 		      void push(const Item&, const Prio&) {}
-		#endif
 		#endif
 		      /// \brief Return the item having minimum priority.
 		      ///
 		      /// This function returns the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Item top() const { return Item(); }
 		      /// \brief The minimum priority.
 		      ///
 		      /// This function returns the minimum priority.
 		      /// \pre The heap must be non-empty.
 		      Prio prio() const { return Prio(); }
 		      /// \brief Remove the item having minimum priority.
 		      ///
 		      /// This function removes the item having minimum priority.
 		      /// \pre The heap must be non-empty.
 		      void pop() {}
 		      /// \brief Remove the given item from the heap.
 		      ///
 		      /// This function removes the given item from the heap if it is
 		      /// already stored.
 		      /// \param i The item to delete.
 		      /// \pre \e i must be in the heap.
 		#ifdef DOXYGEN
 		      void erase(const Item &i) {}
 		#else
 		      void erase(const Item&) {}
-		#endif
 		#endif
 		      /// \brief The priority of the given item.
 		      ///
 		      /// This function returns the priority of the given item.
 		      /// \param i The item.
 		      /// \pre \e i must be in the heap.
 		#ifdef DOXYGEN
 		      Prio operator[](const Item &i) const {}
 		#else
 		      Prio operator[](const Item&) const { return Prio(); }
-		#endif
 		#endif
 		      /// \brief Set the priority of an item or insert it, if it is
 		      /// not stored in the heap.
 		      ///
 		      /// This method sets the priority of the given item if it is
 		      /// already stored in the heap. Otherwise it inserts the given
 		      /// item into the heap with the given priority.
 		      ///
 		      /// \param i The item.
 		      /// \param p The priority.
 		#ifdef DOXYGEN
 		      void set(const Item &i, const Prio &p) {}
 		#else
 		      void set(const Item&, const Prio&) {}
-		#endif
 		#endif
 		      /// \brief Decrease the priority of an item to the given value.
 		      ///
 		      /// This function decreases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at least \e p.
 		#ifdef DOXYGEN
 		      void decrease(const Item &i, const Prio &p) {}
 		#else
 		      void decrease(const Item&, const Prio&) {}
-		#endif
 		#endif
 		      /// \brief Increase the priority of an item to the given value.
 		      ///
 		      /// This function increases the priority of an item to the given value.
 		      /// \param i The item.
 		      /// \param p The priority.
 		      /// \pre \e i must be stored in the heap with priority at most \e p.
 		#ifdef DOXYGEN
 		      void increase(const Item &i, const Prio &p) {}
 		#else
 		      void increase(const Item&, const Prio&) {}
-		#endif
 		#endif
 		      /// \brief Return the state of an item.
 		      ///
 		      /// This method returns \c PRE_HEAP if the given item has never
 		      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
 		      /// and \c POST_HEAP otherwise.
 		      /// In the latter case it is possible that the item will get back
 		      /// to the heap again.
 		      /// \param i The item.
 		#ifdef DOXYGEN
 		      State state(const Item &i) const {}
 		#else
 		      State state(const Item&) const { return PRE_HEAP; }
-		#endif
 		#endif
 		      /// \brief Set the state of an item in the heap.
 		      ///
 		      /// This function sets the state of the given item in the heap.
 		      /// It can be used to manually clear the heap when it is important
 		      /// to achive better time complexity.
 		      /// \param i The item.
 		      /// \param st The state. It should not be \c IN_HEAP.
 		#ifdef DOXYGEN
 		      void state(const Item& i, State st) {}
 		#else
 		      void state(const Item&, State) {}
-		#endif
 		#endif
 		      template <typename _Heap>
 		      struct Constraints {
 		      public:
 		        void constraints() {
 		          typedef typename _Heap::Item OwnItem;
 		          typedef typename _Heap::Prio OwnPrio;
 		          typedef typename _Heap::State OwnState;
 		          Item item;
 		          Prio prio;
 		          item=Item();
 		          prio=Prio();
 		          ignore_unused_variable_warning(item);
 		          ignore_unused_variable_warning(prio);
 		          OwnItem own_item;
 		          OwnPrio own_prio;
 		          OwnState own_state;
 		          own_item=Item();
 		          own_prio=Prio();
 		          ignore_unused_variable_warning(own_item);
 		          ignore_unused_variable_warning(own_prio);

lemon/connectivity.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CONNECTIVITY_H
 		#define LEMON_CONNECTIVITY_H
 		#include <lemon/dfs.h>
 		#include <lemon/bfs.h>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
@@ -237,49 +237,49 @@
+		         }
+		      }
 		    private:
 		      const Digraph& _digraph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _compMap;
 		      int _num;
 		    };
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether a directed graph is strongly connected.
 		  ///
 		  /// This function checks whether the given directed graph is strongly
 		  /// connected, i.e. any two nodes of the digraph are
 		  /// connected with directed paths in both direction.
 		  ///
 		  /// \return \c true if the digraph is strongly connected.
 		  /// \note By definition, the empty digraph is strongly connected.
-		  ///
 		  ///
 		  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()
 		  /// \see connected()
 		  template <typename Digraph>
 		  bool stronglyConnected(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typename Digraph::Node source = NodeIt(digraph);
 		    if (source == INVALID) return true;
 		    using namespace _connectivity_bits;
 		    typedef DfsVisitor<Digraph> Visitor;
 		    Visitor visitor;
 		    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);
 		    dfs.init();
 		    dfs.addSource(source);
 		    dfs.start();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
@@ -289,49 +289,49 @@
 		    typedef ReverseDigraph<const Digraph> RDigraph;
 		    typedef typename RDigraph::NodeIt RNodeIt;
 		    RDigraph rdigraph(digraph);
 		    typedef DfsVisitor<RDigraph> RVisitor;
 		    RVisitor rvisitor;
 		    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);
 		    rdfs.init();
 		    rdfs.addSource(source);
 		    rdfs.start();
 		    for (RNodeIt it(rdigraph); it != INVALID; ++it) {
 		      if (!rdfs.reached(it)) {
 		        return false;
+		      }
+		    }
 		    return true;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the number of strongly connected components of a
 		  /// \brief Count the number of strongly connected components of a
 		  /// directed graph
 		  ///
 		  /// This function counts the number of strongly connected components of
 		  /// the given directed graph.
 		  ///
 		  /// The strongly connected components are the classes of an
 		  /// equivalence relation on the nodes of a digraph. Two nodes are in
 		  /// the same class if they are connected with directed paths in both
 		  /// direction.
 		  ///
 		  /// \return The number of strongly connected components.
 		  /// \note By definition, the empty digraph has zero
 		  /// strongly connected components.
 		  ///
 		  /// \see stronglyConnected(), stronglyConnectedComponents()
 		  template <typename Digraph>
 		  int countStronglyConnectedComponents(const Digraph& digraph) {
 		    checkConcept<concepts::Digraph, Digraph>();
 		    using namespace _connectivity_bits;
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::Arc Arc;
 		    typedef typename Digraph::NodeIt NodeIt;
@@ -723,63 +723,63 @@
+		      }
 		    private:
 		      const Digraph& _graph;
 		      NodeMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Node> _predMap;
 		      std::stack<Edge> _edgeStack;
 		      int _num;
 		      bool rootCut;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether an undirected graph is bi-node-connected.
 		  ///
-		  /// This function checks whether the given undirected graph is
 		  /// This function checks whether the given undirected graph is
 		  /// bi-node-connected, i.e. any two edges are on same circle.
 		  ///
 		  /// \return \c true if the graph bi-node-connected.
 		  /// \note By definition, the empty graph is bi-node-connected.
 		  ///
 		  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  bool biNodeConnected(const Graph& graph) {
 		    return countBiNodeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
-		  /// \brief Count the number of bi-node-connected components of an
 		  /// \brief Count the number of bi-node-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// This function counts the number of bi-node-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph>
 		  int countBiNodeConnectedComponents(const Graph& graph) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    using namespace _connectivity_bits;
 		    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compNum);
@@ -791,95 +791,95 @@
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected components of an undirected graph.
 		  ///
 		  /// This function finds the bi-node-connected components of the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  ///
 		  /// \image html node_biconnected_components.png
 		  /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval compMap A writable edge map. The values will be set from 0
 		  /// to the number of the bi-node-connected components minus one. Each
-		  /// value of the map will be set exactly once, and the values of a
 		  /// value of the map will be set exactly once, and the values of a
 		  /// certain component will be set continuously.
 		  /// \return The number of bi-node-connected components.
 		  ///
 		  /// \see biNodeConnected(), countBiNodeConnectedComponents()
 		  template <typename Graph, typename EdgeMap>
 		  int biNodeConnectedComponents(const Graph& graph,
 		                                EdgeMap& compMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-node-connected cut nodes in an undirected graph.
 		  ///
 		  /// This function finds the bi-node-connected cut nodes in the given
 		  /// undirected graph.
 		  ///
 		  /// The bi-node-connected components are the classes of an equivalence
 		  /// relation on the edges of a undirected graph. Two edges are in the
 		  /// same class if they are on same circle.
 		  /// The bi-node-connected components are separted by the cut nodes of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
-		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \retval cutMap A writable node map. The values will be set to
 		  /// \c true for the nodes that separate two or more components
 		  /// (exactly once for each cut node), and will not be changed for
 		  /// other nodes.
 		  /// \return The number of the cut nodes.
 		  ///
 		  /// \see biNodeConnected(), biNodeConnectedComponents()
 		  template <typename Graph, typename NodeMap>
 		  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();
 		    using namespace _connectivity_bits;
 		    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;
 		    int cutNum = 0;
 		    Visitor visitor(graph, cutMap, cutNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
@@ -1064,49 +1064,49 @@
 		        if (_retMap[_graph.source(edge)] > _retMap[_graph.target(edge)]) {
 		          _retMap.set(_graph.source(edge), _retMap[_graph.target(edge)]);
+		        }
+		      }
 		    private:
 		      const Digraph& _graph;
 		      ArcMap& _cutMap;
 		      int& _cutNum;
 		      typename Digraph::template NodeMap<int> _numMap;
 		      typename Digraph::template NodeMap<int> _retMap;
 		      typename Digraph::template NodeMap<Arc> _predMap;
 		      int _num;
 		    };
+		  }
 		  template <typename Graph>
 		  int countBiEdgeConnectedComponents(const Graph& graph);
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Check whether an undirected graph is bi-edge-connected.
 		  ///
-		  /// This function checks whether the given undirected graph is
 		  /// This function checks whether the given undirected graph is
 		  /// bi-edge-connected, i.e. any two nodes are connected with at least
 		  /// two edge-disjoint paths.
 		  ///
 		  /// \return \c true if the graph is bi-edge-connected.
 		  /// \note By definition, the empty graph is bi-edge-connected.
 		  ///
 		  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()
 		  template <typename Graph>
 		  bool biEdgeConnected(const Graph& graph) {
 		    return countBiEdgeConnectedComponents(graph) <= 1;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Count the number of bi-edge-connected components of an
 		  /// undirected graph.
 		  ///
 		  /// This function counts the number of bi-edge-connected components of
 		  /// the given undirected graph.
 		  ///
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
@@ -1171,49 +1171,49 @@
 		    using namespace _connectivity_bits;
 		    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;
 		    int compNum = 0;
 		    Visitor visitor(graph, compMap, compNum);
 		    DfsVisit<Graph, Visitor> dfs(graph, visitor);
 		    dfs.init();
 		    for (NodeIt it(graph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
 		    return compNum;
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Find the bi-edge-connected cut edges in an undirected graph.
 		  ///
 		  /// This function finds the bi-edge-connected cut edges in the given
-		  /// undirected graph.
 		  /// undirected graph.
 		  ///
 		  /// The bi-edge-connected components are the classes of an equivalence
 		  /// relation on the nodes of an undirected graph. Two nodes are in the
 		  /// same class if they are connected with at least two edge-disjoint
 		  /// paths.
 		  /// The bi-edge-connected components are separted by the cut edges of
 		  /// the components.
 		  ///
 		  /// \param graph The undirected graph.
 		  /// \retval cutMap A writable edge map. The values will be set to \c true
 		  /// for the cut edges (exactly once for each cut edge), and will not be
 		  /// changed for other edges.
 		  /// \return The number of cut edges.
 		  ///
 		  /// \see biEdgeConnected(), biEdgeConnectedComponents()
 		  template <typename Graph, typename EdgeMap>
 		  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {
 		    checkConcept<concepts::Graph, Graph>();
 		    typedef typename Graph::NodeIt NodeIt;
 		    typedef typename Graph::Edge Edge;
 		    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();
 		    using namespace _connectivity_bits;
@@ -1328,49 +1328,49 @@
 		      visitor(order, countNodes(digraph));
 		    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >
 		      dfs(digraph, visitor);
 		    dfs.init();
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      if (!dfs.reached(it)) {
 		        dfs.addSource(it);
 		        dfs.start();
+		      }
+		    }
+		  }
 		  /// \ingroup graph_properties
 		  ///
 		  /// \brief Sort the nodes of a DAG into topolgical order.
 		  ///
 		  /// This function sorts the nodes of the given acyclic digraph (DAG)
 		  /// into topolgical order and also checks whether the given digraph
 		  /// is DAG.
 		  ///
 		  /// \param digraph The digraph.
 		  /// \retval order A readable and writable node map. The values will be
-		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// set from 0 to the number of the nodes in the digraph minus one.
 		  /// Each value of the map will be set exactly once, and the values will
 		  /// be set descending order.
 		  /// \return \c false if the digraph is not DAG.
 		  ///
 		  /// \see dag(), topologicalSort()
 		  template <typename Digraph, typename NodeMap>
 		  bool checkedTopologicalSort(const Digraph& digraph, NodeMap& order) {
 		    using namespace _connectivity_bits;
 		    checkConcept<concepts::Digraph, Digraph>();
 		    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,
 		      NodeMap>();
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
 		    typedef typename Digraph::Arc Arc;
 		    for (NodeIt it(digraph); it != INVALID; ++it) {
 		      order.set(it, -1);
+		    }
 		    TopologicalSortVisitor<Digraph, NodeMap>
 		      visitor(order, countNodes(digraph));

lemon/core.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
+		 * Copyright (C) 2003-2010
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CORE_H
 		#define LEMON_CORE_H
 		#include <vector>
 		#include <algorithm>
 		#include <lemon/config.h>
 		#include <lemon/bits/enable_if.h>
 		#include <lemon/bits/traits.h>
 		#include <lemon/assert.h>
@@ -1218,88 +1218,89 @@
 		  ///time bound for arc look-ups. This class also guarantees the
 		  ///optimal time bound in a constant factor for any distribution of
 		  ///queries.
 		  ///
 		  ///\tparam GR The type of the underlying digraph.
 		  ///
 		  ///\sa ArcLookUp
 		  ///\sa AllArcLookUp
 		  template <typename GR>
 		  class DynArcLookUp
 		    : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
+		  {
 		    typedef typename ItemSetTraits<GR, typename GR::Arc>
 		    ::ItemNotifier::ObserverBase Parent;
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		  public:
 		    /// The Digraph type
 		    typedef GR Digraph;
 		  protected:
-		    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
 		    class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type
+		    {
 		      typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
 		    public:
 		      AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
 		      virtual void add(const Node& node) {
 		        Parent::add(node);
 		        Parent::set(node, INVALID);
+		      }
 		      virtual void add(const std::vector<Node>& nodes) {
 		        Parent::add(nodes);
 		        for (int i = 0; i < int(nodes.size()); ++i) {
 		          Parent::set(nodes[i], INVALID);
+		        }
+		      }
 		      virtual void build() {
 		        Parent::build();
 		        Node it;
 		        typename Parent::Notifier* nf = Parent::notifier();
 		        for (nf->first(it); it != INVALID; nf->next(it)) {
 		          Parent::set(it, INVALID);
+		        }
+		      }
 		    };
 		    class ArcLess {
 		      const Digraph &g;
 		    public:
 		      ArcLess(const Digraph &_g) : g(_g) {}
 		      bool operator()(Arc a,Arc b) const
+		      {
 		        return g.target(a)<g.target(b);
+		      }
 		    };
-		  protected:
 		  protected:
 		    const Digraph &_g;
 		    AutoNodeMap _head;
 		    typename Digraph::template ArcMap<Arc> _parent;
 		    typename Digraph::template ArcMap<Arc> _left;
 		    typename Digraph::template ArcMap<Arc> _right;
 		  public:
 		    ///Constructor
 		    ///Constructor.
 		    ///
 		    ///It builds up the search database.
 		    DynArcLookUp(const Digraph &g)
 		      : _g(g),_head(g),_parent(g),_left(g),_right(g)
+		    {
 		      Parent::attach(_g.notifier(typename Digraph::Arc()));
 		      refresh();
+		    }
 		  protected:
 		    virtual void add(const Arc& arc) {

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

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-~~2009~~
	5	* Copyright (C) 2003-2010
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/arg_parser.h>
20	20
21	21	namespace lemon {
22	22
23	23	void ArgParser::_terminate(ArgParserException::Reason reason) const
24	24	{
25	25	if(_exit_on_problems)
26	26	exit(1);
27	27	else throw(ArgParserException(reason));
28	28	}
29
30
	29
	30
31	31	void ArgParser::_showHelp(void *p)
32	32	{
33	33	(static_cast<ArgParser*>(p))->showHelp();
34	34	(static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);
35	35	}
36	36
37	37	ArgParser::ArgParser(int argc, const char * const *argv)
38	38	:_argc(argc), _argv(argv), _command_name(argv[0]),
39	39	_exit_on_problems(true) {
40	40	funcOption("-help","Print a short help message",_showHelp,this);
41	41	synonym("help","-help");
42	42	synonym("h","-help");
43	43	}
44	44
45	45	ArgParser::~ArgParser()
46	46	{
47	47	for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
48	48	if(i->second.self_delete)
49	49	switch(i->second.type) {
50	50	case BOOL:
51	51	delete i->second.bool_p;
52	52	break;
53	53	case STRING:
54	54	delete i->second.string_p;

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5		* Copyright (C) 2003-~~2008~~
	5	* Copyright (C) 2003-2010
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/clp.h>
20	20	#include <coin/ClpSimplex.hpp>
21	21
22	22	namespace lemon {
23	23
24	24	ClpLp::ClpLp() {
25	25	_prob = new ClpSimplex();
26	26	_init_temporals();
27	27	messageLevel(MESSAGE_NOTHING);
28	28	}
29	29