LEMON/LEMON-main Changeset - r469:04c0631fd332

Repositories » LEMON » LEMON-main

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

Changeset - r469:04c0631fd332

« 468:68fe66
« 467:a1155a

515:c35afa »
470:81627f »

r469:04c0631fd332

Mon, 12 Jan 2009 14:37:37

[Not Reviewed]

0 comments (0 inline)

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

Merge

0 3 3

merge default

3 files changed with 2423 insertions and 0 deletions:

lemon/bits/edge_set_extender.h

628

lemon/edge_set.h

1410

test/edge_set_test.cc

380

lemon/Makefile.am

test/CMakeLists.txt

test/Makefile.am

↑ Collapse diff ↑

lemon/bits/edge_set_extender.h

Show inline comments

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

lemon/edge_set.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * 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_EDGE_SET_H
 		#define LEMON_EDGE_SET_H
 		#include <lemon/core.h>
 		#include <lemon/bits/edge_set_extender.h>
 		/// \ingroup semi_adaptors
 		/// \file
 		/// \brief ArcSet and EdgeSet classes.
 		///
 		/// Graphs which use another graph's node-set as own.
 		namespace lemon {
 		  template <typename _Graph>
 		  class ListArcSetBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out, first_in;
 		      NodeT() : first_out(-1), first_in(-1) {}
 		    };
 		    typedef typename ItemSetTraits<Graph, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* nodes;
 		    struct ArcT {
 		      Node source, target;
 		      int next_out, next_in;
 		      int prev_out, prev_in;
 		      ArcT() : prev_out(-1), prev_in(-1) {}
 		    };
 		    std::vector<ArcT> arcs;
 		    int first_arc;
 		    int first_free_arc;
 		    const Graph* graph;
 		    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 		      graph = &_graph;
 		      nodes = &_nodes;
+		    }
 		  public:
 		    class Arc {
 		      friend class ListArcSetBase<Graph>;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
 		    Arc addArc(const Node& u, const Node& v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[first_free_arc].next_in;
+		      }
 		      arcs[n].next_in = (*nodes)[v].first_in;
 		      if ((*nodes)[v].first_in != -1) {
 		        arcs[(*nodes)[v].first_in].prev_in = n;
+		      }
 		      (*nodes)[v].first_in = n;
 		      arcs[n].next_out = (*nodes)[u].first_out;
 		      if ((*nodes)[u].first_out != -1) {
 		        arcs[(*nodes)[u].first_out].prev_out = n;
+		      }
 		      (*nodes)[u].first_out = n;
 		      arcs[n].source = u;
 		      arcs[n].target = v;
 		      return Arc(n);
+		    }
 		    void erase(const Arc& arc) {
 		      int n = arc.id;
 		      if (arcs[n].prev_in != -1) {
 		        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
 		      } else {
 		        (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
+		      }
 		      if (arcs[n].next_in != -1) {
 		        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
+		      }
 		      if (arcs[n].prev_out != -1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
+		      }
 		      if (arcs[n].next_out != -1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*nodes)[node].first_in = -1;
 		        (*nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
 		      first_arc = -1;
 		      first_free_arc = -1;
+		    }
 		    void first(Node& node) const {
 		      graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      Node node;
 		      first(node);
 		      while (node != INVALID && (*nodes)[node].first_in == -1) {
 		        next(node);
+		      }
 		      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+		    }
 		    void next(Arc& arc) const {
 		      if (arcs[arc.id].next_in != -1) {
 		        arc.id = arcs[arc.id].next_in;
 		      } else {
 		        Node node = arcs[arc.id].target;
 		        next(node);
 		        while (node != INVALID && (*nodes)[node].first_in == -1) {
 		          next(node);
+		        }
 		        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
+		      }
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_in;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_in;
+		    }
 		    int id(const Node& node) const { return graph->id(node); }
 		    int id(const Arc& arc) const { return arc.id; }
 		    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return Arc(ix); }
 		    int maxNodeId() const { return graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    Node source(const Arc& arc) const { return arcs[arc.id].source;}
 		    Node target(const Arc& arc) const { return arcs[arc.id].target;}
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return graph->notifier(Node());
+		    }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const ListArcSetBase<Graph>& arcset)
 		        : Parent(*arcset.graph) {}
 		      NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
 		        : Parent(*arcset.graph, value) {}
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup semi_adaptors
 		  ///
 		  /// \brief Digraph using a node set of another digraph or graph and
 		  /// an own arc set.
 		  ///
 		  /// This structure can be used to establish another directed graph
 		  /// over a node set of an existing one. This class uses the same
 		  /// Node type as the underlying graph, and each valid node of the
 		  /// original graph is valid in this arc set, therefore the node
 		  /// objects of the original graph can be used directly with this
 		  /// class. The node handling functions (id handling, observing, and
 		  /// iterators) works equivalently as in the original graph.
 		  ///
 		  /// This implementation is based on doubly-linked lists, from each
 		  /// node the outgoing and the incoming arcs make up lists, therefore
 		  /// one arc can be erased in constant time. It also makes possible,
 		  /// that node can be removed from the underlying graph, in this case
 		  /// all arcs incident to the given node is erased from the arc set.
 		  ///
 		  /// \param _Graph The type of the graph which shares its node set with
 		  /// this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  /// concept.
 		  ///
 		  /// This class is fully conform to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  template <typename _Graph>
 		  class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
 		  public:
 		    typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef _Graph Graph;
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
 		      Parent::firstIn(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstIn(arc, node);
+		      }
+		    }
 		    void clearNodes() {
 		      Parent::clear();
+		    }
 		    class NodesImpl : public NodesImplBase {
 		    public:
 		      typedef NodesImplBase Parent;
 		      NodesImpl(const Graph& graph, ListArcSet& arcset)
 		        : Parent(graph), _arcset(arcset) {}
 		      virtual ~NodesImpl() {}
 		    protected:
 		      virtual void erase(const Node& node) {
 		        _arcset.eraseNode(node);
 		        Parent::erase(node);
+		      }
 		      virtual void erase(const std::vector<Node>& nodes) {
 		        for (int i = 0; i < int(nodes.size()); ++i) {
 		          _arcset.eraseNode(nodes[i]);
+		        }
 		        Parent::erase(nodes);
+		      }
 		      virtual void clear() {
 		        _arcset.clearNodes();
 		        Parent::clear();
+		      }
 		    private:
 		      ListArcSet& _arcset;
 		    };
 		    NodesImpl nodes;
 		  public:
 		    /// \brief Constructor of the ArcSet.
 		    ///
 		    /// Constructor of the ArcSet.
 		    ListArcSet(const Graph& graph) : nodes(graph, *this) {
 		      Parent::initalize(graph, nodes);
+		    }
 		    /// \brief Add a new arc to the digraph.
 		    ///
 		    /// Add a new arc to the digraph with source node \c s
 		    /// and target node \c t.
 		    /// \return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// \brief Erase an arc from the digraph.
 		    ///
 		    /// Erase an arc \c a from the digraph.
 		    void erase(const Arc& a) {
 		      return Parent::erase(a);
+		    }
 		  };
 		  template <typename _Graph>
 		  class ListEdgeSetBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out;
 		      NodeT() : first_out(-1) {}
 		    };
 		    typedef typename ItemSetTraits<Graph, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* nodes;
 		    struct ArcT {
 		      Node target;
 		      int prev_out, next_out;
 		      ArcT() : prev_out(-1), next_out(-1) {}
 		    };
 		    std::vector<ArcT> arcs;
 		    int first_arc;
 		    int first_free_arc;
 		    const Graph* graph;
 		    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 		      graph = &_graph;
 		      nodes = &_nodes;
