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