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 27 insertions and 27 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/lgf_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;
+		    }

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);

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)
 		      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/lgf_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-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/list_graph.h>
#include <lemon/lgf_reader.h>
#include "test_tools.h"

using namespace lemon;

char test_lgf[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "@arcs\n"
  "     label\n"
  "0 1  0\n"
  "1 0  1\n"
  "@attributes\n"
  "source 0\n"
  "target 1\n";

char test_lgf_nomap[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "@arcs\n"
  "     -\n"
  "0 1\n";

char test_lgf_bad1[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "@arcs\n"
  "     - another\n"
  "0 1\n";

char test_lgf_bad2[] =
  "@nodes\n"
  "label\n"
  "0\n"
  "1\n"
  "@arcs\n"
  "     label -\n"
  "0 1\n";


int main() 
int main()
{
  {
    ListDigraph d; 
    ListDigraph d;
    ListDigraph::Node s,t;
    ListDigraph::ArcMap<int> label(d);
    std::istringstream input(test_lgf);
    digraphReader(d, input).
      node("source", s).
      node("target", t).
      arcMap("label", label).
      run();
    check(countNodes(d) == 2,"There should be 2 nodes");
    check(countArcs(d) == 2,"There should be 2 arcs");
  }
  {
    ListGraph g;
    ListGraph::Node s,t;
    ListGraph::EdgeMap<int> label(g);
    std::istringstream input(test_lgf);
    graphReader(g, input).
      node("source", s).
      node("target", t).
      edgeMap("label", label).
      run();
    check(countNodes(g) == 2,"There should be 2 nodes");
    check(countEdges(g) == 2,"There should be 2 arcs");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_nomap);
    digraphReader(d, input).
      run();
    check(countNodes(d) == 2,"There should be 2 nodes");
    check(countArcs(d) == 1,"There should be 1 arc");
  }
  {
    ListGraph g;
    std::istringstream input(test_lgf_nomap);
    graphReader(g, input).
      run();
    check(countNodes(g) == 2,"There should be 2 nodes");
    check(countEdges(g) == 1,"There should be 1 edge");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_bad1);
    bool ok=false;
    try {
      digraphReader(d, input).
        run();
    }
    catch (FormatError& error) 
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }
  {
    ListGraph g;
    std::istringstream input(test_lgf_bad1);
    bool ok=false;
    try {
      graphReader(g, input).
        run();
    }
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }

  {
    ListDigraph d; 
    ListDigraph d;
    std::istringstream input(test_lgf_bad2);
    bool ok=false;
    try {
      digraphReader(d, input).
        run();
    }
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }
  {
    ListGraph g;
    std::istringstream input(test_lgf_bad2);
    bool ok=false;
    try {
      graphReader(g, input).
        run();
    }
    catch (FormatError& error)
      {
        ok = true;
      }
    check(ok,"FormatError exception should have occured");
  }
}

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");

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

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2011
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/list_graph.h>
20	20	#include <lemon/lgf_reader.h>
21	21	#include "test_tools.h"
22	22
23	23	using namespace lemon;
24	24
25	25	char test_lgf[] =
26	26	"@nodes\n"
27	27	"label\n"
28	28	"0\n"
29	29	"1\n"
30	30	"@arcs\n"
31	31	" label\n"
32	32	"0 1 0\n"
33	33	"1 0 1\n"
34	34	"@attributes\n"
35	35	"source 0\n"
36	36	"target 1\n";
37	37
38	38	char test_lgf_nomap[] =
39	39	"@nodes\n"
40	40	"label\n"
41	41	"0\n"
42	42	"1\n"
43	43	"@arcs\n"
44	44	" -\n"
45	45	"0 1\n";
46	46
47	47	char test_lgf_bad1[] =
48	48	"@nodes\n"
49	49	"label\n"
50	50	"0\n"
51	51	"1\n"
52	52	"@arcs\n"
53	53	" - another\n"
54	54	"0 1\n";
55	55
56	56	char test_lgf_bad2[] =
57	57	"@nodes\n"
58	58	"label\n"
59	59	"0\n"
60	60	"1\n"
61	61	"@arcs\n"
62	62	" label -\n"
63	63	"0 1\n";
64	64
65	65
66		int main()
	66	int main()
67	67	{
68	68	{
69		ListDigraph d;
	69	ListDigraph d;
70	70	ListDigraph::Node s,t;
71	71	ListDigraph::ArcMap<int> label(d);
72	72	std::istringstream input(test_lgf);
73	73	digraphReader(d, input).
74	74	node("source", s).
75	75	node("target", t).
76	76	arcMap("label", label).
77	77	run();
78	78	check(countNodes(d) == 2,"There should be 2 nodes");
79	79	check(countArcs(d) == 2,"There should be 2 arcs");
80	80	}
81	81	{
82	82	ListGraph g;
83	83	ListGraph::Node s,t;
84	84	ListGraph::EdgeMap<int> label(g);
85	85	std::istringstream input(test_lgf);
86	86	graphReader(g, input).
87	87	node("source", s).
88	88	node("target", t).
89	89	edgeMap("label", label).
90	90	run();
91	91	check(countNodes(g) == 2,"There should be 2 nodes");
92	92	check(countEdges(g) == 2,"There should be 2 arcs");
93	93	}
94	94
95	95	{
96		ListDigraph d;
	96	ListDigraph d;
97	97	std::istringstream input(test_lgf_nomap);
98	98	digraphReader(d, input).
99	99	run();
100	100	check(countNodes(d) == 2,"There should be 2 nodes");
101	101	check(countArcs(d) == 1,"There should be 1 arc");
102	102	}
103	103	{
104	104	ListGraph g;
105	105	std::istringstream input(test_lgf_nomap);
106	106	graphReader(g, input).
107	107	run();
108	108	check(countNodes(g) == 2,"There should be 2 nodes");
109	109	check(countEdges(g) == 1,"There should be 1 edge");
110	110	}
111	111
112	112	{
113		ListDigraph d;
	113	ListDigraph d;
114	114	std::istringstream input(test_lgf_bad1);
115	115	bool ok=false;
116	116	try {
117	117	digraphReader(d, input).
118	118	run();
119	119	}
120		catch (FormatError& error)
	120	catch (FormatError& error)
121	121	{
122	122	ok = true;
123	123	}
124	124	check(ok,"FormatError exception should have occured");
125	125	}
126	126	{
127	127	ListGraph g;
128	128	std::istringstream input(test_lgf_bad1);
129	129	bool ok=false;
130	130	try {
131	131	graphReader(g, input).
132	132	run();
133	133	}
134	134	catch (FormatError& error)
135	135	{
136	136	ok = true;
137	137	}
138	138	check(ok,"FormatError exception should have occured");
139	139	}
140	140
141	141	{
142		ListDigraph d;
	142	ListDigraph d;
143	143	std::istringstream input(test_lgf_bad2);
144	144	bool ok=false;
145	145	try {
146	146	digraphReader(d, input).
147	147	run();
148	148	}
149	149	catch (FormatError& error)
150	150	{
151	151	ok = true;
152	152	}
153	153	check(ok,"FormatError exception should have occured");
154	154	}
155	155	{
156	156	ListGraph g;
157	157	std::istringstream input(test_lgf_bad2);
158	158	bool ok=false;
159	159	try {
160	160	graphReader(g, input).
161	161	run();
162	162	}
163	163	catch (FormatError& error)
164	164	{
165	165	ok = true;
166	166	}
167	167	check(ok,"FormatError exception should have occured");
168	168	}
169	169	}