+		    }
 		  public:
 		    class Edge {
 		      friend class ListEdgeSetBase;
 		    protected:
 		      int id;
 		      explicit Edge(int _id) { id = _id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { id = -1; }
 		      bool operator==(const Edge& arc) const {return id == arc.id;}
 		      bool operator!=(const Edge& arc) const {return id != arc.id;}
 		      bool operator<(const Edge& arc) const {return id < arc.id;}
 		    };
 		    class Arc {
 		      friend class ListEdgeSetBase;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      operator Edge() const { return edgeFromId(id / 2); }
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
 		    Edge addEdge(const Node& u, const Node& v) {
 		      int n;
 		      if (first_free_arc == -1) {
 		        n = arcs.size();
 		        arcs.push_back(ArcT());
 		        arcs.push_back(ArcT());
 		      } else {
 		        n = first_free_arc;
 		        first_free_arc = arcs[n].next_out;
+		      }
 		      arcs[n].target = u;
 		      arcs[n | 1].target = v;
 		      arcs[n].next_out = (*nodes)[v].first_out;
 		      if ((*nodes)[v].first_out != -1) {
 		        arcs[(*nodes)[v].first_out].prev_out = n;
+		      }
 		      (*nodes)[v].first_out = n;
 		      arcs[n].prev_out = -1;
 		      if ((*nodes)[u].first_out != -1) {
 		        arcs[(*nodes)[u].first_out].prev_out = (n | 1);
+		      }
 		      arcs[n | 1].next_out = (*nodes)[u].first_out;
 		      (*nodes)[u].first_out = (n | 1);
 		      arcs[n | 1].prev_out = -1;
 		      return Edge(n / 2);
+		    }
 		    void erase(const Edge& arc) {
 		      int n = arc.id * 2;
 		      if (arcs[n].next_out != -1) {
 		        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
+		      }
 		      if (arcs[n].prev_out != -1) {
 		        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
 		      } else {
 		        (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
+		      }
 		      if (arcs[n | 1].next_out != -1) {
 		        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
+		      }
 		      if (arcs[n | 1].prev_out != -1) {
 		        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
 		      } else {
 		        (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
+		      }
 		      arcs[n].next_out = first_free_arc;
 		      first_free_arc = n;
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
 		      first_arc = -1;
 		      first_free_arc = -1;
+		    }
 		    void first(Node& node) const {
 		      graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      Node node;
 		      first(node);
 		      while (node != INVALID && (*nodes)[node].first_out == -1) {
 		        next(node);
+		      }
 		      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+		    }
 		    void next(Arc& arc) const {
 		      if (arcs[arc.id].next_out != -1) {
 		        arc.id = arcs[arc.id].next_out;
 		      } else {
 		        Node node = arcs[arc.id ^ 1].target;
 		        next(node);
 		        while(node != INVALID && (*nodes)[node].first_out == -1) {
 		          next(node);
+		        }
 		        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
+		      }
+		    }
 		    void first(Edge& edge) const {
 		      Node node;
 		      first(node);
 		      while (node != INVALID) {
 		        edge.id = (*nodes)[node].first_out;
 		        while ((edge.id & 1) != 1) {
 		          edge.id = arcs[edge.id].next_out;
+		        }
 		        if (edge.id != -1) {
 		          edge.id /= 2;
 		          return;
+		        }
 		        next(node);
+		      }
 		      edge.id = -1;
+		    }
 		    void next(Edge& edge) const {
 		      Node node = arcs[edge.id * 2].target;
 		      edge.id = arcs[(edge.id * 2) | 1].next_out;
 		      while ((edge.id & 1) != 1) {
 		        edge.id = arcs[edge.id].next_out;
+		      }
 		      if (edge.id != -1) {
 		        edge.id /= 2;
 		        return;
+		      }
 		      next(node);
 		      while (node != INVALID) {
 		        edge.id = (*nodes)[node].first_out;
 		        while ((edge.id & 1) != 1) {
 		          edge.id = arcs[edge.id].next_out;
+		        }
 		        if (edge.id != -1) {
 		          edge.id /= 2;
 		          return;
+		        }
 		        next(node);
+		      }
 		      edge.id = -1;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc.id = (((*nodes)[node].first_out) ^ 1);
 		      if (arc.id == -2) arc.id = -1;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 		      if (arc.id == -2) arc.id = -1;
+		    }
 		    void firstInc(Edge &arc, bool& dir, const Node& node) const {
 		      int de = (*nodes)[node].first_out;
 		      if (de != -1 ) {
 		        arc.id = de / 2;
 		        dir = ((de & 1) == 1);
 		      } else {
 		        arc.id = -1;
 		        dir = true;
+		      }
+		    }
 		    void nextInc(Edge &arc, bool& dir) const {
 		      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
 		      if (de != -1 ) {
 		        arc.id = de / 2;
 		        dir = ((de & 1) == 1);
 		      } else {
 		        arc.id = -1;
 		        dir = true;
+		      }
+		    }
 		    static bool direction(Arc arc) {
 		      return (arc.id & 1) == 1;
+		    }
 		    static Arc direct(Edge edge, bool dir) {
 		      return Arc(edge.id * 2 + (dir ? 1 : 0));
+		    }
 		    int id(const Node& node) const { return graph->id(node); }
 		    static int id(Arc e) { return e.id; }
 		    static int id(Edge e) { return e.id; }
 		    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
 		    static Arc arcFromId(int id) { return Arc(id);}
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    int maxNodeId() const { return graph->maxNodeId(); };
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    int maxArcId() const { return arcs.size()-1; }
 		    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 		    Node target(Arc e) const { return arcs[e.id].target; }
 		    Node u(Edge e) const { return arcs[2 * e.id].target; }
 		    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return graph->notifier(Node());
+		    }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
 		        : Parent(*arcset.graph) {}
 		      NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
 		        : Parent(*arcset.graph, value) {}
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup semi_adaptors
 		  ///
 		  /// \brief Graph using a node set of another digraph or graph and an
 		  /// own edge set.
 		  ///
 		  /// This structure can be used to establish another graph over a
 		  /// node set of an existing one. This class uses the same Node type
 		  /// as the underlying graph, and each valid node of the original
 		  /// graph is valid in this arc set, therefore the node objects of
 		  /// the original graph can be used directly with this class. The
 		  /// node handling functions (id handling, observing, and iterators)
 		  /// works equivalently as in the original graph.
 		  ///
 		  /// This implementation is based on doubly-linked lists, from each
 		  /// node the incident edges make up lists, therefore one edge can be
 		  /// erased in constant time. It also makes possible, that node can
 		  /// be removed from the underlying graph, in this case all edges
 		  /// incident to the given node is erased from the arc set.
 		  ///
 		  /// \param _Graph The type of the graph which shares its node set
 		  /// with this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  /// concept.
 		  ///
 		  /// This class is fully conform to the \ref concepts::Graph "Graph"
 		  /// concept.
 		  template <typename _Graph>
 		  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
 		  public:
 		    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    typedef _Graph Graph;
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      Arc arc;
 		      Parent::firstOut(arc, node);
 		      while (arc != INVALID ) {
 		        erase(arc);
 		        Parent::firstOut(arc, node);
+		      }
+		    }
 		    void clearNodes() {
 		      Parent::clear();
+		    }
 		    class NodesImpl : public NodesImplBase {
 		    public:
 		      typedef NodesImplBase Parent;
 		      NodesImpl(const Graph& graph, ListEdgeSet& arcset)
 		        : Parent(graph), _arcset(arcset) {}
 		      virtual ~NodesImpl() {}
 		    protected:
 		      virtual void erase(const Node& node) {
 		        _arcset.eraseNode(node);
 		        Parent::erase(node);
+		      }
 		      virtual void erase(const std::vector<Node>& nodes) {
 		        for (int i = 0; i < int(nodes.size()); ++i) {
 		          _arcset.eraseNode(nodes[i]);
+		        }
 		        Parent::erase(nodes);
+		      }
 		      virtual void clear() {
 		        _arcset.clearNodes();
 		        Parent::clear();
+		      }
 		    private:
 		      ListEdgeSet& _arcset;
 		    };
 		    NodesImpl nodes;
 		  public:
 		    /// \brief Constructor of the EdgeSet.
 		    ///
 		    /// Constructor of the EdgeSet.
 		    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
 		      Parent::initalize(graph, nodes);
+		    }
 		    /// \brief Add a new edge to the graph.
 		    ///
 		    /// Add a new edge to the graph with node \c u
 		    /// and node \c v endpoints.
 		    /// \return the new edge.
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return Parent::addEdge(u, v);
+		    }
 		    /// \brief Erase an edge from the graph.
 		    ///
 		    /// Erase the edge \c e from the graph.
 		    void erase(const Edge& e) {
 		      return Parent::erase(e);
+		    }
 		  };
 		  template <typename _Graph>
 		  class SmartArcSetBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out, first_in;
 		      NodeT() : first_out(-1), first_in(-1) {}
 		    };
 		    typedef typename ItemSetTraits<Graph, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* nodes;
 		    struct ArcT {
 		      Node source, target;
 		      int next_out, next_in;
 		      ArcT() {}
 		    };
 		    std::vector<ArcT> arcs;
 		    const Graph* graph;
 		    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 		      graph = &_graph;
 		      nodes = &_nodes;
