LEMON/LEMON-official Changeset - r1084:d303bfa8b1ed

Repositories » LEMON » LEMON-official

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

Changeset - r1084:d303bfa8b1ed

« 1083:7887be

1085:7340bd »

r1084:d303bfa8b1ed

Mon, 08 Aug 2011 13:13:03

[Not Reviewed]

0 comments (0 inline)

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

Unify sources

0 13 0

r1.2.2 1.2

13 files changed with 12 insertions and 12 deletions:

doc/lgf.dox

lemon/bits/graph_adaptor_extender.h

lemon/bits/path_dump.h

lemon/bits/windows.cc

lemon/cost_scaling.h

lemon/maps.h

lemon/preflow.h

test/dfs_test.cc

test/graph_copy_test.cc

test/heap_test.cc

test/maps_test.cc

test/preflow_test.cc

↑ Collapse diff ↑

doc/lgf.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-2011
 		 * 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 lgf-format LEMON Graph Format (LGF)
 		The \e LGF is a <em>column oriented</em>
 		file format for storing graphs and associated data like
 		node and edge maps.
 		Each line with \c '#' first non-whitespace
 		character is considered as a comment line.
 		Otherwise the file consists of sections starting with
 		a header line. The header lines starts with an \c '@' character followed by the
 		type of section. The standard section types are \c \@nodes, \c
 		\@arcs and \c \@edges
 		and \@attributes. Each header line may also have an optional
 		\e name, which can be use to distinguish the sections of the same
 		type.
 		The standard sections are column oriented, each line consists of
 		<em>token</em>s separated by whitespaces. A token can be \e plain or
 		\e quoted. A plain token is just a sequence of non-whitespace characters,
 		while a quoted token is a
 		character sequence surrounded by double quotes, and it can also
 		contain whitespaces and escape sequences.
 		The \c \@nodes section describes a set of nodes and associated
 		maps. The first is a header line, its columns are the names of the
 		maps appearing in the following lines.
 		One of the maps must be called \c
 		"label", which plays special role in the file.
 		The following
 		non-empty lines until the next section describes nodes of the
 		graph. Each line contains the values of the node maps
 		associated to the current node.
 		\code
 		 @nodes
 		 label  coordinates  size    title
 (10,20)      10      "First node"
 (80,80)      8       "Second node"
 (40,10)      10      "Third node"
 		\endcode
 		The \c \@arcs section is very similar to the \c \@nodes section, it
 		again starts with a header line describing the names of the maps, but
 		the \c "label" map is not obligatory here. The following lines
 		describe the arcs. The first two tokens of each line are the source
 		and the target node of the arc, respectively, then come the map
 		values. The source and target tokens must be node labels.
 		\code
 		 @arcs
 		         capacity
 2   16
 3   12
 3   18
 		\endcode
 		If there is no map in the \c \@arcs section at all, then it must be
 		indicated by a sole '-' sign in the first line.
 		\code
 		 @arcs
+		         -
 2
 3
 3
 		\endcode
 		The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
 		also store the edge set of an undirected graph. In such case there is
 		a conventional method for store arc maps in the file, if two columns
 		have the same caption with \c '+' and \c '-' prefix, then these columns
 		can be regarded as the values of an arc map.
 		The \c \@attributes section contains key-value pairs, each line
 		consists of two tokens, an attribute name, and then an attribute
 		value. The value of the attribute could be also a label value of a
 		node or an edge, or even an edge label prefixed with \c '+' or \c '-',
 		which regards to the forward or backward directed arc of the
 		corresponding edge.
 		\code
 		 @attributes
 		 source 1
 		 target 3
 		 caption "LEMON test digraph"
 		\endcode
 		The \e LGF can contain extra sections, but there is no restriction on
 		the format of such sections.
 		*/
+		}
 		//  LocalWords:  whitespace whitespaces

lemon/bits/graph_adaptor_extender.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-2011
 		 * 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_GRAPH_ADAPTOR_EXTENDER_H
 		#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		namespace lemon {
 		  template <typename _Digraph>
 		  class DigraphAdaptorExtender : public _Digraph {
 		    typedef _Digraph Parent;
 		  public:
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender Adaptor;
 		    // 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);
 		      else if(n==Parent::target(e))
 		        return Parent::source(e);
 		      else
 		        return INVALID;
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		  };
 		  template <typename _Graph>
 		  class GraphAdaptorExtender : public _Graph {
 		    typedef _Graph Parent;
 		  public:
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    // Graph extension
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    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);
 		      else if( n == Parent::v(e))
 		        return Parent::u(e);
 		      else
 		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &a) const {
 		      return Parent::direct(a, !Parent::direction(a));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Adaptor* _adaptor;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Adaptor& adaptor, const Edge& e) :
 		        Edge(e), _adaptor(&adaptor) { }
 		      EdgeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Edge {
 		      friend class GraphAdaptorExtender;
 		      const Adaptor* _adaptor;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
 		        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
+		      }
 		      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
 		        : _adaptor(&adaptor), Edge(e) {
 		        direction = (_adaptor->u(e) == n);
+		      }
 		      IncEdgeIt& operator++() {
 		        _adaptor->nextInc(*this, direction);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node runningNode(const OutArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node baseNode(const InArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node runningNode(const InArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::u(e) : Parent::v(e);
+		    }
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::v(e) : Parent::u(e);
+		    }
 		  };
+		}
 		#endif

lemon/bits/path_dump.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-2011
 		 * 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_PATH_DUMP_H
 		#define LEMON_BITS_PATH_DUMP_H
 		#include <lemon/core.h>
 		#include <lemon/concept_check.h>
 		namespace lemon {
 		  template <typename _Digraph, typename _PredMap>
 		  class PredMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMap PredMap;
 		    PredMapPath(const Digraph& _digraph, const PredMap& _predMap,
 		                typename Digraph::Node _target)
 		      : digraph(_digraph), predMap(_predMap), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMap[node]) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return predMap[target] == INVALID;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMap[current] == INVALID) current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMap[current];
+		      }
 		      RevArcIt& operator++() {
 		        current = path->digraph.source(path->predMap[current]);
 		        if (path->predMap[current] == INVALID) current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMap& predMap;
 		    typename Digraph::Node target;
 		  };
 		  template <typename _Digraph, typename _PredMatrixMap>
 		  class PredMatrixMapPath {
 		  public:
 		    typedef True RevPathTag;
 		    typedef _Digraph Digraph;
 		    typedef typename Digraph::Arc Arc;
 		    typedef _PredMatrixMap PredMatrixMap;
 		    PredMatrixMapPath(const Digraph& _digraph,
 		                      const PredMatrixMap& _predMatrixMap,
 		                      typename Digraph::Node _source,
 		                      typename Digraph::Node _target)
 		      : digraph(_digraph), predMatrixMap(_predMatrixMap),
 		        source(_source), target(_target) {}
 		    int length() const {
 		      int len = 0;
 		      typename Digraph::Node node = target;
 		      typename Digraph::Arc arc;
 		      while ((arc = predMatrixMap(source, node)) != INVALID) {
 		        node = digraph.source(arc);
 		        ++len;
+		      }
 		      return len;
+		    }
 		    bool empty() const {
 		      return predMatrixMap(source, target) == INVALID;
+		    }
 		    class RevArcIt {
 		    public:
 		      RevArcIt() {}
 		      RevArcIt(Invalid) : path(0), current(INVALID) {}
 		      RevArcIt(const PredMatrixMapPath& _path)
 		        : path(&_path), current(_path.target) {
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
+		      }
 		      operator const typename Digraph::Arc() const {
 		        return path->predMatrixMap(path->source, current);
+		      }
 		      RevArcIt& operator++() {
 		        current =
 		          path->digraph.source(path->predMatrixMap(path->source, current));
 		        if (path->predMatrixMap(path->source, current) == INVALID)
 		          current = INVALID;
 		        return *this;
+		      }
 		      bool operator==(const RevArcIt& e) const {
 		        return current == e.current;
+		      }
 		      bool operator!=(const RevArcIt& e) const {
 		        return current != e.current;
+		      }
 		      bool operator<(const RevArcIt& e) const {
 		        return current < e.current;
+		      }
 		    private:
 		      const PredMatrixMapPath* path;
 		      typename Digraph::Node current;
 		    };
 		  private:
 		    const Digraph& digraph;
 		    const PredMatrixMap& predMatrixMap;
 		    typename Digraph::Node source;
 		    typename Digraph::Node target;
 		  };
+		}
 		#endif

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-2010
+		 * Copyright (C) 2003-2011
 		 * 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
 		#endif
 		#ifdef UNICODE
 		#undef UNICODE
 		#endif
 		#include <windows.h>
 		#ifdef LOCALE_INVARIANT
 		#define MY_LOCALE LOCALE_INVARIANT
 		#else
 		#define MY_LOCALE LOCALE_NEUTRAL
 		#endif
 		#else
 		#include <unistd.h>
 		#include <ctime>
 		#ifndef WIN32
 		#include <sys/times.h>
 		#endif
 		#include <sys/time.h>
 		#endif
 		#include <cmath>
 		#include <sstream>
 		namespace lemon {
 		  namespace bits {
 		    void getWinProcTimes(double &rtime,
 		                         double &utime, double &stime,
 		                         double &cutime, double &cstime)
+		    {
 		#ifdef WIN32
 		      static const double ch = 4294967296.0e-7;
 		      static const double cl = 1.0e-7;
 		      FILETIME system;
 		      GetSystemTimeAsFileTime(&system);
 		      rtime = ch * system.dwHighDateTime + cl * system.dwLowDateTime;
 		      FILETIME create, exit, kernel, user;
 		      if (GetProcessTimes(GetCurrentProcess(),&create, &exit, &kernel, &user)) {
 		        utime = ch * user.dwHighDateTime + cl * user.dwLowDateTime;
 		        stime = ch * kernel.dwHighDateTime + cl * kernel.dwLowDateTime;
 		        cutime = 0;
 		        cstime = 0;
 		      } else {
 		        rtime = 0;
 		        utime = 0;
 		        stime = 0;
 		        cutime = 0;
 		        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,
 		                        ("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);
 		      return GetCurrentProcessId() + time.dwHighDateTime + time.dwLowDateTime;
 		#else
 		      timeval tv;
 		      gettimeofday(&tv, 0);
 		      return getpid() + tv.tv_sec + tv.tv_usec;
 		#endif
+		    }
+		  }
+		}

lemon/cost_scaling.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2010
+		 * Copyright (C) 2003-2011
 		 * 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_COST_SCALING_H
 		#define LEMON_COST_SCALING_H
 		/// \ingroup min_cost_flow_algs
 		/// \file
 		/// \brief Cost scaling algorithm for finding a minimum cost flow.
 		#include <vector>
 		#include <deque>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/maps.h>
 		#include <lemon/math.h>
 		#include <lemon/static_graph.h>
 		#include <lemon/circulation.h>
 		#include <lemon/bellman_ford.h>
 		namespace lemon {
 		  /// \brief Default traits class of CostScaling algorithm.
 		  ///
 		  /// Default traits class of CostScaling algorithm.
 		  /// \tparam GR Digraph type.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values. By default it is \c int.
 		  /// \tparam C The number type used for costs and potentials.
 		  /// By default it is the same as \c V.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V = int, typename C = V>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             bool integer = std::numeric_limits<C>::is_integer >
 		#endif
 		  struct CostScalingDefaultTraits
+		  {
 		    /// The type of the digraph
 		    typedef GR Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef V Value;
 		    /// The type of the arc costs
 		    typedef C Cost;
 		    /// \brief The large cost type used for internal computations
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// It is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    typedef double LargeCost;
 		  };
 		  // Default traits class for integer cost types
 		  template <typename GR, typename V, typename C>
 		  struct CostScalingDefaultTraits<GR, V, C, true>
+		  {
 		    typedef GR Digraph;
 		    typedef V Value;
 		    typedef C Cost;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeCost;
 		#else
 		    typedef long LargeCost;
 		#endif
 		  };
 		  /// \addtogroup min_cost_flow_algs
 		  /// @{
 		  /// \brief Implementation of the Cost Scaling algorithm for
 		  /// finding a \ref min_cost_flow "minimum cost flow".
 		  ///
 		  /// \ref CostScaling implements a cost scaling algorithm that performs
 		  /// push/augment and relabel operations for finding a \ref min_cost_flow
 		  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
 		  /// \ref goldberg97efficient, \ref bunnagel98efficient.
 		  /// It is a highly efficient primal-dual solution method, which
 		  /// can be viewed as the generalization of the \ref Preflow
 		  /// "preflow push-relabel" algorithm for the maximum flow problem.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
 		  /// specified, then default values will be used.
 		  ///
 		  /// \tparam GR The digraph type the algorithm runs on.
 		  /// \tparam V The number type used for flow amounts, capacity bounds
 		  /// and supply values in the algorithm. By default, it is \c int.
 		  /// \tparam C The number type used for costs and potentials in the
 		  /// algorithm. By default, it is the same as \c V.
 		  /// \tparam TR The traits class that defines various types used by the
 		  /// algorithm. By default, it is \ref CostScalingDefaultTraits
 		  /// "CostScalingDefaultTraits<GR, V, C>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		  ///
 		  /// \warning Both number types must be signed and all input data must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  ///
 		  /// \note %CostScaling provides three different internal methods,
 		  /// from which the most efficient one is used by default.
 		  /// For more information, see \ref Method.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
 		  template < typename GR, typename V = int, typename C = V,
 		             typename TR = CostScalingDefaultTraits<GR, V, C> >
 		#endif
 		  class CostScaling
+		  {
 		  public:
 		    /// The type of the digraph
 		    typedef typename TR::Digraph Digraph;
 		    /// The type of the flow amounts, capacity bounds and supply values
 		    typedef typename TR::Value Value;
 		    /// The type of the arc costs
 		    typedef typename TR::Cost Cost;
 		    /// \brief The large cost type
 		    ///
 		    /// The large cost type used for internal computations.
 		    /// By default, it is \c long \c long if the \c Cost type is integer,
 		    /// otherwise it is \c double.
 		    typedef typename TR::LargeCost LargeCost;
 		    /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
 		    typedef TR Traits;
 		  public:
 		    /// \brief Problem type constants for the \c run() function.
 		    ///
 		    /// Enum type containing the problem type constants that can be
 		    /// returned by the \ref run() function of the algorithm.
 		    enum ProblemType {
 		      /// The problem has no feasible solution (flow).
 		      INFEASIBLE,
 		      /// The problem has optimal solution (i.e. it is feasible and
 		      /// bounded), and the algorithm has found optimal flow and node
 		      /// potentials (primal and dual solutions).
 		      OPTIMAL,
 		      /// The digraph contains an arc of negative cost and infinite
 		      /// upper bound. It means that the objective function is unbounded
 		      /// on that arc, however, note that it could actually be bounded
 		      /// over the feasible flows, but this algroithm cannot handle
 		      /// these cases.
 		      UNBOUNDED
 		    };
 		    /// \brief Constants for selecting the internal method.
 		    ///
 		    /// Enum type containing constants for selecting the internal method
 		    /// for the \ref run() function.
 		    ///
 		    /// \ref CostScaling provides three internal methods that differ mainly
 		    /// in their base operations, which are used in conjunction with the
 		    /// relabel operation.
 		    /// By default, the so called \ref PARTIAL_AUGMENT
 		    /// "Partial Augment-Relabel" method is used, which proved to be
 		    /// the most efficient and the most robust on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
 		    enum Method {
 		      /// Local push operations are used, i.e. flow is moved only on one
 		      /// admissible arc at once.
 		      PUSH,
 		      /// Augment operations are used, i.e. flow is moved on admissible
 		      /// paths from a node with excess to a node with deficit.
 		      AUGMENT,
 		      /// Partial augment operations are used, i.e. flow is moved on
 		      /// admissible paths started from a node with excess, but the
 		      /// lengths of these paths are limited. This method can be viewed
 		      /// as a combined version of the previous two operations.
 		      PARTIAL_AUGMENT
 		    };
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
 		    typedef std::vector<int> IntVector;
 		    typedef std::vector<Value> ValueVector;
 		    typedef std::vector<Cost> CostVector;
 		    typedef std::vector<LargeCost> LargeCostVector;
 		    typedef std::vector<char> BoolVector;
 		    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
 		  private:
 		    template <typename KT, typename VT>
 		    class StaticVectorMap {
 		    public:
 		      typedef KT Key;
 		      typedef VT Value;
 		      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
 		      const Value& operator[](const Key& key) const {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      Value& operator[](const Key& key) {
 		        return _v[StaticDigraph::id(key)];
+		      }
 		      void set(const Key& key, const Value& val) {
 		        _v[StaticDigraph::id(key)] = val;
+		      }
 		    private:
 		      std::vector<Value>& _v;
 		    };
 		    typedef StaticVectorMap<StaticDigraph::Node, LargeCost> LargeCostNodeMap;
 		    typedef StaticVectorMap<StaticDigraph::Arc, LargeCost> LargeCostArcMap;
 		  private:
 		    // Data related to the underlying digraph
 		    const GR &_graph;
 		    int _node_num;
 		    int _arc_num;
 		    int _res_node_num;
 		    int _res_arc_num;
 		    int _root;
 		    // Parameters of the problem
 		    bool _have_lower;
 		    Value _sum_supply;
 		    int _sup_node_num;
 		    // Data structures for storing the digraph
 		    IntNodeMap _node_id;
 		    IntArcMap _arc_idf;
 		    IntArcMap _arc_idb;
 		    IntVector _first_out;
 		    BoolVector _forward;
 		    IntVector _source;
 		    IntVector _target;
 		    IntVector _reverse;
 		    // Node and arc data
 		    ValueVector _lower;
 		    ValueVector _upper;
 		    CostVector _scost;
 		    ValueVector _supply;
 		    ValueVector _res_cap;
 		    LargeCostVector _cost;
 		    LargeCostVector _pi;
 		    ValueVector _excess;
 		    IntVector _next_out;
 		    std::deque<int> _active_nodes;
 		    // Data for scaling
 		    LargeCost _epsilon;
 		    int _alpha;
 		    IntVector _buckets;
 		    IntVector _bucket_next;
 		    IntVector _bucket_prev;
 		    IntVector _rank;
 		    int _max_rank;
 		    // Data for a StaticDigraph structure
 		    typedef std::pair<int, int> IntPair;
 		    StaticDigraph _sgr;
 		    std::vector<IntPair> _arc_vec;
 		    std::vector<LargeCost> _cost_vec;
 		    LargeCostArcMap _cost_map;
 		    LargeCostNodeMap _pi_map;
 		  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;
 		  public:
 		    /// \name Named Template Parameters
 		    /// @{
 		    template <typename T>
 		    struct SetLargeCostTraits : public Traits {
 		      typedef T LargeCost;
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// \c LargeCost type.
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting \c LargeCost
 		    /// type, which is used for internal computations in the algorithm.
 		    /// \c Cost must be convertible to \c LargeCost.
 		    template <typename T>
 		    struct SetLargeCost
 		      : public CostScaling<GR, V, C, SetLargeCostTraits<T> > {
 		      typedef  CostScaling<GR, V, C, SetLargeCostTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    CostScaling() {}
 		  public:
 		    /// \brief Constructor.
 		    ///
 		    /// The constructor of the class.
 		    ///
 		    /// \param graph The digraph the algorithm runs on.
 		    CostScaling(const GR& graph) :
 		      _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
 		      _cost_map(_cost_vec), _pi_map(_pi),
 		      INF(std::numeric_limits<Value>::has_infinity ?
 		          std::numeric_limits<Value>::infinity() :
 		          std::numeric_limits<Value>::max())
+		    {
 		      // Check the number types
 		      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
 		        "The flow type of CostScaling must be signed");
 		      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
 		        "The cost type of CostScaling must be signed");
 		      // Reset data structures
 		      reset();
+		    }
 		    /// \name Parameters
 		    /// The parameters of the algorithm can be specified using these
 		    /// functions.
 		    /// @{
 		    /// \brief Set the lower bounds on the arcs.
 		    ///
 		    /// This function sets the lower bounds on the arcs.
 		    /// If it is not used before calling \ref run(), the lower bounds
 		    /// will be set to zero on all arcs.
 		    ///
 		    /// \param map An arc map storing the lower bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template <typename LowerMap>
 		    CostScaling& lowerMap(const LowerMap& map) {
 		      _have_lower = true;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _lower[_arc_idf[a]] = map[a];
 		        _lower[_arc_idb[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the upper bounds (capacities) on the arcs.
 		    ///
 		    /// This function sets the upper bounds (capacities) on the arcs.
 		    /// If it is not used before calling \ref run(), the upper bounds
 		    /// will be set to \ref INF on all arcs (i.e. the flow value will be
 		    /// unbounded from above).
 		    ///
 		    /// \param map An arc map storing the upper bounds.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename UpperMap>
 		    CostScaling& upperMap(const UpperMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _upper[_arc_idf[a]] = map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the costs of the arcs.
 		    ///
 		    /// This function sets the costs of the arcs.
 		    /// If it is not used before calling \ref run(), the costs
 		    /// will be set to \c 1 on all arcs.
 		    ///
 		    /// \param map An arc map storing the costs.
 		    /// Its \c Value type must be convertible to the \c Cost type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename CostMap>
 		    CostScaling& costMap(const CostMap& map) {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        _scost[_arc_idf[a]] =  map[a];
 		        _scost[_arc_idb[a]] = -map[a];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set the supply values of the nodes.
 		    ///
 		    /// This function sets the supply values of the nodes.
 		    /// If neither this function nor \ref stSupply() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// \param map A node map storing the supply values.
 		    /// Its \c Value type must be convertible to the \c Value type
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    template<typename SupplyMap>
 		    CostScaling& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        _supply[_node_id[n]] = map[n];
+		      }
 		      return *this;
+		    }
 		    /// \brief Set single source and target nodes and a supply value.
 		    ///
 		    /// This function sets a single source node and a single target node
 		    /// and the required flow value.
 		    /// If neither this function nor \ref supplyMap() is used before
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
 		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.
 		    /// \param t The target node.
 		    /// \param k The required amount of flow from node \c s to node \c t
 		    /// (i.e. the supply of \c s and the demand of \c t).
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& stSupply(const Node& s, const Node& t, Value k) {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      _supply[_node_id[s]] =  k;
 		      _supply[_node_id[t]] = -k;
 		      return *this;
+		    }
 		    /// @}
 		    /// \name Execution control
 		    /// The algorithm can be executed using \ref run().
 		    /// @{
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This function runs the algorithm.
 		    /// The paramters can be specified using functions \ref lowerMap(),
 		    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    /// For example,
 		    /// \code
 		    ///   CostScaling<ListDigraph> cs(graph);
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// This function can be called more than once. All the given parameters
 		    /// are kept for the next call, unless \ref resetParams() or \ref reset()
 		    /// is used, thus only the modified parameters have to be set again.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class (or the last \ref reset() call), then the \ref reset()
 		    /// function must be called.
 		    ///
 		    /// \param method The internal method that will be used in the
 		    /// algorithm. For more information, see \ref Method.
 		    /// \param factor The cost scaling factor. It must be larger than one.
 		    ///
 		    /// \return \c INFEASIBLE if no feasible flow exists,
 		    /// \n \c OPTIMAL if the problem has optimal solution
 		    /// (i.e. it is feasible and bounded), and the algorithm has found
 		    /// optimal flow and node potentials (primal and dual solutions),
 		    /// \n \c UNBOUNDED if the 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.
 		    ///
 		    /// \see ProblemType, Method
 		    /// \see resetParams(), reset()
 		    ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
 		      _alpha = factor;
 		      ProblemType pt = init();
 		      if (pt != OPTIMAL) return pt;
 		      start(method);
 		      return OPTIMAL;
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple \ref run() calls. Basically, all the given
 		    /// parameters are kept for the next \ref run() call, unless
 		    /// \ref resetParams() or \ref reset() is used.
 		    /// If the underlying digraph was also modified after the construction
 		    /// of the class or the last \ref reset() call, then the \ref reset()
 		    /// function must be used, otherwise \ref resetParams() is sufficient.
 		    ///
 		    /// For example,
 		    /// \code
 		    ///   CostScaling<ListDigraph> cs(graph);
 		    ///
 		    ///   // First run
 		    ///   cs.lowerMap(lower).upperMap(upper).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    ///
 		    ///   // Run again with modified cost map (resetParams() is not called,
 		    ///   // so only the cost map have to be set again)
 		    ///   cost[e] += 100;
 		    ///   cs.costMap(cost).run();
 		    ///
 		    ///   // Run again from scratch using resetParams()
 		    ///   // (the lower bounds will be set to zero on all arcs)
 		    ///   cs.resetParams();
 		    ///   cs.upperMap(capacity).costMap(cost)
 		    ///     .supplyMap(sup).run();
 		    /// \endcode
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \see reset(), run()
 		    CostScaling& resetParams() {
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        _supply[i] = 0;
+		      }
 		      int limit = _first_out[_root];
 		      for (int j = 0; j != limit; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = _forward[j] ? 1 : -1;
+		      }
 		      for (int j = limit; j != _res_arc_num; ++j) {
 		        _lower[j] = 0;
 		        _upper[j] = INF;
 		        _scost[j] = 0;
 		        _scost[_reverse[j]] = 0;
+		      }
 		      _have_lower = false;
 		      return *this;
+		    }
 		    /// \brief Reset all the parameters that have been given before.
 		    ///
 		    /// This function resets all the paramaters that have been given
 		    /// before using functions \ref lowerMap(), \ref upperMap(),
 		    /// \ref costMap(), \ref supplyMap(), \ref stSupply().
 		    ///
 		    /// It is useful for multiple run() calls. If this function is not
 		    /// used, all the parameters given before are kept for the next
 		    /// \ref run() call.
 		    /// However, the underlying digraph must not be modified after this
 		    /// class have been constructed, since it copies and extends the graph.
 		    /// \return <tt>(*this)</tt>
 		    CostScaling& reset() {
 		      // Resize vectors
 		      _node_num = countNodes(_graph);
 		      _arc_num = countArcs(_graph);
 		      _res_node_num = _node_num + 1;
 		      _res_arc_num = 2 * (_arc_num + _node_num);
 		      _root = _node_num;
 		      _first_out.resize(_res_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);
 		      _scost.resize(_res_arc_num);
 		      _supply.resize(_res_node_num);
 		      _res_cap.resize(_res_arc_num);
 		      _cost.resize(_res_arc_num);
 		      _pi.resize(_res_node_num);
 		      _excess.resize(_res_node_num);
 		      _next_out.resize(_res_node_num);
 		      _arc_vec.reserve(_res_arc_num);
 		      _cost_vec.reserve(_res_arc_num);
 		      // Copy the graph
 		      int i = 0, j = 0, k = 2 * _arc_num + _node_num;
 		      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[_res_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
 		    /// It is useful if the total cost cannot be stored in the \c Cost
 		    /// type of the algorithm, which is the default return type of the
 		    /// function.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename Number>
 		    Number totalCost() const {
 		      Number c = 0;
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        int i = _arc_idb[a];
 		        c += static_cast<Number>(_res_cap[i]) *
 		             (-static_cast<Number>(_scost[i]));
+		      }
 		      return c;
+		    }
 		#ifndef DOXYGEN
 		    Cost totalCost() const {
 		      return totalCost<Cost>();
+		    }
 		#endif
 		    /// \brief Return the flow on the given arc.
 		    ///
 		    /// This function returns the flow on the given arc.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Value flow(const Arc& a) const {
 		      return _res_cap[_arc_idb[a]];
+		    }
 		    /// \brief Return the flow map (the primal solution).
 		    ///
 		    /// This function copies the flow value on each arc into the given
 		    /// map. The \c Value type of the algorithm must be convertible to
 		    /// the \c Value type of the map.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    template <typename FlowMap>
 		    void flowMap(FlowMap &map) const {
 		      for (ArcIt a(_graph); a != INVALID; ++a) {
 		        map.set(a, _res_cap[_arc_idb[a]]);
+		      }
+		    }
 		    /// \brief Return the potential (dual value) of the given node.
 		    ///
 		    /// This function returns the potential (dual value) of the
 		    /// given node.
 		    ///
 		    /// \pre \ref run() must be called before using this function.
 		    Cost potential(const Node& n) const {
 		      return static_cast<Cost>(_pi[_node_id[n]]);
+		    }
 		    /// \brief Return the potential map (the dual solution).
 		    ///
 		    /// This function copies the potential (dual value) of each node
 		    /// into the given map.
 		    /// The \c Cost type of the algorithm must be convertible to the
 		    /// \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, static_cast<Cost>(_pi[_node_id[n]]));
+		      }
+		    }
 		    /// @}
 		  private:
 		    // Initialize the algorithm
 		    ProblemType init() {
 		      if (_res_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 != _res_node_num; ++i) {
 		        _pi[i] = 0;
 		        _excess[i] = _supply[i];
+		      }
 		      // Remove infinite upper bounds and check negative arcs
 		      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 = _scost[j] < 0 ? _upper[j] : _lower[j];
 		              if (c >= MAX) return UNBOUNDED;
 		              _excess[i] -= c;
 		              _excess[_target[j]] += c;
+		            }
+		          }
+		        }
 		      } else {
 		        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] && _scost[j] < 0) {
 		              Value c = _upper[j];
 		              if (c >= MAX) return UNBOUNDED;
 		              _excess[i] -= c;
 		              _excess[_target[j]] += c;
+		            }
+		          }
+		        }
+		      }
 		      Value ex, max_cap = 0;
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        ex = _excess[i];
 		        _excess[i] = 0;
 		        if (ex < 0) max_cap -= ex;
