lemon/edge_set.h
changeset 524 06e0fb20a97c
parent 468 68fe66e2b34a
child 559 c5fd2d996909
equal deleted inserted replaced
0:156cf2b3e5a3 1:539ef86d6577
    27 /// \brief ArcSet and EdgeSet classes.
    27 /// \brief ArcSet and EdgeSet classes.
    28 ///
    28 ///
    29 /// Graphs which use another graph's node-set as own.
    29 /// Graphs which use another graph's node-set as own.
    30 namespace lemon {
    30 namespace lemon {
    31 
    31 
    32   template <typename _Graph>
    32   template <typename GR>
    33   class ListArcSetBase {
    33   class ListArcSetBase {
    34   public:
    34   public:
    35 
    35 
    36     typedef _Graph Graph;
    36     typedef GR Graph;
    37     typedef typename Graph::Node Node;
    37     typedef typename GR::Node Node;
    38     typedef typename Graph::NodeIt NodeIt;
    38     typedef typename GR::NodeIt NodeIt;
    39 
    39 
    40   protected:
    40   protected:
    41 
    41 
    42     struct NodeT {
    42     struct NodeT {
    43       int first_out, first_in;
    43       int first_out, first_in;
    44       NodeT() : first_out(-1), first_in(-1) {}
    44       NodeT() : first_out(-1), first_in(-1) {}
    45     };
    45     };
    46 
    46 
    47     typedef typename ItemSetTraits<Graph, Node>::
    47     typedef typename ItemSetTraits<GR, Node>::
    48     template Map<NodeT>::Type NodesImplBase;
    48     template Map<NodeT>::Type NodesImplBase;
    49 
    49 
    50     NodesImplBase* nodes;
    50     NodesImplBase* _nodes;
    51 
    51 
    52     struct ArcT {
    52     struct ArcT {
    53       Node source, target;
    53       Node source, target;
    54       int next_out, next_in;
    54       int next_out, next_in;
    55       int prev_out, prev_in;
    55       int prev_out, prev_in;
    59     std::vector<ArcT> arcs;
    59     std::vector<ArcT> arcs;
    60 
    60 
    61     int first_arc;
    61     int first_arc;
    62     int first_free_arc;
    62     int first_free_arc;
    63 
    63 
    64     const Graph* graph;
    64     const GR* _graph;
    65 
    65 
    66     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
    66     void initalize(const GR& graph, NodesImplBase& nodes) {
    67       graph = &_graph;
    67       _graph = &graph;
    68       nodes = &_nodes;
    68       _nodes = &nodes;
    69     }
    69     }
    70 
    70 
    71   public:
    71   public:
    72 
    72 
    73     class Arc {
    73     class Arc {
    74       friend class ListArcSetBase<Graph>;
    74       friend class ListArcSetBase<GR>;
    75     protected:
    75     protected:
    76       Arc(int _id) : id(_id) {}
    76       Arc(int _id) : id(_id) {}
    77       int id;
    77       int id;
    78     public:
    78     public:
    79       Arc() {}
    79       Arc() {}
    92         arcs.push_back(ArcT());
    92         arcs.push_back(ArcT());
    93       } else {
    93       } else {
    94         n = first_free_arc;
    94         n = first_free_arc;
    95         first_free_arc = arcs[first_free_arc].next_in;
    95         first_free_arc = arcs[first_free_arc].next_in;
    96       }
    96       }
    97       arcs[n].next_in = (*nodes)[v].first_in;
    97       arcs[n].next_in = (*_nodes)[v].first_in;
    98       if ((*nodes)[v].first_in != -1) {
    98       if ((*_nodes)[v].first_in != -1) {
    99         arcs[(*nodes)[v].first_in].prev_in = n;
    99         arcs[(*_nodes)[v].first_in].prev_in = n;
   100       }
   100       }
   101       (*nodes)[v].first_in = n;
   101       (*_nodes)[v].first_in = n;
   102       arcs[n].next_out = (*nodes)[u].first_out;
   102       arcs[n].next_out = (*_nodes)[u].first_out;
   103       if ((*nodes)[u].first_out != -1) {
   103       if ((*_nodes)[u].first_out != -1) {
   104         arcs[(*nodes)[u].first_out].prev_out = n;
   104         arcs[(*_nodes)[u].first_out].prev_out = n;
   105       }
   105       }
   106       (*nodes)[u].first_out = n;
   106       (*_nodes)[u].first_out = n;
   107       arcs[n].source = u;
   107       arcs[n].source = u;
   108       arcs[n].target = v;
   108       arcs[n].target = v;
   109       return Arc(n);
   109       return Arc(n);
   110     }
   110     }
   111 
   111 
   112     void erase(const Arc& arc) {
   112     void erase(const Arc& arc) {
   113       int n = arc.id;
   113       int n = arc.id;
   114       if (arcs[n].prev_in != -1) {
   114       if (arcs[n].prev_in != -1) {
   115         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   115         arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
   116       } else {
   116       } else {
   117         (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
   117         (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
   118       }
   118       }
   119       if (arcs[n].next_in != -1) {
   119       if (arcs[n].next_in != -1) {
   120         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   120         arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
   121       }
   121       }
   122 
   122 
   123       if (arcs[n].prev_out != -1) {
   123       if (arcs[n].prev_out != -1) {
   124         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   124         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   125       } else {
   125       } else {
   126         (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
   126         (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
   127       }
   127       }
   128       if (arcs[n].next_out != -1) {
   128       if (arcs[n].next_out != -1) {
   129         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   129         arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
   130       }
   130       }
   131 
   131 
   132     }
   132     }
   133 
   133 
   134     void clear() {
   134     void clear() {
   135       Node node;
   135       Node node;
   136       for (first(node); node != INVALID; next(node)) {
   136       for (first(node); node != INVALID; next(node)) {
   137         (*nodes)[node].first_in = -1;
   137         (*_nodes)[node].first_in = -1;
   138         (*nodes)[node].first_out = -1;
   138         (*_nodes)[node].first_out = -1;
   139       }
   139       }
   140       arcs.clear();
   140       arcs.clear();
   141       first_arc = -1;
   141       first_arc = -1;
   142       first_free_arc = -1;
   142       first_free_arc = -1;
   143     }
   143     }
   144 
   144 
   145     void first(Node& node) const {
   145     void first(Node& node) const {
   146       graph->first(node);
   146       _graph->first(node);
   147     }
   147     }
   148 
   148 
   149     void next(Node& node) const {
   149     void next(Node& node) const {
   150       graph->next(node);
   150       _graph->next(node);
   151     }
   151     }
   152 
   152 
   153     void first(Arc& arc) const {
   153     void first(Arc& arc) const {
   154       Node node;
   154       Node node;
   155       first(node);
   155       first(node);
   156       while (node != INVALID && (*nodes)[node].first_in == -1) {
   156       while (node != INVALID && (*_nodes)[node].first_in == -1) {
   157         next(node);
   157         next(node);
   158       }
   158       }
   159       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   159       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
   160     }
   160     }
   161 
   161 
   162     void next(Arc& arc) const {
   162     void next(Arc& arc) const {
   163       if (arcs[arc.id].next_in != -1) {
   163       if (arcs[arc.id].next_in != -1) {
   164         arc.id = arcs[arc.id].next_in;
   164         arc.id = arcs[arc.id].next_in;
   165       } else {
   165       } else {
   166         Node node = arcs[arc.id].target;
   166         Node node = arcs[arc.id].target;
   167         next(node);
   167         next(node);
   168         while (node != INVALID && (*nodes)[node].first_in == -1) {
   168         while (node != INVALID && (*_nodes)[node].first_in == -1) {
   169           next(node);
   169           next(node);
   170         }
   170         }
   171         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
   171         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
   172       }
   172       }
   173     }
   173     }
   174 
   174 
   175     void firstOut(Arc& arc, const Node& node) const {
   175     void firstOut(Arc& arc, const Node& node) const {
   176       arc.id = (*nodes)[node].first_out;
   176       arc.id = (*_nodes)[node].first_out;
   177     }
   177     }
   178 
   178 
   179     void nextOut(Arc& arc) const {
   179     void nextOut(Arc& arc) const {
   180       arc.id = arcs[arc.id].next_out;
   180       arc.id = arcs[arc.id].next_out;
   181     }
   181     }
   182 
   182 
   183     void firstIn(Arc& arc, const Node& node) const {
   183     void firstIn(Arc& arc, const Node& node) const {
   184       arc.id = (*nodes)[node].first_in;
   184       arc.id = (*_nodes)[node].first_in;
   185     }
   185     }
   186 
   186 
   187     void nextIn(Arc& arc) const {
   187     void nextIn(Arc& arc) const {
   188       arc.id = arcs[arc.id].next_in;
   188       arc.id = arcs[arc.id].next_in;
   189     }
   189     }
   190 
   190 
   191     int id(const Node& node) const { return graph->id(node); }
   191     int id(const Node& node) const { return _graph->id(node); }
   192     int id(const Arc& arc) const { return arc.id; }
   192     int id(const Arc& arc) const { return arc.id; }
   193 
   193 
   194     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
   194     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
   195     Arc arcFromId(int ix) const { return Arc(ix); }
   195     Arc arcFromId(int ix) const { return Arc(ix); }
   196 
   196 
   197     int maxNodeId() const { return graph->maxNodeId(); };
   197     int maxNodeId() const { return _graph->maxNodeId(); };
   198     int maxArcId() const { return arcs.size() - 1; }
   198     int maxArcId() const { return arcs.size() - 1; }
   199 
   199 
   200     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   200     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   201     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   201     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   202 
   202 
   203     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   203     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   204 
   204 
   205     NodeNotifier& notifier(Node) const {
   205     NodeNotifier& notifier(Node) const {
   206       return graph->notifier(Node());
   206       return _graph->notifier(Node());
   207     }
   207     }
   208 
   208 
   209     template <typename _Value>
   209     template <typename V>
   210     class NodeMap : public Graph::template NodeMap<_Value> {
   210     class NodeMap : public GR::template NodeMap<V> {
   211     public:
   211     public:
   212 
   212 
   213       typedef typename _Graph::template NodeMap<_Value> Parent;
   213       typedef typename GR::template NodeMap<V> Parent;
   214 
   214 
   215       explicit NodeMap(const ListArcSetBase<Graph>& arcset)
   215       explicit NodeMap(const ListArcSetBase<GR>& arcset)
   216         : Parent(*arcset.graph) {}
   216         : Parent(*arcset._graph) {}
   217 
   217 
   218       NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
   218       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
   219         : Parent(*arcset.graph, value) {}
   219         : Parent(*arcset._graph, value) {}
   220 
   220 
   221       NodeMap& operator=(const NodeMap& cmap) {
   221       NodeMap& operator=(const NodeMap& cmap) {
   222         return operator=<NodeMap>(cmap);
   222         return operator=<NodeMap>(cmap);
   223       }
   223       }
   224 
   224 
   248   /// node the outgoing and the incoming arcs make up lists, therefore
   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,
   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
   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.
   251   /// all arcs incident to the given node is erased from the arc set.
   252   ///
   252   ///
   253   /// \param _Graph The type of the graph which shares its node set with
   253   /// \param GR The type of the graph which shares its node set with
   254   /// this class. Its interface must conform to the
   254   /// this class. Its interface must conform to the
   255   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   255   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   256   /// concept.
   256   /// concept.
   257   ///
   257   ///
   258   /// This class is fully conform to the \ref concepts::Digraph
   258   /// This class is fully conform to the \ref concepts::Digraph
   259   /// "Digraph" concept.
   259   /// "Digraph" concept.
   260   template <typename _Graph>
   260   template <typename GR>
   261   class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
   261   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
   262 
   262 
   263   public:
   263   public:
   264 
   264 
   265     typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
   265     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
   266 
   266 
   267     typedef typename Parent::Node Node;
   267     typedef typename Parent::Node Node;
   268     typedef typename Parent::Arc Arc;
   268     typedef typename Parent::Arc Arc;
   269 
   269 
   270     typedef _Graph Graph;
   270     typedef GR Graph;
   271 
   271 
   272 
   272 
   273     typedef typename Parent::NodesImplBase NodesImplBase;
   273     typedef typename Parent::NodesImplBase NodesImplBase;
   274 
   274 
   275     void eraseNode(const Node& node) {
   275     void eraseNode(const Node& node) {
   293 
   293 
   294     class NodesImpl : public NodesImplBase {
   294     class NodesImpl : public NodesImplBase {
   295     public:
   295     public:
   296       typedef NodesImplBase Parent;
   296       typedef NodesImplBase Parent;
   297 
   297 
   298       NodesImpl(const Graph& graph, ListArcSet& arcset)
   298       NodesImpl(const GR& graph, ListArcSet& arcset)
   299         : Parent(graph), _arcset(arcset) {}
   299         : Parent(graph), _arcset(arcset) {}
   300 
   300 
   301       virtual ~NodesImpl() {}
   301       virtual ~NodesImpl() {}
   302 
   302 
   303     protected:
   303     protected:
   319 
   319 
   320     private:
   320     private:
   321       ListArcSet& _arcset;
   321       ListArcSet& _arcset;
   322     };
   322     };
   323 
   323 
   324     NodesImpl nodes;
   324     NodesImpl _nodes;
   325 
   325 
   326   public:
   326   public:
   327 
   327 
   328     /// \brief Constructor of the ArcSet.
   328     /// \brief Constructor of the ArcSet.
   329     ///
   329     ///
   330     /// Constructor of the ArcSet.
   330     /// Constructor of the ArcSet.
   331     ListArcSet(const Graph& graph) : nodes(graph, *this) {
   331     ListArcSet(const GR& graph) : _nodes(graph, *this) {
   332       Parent::initalize(graph, nodes);
   332       Parent::initalize(graph, _nodes);
   333     }
   333     }
   334 
   334 
   335     /// \brief Add a new arc to the digraph.
   335     /// \brief Add a new arc to the digraph.
   336     ///
   336     ///
   337     /// Add a new arc to the digraph with source node \c s
   337     /// Add a new arc to the digraph with source node \c s
   348       return Parent::erase(a);
   348       return Parent::erase(a);
   349     }
   349     }
   350 
   350 
   351   };
   351   };
   352 
   352 
   353   template <typename _Graph>
   353   template <typename GR>
   354   class ListEdgeSetBase {
   354   class ListEdgeSetBase {
   355   public:
   355   public:
   356 
   356 
   357     typedef _Graph Graph;
   357     typedef GR Graph;
   358     typedef typename Graph::Node Node;
   358     typedef typename GR::Node Node;
   359     typedef typename Graph::NodeIt NodeIt;
   359     typedef typename GR::NodeIt NodeIt;
   360 
   360 
   361   protected:
   361   protected:
   362 
   362 
   363     struct NodeT {
   363     struct NodeT {
   364       int first_out;
   364       int first_out;
   365       NodeT() : first_out(-1) {}
   365       NodeT() : first_out(-1) {}
   366     };
   366     };
   367 
   367 
   368     typedef typename ItemSetTraits<Graph, Node>::
   368     typedef typename ItemSetTraits<GR, Node>::
   369     template Map<NodeT>::Type NodesImplBase;
   369     template Map<NodeT>::Type NodesImplBase;
   370 
   370 
   371     NodesImplBase* nodes;
   371     NodesImplBase* _nodes;
   372 
   372 
   373     struct ArcT {
   373     struct ArcT {
   374       Node target;
   374       Node target;
   375       int prev_out, next_out;
   375       int prev_out, next_out;
   376       ArcT() : prev_out(-1), next_out(-1) {}
   376       ArcT() : prev_out(-1), next_out(-1) {}
   379     std::vector<ArcT> arcs;
   379     std::vector<ArcT> arcs;
   380 
   380 
   381     int first_arc;
   381     int first_arc;
   382     int first_free_arc;
   382     int first_free_arc;
   383 
   383 
   384     const Graph* graph;
   384     const GR* _graph;
   385 
   385 
   386     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
   386     void initalize(const GR& graph, NodesImplBase& nodes) {
   387       graph = &_graph;
   387       _graph = &graph;
   388       nodes = &_nodes;
   388       _nodes = &nodes;
   389     }
   389     }
   390 
   390 
   391   public:
   391   public:
   392 
   392 
   393     class Edge {
   393     class Edge {
   435       }
   435       }
   436 
   436 
   437       arcs[n].target = u;
   437       arcs[n].target = u;
   438       arcs[n | 1].target = v;
   438       arcs[n | 1].target = v;
   439 
   439 
   440       arcs[n].next_out = (*nodes)[v].first_out;
   440       arcs[n].next_out = (*_nodes)[v].first_out;
   441       if ((*nodes)[v].first_out != -1) {
   441       if ((*_nodes)[v].first_out != -1) {
   442         arcs[(*nodes)[v].first_out].prev_out = n;
   442         arcs[(*_nodes)[v].first_out].prev_out = n;
   443       }
   443       }
   444       (*nodes)[v].first_out = n;
   444       (*_nodes)[v].first_out = n;
   445       arcs[n].prev_out = -1;
   445       arcs[n].prev_out = -1;
   446 
   446 
   447       if ((*nodes)[u].first_out != -1) {
   447       if ((*_nodes)[u].first_out != -1) {
   448         arcs[(*nodes)[u].first_out].prev_out = (n | 1);
   448         arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
   449       }
   449       }
   450       arcs[n | 1].next_out = (*nodes)[u].first_out;
   450       arcs[n | 1].next_out = (*_nodes)[u].first_out;
   451       (*nodes)[u].first_out = (n | 1);
   451       (*_nodes)[u].first_out = (n | 1);
   452       arcs[n | 1].prev_out = -1;
   452       arcs[n | 1].prev_out = -1;
   453 
   453 
   454       return Edge(n / 2);
   454       return Edge(n / 2);
   455     }
   455     }
   456 
   456 
   462       }
   462       }
   463 
   463 
   464       if (arcs[n].prev_out != -1) {
   464       if (arcs[n].prev_out != -1) {
   465         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   465         arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
   466       } else {
   466       } else {
   467         (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
   467         (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
   468       }
   468       }
   469 
   469 
   470       if (arcs[n | 1].next_out != -1) {
   470       if (arcs[n | 1].next_out != -1) {
   471         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   471         arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
   472       }
   472       }
   473 
   473 
   474       if (arcs[n | 1].prev_out != -1) {
   474       if (arcs[n | 1].prev_out != -1) {
   475         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   475         arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
   476       } else {
   476       } else {
   477         (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
   477         (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
   478       }
   478       }
   479 
   479 
   480       arcs[n].next_out = first_free_arc;
   480       arcs[n].next_out = first_free_arc;
   481       first_free_arc = n;
   481       first_free_arc = n;
   482 
   482 
   483     }
   483     }
   484 
   484 
   485     void clear() {
   485     void clear() {
   486       Node node;
   486       Node node;
   487       for (first(node); node != INVALID; next(node)) {
   487       for (first(node); node != INVALID; next(node)) {
   488         (*nodes)[node].first_out = -1;
   488         (*_nodes)[node].first_out = -1;
   489       }
   489       }
   490       arcs.clear();
   490       arcs.clear();
   491       first_arc = -1;
   491       first_arc = -1;
   492       first_free_arc = -1;
   492       first_free_arc = -1;
   493     }
   493     }
   494 
   494 
   495     void first(Node& node) const {
   495     void first(Node& node) const {
   496       graph->first(node);
   496       _graph->first(node);
   497     }
   497     }
   498 
   498 
   499     void next(Node& node) const {
   499     void next(Node& node) const {
   500       graph->next(node);
   500       _graph->next(node);
   501     }
   501     }
   502 
   502 
   503     void first(Arc& arc) const {
   503     void first(Arc& arc) const {
   504       Node node;
   504       Node node;
   505       first(node);
   505       first(node);
   506       while (node != INVALID && (*nodes)[node].first_out == -1) {
   506       while (node != INVALID && (*_nodes)[node].first_out == -1) {
   507         next(node);
   507         next(node);
   508       }
   508       }
   509       arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
   509       arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
   510     }
   510     }
   511 
   511 
   512     void next(Arc& arc) const {
   512     void next(Arc& arc) const {
   513       if (arcs[arc.id].next_out != -1) {
   513       if (arcs[arc.id].next_out != -1) {
   514         arc.id = arcs[arc.id].next_out;
   514         arc.id = arcs[arc.id].next_out;
   515       } else {
   515       } else {
   516         Node node = arcs[arc.id ^ 1].target;
   516         Node node = arcs[arc.id ^ 1].target;
   517         next(node);
   517         next(node);
   518         while(node != INVALID && (*nodes)[node].first_out == -1) {
   518         while(node != INVALID && (*_nodes)[node].first_out == -1) {
   519           next(node);
   519           next(node);
   520         }
   520         }
   521         arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
   521         arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
   522       }
   522       }
   523     }
   523     }
   524 
   524 
   525     void first(Edge& edge) const {
   525     void first(Edge& edge) const {
   526       Node node;
   526       Node node;
   527       first(node);
   527       first(node);
   528       while (node != INVALID) {
   528       while (node != INVALID) {
   529         edge.id = (*nodes)[node].first_out;
   529         edge.id = (*_nodes)[node].first_out;
   530         while ((edge.id & 1) != 1) {
   530         while ((edge.id & 1) != 1) {
   531           edge.id = arcs[edge.id].next_out;
   531           edge.id = arcs[edge.id].next_out;
   532         }
   532         }
   533         if (edge.id != -1) {
   533         if (edge.id != -1) {
   534           edge.id /= 2;
   534           edge.id /= 2;
   549         edge.id /= 2;
   549         edge.id /= 2;
   550         return;
   550         return;
   551       }
   551       }
   552       next(node);
   552       next(node);
   553       while (node != INVALID) {
   553       while (node != INVALID) {
   554         edge.id = (*nodes)[node].first_out;
   554         edge.id = (*_nodes)[node].first_out;
   555         while ((edge.id & 1) != 1) {
   555         while ((edge.id & 1) != 1) {
   556           edge.id = arcs[edge.id].next_out;
   556           edge.id = arcs[edge.id].next_out;
   557         }
   557         }
   558         if (edge.id != -1) {
   558         if (edge.id != -1) {
   559           edge.id /= 2;
   559           edge.id /= 2;
   563       }
   563       }
   564       edge.id = -1;
   564       edge.id = -1;
   565     }
   565     }
   566 
   566 
   567     void firstOut(Arc& arc, const Node& node) const {
   567     void firstOut(Arc& arc, const Node& node) const {
   568       arc.id = (*nodes)[node].first_out;
   568       arc.id = (*_nodes)[node].first_out;
   569     }
   569     }
   570 
   570 
   571     void nextOut(Arc& arc) const {
   571     void nextOut(Arc& arc) const {
   572       arc.id = arcs[arc.id].next_out;
   572       arc.id = arcs[arc.id].next_out;
   573     }
   573     }
   574 
   574 
   575     void firstIn(Arc& arc, const Node& node) const {
   575     void firstIn(Arc& arc, const Node& node) const {
   576       arc.id = (((*nodes)[node].first_out) ^ 1);
   576       arc.id = (((*_nodes)[node].first_out) ^ 1);
   577       if (arc.id == -2) arc.id = -1;
   577       if (arc.id == -2) arc.id = -1;
   578     }
   578     }
   579 
   579 
   580     void nextIn(Arc& arc) const {
   580     void nextIn(Arc& arc) const {
   581       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
   581       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
   582       if (arc.id == -2) arc.id = -1;
   582       if (arc.id == -2) arc.id = -1;
   583     }
   583     }
   584 
   584 
   585     void firstInc(Edge &arc, bool& dir, const Node& node) const {
   585     void firstInc(Edge &arc, bool& dir, const Node& node) const {
   586       int de = (*nodes)[node].first_out;
   586       int de = (*_nodes)[node].first_out;
   587       if (de != -1 ) {
   587       if (de != -1 ) {
   588         arc.id = de / 2;
   588         arc.id = de / 2;
   589         dir = ((de & 1) == 1);
   589         dir = ((de & 1) == 1);
   590       } else {
   590       } else {
   591         arc.id = -1;
   591         arc.id = -1;
   609 
   609 
   610     static Arc direct(Edge edge, bool dir) {
   610     static Arc direct(Edge edge, bool dir) {
   611       return Arc(edge.id * 2 + (dir ? 1 : 0));
   611       return Arc(edge.id * 2 + (dir ? 1 : 0));
   612     }
   612     }
   613 
   613 
   614     int id(const Node& node) const { return graph->id(node); }
   614     int id(const Node& node) const { return _graph->id(node); }
   615     static int id(Arc e) { return e.id; }
   615     static int id(Arc e) { return e.id; }
   616     static int id(Edge e) { return e.id; }
   616     static int id(Edge e) { return e.id; }
   617 
   617 
   618     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
   618     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
   619     static Arc arcFromId(int id) { return Arc(id);}
   619     static Arc arcFromId(int id) { return Arc(id);}
   620     static Edge edgeFromId(int id) { return Edge(id);}
   620     static Edge edgeFromId(int id) { return Edge(id);}
   621 
   621 
   622     int maxNodeId() const { return graph->maxNodeId(); };
   622     int maxNodeId() const { return _graph->maxNodeId(); };
   623     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   623     int maxEdgeId() const { return arcs.size() / 2 - 1; }
   624     int maxArcId() const { return arcs.size()-1; }
   624     int maxArcId() const { return arcs.size()-1; }
   625 
   625 
   626     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
   626     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
   627     Node target(Arc e) const { return arcs[e.id].target; }
   627     Node target(Arc e) const { return arcs[e.id].target; }
   628 
   628 
   629     Node u(Edge e) const { return arcs[2 * e.id].target; }
   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; }
   630     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
   631 
   631 
   632     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   632     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   633 
   633 
   634     NodeNotifier& notifier(Node) const {
   634     NodeNotifier& notifier(Node) const {
   635       return graph->notifier(Node());
   635       return _graph->notifier(Node());
   636     }
   636     }
   637 
   637 
   638     template <typename _Value>
   638     template <typename V>
   639     class NodeMap : public Graph::template NodeMap<_Value> {
   639     class NodeMap : public GR::template NodeMap<V> {
   640     public:
   640     public:
   641 
   641 
   642       typedef typename _Graph::template NodeMap<_Value> Parent;
   642       typedef typename GR::template NodeMap<V> Parent;
   643 
   643 
   644       explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
   644       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
   645         : Parent(*arcset.graph) {}
   645         : Parent(*arcset._graph) {}
   646 
   646 
   647       NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
   647       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
   648         : Parent(*arcset.graph, value) {}
   648         : Parent(*arcset._graph, value) {}
   649 
   649 
   650       NodeMap& operator=(const NodeMap& cmap) {
   650       NodeMap& operator=(const NodeMap& cmap) {
   651         return operator=<NodeMap>(cmap);
   651         return operator=<NodeMap>(cmap);
   652       }
   652       }
   653 
   653 
   677   /// node the incident edges make up lists, therefore one edge can be
   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
   678   /// erased in constant time. It also makes possible, that node can
   679   /// be removed from the underlying graph, in this case all edges
   679   /// be removed from the underlying graph, in this case all edges
   680   /// incident to the given node is erased from the arc set.
   680   /// incident to the given node is erased from the arc set.
   681   ///
   681   ///
   682   /// \param _Graph The type of the graph which shares its node set
   682   /// \param GR The type of the graph which shares its node set
   683   /// with this class. Its interface must conform to the
   683   /// with this class. Its interface must conform to the
   684   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   684   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   685   /// concept.
   685   /// concept.
   686   ///
   686   ///
   687   /// This class is fully conform to the \ref concepts::Graph "Graph"
   687   /// This class is fully conform to the \ref concepts::Graph "Graph"
   688   /// concept.
   688   /// concept.
   689   template <typename _Graph>
   689   template <typename GR>
   690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
   690   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
   691 
   691 
   692   public:
   692   public:
   693 
   693 
   694     typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
   694     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
   695 
   695 
   696     typedef typename Parent::Node Node;
   696     typedef typename Parent::Node Node;
   697     typedef typename Parent::Arc Arc;
   697     typedef typename Parent::Arc Arc;
   698     typedef typename Parent::Edge Edge;
   698     typedef typename Parent::Edge Edge;
   699 
   699 
   700     typedef _Graph Graph;
   700     typedef GR Graph;
   701 
   701 
   702 
   702 
   703     typedef typename Parent::NodesImplBase NodesImplBase;
   703     typedef typename Parent::NodesImplBase NodesImplBase;
   704 
   704 
   705     void eraseNode(const Node& node) {
   705     void eraseNode(const Node& node) {
   718 
   718 
   719     class NodesImpl : public NodesImplBase {
   719     class NodesImpl : public NodesImplBase {
   720     public:
   720     public:
   721       typedef NodesImplBase Parent;
   721       typedef NodesImplBase Parent;
   722 
   722 
   723       NodesImpl(const Graph& graph, ListEdgeSet& arcset)
   723       NodesImpl(const GR& graph, ListEdgeSet& arcset)
   724         : Parent(graph), _arcset(arcset) {}
   724         : Parent(graph), _arcset(arcset) {}
   725 
   725 
   726       virtual ~NodesImpl() {}
   726       virtual ~NodesImpl() {}
   727 
   727 
   728     protected:
   728     protected:
   744 
   744 
   745     private:
   745     private:
   746       ListEdgeSet& _arcset;
   746       ListEdgeSet& _arcset;
   747     };
   747     };
   748 
   748 
   749     NodesImpl nodes;
   749     NodesImpl _nodes;
   750 
   750 
   751   public:
   751   public:
   752 
   752 
   753     /// \brief Constructor of the EdgeSet.
   753     /// \brief Constructor of the EdgeSet.
   754     ///
   754     ///
   755     /// Constructor of the EdgeSet.
   755     /// Constructor of the EdgeSet.
   756     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
   756     ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
   757       Parent::initalize(graph, nodes);
   757       Parent::initalize(graph, _nodes);
   758     }
   758     }
   759 
   759 
   760     /// \brief Add a new edge to the graph.
   760     /// \brief Add a new edge to the graph.
   761     ///
   761     ///
   762     /// Add a new edge to the graph with node \c u
   762     /// Add a new edge to the graph with node \c u
   773       return Parent::erase(e);
   773       return Parent::erase(e);
   774     }
   774     }
   775 
   775 
   776   };
   776   };
   777 
   777 
   778   template <typename _Graph>
   778   template <typename GR>
   779   class SmartArcSetBase {
   779   class SmartArcSetBase {
   780   public:
   780   public:
   781 
   781 
   782     typedef _Graph Graph;
   782     typedef GR Graph;
   783     typedef typename Graph::Node Node;
   783     typedef typename Graph::Node Node;
   784     typedef typename Graph::NodeIt NodeIt;
   784     typedef typename Graph::NodeIt NodeIt;
   785 
   785 
   786   protected:
   786   protected:
   787 
   787 
   788     struct NodeT {
   788     struct NodeT {
   789       int first_out, first_in;
   789       int first_out, first_in;
   790       NodeT() : first_out(-1), first_in(-1) {}
   790       NodeT() : first_out(-1), first_in(-1) {}
   791     };
   791     };
   792 
   792 
   793     typedef typename ItemSetTraits<Graph, Node>::
   793     typedef typename ItemSetTraits<GR, Node>::
   794     template Map<NodeT>::Type NodesImplBase;
   794     template Map<NodeT>::Type NodesImplBase;
   795 
   795 
   796     NodesImplBase* nodes;
   796     NodesImplBase* _nodes;
   797 
   797 
   798     struct ArcT {
   798     struct ArcT {
   799       Node source, target;
   799       Node source, target;
   800       int next_out, next_in;
   800       int next_out, next_in;
   801       ArcT() {}
   801       ArcT() {}
   802     };
   802     };
   803 
   803 
   804     std::vector<ArcT> arcs;
   804     std::vector<ArcT> arcs;
   805 
   805 
   806     const Graph* graph;
   806     const GR* _graph;
   807 
   807 
   808     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
   808     void initalize(const GR& graph, NodesImplBase& nodes) {
   809       graph = &_graph;
   809       _graph = &graph;
   810       nodes = &_nodes;
   810       _nodes = &nodes;
   811     }
   811     }
   812 
   812 
   813   public:
   813   public:
   814 
   814 
   815     class Arc {
   815     class Arc {
   816       friend class SmartArcSetBase<Graph>;
   816       friend class SmartArcSetBase<GR>;
   817     protected:
   817     protected:
   818       Arc(int _id) : id(_id) {}
   818       Arc(int _id) : id(_id) {}
   819       int id;
   819       int id;
   820     public:
   820     public:
   821       Arc() {}
   821       Arc() {}
   828     SmartArcSetBase() {}
   828     SmartArcSetBase() {}
   829 
   829 
   830     Arc addArc(const Node& u, const Node& v) {
   830     Arc addArc(const Node& u, const Node& v) {
   831       int n = arcs.size();
   831       int n = arcs.size();
   832       arcs.push_back(ArcT());
   832       arcs.push_back(ArcT());
   833       arcs[n].next_in = (*nodes)[v].first_in;
   833       arcs[n].next_in = (*_nodes)[v].first_in;
   834       (*nodes)[v].first_in = n;
   834       (*_nodes)[v].first_in = n;
   835       arcs[n].next_out = (*nodes)[u].first_out;
   835       arcs[n].next_out = (*_nodes)[u].first_out;
   836       (*nodes)[u].first_out = n;
   836       (*_nodes)[u].first_out = n;
   837       arcs[n].source = u;
   837       arcs[n].source = u;
   838       arcs[n].target = v;
   838       arcs[n].target = v;
   839       return Arc(n);
   839       return Arc(n);
   840     }
   840     }
   841 
   841 
   842     void clear() {
   842     void clear() {
   843       Node node;
   843       Node node;
   844       for (first(node); node != INVALID; next(node)) {
   844       for (first(node); node != INVALID; next(node)) {
   845         (*nodes)[node].first_in = -1;
   845         (*_nodes)[node].first_in = -1;
   846         (*nodes)[node].first_out = -1;
   846         (*_nodes)[node].first_out = -1;
   847       }
   847       }
   848       arcs.clear();
   848       arcs.clear();
   849     }
   849     }
   850 
   850 
   851     void first(Node& node) const {
   851     void first(Node& node) const {
   852       graph->first(node);
   852       _graph->first(node);
   853     }
   853     }
   854 
   854 
   855     void next(Node& node) const {
   855     void next(Node& node) const {
   856       graph->next(node);
   856       _graph->next(node);
   857     }
   857     }
   858 
   858 
   859     void first(Arc& arc) const {
   859     void first(Arc& arc) const {
   860       arc.id = arcs.size() - 1;
   860       arc.id = arcs.size() - 1;
   861     }
   861     }
   863     void next(Arc& arc) const {
   863     void next(Arc& arc) const {
   864       --arc.id;
   864       --arc.id;
   865     }
   865     }
   866 
   866 
   867     void firstOut(Arc& arc, const Node& node) const {
   867     void firstOut(Arc& arc, const Node& node) const {
   868       arc.id = (*nodes)[node].first_out;
   868       arc.id = (*_nodes)[node].first_out;
   869     }
   869     }
   870 
   870 
   871     void nextOut(Arc& arc) const {
   871     void nextOut(Arc& arc) const {
   872       arc.id = arcs[arc.id].next_out;
   872       arc.id = arcs[arc.id].next_out;
   873     }
   873     }
   874 
   874 
   875     void firstIn(Arc& arc, const Node& node) const {
   875     void firstIn(Arc& arc, const Node& node) const {
   876       arc.id = (*nodes)[node].first_in;
   876       arc.id = (*_nodes)[node].first_in;
   877     }
   877     }
   878 
   878 
   879     void nextIn(Arc& arc) const {
   879     void nextIn(Arc& arc) const {
   880       arc.id = arcs[arc.id].next_in;
   880       arc.id = arcs[arc.id].next_in;
   881     }
   881     }
   882 
   882 
   883     int id(const Node& node) const { return graph->id(node); }
   883     int id(const Node& node) const { return _graph->id(node); }
   884     int id(const Arc& arc) const { return arc.id; }
   884     int id(const Arc& arc) const { return arc.id; }
   885 
   885 
   886     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
   886     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
   887     Arc arcFromId(int ix) const { return Arc(ix); }
   887     Arc arcFromId(int ix) const { return Arc(ix); }
   888 
   888 
   889     int maxNodeId() const { return graph->maxNodeId(); };
   889     int maxNodeId() const { return _graph->maxNodeId(); };
   890     int maxArcId() const { return arcs.size() - 1; }
   890     int maxArcId() const { return arcs.size() - 1; }
   891 
   891 
   892     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   892     Node source(const Arc& arc) const { return arcs[arc.id].source;}
   893     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   893     Node target(const Arc& arc) const { return arcs[arc.id].target;}
   894 
   894 
   895     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
   895     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
   896 
   896 
   897     NodeNotifier& notifier(Node) const {
   897     NodeNotifier& notifier(Node) const {
   898       return graph->notifier(Node());
   898       return _graph->notifier(Node());
   899     }
   899     }
   900 
   900 
   901     template <typename _Value>
   901     template <typename V>
   902     class NodeMap : public Graph::template NodeMap<_Value> {
   902     class NodeMap : public GR::template NodeMap<V> {
   903     public:
   903     public:
   904 
   904 
   905       typedef typename _Graph::template NodeMap<_Value> Parent;
   905       typedef typename GR::template NodeMap<V> Parent;
   906 
   906 
   907       explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
   907       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
   908         : Parent(*arcset.graph) { }
   908         : Parent(*arcset._graph) { }
   909 
   909 
   910       NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
   910       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
   911         : Parent(*arcset.graph, value) { }
   911         : Parent(*arcset._graph, value) { }
   912 
   912 
   913       NodeMap& operator=(const NodeMap& cmap) {
   913       NodeMap& operator=(const NodeMap& cmap) {
   914         return operator=<NodeMap>(cmap);
   914         return operator=<NodeMap>(cmap);
   915       }
   915       }
   916 
   916 
   935   /// original graph is valid in this arc set, therefore the node
   935   /// original graph is valid in this arc set, therefore the node
   936   /// objects of the original graph can be used directly with this
   936   /// objects of the original graph can be used directly with this
   937   /// class. The node handling functions (id handling, observing, and
   937   /// class. The node handling functions (id handling, observing, and
   938   /// iterators) works equivalently as in the original graph.
   938   /// iterators) works equivalently as in the original graph.
   939   ///
   939   ///
   940   /// \param _Graph The type of the graph which shares its node set with
   940   /// \param GR The type of the graph which shares its node set with
   941   /// this class. Its interface must conform to the
   941   /// this class. Its interface must conform to the
   942   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   942   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
   943   /// concept.
   943   /// concept.
   944   ///
   944   ///
   945   /// This implementation is slightly faster than the \c ListArcSet,
   945   /// This implementation is slightly faster than the \c ListArcSet,
   952   /// the arc set is invalidated, and it cannot be used anymore. The
   952   /// the arc set is invalidated, and it cannot be used anymore. The
   953   /// validity can be checked with the \c valid() member function.
   953   /// validity can be checked with the \c valid() member function.
   954   ///
   954   ///
   955   /// This class is fully conform to the \ref concepts::Digraph
   955   /// This class is fully conform to the \ref concepts::Digraph
   956   /// "Digraph" concept.
   956   /// "Digraph" concept.
   957   template <typename _Graph>
   957   template <typename GR>
   958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
   958   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
   959 
   959 
   960   public:
   960   public:
   961 
   961 
   962     typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
   962     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
   963 
   963 
   964     typedef typename Parent::Node Node;
   964     typedef typename Parent::Node Node;
   965     typedef typename Parent::Arc Arc;
   965     typedef typename Parent::Arc Arc;
   966 
   966 
   967     typedef _Graph Graph;
   967     typedef GR Graph;
   968 
   968 
   969   protected:
   969   protected:
   970 
   970 
   971     typedef typename Parent::NodesImplBase NodesImplBase;
   971     typedef typename Parent::NodesImplBase NodesImplBase;
   972 
   972 
   984 
   984 
   985     class NodesImpl : public NodesImplBase {
   985     class NodesImpl : public NodesImplBase {
   986     public:
   986     public:
   987       typedef NodesImplBase Parent;
   987       typedef NodesImplBase Parent;
   988 
   988 
   989       NodesImpl(const Graph& graph, SmartArcSet& arcset)
   989       NodesImpl(const GR& graph, SmartArcSet& arcset)
   990         : Parent(graph), _arcset(arcset) {}
   990         : Parent(graph), _arcset(arcset) {}
   991 
   991 
   992       virtual ~NodesImpl() {}
   992       virtual ~NodesImpl() {}
   993 
   993 
   994       bool attached() const {
   994       bool attached() const {
  1024 
  1024 
  1025     private:
  1025     private:
  1026       SmartArcSet& _arcset;
  1026       SmartArcSet& _arcset;
  1027     };
  1027     };
  1028 
  1028 
  1029     NodesImpl nodes;
  1029     NodesImpl _nodes;
  1030 
  1030 
  1031   public:
  1031   public:
  1032 
  1032 
  1033     /// \brief Constructor of the ArcSet.
  1033     /// \brief Constructor of the ArcSet.
  1034     ///
  1034     ///
  1035     /// Constructor of the ArcSet.
  1035     /// Constructor of the ArcSet.
  1036     SmartArcSet(const Graph& graph) : nodes(graph, *this) {
  1036     SmartArcSet(const GR& graph) : _nodes(graph, *this) {
  1037       Parent::initalize(graph, nodes);
  1037       Parent::initalize(graph, _nodes);
  1038     }
  1038     }
  1039 
  1039 
  1040     /// \brief Add a new arc to the digraph.
  1040     /// \brief Add a new arc to the digraph.
  1041     ///
  1041     ///
  1042     /// Add a new arc to the digraph with source node \c s
  1042     /// Add a new arc to the digraph with source node \c s
  1050     ///
  1050     ///
  1051     /// This functions gives back false if the ArcSet is
  1051     /// This functions gives back false if the ArcSet is
  1052     /// invalidated. It occurs when a node in the underlying graph is
  1052     /// invalidated. It occurs when a node in the underlying graph is
  1053     /// erased and it is not isolated in the ArcSet.
  1053     /// erased and it is not isolated in the ArcSet.
  1054     bool valid() const {
  1054     bool valid() const {
  1055       return nodes.attached();
  1055       return _nodes.attached();
  1056     }
  1056     }
  1057 
  1057 
  1058   };
  1058   };
  1059 
  1059 
  1060 
  1060 
  1061   template <typename _Graph>
  1061   template <typename GR>
  1062   class SmartEdgeSetBase {
  1062   class SmartEdgeSetBase {
  1063   public:
  1063   public:
  1064 
  1064 
  1065     typedef _Graph Graph;
  1065     typedef GR Graph;
  1066     typedef typename Graph::Node Node;
  1066     typedef typename GR::Node Node;
  1067     typedef typename Graph::NodeIt NodeIt;
  1067     typedef typename GR::NodeIt NodeIt;
  1068 
  1068 
  1069   protected:
  1069   protected:
  1070 
  1070 
  1071     struct NodeT {
  1071     struct NodeT {
  1072       int first_out;
  1072       int first_out;
  1073       NodeT() : first_out(-1) {}
  1073       NodeT() : first_out(-1) {}
  1074     };
  1074     };
  1075 
  1075 
  1076     typedef typename ItemSetTraits<Graph, Node>::
  1076     typedef typename ItemSetTraits<GR, Node>::
  1077     template Map<NodeT>::Type NodesImplBase;
  1077     template Map<NodeT>::Type NodesImplBase;
  1078 
  1078 
  1079     NodesImplBase* nodes;
  1079     NodesImplBase* _nodes;
  1080 
  1080 
  1081     struct ArcT {
  1081     struct ArcT {
  1082       Node target;
  1082       Node target;
  1083       int next_out;
  1083       int next_out;
  1084       ArcT() {}
  1084       ArcT() {}
  1085     };
  1085     };
  1086 
  1086 
  1087     std::vector<ArcT> arcs;
  1087     std::vector<ArcT> arcs;
  1088 
  1088 
  1089     const Graph* graph;
  1089     const GR* _graph;
  1090 
  1090 
  1091     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
  1091     void initalize(const GR& graph, NodesImplBase& nodes) {
  1092       graph = &_graph;
  1092       _graph = &graph;
  1093       nodes = &_nodes;
  1093       _nodes = &nodes;
  1094     }
  1094     }
  1095 
  1095 
  1096   public:
  1096   public:
  1097 
  1097 
  1098     class Edge {
  1098     class Edge {
  1133       arcs.push_back(ArcT());
  1133       arcs.push_back(ArcT());
  1134 
  1134 
  1135       arcs[n].target = u;
  1135       arcs[n].target = u;
  1136       arcs[n | 1].target = v;
  1136       arcs[n | 1].target = v;
  1137 
  1137 
  1138       arcs[n].next_out = (*nodes)[v].first_out;
  1138       arcs[n].next_out = (*_nodes)[v].first_out;
  1139       (*nodes)[v].first_out = n;
  1139       (*_nodes)[v].first_out = n;
  1140 
  1140 
  1141       arcs[n | 1].next_out = (*nodes)[u].first_out;
  1141       arcs[n | 1].next_out = (*_nodes)[u].first_out;
  1142       (*nodes)[u].first_out = (n | 1);
  1142       (*_nodes)[u].first_out = (n | 1);
  1143 
  1143 
  1144       return Edge(n / 2);
  1144       return Edge(n / 2);
  1145     }
  1145     }
  1146 
  1146 
  1147     void clear() {
  1147     void clear() {
  1148       Node node;
  1148       Node node;
  1149       for (first(node); node != INVALID; next(node)) {
  1149       for (first(node); node != INVALID; next(node)) {
  1150         (*nodes)[node].first_out = -1;
  1150         (*_nodes)[node].first_out = -1;
  1151       }
  1151       }
  1152       arcs.clear();
  1152       arcs.clear();
  1153     }
  1153     }
  1154 
  1154 
  1155     void first(Node& node) const {
  1155     void first(Node& node) const {
  1156       graph->first(node);
  1156       _graph->first(node);
  1157     }
  1157     }
  1158 
  1158 
  1159     void next(Node& node) const {
  1159     void next(Node& node) const {
  1160       graph->next(node);
  1160       _graph->next(node);
  1161     }
  1161     }
  1162 
  1162 
  1163     void first(Arc& arc) const {
  1163     void first(Arc& arc) const {
  1164       arc.id = arcs.size() - 1;
  1164       arc.id = arcs.size() - 1;
  1165     }
  1165     }
  1175     void next(Edge& arc) const {
  1175     void next(Edge& arc) const {
  1176       --arc.id;
  1176       --arc.id;
  1177     }
  1177     }
  1178 
  1178 
  1179     void firstOut(Arc& arc, const Node& node) const {
  1179     void firstOut(Arc& arc, const Node& node) const {
  1180       arc.id = (*nodes)[node].first_out;
  1180       arc.id = (*_nodes)[node].first_out;
  1181     }
  1181     }
  1182 
  1182 
  1183     void nextOut(Arc& arc) const {
  1183     void nextOut(Arc& arc) const {
  1184       arc.id = arcs[arc.id].next_out;
  1184       arc.id = arcs[arc.id].next_out;
  1185     }
  1185     }
  1186 
  1186 
  1187     void firstIn(Arc& arc, const Node& node) const {
  1187     void firstIn(Arc& arc, const Node& node) const {
  1188       arc.id = (((*nodes)[node].first_out) ^ 1);
  1188       arc.id = (((*_nodes)[node].first_out) ^ 1);
  1189       if (arc.id == -2) arc.id = -1;
  1189       if (arc.id == -2) arc.id = -1;
  1190     }
  1190     }
  1191 
  1191 
  1192     void nextIn(Arc& arc) const {
  1192     void nextIn(Arc& arc) const {
  1193       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
  1193       arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1);
  1194       if (arc.id == -2) arc.id = -1;
  1194       if (arc.id == -2) arc.id = -1;
  1195     }
  1195     }
  1196 
  1196 
  1197     void firstInc(Edge &arc, bool& dir, const Node& node) const {
  1197     void firstInc(Edge &arc, bool& dir, const Node& node) const {
  1198       int de = (*nodes)[node].first_out;
  1198       int de = (*_nodes)[node].first_out;
  1199       if (de != -1 ) {
  1199       if (de != -1 ) {
  1200         arc.id = de / 2;
  1200         arc.id = de / 2;
  1201         dir = ((de & 1) == 1);
  1201         dir = ((de & 1) == 1);
  1202       } else {
  1202       } else {
  1203         arc.id = -1;
  1203         arc.id = -1;
  1221 
  1221 
  1222     static Arc direct(Edge edge, bool dir) {
  1222     static Arc direct(Edge edge, bool dir) {
  1223       return Arc(edge.id * 2 + (dir ? 1 : 0));
  1223       return Arc(edge.id * 2 + (dir ? 1 : 0));
  1224     }
  1224     }
  1225 
  1225 
  1226     int id(Node node) const { return graph->id(node); }
  1226     int id(Node node) const { return _graph->id(node); }
  1227     static int id(Arc arc) { return arc.id; }
  1227     static int id(Arc arc) { return arc.id; }
  1228     static int id(Edge arc) { return arc.id; }
  1228     static int id(Edge arc) { return arc.id; }
  1229 
  1229 
  1230     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
  1230     Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
  1231     static Arc arcFromId(int id) { return Arc(id); }
  1231     static Arc arcFromId(int id) { return Arc(id); }
  1232     static Edge edgeFromId(int id) { return Edge(id);}
  1232     static Edge edgeFromId(int id) { return Edge(id);}
  1233 
  1233 
  1234     int maxNodeId() const { return graph->maxNodeId(); };
  1234     int maxNodeId() const { return _graph->maxNodeId(); };
  1235     int maxArcId() const { return arcs.size() - 1; }
  1235     int maxArcId() const { return arcs.size() - 1; }
  1236     int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1236     int maxEdgeId() const { return arcs.size() / 2 - 1; }
  1237 
  1237 
  1238     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
  1238     Node source(Arc e) const { return arcs[e.id ^ 1].target; }
  1239     Node target(Arc e) const { return arcs[e.id].target; }
  1239     Node target(Arc e) const { return arcs[e.id].target; }
  1240 
  1240 
  1241     Node u(Edge e) const { return arcs[2 * e.id].target; }
  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; }
  1242     Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
  1243 
  1243 
  1244     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
  1244     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
  1245 
  1245 
  1246     NodeNotifier& notifier(Node) const {
  1246     NodeNotifier& notifier(Node) const {
  1247       return graph->notifier(Node());
  1247       return _graph->notifier(Node());
  1248     }
  1248     }
  1249 
  1249 
  1250     template <typename _Value>
  1250     template <typename V>
  1251     class NodeMap : public Graph::template NodeMap<_Value> {
  1251     class NodeMap : public GR::template NodeMap<V> {
  1252     public:
  1252     public:
  1253 
  1253 
  1254       typedef typename _Graph::template NodeMap<_Value> Parent;
  1254       typedef typename GR::template NodeMap<V> Parent;
  1255 
  1255 
  1256       explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
  1256       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
  1257         : Parent(*arcset.graph) { }
  1257         : Parent(*arcset._graph) { }
  1258 
  1258 
  1259       NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
  1259       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
  1260         : Parent(*arcset.graph, value) { }
  1260         : Parent(*arcset._graph, value) { }
  1261 
  1261 
  1262       NodeMap& operator=(const NodeMap& cmap) {
  1262       NodeMap& operator=(const NodeMap& cmap) {
  1263         return operator=<NodeMap>(cmap);
  1263         return operator=<NodeMap>(cmap);
  1264       }
  1264       }
  1265 
  1265 
  1283   /// graph is valid in this arc set, therefore the node objects of
  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
  1284   /// the original graph can be used directly with this class. The
  1285   /// node handling functions (id handling, observing, and iterators)
  1285   /// node handling functions (id handling, observing, and iterators)
  1286   /// works equivalently as in the original graph.
  1286   /// works equivalently as in the original graph.
  1287   ///
  1287   ///
  1288   /// \param _Graph The type of the graph which shares its node set
  1288   /// \param GR The type of the graph which shares its node set
  1289   /// with this class. Its interface must conform to the
  1289   /// with this class. Its interface must conform to the
  1290   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
  1290   /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
  1291   ///  concept.
  1291   ///  concept.
  1292   ///
  1292   ///
  1293   /// This implementation is slightly faster than the \c ListEdgeSet,
  1293   /// This implementation is slightly faster than the \c ListEdgeSet,
  1300   /// is invalidated, and it cannot be used anymore. The validity can
  1300   /// is invalidated, and it cannot be used anymore. The validity can
  1301   /// be checked with the \c valid() member function.
  1301   /// be checked with the \c valid() member function.
  1302   ///
  1302   ///
  1303   /// This class is fully conform to the \ref concepts::Graph
  1303   /// This class is fully conform to the \ref concepts::Graph
  1304   /// "Graph" concept.
  1304   /// "Graph" concept.
  1305   template <typename _Graph>
  1305   template <typename GR>
  1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
  1306   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
  1307 
  1307 
  1308   public:
  1308   public:
  1309 
  1309 
  1310     typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
  1310     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
  1311 
  1311 
  1312     typedef typename Parent::Node Node;
  1312     typedef typename Parent::Node Node;
  1313     typedef typename Parent::Arc Arc;
  1313     typedef typename Parent::Arc Arc;
  1314     typedef typename Parent::Edge Edge;
  1314     typedef typename Parent::Edge Edge;
  1315 
  1315 
  1316     typedef _Graph Graph;
  1316     typedef GR Graph;
  1317 
  1317 
  1318   protected:
  1318   protected:
  1319 
  1319 
  1320     typedef typename Parent::NodesImplBase NodesImplBase;
  1320     typedef typename Parent::NodesImplBase NodesImplBase;
  1321 
  1321 
  1332 
  1332 
  1333     class NodesImpl : public NodesImplBase {
  1333     class NodesImpl : public NodesImplBase {
  1334     public:
  1334     public:
  1335       typedef NodesImplBase Parent;
  1335       typedef NodesImplBase Parent;
  1336 
  1336 
  1337       NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
  1337       NodesImpl(const GR& graph, SmartEdgeSet& arcset)
  1338         : Parent(graph), _arcset(arcset) {}
  1338         : Parent(graph), _arcset(arcset) {}
  1339 
  1339 
  1340       virtual ~NodesImpl() {}
  1340       virtual ~NodesImpl() {}
  1341 
  1341 
  1342       bool attached() const {
  1342       bool attached() const {
  1372 
  1372 
  1373     private:
  1373     private:
  1374       SmartEdgeSet& _arcset;
  1374       SmartEdgeSet& _arcset;
  1375     };
  1375     };
  1376 
  1376 
  1377     NodesImpl nodes;
  1377     NodesImpl _nodes;
  1378 
  1378 
  1379   public:
  1379   public:
  1380 
  1380 
  1381     /// \brief Constructor of the EdgeSet.
  1381     /// \brief Constructor of the EdgeSet.
  1382     ///
  1382     ///
  1383     /// Constructor of the EdgeSet.
  1383     /// Constructor of the EdgeSet.
  1384     SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
  1384     SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
  1385       Parent::initalize(graph, nodes);
  1385       Parent::initalize(graph, _nodes);
  1386     }
  1386     }
  1387 
  1387 
  1388     /// \brief Add a new edge to the graph.
  1388     /// \brief Add a new edge to the graph.
  1389     ///
  1389     ///
  1390     /// Add a new edge to the graph with node \c u
  1390     /// Add a new edge to the graph with node \c u
  1398     ///
  1398     ///
  1399     /// This functions gives back false if the EdgeSet is
  1399     /// This functions gives back false if the EdgeSet is
  1400     /// invalidated. It occurs when a node in the underlying graph is
  1400     /// invalidated. It occurs when a node in the underlying graph is
  1401     /// erased and it is not isolated in the EdgeSet.
  1401     /// erased and it is not isolated in the EdgeSet.
  1402     bool valid() const {
  1402     bool valid() const {
  1403       return nodes.attached();
  1403       return _nodes.attached();
  1404     }
  1404     }
  1405 
  1405 
  1406   };
  1406   };
  1407 
  1407 
  1408 }
  1408 }