lemon/edge_set.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 13 Feb 2009 14:56:27 +0000
changeset 486 bc0a130bbb46
child 488 9b9ffe7d9b75
permissions -rw-r--r--
Fix in lp_base.cc targeting AIX/xlC compatibility
     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