+		    }
 		  public:
 		    class Arc {
 		      friend class SmartArcSetBase<Graph>;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    SmartArcSetBase() {}
 		    Arc addArc(const Node& u, const Node& v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs[n].next_in = (*nodes)[v].first_in;
 		      (*nodes)[v].first_in = n;
 		      arcs[n].next_out = (*nodes)[u].first_out;
 		      (*nodes)[u].first_out = n;
 		      arcs[n].source = u;
 		      arcs[n].target = v;
 		      return Arc(n);
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*nodes)[node].first_in = -1;
 		        (*nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
+		    }
 		    void first(Node& node) const {
 		      graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      arc.id = arcs.size() - 1;
+		    }
 		    void next(Arc& arc) const {
 		      --arc.id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_in;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_in;
+		    }
 		    int id(const Node& node) const { return graph->id(node); }
 		    int id(const Arc& arc) const { return arc.id; }
 		    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const { return Arc(ix); }
 		    int maxNodeId() const { return graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    Node source(const Arc& arc) const { return arcs[arc.id].source;}
 		    Node target(const Arc& arc) const { return arcs[arc.id].target;}
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return graph->notifier(Node());
+		    }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
 		        : Parent(*arcset.graph) { }
 		      NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
 		        : Parent(*arcset.graph, value) { }
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup semi_adaptors
 		  ///
 		  /// \brief Digraph using a node set of another digraph or graph and
 		  /// an own arc set.
 		  ///
 		  /// This structure can be used to establish another directed graph
 		  /// over a node set of an existing one. This class uses the same
 		  /// Node type as the underlying graph, and each valid node of the
 		  /// original graph is valid in this arc set, therefore the node
 		  /// objects of the original graph can be used directly with this
 		  /// class. The node handling functions (id handling, observing, and
 		  /// iterators) works equivalently as in the original graph.
 		  ///
 		  /// \param _Graph The type of the graph which shares its node set with
 		  /// this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  /// concept.
 		  ///
 		  /// This implementation is slightly faster than the \c ListArcSet,
 		  /// because it uses continuous storage for arcs and it uses just
 		  /// single-linked lists for enumerate outgoing and incoming
 		  /// arcs. Therefore the arcs cannot be erased from the arc sets.
 		  ///
 		  /// \warning If a node is erased from the underlying graph and this
 		  /// node is the source or target of one arc in the arc set, then
 		  /// the arc set is invalidated, and it cannot be used anymore. The
 		  /// validity can be checked with the \c valid() member function.
 		  ///
 		  /// This class is fully conform to the \ref concepts::Digraph
 		  /// "Digraph" concept.
 		  template <typename _Graph>
 		  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
 		  public:
 		    typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef _Graph Graph;
 		  protected:
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      if (typename Parent::InArcIt(*this, node) == INVALID &&
 		          typename Parent::OutArcIt(*this, node) == INVALID) {
 		        return;
+		      }
 		      throw typename NodesImplBase::Notifier::ImmediateDetach();
+		    }
 		    void clearNodes() {
 		      Parent::clear();
+		    }
 		    class NodesImpl : public NodesImplBase {
 		    public:
 		      typedef NodesImplBase Parent;
 		      NodesImpl(const Graph& graph, SmartArcSet& arcset)
 		        : Parent(graph), _arcset(arcset) {}
 		      virtual ~NodesImpl() {}
 		      bool attached() const {
 		        return Parent::attached();
+		      }
 		    protected:
 		      virtual void erase(const Node& node) {
 		        try {
 		          _arcset.eraseNode(node);
 		          Parent::erase(node);
 		        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
 		          Parent::clear();
 		          throw;
+		        }
+		      }
 		      virtual void erase(const std::vector<Node>& nodes) {
 		        try {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            _arcset.eraseNode(nodes[i]);
+		          }
 		          Parent::erase(nodes);
 		        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
 		          Parent::clear();
 		          throw;
+		        }
+		      }
 		      virtual void clear() {
 		        _arcset.clearNodes();
 		        Parent::clear();
+		      }
 		    private:
 		      SmartArcSet& _arcset;
 		    };
 		    NodesImpl nodes;
 		  public:
 		    /// \brief Constructor of the ArcSet.
 		    ///
 		    /// Constructor of the ArcSet.
 		    SmartArcSet(const Graph& graph) : nodes(graph, *this) {
 		      Parent::initalize(graph, nodes);
+		    }
 		    /// \brief Add a new arc to the digraph.
 		    ///
 		    /// Add a new arc to the digraph with source node \c s
 		    /// and target node \c t.
 		    /// \return the new arc.
 		    Arc addArc(const Node& s, const Node& t) {
 		      return Parent::addArc(s, t);
+		    }
 		    /// \brief Validity check
 		    ///
 		    /// This functions gives back false if the ArcSet is
 		    /// invalidated. It occurs when a node in the underlying graph is
 		    /// erased and it is not isolated in the ArcSet.
 		    bool valid() const {
 		      return nodes.attached();
+		    }
 		  };
 		  template <typename _Graph>
 		  class SmartEdgeSetBase {
 		  public:
 		    typedef _Graph Graph;
 		    typedef typename Graph::Node Node;
 		    typedef typename Graph::NodeIt NodeIt;
 		  protected:
 		    struct NodeT {
 		      int first_out;
 		      NodeT() : first_out(-1) {}
 		    };
 		    typedef typename ItemSetTraits<Graph, Node>::
 		    template Map<NodeT>::Type NodesImplBase;
 		    NodesImplBase* nodes;
 		    struct ArcT {
 		      Node target;
 		      int next_out;
 		      ArcT() {}
 		    };
 		    std::vector<ArcT> arcs;
 		    const Graph* graph;
 		    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
 		      graph = &_graph;
 		      nodes = &_nodes;
+		    }
 		  public:
 		    class Edge {
 		      friend class SmartEdgeSetBase;
 		    protected:
 		      int id;
 		      explicit Edge(int _id) { id = _id;}
 		    public:
 		      Edge() {}
 		      Edge (Invalid) { id = -1; }
 		      bool operator==(const Edge& arc) const {return id == arc.id;}
 		      bool operator!=(const Edge& arc) const {return id != arc.id;}
 		      bool operator<(const Edge& arc) const {return id < arc.id;}
 		    };
 		    class Arc {
 		      friend class SmartEdgeSetBase;
 		    protected:
 		      Arc(int _id) : id(_id) {}
 		      int id;
 		    public:
 		      operator Edge() const { return edgeFromId(id / 2); }
 		      Arc() {}
 		      Arc(Invalid) : id(-1) {}
 		      bool operator==(const Arc& arc) const { return id == arc.id; }
 		      bool operator!=(const Arc& arc) const { return id != arc.id; }
 		      bool operator<(const Arc& arc) const { return id < arc.id; }
 		    };
 		    SmartEdgeSetBase() {}
 		    Edge addEdge(const Node& u, const Node& v) {
 		      int n = arcs.size();
 		      arcs.push_back(ArcT());
 		      arcs.push_back(ArcT());
 		      arcs[n].target = u;
 		      arcs[n | 1].target = v;
 		      arcs[n].next_out = (*nodes)[v].first_out;
 		      (*nodes)[v].first_out = n;
 		      arcs[n | 1].next_out = (*nodes)[u].first_out;
 		      (*nodes)[u].first_out = (n | 1);
 		      return Edge(n / 2);
+		    }
 		    void clear() {
 		      Node node;
 		      for (first(node); node != INVALID; next(node)) {
 		        (*nodes)[node].first_out = -1;
+		      }
 		      arcs.clear();
+		    }
 		    void first(Node& node) const {
 		      graph->first(node);
+		    }
 		    void next(Node& node) const {
 		      graph->next(node);
+		    }
 		    void first(Arc& arc) const {
 		      arc.id = arcs.size() - 1;
+		    }
 		    void next(Arc& arc) const {
 		      --arc.id;
+		    }
 		    void first(Edge& arc) const {
 		      arc.id = arcs.size() / 2 - 1;
+		    }
 		    void next(Edge& arc) const {
 		      --arc.id;
+		    }
 		    void firstOut(Arc& arc, const Node& node) const {
 		      arc.id = (*nodes)[node].first_out;
+		    }
 		    void nextOut(Arc& arc) const {
 		      arc.id = arcs[arc.id].next_out;
+		    }
 		    void firstIn(Arc& arc, const Node& node) const {
 		      arc.id = (((*nodes)[node].first_out) ^ 1);
 		      if (arc.id == -2) arc.id = -1;
+		    }
 		    void nextIn(Arc& arc) const {
 		      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
 		      if (arc.id == -2) arc.id = -1;
+		    }
 		    void firstInc(Edge &arc, bool& dir, const Node& node) const {
 		      int de = (*nodes)[node].first_out;
 		      if (de != -1 ) {
 		        arc.id = de / 2;
 		        dir = ((de & 1) == 1);
 		      } else {
 		        arc.id = -1;
 		        dir = true;
+		      }
+		    }
 		    void nextInc(Edge &arc, bool& dir) const {
 		      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
 		      if (de != -1 ) {
 		        arc.id = de / 2;
 		        dir = ((de & 1) == 1);
 		      } else {
 		        arc.id = -1;
 		        dir = true;
+		      }
+		    }
 		    static bool direction(Arc arc) {
 		      return (arc.id & 1) == 1;
+		    }
 		    static Arc direct(Edge edge, bool dir) {
 		      return Arc(edge.id * 2 + (dir ? 1 : 0));
+		    }
 		    int id(Node node) const { return graph->id(node); }
 		    static int id(Arc arc) { return arc.id; }
 		    static int id(Edge arc) { return arc.id; }
 		    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
 		    static Arc arcFromId(int id) { return Arc(id); }
 		    static Edge edgeFromId(int id) { return Edge(id);}
 		    int maxNodeId() const { return graph->maxNodeId(); };
 		    int maxArcId() const { return arcs.size() - 1; }
 		    int maxEdgeId() const { return arcs.size() / 2 - 1; }
 		    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
 		    Node target(Arc e) const { return arcs[e.id].target; }
 		    Node u(Edge e) const { return arcs[2 * e.id].target; }
 		    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
 		    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const {
 		      return graph->notifier(Node());
+		    }
 		    template <typename _Value>
 		    class NodeMap : public Graph::template NodeMap<_Value> {
 		    public:
 		      typedef typename _Graph::template NodeMap<_Value> Parent;
 		      explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
 		        : Parent(*arcset.graph) { }
 		      NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
 		        : Parent(*arcset.graph, value) { }
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  };
 		  /// \ingroup semi_adaptors
 		  ///
 		  /// \brief Graph using a node set of another digraph or graph and an
 		  /// own edge set.
 		  ///
 		  /// This structure can be used to establish another graph over a
 		  /// node set of an existing one. This class uses the same Node type
 		  /// as the underlying graph, and each valid node of the original
 		  /// graph is valid in this arc set, therefore the node objects of
 		  /// the original graph can be used directly with this class. The
 		  /// node handling functions (id handling, observing, and iterators)
 		  /// works equivalently as in the original graph.
 		  ///
 		  /// \param _Graph The type of the graph which shares its node set
 		  /// with this class. Its interface must conform to the
 		  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
 		  ///  concept.
 		  ///
 		  /// This implementation is slightly faster than the \c ListEdgeSet,
 		  /// because it uses continuous storage for edges and it uses just
 		  /// single-linked lists for enumerate incident edges. Therefore the
 		  /// edges cannot be erased from the edge sets.
 		  ///
 		  /// \warning If a node is erased from the underlying graph and this
 		  /// node is incident to one edge in the edge set, then the edge set
 		  /// is invalidated, and it cannot be used anymore. The validity can
 		  /// be checked with the \c valid() member function.
 		  ///
 		  /// This class is fully conform to the \ref concepts::Graph
 		  /// "Graph" concept.
 		  template <typename _Graph>
 		  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
 		  public:
 		    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    typedef _Graph Graph;
 		  protected:
 		    typedef typename Parent::NodesImplBase NodesImplBase;
 		    void eraseNode(const Node& node) {
 		      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
 		        return;
+		      }
 		      throw typename NodesImplBase::Notifier::ImmediateDetach();
