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