+		      }
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_upper[j] >= MAX) _upper[j] = max_cap;
+		      }
 		      // Initialize the large cost vector and the epsilon parameter
 		      _epsilon = 0;
 		      LargeCost lc;
 		      for (int i = 0; i != _root; ++i) {
 		        last_out = _first_out[i+1];
 		        for (int j = _first_out[i]; j != last_out; ++j) {
 		          lc = static_cast<LargeCost>(_scost[j]) * _res_node_num * _alpha;
 		          _cost[j] = lc;
 		          if (lc > _epsilon) _epsilon = lc;
+		        }
+		      }
 		      _epsilon /= _alpha;
 		      // Initialize maps for Circulation and remove non-zero lower bounds
 		      ConstMap<Arc, Value> low(0);
 		      typedef typename Digraph::template ArcMap<Value> ValueArcMap;
 		      typedef typename Digraph::template NodeMap<Value> ValueNodeMap;
 		      ValueArcMap cap(_graph), flow(_graph);
 		      ValueNodeMap sup(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        sup[n] = _supply[_node_id[n]];
+		      }
 		      if (_have_lower) {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          int j = _arc_idf[a];
 		          Value c = _lower[j];
 		          cap[a] = _upper[j] - c;
 		          sup[_graph.source(a)] -= c;
 		          sup[_graph.target(a)] += c;
+		        }
 		      } else {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          cap[a] = _upper[_arc_idf[a]];
+		        }
+		      }
 		      _sup_node_num = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if (sup[n] > 0) ++_sup_node_num;
+		      }
 		      // Find a feasible flow using Circulation
 		      Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap>
 		        circ(_graph, low, cap, sup);
 		      if (!circ.flowMap(flow).run()) return INFEASIBLE;
 		      // Set residual capacities and handle GEQ supply type
 		      if (_sum_supply < 0) {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          Value fa = flow[a];
 		          _res_cap[_arc_idf[a]] = cap[a] - fa;
 		          _res_cap[_arc_idb[a]] = fa;
 		          sup[_graph.source(a)] -= fa;
 		          sup[_graph.target(a)] += fa;
+		        }
 		        for (NodeIt n(_graph); n != INVALID; ++n) {
 		          _excess[_node_id[n]] = sup[n];
+		        }
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int u = _target[a];
 		          int ra = _reverse[a];
 		          _res_cap[a] = -_sum_supply + 1;
 		          _res_cap[ra] = -_excess[u];
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
 		          _excess[u] = 0;
+		        }
 		      } else {
 		        for (ArcIt a(_graph); a != INVALID; ++a) {
 		          Value fa = flow[a];
 		          _res_cap[_arc_idf[a]] = cap[a] - fa;
 		          _res_cap[_arc_idb[a]] = fa;
+		        }
 		        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
 		          int ra = _reverse[a];
 		          _res_cap[a] = 0;
 		          _res_cap[ra] = 0;
 		          _cost[a] = 0;
 		          _cost[ra] = 0;
+		        }
+		      }
 		      return OPTIMAL;
+		    }
 		    // Execute the algorithm and transform the results
 		    void start(Method method) {
 		      // Maximum path length for partial augment
 		      const int MAX_PATH_LENGTH = 4;
 		      // Initialize data structures for buckets
 		      _max_rank = _alpha * _res_node_num;
 		      _buckets.resize(_max_rank);
 		      _bucket_next.resize(_res_node_num + 1);
 		      _bucket_prev.resize(_res_node_num + 1);
 		      _rank.resize(_res_node_num + 1);
 		      // Execute the algorithm
 		      switch (method) {
 		        case PUSH:
 		          startPush();
 		          break;
 		        case AUGMENT:
 		          startAugment(_res_node_num - 1);
 		          break;
 		        case PARTIAL_AUGMENT:
 		          startAugment(MAX_PATH_LENGTH);
 		          break;
+		      }
 		      // Compute node potentials for the original costs
 		      _arc_vec.clear();
 		      _cost_vec.clear();
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_res_cap[j] > 0) {
 		          _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		          _cost_vec.push_back(_scost[j]);
+		        }
+		      }
 		      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		      typename BellmanFord<StaticDigraph, LargeCostArcMap>
 		        ::template SetDistMap<LargeCostNodeMap>::Create bf(_sgr, _cost_map);
 		      bf.distMap(_pi_map);
 		      bf.init(0);
 		      bf.start();
 		      // 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];
+		        }
+		      }
+		    }
 		    // Initialize a cost scaling phase
 		    void initPhase() {
 		      // Saturate arcs not satisfying the optimality condition
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        int last_out = _first_out[u+1];
 		        LargeCost pi_u = _pi[u];
 		        for (int a = _first_out[u]; a != last_out; ++a) {
 		          int v = _target[a];
 		          if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
 		            Value delta = _res_cap[a];
 		            _excess[u] -= delta;
 		            _excess[v] += delta;
 		            _res_cap[a] = 0;
 		            _res_cap[_reverse[a]] += delta;
+		          }
+		        }
+		      }
 		      // Find active nodes (i.e. nodes with positive excess)
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        if (_excess[u] > 0) _active_nodes.push_back(u);
+		      }
 		      // Initialize the next arcs
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        _next_out[u] = _first_out[u];
+		      }
+		    }
 		    // Early termination heuristic
 		    bool earlyTermination() {
 		      const double EARLY_TERM_FACTOR = 3.0;
 		      // Build a static residual graph
 		      _arc_vec.clear();
 		      _cost_vec.clear();
 		      for (int j = 0; j != _res_arc_num; ++j) {
 		        if (_res_cap[j] > 0) {
 		          _arc_vec.push_back(IntPair(_source[j], _target[j]));
 		          _cost_vec.push_back(_cost[j] + 1);
+		        }
+		      }
 		      _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end());
 		      // Run Bellman-Ford algorithm to check if the current flow is optimal
 		      BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map);
 		      bf.init(0);
 		      bool done = false;
 		      int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num)));
 		      for (int i = 0; i < K && !done; ++i) {
 		        done = bf.processNextWeakRound();
+		      }
 		      return done;
+		    }
 		    // Global potential update heuristic
 		    void globalUpdate() {
 		      int bucket_end = _root + 1;
 		      // Initialize buckets
 		      for (int r = 0; r != _max_rank; ++r) {
 		        _buckets[r] = bucket_end;
+		      }
 		      Value total_excess = 0;
 		      for (int i = 0; i != _res_node_num; ++i) {
 		        if (_excess[i] < 0) {
 		          _rank[i] = 0;
 		          _bucket_next[i] = _buckets[0];
 		          _bucket_prev[_buckets[0]] = i;
 		          _buckets[0] = i;
 		        } else {
 		          total_excess += _excess[i];
 		          _rank[i] = _max_rank;
+		        }
+		      }
 		      if (total_excess == 0) return;
 		      // Search the buckets
 		      int r = 0;
 		      for ( ; r != _max_rank; ++r) {
 		        while (_buckets[r] != bucket_end) {
 		          // Remove the first node from the current bucket
 		          int u = _buckets[r];
 		          _buckets[r] = _bucket_next[u];
 		          // Search the incomming arcs of u
 		          LargeCost pi_u = _pi[u];
 		          int last_out = _first_out[u+1];
 		          for (int a = _first_out[u]; a != last_out; ++a) {
 		            int ra = _reverse[a];
 		            if (_res_cap[ra] > 0) {
 		              int v = _source[ra];
 		              int old_rank_v = _rank[v];
 		              if (r < old_rank_v) {
 		                // Compute the new rank of v
 		                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
 		                int new_rank_v = old_rank_v;
 		                if (nrc < LargeCost(_max_rank))
 		                  new_rank_v = r + 1 + int(nrc);
 		                // Change the rank of v
 		                if (new_rank_v < old_rank_v) {
 		                  _rank[v] = new_rank_v;
 		                  _next_out[v] = _first_out[v];
 		                  // Remove v from its old bucket
 		                  if (old_rank_v < _max_rank) {
 		                    if (_buckets[old_rank_v] == v) {
 		                      _buckets[old_rank_v] = _bucket_next[v];
 		                    } else {
 		                      _bucket_next[_bucket_prev[v]] = _bucket_next[v];
 		                      _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
+		                    }
+		                  }
 		                  // Insert v to its new bucket
 		                  _bucket_next[v] = _buckets[new_rank_v];
 		                  _bucket_prev[_buckets[new_rank_v]] = v;
 		                  _buckets[new_rank_v] = v;
+		                }
+		              }
+		            }
+		          }
 		          // Finish search if there are no more active nodes
 		          if (_excess[u] > 0) {
 		            total_excess -= _excess[u];
 		            if (total_excess <= 0) break;
+		          }
+		        }
 		        if (total_excess <= 0) break;
+		      }
 		      // Relabel nodes
 		      for (int u = 0; u != _res_node_num; ++u) {
 		        int k = std::min(_rank[u], r);
 		        if (k > 0) {
 		          _pi[u] -= _epsilon * k;
 		          _next_out[u] = _first_out[u];
+		        }
+		      }
+		    }
 		    /// Execute the algorithm performing augment and relabel operations
 		    void startAugment(int max_length) {
 		      // Paramters for heuristics
 		      const int EARLY_TERM_EPSILON_LIMIT = 1000;
 		      const double GLOBAL_UPDATE_FACTOR = 3.0;
 		      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
 		        (_res_node_num + _sup_node_num * _sup_node_num));
 		      int next_update_limit = global_update_freq;
 		      int relabel_cnt = 0;
 		      // Perform cost scaling phases
 		      std::vector<int> path;
 		      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+		      {
 		        // Early termination heuristic
 		        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
 		          if (earlyTermination()) break;
+		        }
 		        // Initialize current phase
 		        initPhase();
 		        // Perform partial augment and relabel operations
 		        while (true) {
 		          // Select an active node (FIFO selection)
 		          while (_active_nodes.size() > 0 &&
 		                 _excess[_active_nodes.front()] <= 0) {
 		            _active_nodes.pop_front();
+		          }
 		          if (_active_nodes.size() == 0) break;
 		          int start = _active_nodes.front();
 		          // Find an augmenting path from the start node
 		          path.clear();
 		          int tip = start;
 		          while (_excess[tip] >= 0 && int(path.size()) < max_length) {
 		            int u;
 		            LargeCost min_red_cost, rc, pi_tip = _pi[tip];
 		            int last_out = _first_out[tip+1];
 		            for (int a = _next_out[tip]; a != last_out; ++a) {
 		              u = _target[a];
 		              if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) {
 		                path.push_back(a);
 		                _next_out[tip] = a;
 		                tip = u;
 		                goto next_step;
+		              }
+		            }
 		            // Relabel tip node
 		            min_red_cost = std::numeric_limits<LargeCost>::max();
 		            if (tip != start) {
 		              int ra = _reverse[path.back()];
 		              min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]];
+		            }
 		            for (int a = _first_out[tip]; a != last_out; ++a) {
 		              rc = _cost[a] + pi_tip - _pi[_target[a]];
 		              if (_res_cap[a] > 0 && rc < min_red_cost) {
 		                min_red_cost = rc;
+		              }
+		            }
 		            _pi[tip] -= min_red_cost + _epsilon;
 		            _next_out[tip] = _first_out[tip];
 		            ++relabel_cnt;
 		            // Step back
 		            if (tip != start) {
 		              tip = _source[path.back()];
 		              path.pop_back();
+		            }
 		          next_step: ;
+		          }
 		          // Augment along the found path (as much flow as possible)
 		          Value delta;
 		          int pa, u, v = start;
 		          for (int i = 0; i != int(path.size()); ++i) {
 		            pa = path[i];
 		            u = v;
 		            v = _target[pa];
 		            delta = std::min(_res_cap[pa], _excess[u]);
 		            _res_cap[pa] -= delta;
 		            _res_cap[_reverse[pa]] += delta;
 		            _excess[u] -= delta;
 		            _excess[v] += delta;
 		            if (_excess[v] > 0 && _excess[v] <= delta)
 		              _active_nodes.push_back(v);
+		          }
 		          // Global update heuristic
 		          if (relabel_cnt >= next_update_limit) {
 		            globalUpdate();
 		            next_update_limit += global_update_freq;
+		          }
+		        }
+		      }
+		    }
 		    /// Execute the algorithm performing push and relabel operations
 		    void startPush() {
 		      // Paramters for heuristics
 		      const int EARLY_TERM_EPSILON_LIMIT = 1000;
 		      const double GLOBAL_UPDATE_FACTOR = 2.0;
 		      const int global_update_freq = int(GLOBAL_UPDATE_FACTOR *
 		        (_res_node_num + _sup_node_num * _sup_node_num));
 		      int next_update_limit = global_update_freq;
 		      int relabel_cnt = 0;
 		      // Perform cost scaling phases
 		      BoolVector hyper(_res_node_num, false);
 		      LargeCostVector hyper_cost(_res_node_num);
 		      for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ?
 : _epsilon / _alpha )