+		    }
 		    void clearNodes() {
 		      Parent::clear();
+		    }
 		    class NodesImpl : public NodesImplBase {
 		    public:
 		      typedef NodesImplBase Parent;
 		      NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
 		        : Parent(graph), _arcset(arcset) {}
 		      virtual ~NodesImpl() {}
 		      bool attached() const {
 		        return Parent::attached();
+		      }
 		    protected:
 		      virtual void erase(const Node& node) {
 		        try {
 		          _arcset.eraseNode(node);
 		          Parent::erase(node);
 		        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
 		          Parent::clear();
 		          throw;
+		        }
+		      }
 		      virtual void erase(const std::vector<Node>& nodes) {
 		        try {
 		          for (int i = 0; i < int(nodes.size()); ++i) {
 		            _arcset.eraseNode(nodes[i]);
+		          }
 		          Parent::erase(nodes);
 		        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
 		          Parent::clear();
 		          throw;
+		        }
+		      }
 		      virtual void clear() {
 		        _arcset.clearNodes();
 		        Parent::clear();
+		      }
 		    private:
 		      SmartEdgeSet& _arcset;
 		    };
 		    NodesImpl nodes;
 		  public:
 		    /// \brief Constructor of the EdgeSet.
 		    ///
 		    /// Constructor of the EdgeSet.
 		    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
 		      Parent::initalize(graph, nodes);
