Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 12 Jan 2009 13:37:37 +0000
changeset 46904c0631fd332
parent 467 a1155a9e8e09
parent 468 68fe66e2b34a
child 470 81627fa1b007
child 504 c35afa9e89e7
Merge
lemon/Makefile.am
test/CMakeLists.txt
test/Makefile.am
     1.1 --- a/lemon/Makefile.am	Mon Jan 12 13:18:03 2009 +0000
     1.2 +++ b/lemon/Makefile.am	Mon Jan 12 13:37:37 2009 +0000
     1.3 @@ -60,6 +60,7 @@
     1.4  	lemon/dijkstra.h \
     1.5  	lemon/dim2.h \
     1.6  	lemon/dimacs.h \
     1.7 +	lemon/edge_set.h \
     1.8  	lemon/elevator.h \
     1.9  	lemon/error.h \
    1.10  	lemon/full_graph.h \
    1.11 @@ -97,6 +98,7 @@
    1.12  	lemon/bits/base_extender.h \
    1.13  	lemon/bits/bezier.h \
    1.14  	lemon/bits/default_map.h \
    1.15 +	lemon/bits/edge_set_extender.h \
    1.16  	lemon/bits/enable_if.h \
    1.17  	lemon/bits/graph_adaptor_extender.h \
    1.18  	lemon/bits/graph_extender.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/bits/edge_set_extender.h	Mon Jan 12 13:37:37 2009 +0000
     2.3 @@ -0,0 +1,628 @@
     2.4 +/* -*- C++ -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library
     2.7 + *
     2.8 + * Copyright (C) 2003-2008
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
    2.23 +#define LEMON_BITS_EDGE_SET_EXTENDER_H
    2.24 +
    2.25 +#include <lemon/error.h>
    2.26 +#include <lemon/bits/default_map.h>
    2.27 +
    2.28 +///\ingroup digraphbits
    2.29 +///\file
    2.30 +///\brief Extenders for the arc set types
    2.31 +namespace lemon {
    2.32 +
    2.33 +  /// \ingroup digraphbits
    2.34 +  ///
    2.35 +  /// \brief Extender for the ArcSets
    2.36 +  template <typename Base>
    2.37 +  class ArcSetExtender : public Base {
    2.38 +  public:
    2.39 +
    2.40 +    typedef Base Parent;
    2.41 +    typedef ArcSetExtender Digraph;
    2.42 +
    2.43 +    // Base extensions
    2.44 +
    2.45 +    typedef typename Parent::Node Node;
    2.46 +    typedef typename Parent::Arc Arc;
    2.47 +
    2.48 +    int maxId(Node) const {
    2.49 +      return Parent::maxNodeId();
    2.50 +    }
    2.51 +
    2.52 +    int maxId(Arc) const {
    2.53 +      return Parent::maxArcId();
    2.54 +    }
    2.55 +
    2.56 +    Node fromId(int id, Node) const {
    2.57 +      return Parent::nodeFromId(id);
    2.58 +    }
    2.59 +
    2.60 +    Arc fromId(int id, Arc) const {
    2.61 +      return Parent::arcFromId(id);
    2.62 +    }
    2.63 +
    2.64 +    Node oppositeNode(const Node &n, const Arc &e) const {
    2.65 +      if (n == Parent::source(e))
    2.66 +	return Parent::target(e);
    2.67 +      else if(n==Parent::target(e))
    2.68 +	return Parent::source(e);
    2.69 +      else
    2.70 +	return INVALID;
    2.71 +    }
    2.72 +
    2.73 +
    2.74 +    // Alteration notifier extensions
    2.75 +
    2.76 +    /// The arc observer registry.
    2.77 +    typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
    2.78 +
    2.79 +  protected:
    2.80 +
    2.81 +    mutable ArcNotifier arc_notifier;
    2.82 +
    2.83 +  public:
    2.84 +
    2.85 +    using Parent::notifier;
    2.86 +
    2.87 +    /// \brief Gives back the arc alteration notifier.
    2.88 +    ///
    2.89 +    /// Gives back the arc alteration notifier.
    2.90 +    ArcNotifier& notifier(Arc) const {
    2.91 +      return arc_notifier;
    2.92 +    }
    2.93 +
    2.94 +    // Iterable extensions
    2.95 +
    2.96 +    class NodeIt : public Node { 
    2.97 +      const Digraph* digraph;
    2.98 +    public:
    2.99 +
   2.100 +      NodeIt() {}
   2.101 +
   2.102 +      NodeIt(Invalid i) : Node(i) { }
   2.103 +
   2.104 +      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
   2.105 +	_graph.first(static_cast<Node&>(*this));
   2.106 +      }
   2.107 +
   2.108 +      NodeIt(const Digraph& _graph, const Node& node) 
   2.109 +	: Node(node), digraph(&_graph) {}
   2.110 +
   2.111 +      NodeIt& operator++() { 
   2.112 +	digraph->next(*this);
   2.113 +	return *this; 
   2.114 +      }
   2.115 +
   2.116 +    };
   2.117 +
   2.118 +
   2.119 +    class ArcIt : public Arc { 
   2.120 +      const Digraph* digraph;
   2.121 +    public:
   2.122 +
   2.123 +      ArcIt() { }
   2.124 +
   2.125 +      ArcIt(Invalid i) : Arc(i) { }
   2.126 +
   2.127 +      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
   2.128 +	_graph.first(static_cast<Arc&>(*this));
   2.129 +      }
   2.130 +
   2.131 +      ArcIt(const Digraph& _graph, const Arc& e) : 
   2.132 +	Arc(e), digraph(&_graph) { }
   2.133 +
   2.134 +      ArcIt& operator++() { 
   2.135 +	digraph->next(*this);
   2.136 +	return *this; 
   2.137 +      }
   2.138 +
   2.139 +    };
   2.140 +
   2.141 +
   2.142 +    class OutArcIt : public Arc { 
   2.143 +      const Digraph* digraph;
   2.144 +    public:
   2.145 +
   2.146 +      OutArcIt() { }
   2.147 +
   2.148 +      OutArcIt(Invalid i) : Arc(i) { }
   2.149 +
   2.150 +      OutArcIt(const Digraph& _graph, const Node& node) 
   2.151 +	: digraph(&_graph) {
   2.152 +	_graph.firstOut(*this, node);
   2.153 +      }
   2.154 +
   2.155 +      OutArcIt(const Digraph& _graph, const Arc& arc) 
   2.156 +	: Arc(arc), digraph(&_graph) {}
   2.157 +
   2.158 +      OutArcIt& operator++() { 
   2.159 +	digraph->nextOut(*this);
   2.160 +	return *this; 
   2.161 +      }
   2.162 +
   2.163 +    };
   2.164 +
   2.165 +
   2.166 +    class InArcIt : public Arc { 
   2.167 +      const Digraph* digraph;
   2.168 +    public:
   2.169 +
   2.170 +      InArcIt() { }
   2.171 +
   2.172 +      InArcIt(Invalid i) : Arc(i) { }
   2.173 +
   2.174 +      InArcIt(const Digraph& _graph, const Node& node) 
   2.175 +	: digraph(&_graph) {
   2.176 +	_graph.firstIn(*this, node);
   2.177 +      }
   2.178 +
   2.179 +      InArcIt(const Digraph& _graph, const Arc& arc) : 
   2.180 +	Arc(arc), digraph(&_graph) {}
   2.181 +
   2.182 +      InArcIt& operator++() { 
   2.183 +	digraph->nextIn(*this);
   2.184 +	return *this; 
   2.185 +      }
   2.186 +
   2.187 +    };
   2.188 +
   2.189 +    /// \brief Base node of the iterator
   2.190 +    ///
   2.191 +    /// Returns the base node (ie. the source in this case) of the iterator
   2.192 +    Node baseNode(const OutArcIt &e) const {
   2.193 +      return Parent::source(static_cast<const Arc&>(e));
   2.194 +    }
   2.195 +    /// \brief Running node of the iterator
   2.196 +    ///
   2.197 +    /// Returns the running node (ie. the target in this case) of the
   2.198 +    /// iterator
   2.199 +    Node runningNode(const OutArcIt &e) const {
   2.200 +      return Parent::target(static_cast<const Arc&>(e));
   2.201 +    }
   2.202 +
   2.203 +    /// \brief Base node of the iterator
   2.204 +    ///
   2.205 +    /// Returns the base node (ie. the target in this case) of the iterator
   2.206 +    Node baseNode(const InArcIt &e) const {
   2.207 +      return Parent::target(static_cast<const Arc&>(e));
   2.208 +    }
   2.209 +    /// \brief Running node of the iterator
   2.210 +    ///
   2.211 +    /// Returns the running node (ie. the source in this case) of the
   2.212 +    /// iterator
   2.213 +    Node runningNode(const InArcIt &e) const {
   2.214 +      return Parent::source(static_cast<const Arc&>(e));
   2.215 +    }
   2.216 +
   2.217 +    using Parent::first;
   2.218 +
   2.219 +    // Mappable extension
   2.220 +    
   2.221 +    template <typename _Value>
   2.222 +    class ArcMap 
   2.223 +      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   2.224 +    public:
   2.225 +      typedef ArcSetExtender Digraph;
   2.226 +      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   2.227 +
   2.228 +      explicit ArcMap(const Digraph& _g) 
   2.229 +	: Parent(_g) {}
   2.230 +      ArcMap(const Digraph& _g, const _Value& _v) 
   2.231 +	: Parent(_g, _v) {}
   2.232 +
   2.233 +      ArcMap& operator=(const ArcMap& cmap) {
   2.234 +	return operator=<ArcMap>(cmap);
   2.235 +      }
   2.236 +
   2.237 +      template <typename CMap>
   2.238 +      ArcMap& operator=(const CMap& cmap) {
   2.239 +        Parent::operator=(cmap);
   2.240 +	return *this;
   2.241 +      }
   2.242 +
   2.243 +    };
   2.244 +
   2.245 +
   2.246 +    // Alteration extension
   2.247 +
   2.248 +    Arc addArc(const Node& from, const Node& to) {
   2.249 +      Arc arc = Parent::addArc(from, to);
   2.250 +      notifier(Arc()).add(arc);
   2.251 +      return arc;
   2.252 +    }
   2.253 +    
   2.254 +    void clear() {
   2.255 +      notifier(Arc()).clear();
   2.256 +      Parent::clear();
   2.257 +    }
   2.258 +
   2.259 +    void erase(const Arc& arc) {
   2.260 +      notifier(Arc()).erase(arc);
   2.261 +      Parent::erase(arc);
   2.262 +    }
   2.263 +
   2.264 +    ArcSetExtender() {
   2.265 +      arc_notifier.setContainer(*this);
   2.266 +    }
   2.267 +
   2.268 +    ~ArcSetExtender() {
   2.269 +      arc_notifier.clear();
   2.270 +    }
   2.271 +
   2.272 +  };
   2.273 +
   2.274 +
   2.275 +  /// \ingroup digraphbits
   2.276 +  ///
   2.277 +  /// \brief Extender for the EdgeSets
   2.278 +  template <typename Base>
   2.279 +  class EdgeSetExtender : public Base {
   2.280 +
   2.281 +  public:
   2.282 +
   2.283 +    typedef Base Parent;
   2.284 +    typedef EdgeSetExtender Digraph;
   2.285 +
   2.286 +    typedef typename Parent::Node Node;
   2.287 +    typedef typename Parent::Arc Arc;
   2.288 +    typedef typename Parent::Edge Edge;
   2.289 +
   2.290 +
   2.291 +    int maxId(Node) const {
   2.292 +      return Parent::maxNodeId();
   2.293 +    }
   2.294 +
   2.295 +    int maxId(Arc) const {
   2.296 +      return Parent::maxArcId();
   2.297 +    }
   2.298 +
   2.299 +    int maxId(Edge) const {
   2.300 +      return Parent::maxEdgeId();
   2.301 +    }
   2.302 +
   2.303 +    Node fromId(int id, Node) const {
   2.304 +      return Parent::nodeFromId(id);
   2.305 +    }
   2.306 +
   2.307 +    Arc fromId(int id, Arc) const {
   2.308 +      return Parent::arcFromId(id);
   2.309 +    }
   2.310 +
   2.311 +    Edge fromId(int id, Edge) const {
   2.312 +      return Parent::edgeFromId(id);
   2.313 +    }
   2.314 +
   2.315 +    Node oppositeNode(const Node &n, const Edge &e) const {
   2.316 +      if( n == Parent::u(e))
   2.317 +	return Parent::v(e);
   2.318 +      else if( n == Parent::v(e))
   2.319 +	return Parent::u(e);
   2.320 +      else
   2.321 +	return INVALID;
   2.322 +    }
   2.323 +
   2.324 +    Arc oppositeArc(const Arc &e) const {
   2.325 +      return Parent::direct(e, !Parent::direction(e));
   2.326 +    }
   2.327 +
   2.328 +    using Parent::direct;
   2.329 +    Arc direct(const Edge &e, const Node &s) const {
   2.330 +      return Parent::direct(e, Parent::u(e) == s);
   2.331 +    }
   2.332 +
   2.333 +    typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
   2.334 +    typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
   2.335 +
   2.336 +
   2.337 +  protected:
   2.338 +
   2.339 +    mutable ArcNotifier arc_notifier;
   2.340 +    mutable EdgeNotifier edge_notifier;
   2.341 +
   2.342 +  public:
   2.343 +
   2.344 +    using Parent::notifier;
   2.345 +    
   2.346 +    ArcNotifier& notifier(Arc) const {
   2.347 +      return arc_notifier;
   2.348 +    }
   2.349 +
   2.350 +    EdgeNotifier& notifier(Edge) const {
   2.351 +      return edge_notifier;
   2.352 +    }
   2.353 +
   2.354 +
   2.355 +    class NodeIt : public Node { 
   2.356 +      const Digraph* digraph;
   2.357 +    public:
   2.358 +
   2.359 +      NodeIt() {}
   2.360 +
   2.361 +      NodeIt(Invalid i) : Node(i) { }
   2.362 +
   2.363 +      explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
   2.364 +	_graph.first(static_cast<Node&>(*this));
   2.365 +      }
   2.366 +
   2.367 +      NodeIt(const Digraph& _graph, const Node& node) 
   2.368 +	: Node(node), digraph(&_graph) {}
   2.369 +
   2.370 +      NodeIt& operator++() { 
   2.371 +	digraph->next(*this);
   2.372 +	return *this; 
   2.373 +      }
   2.374 +
   2.375 +    };
   2.376 +
   2.377 +
   2.378 +    class ArcIt : public Arc { 
   2.379 +      const Digraph* digraph;
   2.380 +    public:
   2.381 +
   2.382 +      ArcIt() { }
   2.383 +
   2.384 +      ArcIt(Invalid i) : Arc(i) { }
   2.385 +
   2.386 +      explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
   2.387 +	_graph.first(static_cast<Arc&>(*this));
   2.388 +      }
   2.389 +
   2.390 +      ArcIt(const Digraph& _graph, const Arc& e) : 
   2.391 +	Arc(e), digraph(&_graph) { }
   2.392 +
   2.393 +      ArcIt& operator++() { 
   2.394 +	digraph->next(*this);
   2.395 +	return *this; 
   2.396 +      }
   2.397 +
   2.398 +    };
   2.399 +
   2.400 +
   2.401 +    class OutArcIt : public Arc { 
   2.402 +      const Digraph* digraph;
   2.403 +    public:
   2.404 +
   2.405 +      OutArcIt() { }
   2.406 +
   2.407 +      OutArcIt(Invalid i) : Arc(i) { }
   2.408 +
   2.409 +      OutArcIt(const Digraph& _graph, const Node& node) 
   2.410 +	: digraph(&_graph) {
   2.411 +	_graph.firstOut(*this, node);
   2.412 +      }
   2.413 +
   2.414 +      OutArcIt(const Digraph& _graph, const Arc& arc) 
   2.415 +	: Arc(arc), digraph(&_graph) {}
   2.416 +
   2.417 +      OutArcIt& operator++() { 
   2.418 +	digraph->nextOut(*this);
   2.419 +	return *this; 
   2.420 +      }
   2.421 +
   2.422 +    };
   2.423 +
   2.424 +
   2.425 +    class InArcIt : public Arc { 
   2.426 +      const Digraph* digraph;
   2.427 +    public:
   2.428 +
   2.429 +      InArcIt() { }
   2.430 +
   2.431 +      InArcIt(Invalid i) : Arc(i) { }
   2.432 +
   2.433 +      InArcIt(const Digraph& _graph, const Node& node) 
   2.434 +	: digraph(&_graph) {
   2.435 +	_graph.firstIn(*this, node);
   2.436 +      }
   2.437 +
   2.438 +      InArcIt(const Digraph& _graph, const Arc& arc) : 
   2.439 +	Arc(arc), digraph(&_graph) {}
   2.440 +
   2.441 +      InArcIt& operator++() { 
   2.442 +	digraph->nextIn(*this);
   2.443 +	return *this; 
   2.444 +      }
   2.445 +
   2.446 +    };
   2.447 +
   2.448 +
   2.449 +    class EdgeIt : public Parent::Edge { 
   2.450 +      const Digraph* digraph;
   2.451 +    public:
   2.452 +
   2.453 +      EdgeIt() { }
   2.454 +
   2.455 +      EdgeIt(Invalid i) : Edge(i) { }
   2.456 +
   2.457 +      explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
   2.458 +	_graph.first(static_cast<Edge&>(*this));
   2.459 +      }
   2.460 +
   2.461 +      EdgeIt(const Digraph& _graph, const Edge& e) : 
   2.462 +	Edge(e), digraph(&_graph) { }
   2.463 +
   2.464 +      EdgeIt& operator++() { 
   2.465 +	digraph->next(*this);
   2.466 +	return *this; 
   2.467 +      }
   2.468 +
   2.469 +    };
   2.470 +
   2.471 +    class IncEdgeIt : public Parent::Edge {
   2.472 +      friend class EdgeSetExtender;
   2.473 +      const Digraph* digraph;
   2.474 +      bool direction;
   2.475 +    public:
   2.476 +
   2.477 +      IncEdgeIt() { }
   2.478 +
   2.479 +      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   2.480 +
   2.481 +      IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
   2.482 +	_graph.firstInc(*this, direction, n);
   2.483 +      }
   2.484 +
   2.485 +      IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
   2.486 +	: digraph(&_graph), Edge(ue) {
   2.487 +	direction = (_graph.source(ue) == n);
   2.488 +      }
   2.489 +
   2.490 +      IncEdgeIt& operator++() {
   2.491 +	digraph->nextInc(*this, direction);
   2.492 +	return *this; 
   2.493 +      }
   2.494 +    };
   2.495 +
   2.496 +    /// \brief Base node of the iterator
   2.497 +    ///
   2.498 +    /// Returns the base node (ie. the source in this case) of the iterator
   2.499 +    Node baseNode(const OutArcIt &e) const {
   2.500 +      return Parent::source(static_cast<const Arc&>(e));
   2.501 +    }
   2.502 +    /// \brief Running node of the iterator
   2.503 +    ///
   2.504 +    /// Returns the running node (ie. the target in this case) of the
   2.505 +    /// iterator
   2.506 +    Node runningNode(const OutArcIt &e) const {
   2.507 +      return Parent::target(static_cast<const Arc&>(e));
   2.508 +    }
   2.509 +
   2.510 +    /// \brief Base node of the iterator
   2.511 +    ///
   2.512 +    /// Returns the base node (ie. the target in this case) of the iterator
   2.513 +    Node baseNode(const InArcIt &e) const {
   2.514 +      return Parent::target(static_cast<const Arc&>(e));
   2.515 +    }
   2.516 +    /// \brief Running node of the iterator
   2.517 +    ///
   2.518 +    /// Returns the running node (ie. the source in this case) of the
   2.519 +    /// iterator
   2.520 +    Node runningNode(const InArcIt &e) const {
   2.521 +      return Parent::source(static_cast<const Arc&>(e));
   2.522 +    }
   2.523 +
   2.524 +    /// Base node of the iterator
   2.525 +    ///
   2.526 +    /// Returns the base node of the iterator
   2.527 +    Node baseNode(const IncEdgeIt &e) const {
   2.528 +      return e.direction ? u(e) : v(e);
   2.529 +    }
   2.530 +    /// Running node of the iterator
   2.531 +    ///
   2.532 +    /// Returns the running node of the iterator
   2.533 +    Node runningNode(const IncEdgeIt &e) const {
   2.534 +      return e.direction ? v(e) : u(e);
   2.535 +    }
   2.536 +
   2.537 +
   2.538 +    template <typename _Value>
   2.539 +    class ArcMap 
   2.540 +      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   2.541 +    public:
   2.542 +      typedef EdgeSetExtender Digraph;
   2.543 +      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   2.544 +
   2.545 +      ArcMap(const Digraph& _g) 
   2.546 +	: Parent(_g) {}
   2.547 +      ArcMap(const Digraph& _g, const _Value& _v) 
   2.548 +	: Parent(_g, _v) {}
   2.549 +
   2.550 +      ArcMap& operator=(const ArcMap& cmap) {
   2.551 +	return operator=<ArcMap>(cmap);
   2.552 +      }
   2.553 +
   2.554 +      template <typename CMap>
   2.555 +      ArcMap& operator=(const CMap& cmap) {
   2.556 +        Parent::operator=(cmap);
   2.557 +	return *this;
   2.558 +      }
   2.559 +
   2.560 +    };
   2.561 +
   2.562 +
   2.563 +    template <typename _Value>
   2.564 +    class EdgeMap 
   2.565 +      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
   2.566 +    public:
   2.567 +      typedef EdgeSetExtender Digraph;
   2.568 +      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
   2.569 +
   2.570 +      EdgeMap(const Digraph& _g) 
   2.571 +	: Parent(_g) {}
   2.572 +
   2.573 +      EdgeMap(const Digraph& _g, const _Value& _v) 
   2.574 +	: Parent(_g, _v) {}
   2.575 +
   2.576 +      EdgeMap& operator=(const EdgeMap& cmap) {
   2.577 +	return operator=<EdgeMap>(cmap);
   2.578 +      }
   2.579 +
   2.580 +      template <typename CMap>
   2.581 +      EdgeMap& operator=(const CMap& cmap) {
   2.582 +        Parent::operator=(cmap);
   2.583 +	return *this;
   2.584 +      }
   2.585 +
   2.586 +    };
   2.587 +
   2.588 +
   2.589 +    // Alteration extension
   2.590 +
   2.591 +    Edge addEdge(const Node& from, const Node& to) {
   2.592 +      Edge edge = Parent::addEdge(from, to);
   2.593 +      notifier(Edge()).add(edge);
   2.594 +      std::vector<Arc> arcs;
   2.595 +      arcs.push_back(Parent::direct(edge, true));
   2.596 +      arcs.push_back(Parent::direct(edge, false));
   2.597 +      notifier(Arc()).add(arcs);
   2.598 +      return edge;
   2.599 +    }
   2.600 +    
   2.601 +    void clear() {
   2.602 +      notifier(Arc()).clear();
   2.603 +      notifier(Edge()).clear();
   2.604 +      Parent::clear();
   2.605 +    }
   2.606 +
   2.607 +    void erase(const Edge& edge) {
   2.608 +      std::vector<Arc> arcs;
   2.609 +      arcs.push_back(Parent::direct(edge, true));
   2.610 +      arcs.push_back(Parent::direct(edge, false));
   2.611 +      notifier(Arc()).erase(arcs);
   2.612 +      notifier(Edge()).erase(edge);
   2.613 +      Parent::erase(edge);
   2.614 +    }
   2.615 +
   2.616 +
   2.617 +    EdgeSetExtender() {
   2.618 +      arc_notifier.setContainer(*this);
   2.619 +      edge_notifier.setContainer(*this);
   2.620 +    }
   2.621 +
   2.622 +    ~EdgeSetExtender() {
   2.623 +      edge_notifier.clear();
   2.624 +      arc_notifier.clear();
   2.625 +    }
   2.626 +    
   2.627 +  };
   2.628 +
   2.629 +}
   2.630 +
   2.631 +#endif
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/lemon/edge_set.h	Mon Jan 12 13:37:37 2009 +0000
     3.3 @@ -0,0 +1,1410 @@
     3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     3.5 + *
     3.6 + * This file is a part of LEMON, a generic C++ optimization library.
     3.7 + *
     3.8 + * Copyright (C) 2003-2008
     3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    3.11 + *
    3.12 + * Permission to use, modify and distribute this software is granted
    3.13 + * provided that this copyright notice appears in all copies. For
    3.14 + * precise terms see the accompanying LICENSE file.
    3.15 + *
    3.16 + * This software is provided "AS IS" with no warranty of any kind,
    3.17 + * express or implied, and with no claim as to its suitability for any
    3.18 + * purpose.
    3.19 + *
    3.20 + */
    3.21 +
    3.22 +#ifndef LEMON_EDGE_SET_H
    3.23 +#define LEMON_EDGE_SET_H
    3.24 +
    3.25 +#include <lemon/core.h>
    3.26 +#include <lemon/bits/edge_set_extender.h>
    3.27 +
    3.28 +/// \ingroup semi_adaptors
    3.29 +/// \file
    3.30 +/// \brief ArcSet and EdgeSet classes.
    3.31 +///
    3.32 +/// Graphs which use another graph's node-set as own.
    3.33 +namespace lemon {
    3.34 +
    3.35 +  template <typename _Graph>
    3.36 +  class ListArcSetBase {
    3.37 +  public:
    3.38 +
    3.39 +    typedef _Graph Graph;
    3.40 +    typedef typename Graph::Node Node;
    3.41 +    typedef typename Graph::NodeIt NodeIt;
    3.42 +
    3.43 +  protected:
    3.44 +
    3.45 +    struct NodeT {
    3.46 +      int first_out, first_in;
    3.47 +      NodeT() : first_out(-1), first_in(-1) {}
    3.48 +    };
    3.49 +
    3.50 +    typedef typename ItemSetTraits<Graph, Node>::
    3.51 +    template Map<NodeT>::Type NodesImplBase;
    3.52 +
    3.53 +    NodesImplBase* nodes;
    3.54 +
    3.55 +    struct ArcT {
    3.56 +      Node source, target;
    3.57 +      int next_out, next_in;
    3.58 +      int prev_out, prev_in;
    3.59 +      ArcT() : prev_out(-1), prev_in(-1) {}
    3.60 +    };
    3.61 +
    3.62 +    std::vector<ArcT> arcs;
    3.63 +
    3.64 +    int first_arc;
    3.65 +    int first_free_arc;
    3.66 +
    3.67 +    const Graph* graph;
    3.68 +
    3.69 +    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    3.70 +      graph = &_graph;
    3.71 +      nodes = &_nodes;
    3.72 +    }
    3.73 +
    3.74 +  public:
    3.75 +
    3.76 +    class Arc {
    3.77 +      friend class ListArcSetBase<Graph>;
    3.78 +    protected:
    3.79 +      Arc(int _id) : id(_id) {}
    3.80 +      int id;
    3.81 +    public:
    3.82 +      Arc() {}
    3.83 +      Arc(Invalid) : id(-1) {}
    3.84 +      bool operator==(const Arc& arc) const { return id == arc.id; }
    3.85 +      bool operator!=(const Arc& arc) const { return id != arc.id; }
    3.86 +      bool operator<(const Arc& arc) const { return id < arc.id; }
    3.87 +    };
    3.88 +
    3.89 +    ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
    3.90 +
    3.91 +    Arc addArc(const Node& u, const Node& v) {
    3.92 +      int n;
    3.93 +      if (first_free_arc == -1) {
    3.94 +        n = arcs.size();
    3.95 +        arcs.push_back(ArcT());
    3.96 +      } else {
    3.97 +        n = first_free_arc;
    3.98 +        first_free_arc = arcs[first_free_arc].next_in;
    3.99 +      }
   3.100 +      arcs[n].next_in = (*nodes)[v].first_in;
   3.101 +      if ((*nodes)[v].first_in != -1) {
   3.102 +        arcs[(*nodes)[v].first_in].prev_in = n;
   3.103 +      }
   3.104 +      (*nodes)[v].first_in = n;
   3.105 +      arcs[n].next_out = (*nodes)[u].first_out;
   3.106 +      if ((*nodes)[u].first_out != -1) {
   3.107 +        arcs[(*nodes)[u].first_out].prev_out = n;
   3.108 +      }
   3.109 +      (*nodes)[u].first_out = n;
   3.110 +      arcs[n].source = u;
   3.111 +      arcs[n].target = v;
   3.112 +      return Arc(n);
   3.113 +    }
   3.114 +
   3.115 +    void erase(const Arc& arc) {
   3.116 +      int n = arc.id;
   3.117 +      if (arcs[n].prev_in != -1) {
   3.118 +        arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   3.119 +      } else {
   3.120 +        (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
   3.121 +      }
   3.122 +      if (arcs[n].next_in != -1) {
   3.123 +        arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   3.124 +      }
   3.125 +
   3.126 +      if (arcs[n].prev_out != -1) {
   3.127 +        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   3.128 +      } else {
   3.129 +        (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
   3.130 +      }
   3.131 +      if (arcs[n].next_out != -1) {
   3.132 +        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   3.133 +      }
   3.134 +
   3.135 +    }
   3.136 +
   3.137 +    void clear() {
   3.138 +      Node node;
   3.139 +      for (first(node); node != INVALID; next(node)) {
   3.140 +        (*nodes)[node].first_in = -1;
   3.141 +        (*nodes)[node].first_out = -1;
   3.142 +      }
   3.143 +      arcs.clear();
   3.144 +      first_arc = -1;
   3.145 +      first_free_arc = -1;
   3.146 +    }
   3.147 +
   3.148 +    void first(Node& node) const {
   3.149 +      graph->first(node);
   3.150 +    }
   3.151 +
   3.152 +    void next(Node& node) const {
   3.153 +      graph->next(node);
   3.154 +    }
   3.155 +
   3.156 +    void first(Arc& arc) const {
   3.157 +      Node node;
   3.158 +      first(node);
   3.159 +      while (node != INVALID && (*nodes)[node].first_in == -1) {
   3.160 +        next(node);
   3.161 +      }
   3.162 +      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   3.163 +    }
   3.164 +
   3.165 +    void next(Arc& arc) const {
   3.166 +      if (arcs[arc.id].next_in != -1) {
   3.167 +        arc.id = arcs[arc.id].next_in;
   3.168 +      } else {
   3.169 +        Node node = arcs[arc.id].target;
   3.170 +        next(node);
   3.171 +        while (node != INVALID && (*nodes)[node].first_in == -1) {
   3.172 +          next(node);
   3.173 +        }
   3.174 +        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   3.175 +      }
   3.176 +    }
   3.177 +
   3.178 +    void firstOut(Arc& arc, const Node& node) const {
   3.179 +      arc.id = (*nodes)[node].first_out;
   3.180 +    }
   3.181 +
   3.182 +    void nextOut(Arc& arc) const {
   3.183 +      arc.id = arcs[arc.id].next_out;
   3.184 +    }
   3.185 +
   3.186 +    void firstIn(Arc& arc, const Node& node) const {
   3.187 +      arc.id = (*nodes)[node].first_in;
   3.188 +    }
   3.189 +
   3.190 +    void nextIn(Arc& arc) const {
   3.191 +      arc.id = arcs[arc.id].next_in;
   3.192 +    }
   3.193 +
   3.194 +    int id(const Node& node) const { return graph->id(node); }
   3.195 +    int id(const Arc& arc) const { return arc.id; }
   3.196 +
   3.197 +    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
   3.198 +    Arc arcFromId(int ix) const { return Arc(ix); }
   3.199 +
   3.200 +    int maxNodeId() const { return graph->maxNodeId(); };
   3.201 +    int maxArcId() const { return arcs.size() - 1; }
   3.202 +
   3.203 +    Node source(const Arc& arc) const { return arcs[arc.id].source;}
   3.204 +    Node target(const Arc& arc) const { return arcs[arc.id].target;}
   3.205 +
   3.206 +    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   3.207 +
   3.208 +    NodeNotifier& notifier(Node) const {
   3.209 +      return graph->notifier(Node());
   3.210 +    }
   3.211 +
   3.212 +    template <typename _Value>
   3.213 +    class NodeMap : public Graph::template NodeMap<_Value> {
   3.214 +    public:
   3.215 +
   3.216 +      typedef typename _Graph::template NodeMap<_Value> Parent;
   3.217 +
   3.218 +      explicit NodeMap(const ListArcSetBase<Graph>& arcset)
   3.219 +        : Parent(*arcset.graph) {}
   3.220 +
   3.221 +      NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
   3.222 +        : Parent(*arcset.graph, value) {}
   3.223 +
   3.224 +      NodeMap& operator=(const NodeMap& cmap) {
   3.225 +        return operator=<NodeMap>(cmap);
   3.226 +      }
   3.227 +
   3.228 +      template <typename CMap>
   3.229 +      NodeMap& operator=(const CMap& cmap) {
   3.230 +        Parent::operator=(cmap);
   3.231 +        return *this;
   3.232 +      }
   3.233 +    };
   3.234 +
   3.235 +  };
   3.236 +
   3.237 +  /// \ingroup semi_adaptors
   3.238 +  ///
   3.239 +  /// \brief Digraph using a node set of another digraph or graph and
   3.240 +  /// an own arc set.
   3.241 +  ///
   3.242 +  /// This structure can be used to establish another directed graph
   3.243 +  /// over a node set of an existing one. This class uses the same
   3.244 +  /// Node type as the underlying graph, and each valid node of the
   3.245 +  /// original graph is valid in this arc set, therefore the node
   3.246 +  /// objects of the original graph can be used directly with this
   3.247 +  /// class. The node handling functions (id handling, observing, and
   3.248 +  /// iterators) works equivalently as in the original graph.
   3.249 +  ///
   3.250 +  /// This implementation is based on doubly-linked lists, from each
   3.251 +  /// node the outgoing and the incoming arcs make up lists, therefore
   3.252 +  /// one arc can be erased in constant time. It also makes possible,
   3.253 +  /// that node can be removed from the underlying graph, in this case
   3.254 +  /// all arcs incident to the given node is erased from the arc set.
   3.255 +  ///
   3.256 +  /// \param _Graph The type of the graph which shares its node set with
   3.257 +  /// this class. Its interface must conform to the
   3.258 +  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   3.259 +  /// concept.
   3.260 +  ///
   3.261 +  /// This class is fully conform to the \ref concepts::Digraph
   3.262 +  /// "Digraph" concept.
   3.263 +  template <typename _Graph>
   3.264 +  class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
   3.265 +
   3.266 +  public:
   3.267 +
   3.268 +    typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
   3.269 +
   3.270 +    typedef typename Parent::Node Node;
   3.271 +    typedef typename Parent::Arc Arc;
   3.272 +
   3.273 +    typedef _Graph Graph;
   3.274 +
   3.275 +
   3.276 +    typedef typename Parent::NodesImplBase NodesImplBase;
   3.277 +
   3.278 +    void eraseNode(const Node& node) {
   3.279 +      Arc arc;
   3.280 +      Parent::firstOut(arc, node);
   3.281 +      while (arc != INVALID ) {
   3.282 +        erase(arc);
   3.283 +        Parent::firstOut(arc, node);
   3.284 +      }
   3.285 +
   3.286 +      Parent::firstIn(arc, node);
   3.287 +      while (arc != INVALID ) {
   3.288 +        erase(arc);
   3.289 +        Parent::firstIn(arc, node);
   3.290 +      }
   3.291 +    }
   3.292 +
   3.293 +    void clearNodes() {
   3.294 +      Parent::clear();
   3.295 +    }
   3.296 +
   3.297 +    class NodesImpl : public NodesImplBase {
   3.298 +    public:
   3.299 +      typedef NodesImplBase Parent;
   3.300 +
   3.301 +      NodesImpl(const Graph& graph, ListArcSet& arcset)
   3.302 +        : Parent(graph), _arcset(arcset) {}
   3.303 +
   3.304 +      virtual ~NodesImpl() {}
   3.305 +
   3.306 +    protected:
   3.307 +
   3.308 +      virtual void erase(const Node& node) {
   3.309 +        _arcset.eraseNode(node);
   3.310 +        Parent::erase(node);
   3.311 +      }
   3.312 +      virtual void erase(const std::vector<Node>& nodes) {
   3.313 +        for (int i = 0; i < int(nodes.size()); ++i) {
   3.314 +          _arcset.eraseNode(nodes[i]);
   3.315 +        }
   3.316 +        Parent::erase(nodes);
   3.317 +      }
   3.318 +      virtual void clear() {
   3.319 +        _arcset.clearNodes();
   3.320 +        Parent::clear();
   3.321 +      }
   3.322 +
   3.323 +    private:
   3.324 +      ListArcSet& _arcset;
   3.325 +    };
   3.326 +
   3.327 +    NodesImpl nodes;
   3.328 +
   3.329 +  public:
   3.330 +
   3.331 +    /// \brief Constructor of the ArcSet.
   3.332 +    ///
   3.333 +    /// Constructor of the ArcSet.
   3.334 +    ListArcSet(const Graph& graph) : nodes(graph, *this) {
   3.335 +      Parent::initalize(graph, nodes);
   3.336 +    }
   3.337 +
   3.338 +    /// \brief Add a new arc to the digraph.
   3.339 +    ///
   3.340 +    /// Add a new arc to the digraph with source node \c s
   3.341 +    /// and target node \c t.
   3.342 +    /// \return the new arc.
   3.343 +    Arc addArc(const Node& s, const Node& t) {
   3.344 +      return Parent::addArc(s, t);
   3.345 +    }
   3.346 +
   3.347 +    /// \brief Erase an arc from the digraph.
   3.348 +    ///
   3.349 +    /// Erase an arc \c a from the digraph.
   3.350 +    void erase(const Arc& a) {
   3.351 +      return Parent::erase(a);
   3.352 +    }
   3.353 +
   3.354 +  };
   3.355 +
   3.356 +  template <typename _Graph>
   3.357 +  class ListEdgeSetBase {
   3.358 +  public:
   3.359 +
   3.360 +    typedef _Graph Graph;
   3.361 +    typedef typename Graph::Node Node;
   3.362 +    typedef typename Graph::NodeIt NodeIt;
   3.363 +
   3.364 +  protected:
   3.365 +
   3.366 +    struct NodeT {
   3.367 +      int first_out;
   3.368 +      NodeT() : first_out(-1) {}
   3.369 +    };
   3.370 +
   3.371 +    typedef typename ItemSetTraits<Graph, Node>::
   3.372 +    template Map<NodeT>::Type NodesImplBase;
   3.373 +
   3.374 +    NodesImplBase* nodes;
   3.375 +
   3.376 +    struct ArcT {
   3.377 +      Node target;
   3.378 +      int prev_out, next_out;
   3.379 +      ArcT() : prev_out(-1), next_out(-1) {}
   3.380 +    };
   3.381 +
   3.382 +    std::vector<ArcT> arcs;
   3.383 +
   3.384 +    int first_arc;
   3.385 +    int first_free_arc;
   3.386 +
   3.387 +    const Graph* graph;
   3.388 +
   3.389 +    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
   3.390 +      graph = &_graph;
   3.391 +      nodes = &_nodes;
   3.392 +    }
   3.393 +
   3.394 +  public:
   3.395 +
   3.396 +    class Edge {
   3.397 +      friend class ListEdgeSetBase;
   3.398 +    protected:
   3.399 +
   3.400 +      int id;
   3.401 +      explicit Edge(int _id) { id = _id;}
   3.402 +
   3.403 +    public:
   3.404 +      Edge() {}
   3.405 +      Edge (Invalid) { id = -1; }
   3.406 +      bool operator==(const Edge& arc) const {return id == arc.id;}
   3.407 +      bool operator!=(const Edge& arc) const {return id != arc.id;}
   3.408 +      bool operator<(const Edge& arc) const {return id < arc.id;}
   3.409 +    };
   3.410 +
   3.411 +    class Arc {
   3.412 +      friend class ListEdgeSetBase;
   3.413 +    protected:
   3.414 +      Arc(int _id) : id(_id) {}
   3.415 +      int id;
   3.416 +    public:
   3.417 +      operator Edge() const { return edgeFromId(id / 2); }
   3.418 +
   3.419 +      Arc() {}
   3.420 +      Arc(Invalid) : id(-1) {}
   3.421 +      bool operator==(const Arc& arc) const { return id == arc.id; }
   3.422 +      bool operator!=(const Arc& arc) const { return id != arc.id; }
   3.423 +      bool operator<(const Arc& arc) const { return id < arc.id; }
   3.424 +    };
   3.425 +
   3.426 +    ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
   3.427 +
   3.428 +    Edge addEdge(const Node& u, const Node& v) {
   3.429 +      int n;
   3.430 +
   3.431 +      if (first_free_arc == -1) {
   3.432 +        n = arcs.size();
   3.433 +        arcs.push_back(ArcT());
   3.434 +        arcs.push_back(ArcT());
   3.435 +      } else {
   3.436 +        n = first_free_arc;
   3.437 +        first_free_arc = arcs[n].next_out;
   3.438 +      }
   3.439 +
   3.440 +      arcs[n].target = u;
   3.441 +      arcs[n | 1].target = v;
   3.442 +
   3.443 +      arcs[n].next_out = (*nodes)[v].first_out;
   3.444 +      if ((*nodes)[v].first_out != -1) {
   3.445 +        arcs[(*nodes)[v].first_out].prev_out = n;
   3.446 +      }
   3.447 +      (*nodes)[v].first_out = n;
   3.448 +      arcs[n].prev_out = -1;
   3.449 +
   3.450 +      if ((*nodes)[u].first_out != -1) {
   3.451 +        arcs[(*nodes)[u].first_out].prev_out = (n | 1);
   3.452 +      }
   3.453 +      arcs[n | 1].next_out = (*nodes)[u].first_out;
   3.454 +      (*nodes)[u].first_out = (n | 1);
   3.455 +      arcs[n | 1].prev_out = -1;
   3.456 +
   3.457 +      return Edge(n / 2);
   3.458 +    }
   3.459 +
   3.460 +    void erase(const Edge& arc) {
   3.461 +      int n = arc.id * 2;
   3.462 +
   3.463 +      if (arcs[n].next_out != -1) {
   3.464 +        arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   3.465 +      }
   3.466 +
   3.467 +      if (arcs[n].prev_out != -1) {
   3.468 +        arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   3.469 +      } else {
   3.470 +        (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
   3.471 +      }
   3.472 +
   3.473 +      if (arcs[n | 1].next_out != -1) {
   3.474 +        arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   3.475 +      }
   3.476 +
   3.477 +      if (arcs[n | 1].prev_out != -1) {
   3.478 +        arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   3.479 +      } else {
   3.480 +        (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
   3.481 +      }
   3.482 +
   3.483 +      arcs[n].next_out = first_free_arc;
   3.484 +      first_free_arc = n;
   3.485 +
   3.486 +    }
   3.487 +
   3.488 +    void clear() {
   3.489 +      Node node;
   3.490 +      for (first(node); node != INVALID; next(node)) {
   3.491 +        (*nodes)[node].first_out = -1;
   3.492 +      }
   3.493 +      arcs.clear();
   3.494 +      first_arc = -1;
   3.495 +      first_free_arc = -1;
   3.496 +    }
   3.497 +
   3.498 +    void first(Node& node) const {
   3.499 +      graph->first(node);
   3.500 +    }
   3.501 +
   3.502 +    void next(Node& node) const {
   3.503 +      graph->next(node);
   3.504 +    }
   3.505 +
   3.506 +    void first(Arc& arc) const {
   3.507 +      Node node;
   3.508 +      first(node);
   3.509 +      while (node != INVALID && (*nodes)[node].first_out == -1) {
   3.510 +        next(node);
   3.511 +      }
   3.512 +      arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
   3.513 +    }
   3.514 +
   3.515 +    void next(Arc& arc) const {
   3.516 +      if (arcs[arc.id].next_out != -1) {
   3.517 +        arc.id = arcs[arc.id].next_out;
   3.518 +      } else {
   3.519 +        Node node = arcs[arc.id ^ 1].target;
   3.520 +        next(node);
   3.521 +        while(node != INVALID && (*nodes)[node].first_out == -1) {
   3.522 +          next(node);
   3.523 +        }
   3.524 +        arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
   3.525 +      }
   3.526 +    }
   3.527 +
   3.528 +    void first(Edge& edge) const {
   3.529 +      Node node;
   3.530 +      first(node);
   3.531 +      while (node != INVALID) {
   3.532 +        edge.id = (*nodes)[node].first_out;
   3.533 +        while ((edge.id & 1) != 1) {
   3.534 +          edge.id = arcs[edge.id].next_out;
   3.535 +        }
   3.536 +        if (edge.id != -1) {
   3.537 +          edge.id /= 2;
   3.538 +          return;
   3.539 +        }
   3.540 +        next(node);
   3.541 +      }
   3.542 +      edge.id = -1;
   3.543 +    }
   3.544 +
   3.545 +    void next(Edge& edge) const {
   3.546 +      Node node = arcs[edge.id * 2].target;
   3.547 +      edge.id = arcs[(edge.id * 2) | 1].next_out;
   3.548 +      while ((edge.id & 1) != 1) {
   3.549 +        edge.id = arcs[edge.id].next_out;
   3.550 +      }
   3.551 +      if (edge.id != -1) {
   3.552 +        edge.id /= 2;
   3.553 +        return;
   3.554 +      }
   3.555 +      next(node);
   3.556 +      while (node != INVALID) {
   3.557 +        edge.id = (*nodes)[node].first_out;
   3.558 +        while ((edge.id & 1) != 1) {
   3.559 +          edge.id = arcs[edge.id].next_out;
   3.560 +        }
   3.561 +        if (edge.id != -1) {
   3.562 +          edge.id /= 2;
   3.563 +          return;
   3.564 +        }
   3.565 +        next(node);
   3.566 +      }
   3.567 +      edge.id = -1;
   3.568 +    }
   3.569 +
   3.570 +    void firstOut(Arc& arc, const Node& node) const {
   3.571 +      arc.id = (*nodes)[node].first_out;
   3.572 +    }
   3.573 +
   3.574 +    void nextOut(Arc& arc) const {
   3.575 +      arc.id = arcs[arc.id].next_out;
   3.576 +    }
   3.577 +
   3.578 +    void firstIn(Arc& arc, const Node& node) const {
   3.579 +      arc.id = (((*nodes)[node].first_out) ^ 1);
   3.580 +      if (arc.id == -2) arc.id = -1;
   3.581 +    }
   3.582 +
   3.583 +    void nextIn(Arc& arc) const {
   3.584 +      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
   3.585 +      if (arc.id == -2) arc.id = -1;
   3.586 +    }
   3.587 +
   3.588 +    void firstInc(Edge &arc, bool& dir, const Node& node) const {
   3.589 +      int de = (*nodes)[node].first_out;
   3.590 +      if (de != -1 ) {
   3.591 +        arc.id = de / 2;
   3.592 +        dir = ((de & 1) == 1);
   3.593 +      } else {
   3.594 +        arc.id = -1;
   3.595 +        dir = true;
   3.596 +      }
   3.597 +    }
   3.598 +    void nextInc(Edge &arc, bool& dir) const {
   3.599 +      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
   3.600 +      if (de != -1 ) {
   3.601 +        arc.id = de / 2;
   3.602 +        dir = ((de & 1) == 1);
   3.603 +      } else {
   3.604 +        arc.id = -1;
   3.605 +        dir = true;
   3.606 +      }
   3.607 +    }
   3.608 +
   3.609 +    static bool direction(Arc arc) {
   3.610 +      return (arc.id & 1) == 1;
   3.611 +    }
   3.612 +
   3.613 +    static Arc direct(Edge edge, bool dir) {
   3.614 +      return Arc(edge.id * 2 + (dir ? 1 : 0));
   3.615 +    }
   3.616 +
   3.617 +    int id(const Node& node) const { return graph->id(node); }
   3.618 +    static int id(Arc e) { return e.id; }
   3.619 +    static int id(Edge e) { return e.id; }
   3.620 +
   3.621 +    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
   3.622 +    static Arc arcFromId(int id) { return Arc(id);}
   3.623 +    static Edge edgeFromId(int id) { return Edge(id);}
   3.624 +
   3.625 +    int maxNodeId() const { return graph->maxNodeId(); };
   3.626 +    int maxEdgeId() const { return arcs.size() / 2 - 1; }
   3.627 +    int maxArcId() const { return arcs.size()-1; }
   3.628 +
   3.629 +    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
   3.630 +    Node target(Arc e) const { return arcs[e.id].target; }
   3.631 +
   3.632 +    Node u(Edge e) const { return arcs[2 * e.id].target; }
   3.633 +    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
   3.634 +
   3.635 +    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   3.636 +
   3.637 +    NodeNotifier& notifier(Node) const {
   3.638 +      return graph->notifier(Node());
   3.639 +    }
   3.640 +
   3.641 +    template <typename _Value>
   3.642 +    class NodeMap : public Graph::template NodeMap<_Value> {
   3.643 +    public:
   3.644 +
   3.645 +      typedef typename _Graph::template NodeMap<_Value> Parent;
   3.646 +
   3.647 +      explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
   3.648 +        : Parent(*arcset.graph) {}
   3.649 +
   3.650 +      NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
   3.651 +        : Parent(*arcset.graph, value) {}
   3.652 +
   3.653 +      NodeMap& operator=(const NodeMap& cmap) {
   3.654 +        return operator=<NodeMap>(cmap);
   3.655 +      }
   3.656 +
   3.657 +      template <typename CMap>
   3.658 +      NodeMap& operator=(const CMap& cmap) {
   3.659 +        Parent::operator=(cmap);
   3.660 +        return *this;
   3.661 +      }
   3.662 +    };
   3.663 +
   3.664 +  };
   3.665 +
   3.666 +  /// \ingroup semi_adaptors
   3.667 +  ///
   3.668 +  /// \brief Graph using a node set of another digraph or graph and an
   3.669 +  /// own edge set.
   3.670 +  ///
   3.671 +  /// This structure can be used to establish another graph over a
   3.672 +  /// node set of an existing one. This class uses the same Node type
   3.673 +  /// as the underlying graph, and each valid node of the original
   3.674 +  /// graph is valid in this arc set, therefore the node objects of
   3.675 +  /// the original graph can be used directly with this class. The
   3.676 +  /// node handling functions (id handling, observing, and iterators)
   3.677 +  /// works equivalently as in the original graph.
   3.678 +  ///
   3.679 +  /// This implementation is based on doubly-linked lists, from each
   3.680 +  /// node the incident edges make up lists, therefore one edge can be
   3.681 +  /// erased in constant time. It also makes possible, that node can
   3.682 +  /// be removed from the underlying graph, in this case all edges
   3.683 +  /// incident to the given node is erased from the arc set.
   3.684 +  ///
   3.685 +  /// \param _Graph The type of the graph which shares its node set
   3.686 +  /// with this class. Its interface must conform to the
   3.687 +  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   3.688 +  /// concept.
   3.689 +  ///
   3.690 +  /// This class is fully conform to the \ref concepts::Graph "Graph"
   3.691 +  /// concept.
   3.692 +  template <typename _Graph>
   3.693 +  class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
   3.694 +
   3.695 +  public:
   3.696 +
   3.697 +    typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
   3.698 +
   3.699 +    typedef typename Parent::Node Node;
   3.700 +    typedef typename Parent::Arc Arc;
   3.701 +    typedef typename Parent::Edge Edge;
   3.702 +
   3.703 +    typedef _Graph Graph;
   3.704 +
   3.705 +
   3.706 +    typedef typename Parent::NodesImplBase NodesImplBase;
   3.707 +
   3.708 +    void eraseNode(const Node& node) {
   3.709 +      Arc arc;
   3.710 +      Parent::firstOut(arc, node);
   3.711 +      while (arc != INVALID ) {
   3.712 +        erase(arc);
   3.713 +        Parent::firstOut(arc, node);
   3.714 +      }
   3.715 +
   3.716 +    }
   3.717 +
   3.718 +    void clearNodes() {
   3.719 +      Parent::clear();
   3.720 +    }
   3.721 +
   3.722 +    class NodesImpl : public NodesImplBase {
   3.723 +    public:
   3.724 +      typedef NodesImplBase Parent;
   3.725 +
   3.726 +      NodesImpl(const Graph& graph, ListEdgeSet& arcset)
   3.727 +        : Parent(graph), _arcset(arcset) {}
   3.728 +
   3.729 +      virtual ~NodesImpl() {}
   3.730 +
   3.731 +    protected:
   3.732 +
   3.733 +      virtual void erase(const Node& node) {
   3.734 +        _arcset.eraseNode(node);
   3.735 +        Parent::erase(node);
   3.736 +      }
   3.737 +      virtual void erase(const std::vector<Node>& nodes) {
   3.738 +        for (int i = 0; i < int(nodes.size()); ++i) {
   3.739 +          _arcset.eraseNode(nodes[i]);
   3.740 +        }
   3.741 +        Parent::erase(nodes);
   3.742 +      }
   3.743 +      virtual void clear() {
   3.744 +        _arcset.clearNodes();
   3.745 +        Parent::clear();
   3.746 +      }
   3.747 +
   3.748 +    private:
   3.749 +      ListEdgeSet& _arcset;
   3.750 +    };
   3.751 +
   3.752 +    NodesImpl nodes;
   3.753 +
   3.754 +  public:
   3.755 +
   3.756 +    /// \brief Constructor of the EdgeSet.
   3.757 +    ///
   3.758 +    /// Constructor of the EdgeSet.
   3.759 +    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
   3.760 +      Parent::initalize(graph, nodes);
   3.761 +    }
   3.762 +
   3.763 +    /// \brief Add a new edge to the graph.
   3.764 +    ///
   3.765 +    /// Add a new edge to the graph with node \c u
   3.766 +    /// and node \c v endpoints.
   3.767 +    /// \return the new edge.
   3.768 +    Edge addEdge(const Node& u, const Node& v) {
   3.769 +      return Parent::addEdge(u, v);
   3.770 +    }
   3.771 +
   3.772 +    /// \brief Erase an edge from the graph.
   3.773 +    ///
   3.774 +    /// Erase the edge \c e from the graph.
   3.775 +    void erase(const Edge& e) {
   3.776 +      return Parent::erase(e);
   3.777 +    }
   3.778 +
   3.779 +  };
   3.780 +
   3.781 +  template <typename _Graph>
   3.782 +  class SmartArcSetBase {
   3.783 +  public:
   3.784 +
   3.785 +    typedef _Graph Graph;
   3.786 +    typedef typename Graph::Node Node;
   3.787 +    typedef typename Graph::NodeIt NodeIt;
   3.788 +
   3.789 +  protected:
   3.790 +
   3.791 +    struct NodeT {
   3.792 +      int first_out, first_in;
   3.793 +      NodeT() : first_out(-1), first_in(-1) {}
   3.794 +    };
   3.795 +
   3.796 +    typedef typename ItemSetTraits<Graph, Node>::
   3.797 +    template Map<NodeT>::Type NodesImplBase;
   3.798 +
   3.799 +    NodesImplBase* nodes;
   3.800 +
   3.801 +    struct ArcT {
   3.802 +      Node source, target;
   3.803 +      int next_out, next_in;
   3.804 +      ArcT() {}
   3.805 +    };
   3.806 +
   3.807 +    std::vector<ArcT> arcs;
   3.808 +
   3.809 +    const Graph* graph;
   3.810 +
   3.811 +    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
   3.812 +      graph = &_graph;
   3.813 +      nodes = &_nodes;
   3.814 +    }
   3.815 +
   3.816 +  public:
   3.817 +
   3.818 +    class Arc {
   3.819 +      friend class SmartArcSetBase<Graph>;
   3.820 +    protected:
   3.821 +      Arc(int _id) : id(_id) {}
   3.822 +      int id;
   3.823 +    public:
   3.824 +      Arc() {}
   3.825 +      Arc(Invalid) : id(-1) {}
   3.826 +      bool operator==(const Arc& arc) const { return id == arc.id; }
   3.827 +      bool operator!=(const Arc& arc) const { return id != arc.id; }
   3.828 +      bool operator<(const Arc& arc) const { return id < arc.id; }
   3.829 +    };
   3.830 +
   3.831 +    SmartArcSetBase() {}
   3.832 +
   3.833 +    Arc addArc(const Node& u, const Node& v) {
   3.834 +      int n = arcs.size();
   3.835 +      arcs.push_back(ArcT());
   3.836 +      arcs[n].next_in = (*nodes)[v].first_in;
   3.837 +      (*nodes)[v].first_in = n;
   3.838 +      arcs[n].next_out = (*nodes)[u].first_out;
   3.839 +      (*nodes)[u].first_out = n;
   3.840 +      arcs[n].source = u;
   3.841 +      arcs[n].target = v;
   3.842 +      return Arc(n);
   3.843 +    }
   3.844 +
   3.845 +    void clear() {
   3.846 +      Node node;
   3.847 +      for (first(node); node != INVALID; next(node)) {
   3.848 +        (*nodes)[node].first_in = -1;
   3.849 +        (*nodes)[node].first_out = -1;
   3.850 +      }
   3.851 +      arcs.clear();
   3.852 +    }
   3.853 +
   3.854 +    void first(Node& node) const {
   3.855 +      graph->first(node);
   3.856 +    }
   3.857 +
   3.858 +    void next(Node& node) const {
   3.859 +      graph->next(node);
   3.860 +    }
   3.861 +
   3.862 +    void first(Arc& arc) const {
   3.863 +      arc.id = arcs.size() - 1;
   3.864 +    }
   3.865 +
   3.866 +    void next(Arc& arc) const {
   3.867 +      --arc.id;
   3.868 +    }
   3.869 +
   3.870 +    void firstOut(Arc& arc, const Node& node) const {
   3.871 +      arc.id = (*nodes)[node].first_out;
   3.872 +    }
   3.873 +
   3.874 +    void nextOut(Arc& arc) const {
   3.875 +      arc.id = arcs[arc.id].next_out;
   3.876 +    }
   3.877 +
   3.878 +    void firstIn(Arc& arc, const Node& node) const {
   3.879 +      arc.id = (*nodes)[node].first_in;
   3.880 +    }
   3.881 +
   3.882 +    void nextIn(Arc& arc) const {
   3.883 +      arc.id = arcs[arc.id].next_in;
   3.884 +    }
   3.885 +
   3.886 +    int id(const Node& node) const { return graph->id(node); }
   3.887 +    int id(const Arc& arc) const { return arc.id; }
   3.888 +
   3.889 +    Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
   3.890 +    Arc arcFromId(int ix) const { return Arc(ix); }
   3.891 +
   3.892 +    int maxNodeId() const { return graph->maxNodeId(); };
   3.893 +    int maxArcId() const { return arcs.size() - 1; }
   3.894 +
   3.895 +    Node source(const Arc& arc) const { return arcs[arc.id].source;}
   3.896 +    Node target(const Arc& arc) const { return arcs[arc.id].target;}
   3.897 +
   3.898 +    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   3.899 +
   3.900 +    NodeNotifier& notifier(Node) const {
   3.901 +      return graph->notifier(Node());
   3.902 +    }
   3.903 +
   3.904 +    template <typename _Value>
   3.905 +    class NodeMap : public Graph::template NodeMap<_Value> {
   3.906 +    public:
   3.907 +
   3.908 +      typedef typename _Graph::template NodeMap<_Value> Parent;
   3.909 +
   3.910 +      explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
   3.911 +        : Parent(*arcset.graph) { }
   3.912 +
   3.913 +      NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
   3.914 +        : Parent(*arcset.graph, value) { }
   3.915 +
   3.916 +      NodeMap& operator=(const NodeMap& cmap) {
   3.917 +        return operator=<NodeMap>(cmap);
   3.918 +      }
   3.919 +
   3.920 +      template <typename CMap>
   3.921 +      NodeMap& operator=(const CMap& cmap) {
   3.922 +        Parent::operator=(cmap);
   3.923 +        return *this;
   3.924 +      }
   3.925 +    };
   3.926 +
   3.927 +  };
   3.928 +
   3.929 +
   3.930 +  /// \ingroup semi_adaptors
   3.931 +  ///
   3.932 +  /// \brief Digraph using a node set of another digraph or graph and
   3.933 +  /// an own arc set.
   3.934 +  ///
   3.935 +  /// This structure can be used to establish another directed graph
   3.936 +  /// over a node set of an existing one. This class uses the same
   3.937 +  /// Node type as the underlying graph, and each valid node of the
   3.938 +  /// original graph is valid in this arc set, therefore the node
   3.939 +  /// objects of the original graph can be used directly with this
   3.940 +  /// class. The node handling functions (id handling, observing, and
   3.941 +  /// iterators) works equivalently as in the original graph.
   3.942 +  ///
   3.943 +  /// \param _Graph The type of the graph which shares its node set with
   3.944 +  /// this class. Its interface must conform to the
   3.945 +  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   3.946 +  /// concept.
   3.947 +  ///
   3.948 +  /// This implementation is slightly faster than the \c ListArcSet,
   3.949 +  /// because it uses continuous storage for arcs and it uses just
   3.950 +  /// single-linked lists for enumerate outgoing and incoming
   3.951 +  /// arcs. Therefore the arcs cannot be erased from the arc sets.
   3.952 +  ///
   3.953 +  /// \warning If a node is erased from the underlying graph and this
   3.954 +  /// node is the source or target of one arc in the arc set, then
   3.955 +  /// the arc set is invalidated, and it cannot be used anymore. The
   3.956 +  /// validity can be checked with the \c valid() member function.
   3.957 +  ///
   3.958 +  /// This class is fully conform to the \ref concepts::Digraph
   3.959 +  /// "Digraph" concept.
   3.960 +  template <typename _Graph>
   3.961 +  class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
   3.962 +
   3.963 +  public:
   3.964 +
   3.965 +    typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
   3.966 +
   3.967 +    typedef typename Parent::Node Node;
   3.968 +    typedef typename Parent::Arc Arc;
   3.969 +
   3.970 +    typedef _Graph Graph;
   3.971 +
   3.972 +  protected:
   3.973 +
   3.974 +    typedef typename Parent::NodesImplBase NodesImplBase;
   3.975 +
   3.976 +    void eraseNode(const Node& node) {
   3.977 +      if (typename Parent::InArcIt(*this, node) == INVALID &&
   3.978 +          typename Parent::OutArcIt(*this, node) == INVALID) {
   3.979 +        return;
   3.980 +      }
   3.981 +      throw typename NodesImplBase::Notifier::ImmediateDetach();
   3.982 +    }
   3.983 +
   3.984 +    void clearNodes() {
   3.985 +      Parent::clear();
   3.986 +    }
   3.987 +
   3.988 +    class NodesImpl : public NodesImplBase {
   3.989 +    public:
   3.990 +      typedef NodesImplBase Parent;
   3.991 +
   3.992 +      NodesImpl(const Graph& graph, SmartArcSet& arcset)
   3.993 +        : Parent(graph), _arcset(arcset) {}
   3.994 +
   3.995 +      virtual ~NodesImpl() {}
   3.996 +
   3.997 +      bool attached() const {
   3.998 +        return Parent::attached();
   3.999 +      }
  3.1000 +
  3.1001 +    protected:
  3.1002 +
  3.1003 +      virtual void erase(const Node& node) {
  3.1004 +        try {
  3.1005 +          _arcset.eraseNode(node);
  3.1006 +          Parent::erase(node);
  3.1007 +        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  3.1008 +          Parent::clear();
  3.1009 +          throw;
  3.1010 +        }
  3.1011 +      }
  3.1012 +      virtual void erase(const std::vector<Node>& nodes) {
  3.1013 +        try {
  3.1014 +          for (int i = 0; i < int(nodes.size()); ++i) {
  3.1015 +            _arcset.eraseNode(nodes[i]);
  3.1016 +          }
  3.1017 +          Parent::erase(nodes);
  3.1018 +        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  3.1019 +          Parent::clear();
  3.1020 +          throw;
  3.1021 +        }
  3.1022 +      }
  3.1023 +      virtual void clear() {
  3.1024 +        _arcset.clearNodes();
  3.1025 +        Parent::clear();
  3.1026 +      }
  3.1027 +
  3.1028 +    private:
  3.1029 +      SmartArcSet& _arcset;
  3.1030 +    };
  3.1031 +
  3.1032 +    NodesImpl nodes;
  3.1033 +
  3.1034 +  public:
  3.1035 +
  3.1036 +    /// \brief Constructor of the ArcSet.
  3.1037 +    ///
  3.1038 +    /// Constructor of the ArcSet.
  3.1039 +    SmartArcSet(const Graph& graph) : nodes(graph, *this) {
  3.1040 +      Parent::initalize(graph, nodes);
  3.1041 +    }
  3.1042 +
  3.1043 +    /// \brief Add a new arc to the digraph.
  3.1044 +    ///
  3.1045 +    /// Add a new arc to the digraph with source node \c s
  3.1046 +    /// and target node \c t.
  3.1047 +    /// \return the new arc.
  3.1048 +    Arc addArc(const Node& s, const Node& t) {
  3.1049 +      return Parent::addArc(s, t);
  3.1050 +    }
  3.1051 +
  3.1052 +    /// \brief Validity check
  3.1053 +    ///
  3.1054 +    /// This functions gives back false if the ArcSet is
  3.1055 +    /// invalidated. It occurs when a node in the underlying graph is
  3.1056 +    /// erased and it is not isolated in the ArcSet.
  3.1057 +    bool valid() const {
  3.1058 +      return nodes.attached();
  3.1059 +    }
  3.1060 +
  3.1061 +  };
  3.1062 +
  3.1063 +
  3.1064 +  template <typename _Graph>
  3.1065 +  class SmartEdgeSetBase {
  3.1066 +  public:
  3.1067 +
  3.1068 +    typedef _Graph Graph;
  3.1069 +    typedef typename Graph::Node Node;
  3.1070 +    typedef typename Graph::NodeIt NodeIt;
  3.1071 +
  3.1072 +  protected:
  3.1073 +
  3.1074 +    struct NodeT {
  3.1075 +      int first_out;
  3.1076 +      NodeT() : first_out(-1) {}
  3.1077 +    };
  3.1078 +
  3.1079 +    typedef typename ItemSetTraits<Graph, Node>::
  3.1080 +    template Map<NodeT>::Type NodesImplBase;
  3.1081 +
  3.1082 +    NodesImplBase* nodes;
  3.1083 +
  3.1084 +    struct ArcT {
  3.1085 +      Node target;
  3.1086 +      int next_out;
  3.1087 +      ArcT() {}
  3.1088 +    };
  3.1089 +
  3.1090 +    std::vector<ArcT> arcs;
  3.1091 +
  3.1092 +    const Graph* graph;
  3.1093 +
  3.1094 +    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
  3.1095 +      graph = &_graph;
  3.1096 +      nodes = &_nodes;
  3.1097 +    }
  3.1098 +
  3.1099 +  public:
  3.1100 +
  3.1101 +    class Edge {
  3.1102 +      friend class SmartEdgeSetBase;
  3.1103 +    protected:
  3.1104 +
  3.1105 +      int id;
  3.1106 +      explicit Edge(int _id) { id = _id;}
  3.1107 +
  3.1108 +    public:
  3.1109 +      Edge() {}
  3.1110 +      Edge (Invalid) { id = -1; }
  3.1111 +      bool operator==(const Edge& arc) const {return id == arc.id;}
  3.1112 +      bool operator!=(const Edge& arc) const {return id != arc.id;}
  3.1113 +      bool operator<(const Edge& arc) const {return id < arc.id;}
  3.1114 +    };
  3.1115 +
  3.1116 +    class Arc {
  3.1117 +      friend class SmartEdgeSetBase;
  3.1118 +    protected:
  3.1119 +      Arc(int _id) : id(_id) {}
  3.1120 +      int id;
  3.1121 +    public:
  3.1122 +      operator Edge() const { return edgeFromId(id / 2); }
  3.1123 +
  3.1124 +      Arc() {}
  3.1125 +      Arc(Invalid) : id(-1) {}
  3.1126 +      bool operator==(const Arc& arc) const { return id == arc.id; }
  3.1127 +      bool operator!=(const Arc& arc) const { return id != arc.id; }
  3.1128 +      bool operator<(const Arc& arc) const { return id < arc.id; }
  3.1129 +    };
  3.1130 +
  3.1131 +    SmartEdgeSetBase() {}
  3.1132 +
  3.1133 +    Edge addEdge(const Node& u, const Node& v) {
  3.1134 +      int n = arcs.size();
  3.1135 +      arcs.push_back(ArcT());
  3.1136 +      arcs.push_back(ArcT());
  3.1137 +
  3.1138 +      arcs[n].target = u;
  3.1139 +      arcs[n | 1].target = v;
  3.1140 +
  3.1141 +      arcs[n].next_out = (*nodes)[v].first_out;
  3.1142 +      (*nodes)[v].first_out = n;
  3.1143 +
  3.1144 +      arcs[n | 1].next_out = (*nodes)[u].first_out;
  3.1145 +      (*nodes)[u].first_out = (n | 1);
  3.1146 +
  3.1147 +      return Edge(n / 2);
  3.1148 +    }
  3.1149 +
  3.1150 +    void clear() {
  3.1151 +      Node node;
  3.1152 +      for (first(node); node != INVALID; next(node)) {
  3.1153 +        (*nodes)[node].first_out = -1;
  3.1154 +      }
  3.1155 +      arcs.clear();
  3.1156 +    }
  3.1157 +
  3.1158 +    void first(Node& node) const {
  3.1159 +      graph->first(node);
  3.1160 +    }
  3.1161 +
  3.1162 +    void next(Node& node) const {
  3.1163 +      graph->next(node);
  3.1164 +    }
  3.1165 +
  3.1166 +    void first(Arc& arc) const {
  3.1167 +      arc.id = arcs.size() - 1;
  3.1168 +    }
  3.1169 +
  3.1170 +    void next(Arc& arc) const {
  3.1171 +      --arc.id;
  3.1172 +    }
  3.1173 +
  3.1174 +    void first(Edge& arc) const {
  3.1175 +      arc.id = arcs.size() / 2 - 1;
  3.1176 +    }
  3.1177 +
  3.1178 +    void next(Edge& arc) const {
  3.1179 +      --arc.id;
  3.1180 +    }
  3.1181 +
  3.1182 +    void firstOut(Arc& arc, const Node& node) const {
  3.1183 +      arc.id = (*nodes)[node].first_out;
  3.1184 +    }
  3.1185 +
  3.1186 +    void nextOut(Arc& arc) const {
  3.1187 +      arc.id = arcs[arc.id].next_out;
  3.1188 +    }
  3.1189 +
  3.1190 +    void firstIn(Arc& arc, const Node& node) const {
  3.1191 +      arc.id = (((*nodes)[node].first_out) ^ 1);
  3.1192 +      if (arc.id == -2) arc.id = -1;
  3.1193 +    }
  3.1194 +
  3.1195 +    void nextIn(Arc& arc) const {
  3.1196 +      arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
  3.1197 +      if (arc.id == -2) arc.id = -1;
  3.1198 +    }
  3.1199 +
  3.1200 +    void firstInc(Edge &arc, bool& dir, const Node& node) const {
  3.1201 +      int de = (*nodes)[node].first_out;
  3.1202 +      if (de != -1 ) {
  3.1203 +        arc.id = de / 2;
  3.1204 +        dir = ((de & 1) == 1);
  3.1205 +      } else {
  3.1206 +        arc.id = -1;
  3.1207 +        dir = true;
  3.1208 +      }
  3.1209 +    }
  3.1210 +    void nextInc(Edge &arc, bool& dir) const {
  3.1211 +      int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
  3.1212 +      if (de != -1 ) {
  3.1213 +        arc.id = de / 2;
  3.1214 +        dir = ((de & 1) == 1);
  3.1215 +      } else {
  3.1216 +        arc.id = -1;
  3.1217 +        dir = true;
  3.1218 +      }
  3.1219 +    }
  3.1220 +
  3.1221 +    static bool direction(Arc arc) {
  3.1222 +      return (arc.id & 1) == 1;
  3.1223 +    }
  3.1224 +
  3.1225 +    static Arc direct(Edge edge, bool dir) {
  3.1226 +      return Arc(edge.id * 2 + (dir ? 1 : 0));
  3.1227 +    }
  3.1228 +
  3.1229 +    int id(Node node) const { return graph->id(node); }
  3.1230 +    static int id(Arc arc) { return arc.id; }
  3.1231 +    static int id(Edge arc) { return arc.id; }
  3.1232 +
  3.1233 +    Node nodeFromId(int id) const { return graph->nodeFromId(id); }
  3.1234 +    static Arc arcFromId(int id) { return Arc(id); }
  3.1235 +    static Edge edgeFromId(int id) { return Edge(id);}
  3.1236 +
  3.1237 +    int maxNodeId() const { return graph->maxNodeId(); };
  3.1238 +    int maxArcId() const { return arcs.size() - 1; }
  3.1239 +    int maxEdgeId() const { return arcs.size() / 2 - 1; }
  3.1240 +
  3.1241 +    Node source(Arc e) const { return arcs[e.id ^ 1].target; }
  3.1242 +    Node target(Arc e) const { return arcs[e.id].target; }
  3.1243 +
  3.1244 +    Node u(Edge e) const { return arcs[2 * e.id].target; }
  3.1245 +    Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
  3.1246 +
  3.1247 +    typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
  3.1248 +
  3.1249 +    NodeNotifier& notifier(Node) const {
  3.1250 +      return graph->notifier(Node());
  3.1251 +    }
  3.1252 +
  3.1253 +    template <typename _Value>
  3.1254 +    class NodeMap : public Graph::template NodeMap<_Value> {
  3.1255 +    public:
  3.1256 +
  3.1257 +      typedef typename _Graph::template NodeMap<_Value> Parent;
  3.1258 +
  3.1259 +      explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
  3.1260 +        : Parent(*arcset.graph) { }
  3.1261 +
  3.1262 +      NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
  3.1263 +        : Parent(*arcset.graph, value) { }
  3.1264 +
  3.1265 +      NodeMap& operator=(const NodeMap& cmap) {
  3.1266 +        return operator=<NodeMap>(cmap);
  3.1267 +      }
  3.1268 +
  3.1269 +      template <typename CMap>
  3.1270 +      NodeMap& operator=(const CMap& cmap) {
  3.1271 +        Parent::operator=(cmap);
  3.1272 +        return *this;
  3.1273 +      }
  3.1274 +    };
  3.1275 +
  3.1276 +  };
  3.1277 +
  3.1278 +  /// \ingroup semi_adaptors
  3.1279 +  ///
  3.1280 +  /// \brief Graph using a node set of another digraph or graph and an
  3.1281 +  /// own edge set.
  3.1282 +  ///
  3.1283 +  /// This structure can be used to establish another graph over a
  3.1284 +  /// node set of an existing one. This class uses the same Node type
  3.1285 +  /// as the underlying graph, and each valid node of the original
  3.1286 +  /// graph is valid in this arc set, therefore the node objects of
  3.1287 +  /// the original graph can be used directly with this class. The
  3.1288 +  /// node handling functions (id handling, observing, and iterators)
  3.1289 +  /// works equivalently as in the original graph.
  3.1290 +  ///
  3.1291 +  /// \param _Graph The type of the graph which shares its node set
  3.1292 +  /// with this class. Its interface must conform to the
  3.1293 +  /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
  3.1294 +  ///  concept.
  3.1295 +  ///
  3.1296 +  /// This implementation is slightly faster than the \c ListEdgeSet,
  3.1297 +  /// because it uses continuous storage for edges and it uses just
  3.1298 +  /// single-linked lists for enumerate incident edges. Therefore the
  3.1299 +  /// edges cannot be erased from the edge sets.
  3.1300 +  ///
  3.1301 +  /// \warning If a node is erased from the underlying graph and this
  3.1302 +  /// node is incident to one edge in the edge set, then the edge set
  3.1303 +  /// is invalidated, and it cannot be used anymore. The validity can
  3.1304 +  /// be checked with the \c valid() member function.
  3.1305 +  ///
  3.1306 +  /// This class is fully conform to the \ref concepts::Graph
  3.1307 +  /// "Graph" concept.
  3.1308 +  template <typename _Graph>
  3.1309 +  class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
  3.1310 +
  3.1311 +  public:
  3.1312 +
  3.1313 +    typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
  3.1314 +
  3.1315 +    typedef typename Parent::Node Node;
  3.1316 +    typedef typename Parent::Arc Arc;
  3.1317 +    typedef typename Parent::Edge Edge;
  3.1318 +
  3.1319 +    typedef _Graph Graph;
  3.1320 +
  3.1321 +  protected:
  3.1322 +
  3.1323 +    typedef typename Parent::NodesImplBase NodesImplBase;
  3.1324 +
  3.1325 +    void eraseNode(const Node& node) {
  3.1326 +      if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
  3.1327 +        return;
  3.1328 +      }
  3.1329 +      throw typename NodesImplBase::Notifier::ImmediateDetach();
  3.1330 +    }
  3.1331 +
  3.1332 +    void clearNodes() {
  3.1333 +      Parent::clear();
  3.1334 +    }
  3.1335 +
  3.1336 +    class NodesImpl : public NodesImplBase {
  3.1337 +    public:
  3.1338 +      typedef NodesImplBase Parent;
  3.1339 +
  3.1340 +      NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
  3.1341 +        : Parent(graph), _arcset(arcset) {}
  3.1342 +
  3.1343 +      virtual ~NodesImpl() {}
  3.1344 +
  3.1345 +      bool attached() const {
  3.1346 +        return Parent::attached();
  3.1347 +      }
  3.1348 +
  3.1349 +    protected:
  3.1350 +
  3.1351 +      virtual void erase(const Node& node) {
  3.1352 +        try {
  3.1353 +          _arcset.eraseNode(node);
  3.1354 +          Parent::erase(node);
  3.1355 +        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  3.1356 +          Parent::clear();
  3.1357 +          throw;
  3.1358 +        }
  3.1359 +      }
  3.1360 +      virtual void erase(const std::vector<Node>& nodes) {
  3.1361 +        try {
  3.1362 +          for (int i = 0; i < int(nodes.size()); ++i) {
  3.1363 +            _arcset.eraseNode(nodes[i]);
  3.1364 +          }
  3.1365 +          Parent::erase(nodes);
  3.1366 +        } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  3.1367 +          Parent::clear();
  3.1368 +          throw;
  3.1369 +        }
  3.1370 +      }
  3.1371 +      virtual void clear() {
  3.1372 +        _arcset.clearNodes();
  3.1373 +        Parent::clear();
  3.1374 +      }
  3.1375 +
  3.1376 +    private:
  3.1377 +      SmartEdgeSet& _arcset;
  3.1378 +    };
  3.1379 +
  3.1380 +    NodesImpl nodes;
  3.1381 +
  3.1382 +  public:
  3.1383 +
  3.1384 +    /// \brief Constructor of the EdgeSet.
  3.1385 +    ///
  3.1386 +    /// Constructor of the EdgeSet.
  3.1387 +    SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
  3.1388 +      Parent::initalize(graph, nodes);
  3.1389 +    }
  3.1390 +
  3.1391 +    /// \brief Add a new edge to the graph.
  3.1392 +    ///
  3.1393 +    /// Add a new edge to the graph with node \c u
  3.1394 +    /// and node \c v endpoints.
  3.1395 +    /// \return the new edge.
  3.1396 +    Edge addEdge(const Node& u, const Node& v) {
  3.1397 +      return Parent::addEdge(u, v);
  3.1398 +    }
  3.1399 +
  3.1400 +    /// \brief Validity check
  3.1401 +    ///
  3.1402 +    /// This functions gives back false if the EdgeSet is
  3.1403 +    /// invalidated. It occurs when a node in the underlying graph is
  3.1404 +    /// erased and it is not isolated in the EdgeSet.
  3.1405 +    bool valid() const {
  3.1406 +      return nodes.attached();
  3.1407 +    }
  3.1408 +
  3.1409 +  };
  3.1410 +
  3.1411 +}
  3.1412 +
  3.1413 +#endif
     4.1 --- a/test/CMakeLists.txt	Mon Jan 12 13:18:03 2009 +0000
     4.2 +++ b/test/CMakeLists.txt	Mon Jan 12 13:37:37 2009 +0000
     4.3 @@ -12,6 +12,7 @@
     4.4    dijkstra_test
     4.5    dim_test
     4.6    error_test
     4.7 +  edge_set_test
     4.8    graph_copy_test
     4.9    graph_test
    4.10    graph_utils_test
     5.1 --- a/test/Makefile.am	Mon Jan 12 13:18:03 2009 +0000
     5.2 +++ b/test/Makefile.am	Mon Jan 12 13:37:37 2009 +0000
     5.3 @@ -14,6 +14,7 @@
     5.4  	test/digraph_test \
     5.5  	test/dijkstra_test \
     5.6  	test/dim_test \
     5.7 +	test/edge_set_test \
     5.8  	test/error_test \
     5.9  	test/graph_copy_test \
    5.10  	test/graph_test \
    5.11 @@ -51,6 +52,7 @@
    5.12  test_digraph_test_SOURCES = test/digraph_test.cc
    5.13  test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    5.14  test_dim_test_SOURCES = test/dim_test.cc
    5.15 +test_edge_set_test_SOURCES = test/edge_set_test.cc
    5.16  test_error_test_SOURCES = test/error_test.cc
    5.17  test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    5.18  test_graph_test_SOURCES = test/graph_test.cc
     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/test/edge_set_test.cc	Mon Jan 12 13:37:37 2009 +0000
     6.3 @@ -0,0 +1,380 @@
     6.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     6.5 + *
     6.6 + * This file is a part of LEMON, a generic C++ optimization library.
     6.7 + *
     6.8 + * Copyright (C) 2003-2008
     6.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    6.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    6.11 + *
    6.12 + * Permission to use, modify and distribute this software is granted
    6.13 + * provided that this copyright notice appears in all copies. For
    6.14 + * precise terms see the accompanying LICENSE file.
    6.15 + *
    6.16 + * This software is provided "AS IS" with no warranty of any kind,
    6.17 + * express or implied, and with no claim as to its suitability for any
    6.18 + * purpose.
    6.19 + *
    6.20 + */
    6.21 +
    6.22 +#include <iostream>
    6.23 +#include <vector>
    6.24 +
    6.25 +#include <lemon/concepts/digraph.h>
    6.26 +#include <lemon/concepts/graph.h>
    6.27 +#include <lemon/concept_check.h>
    6.28 +
    6.29 +#include <lemon/list_graph.h>
    6.30 +
    6.31 +#include <lemon/edge_set.h>
    6.32 +
    6.33 +#include "graph_test.h"
    6.34 +#include "test_tools.h"
    6.35 +
    6.36 +using namespace lemon;
    6.37 +
    6.38 +void checkSmartArcSet() {
    6.39 +  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
    6.40 +
    6.41 +  typedef ListDigraph Digraph;
    6.42 +  typedef SmartArcSet<Digraph> ArcSet;
    6.43 +
    6.44 +  Digraph digraph;
    6.45 +  Digraph::Node
    6.46 +    n1 = digraph.addNode(),
    6.47 +    n2 = digraph.addNode();
    6.48 +
    6.49 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
    6.50 +
    6.51 +  ArcSet arc_set(digraph);
    6.52 +
    6.53 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
    6.54 +
    6.55 +  checkGraphNodeList(arc_set, 2);
    6.56 +  checkGraphArcList(arc_set, 0);
    6.57 +
    6.58 +  Digraph::Node
    6.59 +    n3 = digraph.addNode();
    6.60 +  checkGraphNodeList(arc_set, 3);
    6.61 +  checkGraphArcList(arc_set, 0);
    6.62 +
    6.63 +  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
    6.64 +  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
    6.65 +  checkGraphNodeList(arc_set, 3);
    6.66 +  checkGraphArcList(arc_set, 1);
    6.67 +
    6.68 +  checkGraphOutArcList(arc_set, n1, 1);
    6.69 +  checkGraphOutArcList(arc_set, n2, 0);
    6.70 +  checkGraphOutArcList(arc_set, n3, 0);
    6.71 +
    6.72 +  checkGraphInArcList(arc_set, n1, 0);
    6.73 +  checkGraphInArcList(arc_set, n2, 1);
    6.74 +  checkGraphInArcList(arc_set, n3, 0);
    6.75 +
    6.76 +  checkGraphConArcList(arc_set, 1);
    6.77 +
    6.78 +  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
    6.79 +    a3 = arc_set.addArc(n2, n3),
    6.80 +    a4 = arc_set.addArc(n2, n3);
    6.81 +  checkGraphNodeList(arc_set, 3);
    6.82 +  checkGraphArcList(arc_set, 4);
    6.83 +
    6.84 +  checkGraphOutArcList(arc_set, n1, 1);
    6.85 +  checkGraphOutArcList(arc_set, n2, 3);
    6.86 +  checkGraphOutArcList(arc_set, n3, 0);
    6.87 +
    6.88 +  checkGraphInArcList(arc_set, n1, 1);
    6.89 +  checkGraphInArcList(arc_set, n2, 1);
    6.90 +  checkGraphInArcList(arc_set, n3, 2);
    6.91 +
    6.92 +  checkGraphConArcList(arc_set, 4);
    6.93 +
    6.94 +  checkNodeIds(arc_set);
    6.95 +  checkArcIds(arc_set);
    6.96 +  checkGraphNodeMap(arc_set);
    6.97 +  checkGraphArcMap(arc_set);
    6.98 +
    6.99 +  check(arc_set.valid(), "Wrong validity");
   6.100 +  digraph.erase(n1);
   6.101 +  check(!arc_set.valid(), "Wrong validity");
   6.102 +}
   6.103 +
   6.104 +void checkListArcSet() {
   6.105 +  checkConcept<concepts::Digraph, SmartArcSet<concepts::Digraph> >();
   6.106 +
   6.107 +  typedef ListDigraph Digraph;
   6.108 +  typedef ListArcSet<Digraph> ArcSet;
   6.109 +
   6.110 +  Digraph digraph;
   6.111 +  Digraph::Node
   6.112 +    n1 = digraph.addNode(),
   6.113 +    n2 = digraph.addNode();
   6.114 +
   6.115 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   6.116 +
   6.117 +  ArcSet arc_set(digraph);
   6.118 +
   6.119 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   6.120 +
   6.121 +  checkGraphNodeList(arc_set, 2);
   6.122 +  checkGraphArcList(arc_set, 0);
   6.123 +
   6.124 +  Digraph::Node
   6.125 +    n3 = digraph.addNode();
   6.126 +  checkGraphNodeList(arc_set, 3);
   6.127 +  checkGraphArcList(arc_set, 0);
   6.128 +
   6.129 +  ArcSet::Arc a1 = arc_set.addArc(n1, n2);
   6.130 +  check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");
   6.131 +  checkGraphNodeList(arc_set, 3);
   6.132 +  checkGraphArcList(arc_set, 1);
   6.133 +
   6.134 +  checkGraphOutArcList(arc_set, n1, 1);
   6.135 +  checkGraphOutArcList(arc_set, n2, 0);
   6.136 +  checkGraphOutArcList(arc_set, n3, 0);
   6.137 +
   6.138 +  checkGraphInArcList(arc_set, n1, 0);
   6.139 +  checkGraphInArcList(arc_set, n2, 1);
   6.140 +  checkGraphInArcList(arc_set, n3, 0);
   6.141 +
   6.142 +  checkGraphConArcList(arc_set, 1);
   6.143 +
   6.144 +  ArcSet::Arc a2 = arc_set.addArc(n2, n1),
   6.145 +    a3 = arc_set.addArc(n2, n3),
   6.146 +    a4 = arc_set.addArc(n2, n3);
   6.147 +  checkGraphNodeList(arc_set, 3);
   6.148 +  checkGraphArcList(arc_set, 4);
   6.149 +
   6.150 +  checkGraphOutArcList(arc_set, n1, 1);
   6.151 +  checkGraphOutArcList(arc_set, n2, 3);
   6.152 +  checkGraphOutArcList(arc_set, n3, 0);
   6.153 +
   6.154 +  checkGraphInArcList(arc_set, n1, 1);
   6.155 +  checkGraphInArcList(arc_set, n2, 1);
   6.156 +  checkGraphInArcList(arc_set, n3, 2);
   6.157 +
   6.158 +  checkGraphConArcList(arc_set, 4);
   6.159 +
   6.160 +  checkNodeIds(arc_set);
   6.161 +  checkArcIds(arc_set);
   6.162 +  checkGraphNodeMap(arc_set);
   6.163 +  checkGraphArcMap(arc_set);
   6.164 +
   6.165 +  digraph.erase(n1);
   6.166 +
   6.167 +  checkGraphNodeList(arc_set, 2);
   6.168 +  checkGraphArcList(arc_set, 2);
   6.169 +
   6.170 +  checkGraphOutArcList(arc_set, n2, 2);
   6.171 +  checkGraphOutArcList(arc_set, n3, 0);
   6.172 +
   6.173 +  checkGraphInArcList(arc_set, n2, 0);
   6.174 +  checkGraphInArcList(arc_set, n3, 2);
   6.175 +
   6.176 +  checkNodeIds(arc_set);
   6.177 +  checkArcIds(arc_set);
   6.178 +  checkGraphNodeMap(arc_set);
   6.179 +  checkGraphArcMap(arc_set);
   6.180 +
   6.181 +  checkGraphConArcList(arc_set, 2);
   6.182 +}
   6.183 +
   6.184 +void checkSmartEdgeSet() {
   6.185 +  checkConcept<concepts::Digraph, SmartEdgeSet<concepts::Digraph> >();
   6.186 +
   6.187 +  typedef ListDigraph Digraph;
   6.188 +  typedef SmartEdgeSet<Digraph> EdgeSet;
   6.189 +
   6.190 +  Digraph digraph;
   6.191 +  Digraph::Node
   6.192 +    n1 = digraph.addNode(),
   6.193 +    n2 = digraph.addNode();
   6.194 +
   6.195 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   6.196 +
   6.197 +  EdgeSet edge_set(digraph);
   6.198 +
   6.199 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   6.200 +
   6.201 +  checkGraphNodeList(edge_set, 2);
   6.202 +  checkGraphArcList(edge_set, 0);
   6.203 +  checkGraphEdgeList(edge_set, 0);
   6.204 +
   6.205 +  Digraph::Node
   6.206 +    n3 = digraph.addNode();
   6.207 +  checkGraphNodeList(edge_set, 3);
   6.208 +  checkGraphArcList(edge_set, 0);
   6.209 +  checkGraphEdgeList(edge_set, 0);
   6.210 +
   6.211 +  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   6.212 +  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   6.213 +        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   6.214 +  checkGraphNodeList(edge_set, 3);
   6.215 +  checkGraphArcList(edge_set, 2);
   6.216 +  checkGraphEdgeList(edge_set, 1);
   6.217 +
   6.218 +  checkGraphOutArcList(edge_set, n1, 1);
   6.219 +  checkGraphOutArcList(edge_set, n2, 1);
   6.220 +  checkGraphOutArcList(edge_set, n3, 0);
   6.221 +
   6.222 +  checkGraphInArcList(edge_set, n1, 1);
   6.223 +  checkGraphInArcList(edge_set, n2, 1);
   6.224 +  checkGraphInArcList(edge_set, n3, 0);
   6.225 +
   6.226 +  checkGraphIncEdgeList(edge_set, n1, 1);
   6.227 +  checkGraphIncEdgeList(edge_set, n2, 1);
   6.228 +  checkGraphIncEdgeList(edge_set, n3, 0);
   6.229 +
   6.230 +  checkGraphConEdgeList(edge_set, 1);
   6.231 +  checkGraphConArcList(edge_set, 2);
   6.232 +
   6.233 +  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   6.234 +    e3 = edge_set.addEdge(n2, n3),
   6.235 +    e4 = edge_set.addEdge(n2, n3);
   6.236 +  checkGraphNodeList(edge_set, 3);
   6.237 +  checkGraphEdgeList(edge_set, 4);
   6.238 +
   6.239 +  checkGraphOutArcList(edge_set, n1, 2);
   6.240 +  checkGraphOutArcList(edge_set, n2, 4);
   6.241 +  checkGraphOutArcList(edge_set, n3, 2);
   6.242 +
   6.243 +  checkGraphInArcList(edge_set, n1, 2);
   6.244 +  checkGraphInArcList(edge_set, n2, 4);
   6.245 +  checkGraphInArcList(edge_set, n3, 2);
   6.246 +
   6.247 +  checkGraphIncEdgeList(edge_set, n1, 2);
   6.248 +  checkGraphIncEdgeList(edge_set, n2, 4);
   6.249 +  checkGraphIncEdgeList(edge_set, n3, 2);
   6.250 +
   6.251 +  checkGraphConEdgeList(edge_set, 4);
   6.252 +  checkGraphConArcList(edge_set, 8);
   6.253 +
   6.254 +  checkArcDirections(edge_set);
   6.255 +
   6.256 +  checkNodeIds(edge_set);
   6.257 +  checkArcIds(edge_set);
   6.258 +  checkEdgeIds(edge_set);
   6.259 +  checkGraphNodeMap(edge_set);
   6.260 +  checkGraphArcMap(edge_set);
   6.261 +  checkGraphEdgeMap(edge_set);
   6.262 +
   6.263 +  check(edge_set.valid(), "Wrong validity");
   6.264 +  digraph.erase(n1);
   6.265 +  check(!edge_set.valid(), "Wrong validity");
   6.266 +}
   6.267 +
   6.268 +void checkListEdgeSet() {
   6.269 +  checkConcept<concepts::Digraph, ListEdgeSet<concepts::Digraph> >();
   6.270 +
   6.271 +  typedef ListDigraph Digraph;
   6.272 +  typedef ListEdgeSet<Digraph> EdgeSet;
   6.273 +
   6.274 +  Digraph digraph;
   6.275 +  Digraph::Node
   6.276 +    n1 = digraph.addNode(),
   6.277 +    n2 = digraph.addNode();
   6.278 +
   6.279 +  Digraph::Arc ga1 = digraph.addArc(n1, n2);
   6.280 +
   6.281 +  EdgeSet edge_set(digraph);
   6.282 +
   6.283 +  Digraph::Arc ga2 = digraph.addArc(n2, n1);
   6.284 +
   6.285 +  checkGraphNodeList(edge_set, 2);
   6.286 +  checkGraphArcList(edge_set, 0);
   6.287 +  checkGraphEdgeList(edge_set, 0);
   6.288 +
   6.289 +  Digraph::Node
   6.290 +    n3 = digraph.addNode();
   6.291 +  checkGraphNodeList(edge_set, 3);
   6.292 +  checkGraphArcList(edge_set, 0);
   6.293 +  checkGraphEdgeList(edge_set, 0);
   6.294 +
   6.295 +  EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);
   6.296 +  check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||
   6.297 +        (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");
   6.298 +  checkGraphNodeList(edge_set, 3);
   6.299 +  checkGraphArcList(edge_set, 2);
   6.300 +  checkGraphEdgeList(edge_set, 1);
   6.301 +
   6.302 +  checkGraphOutArcList(edge_set, n1, 1);
   6.303 +  checkGraphOutArcList(edge_set, n2, 1);
   6.304 +  checkGraphOutArcList(edge_set, n3, 0);
   6.305 +
   6.306 +  checkGraphInArcList(edge_set, n1, 1);
   6.307 +  checkGraphInArcList(edge_set, n2, 1);
   6.308 +  checkGraphInArcList(edge_set, n3, 0);
   6.309 +
   6.310 +  checkGraphIncEdgeList(edge_set, n1, 1);
   6.311 +  checkGraphIncEdgeList(edge_set, n2, 1);
   6.312 +  checkGraphIncEdgeList(edge_set, n3, 0);
   6.313 +
   6.314 +  checkGraphConEdgeList(edge_set, 1);
   6.315 +  checkGraphConArcList(edge_set, 2);
   6.316 +
   6.317 +  EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),
   6.318 +    e3 = edge_set.addEdge(n2, n3),
   6.319 +    e4 = edge_set.addEdge(n2, n3);
   6.320 +  checkGraphNodeList(edge_set, 3);
   6.321 +  checkGraphEdgeList(edge_set, 4);
   6.322 +
   6.323 +  checkGraphOutArcList(edge_set, n1, 2);
   6.324 +  checkGraphOutArcList(edge_set, n2, 4);
   6.325 +  checkGraphOutArcList(edge_set, n3, 2);
   6.326 +
   6.327 +  checkGraphInArcList(edge_set, n1, 2);
   6.328 +  checkGraphInArcList(edge_set, n2, 4);
   6.329 +  checkGraphInArcList(edge_set, n3, 2);
   6.330 +
   6.331 +  checkGraphIncEdgeList(edge_set, n1, 2);
   6.332 +  checkGraphIncEdgeList(edge_set, n2, 4);
   6.333 +  checkGraphIncEdgeList(edge_set, n3, 2);
   6.334 +
   6.335 +  checkGraphConEdgeList(edge_set, 4);
   6.336 +  checkGraphConArcList(edge_set, 8);
   6.337 +
   6.338 +  checkArcDirections(edge_set);
   6.339 +
   6.340 +  checkNodeIds(edge_set);
   6.341 +  checkArcIds(edge_set);
   6.342 +  checkEdgeIds(edge_set);
   6.343 +  checkGraphNodeMap(edge_set);
   6.344 +  checkGraphArcMap(edge_set);
   6.345 +  checkGraphEdgeMap(edge_set);
   6.346 +
   6.347 +  digraph.erase(n1);
   6.348 +
   6.349 +  checkGraphNodeList(edge_set, 2);
   6.350 +  checkGraphArcList(edge_set, 4);
   6.351 +  checkGraphEdgeList(edge_set, 2);
   6.352 +
   6.353 +  checkGraphOutArcList(edge_set, n2, 2);
   6.354 +  checkGraphOutArcList(edge_set, n3, 2);
   6.355 +
   6.356 +  checkGraphInArcList(edge_set, n2, 2);
   6.357 +  checkGraphInArcList(edge_set, n3, 2);
   6.358 +
   6.359 +  checkGraphIncEdgeList(edge_set, n2, 2);
   6.360 +  checkGraphIncEdgeList(edge_set, n3, 2);
   6.361 +
   6.362 +  checkNodeIds(edge_set);
   6.363 +  checkArcIds(edge_set);
   6.364 +  checkEdgeIds(edge_set);
   6.365 +  checkGraphNodeMap(edge_set);
   6.366 +  checkGraphArcMap(edge_set);
   6.367 +  checkGraphEdgeMap(edge_set);
   6.368 +
   6.369 +  checkGraphConEdgeList(edge_set, 2);
   6.370 +  checkGraphConArcList(edge_set, 4);
   6.371 +
   6.372 +}
   6.373 +
   6.374 +
   6.375 +int main() {
   6.376 +
   6.377 +  checkSmartArcSet();
   6.378 +  checkListArcSet();
   6.379 +  checkSmartEdgeSet();
   6.380 +  checkListEdgeSet();
   6.381 +
   6.382 +  return 0;
   6.383 +}