+		      {
 		        // Early termination heuristic
 		        if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) {
 		          if (earlyTermination()) break;
+		        }
 		        // Initialize current phase
 		        initPhase();
 		        // Perform push and relabel operations
 		        while (_active_nodes.size() > 0) {
 		          LargeCost min_red_cost, rc, pi_n;
 		          Value delta;
 		          int n, t, a, last_out = _res_arc_num;
 		        next_node:
 		          // Select an active node (FIFO selection)
 		          n = _active_nodes.front();
 		          last_out = _first_out[n+1];
 		          pi_n = _pi[n];
 		          // Perform push operations if there are admissible arcs
 		          if (_excess[n] > 0) {
 		            for (a = _next_out[n]; a != last_out; ++a) {
 		              if (_res_cap[a] > 0 &&
 		                  _cost[a] + pi_n - _pi[_target[a]] < 0) {
 		                delta = std::min(_res_cap[a], _excess[n]);
 		                t = _target[a];
 		                // Push-look-ahead heuristic
 		                Value ahead = -_excess[t];
 		                int last_out_t = _first_out[t+1];
 		                LargeCost pi_t = _pi[t];
 		                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
 		                  if (_res_cap[ta] > 0 &&
 		                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
 		                    ahead += _res_cap[ta];
 		                  if (ahead >= delta) break;
+		                }
 		                if (ahead < 0) ahead = 0;
 		                // Push flow along the arc
 		                if (ahead < delta && !hyper[t]) {
 		                  _res_cap[a] -= ahead;
 		                  _res_cap[_reverse[a]] += ahead;
 		                  _excess[n] -= ahead;
 		                  _excess[t] += ahead;
 		                  _active_nodes.push_front(t);
 		                  hyper[t] = true;
 		                  hyper_cost[t] = _cost[a] + pi_n - pi_t;
 		                  _next_out[n] = a;
 		                  goto next_node;
 		                } else {
 		                  _res_cap[a] -= delta;
 		                  _res_cap[_reverse[a]] += delta;
 		                  _excess[n] -= delta;
 		                  _excess[t] += delta;
 		                  if (_excess[t] > 0 && _excess[t] <= delta)
 		                    _active_nodes.push_back(t);
+		                }
 		                if (_excess[n] == 0) {
 		                  _next_out[n] = a;
 		                  goto remove_nodes;
+		                }
+		              }
+		            }
 		            _next_out[n] = a;
+		          }
 		          // Relabel the node if it is still active (or hyper)
 		          if (_excess[n] > 0 || hyper[n]) {
 		             min_red_cost = hyper[n] ? -hyper_cost[n] :
 		               std::numeric_limits<LargeCost>::max();
 		            for (int a = _first_out[n]; a != last_out; ++a) {
 		              rc = _cost[a] + pi_n - _pi[_target[a]];
 		              if (_res_cap[a] > 0 && rc < min_red_cost) {
 		                min_red_cost = rc;
+		              }
+		            }
 		            _pi[n] -= min_red_cost + _epsilon;
 		            _next_out[n] = _first_out[n];
 		            hyper[n] = false;
 		            ++relabel_cnt;
+		          }
 		          // Remove nodes that are not active nor hyper
 		        remove_nodes:
 		          while ( _active_nodes.size() > 0 &&
 		                  _excess[_active_nodes.front()] <= 0 &&
 		                  !hyper[_active_nodes.front()] ) {
 		            _active_nodes.pop_front();
+		          }
 		          // Global update heuristic
 		          if (relabel_cnt >= next_update_limit) {
 		            globalUpdate();
 		            for (int u = 0; u != _res_node_num; ++u)
 		              hyper[u] = false;
 		            next_update_limit += global_update_freq;
+		          }
+		        }
+		      }
+		    }
 		  }; //class CostScaling
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_COST_SCALING_H

lemon/maps.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2010
+		 * Copyright (C) 2003-2011
 		 * 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_MAPS_H
 		#define LEMON_MAPS_H
 		#include <iterator>
 		#include <functional>
 		#include <vector>
 		#include <map>
 		#include <lemon/core.h>
 		///\file
 		///\ingroup maps
 		///\brief Miscellaneous property maps
 		namespace lemon {
 		  /// \addtogroup maps
 		  /// @{
 		  /// Base class of maps.
 		  /// Base class of maps. It provides the necessary type definitions
 		  /// required by the map %concepts.
 		  template<typename K, typename V>
 		  class MapBase {
 		  public:
 		    /// \brief The key type of the map.
 		    typedef K Key;
 		    /// \brief The value type of the map.
 		    /// (The type of objects associated with the keys).
 		    typedef V Value;
 		  };
 		  /// Null map. (a.k.a. DoNothingMap)
 		  /// This map can be used if you have to provide a map only for
 		  /// its type definitions, or if you have to provide a writable map,
 		  /// but data written to it is not required (i.e. it will be sent to
 		  /// <tt>/dev/null</tt>).
 		  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		  ///
 		  /// \sa ConstMap
 		  template<typename K, typename V>
 		  class NullMap : public MapBase<K, V> {
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef V Value;
 		    /// Gives back a default constructed element.
 		    Value operator[](const Key&) const { return Value(); }
 		    /// Absorbs the value.
 		    void set(const Key&, const Value&) {}
 		  };
 		  /// Returns a \c NullMap class
 		  /// This function just returns a \c NullMap class.
 		  /// \relates NullMap
 		  template <typename K, typename V>
 		  NullMap<K, V> nullMap() {
 		    return NullMap<K, V>();
+		  }
 		  /// Constant map.
 		  /// This \ref concepts::ReadMap "readable map" assigns a specified
 		  /// value to each key.
 		  ///
 		  /// In other aspects it is equivalent to \c NullMap.
 		  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// concept, but it absorbs the data written to it.
 		  ///
 		  /// The simplest way of using this map is through the constMap()
 		  /// function.
 		  ///
 		  /// \sa NullMap
 		  /// \sa IdentityMap
 		  template<typename K, typename V>
 		  class ConstMap : public MapBase<K, V> {
 		  private:
 		    V _value;
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef V Value;
 		    /// Default constructor
 		    /// Default constructor.
 		    /// The value of the map will be default constructed.
 		    ConstMap() {}
 		    /// Constructor with specified initial value
 		    /// Constructor with specified initial value.
 		    /// \param v The initial value of the map.
 		    ConstMap(const Value &v) : _value(v) {}
 		    /// Gives back the specified value.
 		    Value operator[](const Key&) const { return _value; }
 		    /// Absorbs the value.
 		    void set(const Key&, const Value&) {}
 		    /// Sets the value that is assigned to each key.
 		    void setAll(const Value &v) {
 		      _value = v;
+		    }
 		    template<typename V1>
 		    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
 		  };
 		  /// Returns a \c ConstMap class
 		  /// This function just returns a \c ConstMap class.
 		  /// \relates ConstMap
 		  template<typename K, typename V>
 		  inline ConstMap<K, V> constMap(const V &v) {
 		    return ConstMap<K, V>(v);
+		  }
 		  template<typename K, typename V>
 		  inline ConstMap<K, V> constMap() {
 		    return ConstMap<K, V>();
+		  }
 		  template<typename T, T v>
 		  struct Const {};
 		  /// Constant map with inlined constant value.
 		  /// This \ref concepts::ReadMap "readable map" assigns a specified
 		  /// value to each key.
 		  ///
 		  /// In other aspects it is equivalent to \c NullMap.
 		  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
 		  /// concept, but it absorbs the data written to it.
 		  ///
 		  /// The simplest way of using this map is through the constMap()
 		  /// function.
 		  ///
 		  /// \sa NullMap
 		  /// \sa IdentityMap
 		  template<typename K, typename V, V v>
 		  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef V Value;
 		    /// Constructor.
 		    ConstMap() {}
 		    /// Gives back the specified value.
 		    Value operator[](const Key&) const { return v; }
 		    /// Absorbs the value.
 		    void set(const Key&, const Value&) {}
 		  };
 		  /// Returns a \c ConstMap class with inlined constant value
 		  /// This function just returns a \c ConstMap class with inlined
 		  /// constant value.
 		  /// \relates ConstMap
 		  template<typename K, typename V, V v>
 		  inline ConstMap<K, Const<V, v> > constMap() {
 		    return ConstMap<K, Const<V, v> >();
+		  }
 		  /// Identity map.
 		  /// This \ref concepts::ReadMap "read-only map" gives back the given
 		  /// key as value without any modification.
 		  ///
 		  /// \sa ConstMap
 		  template <typename T>
 		  class IdentityMap : public MapBase<T, T> {
 		  public:
 		    ///\e
 		    typedef T Key;
 		    ///\e
 		    typedef T Value;
 		    /// Gives back the given value without any modification.
 		    Value operator[](const Key &k) const {
 		      return k;
+		    }
 		  };
 		  /// Returns an \c IdentityMap class
 		  /// This function just returns an \c IdentityMap class.
 		  /// \relates IdentityMap
 		  template<typename T>
 		  inline IdentityMap<T> identityMap() {
 		    return IdentityMap<T>();
+		  }
 		  /// \brief Map for storing values for integer keys from the range
 		  /// <tt>[0..size-1]</tt>.
 		  ///
 		  /// This map is essentially a wrapper for \c std::vector. It assigns
 		  /// values to integer keys from the range <tt>[0..size-1]</tt>.
 		  /// It can be used together with some data structures, e.g.
 		  /// heap types and \c UnionFind, when the used items are small
 		  /// integers. This map conforms to the \ref concepts::ReferenceMap
 		  /// "ReferenceMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the rangeMap()
 		  /// function.
 		  template <typename V>
 		  class RangeMap : public MapBase<int, V> {
 		    template <typename V1>
 		    friend class RangeMap;
 		  private:
 		    typedef std::vector<V> Vector;
 		    Vector _vector;
 		  public:
 		    /// Key type
 		    typedef int Key;
 		    /// Value type
 		    typedef V Value;
 		    /// Reference type
 		    typedef typename Vector::reference Reference;
 		    /// Const reference type
 		    typedef typename Vector::const_reference ConstReference;
 		    typedef True ReferenceMapTag;
 		  public:
 		    /// Constructor with specified default value.
 		    RangeMap(int size = 0, const Value &value = Value())
 		      : _vector(size, value) {}
 		    /// Constructs the map from an appropriate \c std::vector.
 		    template <typename V1>
 		    RangeMap(const std::vector<V1>& vector)
 		      : _vector(vector.begin(), vector.end()) {}
 		    /// Constructs the map from another \c RangeMap.
 		    template <typename V1>
 		    RangeMap(const RangeMap<V1> &c)
 		      : _vector(c._vector.begin(), c._vector.end()) {}
 		    /// Returns the size of the map.
 		    int size() {
 		      return _vector.size();
+		    }
 		    /// Resizes the map.
 		    /// Resizes the underlying \c std::vector container, so changes the
 		    /// keyset of the map.
 		    /// \param size The new size of the map. The new keyset will be the
 		    /// range <tt>[0..size-1]</tt>.
 		    /// \param value The default value to assign to the new keys.
 		    void resize(int size, const Value &value = Value()) {
 		      _vector.resize(size, value);
+		    }
 		  private:
 		    RangeMap& operator=(const RangeMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      return _vector[k];
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      return _vector[k];
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      _vector[k] = v;
+		    }
 		  };
 		  /// Returns a \c RangeMap class
 		  /// This function just returns a \c RangeMap class.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
 		    return RangeMap<V>(size, value);
+		  }
 		  /// \brief Returns a \c RangeMap class created from an appropriate
 		  /// \c std::vector
 		  /// This function just returns a \c RangeMap class created from an
 		  /// appropriate \c std::vector.
 		  /// \relates RangeMap
 		  template<typename V>
 		  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
 		    return RangeMap<V>(vector);
+		  }
 		  /// Map type based on \c std::map
 		  /// This map is essentially a wrapper for \c std::map with addition
 		  /// that you can specify a default value for the keys that are not
 		  /// stored actually. This value can be different from the default
 		  /// contructed value (i.e. \c %Value()).
 		  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
 		  /// concept.
 		  ///
 		  /// This map is useful if a default value should be assigned to most of
 		  /// the keys and different values should be assigned only to a few
 		  /// keys (i.e. the map is "sparse").
 		  /// The name of this type also refers to this important usage.
 		  ///
 		  /// Apart form that, this map can be used in many other cases since it
 		  /// is based on \c std::map, which is a general associative container.
 		  /// However, keep in mind that it is usually not as efficient as other
 		  /// maps.
 		  ///
 		  /// The simplest way of using this map is through the sparseMap()
 		  /// function.
 		  template <typename K, typename V, typename Comp = std::less<K> >
 		  class SparseMap : public MapBase<K, V> {
 		    template <typename K1, typename V1, typename C1>
 		    friend class SparseMap;
 		  public:
 		    /// Key type
 		    typedef K Key;
 		    /// Value type
 		    typedef V Value;
 		    /// Reference type
 		    typedef Value& Reference;
 		    /// Const reference type
 		    typedef const Value& ConstReference;
 		    typedef True ReferenceMapTag;
 		  private:
 		    typedef std::map<K, V, Comp> Map;
 		    Map _map;
 		    Value _value;
 		  public:
 		    /// \brief Constructor with specified default value.
 		    SparseMap(const Value &value = Value()) : _value(value) {}
 		    /// \brief Constructs the map from an appropriate \c std::map, and
 		    /// explicitly specifies a default value.
 		    template <typename V1, typename Comp1>
 		    SparseMap(const std::map<Key, V1, Comp1> &map,
 		              const Value &value = Value())
 		      : _map(map.begin(), map.end()), _value(value) {}
 		    /// \brief Constructs the map from another \c SparseMap.
 		    template<typename V1, typename Comp1>
 		    SparseMap(const SparseMap<Key, V1, Comp1> &c)
 		      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
 		  private:
 		    SparseMap& operator=(const SparseMap&);
 		  public:
 		    ///\e
 		    Reference operator[](const Key &k) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        return it->second;
 		      else
 		        return _map.insert(it, std::make_pair(k, _value))->second;
+		    }
 		    ///\e
 		    ConstReference operator[](const Key &k) const {
 		      typename Map::const_iterator it = _map.find(k);
 		      if (it != _map.end())
 		        return it->second;
 		      else
 		        return _value;
+		    }
 		    ///\e
 		    void set(const Key &k, const Value &v) {
 		      typename Map::iterator it = _map.lower_bound(k);
 		      if (it != _map.end() && !_map.key_comp()(k, it->first))
 		        it->second = v;
 		      else
 		        _map.insert(it, std::make_pair(k, v));
+		    }
 		    ///\e
 		    void setAll(const Value &v) {
 		      _value = v;
 		      _map.clear();
+		    }
 		  };
 		  /// Returns a \c SparseMap class
 		  /// This function just returns a \c SparseMap class with specified
 		  /// default value.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, Compare>(value);
+		  }
 		  template<typename K, typename V>
 		  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
 		    return SparseMap<K, V, std::less<K> >(value);
+		  }
 		  /// \brief Returns a \c SparseMap class created from an appropriate
 		  /// \c std::map
 		  /// This function just returns a \c SparseMap class created from an
 		  /// appropriate \c std::map.
 		  /// \relates SparseMap
 		  template<typename K, typename V, typename Compare>
 		  inline SparseMap<K, V, Compare>
 		    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
+		  {
 		    return SparseMap<K, V, Compare>(map, value);
+		  }
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// Composition of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the
 		  /// composition of two given maps. That is to say, if \c m1 is of
 		  /// type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   ComposeMap<M1, M2> cm(m1,m2);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M2 and the
 		  /// \c Value type is from \c M1.
 		  /// \c M2::Value must be convertible to \c M1::Key.
 		  ///
 		  /// The simplest way of using this map is through the composeMap()
 		  /// function.
 		  ///
 		  /// \sa CombineMap
 		  template <typename M1, typename M2>
 		  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M2::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    typename MapTraits<M1>::ConstReturnValue
 		    operator[](const Key &k) const { return _m1[_m2[k]]; }
 		  };
 		  /// Returns a \c ComposeMap class
 		  /// This function just returns a \c ComposeMap class.
 		  ///
 		  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
 		  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
 		  /// will be equal to <tt>m1[m2[x]]</tt>.
 		  ///
 		  /// \relates ComposeMap
 		  template <typename M1, typename M2>
 		  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
 		    return ComposeMap<M1, M2>(m1, m2);
+		  }
 		  /// Combination of two maps using an STL (binary) functor.
 		  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
 		  /// binary functor and returns the combination of the two given maps
 		  /// using the functor.
 		  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
 		  /// and \c f is of \c F, then for
 		  /// \code
 		  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
 		  /// \endcode
 		  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
 		  ///
 		  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
 		  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
 		  /// \c M2::Value and \c M1::Value must be convertible to the
 		  /// corresponding input parameter of \c F and the return type of \c F
 		  /// must be convertible to \c V.
 		  ///
 		  /// The simplest way of using this map is through the combineMap()
 		  /// function.
 		  ///
 		  /// \sa ComposeMap
 		  template<typename M1, typename M2, typename F,
 		           typename V = typename F::result_type>
 		  class CombineMap : public MapBase<typename M1::Key, V> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		    F _f;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef V Value;
 		    /// Constructor
 		    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
 		      : _m1(m1), _m2(m2), _f(f) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
 		  };
 		  /// Returns a \c CombineMap class
 		  /// This function just returns a \c CombineMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then
 		  /// \code
 		  ///   combineMap(m1,m2,std::plus<double>())
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   addMap(m1,m2)
 		  /// \endcode
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates CombineMap
 		  template<typename M1, typename M2, typename F, typename V>
 		  inline CombineMap<M1, M2, F, V>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return CombineMap<M1, M2, F, V>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename F>
 		  inline CombineMap<M1, M2, F, typename F::result_type>
 		  combineMap(const M1 &m1, const M2 &m2, const F &f) {
 		    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
+		  }
 		  template<typename M1, typename M2, typename K1, typename K2, typename V>
 		  inline CombineMap<M1, M2, V (*)(K1, K2), V>
 		  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
 		    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
+		  }
 		  /// Converts an STL style (unary) functor to a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the value
 		  /// of a given functor. Actually, it just wraps the functor and
 		  /// provides the \c Key and \c Value typedefs.
 		  ///
 		  /// Template parameters \c K and \c V will become its \c Key and
 		  /// \c Value. In most cases they have to be given explicitly because
 		  /// a functor typically does not provide \c argument_type and
 		  /// \c result_type typedefs.
 		  /// Parameter \c F is the type of the used functor.
 		  ///
 		  /// The simplest way of using this map is through the functorToMap()
 		  /// function.
 		  ///
 		  /// \sa MapToFunctor
 		  template<typename F,
 		           typename K = typename F::argument_type,
 		           typename V = typename F::result_type>
 		  class FunctorToMap : public MapBase<K, V> {
 		    F _f;
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef V Value;
 		    /// Constructor
 		    FunctorToMap(const F &f = F()) : _f(f) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _f(k); }
 		  };
 		  /// Returns a \c FunctorToMap class
 		  /// This function just returns a \c FunctorToMap class.
 		  ///
 		  /// This function is specialized for adaptable binary function
 		  /// classes and C++ functions.
 		  ///
 		  /// \relates FunctorToMap
 		  template<typename K, typename V, typename F>
 		  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
 		    return FunctorToMap<F, K, V>(f);
+		  }
 		  template <typename F>
 		  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
 		    functorToMap(const F &f)
+		  {
 		    return FunctorToMap<F, typename F::argument_type,
 		      typename F::result_type>(f);
+		  }
 		  template <typename K, typename V>
 		  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
 		    return FunctorToMap<V (*)(K), K, V>(f);