+		    }
 		    /// \brief Add a new edge to the graph.
 		    ///
 		    /// Add a new edge to the graph with node \c u
 		    /// and node \c v endpoints.
 		    /// \return the new edge.
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return Parent::addEdge(u, v);
+		    }
 		    /// \brief Validity check
 		    ///
 		    /// This functions gives back false if the EdgeSet is
 		    /// invalidated. It occurs when a node in the underlying graph is
 		    /// erased and it is not isolated in the EdgeSet.
 		    bool valid() const {
 		      return nodes.attached();
+		    }
 		  };
+		}
 		#endif

test/edge_set_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-2008
 		 * 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 <vector>
 		#include <lemon/concepts/digraph.h>
 		#include <lemon/concepts/graph.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/list_graph.h>
 		#include <lemon/edge_set.h>
 		#include "graph_test.h"
 		#include "test_tools.h"
 		using namespace lemon;
 		void checkSmartArcSet() {
 		  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef SmartArcSet<Digraph> ArcSet;
 		  Digraph digraph;
 		  Digraph::Node
 		    n1 = digraph.addNode(),
 		    n2 = digraph.addNode();
 		  Digraph::Arc ga1 = digraph.addArc(n1, n2);
 		  ArcSet arc_set(digraph);
 		  Digraph::Arc ga2 = digraph.addArc(n2, n1);
 		  checkGraphNodeList(arc_set, 2);
 		  checkGraphArcList(arc_set, 0);
 		  Digraph::Node
 		    n3 = digraph.addNode();
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 0);
 		  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
 		  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 1);
 		  checkGraphOutArcList(arc_set, n1, 1);
 		  checkGraphOutArcList(arc_set, n2, 0);
 		  checkGraphOutArcList(arc_set, n3, 0);
 		  checkGraphInArcList(arc_set, n1, 0);
 		  checkGraphInArcList(arc_set, n2, 1);
 		  checkGraphInArcList(arc_set, n3, 0);
 		  checkGraphConArcList(arc_set, 1);
 		  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
 		    a3 = arc_set.addArc(n2, n3),
 		    a4 = arc_set.addArc(n2, n3);
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 4);
 		  checkGraphOutArcList(arc_set, n1, 1);
 		  checkGraphOutArcList(arc_set, n2, 3);
 		  checkGraphOutArcList(arc_set, n3, 0);
 		  checkGraphInArcList(arc_set, n1, 1);
 		  checkGraphInArcList(arc_set, n2, 1);
 		  checkGraphInArcList(arc_set, n3, 2);
 		  checkGraphConArcList(arc_set, 4);
 		  checkNodeIds(arc_set);
 		  checkArcIds(arc_set);
 		  checkGraphNodeMap(arc_set);
 		  checkGraphArcMap(arc_set);
 		  check(arc_set.valid(), "Wrong validity");
 		  digraph.erase(n1);
 		  check(!arc_set.valid(), "Wrong validity");
