lemon/edge_set.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 12 May 2009 12:08:06 +0200
changeset 664 cc61d09f053b
parent 617 4137ef9aacc6
child 670 926c47568a56
permissions -rw-r--r--
Extend min cost flow test file + check dual costs (#291)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_EDGE_SET_H
    20 #define LEMON_EDGE_SET_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/bits/edge_set_extender.h>
    24 
    25 /// \ingroup graphs
    26 /// \file
    27 /// \brief ArcSet and EdgeSet classes.
    28 ///
    29 /// Graphs which use another graph's node-set as own.
    30 namespace lemon {
    31 
    32   template <typename GR>
    33   class ListArcSetBase {
    34   public:
    35 
    36     typedef typename GR::Node Node;
    37     typedef typename GR::NodeIt NodeIt;
    38 
    39   protected:
    40 
    41     struct NodeT {
    42       int first_out, first_in;
    43       NodeT() : first_out(-1), first_in(-1) {}
    44     };
    45 
    46     typedef typename ItemSetTraits<GR, Node>::
    47     template Map<NodeT>::Type NodesImplBase;
    48 
    49     NodesImplBase* _nodes;
    50 
    51     struct ArcT {
    52       Node source, target;
    53       int next_out, next_in;
    54       int prev_out, prev_in;
    55       ArcT() : prev_out(-1), prev_in(-1) {}
    56     };
    57 
    58     std::vector<ArcT> arcs;
    59 
    60     int first_arc;
    61     int first_free_arc;
    62 
    63     const GR* _graph;
    64 
    65     void initalize(const GR& graph, NodesImplBase& nodes) {
    66       _graph = &graph;
    67       _nodes = &nodes;
    68     }
    69 
    70   public:
    71 
    72     class Arc {
    73       friend class ListArcSetBase<GR>;
    74     protected:
    75       Arc(int _id) : id(_id) {}
    76       int id;
    77     public:
    78       Arc() {}
    79       Arc(Invalid) : id(-1) {}
    80       bool operator==(const Arc& arc) const { return id == arc.id; }
    81       bool operator!=(const Arc& arc) const { return id != arc.id; }
    82       bool operator<(const Arc& arc) const { return id < arc.id; }
    83     };
    84 
    85     ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
    86 
    87     Arc addArc(const Node& u, const Node& v) {
    88       int n;
    89       if (first_free_arc == -1) {
    90         n = arcs.size();
    91         arcs.push_back(ArcT());
    92       } else {
    93         n = first_free_arc;
    94         first_free_arc = arcs[first_free_arc].next_in;
    95       }
    96       arcs[n].next_in = (*_nodes)[v].first_in;
    97       if ((*_nodes)[v].first_in != -1) {
    98         arcs[(*_nodes)[v].first_in].prev_in = n;
    99       }
   100       (*_nodes)[v].first_in = n;
   101       arcs[n].next_out = (*_nodes)[u].first_out;
   102       if ((*_nodes)[u].first_out != -1) {
   103         arcs[(*_nodes)[u].first_out].prev_out = n;
   104       }
   105       (*_nodes)[u].first_out = n;
   106       arcs[n].source = u;
   107       arcs[n].target = v;
   108       return Arc(n);
   109     }
   110 
   111     void erase(const Arc& arc) {
   112       int n = arc.id;
   113       if (arcs[n].prev_in != -1) {
   114         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   115       } else {
   116         (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
   117       }
   118       if (arcs[n].next_in != -1) {
   119         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   120       }
   121 
   122       if (arcs[n].prev_out != -1) {
   123         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   124       } else {
   125         (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
   126       }
   127       if (arcs[n].next_out != -1) {
   128         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   129       }
   130 
   131     }
   132 
   133     void clear() {
   134       Node node;
   135       for (first(node); node != INVALID; next(node)) {
   136         (*_nodes)[node].first_in = -1;
   137         (*_nodes)[node].first_out = -1;
   138       }
   139       arcs.clear();
   140       first_arc = -1;
   141       first_free_arc = -1;
   142     }
   143 
   144     void first(Node& node) const {
   145       _graph->first(node);
   146     }
   147 
   148     void next(Node& node) const {
   149       _graph->next(node);
   150     }
   151 
   152     void first(Arc& arc) const {
   153       Node node;
   154       first(node);
   155       while (node != INVALID && (*_nodes)[node].first_in == -1) {
   156         next(node);
   157       }
   158       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
   159     }
   160 
   161     void next(Arc& arc) const {
   162       if (arcs[arc.id].next_in != -1) {
   163         arc.id = arcs[arc.id].next_in;
   164       } else {
   165         Node node = arcs[arc.id].target;
   166         next(node);
   167         while (node != INVALID && (*_nodes)[node].first_in == -1) {
   168           next(node);
   169         }
   170         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
   171       }
   172     }
   173 
   174     void firstOut(Arc& arc, const Node& node) const {
   175       arc.id = (*_nodes)[node].first_out;
   176     }
   177 
   178     void nextOut(Arc& arc) const {
   179       arc.id = arcs[arc.id].next_out;
   180     }
   181 
   182     void firstIn(Arc& arc, const Node& node) const {
   183       arc.id = (*_nodes)[node].first_in;
   184     }
   185 
   186     void nextIn(Arc& arc) const {
   187       arc.id = arcs[arc.id].next_in;
   188     }
   189 
   190     int id(const Node& node) const { return _graph->id(node); }
   191     int id(const Arc& arc) const { return arc.id; }
   192 
   193     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
   194     Arc arcFromId(int ix) const { return Arc(ix); }
   195 
   196     int maxNodeId() const { return _graph->maxNodeId(); };
   197     int maxArcId() const { return arcs.size() - 1; }
   198 
   199     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   200     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   201 
   202     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   203 
   204     NodeNotifier& notifier(Node) const {
   205       return _graph->notifier(Node());
   206     }
   207 
   208     template <typename V>
   209     class NodeMap : public GR::template NodeMap<V> {
   210       typedef typename GR::template NodeMap<V> Parent;
   211 
   212     public:
   213 
   214       explicit NodeMap(const ListArcSetBase<GR>& arcset)
   215         : Parent(*arcset._graph) {}
   216 
   217       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
   218         : Parent(*arcset._graph, value) {}
   219 
   220       NodeMap& operator=(const NodeMap& cmap) {
   221         return operator=<NodeMap>(cmap);
   222       }
   223 
   224       template <typename CMap>
   225       NodeMap& operator=(const CMap& cmap) {
   226         Parent::operator=(cmap);
   227         return *this;
   228       }
   229     };
   230 
   231   };
   232 
   233   /// \ingroup graphs
   234   ///
   235   /// \brief Digraph using a node set of another digraph or graph and
   236   /// an own arc set.
   237   ///
   238   /// This structure can be used to establish another directed graph
   239   /// over a node set of an existing one. This class uses the same
   240   /// Node type as the underlying graph, and each valid node of the
   241   /// original graph is valid in this arc set, therefore the node
   242   /// objects of the original graph can be used directly with this
   243   /// class. The node handling functions (id handling, observing, and
   244   /// iterators) works equivalently as in the original graph.
   245   ///
   246   /// This implementation is based on doubly-linked lists, from each
   247   /// node the outgoing and the incoming arcs make up lists, therefore
   248   /// one arc can be erased in constant time. It also makes possible,
   249   /// that node can be removed from the underlying graph, in this case
   250   /// all arcs incident to the given node is erased from the arc set.
   251   ///
   252   /// \param GR The type of the graph which shares its node set with
   253   /// this class. Its interface must conform to the
   254   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   255   /// concept.
   256   ///
   257   /// This class fully conforms to the \ref concepts::Digraph
   258   /// "Digraph" concept.
   259   template <typename GR>
   260   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
   261     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
   262 
   263   public:
   264 
   265     typedef typename Parent::Node Node;
   266     typedef typename Parent::Arc Arc;
   267 
   268     typedef typename Parent::NodesImplBase NodesImplBase;
   269 
   270     void eraseNode(const Node& node) {
   271       Arc arc;
   272       Parent::firstOut(arc, node);
   273       while (arc != INVALID ) {
   274         erase(arc);
   275         Parent::firstOut(arc, node);
   276       }
   277 
   278       Parent::firstIn(arc, node);
   279       while (arc != INVALID ) {
   280         erase(arc);
   281         Parent::firstIn(arc, node);
   282       }
   283     }
   284 
   285     void clearNodes() {
   286       Parent::clear();
   287     }
   288 
   289     class NodesImpl : public NodesImplBase {
   290       typedef NodesImplBase Parent;
   291 
   292     public:
   293       NodesImpl(const GR& graph, ListArcSet& arcset)
   294         : Parent(graph), _arcset(arcset) {}
   295 
   296       virtual ~NodesImpl() {}
   297 
   298     protected:
   299 
   300       virtual void erase(const Node& node) {
   301         _arcset.eraseNode(node);
   302         Parent::erase(node);
   303       }
   304       virtual void erase(const std::vector<Node>& nodes) {
   305         for (int i = 0; i < int(nodes.size()); ++i) {
   306           _arcset.eraseNode(nodes[i]);
   307         }
   308         Parent::erase(nodes);
   309       }
   310       virtual void clear() {
   311         _arcset.clearNodes();
   312         Parent::clear();
   313       }
   314 
   315     private:
   316       ListArcSet& _arcset;
   317     };
   318 
   319     NodesImpl _nodes;
   320 
   321   public:
   322 
   323     /// \brief Constructor of the ArcSet.
   324     ///
   325     /// Constructor of the ArcSet.
   326     ListArcSet(const GR& graph) : _nodes(graph, *this) {
   327       Parent::initalize(graph, _nodes);
   328     }
   329 
   330     /// \brief Add a new arc to the digraph.
   331     ///
   332     /// Add a new arc to the digraph with source node \c s
   333     /// and target node \c t.
   334     /// \return The new arc.
   335     Arc addArc(const Node& s, const Node& t) {
   336       return Parent::addArc(s, t);
   337     }
   338 
   339     /// \brief Erase an arc from the digraph.
   340     ///
   341     /// Erase an arc \c a from the digraph.
   342     void erase(const Arc& a) {
   343       return Parent::erase(a);
   344     }
   345 
   346   };
   347 
   348   template <typename GR>
   349   class ListEdgeSetBase {
   350   public:
   351 
   352     typedef typename GR::Node Node;
   353     typedef typename GR::NodeIt NodeIt;
   354 
   355   protected:
   356 
   357     struct NodeT {
   358       int first_out;
   359       NodeT() : first_out(-1) {}
   360     };
   361 
   362     typedef typename ItemSetTraits<GR, Node>::
   363     template Map<NodeT>::Type NodesImplBase;
   364 
   365     NodesImplBase* _nodes;
   366 
   367     struct ArcT {
   368       Node target;
   369       int prev_out, next_out;
   370       ArcT() : prev_out(-1), next_out(-1) {}
   371     };
   372 
   373     std::vector<ArcT> arcs;
   374 
   375     int first_arc;
   376     int first_free_arc;
   377 
   378     const GR* _graph;
   379 
   380     void initalize(const GR& graph, NodesImplBase& nodes) {
   381       _graph = &graph;
   382       _nodes = &nodes;
   383     }
   384 
   385   public:
   386 
   387     class Edge {
   388       friend class ListEdgeSetBase;
   389     protected:
   390 
   391       int id;
   392       explicit Edge(int _id) { id = _id;}
   393 
   394     public:
   395       Edge() {}
   396       Edge (Invalid) { id = -1; }
   397       bool operator==(const Edge& arc) const {return id == arc.id;}
   398       bool operator!=(const Edge& arc) const {return id != arc.id;}
   399       bool operator<(const Edge& arc) const {return id < arc.id;}
   400     };
   401 
   402     class Arc {
   403       friend class ListEdgeSetBase;
   404     protected:
   405       Arc(int _id) : id(_id) {}
   406       int id;
   407     public:
   408       operator Edge() const { return edgeFromId(id / 2); }
   409 
   410       Arc() {}
   411       Arc(Invalid) : id(-1) {}
   412       bool operator==(const Arc& arc) const { return id == arc.id; }
   413       bool operator!=(const Arc& arc) const { return id != arc.id; }
   414       bool operator<(const Arc& arc) const { return id < arc.id; }
   415     };
   416 
   417     ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
   418 
   419     Edge addEdge(const Node& u, const Node& v) {
   420       int n;
   421 
   422       if (first_free_arc == -1) {
   423         n = arcs.size();
   424         arcs.push_back(ArcT());
   425         arcs.push_back(ArcT());
   426       } else {
   427         n = first_free_arc;
   428         first_free_arc = arcs[n].next_out;
   429       }
   430 
   431       arcs[n].target = u;
   432       arcs[n | 1].target = v;
   433 
   434       arcs[n].next_out = (*_nodes)[v].first_out;
   435       if ((*_nodes)[v].first_out != -1) {
   436         arcs[(*_nodes)[v].first_out].prev_out = n;
   437       }
   438       (*_nodes)[v].first_out = n;
   439       arcs[n].prev_out = -1;
   440 
   441       if ((*_nodes)[u].first_out != -1) {
   442         arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
   443       }
   444       arcs[n | 1].next_out = (*_nodes)[u].first_out;
   445       (*_nodes)[u].first_out = (n | 1);
   446       arcs[n | 1].prev_out = -1;
   447 
   448       return Edge(n / 2);
   449     }
   450 
   451     void erase(const Edge& arc) {
   452       int n = arc.id * 2;
   453 
   454       if (arcs[n].next_out != -1) {
   455         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   456       }
   457 
   458       if (arcs[n].prev_out != -1) {
   459         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   460       } else {
   461         (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
   462       }
   463 
   464       if (arcs[n | 1].next_out != -1) {
   465         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   466       }
   467 
   468       if (arcs[n | 1].prev_out != -1) {
   469         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   470       } else {
   471         (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
   472       }
   473 
   474       arcs[n].next_out = first_free_arc;
   475       first_free_arc = n;
   476 
   477     }
   478 
   479     void clear() {
   480       Node node;
   481       for (first(node); node != INVALID; next(node)) {
   482         (*_nodes)[node].first_out = -1;
   483       }
   484       arcs.clear();
   485       first_arc = -1;
   486       first_free_arc = -1;
   487     }
   488 
   489     void first(Node& node) const {
   490       _graph->first(node);
   491     }
   492 
   493     void next(Node& node) const {
   494       _graph->next(node);
   495     }
   496 
   497     void first(Arc& arc) const {
   498       Node node;
   499       first(node);
   500       while (node != INVALID && (*_nodes)[node].first_out == -1) {
   501         next(node);
   502       }
   503       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
   504     }
   505 
   506     void next(Arc& arc) const {
   507       if (arcs[arc.id].next_out != -1) {
   508         arc.id = arcs[arc.id].next_out;
   509       } else {
   510         Node node = arcs[arc.id ^ 1].target;
   511         next(node);
   512         while(node != INVALID && (*_nodes)[node].first_out == -1) {
   513           next(node);
   514         }
   515         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
   516       }
   517     }
   518 
   519     void first(Edge& edge) const {
   520       Node node;
   521       first(node);
   522       while (node != INVALID) {
   523         edge.id = (*_nodes)[node].first_out;
   524         while ((edge.id & 1) != 1) {
   525           edge.id = arcs[edge.id].next_out;
   526         }
   527         if (edge.id != -1) {
   528           edge.id /= 2;
   529           return;
   530         }
   531         next(node);
   532       }
   533       edge.id = -1;
   534     }
   535 
   536     void next(Edge& edge) const {
   537       Node node = arcs[edge.id * 2].target;
   538       edge.id = arcs[(edge.id * 2) | 1].next_out;
   539       while ((edge.id & 1) != 1) {
   540         edge.id = arcs[edge.id].next_out;
   541       }
   542       if (edge.id != -1) {
   543         edge.id /= 2;
   544         return;
   545       }
   546       next(node);
   547       while (node != INVALID) {
   548         edge.id = (*_nodes)[node].first_out;
   549         while ((edge.id & 1) != 1) {
   550           edge.id = arcs[edge.id].next_out;
   551         }
   552         if (edge.id != -1) {
   553           edge.id /= 2;
   554           return;
   555         }
   556         next(node);
   557       }
   558       edge.id = -1;
   559     }
   560 
   561     void firstOut(Arc& arc, const Node& node) const {
   562       arc.id = (*_nodes)[node].first_out;
   563     }
   564 
   565     void nextOut(Arc& arc) const {
   566       arc.id = arcs[arc.id].next_out;
   567     }
   568 
   569     void firstIn(Arc& arc, const Node& node) const {
   570       arc.id = (((*_nodes)[node].first_out) ^ 1);
   571       if (arc.id == -2) arc.id = -1;
   572     }
   573 
   574     void nextIn(Arc& arc) const {
   575       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
   576       if (arc.id == -2) arc.id = -1;
   577     }
   578 
   579     void firstInc(Edge &arc, bool& dir, const Node& node) const {
   580       int de = (*_nodes)[node].first_out;
   581       if (de != -1 ) {
   582         arc.id = de / 2;
   583         dir = ((de & 1) == 1);
   584       } else {
   585         arc.id = -1;
   586         dir = true;
   587       }
   588     }
   589     void nextInc(Edge &arc, bool& dir) const {
   590       int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
   591       if (de != -1 ) {
   592         arc.id = de / 2;
   593         dir = ((de & 1) == 1);
   594       } else {
   595         arc.id = -1;
   596         dir = true;
   597       }
   598     }
   599 
   600     static bool direction(Arc arc) {
   601       return (arc.id & 1) == 1;
   602     }
   603 
   604     static Arc direct(Edge edge, bool dir) {
   605       return Arc(edge.id * 2 + (dir ? 1 : 0));
   606     }
   607 
   608     int id(const Node& node) const { return _graph->id(node); }
   609     static int id(Arc e) { return e.id; }
   610     static int id(Edge e) { return e.id; }
   611 
   612     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
   613     static Arc arcFromId(int id) { return Arc(id);}
   614     static Edge edgeFromId(int id) { return Edge(id);}
   615 
   616     int maxNodeId() const { return _graph->maxNodeId(); };
   617     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   618     int maxArcId() const { return arcs.size()-1; }
   619 
   620     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
   621     Node target(Arc e) const { return arcs[e.id].target; }
   622 
   623     Node u(Edge e) const { return arcs[2 * e.id].target; }
   624     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
   625 
   626     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   627 
   628     NodeNotifier& notifier(Node) const {
   629       return _graph->notifier(Node());
   630     }
   631 
   632     template <typename V>
   633     class NodeMap : public GR::template NodeMap<V> {
   634       typedef typename GR::template NodeMap<V> Parent;
   635 
   636     public:
   637 
   638       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
   639         : Parent(*arcset._graph) {}
   640 
   641       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
   642         : Parent(*arcset._graph, value) {}
   643 
   644       NodeMap& operator=(const NodeMap& cmap) {
   645         return operator=<NodeMap>(cmap);
   646       }
   647 
   648       template <typename CMap>
   649       NodeMap& operator=(const CMap& cmap) {
   650         Parent::operator=(cmap);
   651         return *this;
   652       }
   653     };
   654 
   655   };
   656 
   657   /// \ingroup graphs
   658   ///
   659   /// \brief Graph using a node set of another digraph or graph and an
   660   /// own edge set.
   661   ///
   662   /// This structure can be used to establish another graph over a
   663   /// node set of an existing one. This class uses the same Node type
   664   /// as the underlying graph, and each valid node of the original
   665   /// graph is valid in this arc set, therefore the node objects of
   666   /// the original graph can be used directly with this class. The
   667   /// node handling functions (id handling, observing, and iterators)
   668   /// works equivalently as in the original graph.
   669   ///
   670   /// This implementation is based on doubly-linked lists, from each
   671   /// node the incident edges make up lists, therefore one edge can be
   672   /// erased in constant time. It also makes possible, that node can
   673   /// be removed from the underlying graph, in this case all edges
   674   /// incident to the given node is erased from the arc set.
   675   ///
   676   /// \param GR The type of the graph which shares its node set
   677   /// with this class. Its interface must conform to the
   678   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   679   /// concept.
   680   ///
   681   /// This class fully conforms to the \ref concepts::Graph "Graph"
   682   /// concept.
   683   template <typename GR>
   684   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
   685     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
   686 
   687   public:
   688 
   689     typedef typename Parent::Node Node;
   690     typedef typename Parent::Arc Arc;
   691     typedef typename Parent::Edge Edge;
   692 
   693     typedef typename Parent::NodesImplBase NodesImplBase;
   694 
   695     void eraseNode(const Node& node) {
   696       Arc arc;
   697       Parent::firstOut(arc, node);
   698       while (arc != INVALID ) {
   699         erase(arc);
   700         Parent::firstOut(arc, node);
   701       }
   702 
   703     }
   704 
   705     void clearNodes() {
   706       Parent::clear();
   707     }
   708 
   709     class NodesImpl : public NodesImplBase {
   710       typedef NodesImplBase Parent;
   711 
   712     public:
   713       NodesImpl(const GR& graph, ListEdgeSet& arcset)
   714         : Parent(graph), _arcset(arcset) {}
   715 
   716       virtual ~NodesImpl() {}
   717 
   718     protected:
   719 
   720       virtual void erase(const Node& node) {
   721         _arcset.eraseNode(node);
   722         Parent::erase(node);
   723       }
   724       virtual void erase(const std::vector<Node>& nodes) {
   725         for (int i = 0; i < int(nodes.size()); ++i) {
   726           _arcset.eraseNode(nodes[i]);
   727         }
   728         Parent::erase(nodes);
   729       }
   730       virtual void clear() {
   731         _arcset.clearNodes();
   732         Parent::clear();
   733       }
   734 
   735     private:
   736       ListEdgeSet& _arcset;
   737     };
   738 
   739     NodesImpl _nodes;
   740 
   741   public:
   742 
   743     /// \brief Constructor of the EdgeSet.
   744     ///
   745     /// Constructor of the EdgeSet.
   746     ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
   747       Parent::initalize(graph, _nodes);
   748     }
   749 
   750     /// \brief Add a new edge to the graph.
   751     ///
   752     /// Add a new edge to the graph with node \c u
   753     /// and node \c v endpoints.
   754     /// \return The new edge.
   755     Edge addEdge(const Node& u, const Node& v) {
   756       return Parent::addEdge(u, v);
   757     }
   758 
   759     /// \brief Erase an edge from the graph.
   760     ///
   761     /// Erase the edge \c e from the graph.
   762     void erase(const Edge& e) {
   763       return Parent::erase(e);
   764     }
   765 
   766   };
   767 
   768   template <typename GR>
   769   class SmartArcSetBase {
   770   public:
   771 
   772     typedef typename GR::Node Node;
   773     typedef typename GR::NodeIt NodeIt;
   774 
   775   protected:
   776 
   777     struct NodeT {
   778       int first_out, first_in;
   779       NodeT() : first_out(-1), first_in(-1) {}
   780     };
   781 
   782     typedef typename ItemSetTraits<GR, Node>::
   783     template Map<NodeT>::Type NodesImplBase;
   784 
   785     NodesImplBase* _nodes;
   786 
   787     struct ArcT {
   788       Node source, target;
   789       int next_out, next_in;
   790       ArcT() {}
   791     };
   792 
   793     std::vector<ArcT> arcs;
   794 
   795     const GR* _graph;
   796 
   797     void initalize(const GR& graph, NodesImplBase& nodes) {
   798       _graph = &graph;
   799       _nodes = &nodes;
   800     }
   801 
   802   public:
   803 
   804     class Arc {
   805       friend class SmartArcSetBase<GR>;
   806     protected:
   807       Arc(int _id) : id(_id) {}
   808       int id;
   809     public:
   810       Arc() {}
   811       Arc(Invalid) : id(-1) {}
   812       bool operator==(const Arc& arc) const { return id == arc.id; }
   813       bool operator!=(const Arc& arc) const { return id != arc.id; }
   814       bool operator<(const Arc& arc) const { return id < arc.id; }
   815     };
   816 
   817     SmartArcSetBase() {}
   818 
   819     Arc addArc(const Node& u, const Node& v) {
   820       int n = arcs.size();
   821       arcs.push_back(ArcT());
   822       arcs[n].next_in = (*_nodes)[v].first_in;
   823       (*_nodes)[v].first_in = n;
   824       arcs[n].next_out = (*_nodes)[u].first_out;
   825       (*_nodes)[u].first_out = n;
   826       arcs[n].source = u;
   827       arcs[n].target = v;
   828       return Arc(n);
   829     }
   830 
   831     void clear() {
   832       Node node;
   833       for (first(node); node != INVALID; next(node)) {
   834         (*_nodes)[node].first_in = -1;
   835         (*_nodes)[node].first_out = -1;
   836       }
   837       arcs.clear();
   838     }
   839 
   840     void first(Node& node) const {
   841       _graph->first(node);
   842     }
   843 
   844     void next(Node& node) const {
   845       _graph->next(node);
   846     }
   847 
   848     void first(Arc& arc) const {
   849       arc.id = arcs.size() - 1;
   850     }
   851 
   852     void next(Arc& arc) const {
   853       --arc.id;
   854     }
   855 
   856     void firstOut(Arc& arc, const Node& node) const {
   857       arc.id = (*_nodes)[node].first_out;
   858     }
   859 
   860     void nextOut(Arc& arc) const {
   861       arc.id = arcs[arc.id].next_out;
   862     }
   863 
   864     void firstIn(Arc& arc, const Node& node) const {
   865       arc.id = (*_nodes)[node].first_in;
   866     }
   867 
   868     void nextIn(Arc& arc) const {
   869       arc.id = arcs[arc.id].next_in;
   870     }
   871 
   872     int id(const Node& node) const { return _graph->id(node); }
   873     int id(const Arc& arc) const { return arc.id; }
   874 
   875     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
   876     Arc arcFromId(int ix) const { return Arc(ix); }
   877 
   878     int maxNodeId() const { return _graph->maxNodeId(); };
   879     int maxArcId() const { return arcs.size() - 1; }
   880 
   881     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   882     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   883 
   884     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   885 
   886     NodeNotifier& notifier(Node) const {
   887       return _graph->notifier(Node());
   888     }
   889 
   890     template <typename V>
   891     class NodeMap : public GR::template NodeMap<V> {
   892       typedef typename GR::template NodeMap<V> Parent;
   893 
   894     public:
   895 
   896       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
   897         : Parent(*arcset._graph) { }
   898 
   899       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
   900         : Parent(*arcset._graph, value) { }
   901 
   902       NodeMap& operator=(const NodeMap& cmap) {
   903         return operator=<NodeMap>(cmap);
   904       }
   905 
   906       template <typename CMap>
   907       NodeMap& operator=(const CMap& cmap) {
   908         Parent::operator=(cmap);
   909         return *this;
   910       }
   911     };
   912 
   913   };
   914 
   915 
   916   /// \ingroup graphs
   917   ///
   918   /// \brief Digraph using a node set of another digraph or graph and
   919   /// an own arc set.
   920   ///
   921   /// This structure can be used to establish another directed graph
   922   /// over a node set of an existing one. This class uses the same
   923   /// Node type as the underlying graph, and each valid node of the
   924   /// original graph is valid in this arc set, therefore the node
   925   /// objects of the original graph can be used directly with this
   926   /// class. The node handling functions (id handling, observing, and
   927   /// iterators) works equivalently as in the original graph.
   928   ///
   929   /// \param GR The type of the graph which shares its node set with
   930   /// this class. Its interface must conform to the
   931   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   932   /// concept.
   933   ///
   934   /// This implementation is slightly faster than the \c ListArcSet,
   935   /// because it uses continuous storage for arcs and it uses just
   936   /// single-linked lists for enumerate outgoing and incoming
   937   /// arcs. Therefore the arcs cannot be erased from the arc sets.
   938   ///
   939   /// \warning If a node is erased from the underlying graph and this
   940   /// node is the source or target of one arc in the arc set, then
   941   /// the arc set is invalidated, and it cannot be used anymore. The
   942   /// validity can be checked with the \c valid() member function.
   943   ///
   944   /// This class fully conforms to the \ref concepts::Digraph
   945   /// "Digraph" concept.
   946   template <typename GR>
   947   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
   948     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
   949 
   950   public:
   951 
   952     typedef typename Parent::Node Node;
   953     typedef typename Parent::Arc Arc;
   954 
   955   protected:
   956 
   957     typedef typename Parent::NodesImplBase NodesImplBase;
   958 
   959     void eraseNode(const Node& node) {
   960       if (typename Parent::InArcIt(*this, node) == INVALID &&
   961           typename Parent::OutArcIt(*this, node) == INVALID) {
   962         return;
   963       }
   964       throw typename NodesImplBase::Notifier::ImmediateDetach();
   965     }
   966 
   967     void clearNodes() {
   968       Parent::clear();
   969     }
   970 
   971     class NodesImpl : public NodesImplBase {
   972       typedef NodesImplBase Parent;
   973 
   974     public:
   975       NodesImpl(const GR& graph, SmartArcSet& arcset)
   976         : Parent(graph), _arcset(arcset) {}
   977 
   978       virtual ~NodesImpl() {}
   979 
   980       bool attached() const {
   981         return Parent::attached();
   982       }
   983 
   984     protected:
   985 
   986       virtual void erase(const Node& node) {
   987         try {
   988           _arcset.eraseNode(node);
   989           Parent::erase(node);
   990         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
   991           Parent::clear();
   992           throw;
   993         }
   994       }
   995       virtual void erase(const std::vector<Node>& nodes) {
   996         try {
   997           for (int i = 0; i < int(nodes.size()); ++i) {
   998             _arcset.eraseNode(nodes[i]);
   999           }
  1000           Parent::erase(nodes);
  1001         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  1002           Parent::clear();
  1003           throw;
  1004         }
  1005       }
  1006       virtual void clear() {
  1007         _arcset.clearNodes();
  1008         Parent::clear();
  1009       }
  1010 
  1011     private:
  1012       SmartArcSet& _arcset;
  1013     };
  1014 
  1015     NodesImpl _nodes;
  1016 
  1017   public:
  1018 
  1019     /// \brief Constructor of the ArcSet.
  1020     ///
  1021     /// Constructor of the ArcSet.
  1022     SmartArcSet(const GR& graph) : _nodes(graph, *this) {
  1023       Parent::initalize(graph, _nodes);
  1024     }
  1025 
  1026     /// \brief Add a new arc to the digraph.
  1027     ///
  1028     /// Add a new arc to the digraph with source node \c s
  1029     /// and target node \c t.
  1030     /// \return The new arc.
  1031     Arc addArc(const Node& s, const Node& t) {
  1032       return Parent::addArc(s, t);
  1033     }
  1034 
  1035     /// \brief Validity check
  1036     ///
  1037     /// This functions gives back false if the ArcSet is
  1038     /// invalidated. It occurs when a node in the underlying graph is
  1039     /// erased and it is not isolated in the ArcSet.
  1040     bool valid() const {
  1041       return _nodes.attached();
  1042     }
  1043 
  1044   };
  1045 
  1046 
  1047   template <typename GR>
  1048   class SmartEdgeSetBase {
  1049   public:
  1050 
  1051     typedef typename GR::Node Node;
  1052     typedef typename GR::NodeIt NodeIt;
  1053 
  1054   protected:
  1055 
  1056     struct NodeT {
  1057       int first_out;
  1058       NodeT() : first_out(-1) {}
  1059     };
  1060 
  1061     typedef typename ItemSetTraits<GR, Node>::
  1062     template Map<NodeT>::Type NodesImplBase;
  1063 
  1064     NodesImplBase* _nodes;
  1065 
  1066     struct ArcT {
  1067       Node target;
  1068       int next_out;
  1069       ArcT() {}
  1070     };
  1071 
  1072     std::vector<ArcT> arcs;
  1073 
  1074     const GR* _graph;
  1075 
  1076     void initalize(const GR& graph, NodesImplBase& nodes) {
  1077       _graph = &graph;
  1078       _nodes = &nodes;
  1079     }
  1080 
  1081   public:
  1082 
  1083     class Edge {
  1084       friend class SmartEdgeSetBase;
  1085     protected:
  1086 
  1087       int id;
  1088       explicit Edge(int _id) { id = _id;}
  1089 
  1090     public:
  1091       Edge() {}
  1092       Edge (Invalid) { id = -1; }
  1093       bool operator==(const Edge& arc) const {return id == arc.id;}
  1094       bool operator!=(const Edge& arc) const {return id != arc.id;}
  1095       bool operator<(const Edge& arc) const {return id < arc.id;}
  1096     };
  1097 
  1098     class Arc {
  1099       friend class SmartEdgeSetBase;
  1100     protected:
  1101       Arc(int _id) : id(_id) {}
  1102       int id;
  1103     public:
  1104       operator Edge() const { return edgeFromId(id / 2); }
  1105 
  1106       Arc() {}
  1107       Arc(Invalid) : id(-1) {}
  1108       bool operator==(const Arc& arc) const { return id == arc.id; }
  1109       bool operator!=(const Arc& arc) const { return id != arc.id; }
  1110       bool operator<(const Arc& arc) const { return id < arc.id; }
  1111     };
  1112 
  1113     SmartEdgeSetBase() {}
  1114 
  1115     Edge addEdge(const Node& u, const Node& v) {
  1116       int n = arcs.size();
  1117       arcs.push_back(ArcT());
  1118       arcs.push_back(ArcT());
  1119 
  1120       arcs[n].target = u;
  1121       arcs[n | 1].target = v;
  1122 
  1123       arcs[n].next_out = (*_nodes)[v].first_out;
  1124       (*_nodes)[v].first_out = n;
  1125 
  1126       arcs[n | 1].next_out = (*_nodes)[u].first_out;
  1127       (*_nodes)[u].first_out = (n | 1);
  1128 
  1129       return Edge(n / 2);
  1130     }
  1131 
  1132     void clear() {
  1133       Node node;
  1134       for (first(node); node != INVALID; next(node)) {
  1135         (*_nodes)[node].first_out = -1;
  1136       }
  1137       arcs.clear();
  1138     }
  1139 
  1140     void first(Node& node) const {
  1141       _graph->first(node);
  1142     }
  1143 
  1144     void next(Node& node) const {
  1145       _graph->next(node);
  1146     }
  1147 
  1148     void first(Arc& arc) const {
  1149       arc.id = arcs.size() - 1;
  1150     }
  1151 
  1152     void next(Arc& arc) const {
  1153       --arc.id;
  1154     }
  1155 
  1156     void first(Edge& arc) const {
  1157       arc.id = arcs.size() / 2 - 1;
  1158     }
  1159 
  1160     void next(Edge& arc) const {
  1161       --arc.id;
  1162     }
  1163 
  1164     void firstOut(Arc& arc, const Node& node) const {
  1165       arc.id = (*_nodes)[node].first_out;
  1166     }
  1167 
  1168     void nextOut(Arc& arc) const {
  1169       arc.id = arcs[arc.id].next_out;
  1170     }
  1171 
  1172     void firstIn(Arc& arc, const Node& node) const {
  1173       arc.id = (((*_nodes)[node].first_out) ^ 1);
  1174       if (arc.id == -2) arc.id = -1;
  1175     }
  1176 
  1177     void nextIn(Arc& arc) const {
  1178       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
  1179       if (arc.id == -2) arc.id = -1;
  1180     }
  1181 
  1182     void firstInc(Edge &arc, bool& dir, const Node& node) const {
  1183       int de = (*_nodes)[node].first_out;
  1184       if (de != -1 ) {
  1185         arc.id = de / 2;
  1186         dir = ((de & 1) == 1);
  1187       } else {
  1188         arc.id = -1;
  1189         dir = true;
  1190       }
  1191     }
  1192     void nextInc(Edge &arc, bool& dir) const {
  1193       int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out);
  1194       if (de != -1 ) {
  1195         arc.id = de / 2;
  1196         dir = ((de & 1) == 1);
  1197       } else {
  1198         arc.id = -1;
  1199         dir = true;
  1200       }
  1201     }
  1202 
  1203     static bool direction(Arc arc) {
  1204       return (arc.id & 1) == 1;
  1205     }
  1206 
  1207     static Arc direct(Edge edge, bool dir) {
  1208       return Arc(edge.id * 2 + (dir ? 1 : 0));
  1209     }
  1210 
  1211     int id(Node node) const { return _graph->id(node); }
  1212     static int id(Arc arc) { return arc.id; }
  1213     static int id(Edge arc) { return arc.id; }
  1214 
  1215     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
  1216     static Arc arcFromId(int id) { return Arc(id); }
  1217     static Edge edgeFromId(int id) { return Edge(id);}
  1218 
  1219     int maxNodeId() const { return _graph->maxNodeId(); };
  1220     int maxArcId() const { return arcs.size() - 1; }
  1221     int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1222 
  1223     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
  1224     Node target(Arc e) const { return arcs[e.id].target; }
  1225 
  1226     Node u(Edge e) const { return arcs[2 * e.id].target; }
  1227     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
  1228 
  1229     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
  1230 
  1231     NodeNotifier& notifier(Node) const {
  1232       return _graph->notifier(Node());
  1233     }
  1234 
  1235     template <typename V>
  1236     class NodeMap : public GR::template NodeMap<V> {
  1237       typedef typename GR::template NodeMap<V> Parent;
  1238 
  1239     public:
  1240 
  1241       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
  1242         : Parent(*arcset._graph) { }
  1243 
  1244       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
  1245         : Parent(*arcset._graph, value) { }
  1246 
  1247       NodeMap& operator=(const NodeMap& cmap) {
  1248         return operator=<NodeMap>(cmap);
  1249       }
  1250 
  1251       template <typename CMap>
  1252       NodeMap& operator=(const CMap& cmap) {
  1253         Parent::operator=(cmap);
  1254         return *this;
  1255       }
  1256     };
  1257 
  1258   };
  1259 
  1260   /// \ingroup graphs
  1261   ///
  1262   /// \brief Graph using a node set of another digraph or graph and an
  1263   /// own edge set.
  1264   ///
  1265   /// This structure can be used to establish another graph over a
  1266   /// node set of an existing one. This class uses the same Node type
  1267   /// as the underlying graph, and each valid node of the original
  1268   /// graph is valid in this arc set, therefore the node objects of
  1269   /// the original graph can be used directly with this class. The
  1270   /// node handling functions (id handling, observing, and iterators)
  1271   /// works equivalently as in the original graph.
  1272   ///
  1273   /// \param GR The type of the graph which shares its node set
  1274   /// with this class. Its interface must conform to the
  1275   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
  1276   ///  concept.
  1277   ///
  1278   /// This implementation is slightly faster than the \c ListEdgeSet,
  1279   /// because it uses continuous storage for edges and it uses just
  1280   /// single-linked lists for enumerate incident edges. Therefore the
  1281   /// edges cannot be erased from the edge sets.
  1282   ///
  1283   /// \warning If a node is erased from the underlying graph and this
  1284   /// node is incident to one edge in the edge set, then the edge set
  1285   /// is invalidated, and it cannot be used anymore. The validity can
  1286   /// be checked with the \c valid() member function.
  1287   ///
  1288   /// This class fully conforms to the \ref concepts::Graph
  1289   /// "Graph" concept.
  1290   template <typename GR>
  1291   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  1292     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
  1293 
  1294   public:
  1295 
  1296     typedef typename Parent::Node Node;
  1297     typedef typename Parent::Arc Arc;
  1298     typedef typename Parent::Edge Edge;
  1299 
  1300   protected:
  1301 
  1302     typedef typename Parent::NodesImplBase NodesImplBase;
  1303 
  1304     void eraseNode(const Node& node) {
  1305       if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
  1306         return;
  1307       }
  1308       throw typename NodesImplBase::Notifier::ImmediateDetach();
  1309     }
  1310 
  1311     void clearNodes() {
  1312       Parent::clear();
  1313     }
  1314 
  1315     class NodesImpl : public NodesImplBase {
  1316       typedef NodesImplBase Parent;
  1317 
  1318     public:
  1319       NodesImpl(const GR& graph, SmartEdgeSet& arcset)
  1320         : Parent(graph), _arcset(arcset) {}
  1321 
  1322       virtual ~NodesImpl() {}
  1323 
  1324       bool attached() const {
  1325         return Parent::attached();
  1326       }
  1327 
  1328     protected:
  1329 
  1330       virtual void erase(const Node& node) {
  1331         try {
  1332           _arcset.eraseNode(node);
  1333           Parent::erase(node);
  1334         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  1335           Parent::clear();
  1336           throw;
  1337         }
  1338       }
  1339       virtual void erase(const std::vector<Node>& nodes) {
  1340         try {
  1341           for (int i = 0; i < int(nodes.size()); ++i) {
  1342             _arcset.eraseNode(nodes[i]);
  1343           }
  1344           Parent::erase(nodes);
  1345         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
  1346           Parent::clear();
  1347           throw;
  1348         }
  1349       }
  1350       virtual void clear() {
  1351         _arcset.clearNodes();
  1352         Parent::clear();
  1353       }
  1354 
  1355     private:
  1356       SmartEdgeSet& _arcset;
  1357     };
  1358 
  1359     NodesImpl _nodes;
  1360 
  1361   public:
  1362 
  1363     /// \brief Constructor of the EdgeSet.
  1364     ///
  1365     /// Constructor of the EdgeSet.
  1366     SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
  1367       Parent::initalize(graph, _nodes);
  1368     }
  1369 
  1370     /// \brief Add a new edge to the graph.
  1371     ///
  1372     /// Add a new edge to the graph with node \c u
  1373     /// and node \c v endpoints.
  1374     /// \return The new edge.
  1375     Edge addEdge(const Node& u, const Node& v) {
  1376       return Parent::addEdge(u, v);
  1377     }
  1378 
  1379     /// \brief Validity check
  1380     ///
  1381     /// This functions gives back false if the EdgeSet is
  1382     /// invalidated. It occurs when a node in the underlying graph is
  1383     /// erased and it is not isolated in the EdgeSet.
  1384     bool valid() const {
  1385       return _nodes.attached();
  1386     }
  1387 
  1388   };
  1389 
  1390 }
  1391 
  1392 #endif