+		  }
 		  /// Converts a map to an STL style (unary) functor
 		  /// This class converts a map to an STL style (unary) functor.
 		  /// That is it provides an <tt>operator()</tt> to read its values.
 		  ///
 		  /// For the sake of convenience it also works as a usual
 		  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
 		  /// and the \c Key and \c Value typedefs also exist.
 		  ///
 		  /// The simplest way of using this map is through the mapToFunctor()
 		  /// function.
 		  ///
 		  ///\sa FunctorToMap
 		  template <typename M>
 		  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    typedef typename M::Key argument_type;
 		    typedef typename M::Value result_type;
 		    /// Constructor
 		    MapToFunctor(const M &m) : _m(m) {}
 		    ///\e
 		    Value operator()(const Key &k) const { return _m[k]; }
 		    ///\e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \c MapToFunctor class
 		  /// This function just returns a \c MapToFunctor class.
 		  /// \relates MapToFunctor
 		  template<typename M>
 		  inline MapToFunctor<M> mapToFunctor(const M &m) {
 		    return MapToFunctor<M>(m);
+		  }
 		  /// \brief Map adaptor to convert the \c Value type of a map to
 		  /// another type using the default conversion.
 		  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
 		  /// "readable map" to another type using the default conversion.
 		  /// The \c Key type of it is inherited from \c M and the \c Value
 		  /// type is \c V.
 		  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		  ///
 		  /// The simplest way of using this map is through the convertMap()
 		  /// function.
 		  template <typename M, typename V>
 		  class ConvertMap : public MapBase<typename M::Key, V> {
 		    const M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef V Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The underlying map.
 		    ConvertMap(const M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m[k]; }
 		  };
 		  /// Returns a \c ConvertMap class
 		  /// This function just returns a \c ConvertMap class.
 		  /// \relates ConvertMap
 		  template<typename V, typename M>
 		  inline ConvertMap<M, V> convertMap(const M &map) {
 		    return ConvertMap<M, V>(map);
+		  }
 		  /// Applies all map setting operations to two maps
 		  /// This map has two \ref concepts::WriteMap "writable map" parameters
 		  /// and each write request will be passed to both of them.
 		  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
 		  /// operations will return the corresponding values of \c M1.
 		  ///
 		  /// The \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible from those
 		  /// of \c M1.
 		  ///
 		  /// The simplest way of using this map is through the forkMap()
 		  /// function.
 		  template<typename  M1, typename M2>
 		  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    M1 &_m1;
 		    M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
 		    /// Returns the value associated with the given key in the first map.
 		    Value operator[](const Key &k) const { return _m1[k]; }
 		    /// Sets the value associated with the given key in both maps.
 		    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
 		  };
 		  /// Returns a \c ForkMap class
 		  /// This function just returns a \c ForkMap class.
 		  /// \relates ForkMap
 		  template <typename M1, typename M2>
 		  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
 		    return ForkMap<M1,M2>(m1,m2);
+		  }
 		  /// Sum of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the sum
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   AddMap<M1,M2> am(m1,m2);
 		  /// \endcode
 		  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the addMap()
 		  /// function.
 		  ///
 		  /// \sa SubMap, MulMap, DivMap
 		  /// \sa ShiftMap, ShiftWriteMap
 		  template<typename M1, typename M2>
 		  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
 		  };
 		  /// Returns an \c AddMap class
 		  /// This function just returns an \c AddMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]+m2[x]</tt>.
 		  ///
 		  /// \relates AddMap
 		  template<typename M1, typename M2>
 		  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
 		    return AddMap<M1, M2>(m1,m2);
+		  }
 		  /// Difference of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the difference
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   SubMap<M1,M2> sm(m1,m2);
 		  /// \endcode
 		  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the subMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, MulMap, DivMap
 		  template<typename M1, typename M2>
 		  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
 		  };
 		  /// Returns a \c SubMap class
 		  /// This function just returns a \c SubMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]-m2[x]</tt>.
 		  ///
 		  /// \relates SubMap
 		  template<typename M1, typename M2>
 		  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
 		    return SubMap<M1, M2>(m1,m2);
+		  }
 		  /// Product of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the product
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   MulMap<M1,M2> mm(m1,m2);
 		  /// \endcode
 		  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the mulMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, SubMap, DivMap
 		  /// \sa ScaleMap, ScaleWriteMap
 		  template<typename M1, typename M2>
 		  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
 		  };
 		  /// Returns a \c MulMap class
 		  /// This function just returns a \c MulMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]*m2[x]</tt>.
 		  ///
 		  /// \relates MulMap
 		  template<typename M1, typename M2>
 		  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
 		    return MulMap<M1, M2>(m1,m2);
+		  }
 		  /// Quotient of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the quotient
 		  /// of the values of the two given maps.
 		  /// Its \c Key and \c Value types are inherited from \c M1.
 		  /// The \c Key and \c Value of \c M2 must be convertible to those of
 		  /// \c M1.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   DivMap<M1,M2> dm(m1,m2);
 		  /// \endcode
 		  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the divMap()
 		  /// function.
 		  ///
 		  /// \sa AddMap, SubMap, MulMap
 		  template<typename M1, typename M2>
 		  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef typename M1::Value Value;
 		    /// Constructor
 		    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
 		  };
 		  /// Returns a \c DivMap class
 		  /// This function just returns a \c DivMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c double
 		  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]/m2[x]</tt>.
 		  ///
 		  /// \relates DivMap
 		  template<typename M1, typename M2>
 		  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
 		    return DivMap<M1, M2>(m1,m2);
+		  }
 		  /// Shifts a map with a constant.
 		  /// This \ref concepts::ReadMap "read-only map" returns the sum of
 		  /// the given map and a constant value (i.e. it shifts the map with
 		  /// the constant). Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// Actually,
 		  /// \code
 		  ///   ShiftMap<M> sh(m,v);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<M::Key, M::Value> cm(v);
 		  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the shiftMap()
 		  /// function.
 		  ///
 		  /// \sa ShiftWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		    C _v;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m[k]+_v; }
 		  };
 		  /// Shifts a map with a constant (read-write version).
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
 		  /// of the given map and a constant value (i.e. it shifts the map with
 		  /// the constant). Its \c Key and \c Value are inherited from \c M.
 		  /// It makes also possible to write the map.
 		  ///
 		  /// The simplest way of using this map is through the shiftWriteMap()
 		  /// function.
 		  ///
 		  /// \sa ShiftMap
 		  template<typename M, typename C = typename M::Value>
 		  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		    C _v;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m[k]+_v; }
 		    ///\e
 		    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
 		  };
 		  /// Returns a \c ShiftMap class
 		  /// This function just returns a \c ShiftMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
 		  /// <tt>m[x]+v</tt>.
 		  ///
 		  /// \relates ShiftMap
 		  template<typename M, typename C>
 		  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
 		    return ShiftMap<M, C>(m,v);
+		  }
 		  /// Returns a \c ShiftWriteMap class
 		  /// This function just returns a \c ShiftWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
 		  /// <tt>m[x]+v</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates ShiftWriteMap
 		  template<typename M, typename C>
 		  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
 		    return ShiftWriteMap<M, C>(m,v);
+		  }
 		  /// Scales a map with a constant.
 		  /// This \ref concepts::ReadMap "read-only map" returns the value of
 		  /// the given map multiplied from the left side with a constant value.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// Actually,
 		  /// \code
 		  ///   ScaleMap<M> sc(m,v);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<M::Key, M::Value> cm(v);
 		  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the scaleMap()
 		  /// function.
 		  ///
 		  /// \sa ScaleWriteMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		    C _v;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _v*_m[k]; }
 		  };
 		  /// Scales a map with a constant (read-write version).
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
 		  /// the given map multiplied from the left side with a constant value.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// It can also be used as write map if the \c / operator is defined
 		  /// between \c Value and \c C and the given multiplier is not zero.
 		  ///
 		  /// The simplest way of using this map is through the scaleWriteMap()
 		  /// function.
 		  ///
 		  /// \sa ScaleMap
 		  template<typename M, typename C = typename M::Value>
 		  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		    C _v;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    /// Constructor.
 		    /// \param m The undelying map.
 		    /// \param v The constant value.
 		    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _v*_m[k]; }
 		    ///\e
 		    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
 		  };
 		  /// Returns a \c ScaleMap class
 		  /// This function just returns a \c ScaleMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
 		  /// <tt>v*m[x]</tt>.
 		  ///
 		  /// \relates ScaleMap
 		  template<typename M, typename C>
 		  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
 		    return ScaleMap<M, C>(m,v);
+		  }
 		  /// Returns a \c ScaleWriteMap class
 		  /// This function just returns a \c ScaleWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values and \c v is
 		  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
 		  /// <tt>v*m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates ScaleWriteMap
 		  template<typename M, typename C>
 		  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
 		    return ScaleWriteMap<M, C>(m,v);
+		  }
 		  /// Negative of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the negative
 		  /// of the values of the given map (using the unary \c - operator).
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  ///
 		  /// If M::Value is \c int, \c double etc., then
 		  /// \code
 		  ///   NegMap<M> neg(m);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ScaleMap<M> neg(m,-1);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the negMap()
 		  /// function.
 		  ///
 		  /// \sa NegWriteMap
 		  template<typename M>
 		  class NegMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M& _m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    NegMap(const M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return -_m[k]; }
 		  };
 		  /// Negative of a map (read-write version)
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the
 		  /// negative of the values of the given map (using the unary \c -
 		  /// operator).
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// It makes also possible to write the map.
 		  ///
 		  /// If M::Value is \c int, \c double etc., then
 		  /// \code
 		  ///   NegWriteMap<M> neg(m);
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ScaleWriteMap<M> neg(m,-1);
 		  /// \endcode
 		  ///
 		  /// The simplest way of using this map is through the negWriteMap()
 		  /// function.
 		  ///
 		  /// \sa NegMap
 		  template<typename M>
 		  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
 		    M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    NegWriteMap(M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return -_m[k]; }
 		    ///\e
 		    void set(const Key &k, const Value &v) { _m.set(k, -v); }
 		  };
 		  /// Returns a \c NegMap class
 		  /// This function just returns a \c NegMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
 		  ///
 		  /// \relates NegMap
 		  template <typename M>
 		  inline NegMap<M> negMap(const M &m) {
 		    return NegMap<M>(m);
+		  }
 		  /// Returns a \c NegWriteMap class
 		  /// This function just returns a \c NegWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates NegWriteMap
 		  template <typename M>
 		  inline NegWriteMap<M> negWriteMap(M &m) {
 		    return NegWriteMap<M>(m);
+		  }
 		  /// Absolute value of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the absolute
 		  /// value of the values of the given map.
 		  /// Its \c Key and \c Value are inherited from \c M.
 		  /// \c Value must be comparable to \c 0 and the unary \c -
 		  /// operator must be defined for it, of course.
 		  ///
 		  /// The simplest way of using this map is through the absMap()
 		  /// function.
 		  template<typename M>
 		  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
 		    const M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef typename M::Value Value;
 		    /// Constructor
 		    AbsMap(const M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const {
 		      Value tmp = _m[k];
 		      return tmp >= 0 ? tmp : -tmp;
+		    }
 		  };
 		  /// Returns an \c AbsMap class
 		  /// This function just returns an \c AbsMap class.
 		  ///
 		  /// For example, if \c m is a map with \c double values, then
 		  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
 		  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
 		  /// negative.
 		  ///
 		  /// \relates AbsMap
 		  template<typename M>
 		  inline AbsMap<M> absMap(const M &m) {
 		    return AbsMap<M>(m);
+		  }
 		  /// @}
 		  // Logical maps and map adaptors:
 		  /// \addtogroup maps
 		  /// @{
 		  /// Constant \c true map.
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// each key.
 		  ///
 		  /// Note that
 		  /// \code
 		  ///   TrueMap<K> tm;
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<K,bool> tm(true);
 		  /// \endcode
 		  ///
 		  /// \sa FalseMap
 		  /// \sa ConstMap
 		  template <typename K>
 		  class TrueMap : public MapBase<K, bool> {
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Gives back \c true.
 		    Value operator[](const Key&) const { return true; }
 		  };
 		  /// Returns a \c TrueMap class
 		  /// This function just returns a \c TrueMap class.
 		  /// \relates TrueMap
 		  template<typename K>
 		  inline TrueMap<K> trueMap() {
 		    return TrueMap<K>();
+		  }
 		  /// Constant \c false map.
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
 		  /// each key.
 		  ///
 		  /// Note that
 		  /// \code
 		  ///   FalseMap<K> fm;
 		  /// \endcode
 		  /// is equivalent to
 		  /// \code
 		  ///   ConstMap<K,bool> fm(false);
 		  /// \endcode
 		  ///
 		  /// \sa TrueMap
 		  /// \sa ConstMap
 		  template <typename K>
 		  class FalseMap : public MapBase<K, bool> {
 		  public:
 		    ///\e
 		    typedef K Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Gives back \c false.
 		    Value operator[](const Key&) const { return false; }
 		  };
 		  /// Returns a \c FalseMap class
 		  /// This function just returns a \c FalseMap class.
 		  /// \relates FalseMap
 		  template<typename K>
 		  inline FalseMap<K> falseMap() {
 		    return FalseMap<K>();
+		  }
 		  /// @}
 		  /// \addtogroup map_adaptors
 		  /// @{
 		  /// Logical 'and' of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// 'and' of the values of the two given maps.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   AndMap<M1,M2> am(m1,m2);
 		  /// \endcode
 		  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the andMap()
 		  /// function.
 		  ///
 		  /// \sa OrMap
 		  /// \sa NotMap, NotWriteMap
 		  template<typename M1, typename M2>
 		  class AndMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
 		  };
 		  /// Returns an \c AndMap class
 		  /// This function just returns an \c AndMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
 		  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]&&m2[x]</tt>.
 		  ///
 		  /// \relates AndMap
 		  template<typename M1, typename M2>
 		  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
 		    return AndMap<M1, M2>(m1,m2);
+		  }
 		  /// Logical 'or' of two maps
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// 'or' of the values of the two given maps.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   OrMap<M1,M2> om(m1,m2);
 		  /// \endcode
 		  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the orMap()
 		  /// function.
 		  ///
 		  /// \sa AndMap
 		  /// \sa NotMap, NotWriteMap
 		  template<typename M1, typename M2>
 		  class OrMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
 		  };
 		  /// Returns an \c OrMap class
 		  /// This function just returns an \c OrMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
 		  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]||m2[x]</tt>.
 		  ///
 		  /// \relates OrMap
 		  template<typename M1, typename M2>
 		  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
 		    return OrMap<M1, M2>(m1,m2);
+		  }
 		  /// Logical 'not' of a map
 		  /// This \ref concepts::ReadMap "read-only map" returns the logical
 		  /// negation of the values of the given map.
 		  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
 		  ///
 		  /// The simplest way of using this map is through the notMap()
 		  /// function.
 		  ///
 		  /// \sa NotWriteMap
 		  template <typename M>
 		  class NotMap : public MapBase<typename M::Key, bool> {
 		    const M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    NotMap(const M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return !_m[k]; }
 		  };
 		  /// Logical 'not' of a map (read-write version)
 		  /// This \ref concepts::ReadWriteMap "read-write map" returns the
 		  /// logical negation of the values of the given map.
 		  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
 		  /// It makes also possible to write the map. When a value is set,
 		  /// the opposite value is set to the original map.
 		  ///
 		  /// The simplest way of using this map is through the notWriteMap()
 		  /// function.
 		  ///
 		  /// \sa NotMap
 		  template <typename M>
 		  class NotWriteMap : public MapBase<typename M::Key, bool> {
 		    M &_m;
 		  public:
 		    ///\e
 		    typedef typename M::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    NotWriteMap(M &m) : _m(m) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return !_m[k]; }
 		    ///\e
 		    void set(const Key &k, bool v) { _m.set(k, !v); }
 		  };
 		  /// Returns a \c NotMap class
 		  /// This function just returns a \c NotMap class.
 		  ///
 		  /// For example, if \c m is a map with \c bool values, then
 		  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
 		  ///
 		  /// \relates NotMap
 		  template <typename M>
 		  inline NotMap<M> notMap(const M &m) {
 		    return NotMap<M>(m);
+		  }
 		  /// Returns a \c NotWriteMap class
 		  /// This function just returns a \c NotWriteMap class.
 		  ///
 		  /// For example, if \c m is a map with \c bool values, then
 		  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
 		  /// Moreover it makes also possible to write the map.
 		  ///
 		  /// \relates NotWriteMap
 		  template <typename M>
 		  inline NotWriteMap<M> notWriteMap(M &m) {
 		    return NotWriteMap<M>(m);
+		  }
 		  /// Combination of two maps using the \c == operator
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// the keys for which the corresponding values of the two maps are
 		  /// equal.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   EqualMap<M1,M2> em(m1,m2);
 		  /// \endcode
 		  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the equalMap()
 		  /// function.
 		  ///
 		  /// \sa LessMap
 		  template<typename M1, typename M2>
 		  class EqualMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
 		  };
 		  /// Returns an \c EqualMap class
 		  /// This function just returns an \c EqualMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are maps with keys and values of
 		  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]==m2[x]</tt>.
 		  ///
 		  /// \relates EqualMap
 		  template<typename M1, typename M2>
 		  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
 		    return EqualMap<M1, M2>(m1,m2);
+		  }
 		  /// Combination of two maps using the \c < operator
 		  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
 		  /// the keys for which the corresponding value of the first map is
 		  /// less then the value of the second map.
 		  /// Its \c Key type is inherited from \c M1 and its \c Value type is
 		  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
 		  ///
 		  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
 		  /// \code
 		  ///   LessMap<M1,M2> lm(m1,m2);
 		  /// \endcode
 		  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
 		  ///
 		  /// The simplest way of using this map is through the lessMap()
 		  /// function.
 		  ///
 		  /// \sa EqualMap
 		  template<typename M1, typename M2>
 		  class LessMap : public MapBase<typename M1::Key, bool> {
 		    const M1 &_m1;
 		    const M2 &_m2;
 		  public:
 		    ///\e
 		    typedef typename M1::Key Key;
 		    ///\e
 		    typedef bool Value;
 		    /// Constructor
 		    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
 		    ///\e
 		    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
 		  };
 		  /// Returns an \c LessMap class
 		  /// This function just returns an \c LessMap class.
 		  ///
 		  /// For example, if \c m1 and \c m2 are maps with keys and values of
 		  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
 		  /// <tt>m1[x]<m2[x]</tt>.
 		  ///
 		  /// \relates LessMap
 		  template<typename M1, typename M2>
 		  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
 		    return LessMap<M1, M2>(m1,m2);
+		  }
 		  namespace _maps_bits {
 		    template <typename _Iterator, typename Enable = void>
 		    struct IteratorTraits {
 		      typedef typename std::iterator_traits<_Iterator>::value_type Value;
 		    };
 		    template <typename _Iterator>
 		    struct IteratorTraits<_Iterator,
 		      typename exists<typename _Iterator::container_type>::type>
+		    {
 		      typedef typename _Iterator::container_type::value_type Value;
 		    };
+		  }
 		  /// @}
 		  /// \addtogroup maps
 		  /// @{
 		  /// \brief Writable bool map for logging each \c true assigned element
 		  ///
 		  /// A \ref concepts::WriteMap "writable" bool map for logging
 		  /// each \c true assigned element, i.e it copies subsequently each
 		  /// keys set to \c true to the given iterator.
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  ///
 		  /// There are several algorithms that provide solutions through bool
 		  /// maps and most of them assign \c true at most once for each key.
 		  /// In these cases it is a natural request to store each \c true
 		  /// assigned elements (in order of the assignment), which can be
 		  /// easily done with LoggerBoolMap.
 		  ///
 		  /// The simplest way of using this map is through the loggerBoolMap()
 		  /// function.
 		  ///
 		  /// \tparam IT The type of the iterator.
 		  /// \tparam KEY The key type of the map. The default value set
 		  /// according to the iterator type should work in most cases.
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		#ifdef DOXYGEN
 		  template <typename IT, typename KEY>
 		#else
 		  template <typename IT,
 		            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
 		#endif
 		  class LoggerBoolMap : public MapBase<KEY, bool> {
 		  public:
 		    ///\e
 		    typedef KEY Key;
 		    ///\e
 		    typedef bool Value;
 		    ///\e
 		    typedef IT Iterator;
 		    /// Constructor
 		    LoggerBoolMap(Iterator it)
 		      : _begin(it), _end(it) {}
 		    /// Gives back the given iterator set for the first key
 		    Iterator begin() const {
 		      return _begin;
+		    }
 		    /// Gives back the the 'after the last' iterator
 		    Iterator end() const {
 		      return _end;
+		    }
 		    /// The set function of the map
 		    void set(const Key& key, Value value) {
 		      if (value) {
 		        *_end++ = key;
+		      }
+		    }
 		  private:
 		    Iterator _begin;
 		    Iterator _end;
 		  };
 		  /// Returns a \c LoggerBoolMap class
 		  /// This function just returns a \c LoggerBoolMap class.
 		  ///
 		  /// The most important usage of it is storing certain nodes or arcs
 		  /// that were marked \c true by an algorithm.
 		  /// For example, it makes easier to store the nodes in the processing
 		  /// order of Dfs algorithm, as the following examples show.
 		  /// \code
 		  ///   std::vector<Node> v;
 		  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
 		  /// \endcode
 		  /// \code
 		  ///   std::vector<Node> v(countNodes(g));
 		  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
 		  /// \endcode
 		  ///
 		  /// \note The container of the iterator must contain enough space
 		  /// for the elements or the iterator should be an inserter iterator.
 		  ///
 		  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
 		  /// it cannot be used when a readable map is needed, for example, as
 		  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
 		  ///
 		  /// \relates LoggerBoolMap
 		  template<typename Iterator>
 		  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
 		    return LoggerBoolMap<Iterator>(it);