+		}
 		void checkListArcSet() {
 		  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef ListArcSet<Digraph> ArcSet;
 		  Digraph digraph;
 		  Digraph::Node
 		    n1 = digraph.addNode(),
 		    n2 = digraph.addNode();
 		  Digraph::Arc ga1 = digraph.addArc(n1, n2);
 		  ArcSet arc_set(digraph);
 		  Digraph::Arc ga2 = digraph.addArc(n2, n1);
 		  checkGraphNodeList(arc_set, 2);
 		  checkGraphArcList(arc_set, 0);
 		  Digraph::Node
 		    n3 = digraph.addNode();
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 0);
 		  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
 		  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 1);
 		  checkGraphOutArcList(arc_set, n1, 1);
 		  checkGraphOutArcList(arc_set, n2, 0);
 		  checkGraphOutArcList(arc_set, n3, 0);
 		  checkGraphInArcList(arc_set, n1, 0);
 		  checkGraphInArcList(arc_set, n2, 1);
 		  checkGraphInArcList(arc_set, n3, 0);
 		  checkGraphConArcList(arc_set, 1);
 		  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
 		    a3 = arc_set.addArc(n2, n3),
 		    a4 = arc_set.addArc(n2, n3);
 		  checkGraphNodeList(arc_set, 3);
 		  checkGraphArcList(arc_set, 4);
 		  checkGraphOutArcList(arc_set, n1, 1);
 		  checkGraphOutArcList(arc_set, n2, 3);
 		  checkGraphOutArcList(arc_set, n3, 0);
 		  checkGraphInArcList(arc_set, n1, 1);
 		  checkGraphInArcList(arc_set, n2, 1);
 		  checkGraphInArcList(arc_set, n3, 2);
 		  checkGraphConArcList(arc_set, 4);
 		  checkNodeIds(arc_set);
 		  checkArcIds(arc_set);
 		  checkGraphNodeMap(arc_set);
 		  checkGraphArcMap(arc_set);
 		  digraph.erase(n1);
 		  checkGraphNodeList(arc_set, 2);
 		  checkGraphArcList(arc_set, 2);
 		  checkGraphOutArcList(arc_set, n2, 2);
 		  checkGraphOutArcList(arc_set, n3, 0);
 		  checkGraphInArcList(arc_set, n2, 0);
 		  checkGraphInArcList(arc_set, n3, 2);
 		  checkNodeIds(arc_set);
 		  checkArcIds(arc_set);
 		  checkGraphNodeMap(arc_set);
 		  checkGraphArcMap(arc_set);
 		  checkGraphConArcList(arc_set, 2);
