lemon/edge_set.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 06 Aug 2009 20:12:43 +0200
changeset 760 83ce7ce39f21
parent 660 d9cf3b5858ae
child 778 a143f19f465b
permissions -rw-r--r--
Rework and fix the implementation of MinMeanCycle (#179)

- Fix the handling of the cycle means.
- Many implementation improvements:
- More efficient data storage for the strongly connected
components.
- Better handling of BFS queues.
- Merge consecutive BFS searches (perform two BFS searches
instead of three).

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