+		  }
 		  /// @}
 		  /// \addtogroup graph_maps
 		  /// @{
 		  /// \brief Provides an immutable and unique id for each item in a graph.
 		  ///
 		  /// IdMap provides a unique and immutable id for each item of the
 		  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
 		  ///  - \b unique: different items get different ids,
 		  ///  - \b immutable: the id of an item does not change (even if you
 		  ///    delete other nodes).
 		  ///
 		  /// Using this map you get access (i.e. can read) the inner id values of
 		  /// the items stored in the graph, which is returned by the \c id()
 		  /// function of the graph. This map can be inverted with its member
 		  /// class \c InverseMap or with the \c operator()() member.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  ///
 		  /// \see RangeIdMap
 		  template <typename GR, typename K>
 		  class IdMap : public MapBase<K, int> {
 		  public:
 		    /// The graph type of IdMap.
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
 		    typedef K Item;
 		    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
 		    typedef K Key;
 		    /// The value type of IdMap.
 		    typedef int Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Constructor of the map.
 		    explicit IdMap(const Graph& graph) : _graph(&graph) {}
 		    /// \brief Gives back the \e id of the item.
 		    ///
 		    /// Gives back the immutable and unique \e id of the item.
 		    int operator[](const Item& item) const { return _graph->id(item);}
 		    /// \brief Gives back the \e item by its id.
 		    ///
 		    /// Gives back the \e item by its id.
 		    Item operator()(int id) { return _graph->fromId(id, Item()); }
 		  private:
 		    const Graph* _graph;
 		  public:
 		    /// \brief The inverse map type of IdMap.
 		    ///
 		    /// The inverse map type of IdMap. The subscript operator gives back
 		    /// an item by its id.
 		    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
 		    /// \see inverse()
 		    class InverseMap {
 		    public:
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
 		      /// \brief Constructor.
 		      ///
 		      /// Constructor for creating an id-to-item map.
 		      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
 		      /// \brief Gives back an item by its id.
 		      ///
 		      /// Gives back an item by its id.
 		      Item operator[](int id) const { return _graph->fromId(id, Item());}
 		    private:
 		      const Graph* _graph;
 		    };
 		    /// \brief Gives back the inverse of the map.
 		    ///
 		    /// Gives back the inverse of the IdMap.
 		    InverseMap inverse() const { return InverseMap(*_graph);}
 		  };
 		  /// \brief Returns an \c IdMap class.
 		  ///
 		  /// This function just returns an \c IdMap class.
 		  /// \relates IdMap
 		  template <typename K, typename GR>
 		  inline IdMap<GR, K> idMap(const GR& graph) {
 		    return IdMap<GR, K>(graph);
+		  }
 		  /// \brief General cross reference graph map type.
 		  /// This class provides simple invertable graph maps.
 		  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
 		  /// and if a key is set to a new value, then stores it in the inverse map.
 		  /// The graph items can be accessed by their values either using
 		  /// \c InverseMap or \c operator()(), and the values of the map can be
 		  /// accessed with an STL compatible forward iterator (\c ValueIt).
 		  ///
 		  /// This map is intended to be used when all associated values are
 		  /// different (the map is actually invertable) or there are only a few
 		  /// items with the same value.
 		  /// Otherwise consider to use \c IterableValueMap, which is more
 		  /// suitable and more efficient for such cases. It provides iterators
 		  /// to traverse the items with the same associated value, but
 		  /// it does not have \c InverseMap.
 		  ///
 		  /// This type is not reference map, so it cannot be modified with
 		  /// the subscript operator.
 		  ///
 		  /// \tparam GR The graph type.
 		  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
 		  /// \c GR::Edge).
 		  /// \tparam V The value type of the map.
 		  ///
 		  /// \see IterableValueMap
 		  template <typename GR, typename K, typename V>
 		  class CrossRefMap
 		    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
 		  private:
 		    typedef typename ItemSetTraits<GR, K>::
 		      template Map<V>::Type Map;
 		    typedef std::multimap<V, K> Container;
 		    Container _inv_map;
 		  public:
 		    /// The graph type of CrossRefMap.
 		    typedef GR Graph;
 		    typedef GR Digraph;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Item;
 		    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
 		    typedef K Key;
 		    /// The value type of CrossRefMap.
 		    typedef V Value;
 		    /// \brief Constructor.
 		    ///
 		    /// Construct a new CrossRefMap for the given graph.
 		    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
 		    /// \brief Forward iterator for values.
 		    ///
 		    /// This iterator is an STL compatible forward
 		    /// iterator on the values of the map. The values can
 		    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
 		    /// They are considered with multiplicity, so each value is
 		    /// traversed for each item it is assigned to.
 		    class ValueIt
 		      : public std::iterator<std::forward_iterator_tag, Value> {
 		      friend class CrossRefMap;
 		    private:
 		      ValueIt(typename Container::const_iterator _it)
 		        : it(_it) {}
 		    public:
 		      /// Constructor
 		      ValueIt() {}
 		      /// \e
 		      ValueIt& operator++() { ++it; return *this; }
 		      /// \e
 		      ValueIt operator++(int) {
 		        ValueIt tmp(*this);
 		        operator++();
 		        return tmp;
+		      }
 		      /// \e
 		      const Value& operator*() const { return it->first; }
 		      /// \e
 		      const Value* operator->() const { return &(it->first); }
 		      /// \e
 		      bool operator==(ValueIt jt) const { return it == jt.it; }
 		      /// \e
 		      bool operator!=(ValueIt jt) const { return it != jt.it; }
 		    private:
 		      typename Container::const_iterator it;
 		    };
 		    /// Alias for \c ValueIt
 		    typedef ValueIt ValueIterator;
 		    /// \brief Returns an iterator to the first value.
 		    ///
 		    /// Returns an STL compatible iterator to the
 		    /// first value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIt beginValue() const {
 		      return ValueIt(_inv_map.begin());
+		    }
 		    /// \brief Returns an iterator after the last value.
 		    ///
 		    /// Returns an STL compatible iterator after the
 		    /// last value of the map. The values of the
 		    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
 		    /// range.
 		    ValueIt endValue() const {
 		      return ValueIt(_inv_map.end());
+		    }
 		    /// \brief Sets the value associated with the given key.
 		    ///
 		    /// Sets the value associated with the given key.
 		    void set(const Key& key, const Value& val) {
 		      Value oldval = Map::operator[](key);
 		      typename Container::iterator it;
 		      for (it = _inv_map.equal_range(oldval).first;
 		           it != _inv_map.equal_range(oldval).second; ++it) {
 		        if (it->second == key) {
 		          _inv_map.erase(it);
 		          break;
+		        }
+		      }
 		      _inv_map.insert(std::make_pair(val, key));
 		      Map::set(key, val);
+		    }
 		    /// \brief Returns the value associated with the given key.
 		    ///
 		    /// Returns the value associated with the given key.
 		    typename MapTraits<Map>::ConstReturnValue
 		    operator[](const Key& key) const {
 		      return Map::operator[](key);
+		    }

lemon/preflow.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
-		 * Copyright (C) 2003-2010
+		 * Copyright (C) 2003-2011
 		 * 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_PREFLOW_H
 		#define LEMON_PREFLOW_H
 		#include <lemon/tolerance.h>
 		#include <lemon/elevator.h>
 		/// \file
 		/// \ingroup max_flow
 		/// \brief Implementation of the preflow algorithm.
 		namespace lemon {
 		  /// \brief Default traits class of Preflow class.
 		  ///
 		  /// Default traits class of Preflow class.
 		  /// \tparam GR Digraph type.
 		  /// \tparam CAP Capacity map type.
 		  template <typename GR, typename CAP>
 		  struct PreflowDefaultTraits {
 		    /// \brief The type of the digraph the algorithm runs on.
 		    typedef GR Digraph;
 		    /// \brief The type of the map that stores the arc capacities.
 		    ///
 		    /// The type of the map that stores the arc capacities.
 		    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
 		    typedef CAP CapacityMap;
 		    /// \brief The type of the flow values.
 		    typedef typename CapacityMap::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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		#ifdef DOXYGEN
 		    typedef GR::ArcMap<Value> FlowMap;
 		#else
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		#endif
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by Preflow algorithm.
 		    ///
 		    /// The elevator type used by Preflow algorithm.
 		    ///
 		    /// \sa Elevator, LinkedElevator
 		#ifdef DOXYGEN
 		    typedef lemon::Elevator<GR, GR::Node> Elevator;
 		#else
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		#endif
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph for which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /// \ingroup max_flow
 		  ///
 		  /// \brief %Preflow algorithm class.
 		  ///
 		  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
 		  /// \e push-relabel algorithm producing a \ref max_flow
 		  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
 		  /// \ref amo93networkflows, \ref goldberg88newapproach.
 		  /// The preflow algorithms are the fastest known maximum
 		  /// flow algorithms. The current implementation uses a mixture of the
 		  /// \e "highest label" and the \e "bound decrease" heuristics.
 		  /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
 		  ///
 		  /// The algorithm consists of two phases. After the first phase
 		  /// the maximum flow value and the minimum cut is obtained. The
 		  /// second phase constructs a feasible maximum flow on each arc.
 		  ///
 		  /// \warning This implementation cannot handle infinite or very large
 		  /// capacities (e.g. the maximum value of \c CAP::Value).
 		  ///
 		  /// \tparam GR The type of the digraph the algorithm runs on.
 		  /// \tparam CAP The type of the capacity map. 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 PreflowDefaultTraits
 		  /// "PreflowDefaultTraits<GR, CAP>".
 		  /// In most cases, this parameter should not be set directly,
 		  /// consider to use the named template parameters instead.
 		#ifdef DOXYGEN
 		  template <typename GR, typename CAP, typename TR>
 		#else
 		  template <typename GR,
 		            typename CAP = typename GR::template ArcMap<int>,
 		            typename TR = PreflowDefaultTraits<GR, CAP> >
 		#endif
 		  class Preflow {
 		  public:
 		    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the capacity map.
 		    typedef typename Traits::CapacityMap CapacityMap;
 		    ///The type of the flow values.
 		    typedef typename Traits::Value Value;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph& _graph;
 		    const CapacityMap* _capacity;
 		    int _node_num;
 		    Node _source, _target;
 		    FlowMap* _flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tolerance;
 		    bool _phase;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_graph);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_graph, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_graph);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    typedef Preflow Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Preflow<Digraph, CapacityMap, SetFlowMapTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Preflow<Digraph, CapacityMap, SetElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However, an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Preflow<Digraph, CapacityMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Preflow<Digraph, CapacityMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Preflow() {}
 		  public:
 		    /// \brief The constructor of the class.
 		    ///
 		    /// The constructor of the class.
 		    /// \param digraph The digraph the algorithm runs on.
 		    /// \param capacity The capacity of the arcs.
 		    /// \param source The source node.
 		    /// \param target The target node.
 		    Preflow(const Digraph& digraph, const CapacityMap& capacity,
 		            Node source, Node target)
 		      : _graph(digraph), _capacity(&capacity),
 		        _node_num(0), _source(source), _target(target),
 		        _flow(0), _local_flow(false),
 		        _level(0), _local_level(false),
 		        _excess(0), _tolerance(), _phase() {}
 		    /// \brief Destructor.
 		    ///
 		    /// Destructor.
 		    ~Preflow() {
 		      destroyStructures();
+		    }
 		    /// \brief Sets the capacity map.
 		    ///
 		    /// Sets the capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& capacityMap(const CapacityMap& map) {
 		      _capacity = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the source node.
 		    ///
 		    /// Sets the source node.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& source(const Node& node) {
 		      _source = node;
 		      return *this;
+		    }
 		    /// \brief Sets the target node.
 		    ///
 		    /// Sets the target node.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& target(const Node& node) {
 		      _target = node;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by the algorithm.
 		    ///
 		    /// Sets the tolerance object used by the algorithm.
 		    /// \return <tt>(*this)</tt>
 		    Preflow& tolerance(const Tolerance& tolerance) {
 		      _tolerance = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance object used by
 		    /// the algorithm.
 		    const Tolerance& tolerance() const {
 		      return _tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the preflow algorithm is to use
 		    /// \ref run() or \ref runMinCut().\n
 		    /// If you need better control on the initial solution or the execution,
 		    /// you have to call one of the \ref init() functions first, then
 		    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().
 		    ///@{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to zero on each arc.
 		    void init() {
 		      createStructures();
 		      _phase = true;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_excess)[n] = 0;
+		      }
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, 0);
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached[_source] = true;
 		      queue.push_back(_target);
 		      reached[_target] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
 		        if (_tolerance.positive((*_capacity)[e])) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          (*_excess)[u] += (*_capacity)[e];
 		          if (u != _target && !_level->active(u)) {
 		            _level->activate(u);
+		          }
+		        }
+		      }
+		    }
 		    /// \brief Initializes the internal data structures using the
 		    /// given flow map.
 		    ///
 		    /// Initializes the internal data structures and sets the initial
 		    /// flow to the given \c flowMap. The \c flowMap should contain a
 		    /// flow or at least a preflow, i.e. at each node excluding the
 		    /// source node the incoming flow should greater or equal to the
 		    /// outgoing flow.
 		    /// \return \c false if the given \c flowMap is not a preflow.
 		    template <typename FlowMap>
 		    bool init(const FlowMap& flowMap) {
 		      createStructures();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        _flow->set(e, flowMap[e]);
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Value excess = 0;
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess += (*_flow)[e];
+		        }
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          excess -= (*_flow)[e];
+		        }
 		        if (excess < 0 && n != _source) return false;
 		        (*_excess)[n] = excess;
+		      }
 		      typename Digraph::template NodeMap<bool> reached(_graph, false);
 		      _level->initStart();
 		      _level->initAddItem(_target);
 		      std::vector<Node> queue;
 		      reached[_source] = true;
 		      queue.push_back(_target);
 		      reached[_target] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached[v] = true;
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
 		        Value rem = (*_capacity)[e] - (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node u = _graph.target(e);
 		          if ((*_level)[u] == _level->maxLevel()) continue;
 		          _flow->set(e, (*_capacity)[e]);
 		          (*_excess)[u] += rem;
+		        }
+		      }
 		      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
 		        Value rem = (*_flow)[e];
 		        if (_tolerance.positive(rem)) {
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] == _level->maxLevel()) continue;
 		          _flow->set(e, 0);
 		          (*_excess)[v] += rem;
+		        }
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n)
 		        if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n]))
 		          _level->activate(n);
 		      return true;
+		    }
 		    /// \brief Starts the first phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the first phase. After the first phase the maximum flow value
 		    /// and a minimum value cut can already be computed, although a
 		    /// maximum flow is not yet obtained. So after calling this method
 		    /// \ref flowValue() returns the value of a maximum flow and \ref
 		    /// minCut() returns a minimum cut.
 		    /// \pre One of the \ref init() functions must be called before
 		    /// using this function.
 		    void startFirstPhase() {
 		      _phase = true;
 		      while (true) {
 		        int num = _node_num;
 		        Node n = INVALID;
 		        int level = -1;
 		        while (num > 0) {
 		          n = _level->highestActive();
 		          if (n == INVALID) goto first_phase_done;
 		          level = _level->highestActiveLevel();
 		          --num;
 		          Value excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Value rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Value rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_1;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_1:
 		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftHighestActive(new_level + 1);
 		            } else {
 		              _level->liftHighestActiveToTop();
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
+		        }
 		        num = _node_num * 20;
 		        while (num > 0) {
 		          while (level >= 0 && _level->activeFree(level)) {
 		            --level;
+		          }
 		          if (level == -1) {
 		            n = _level->highestActive();
 		            level = _level->highestActiveLevel();
 		            if (n == INVALID) goto first_phase_done;
 		          } else {
 		            n = _level->activeOn(level);
+		          }
 		          --num;
 		          Value excess = (*_excess)[n];
 		          int new_level = _level->maxLevel();
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Value rem = (*_capacity)[e] - (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.target(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] + excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, (*_capacity)[e]);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Value rem = (*_flow)[e];
 		            if (!_tolerance.positive(rem)) continue;
 		            Node v = _graph.source(e);
 		            if ((*_level)[v] < level) {
 		              if (!_level->active(v) && v != _target) {
 		                _level->activate(v);
+		              }
 		              if (!_tolerance.less(rem, excess)) {
 		                _flow->set(e, (*_flow)[e] - excess);
 		                (*_excess)[v] += excess;
 		                excess = 0;
 		                goto no_more_push_2;
 		              } else {
 		                excess -= rem;
 		                (*_excess)[v] += rem;
 		                _flow->set(e, 0);
+		              }
 		            } else if (new_level > (*_level)[v]) {
 		              new_level = (*_level)[v];
+		            }
+		          }
 		        no_more_push_2:
 		          (*_excess)[n] = excess;
 		          if (excess != 0) {
 		            if (new_level + 1 < _level->maxLevel()) {
 		              _level->liftActiveOn(level, new_level + 1);
 		            } else {
 		              _level->liftActiveToTop(level);
+		            }
 		            if (_level->emptyLevel(level)) {
 		              _level->liftToTop(level);
+		            }
 		          } else {
 		            _level->deactivate(n);
+		          }
+		        }
+		      }
 		    first_phase_done:;
+		    }
 		    /// \brief Starts the second phase of the preflow algorithm.
 		    ///
 		    /// The preflow algorithm consists of two phases, this method runs
 		    /// the second phase. After calling one of the \ref init() functions
 		    /// and \ref startFirstPhase() and then \ref startSecondPhase(),
 		    /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the
 		    /// value of a maximum flow, \ref minCut() returns a minimum cut
 		    /// \pre One of the \ref init() functions and \ref startFirstPhase()
 		    /// must be called before using this function.
 		    void startSecondPhase() {
 		      _phase = false;
 		      typename Digraph::template NodeMap<bool> reached(_graph);
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        reached[n] = (*_level)[n] < _level->maxLevel();
+		      }
 		      _level->initStart();
 		      _level->initAddItem(_source);
 		      std::vector<Node> queue;
 		      queue.push_back(_source);
 		      reached[_source] = true;
 		      while (!queue.empty()) {
 		        _level->initNewLevel();
 		        std::vector<Node> nqueue;
 		        for (int i = 0; i < int(queue.size()); ++i) {
 		          Node n = queue[i];
 		          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node v = _graph.target(e);
 		            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
 		              reached[v] = true;
 		              _level->initAddItem(v);
 		              nqueue.push_back(v);
+		            }
+		          }
 		          for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		            Node u = _graph.source(e);
 		            if (!reached[u] &&
 		                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
 		              reached[u] = true;
 		              _level->initAddItem(u);
 		              nqueue.push_back(u);
+		            }
+		          }
+		        }
 		        queue.swap(nqueue);
+		      }
 		      _level->initFinish();
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        if (!reached[n]) {
 		          _level->dirtyTopButOne(n);
 		        } else if ((*_excess)[n] > 0 && _target != n) {
 		          _level->activate(n);
+		        }
+		      }
 		      Node n;
 		      while ((n = _level->highestActive()) != INVALID) {
 		        Value excess = (*_excess)[n];
 		        int level = _level->highestActiveLevel();
 		        int new_level = _level->maxLevel();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Value rem = (*_capacity)[e] - (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.target(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] + excess);
 		              (*_excess)[v] += excess;
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              (*_excess)[v] += rem;
 		              _flow->set(e, (*_capacity)[e]);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Value rem = (*_flow)[e];
 		          if (!_tolerance.positive(rem)) continue;
 		          Node v = _graph.source(e);
 		          if ((*_level)[v] < level) {
 		            if (!_level->active(v) && v != _source) {
 		              _level->activate(v);
+		            }
 		            if (!_tolerance.less(rem, excess)) {
 		              _flow->set(e, (*_flow)[e] - excess);
 		              (*_excess)[v] += excess;
 		              excess = 0;
 		              goto no_more_push;
 		            } else {
 		              excess -= rem;
 		              (*_excess)[v] += rem;
 		              _flow->set(e, 0);
+		            }
 		          } else if (new_level > (*_level)[v]) {
 		            new_level = (*_level)[v];
+		          }
+		        }
 		      no_more_push:
 		        (*_excess)[n] = excess;
 		        if (excess != 0) {
 		          if (new_level + 1 < _level->maxLevel()) {
 		            _level->liftHighestActive(new_level + 1);
 		          } else {
 		            // Calculation error
 		            _level->liftHighestActiveToTop();
+		          }
 		          if (_level->emptyLevel(level)) {
 		            // Calculation error
 		            _level->liftToTop(level);
+		          }
 		        } else {
 		          _level->deactivate(n);
+		        }
+		      }
+		    }
 		    /// \brief Runs the preflow algorithm.
 		    ///
 		    /// Runs the preflow algorithm.
 		    /// \note pf.run() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    ///   pf.startSecondPhase();
 		    /// \endcode
 		    void run() {
 		      init();
 		      startFirstPhase();
 		      startSecondPhase();
+		    }
 		    /// \brief Runs the preflow algorithm to compute the minimum cut.
 		    ///
 		    /// Runs the preflow algorithm to compute the minimum cut.
 		    /// \note pf.runMinCut() is just a shortcut of the following code.
 		    /// \code
 		    ///   pf.init();
 		    ///   pf.startFirstPhase();
 		    /// \endcode
 		    void runMinCut() {
 		      init();
 		      startFirstPhase();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the preflow algorithm can be obtained using these
 		    /// functions.\n
 		    /// Either one of the \ref run() "run*()" functions or one of the
 		    /// \ref startFirstPhase() "start*()" functions should be called
 		    /// before using them.
 		    ///@{
 		    /// \brief Returns the value of the maximum flow.
 		    ///
 		    /// Returns the value of the maximum flow by returning the excess
 		    /// of the target node. This value equals to the value of
 		    /// the maximum flow already after the first phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value flowValue() const {
 		      return (*_excess)[_target];
+		    }
 		    /// \brief Returns the flow value on the given arc.
 		    ///
 		    /// Returns the flow value on the given arc. This method can
 		    /// be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    /// This method can be called after the second phase of the algorithm.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /// \brief Returns \c true when the node is on the source side of the
 		    /// minimum cut.
 		    ///
 		    /// Returns true when the node is on the source side of the found
 		    /// minimum cut. This method can be called both after running \ref
 		    /// startFirstPhase() and \ref startSecondPhase().
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    bool minCut(const Node& node) const {
 		      return ((*_level)[node] == _level->maxLevel()) == _phase;
+		    }
 		    /// \brief Gives back a minimum value cut.
 		    ///
 		    /// Sets \c cutMap to the characteristic vector of a minimum value
 		    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// This method can be called both after running \ref startFirstPhase()
 		    /// and \ref startSecondPhase(). The result after the second phase
 		    /// could be slightly different if inexact computation is used.
 		    ///
 		    /// \note This function calls \ref minCut() for each node, so it runs in
 		    /// O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    template <typename CutMap>
 		    void minCutMap(CutMap& cutMap) const {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        cutMap.set(n, minCut(n));
+		      }
+		    }
 		    /// @}
 		  };