+		}
 		void checkSmartEdgeSet() {
 		  checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef SmartEdgeSet<Digraph> EdgeSet;
 		  Digraph digraph;
 		  Digraph::Node
 		    n1 = digraph.addNode(),
 		    n2 = digraph.addNode();
 		  Digraph::Arc ga1 = digraph.addArc(n1, n2);
 		  EdgeSet edge_set(digraph);
 		  Digraph::Arc ga2 = digraph.addArc(n2, n1);
 		  checkGraphNodeList(edge_set, 2);
 		  checkGraphArcList(edge_set, 0);
 		  checkGraphEdgeList(edge_set, 0);
 		  Digraph::Node
 		    n3 = digraph.addNode();
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphArcList(edge_set, 0);
 		  checkGraphEdgeList(edge_set, 0);
 		  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
 		  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
 		        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphArcList(edge_set, 2);
 		  checkGraphEdgeList(edge_set, 1);
 		  checkGraphOutArcList(edge_set, n1, 1);
 		  checkGraphOutArcList(edge_set, n2, 1);
 		  checkGraphOutArcList(edge_set, n3, 0);
 		  checkGraphInArcList(edge_set, n1, 1);
 		  checkGraphInArcList(edge_set, n2, 1);
 		  checkGraphInArcList(edge_set, n3, 0);
 		  checkGraphIncEdgeList(edge_set, n1, 1);
 		  checkGraphIncEdgeList(edge_set, n2, 1);
 		  checkGraphIncEdgeList(edge_set, n3, 0);
 		  checkGraphConEdgeList(edge_set, 1);
 		  checkGraphConArcList(edge_set, 2);
 		  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
 		    e3 = edge_set.addEdge(n2, n3),
 		    e4 = edge_set.addEdge(n2, n3);
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphEdgeList(edge_set, 4);
 		  checkGraphOutArcList(edge_set, n1, 2);
 		  checkGraphOutArcList(edge_set, n2, 4);
 		  checkGraphOutArcList(edge_set, n3, 2);
 		  checkGraphInArcList(edge_set, n1, 2);
 		  checkGraphInArcList(edge_set, n2, 4);
 		  checkGraphInArcList(edge_set, n3, 2);
 		  checkGraphIncEdgeList(edge_set, n1, 2);
 		  checkGraphIncEdgeList(edge_set, n2, 4);
 		  checkGraphIncEdgeList(edge_set, n3, 2);
 		  checkGraphConEdgeList(edge_set, 4);
 		  checkGraphConArcList(edge_set, 8);
 		  checkArcDirections(edge_set);
 		  checkNodeIds(edge_set);
 		  checkArcIds(edge_set);
 		  checkEdgeIds(edge_set);
 		  checkGraphNodeMap(edge_set);
 		  checkGraphArcMap(edge_set);
 		  checkGraphEdgeMap(edge_set);
 		  check(edge_set.valid(), "Wrong validity");
 		  digraph.erase(n1);
 		  check(!edge_set.valid(), "Wrong validity");
+		}
 		void checkListEdgeSet() {
 		  checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
 		  typedef ListDigraph Digraph;
 		  typedef ListEdgeSet<Digraph> EdgeSet;
 		  Digraph digraph;
 		  Digraph::Node
 		    n1 = digraph.addNode(),
 		    n2 = digraph.addNode();
 		  Digraph::Arc ga1 = digraph.addArc(n1, n2);
 		  EdgeSet edge_set(digraph);
 		  Digraph::Arc ga2 = digraph.addArc(n2, n1);
 		  checkGraphNodeList(edge_set, 2);
 		  checkGraphArcList(edge_set, 0);
 		  checkGraphEdgeList(edge_set, 0);
 		  Digraph::Node
 		    n3 = digraph.addNode();
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphArcList(edge_set, 0);
 		  checkGraphEdgeList(edge_set, 0);
 		  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
 		  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
 		        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphArcList(edge_set, 2);
 		  checkGraphEdgeList(edge_set, 1);
 		  checkGraphOutArcList(edge_set, n1, 1);
 		  checkGraphOutArcList(edge_set, n2, 1);
 		  checkGraphOutArcList(edge_set, n3, 0);
 		  checkGraphInArcList(edge_set, n1, 1);
 		  checkGraphInArcList(edge_set, n2, 1);
 		  checkGraphInArcList(edge_set, n3, 0);
 		  checkGraphIncEdgeList(edge_set, n1, 1);
 		  checkGraphIncEdgeList(edge_set, n2, 1);
 		  checkGraphIncEdgeList(edge_set, n3, 0);
 		  checkGraphConEdgeList(edge_set, 1);
 		  checkGraphConArcList(edge_set, 2);
 		  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
 		    e3 = edge_set.addEdge(n2, n3),
 		    e4 = edge_set.addEdge(n2, n3);
 		  checkGraphNodeList(edge_set, 3);
 		  checkGraphEdgeList(edge_set, 4);
 		  checkGraphOutArcList(edge_set, n1, 2);
 		  checkGraphOutArcList(edge_set, n2, 4);
 		  checkGraphOutArcList(edge_set, n3, 2);
 		  checkGraphInArcList(edge_set, n1, 2);
 		  checkGraphInArcList(edge_set, n2, 4);
 		  checkGraphInArcList(edge_set, n3, 2);
 		  checkGraphIncEdgeList(edge_set, n1, 2);
 		  checkGraphIncEdgeList(edge_set, n2, 4);
 		  checkGraphIncEdgeList(edge_set, n3, 2);
 		  checkGraphConEdgeList(edge_set, 4);
 		  checkGraphConArcList(edge_set, 8);
 		  checkArcDirections(edge_set);
 		  checkNodeIds(edge_set);
 		  checkArcIds(edge_set);
 		  checkEdgeIds(edge_set);
 		  checkGraphNodeMap(edge_set);
 		  checkGraphArcMap(edge_set);
 		  checkGraphEdgeMap(edge_set);
 		  digraph.erase(n1);
 		  checkGraphNodeList(edge_set, 2);
 		  checkGraphArcList(edge_set, 4);
 		  checkGraphEdgeList(edge_set, 2);
 		  checkGraphOutArcList(edge_set, n2, 2);
 		  checkGraphOutArcList(edge_set, n3, 2);
 		  checkGraphInArcList(edge_set, n2, 2);
 		  checkGraphInArcList(edge_set, n3, 2);
 		  checkGraphIncEdgeList(edge_set, n2, 2);
 		  checkGraphIncEdgeList(edge_set, n3, 2);
 		  checkNodeIds(edge_set);
 		  checkArcIds(edge_set);
 		  checkEdgeIds(edge_set);
 		  checkGraphNodeMap(edge_set);
 		  checkGraphArcMap(edge_set);
 		  checkGraphEdgeMap(edge_set);
 		  checkGraphConEdgeList(edge_set, 2);
 		  checkGraphConArcList(edge_set, 4);
+		}
 		int main() {
 		  checkSmartArcSet();
 		  checkListArcSet();
 		  checkSmartEdgeSet();
 		  checkListEdgeSet();
 		  return 0;
+		}