+		}
 		#endif

test/dfs_test.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-2010
+		 * Copyright (C) 2003-2011
 		 * 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/concepts/digraph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dfs.h>
 		#include <lemon/path.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "@arcs\n"
 		  "     label\n"
 		  "0 1  0\n"
 		  "1 2  1\n"
 		  "2 3  2\n"
 		  "1 4  3\n"
 		  "4 2  4\n"
 		  "4 5  5\n"
 		  "5 0  6\n"
 		  "6 3  7\n"
 		  "@attributes\n"
 		  "source 0\n"
 		  "target 5\n"
 		  "source1 6\n"
 		  "target1 3\n";
 		void checkDfsCompile()
+		{
 		  typedef concepts::Digraph Digraph;
 		  typedef Dfs<Digraph> DType;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  Digraph G;
 		  Node s, t;
 		  Arc e;
 		  int l, i;
 		  bool b;
 		  DType::DistMap d(G);
 		  DType::PredMap p(G);
 		  Path<Digraph> pp;
 		  concepts::ReadMap<Arc,bool> am;
+		  {
 		    DType dfs_test(G);
 		    const DType& const_dfs_test = dfs_test;
 		    dfs_test.run(s);
 		    dfs_test.run(s,t);
 		    dfs_test.run();
 		    dfs_test.init();
 		    dfs_test.addSource(s);
 		    e = dfs_test.processNextArc();
 		    e = const_dfs_test.nextArc();
 		    b = const_dfs_test.emptyQueue();
 		    i = const_dfs_test.queueSize();
 		    dfs_test.start();
 		    dfs_test.start(t);
 		    dfs_test.start(am);
 		    l  = const_dfs_test.dist(t);
 		    e  = const_dfs_test.predArc(t);
 		    s  = const_dfs_test.predNode(t);
 		    b  = const_dfs_test.reached(t);
 		    d  = const_dfs_test.distMap();
 		    p  = const_dfs_test.predMap();
 		    pp = const_dfs_test.path(t);
+		  }
+		  {
 		    DType
 		      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
 		      ::SetDistMap<concepts::ReadWriteMap<Node,int> >
 		      ::SetReachedMap<concepts::ReadWriteMap<Node,bool> >
 		      ::SetStandardProcessedMap
 		      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
 		      ::Create dfs_test(G);
 		    concepts::ReadWriteMap<Node,Arc> pred_map;
 		    concepts::ReadWriteMap<Node,int> dist_map;
 		    concepts::ReadWriteMap<Node,bool> reached_map;
 		    concepts::WriteMap<Node,bool> processed_map;
 		    dfs_test
 		      .predMap(pred_map)
 		      .distMap(dist_map)
 		      .reachedMap(reached_map)
 		      .processedMap(processed_map);
 		    dfs_test.run(s);
 		    dfs_test.run(s,t);
 		    dfs_test.run();
 		    dfs_test.init();
 		    dfs_test.addSource(s);
 		    e = dfs_test.processNextArc();
 		    e = dfs_test.nextArc();
 		    b = dfs_test.emptyQueue();
 		    i = dfs_test.queueSize();
 		    dfs_test.start();
 		    dfs_test.start(t);
 		    dfs_test.start(am);
 		    l  = dfs_test.dist(t);
 		    e  = dfs_test.predArc(t);
 		    s  = dfs_test.predNode(t);
 		    b  = dfs_test.reached(t);
 		    pp = dfs_test.path(t);
+		  }
+		}
 		void checkDfsFunctionCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Arc Arc;
 		  typedef Digraph::Node Node;
 		  Digraph g;
 		  bool b;
 		  dfs(g).run(Node());
 		  b=dfs(g).run(Node(),Node());
 		  dfs(g).run();
 		  dfs(g)
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<Node,VType>())
 		    .reachedMap(concepts::ReadWriteMap<Node,bool>())
 		    .processedMap(concepts::WriteMap<Node,bool>())
 		    .run(Node());
 		  b=dfs(g)
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<Node,VType>())
 		    .reachedMap(concepts::ReadWriteMap<Node,bool>())
 		    .processedMap(concepts::WriteMap<Node,bool>())
 		    .path(concepts::Path<Digraph>())
 		    .dist(VType())
 		    .run(Node(),Node());
 		  dfs(g)
 		    .predMap(concepts::ReadWriteMap<Node,Arc>())
 		    .distMap(concepts::ReadWriteMap<Node,VType>())
 		    .reachedMap(concepts::ReadWriteMap<Node,bool>())
 		    .processedMap(concepts::WriteMap<Node,bool>())
 		    .run();
+		}
 		template <class Digraph>
 		void checkDfs() {
 		  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		  Digraph G;
 		  Node s, t;
 		  Node s1, t1;
 		  std::istringstream input(test_lgf);
 		  digraphReader(G, input).
 		    node("source", s).
 		    node("target", t).
 		    node("source1", s1).
 		    node("target1", t1).
 		    run();
 		  Dfs<Digraph> dfs_test(G);
 		  dfs_test.run(s);
 		  Path<Digraph> p = dfs_test.path(t);
 		  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
 		  check(checkPath(G, p),"path() found a wrong path.");
 		  check(pathSource(G, p) == s,"path() found a wrong path.");
 		  check(pathTarget(G, p) == t,"path() found a wrong path.");
 		  for(NodeIt v(G); v!=INVALID; ++v) {
 		    if (dfs_test.reached(v)) {
 		      check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree.");
 		      if (dfs_test.predArc(v)!=INVALID ) {
 		        Arc e=dfs_test.predArc(v);
 		        Node u=G.source(e);
 		        check(u==dfs_test.predNode(v),"Wrong tree.");
 		        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
 		              "Wrong distance. (" << dfs_test.dist(u) << "->"
 		              << dfs_test.dist(v) << ")");
+		      }
+		    }
+		  }
+		  {
 		  Dfs<Digraph> dfs(G);
 		  check(dfs.run(s1,t1) && dfs.reached(t1),"Node 3 is reachable from Node 6.");
+		  }
+		  {
 		    NullMap<Node,Arc> myPredMap;
 		    dfs(G).predMap(myPredMap).run(s);
+		  }
+		}
 		int main()
+		{
 		  checkDfs<ListDigraph>();
 		  checkDfs<SmartDigraph>();
 		  return 0;
+		}

test/graph_copy_test.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-2011
 		 * 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/smart_graph.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/error.h>
 		#include "test_tools.h"
 		using namespace std;
 		using namespace lemon;
 		void digraph_copy_test() {
 		  const int nn = 10;
 		  // Build a digraph
 		  SmartDigraph from;
 		  SmartDigraph::NodeMap<int> fnm(from);
 		  SmartDigraph::ArcMap<int> fam(from);
 		  SmartDigraph::Node fn = INVALID;
 		  SmartDigraph::Arc fa = INVALID;
 		  std::vector<SmartDigraph::Node> fnv;
 		  for (int i = 0; i < nn; ++i) {
 		    SmartDigraph::Node node = from.addNode();
 		    fnv.push_back(node);
 		    fnm[node] = i * i;
 		    if (i == 0) fn = node;
+		  }
 		  for (int i = 0; i < nn; ++i) {
 		    for (int j = 0; j < nn; ++j) {
 		      SmartDigraph::Arc arc = from.addArc(fnv[i], fnv[j]);
 		      fam[arc] = i + j * j;
 		      if (i == 0 && j == 0) fa = arc;
+		    }
+		  }
 		  // Test digraph copy
 		  ListDigraph to;
 		  ListDigraph::NodeMap<int> tnm(to);
 		  ListDigraph::ArcMap<int> tam(to);
 		  ListDigraph::Node tn;
 		  ListDigraph::Arc ta;
 		  SmartDigraph::NodeMap<ListDigraph::Node> nr(from);
 		  SmartDigraph::ArcMap<ListDigraph::Arc> er(from);
 		  ListDigraph::NodeMap<SmartDigraph::Node> ncr(to);
 		  ListDigraph::ArcMap<SmartDigraph::Arc> ecr(to);
 		  digraphCopy(from, to).
 		    nodeMap(fnm, tnm).arcMap(fam, tam).
 		    nodeRef(nr).arcRef(er).
 		    nodeCrossRef(ncr).arcCrossRef(ecr).
 		    node(fn, tn).arc(fa, ta).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
 		  for (SmartDigraph::NodeIt it(from); it != INVALID; ++it) {
 		    check(ncr[nr[it]] == it, "Wrong copy.");
 		    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
+		  }
 		  for (SmartDigraph::ArcIt it(from); it != INVALID; ++it) {
 		    check(ecr[er[it]] == it, "Wrong copy.");
 		    check(fam[it] == tam[er[it]], "Wrong copy.");
 		    check(nr[from.source(it)] == to.source(er[it]), "Wrong copy.");
 		    check(nr[from.target(it)] == to.target(er[it]), "Wrong copy.");
+		  }
 		  for (ListDigraph::NodeIt it(to); it != INVALID; ++it) {
 		    check(nr[ncr[it]] == it, "Wrong copy.");
+		  }
 		  for (ListDigraph::ArcIt it(to); it != INVALID; ++it) {
 		    check(er[ecr[it]] == it, "Wrong copy.");
+		  }
 		  check(tn == nr[fn], "Wrong copy.");
 		  check(ta == er[fa], "Wrong copy.");
 		  // Test repeated copy
 		  digraphCopy(from, to).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
+		}
 		void graph_copy_test() {
 		  const int nn = 10;
 		  // Build a graph
 		  SmartGraph from;
 		  SmartGraph::NodeMap<int> fnm(from);
 		  SmartGraph::ArcMap<int> fam(from);
 		  SmartGraph::EdgeMap<int> fem(from);
 		  SmartGraph::Node fn = INVALID;
 		  SmartGraph::Arc fa = INVALID;
 		  SmartGraph::Edge fe = INVALID;
 		  std::vector<SmartGraph::Node> fnv;
 		  for (int i = 0; i < nn; ++i) {
 		    SmartGraph::Node node = from.addNode();
 		    fnv.push_back(node);
 		    fnm[node] = i * i;
 		    if (i == 0) fn = node;
+		  }
 		  for (int i = 0; i < nn; ++i) {
 		    for (int j = 0; j < nn; ++j) {
 		      SmartGraph::Edge edge = from.addEdge(fnv[i], fnv[j]);
 		      fem[edge] = i * i + j * j;
 		      fam[from.direct(edge, true)] = i + j * j;
 		      fam[from.direct(edge, false)] = i * i + j;
 		      if (i == 0 && j == 0) fa = from.direct(edge, true);
 		      if (i == 0 && j == 0) fe = edge;
+		    }
+		  }
 		  // Test graph copy
 		  ListGraph to;
 		  ListGraph::NodeMap<int> tnm(to);
 		  ListGraph::ArcMap<int> tam(to);
 		  ListGraph::EdgeMap<int> tem(to);
 		  ListGraph::Node tn;
 		  ListGraph::Arc ta;
 		  ListGraph::Edge te;
 		  SmartGraph::NodeMap<ListGraph::Node> nr(from);
 		  SmartGraph::ArcMap<ListGraph::Arc> ar(from);
 		  SmartGraph::EdgeMap<ListGraph::Edge> er(from);
 		  ListGraph::NodeMap<SmartGraph::Node> ncr(to);
 		  ListGraph::ArcMap<SmartGraph::Arc> acr(to);
 		  ListGraph::EdgeMap<SmartGraph::Edge> ecr(to);
 		  graphCopy(from, to).
 		    nodeMap(fnm, tnm).arcMap(fam, tam).edgeMap(fem, tem).
 		    nodeRef(nr).arcRef(ar).edgeRef(er).
 		    nodeCrossRef(ncr).arcCrossRef(acr).edgeCrossRef(ecr).
 		    node(fn, tn).arc(fa, ta).edge(fe, te).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countEdges(from) == countEdges(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
 		  for (SmartGraph::NodeIt it(from); it != INVALID; ++it) {
 		    check(ncr[nr[it]] == it, "Wrong copy.");
 		    check(fnm[it] == tnm[nr[it]], "Wrong copy.");
+		  }
 		  for (SmartGraph::ArcIt it(from); it != INVALID; ++it) {
 		    check(acr[ar[it]] == it, "Wrong copy.");
 		    check(fam[it] == tam[ar[it]], "Wrong copy.");
 		    check(nr[from.source(it)] == to.source(ar[it]), "Wrong copy.");
 		    check(nr[from.target(it)] == to.target(ar[it]), "Wrong copy.");
+		  }
 		  for (SmartGraph::EdgeIt it(from); it != INVALID; ++it) {
 		    check(ecr[er[it]] == it, "Wrong copy.");
 		    check(fem[it] == tem[er[it]], "Wrong copy.");
 		    check(nr[from.u(it)] == to.u(er[it]) || nr[from.u(it)] == to.v(er[it]),
 		          "Wrong copy.");
 		    check(nr[from.v(it)] == to.u(er[it]) || nr[from.v(it)] == to.v(er[it]),
 		          "Wrong copy.");
 		    check((from.u(it) != from.v(it)) == (to.u(er[it]) != to.v(er[it])),
 		          "Wrong copy.");
+		  }
 		  for (ListGraph::NodeIt it(to); it != INVALID; ++it) {
 		    check(nr[ncr[it]] == it, "Wrong copy.");
+		  }
 		  for (ListGraph::ArcIt it(to); it != INVALID; ++it) {
 		    check(ar[acr[it]] == it, "Wrong copy.");
+		  }
 		  for (ListGraph::EdgeIt it(to); it != INVALID; ++it) {
 		    check(er[ecr[it]] == it, "Wrong copy.");
+		  }
 		  check(tn == nr[fn], "Wrong copy.");
 		  check(ta == ar[fa], "Wrong copy.");
 		  check(te == er[fe], "Wrong copy.");
 		  // Test repeated copy
 		  graphCopy(from, to).run();
 		  check(countNodes(from) == countNodes(to), "Wrong copy.");
 		  check(countEdges(from) == countEdges(to), "Wrong copy.");
 		  check(countArcs(from) == countArcs(to), "Wrong copy.");
+		}
 		int main() {
 		  digraph_copy_test();
 		  graph_copy_test();
 		  return 0;
+		}

test/heap_test.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-2011
 		 * 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 <iostream>
 		#include <fstream>
 		#include <string>
 		#include <vector>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/heap.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/dijkstra.h>
 		#include <lemon/maps.h>
 		#include <lemon/bin_heap.h>
 		#include <lemon/quad_heap.h>
 		#include <lemon/dheap.h>
 		#include <lemon/fib_heap.h>
 		#include <lemon/pairing_heap.h>
 		#include <lemon/radix_heap.h>
 		#include <lemon/binomial_heap.h>
 		#include <lemon/bucket_heap.h>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		typedef ListDigraph Digraph;
 		DIGRAPH_TYPEDEFS(Digraph);
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
 		  "9\n"
 		  "@arcs\n"
 		  "                label   capacity\n"
 		  "0       5       0       94\n"
 		  "3       9       1       11\n"
 		  "8       7       2       83\n"
 		  "1       2       3       94\n"
 		  "5       7       4       35\n"
 		  "7       4       5       84\n"
 		  "9       5       6       38\n"
 		  "0       4       7       96\n"
 		  "6       7       8       6\n"
 		  "3       1       9       27\n"
 		  "5       2       10      77\n"
 		  "5       6       11      69\n"
 		  "6       5       12      41\n"
 		  "4       6       13      70\n"
 		  "3       2       14      45\n"
 		  "7       9       15      93\n"
 		  "5       9       16      50\n"
 		  "9       0       17      94\n"
 		  "9       6       18      67\n"
 		  "0       9       19      86\n"
 		  "@attributes\n"
 		  "source 3\n";
 		int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
 		int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
 		int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
 		template <typename Heap>
 		void heapSortTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio(), "Wrong order in heap sort.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void heapIncreaseTest() {
 		  RangeMap<int> map(test_len, -1);
 		  Heap heap(map);
 		  std::vector<int> v(test_len);
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] = test_seq[i];
 		    heap.push(i, v[i]);
+		  }
 		  for (int i = 0; i < test_len; ++i) {
 		    v[i] += test_inc[i];
 		    heap.increase(i, v[i]);
+		  }
 		  std::sort(v.begin(), v.end());
 		  for (int i = 0; i < test_len; ++i) {
 		    check(v[i] == heap.prio(), "Wrong order in heap increase test.");
 		    heap.pop();
+		  }
+		}
 		template <typename Heap>
 		void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
 		                      Node source) {
 		  typename Dijkstra<Digraph, IntArcMap>::template SetStandardHeap<Heap>::
 		    Create dijkstra(digraph, length);
 		  dijkstra.run(source);
 		  for(ArcIt a(digraph); a != INVALID; ++a) {
 		    Node s = digraph.source(a);
 		    Node t = digraph.target(a);
 		    if (dijkstra.reached(s)) {
 		      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
 		             "Error in shortest path tree.");
+		    }
+		  }
 		  for(NodeIt n(digraph); n != INVALID; ++n) {
 		    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
 		      Arc a = dijkstra.predArc(n);
 		      Node s = digraph.source(a);
 		      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
 		             "Error in shortest path tree.");