lemon/Makefile.am

Show inline comments

@@ -51,24 +51,25 @@
 			lemon/bin_heap.h \
 			lemon/circulation.h \
 			lemon/clp.h \
 			lemon/color.h \
 			lemon/concept_check.h \
 			lemon/counter.h \
 			lemon/core.h \
 			lemon/cplex.h \
 			lemon/dfs.h \
 			lemon/dijkstra.h \
 			lemon/dim2.h \
 			lemon/dimacs.h \
 			lemon/edge_set.h \
 			lemon/elevator.h \
 			lemon/error.h \
 			lemon/full_graph.h \
 			lemon/glpk.h \
 			lemon/graph_to_eps.h \
 			lemon/grid_graph.h \
 			lemon/hypercube_graph.h \
 			lemon/kruskal.h \
 			lemon/hao_orlin.h \
 			lemon/lgf_reader.h \
 			lemon/lgf_writer.h \
 			lemon/list_graph.h \
@@ -88,24 +89,25 @@
 			lemon/soplex.h \
 			lemon/suurballe.h \
 			lemon/time_measure.h \
 			lemon/tolerance.h \
 			lemon/unionfind.h
 		bits_HEADERS += \
 			lemon/bits/alteration_notifier.h \
 			lemon/bits/array_map.h \
 			lemon/bits/base_extender.h \
 			lemon/bits/bezier.h \
 			lemon/bits/default_map.h \
 			lemon/bits/edge_set_extender.h \
 			lemon/bits/enable_if.h \
 			lemon/bits/graph_adaptor_extender.h \
 			lemon/bits/graph_extender.h \
 			lemon/bits/map_extender.h \
 			lemon/bits/path_dump.h \
 			lemon/bits/solver_bits.h \
 			lemon/bits/traits.h \
 			lemon/bits/variant.h \
 			lemon/bits/vector_map.h
 		concept_HEADERS += \
 			lemon/concepts/digraph.h \

test/CMakeLists.txt

Show inline comments

@@ -3,24 +3,25 @@
 		LINK_DIRECTORIES(${CMAKE_BINARY_DIR}/lemon)
 		SET(TESTS
 		  adaptors_test
 		  bfs_test
 		  circulation_test
 		  counter_test
 		  dfs_test
 		  digraph_test
 		  dijkstra_test
 		  dim_test
 		  error_test
 		  edge_set_test
 		  graph_copy_test
 		  graph_test
 		  graph_utils_test
 		  hao_orlin_test
 		  heap_test
 		  kruskal_test
 		  lp_test
 		  mip_test
 		  maps_test
 		  max_matching_test
 		  radix_sort_test
 		  path_test

test/Makefile.am

Show inline comments

@@ -5,24 +5,25 @@
 			test/graph_test.h \
 			test/test_tools.h
 		check_PROGRAMS += \
 			test/adaptors_test \
 			test/bfs_test \
 			test/circulation_test \
 			test/counter_test \
 			test/dfs_test \
 			test/digraph_test \
 			test/dijkstra_test \
 			test/dim_test \
 			test/edge_set_test \
 			test/error_test \
 			test/graph_copy_test \
 			test/graph_test \
 			test/graph_utils_test \
 			test/hao_orlin_test \
 			test/heap_test \
 			test/kruskal_test \
 			test/maps_test \
 			test/max_matching_test \
 			test/path_test \
 			test/preflow_test \
 			test/radix_sort_test \
@@ -42,24 +43,25 @@
 		TESTS += $(check_PROGRAMS)
 		XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
 		test_adaptors_test_SOURCES = test/adaptors_test.cc
 		test_bfs_test_SOURCES = test/bfs_test.cc
 		test_circulation_test_SOURCES = test/circulation_test.cc
 		test_counter_test_SOURCES = test/counter_test.cc
 		test_dfs_test_SOURCES = test/dfs_test.cc
 		test_digraph_test_SOURCES = test/digraph_test.cc
 		test_dijkstra_test_SOURCES = test/dijkstra_test.cc
 		test_dim_test_SOURCES = test/dim_test.cc
 		test_edge_set_test_SOURCES = test/edge_set_test.cc
 		test_error_test_SOURCES = test/error_test.cc
 		test_graph_copy_test_SOURCES = test/graph_copy_test.cc
 		test_graph_test_SOURCES = test/graph_test.cc
 		test_graph_utils_test_SOURCES = test/graph_utils_test.cc
 		test_heap_test_SOURCES = test/heap_test.cc
 		test_kruskal_test_SOURCES = test/kruskal_test.cc
 		test_hao_orlin_test_SOURCES = test/hao_orlin_test.cc
 		test_lp_test_SOURCES = test/lp_test.cc
 		test_maps_test_SOURCES = test/maps_test.cc
 		test_mip_test_SOURCES = test/mip_test.cc
 		test_max_matching_test_SOURCES = test/max_matching_test.cc
 		test_path_test_SOURCES = test/path_test.cc

0 comments (0 inline)

RhodeCode

Login to your account