+		    }
+		  }
+		}
 		int main() {
 		  typedef int Item;
 		  typedef int Prio;
 		  typedef RangeMap<int> ItemIntMap;
 		  Digraph digraph;
 		  IntArcMap length(digraph);
 		  Node source;
 		  std::istringstream input(test_lgf);
 		  digraphReader(digraph, input).
 		    arcMap("capacity", length).
 		    node("source", source).
 		    run();
 		  // BinHeap
+		  {
 		    typedef BinHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // QuadHeap
+		  {
 		    typedef QuadHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef QuadHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // DHeap
+		  {
 		    typedef DHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef DHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // FibHeap
+		  {
 		    typedef FibHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // PairingHeap
+		  {
 		    typedef PairingHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef PairingHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // RadixHeap
+		  {
 		    typedef RadixHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef RadixHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // BinomialHeap
+		  {
 		    typedef BinomialHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BinomialHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  // BucketHeap, SimpleBucketHeap
+		  {
 		    typedef BucketHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BucketHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
 		    typedef SimpleBucketHeap<ItemIntMap> SimpleIntHeap;
 		    heapSortTest<SimpleIntHeap>();
+		  }
+		  {
 		    typedef FibHeap<Prio, ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef FibHeap<Prio, IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
+		  {
 		    typedef RadixHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef RadixHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
+		  {
 		    typedef BucketHeap<ItemIntMap> IntHeap;
 		    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
 		    heapSortTest<IntHeap>();
 		    heapIncreaseTest<IntHeap>();
 		    typedef BucketHeap<IntNodeMap > NodeHeap;
 		    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
 		    dijkstraHeapTest<NodeHeap>(digraph, length, source);
+		  }
 		  return 0;
+		}

test/maps_test.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-2010
+		 * Copyright (C) 2003-2011
 		 * 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 <deque>
 		#include <set>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/maps.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/smart_graph.h>
 		#include <lemon/adaptors.h>
 		#include <lemon/dfs.h>
 		#include <algorithm>
 		#include "test_tools.h"
 		using namespace lemon;
 		using namespace lemon::concepts;
 		struct A {};
 		inline bool operator<(A, A) { return true; }
 		struct B {};
 		class C {
 		  int _x;
 		public:
 		  C(int x) : _x(x) {}
 		  int get() const { return _x; }
 		};
 		inline bool operator<(C c1, C c2) { return c1.get() < c2.get(); }
 		inline bool operator==(C c1, C c2) { return c1.get() == c2.get(); }
 		C createC(int x) { return C(x); }
 		template <typename T>
 		class Less {
 		  T _t;
 		public:
 		  Less(T t): _t(t) {}
 		  bool operator()(const T& t) const { return t < _t; }
 		};
 		class F {
 		public:
 		  typedef A argument_type;
 		  typedef B result_type;
 		  B operator()(const A&) const { return B(); }
 		private:
 		  F& operator=(const F&);
 		};
 		int func(A) { return 3; }
 		int binc(int a, B) { return a+1; }
 		template <typename T>
 		class Sum {
 		  T& _sum;
 		public:
 		  Sum(T& sum) : _sum(sum) {}
 		  void operator()(const T& t) { _sum += t; }
 		};
 		typedef ReadMap<A, double> DoubleMap;
 		typedef ReadWriteMap<A, double> DoubleWriteMap;
 		typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
 		typedef ReadMap<A, bool> BoolMap;
 		typedef ReadWriteMap<A, bool> BoolWriteMap;
 		typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
 		int main()
+		{
 		  // Map concepts
 		  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
 		  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
 		  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
 		  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
 		  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
 		  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
 		  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
 		  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
 		  // NullMap
+		  {
 		    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
 		    NullMap<A,B> map1;
 		    NullMap<A,B> map2 = map1;
 		    map1 = nullMap<A,B>();
+		  }
 		  // ConstMap
+		  {
 		    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
 		    checkConcept<ReadWriteMap<A,C>, ConstMap<A,C> >();
 		    ConstMap<A,B> map1;
 		    ConstMap<A,B> map2 = B();
 		    ConstMap<A,B> map3 = map1;
 		    map1 = constMap<A>(B());
 		    map1 = constMap<A,B>();
 		    map1.setAll(B());
 		    ConstMap<A,C> map4(C(1));
 		    ConstMap<A,C> map5 = map4;
 		    map4 = constMap<A>(C(2));
 		    map4.setAll(C(3));
 		    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
 		    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
 		    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
 		    ConstMap<A,Const<int,10> > map6;
 		    ConstMap<A,Const<int,10> > map7 = map6;
 		    map6 = constMap<A,int,10>();
 		    map7 = constMap<A,Const<int,10> >();
 		    check(map6[A()] == 10 && map7[A()] == 10,
 		          "Something is wrong with ConstMap");
+		  }
 		  // IdentityMap
+		  {
 		    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
 		    IdentityMap<A> map1;
 		    IdentityMap<A> map2 = map1;
 		    map1 = identityMap<A>();
 		    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
 		    check(identityMap<double>()[1.0] == 1.0 &&
 		          identityMap<double>()[3.14] == 3.14,
 		          "Something is wrong with IdentityMap");
+		  }
 		  // RangeMap
+		  {
 		    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
 		    RangeMap<B> map1;
 		    RangeMap<B> map2(10);
 		    RangeMap<B> map3(10,B());
 		    RangeMap<B> map4 = map1;
 		    RangeMap<B> map5 = rangeMap<B>();
 		    RangeMap<B> map6 = rangeMap<B>(10);
 		    RangeMap<B> map7 = rangeMap(10,B());
 		    checkConcept< ReferenceMap<int, double, double&, const double&>,
 		                  RangeMap<double> >();
 		    std::vector<double> v(10, 0);
 		    v[5] = 100;
 		    RangeMap<double> map8(v);
 		    RangeMap<double> map9 = rangeMap(v);
 		    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
 		          "Something is wrong with RangeMap");
+		  }
 		  // SparseMap
+		  {
 		    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
 		    SparseMap<A,B> map1;
 		    SparseMap<A,B> map2 = B();
 		    SparseMap<A,B> map3 = sparseMap<A,B>();
 		    SparseMap<A,B> map4 = sparseMap<A>(B());
 		    checkConcept< ReferenceMap<double, int, int&, const int&>,
 		                  SparseMap<double, int> >();
 		    std::map<double, int> m;
 		    SparseMap<double, int> map5(m);
 		    SparseMap<double, int> map6(m,10);
 		    SparseMap<double, int> map7 = sparseMap(m);
 		    SparseMap<double, int> map8 = sparseMap(m,10);
 		    check(map5[1.0] == 0 && map5[3.14] == 0 &&
 		          map6[1.0] == 10 && map6[3.14] == 10,
 		          "Something is wrong with SparseMap");
 		    map5[1.0] = map6[3.14] = 100;
 		    check(map5[1.0] == 100 && map5[3.14] == 0 &&
 		          map6[1.0] == 10 && map6[3.14] == 100,
 		          "Something is wrong with SparseMap");
+		  }
 		  // ComposeMap
+		  {
 		    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
 		    checkConcept<ReadMap<B,double>, CompMap>();
 		    CompMap map1 = CompMap(DoubleMap(),ReadMap<B,A>());
 		    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
 		    SparseMap<double, bool> m1(false); m1[3.14] = true;
 		    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
 		    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1],
 		          "Something is wrong with ComposeMap")
+		  }
 		  // CombineMap
+		  {
 		    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
 		    checkConcept<ReadMap<A,double>, CombMap>();
 		    CombMap map1 = CombMap(DoubleMap(), DoubleMap());
 		    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
 		    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
 		          "Something is wrong with CombineMap");
+		  }
 		  // FunctorToMap, MapToFunctor
+		  {
 		    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
 		    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
 		    FunctorToMap<F> map1;
 		    FunctorToMap<F> map2 = FunctorToMap<F>(F());
 		    B b = functorToMap(F())[A()];
 		    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
 		    MapToFunctor<ReadMap<A,B> > map =
 		      MapToFunctor<ReadMap<A,B> >(ReadMap<A,B>());
 		    check(functorToMap(&func)[A()] == 3,
 		          "Something is wrong with FunctorToMap");
 		    check(mapToFunctor(constMap<A,int>(2))(A()) == 2,
 		          "Something is wrong with MapToFunctor");
 		    check(mapToFunctor(functorToMap(&func))(A()) == 3 &&
 		          mapToFunctor(functorToMap(&func))[A()] == 3,
 		          "Something is wrong with FunctorToMap or MapToFunctor");
 		    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,
 		          "Something is wrong with FunctorToMap or MapToFunctor");
+		  }
 		  // ConvertMap
+		  {
 		    checkConcept<ReadMap<double,double>,
 		      ConvertMap<ReadMap<double, int>, double> >();
 		    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
 		    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
+		  }
 		  // ForkMap
+		  {
 		    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
 		    typedef RangeMap<double> RM;
 		    typedef SparseMap<int, double> SM;
 		    RM m1(10, -1);
 		    SM m2(-1);
 		    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();
 		    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();
 		    ForkMap<RM, SM> map1(m1,m2);
 		    ForkMap<SM, RM> map2 = forkMap(m2,m1);
 		    map2.set(5, 10);
 		    check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 &&
 		          m2[5] == 10 && map2[1] == -1 && map2[5] == 10,
 		          "Something is wrong with ForkMap");
+		  }
 		  // Arithmetic maps:
 		  // - AddMap, SubMap, MulMap, DivMap
 		  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap
 		  // - NegMap, NegWriteMap, AbsMap
+		  {
 		    checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();
 		    checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();
 		    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
 		    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
 		    ConstMap<int, double> c1(1.0), c2(3.14);
 		    IdentityMap<int> im;
 		    ConvertMap<IdentityMap<int>, double> id(im);
 		    check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0,
 		          "Something is wrong with AddMap");
 		    check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,
 		          "Something is wrong with SubMap");
 		    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28,
 		          "Something is wrong with MulMap");
 		    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57,
 		          "Something is wrong with DivMap");
 		    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
 		    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
 		    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();
 		    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();
 		    checkConcept<DoubleMap, NegMap<DoubleMap> >();
 		    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();
 		    checkConcept<DoubleMap, AbsMap<DoubleMap> >();
 		    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,
 		          "Something is wrong with ShiftMap");
 		    check(shiftWriteMap(id, 2.0)[1] == 3.0 &&
 		          shiftWriteMap(id, 2.0)[10] == 12.0,
 		          "Something is wrong with ShiftWriteMap");
 		    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,
 		          "Something is wrong with ScaleMap");
 		    check(scaleWriteMap(id, 2.0)[1] == 2.0 &&
 		          scaleWriteMap(id, 2.0)[10] == 20.0,
 		          "Something is wrong with ScaleWriteMap");
 		    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,
 		          "Something is wrong with NegMap");
 		    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,
 		          "Something is wrong with NegWriteMap");
 		    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,
 		          "Something is wrong with AbsMap");
+		  }
 		  // Logical maps:
 		  // - TrueMap, FalseMap
 		  // - AndMap, OrMap
 		  // - NotMap, NotWriteMap
 		  // - EqualMap, LessMap
+		  {
 		    checkConcept<BoolMap, TrueMap<A> >();
 		    checkConcept<BoolMap, FalseMap<A> >();
 		    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
 		    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
 		    checkConcept<BoolMap, NotMap<BoolMap> >();
 		    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
 		    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
 		    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
 		    TrueMap<int> tm;
 		    FalseMap<int> fm;
 		    RangeMap<bool> rm(2);
 		    rm[0] = true; rm[1] = false;
 		    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] &&
 		          !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
 		          "Something is wrong with AndMap");
 		    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] &&
 		          orMap(fm,rm)[0] && !orMap(fm,rm)[1],
 		          "Something is wrong with OrMap");
 		    check(!notMap(rm)[0] && notMap(rm)[1],
 		          "Something is wrong with NotMap");
 		    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1],
 		          "Something is wrong with NotWriteMap");
 		    ConstMap<int, double> cm(2.0);
 		    IdentityMap<int> im;
 		    ConvertMap<IdentityMap<int>, double> id(im);
 		    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
 		          "Something is wrong with LessMap");
 		    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
 		          "Something is wrong with EqualMap");
+		  }
 		  // LoggerBoolMap
+		  {
 		    typedef std::vector<int> vec;
 		    checkConcept<WriteMap<int, bool>, LoggerBoolMap<vec::iterator> >();
 		    checkConcept<WriteMap<int, bool>,
 		                 LoggerBoolMap<std::back_insert_iterator<vec> > >();
 		    vec v1;
 		    vec v2(10);
 		    LoggerBoolMap<std::back_insert_iterator<vec> >
 		      map1(std::back_inserter(v1));
 		    LoggerBoolMap<vec::iterator> map2(v2.begin());
 		    map1.set(10, false);
 		    map1.set(20, true);   map2.set(20, true);
 		    map1.set(30, false);  map2.set(40, false);
 		    map1.set(50, true);   map2.set(50, true);
 		    map1.set(60, true);   map2.set(60, true);
 		    check(v1.size() == 3 && v2.size() == 10 &&
 		          v1[0]==20 && v1[1]==50 && v1[2]==60 &&
 		          v2[0]==20 && v2[1]==50 && v2[2]==60,
 		          "Something is wrong with LoggerBoolMap");
 		    int i = 0;
 		    for ( LoggerBoolMap<vec::iterator>::Iterator it = map2.begin();
 		          it != map2.end(); ++it )
 		      check(v1[i++] == *it, "Something is wrong with LoggerBoolMap");
 		    typedef ListDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    Graph gr;
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    Node n3 = gr.addNode();
 		    gr.addArc(n3, n0);
 		    gr.addArc(n3, n2);
 		    gr.addArc(n0, n2);
 		    gr.addArc(n2, n1);
 		    gr.addArc(n0, n1);
+		    {
 		      std::vector<Node> v;
 		      dfs(gr).processedMap(loggerBoolMap(std::back_inserter(v))).run();
 		      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
 		            "Something is wrong with LoggerBoolMap");
+		    }
+		    {
 		      std::vector<Node> v(countNodes(gr));
 		      dfs(gr).processedMap(loggerBoolMap(v.begin())).run();
 		      check(v.size()==4 && v[0]==n1 && v[1]==n2 && v[2]==n0 && v[3]==n3,
 		            "Something is wrong with LoggerBoolMap");
+		    }
+		  }
 		  // IdMap, RangeIdMap
+		  {
 		    typedef ListDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadMap<Node, int>, IdMap<Graph, Node> >();
 		    checkConcept<ReadMap<Arc, int>, IdMap<Graph, Arc> >();
 		    checkConcept<ReadMap<Node, int>, RangeIdMap<Graph, Node> >();
 		    checkConcept<ReadMap<Arc, int>, RangeIdMap<Graph, Arc> >();
 		    Graph gr;
 		    IdMap<Graph, Node> nmap(gr);
 		    IdMap<Graph, Arc> amap(gr);
 		    RangeIdMap<Graph, Node> nrmap(gr);
 		    RangeIdMap<Graph, Arc> armap(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    Arc a0 = gr.addArc(n0, n1);
 		    Arc a1 = gr.addArc(n0, n2);
 		    Arc a2 = gr.addArc(n2, n1);
 		    Arc a3 = gr.addArc(n2, n0);
 		    check(nmap[n0] == gr.id(n0) && nmap(gr.id(n0)) == n0, "Wrong IdMap");
 		    check(nmap[n1] == gr.id(n1) && nmap(gr.id(n1)) == n1, "Wrong IdMap");
 		    check(nmap[n2] == gr.id(n2) && nmap(gr.id(n2)) == n2, "Wrong IdMap");
 		    check(amap[a0] == gr.id(a0) && amap(gr.id(a0)) == a0, "Wrong IdMap");
 		    check(amap[a1] == gr.id(a1) && amap(gr.id(a1)) == a1, "Wrong IdMap");
 		    check(amap[a2] == gr.id(a2) && amap(gr.id(a2)) == a2, "Wrong IdMap");
 		    check(amap[a3] == gr.id(a3) && amap(gr.id(a3)) == a3, "Wrong IdMap");
 		    check(nmap.inverse()[gr.id(n0)] == n0, "Wrong IdMap::InverseMap");
 		    check(amap.inverse()[gr.id(a0)] == a0, "Wrong IdMap::InverseMap");
 		    check(nrmap.size() == 3 && armap.size() == 4,
 		          "Wrong RangeIdMap::size()");
 		    check(nrmap[n0] == 0 && nrmap(0) == n0, "Wrong RangeIdMap");
 		    check(nrmap[n1] == 1 && nrmap(1) == n1, "Wrong RangeIdMap");
 		    check(nrmap[n2] == 2 && nrmap(2) == n2, "Wrong RangeIdMap");
 		    check(armap[a0] == 0 && armap(0) == a0, "Wrong RangeIdMap");
 		    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
 		    check(armap[a2] == 2 && armap(2) == a2, "Wrong RangeIdMap");
 		    check(armap[a3] == 3 && armap(3) == a3, "Wrong RangeIdMap");
 		    check(nrmap.inverse()[0] == n0, "Wrong RangeIdMap::InverseMap");
 		    check(armap.inverse()[0] == a0, "Wrong RangeIdMap::InverseMap");
 		    gr.erase(n1);
 		    if (nrmap[n0] == 1) nrmap.swap(n0, n2);
 		    nrmap.swap(n2, n0);
 		    if (armap[a1] == 1) armap.swap(a1, a3);
 		    armap.swap(a3, a1);
 		    check(nrmap.size() == 2 && armap.size() == 2,
 		          "Wrong RangeIdMap::size()");
 		    check(nrmap[n0] == 1 && nrmap(1) == n0, "Wrong RangeIdMap");
 		    check(nrmap[n2] == 0 && nrmap(0) == n2, "Wrong RangeIdMap");
 		    check(armap[a1] == 1 && armap(1) == a1, "Wrong RangeIdMap");
 		    check(armap[a3] == 0 && armap(0) == a3, "Wrong RangeIdMap");
 		    check(nrmap.inverse()[0] == n2, "Wrong RangeIdMap::InverseMap");
 		    check(armap.inverse()[0] == a3, "Wrong RangeIdMap::InverseMap");
+		  }
 		  // SourceMap, TargetMap, ForwardMap, BackwardMap, InDegMap, OutDegMap
+		  {
 		    typedef ListGraph Graph;
 		    GRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadMap<Arc, Node>, SourceMap<Graph> >();
 		    checkConcept<ReadMap<Arc, Node>, TargetMap<Graph> >();
 		    checkConcept<ReadMap<Edge, Arc>, ForwardMap<Graph> >();
 		    checkConcept<ReadMap<Edge, Arc>, BackwardMap<Graph> >();
 		    checkConcept<ReadMap<Node, int>, InDegMap<Graph> >();
 		    checkConcept<ReadMap<Node, int>, OutDegMap<Graph> >();
 		    Graph gr;
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    gr.addEdge(n0,n1);
 		    gr.addEdge(n1,n2);
 		    gr.addEdge(n0,n2);
 		    gr.addEdge(n2,n1);
 		    gr.addEdge(n1,n2);
 		    gr.addEdge(n0,n1);
 		    for (EdgeIt e(gr); e != INVALID; ++e) {
 		      check(forwardMap(gr)[e] == gr.direct(e, true), "Wrong ForwardMap");
 		      check(backwardMap(gr)[e] == gr.direct(e, false), "Wrong BackwardMap");
+		    }
 		    check(mapCompare(gr,
 		          sourceMap(orienter(gr, constMap<Edge, bool>(true))),
 		          targetMap(orienter(gr, constMap<Edge, bool>(false)))),
 		          "Wrong SourceMap or TargetMap");
 		    typedef Orienter<Graph, const ConstMap<Edge, bool> > Digraph;
 		    Digraph dgr(gr, constMap<Edge, bool>(true));
 		    OutDegMap<Digraph> odm(dgr);
 		    InDegMap<Digraph> idm(dgr);
 		    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 1, "Wrong OutDegMap");
 		    check(idm[n0] == 0 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
 		    gr.addEdge(n2, n0);
 		    check(odm[n0] == 3 && odm[n1] == 2 && odm[n2] == 2, "Wrong OutDegMap");
 		    check(idm[n0] == 1 && idm[n1] == 3 && idm[n2] == 3, "Wrong InDegMap");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef ListDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    checkConcept<ReadWriteMap<Node, bool>,
 		                 CrossRefMap<Graph, Node, bool> >();
 		    checkConcept<ReadWriteMap<Node, double>,
 		                 CrossRefMap<Graph, Node, double> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    map.set(n0, 'A');
 		    map.set(n1, 'B');
 		    map.set(n2, 'C');
 		    check(map[n0] == 'A' && map('A') == n0 && map.inverse()['A'] == n0,
 		          "Wrong CrossRefMap");
 		    check(map[n1] == 'B' && map('B') == n1 && map.inverse()['B'] == n1,
 		          "Wrong CrossRefMap");
 		    check(map[n2] == 'C' && map('C') == n2 && map.inverse()['C'] == n2,
 		          "Wrong CrossRefMap");
 		    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
 		          "Wrong CrossRefMap::count()");
 		    CRMap::ValueIt it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
 		    map.set(n2, 'A');
 		    check(map[n0] == 'A' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n0 && map.inverse()['A'] == n0, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == INVALID && map.inverse()['C'] == INVALID,
 		          "Wrong CrossRefMap");
 		    check(map.count('A') == 2 && map.count('B') == 1 && map.count('C') == 0,
 		          "Wrong CrossRefMap::count()");
 		    it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'A' && *it++ == 'B' &&
 		          it == map.endValue(), "Wrong value iterator");
 		    map.set(n0, 'C');
 		    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
 		    check(map.count('A') == 1 && map.count('B') == 1 && map.count('C') == 1,
 		          "Wrong CrossRefMap::count()");
 		    it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
+		  }
 		  // CrossRefMap
+		  {
 		    typedef SmartDigraph Graph;
 		    DIGRAPH_TYPEDEFS(Graph);
 		    checkConcept<ReadWriteMap<Node, int>,
 		                 CrossRefMap<Graph, Node, int> >();
 		    Graph gr;
 		    typedef CrossRefMap<Graph, Node, char> CRMap;
 		    typedef CRMap::ValueIterator ValueIt;
 		    CRMap map(gr);
 		    Node n0 = gr.addNode();
 		    Node n1 = gr.addNode();
 		    Node n2 = gr.addNode();
 		    map.set(n0, 'A');
 		    map.set(n1, 'B');
 		    map.set(n2, 'C');
 		    map.set(n2, 'A');
 		    map.set(n0, 'C');
 		    check(map[n0] == 'C' && map[n1] == 'B' && map[n2] == 'A',
 		          "Wrong CrossRefMap");
 		    check(map('A') == n2 && map.inverse()['A'] == n2, "Wrong CrossRefMap");
 		    check(map('B') == n1 && map.inverse()['B'] == n1, "Wrong CrossRefMap");
 		    check(map('C') == n0 && map.inverse()['C'] == n0, "Wrong CrossRefMap");
 		    ValueIt it = map.beginValue();
 		    check(*it++ == 'A' && *it++ == 'B' && *it++ == 'C' &&
 		          it == map.endValue(), "Wrong value iterator");
+		  }
 		  // Iterable bool map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableBoolMap<SmartGraph, SmartGraph::Node> Ibm;
 		    checkConcept<ReferenceMap<Item, bool, bool&, const bool&>, Ibm>();
 		    const int num = 10;
 		    Graph g;
 		    Ibm map0(g, true);
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Ibm map1(g, true);
 		    int n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)], "Wrong TrueIt");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    n = 0;
 		    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
 		        ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    check(Ibm::FalseIt(map1) == INVALID, "Wrong FalseIt");
 		    check(Ibm::ItemIt(map1, false) == INVALID, "Wrong ItemIt for false");
 		    map1[items[5]] = true;
 		    n = 0;
 		    for (Ibm::ItemIt it(map1, true); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong ItemIt for true");
 		        ++n;
+		    }
 		    check(n == num, "Wrong number");
 		    map1[items[num / 2]] = false;
 		    check(map1[items[num / 2]] == false, "Wrong map value");
 		    n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
 		        ++n;
+		    }
 		    check(n == num - 1, "Wrong number");
 		    n = 0;
 		    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
 		        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
 		        ++n;
+		    }
 		    check(n == 1, "Wrong number");
 		    map1[items[0]] = false;
 		    check(map1[items[0]] == false, "Wrong map value");
 		    map1[items[num - 1]] = false;
 		    check(map1[items[num - 1]] == false, "Wrong map value");
 		    n = 0;
 		    for (Ibm::TrueIt it(map1); it != INVALID; ++it) {
 		        check(map1[static_cast<Item>(it)], "Wrong TrueIt for true");
 		        ++n;
+		    }
 		    check(n == num - 3, "Wrong number");
 		    check(map1.trueNum() == num - 3, "Wrong number");
 		    n = 0;
 		    for (Ibm::FalseIt it(map1); it != INVALID; ++it) {
 		        check(!map1[static_cast<Item>(it)], "Wrong FalseIt for true");
 		        ++n;
+		    }
 		    check(n == 3, "Wrong number");
 		    check(map1.falseNum() == 3, "Wrong number");
+		  }
 		  // Iterable int map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableIntMap<SmartGraph, SmartGraph::Node> Iim;
 		    checkConcept<ReferenceMap<Item, int, int&, const int&>, Iim>();
 		    const int num = 10;
 		    Graph g;
 		    Iim map0(g, 0);
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Iim map1(g);
 		    check(map1.size() == 0, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i;
+		    }
 		    check(map1.size() == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Iim::ItemIt it(map1, i);
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1[items[i]] = i % 2;
+		    }
 		    check(map1.size() == 2, "Wrong size");
 		    int n = 0;
 		    for (Iim::ItemIt it(map1, 0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Iim::ItemIt it(map1, 1); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  // Iterable value map
+		  {
 		    typedef SmartGraph Graph;
 		    typedef SmartGraph::Node Item;
 		    typedef IterableValueMap<SmartGraph, SmartGraph::Node, double> Ivm;
 		    checkConcept<ReadWriteMap<Item, double>, Ivm>();
 		    const int num = 10;
 		    Graph g;
 		    Ivm map0(g, 0.0);
 		    std::vector<Item> items;
 		    for (int i = 0; i < num; ++i) {
 		      items.push_back(g.addNode());
+		    }
 		    Ivm map1(g, 0.0);
 		    check(distance(map1.beginValue(), map1.endValue()) == 1, "Wrong size");
 		    check(*map1.beginValue() == 0.0, "Wrong value");
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == num, "Wrong size");
 		    for (int i = 0; i < num; ++i) {
 		      Ivm::ItemIt it(map1, static_cast<double>(i));
 		      check(static_cast<Item>(it) == items[i], "Wrong value");
 		      ++it;
 		      check(static_cast<Item>(it) == INVALID, "Wrong value");
+		    }
 		    for (Ivm::ValueIt vit = map1.beginValue();
 		         vit != map1.endValue(); ++vit) {
 		      check(map1[static_cast<Item>(Ivm::ItemIt(map1, *vit))] == *vit,
 		            "Wrong ValueIt");
+		    }
 		    for (int i = 0; i < num; ++i) {
 		      map1.set(items[i], static_cast<double>(i % 2));
+		    }
 		    check(distance(map1.beginValue(), map1.endValue()) == 2, "Wrong size");
 		    int n = 0;
 		    for (Ivm::ItemIt it(map1, 0.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 0.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == (num + 1) / 2, "Wrong number");
 		    for (Ivm::ItemIt it(map1, 1.0); it != INVALID; ++it) {
 		      check(map1[static_cast<Item>(it)] == 1.0, "Wrong value");
 		      ++n;
+		    }
 		    check(n == num, "Wrong number");
+		  }
 		  // Graph map utilities:
 		  // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		  // mapFind(), mapFindIf(), mapCount(), mapCountIf()
 		  // mapCopy(), mapCompare(), mapFill()
+		  {
 		    DIGRAPH_TYPEDEFS(SmartDigraph);
 		    SmartDigraph g;
 		    Node n1 = g.addNode();
 		    Node n2 = g.addNode();
 		    Node n3 = g.addNode();
 		    SmartDigraph::NodeMap<int> map1(g);
 		    SmartDigraph::ArcMap<char> map2(g);
 		    ConstMap<Node, A> cmap1 = A();
 		    ConstMap<Arc, C> cmap2 = C(0);
 		    map1[n1] = 10;
 		    map1[n2] = 5;
 		    map1[n3] = 12;
 		    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		    check(mapMin(g, map1) == n2, "Wrong mapMin()");
 		    check(mapMax(g, map1) == n3, "Wrong mapMax()");
 		    check(mapMin(g, map1, std::greater<int>()) == n3, "Wrong mapMin()");
 		    check(mapMax(g, map1, std::greater<int>()) == n2, "Wrong mapMax()");
 		    check(mapMinValue(g, map1) == 5, "Wrong mapMinValue()");
 		    check(mapMaxValue(g, map1) == 12, "Wrong mapMaxValue()");
 		    check(mapMin(g, map2) == INVALID, "Wrong mapMin()");
 		    check(mapMax(g, map2) == INVALID, "Wrong mapMax()");
 		    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
 		    check(mapMax(g, cmap2) == INVALID, "Wrong mapMax()");
 		    Arc a1 = g.addArc(n1, n2);
 		    Arc a2 = g.addArc(n1, n3);
 		    Arc a3 = g.addArc(n2, n3);
 		    Arc a4 = g.addArc(n3, n1);
 		    map2[a1] = 'b';
 		    map2[a2] = 'a';
 		    map2[a3] = 'b';
 		    map2[a4] = 'c';
 		    // mapMin(), mapMax(), mapMinValue(), mapMaxValue()
 		    check(mapMin(g, map2) == a2, "Wrong mapMin()");
 		    check(mapMax(g, map2) == a4, "Wrong mapMax()");
 		    check(mapMin(g, map2, std::greater<int>()) == a4, "Wrong mapMin()");
 		    check(mapMax(g, map2, std::greater<int>()) == a2, "Wrong mapMax()");
 		    check(mapMinValue(g, map2, std::greater<int>()) == 'c',
 		          "Wrong mapMinValue()");
 		    check(mapMaxValue(g, map2, std::greater<int>()) == 'a',
 		          "Wrong mapMaxValue()");
 		    check(mapMin(g, cmap1) != INVALID, "Wrong mapMin()");
 		    check(mapMax(g, cmap2) != INVALID, "Wrong mapMax()");
 		    check(mapMaxValue(g, cmap2) == C(0), "Wrong mapMaxValue()");
 		    check(mapMin(g, composeMap(functorToMap(&createC), map2)) == a2,
 		          "Wrong mapMin()");
 		    check(mapMax(g, composeMap(functorToMap(&createC), map2)) == a4,
 		          "Wrong mapMax()");
 		    check(mapMinValue(g, composeMap(functorToMap(&createC), map2)) == C('a'),
 		          "Wrong mapMinValue()");
 		    check(mapMaxValue(g, composeMap(functorToMap(&createC), map2)) == C('c'),
 		          "Wrong mapMaxValue()");
 		    // mapFind(), mapFindIf()
 		    check(mapFind(g, map1, 5) == n2, "Wrong mapFind()");
 		    check(mapFind(g, map1, 6) == INVALID, "Wrong mapFind()");
 		    check(mapFind(g, map2, 'a') == a2, "Wrong mapFind()");
 		    check(mapFind(g, map2, 'e') == INVALID, "Wrong mapFind()");
 		    check(mapFind(g, cmap2, C(0)) == ArcIt(g), "Wrong mapFind()");
 		    check(mapFind(g, cmap2, C(1)) == INVALID, "Wrong mapFind()");
 		    check(mapFindIf(g, map1, Less<int>(7)) == n2,
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map1, Less<int>(5)) == INVALID,
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map2, Less<char>('d')) == ArcIt(g),
 		          "Wrong mapFindIf()");
 		    check(mapFindIf(g, map2, Less<char>('a')) == INVALID,
 		          "Wrong mapFindIf()");
 		    // mapCount(), mapCountIf()
 		    check(mapCount(g, map1, 5) == 1, "Wrong mapCount()");
 		    check(mapCount(g, map1, 6) == 0, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'a') == 1, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'b') == 2, "Wrong mapCount()");
 		    check(mapCount(g, map2, 'e') == 0, "Wrong mapCount()");
 		    check(mapCount(g, cmap2, C(0)) == 4, "Wrong mapCount()");
 		    check(mapCount(g, cmap2, C(1)) == 0, "Wrong mapCount()");
 		    check(mapCountIf(g, map1, Less<int>(11)) == 2,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map1, Less<int>(13)) == 3,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map1, Less<int>(5)) == 0,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('d')) == 4,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('c')) == 3,
 		          "Wrong mapCountIf()");
 		    check(mapCountIf(g, map2, Less<char>('a')) == 0,
 		          "Wrong mapCountIf()");
 		    // MapIt, ConstMapIt
 		/*
 		These tests can be used after applying bugfix #330
 		    typedef SmartDigraph::NodeMap<int>::MapIt MapIt;
 		    typedef SmartDigraph::NodeMap<int>::ConstMapIt ConstMapIt;
 		    check(*std::min_element(MapIt(map1), MapIt(INVALID)) == 5,
 		          "Wrong NodeMap<>::MapIt");
 		    check(*std::max_element(ConstMapIt(map1), ConstMapIt(INVALID)) == 12,
 		          "Wrong NodeMap<>::MapIt");
 		    int sum = 0;
 		    std::for_each(MapIt(map1), MapIt(INVALID), Sum<int>(sum));
 		    check(sum == 27, "Wrong NodeMap<>::MapIt");
 		    std::for_each(ConstMapIt(map1), ConstMapIt(INVALID), Sum<int>(sum));
 		    check(sum == 54, "Wrong NodeMap<>::ConstMapIt");
 		*/
 		    // mapCopy(), mapCompare(), mapFill()
 		    check(mapCompare(g, map1, map1), "Wrong mapCompare()");
 		    check(mapCompare(g, cmap2, cmap2), "Wrong mapCompare()");
 		    check(mapCompare(g, map1, shiftMap(map1, 0)), "Wrong mapCompare()");
 		    check(mapCompare(g, map2, scaleMap(map2, 1)), "Wrong mapCompare()");
 		    check(!mapCompare(g, map1, shiftMap(map1, 1)), "Wrong mapCompare()");
 		    SmartDigraph::NodeMap<int> map3(g, 0);
 		    SmartDigraph::ArcMap<char> map4(g, 'a');
 		    check(!mapCompare(g, map1, map3), "Wrong mapCompare()");
 		    check(!mapCompare(g, map2, map4), "Wrong mapCompare()");
 		    mapCopy(g, map1, map3);
 		    mapCopy(g, map2, map4);
 		    check(mapCompare(g, map1, map3), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(g, map2, map4), "Wrong mapCompare() or mapCopy()");
 		    Undirector<SmartDigraph> ug(g);
 		    Undirector<SmartDigraph>::EdgeMap<char> umap1(ug, 'x');
 		    Undirector<SmartDigraph>::ArcMap<double> umap2(ug, 3.14);
 		    check(!mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(g, map2, umap1);
 		    check(mapCompare(g, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(g, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(ug, map2, umap1), "Wrong mapCompare() or mapCopy()");
 		    check(mapCompare(ug, umap1, map2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(g, map2, umap1);
 		    mapCopy(g, umap1, map2);
 		    mapCopy(ug, map2, umap1);
 		    mapCopy(ug, umap1, map2);
 		    check(!mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
 		    mapCopy(ug, umap1, umap2);
 		    check(mapCompare(ug, umap1, umap2), "Wrong mapCompare() or mapCopy()");
 		    check(!mapCompare(g, map1, constMap<Node>(2)), "Wrong mapCompare()");
 		    mapFill(g, map1, 2);
 		    check(mapCompare(g, constMap<Node>(2), map1), "Wrong mapFill()");
 		    check(!mapCompare(g, map2, constMap<Arc>('z')), "Wrong mapCompare()");
 		    mapCopy(g, constMap<Arc>('z'), map2);
 		    check(mapCompare(g, constMap<Arc>('z'), map2), "Wrong mapCopy()");
+		  }
 		  return 0;
+		}

test/preflow_test.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-2010
+		 * Copyright (C) 2003-2011
 		 * 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 <iostream>
 		#include "test_tools.h"
 		#include <lemon/smart_graph.h>
 		#include <lemon/preflow.h>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/maps.h>
 		#include <lemon/lgf_reader.h>
 		#include <lemon/elevator.h>
 		using namespace lemon;
 		char test_lgf[] =
 		  "@nodes\n"
 		  "label\n"
 		  "0\n"
 		  "1\n"
 		  "2\n"
 		  "3\n"
 		  "4\n"
 		  "5\n"
 		  "6\n"
 		  "7\n"
 		  "8\n"
 		  "9\n"
 		  "@arcs\n"
 		  "    label capacity\n"
 		  "0 1 0     20\n"
 		  "0 2 1     0\n"
 		  "1 1 2     3\n"
 		  "1 2 3     8\n"
 		  "1 3 4     8\n"
 		  "2 5 5     5\n"
 		  "3 2 6     5\n"
 		  "3 5 7     5\n"
 		  "3 6 8     5\n"
 		  "4 3 9     3\n"
 		  "5 7 10    3\n"
 		  "5 6 11    10\n"
 		  "5 8 12    10\n"
 		  "6 8 13    8\n"
 		  "8 9 14    20\n"
 		  "8 1 15    5\n"
 		  "9 5 16    5\n"
 		  "@attributes\n"
 		  "source 1\n"
 		  "target 8\n";
 		void checkPreflowCompile()
+		{
 		  typedef int VType;
 		  typedef concepts::Digraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::Arc Arc;
 		  typedef concepts::ReadMap<Arc,VType> CapMap;
 		  typedef concepts::ReadWriteMap<Arc,VType> FlowMap;
 		  typedef concepts::WriteMap<Node,bool> CutMap;
 		  typedef Elevator<Digraph, Digraph::Node> Elev;
 		  typedef LinkedElevator<Digraph, Digraph::Node> LinkedElev;
 		  Digraph g;
 		  Node n;
 		  Arc e;
 		  CapMap cap;
 		  FlowMap flow;
 		  CutMap cut;
 		  VType v;
 		  bool b;
 		  typedef Preflow<Digraph, CapMap>
 		            ::SetFlowMap<FlowMap>
 		            ::SetElevator<Elev>
 		            ::SetStandardElevator<LinkedElev>
 		            ::Create PreflowType;
 		  PreflowType preflow_test(g, cap, n, n);
 		  const PreflowType& const_preflow_test = preflow_test;
 		  const PreflowType::Elevator& elev = const_preflow_test.elevator();
 		  preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev));
 		  PreflowType::Tolerance tol = const_preflow_test.tolerance();
 		  preflow_test.tolerance(tol);
 		  preflow_test
 		    .capacityMap(cap)
 		    .flowMap(flow)
 		    .source(n)
 		    .target(n);
 		  preflow_test.init();
 		  preflow_test.init(cap);
 		  preflow_test.startFirstPhase();
 		  preflow_test.startSecondPhase();
 		  preflow_test.run();
 		  preflow_test.runMinCut();
 		  v = const_preflow_test.flowValue();
 		  v = const_preflow_test.flow(e);
 		  const FlowMap& fm = const_preflow_test.flowMap();
 		  b = const_preflow_test.minCut(n);
 		  const_preflow_test.minCutMap(cut);
 		  ignore_unused_variable_warning(fm);
+		}
 		int cutValue (const SmartDigraph& g,
 		              const SmartDigraph::NodeMap<bool>& cut,
 		              const SmartDigraph::ArcMap<int>& cap) {
 		  int c=0;
 		  for(SmartDigraph::ArcIt e(g); e!=INVALID; ++e) {
 		    if (cut[g.source(e)] && !cut[g.target(e)]) c+=cap[e];
+		  }
 		  return c;
+		}
 		bool checkFlow(const SmartDigraph& g,
 		               const SmartDigraph::ArcMap<int>& flow,
 		               const SmartDigraph::ArcMap<int>& cap,
 		               SmartDigraph::Node s, SmartDigraph::Node t) {
 		  for (SmartDigraph::ArcIt e(g); e != INVALID; ++e) {
 		    if (flow[e] < 0 || flow[e] > cap[e]) return false;
+		  }
 		  for (SmartDigraph::NodeIt n(g); n != INVALID; ++n) {
 		    if (n == s || n == t) continue;
 		    int sum = 0;
 		    for (SmartDigraph::OutArcIt e(g, n); e != INVALID; ++e) {
 		      sum += flow[e];
+		    }
 		    for (SmartDigraph::InArcIt e(g, n); e != INVALID; ++e) {
 		      sum -= flow[e];
+		    }
 		    if (sum != 0) return false;
+		  }
 		  return true;
+		}
 		void initFlowTest()
+		{
 		  DIGRAPH_TYPEDEFS(SmartDigraph);
 		  SmartDigraph g;
 		  SmartDigraph::ArcMap<int> cap(g),iflow(g);
 		  Node s=g.addNode(); Node t=g.addNode();
 		  Node n1=g.addNode(); Node n2=g.addNode();
 		  Arc a;
 		  a=g.addArc(s,n1); cap[a]=20; iflow[a]=20;
 		  a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0;
 		  a=g.addArc(n2,t); cap[a]=20; iflow[a]=0;
 		  Preflow<SmartDigraph> pre(g,cap,s,t);
 		  pre.init(iflow);
 		  pre.startFirstPhase();
 		  check(pre.flowValue() == 10, "The incorrect max flow value.");
 		  check(pre.minCut(s), "Wrong min cut (Node s).");
 		  check(pre.minCut(n1), "Wrong min cut (Node n1).");
 		  check(!pre.minCut(n2), "Wrong min cut (Node n2).");
 		  check(!pre.minCut(t), "Wrong min cut (Node t).");
+		}
 		int main() {
 		  typedef SmartDigraph Digraph;
 		  typedef Digraph::Node Node;
 		  typedef Digraph::NodeIt NodeIt;
 		  typedef Digraph::ArcIt ArcIt;
 		  typedef Digraph::ArcMap<int> CapMap;
 		  typedef Digraph::ArcMap<int> FlowMap;
 		  typedef Digraph::NodeMap<bool> CutMap;
 		  typedef Preflow<Digraph, CapMap> PType;
 		  Digraph g;
 		  Node s, t;
 		  CapMap cap(g);
 		  std::istringstream input(test_lgf);
 		  DigraphReader<Digraph>(g,input).
 		    arcMap("capacity", cap).
 		    node("source",s).
 		    node("target",t).
 		    run();
 		  PType preflow_test(g, cap, s, t);
 		  preflow_test.run();
 		  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
 		        "The flow is not feasible.");
 		  CutMap min_cut(g);
 		  preflow_test.minCutMap(min_cut);
 		  int min_cut_value=cutValue(g,min_cut,cap);
 		  check(preflow_test.flowValue() == min_cut_value,
 		        "The max flow value is not equal to the three min cut values.");
 		  FlowMap flow(g);
 		  for(ArcIt e(g); e!=INVALID; ++e) flow[e] = preflow_test.flowMap()[e];
 		  int flow_value=preflow_test.flowValue();
 		  for(ArcIt e(g); e!=INVALID; ++e) cap[e]=2*cap[e];
 		  preflow_test.init(flow);
 		  preflow_test.startFirstPhase();
 		  CutMap min_cut1(g);
 		  preflow_test.minCutMap(min_cut1);
 		  min_cut_value=cutValue(g,min_cut1,cap);
 		  check(preflow_test.flowValue() == min_cut_value &&
 		        min_cut_value == 2*flow_value,
 		        "The max flow value or the min cut value is wrong.");
 		  preflow_test.startSecondPhase();
 		  check(checkFlow(g, preflow_test.flowMap(), cap, s, t),
 		        "The flow is not feasible.");
 		  CutMap min_cut2(g);
 		  preflow_test.minCutMap(min_cut2);
 		  min_cut_value=cutValue(g,min_cut2,cap);
 		  check(preflow_test.flowValue() == min_cut_value &&
 		        min_cut_value == 2*flow_value,
 		        "The max flow value or the three min cut values were not doubled");
 		  preflow_test.flowMap(flow);
 		  NodeIt tmp1(g,s);
 		  ++tmp1;
 		  if ( tmp1 != INVALID ) s=tmp1;
 		  NodeIt tmp2(g,t);
 		  ++tmp2;
 		  if ( tmp2 != INVALID ) t=tmp2;
 		  preflow_test.source(s);
 		  preflow_test.target(t);
 		  preflow_test.run();
 		  CutMap min_cut3(g);
 		  preflow_test.minCutMap(min_cut3);
 		  min_cut_value=cutValue(g,min_cut3,cap);
 		  check(preflow_test.flowValue() == min_cut_value,
 		        "The max flow value or the three min cut values are incorrect.");
 		  initFlowTest();
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account