lemon/bits/graph_extender.h
changeset 87 81e138275860
child 77 2de55e4f57a7
equal deleted inserted replaced
-1:000000000000 0:36c4bf2bb527
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2007
       
     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_BITS_GRAPH_EXTENDER_H
       
    20 #define LEMON_BITS_GRAPH_EXTENDER_H
       
    21 
       
    22 #include <lemon/bits/invalid.h>
       
    23 
       
    24 #include <lemon/bits/map_extender.h>
       
    25 #include <lemon/bits/default_map.h>
       
    26 
       
    27 #include <lemon/concept_check.h>
       
    28 #include <lemon/concepts/maps.h>
       
    29 
       
    30 ///\ingroup graphbits
       
    31 ///\file
       
    32 ///\brief Extenders for the digraph types
       
    33 namespace lemon {
       
    34 
       
    35   /// \ingroup graphbits
       
    36   ///
       
    37   /// \brief Extender for the Digraphs
       
    38   template <typename Base>
       
    39   class DigraphExtender : public Base {
       
    40   public:
       
    41 
       
    42     typedef Base Parent;
       
    43     typedef DigraphExtender Digraph;
       
    44 
       
    45     // Base extensions
       
    46 
       
    47     typedef typename Parent::Node Node;
       
    48     typedef typename Parent::Arc Arc;
       
    49 
       
    50     int maxId(Node) const {
       
    51       return Parent::maxNodeId();
       
    52     }
       
    53 
       
    54     int maxId(Arc) const {
       
    55       return Parent::maxArcId();
       
    56     }
       
    57 
       
    58     Node fromId(int id, Node) const {
       
    59       return Parent::nodeFromId(id);
       
    60     }
       
    61 
       
    62     Arc fromId(int id, Arc) const {
       
    63       return Parent::arcFromId(id);
       
    64     }
       
    65 
       
    66     Node oppositeNode(const Node &n, const Arc &e) const {
       
    67       if (n == Parent::source(e))
       
    68 	return Parent::target(e);
       
    69       else if(n==Parent::target(e))
       
    70 	return Parent::source(e);
       
    71       else
       
    72 	return INVALID;
       
    73     }
       
    74 
       
    75     // Alterable extension
       
    76 
       
    77     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
       
    78     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
       
    79 
       
    80 
       
    81   protected:
       
    82 
       
    83     mutable NodeNotifier node_notifier;
       
    84     mutable ArcNotifier arc_notifier;
       
    85 
       
    86   public:
       
    87 
       
    88     NodeNotifier& notifier(Node) const {
       
    89       return node_notifier;
       
    90     }
       
    91     
       
    92     ArcNotifier& notifier(Arc) const {
       
    93       return arc_notifier;
       
    94     }
       
    95 
       
    96     class NodeIt : public Node { 
       
    97       const Digraph* digraph;
       
    98     public:
       
    99 
       
   100       NodeIt() {}
       
   101 
       
   102       NodeIt(Invalid i) : Node(i) { }
       
   103 
       
   104       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
       
   105 	_digraph.first(static_cast<Node&>(*this));
       
   106       }
       
   107 
       
   108       NodeIt(const Digraph& _digraph, const Node& node) 
       
   109 	: Node(node), digraph(&_digraph) {}
       
   110 
       
   111       NodeIt& operator++() { 
       
   112 	digraph->next(*this);
       
   113 	return *this; 
       
   114       }
       
   115 
       
   116     };
       
   117 
       
   118 
       
   119     class ArcIt : public Arc { 
       
   120       const Digraph* digraph;
       
   121     public:
       
   122 
       
   123       ArcIt() { }
       
   124 
       
   125       ArcIt(Invalid i) : Arc(i) { }
       
   126 
       
   127       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
       
   128 	_digraph.first(static_cast<Arc&>(*this));
       
   129       }
       
   130 
       
   131       ArcIt(const Digraph& _digraph, const Arc& e) : 
       
   132 	Arc(e), digraph(&_digraph) { }
       
   133 
       
   134       ArcIt& operator++() { 
       
   135 	digraph->next(*this);
       
   136 	return *this; 
       
   137       }
       
   138 
       
   139     };
       
   140 
       
   141 
       
   142     class OutArcIt : public Arc { 
       
   143       const Digraph* digraph;
       
   144     public:
       
   145 
       
   146       OutArcIt() { }
       
   147 
       
   148       OutArcIt(Invalid i) : Arc(i) { }
       
   149 
       
   150       OutArcIt(const Digraph& _digraph, const Node& node) 
       
   151 	: digraph(&_digraph) {
       
   152 	_digraph.firstOut(*this, node);
       
   153       }
       
   154 
       
   155       OutArcIt(const Digraph& _digraph, const Arc& arc) 
       
   156 	: Arc(arc), digraph(&_digraph) {}
       
   157 
       
   158       OutArcIt& operator++() { 
       
   159 	digraph->nextOut(*this);
       
   160 	return *this; 
       
   161       }
       
   162 
       
   163     };
       
   164 
       
   165 
       
   166     class InArcIt : public Arc { 
       
   167       const Digraph* digraph;
       
   168     public:
       
   169 
       
   170       InArcIt() { }
       
   171 
       
   172       InArcIt(Invalid i) : Arc(i) { }
       
   173 
       
   174       InArcIt(const Digraph& _digraph, const Node& node) 
       
   175 	: digraph(&_digraph) {
       
   176 	_digraph.firstIn(*this, node);
       
   177       }
       
   178 
       
   179       InArcIt(const Digraph& _digraph, const Arc& arc) : 
       
   180 	Arc(arc), digraph(&_digraph) {}
       
   181 
       
   182       InArcIt& operator++() { 
       
   183 	digraph->nextIn(*this);
       
   184 	return *this; 
       
   185       }
       
   186 
       
   187     };
       
   188 
       
   189     /// \brief Base node of the iterator
       
   190     ///
       
   191     /// Returns the base node (i.e. the source in this case) of the iterator
       
   192     Node baseNode(const OutArcIt &e) const {
       
   193       return Parent::source(e);
       
   194     }
       
   195     /// \brief Running node of the iterator
       
   196     ///
       
   197     /// Returns the running node (i.e. the target in this case) of the
       
   198     /// iterator
       
   199     Node runningNode(const OutArcIt &e) const {
       
   200       return Parent::target(e);
       
   201     }
       
   202 
       
   203     /// \brief Base node of the iterator
       
   204     ///
       
   205     /// Returns the base node (i.e. the target in this case) of the iterator
       
   206     Node baseNode(const InArcIt &e) const {
       
   207       return Parent::target(e);
       
   208     }
       
   209     /// \brief Running node of the iterator
       
   210     ///
       
   211     /// Returns the running node (i.e. the source in this case) of the
       
   212     /// iterator
       
   213     Node runningNode(const InArcIt &e) const {
       
   214       return Parent::source(e);
       
   215     }
       
   216 
       
   217     
       
   218     template <typename _Value>
       
   219     class NodeMap 
       
   220       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
       
   221     public:
       
   222       typedef DigraphExtender Digraph;
       
   223       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
       
   224 
       
   225       explicit NodeMap(const Digraph& digraph) 
       
   226 	: Parent(digraph) {}
       
   227       NodeMap(const Digraph& digraph, const _Value& value) 
       
   228 	: Parent(digraph, value) {}
       
   229 
       
   230       NodeMap& operator=(const NodeMap& cmap) {
       
   231 	return operator=<NodeMap>(cmap);
       
   232       }
       
   233 
       
   234       template <typename CMap>
       
   235       NodeMap& operator=(const CMap& cmap) {
       
   236         Parent::operator=(cmap);
       
   237 	return *this;
       
   238       }
       
   239 
       
   240     };
       
   241 
       
   242     template <typename _Value>
       
   243     class ArcMap 
       
   244       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
       
   245     public:
       
   246       typedef DigraphExtender Digraph;
       
   247       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
       
   248 
       
   249       explicit ArcMap(const Digraph& digraph) 
       
   250 	: Parent(digraph) {}
       
   251       ArcMap(const Digraph& digraph, const _Value& value) 
       
   252 	: Parent(digraph, value) {}
       
   253 
       
   254       ArcMap& operator=(const ArcMap& cmap) {
       
   255 	return operator=<ArcMap>(cmap);
       
   256       }
       
   257 
       
   258       template <typename CMap>
       
   259       ArcMap& operator=(const CMap& cmap) {
       
   260         Parent::operator=(cmap);
       
   261 	return *this;
       
   262       }
       
   263     };
       
   264 
       
   265 
       
   266     Node addNode() {
       
   267       Node node = Parent::addNode();
       
   268       notifier(Node()).add(node);
       
   269       return node;
       
   270     }
       
   271     
       
   272     Arc addArc(const Node& from, const Node& to) {
       
   273       Arc arc = Parent::addArc(from, to);
       
   274       notifier(Arc()).add(arc);
       
   275       return arc;
       
   276     }
       
   277 
       
   278     void clear() {
       
   279       notifier(Arc()).clear();
       
   280       notifier(Node()).clear();
       
   281       Parent::clear();
       
   282     }
       
   283 
       
   284     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
       
   285     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
       
   286       Parent::build(digraph, nodeRef, arcRef);
       
   287       notifier(Node()).build();
       
   288       notifier(Arc()).build();
       
   289     }
       
   290 
       
   291     void erase(const Node& node) {
       
   292       Arc arc;
       
   293       Parent::firstOut(arc, node);
       
   294       while (arc != INVALID ) {
       
   295 	erase(arc);
       
   296 	Parent::firstOut(arc, node);
       
   297       } 
       
   298 
       
   299       Parent::firstIn(arc, node);
       
   300       while (arc != INVALID ) {
       
   301 	erase(arc);
       
   302 	Parent::firstIn(arc, node);
       
   303       }
       
   304 
       
   305       notifier(Node()).erase(node);
       
   306       Parent::erase(node);
       
   307     }
       
   308     
       
   309     void erase(const Arc& arc) {
       
   310       notifier(Arc()).erase(arc);
       
   311       Parent::erase(arc);
       
   312     }
       
   313 
       
   314     DigraphExtender() {
       
   315       node_notifier.setContainer(*this);
       
   316       arc_notifier.setContainer(*this);
       
   317     } 
       
   318     
       
   319 
       
   320     ~DigraphExtender() {
       
   321       arc_notifier.clear();
       
   322       node_notifier.clear();
       
   323     }
       
   324   };
       
   325 
       
   326   /// \ingroup graphbits
       
   327   ///
       
   328   /// \brief Extender for the Graphs
       
   329   template <typename Base> 
       
   330   class GraphExtender : public Base {
       
   331   public:
       
   332     
       
   333     typedef Base Parent;
       
   334     typedef GraphExtender Digraph;
       
   335 
       
   336     typedef typename Parent::Node Node;
       
   337     typedef typename Parent::Arc Arc;
       
   338     typedef typename Parent::Edge Edge;
       
   339 
       
   340     // Graph extension    
       
   341 
       
   342     int maxId(Node) const {
       
   343       return Parent::maxNodeId();
       
   344     }
       
   345 
       
   346     int maxId(Arc) const {
       
   347       return Parent::maxArcId();
       
   348     }
       
   349 
       
   350     int maxId(Edge) const {
       
   351       return Parent::maxEdgeId();
       
   352     }
       
   353 
       
   354     Node fromId(int id, Node) const {
       
   355       return Parent::nodeFromId(id);
       
   356     }
       
   357 
       
   358     Arc fromId(int id, Arc) const {
       
   359       return Parent::arcFromId(id);
       
   360     }
       
   361 
       
   362     Edge fromId(int id, Edge) const {
       
   363       return Parent::edgeFromId(id);
       
   364     }
       
   365 
       
   366     Node oppositeNode(const Node &n, const Edge &e) const {
       
   367       if( n == Parent::source(e))
       
   368 	return Parent::target(e);
       
   369       else if( n == Parent::target(e))
       
   370 	return Parent::source(e);
       
   371       else
       
   372 	return INVALID;
       
   373     }
       
   374 
       
   375     Arc oppositeArc(const Arc &e) const {
       
   376       return Parent::direct(e, !Parent::direction(e));
       
   377     }
       
   378 
       
   379     using Parent::direct;
       
   380     Arc direct(const Edge &ue, const Node &s) const {
       
   381       return Parent::direct(ue, Parent::source(ue) == s);
       
   382     }
       
   383 
       
   384     // Alterable extension
       
   385 
       
   386     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
       
   387     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
       
   388     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
       
   389 
       
   390 
       
   391   protected:
       
   392 
       
   393     mutable NodeNotifier node_notifier;
       
   394     mutable ArcNotifier arc_notifier;
       
   395     mutable EdgeNotifier edge_notifier;
       
   396 
       
   397   public:
       
   398 
       
   399     NodeNotifier& notifier(Node) const {
       
   400       return node_notifier;
       
   401     }
       
   402     
       
   403     ArcNotifier& notifier(Arc) const {
       
   404       return arc_notifier;
       
   405     }
       
   406 
       
   407     EdgeNotifier& notifier(Edge) const {
       
   408       return edge_notifier;
       
   409     }
       
   410 
       
   411 
       
   412 
       
   413     class NodeIt : public Node { 
       
   414       const Digraph* digraph;
       
   415     public:
       
   416 
       
   417       NodeIt() {}
       
   418 
       
   419       NodeIt(Invalid i) : Node(i) { }
       
   420 
       
   421       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
       
   422 	_digraph.first(static_cast<Node&>(*this));
       
   423       }
       
   424 
       
   425       NodeIt(const Digraph& _digraph, const Node& node) 
       
   426 	: Node(node), digraph(&_digraph) {}
       
   427 
       
   428       NodeIt& operator++() { 
       
   429 	digraph->next(*this);
       
   430 	return *this; 
       
   431       }
       
   432 
       
   433     };
       
   434 
       
   435 
       
   436     class ArcIt : public Arc { 
       
   437       const Digraph* digraph;
       
   438     public:
       
   439 
       
   440       ArcIt() { }
       
   441 
       
   442       ArcIt(Invalid i) : Arc(i) { }
       
   443 
       
   444       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
       
   445 	_digraph.first(static_cast<Arc&>(*this));
       
   446       }
       
   447 
       
   448       ArcIt(const Digraph& _digraph, const Arc& e) : 
       
   449 	Arc(e), digraph(&_digraph) { }
       
   450 
       
   451       ArcIt& operator++() { 
       
   452 	digraph->next(*this);
       
   453 	return *this; 
       
   454       }
       
   455 
       
   456     };
       
   457 
       
   458 
       
   459     class OutArcIt : public Arc { 
       
   460       const Digraph* digraph;
       
   461     public:
       
   462 
       
   463       OutArcIt() { }
       
   464 
       
   465       OutArcIt(Invalid i) : Arc(i) { }
       
   466 
       
   467       OutArcIt(const Digraph& _digraph, const Node& node) 
       
   468 	: digraph(&_digraph) {
       
   469 	_digraph.firstOut(*this, node);
       
   470       }
       
   471 
       
   472       OutArcIt(const Digraph& _digraph, const Arc& arc) 
       
   473 	: Arc(arc), digraph(&_digraph) {}
       
   474 
       
   475       OutArcIt& operator++() { 
       
   476 	digraph->nextOut(*this);
       
   477 	return *this; 
       
   478       }
       
   479 
       
   480     };
       
   481 
       
   482 
       
   483     class InArcIt : public Arc { 
       
   484       const Digraph* digraph;
       
   485     public:
       
   486 
       
   487       InArcIt() { }
       
   488 
       
   489       InArcIt(Invalid i) : Arc(i) { }
       
   490 
       
   491       InArcIt(const Digraph& _digraph, const Node& node) 
       
   492 	: digraph(&_digraph) {
       
   493 	_digraph.firstIn(*this, node);
       
   494       }
       
   495 
       
   496       InArcIt(const Digraph& _digraph, const Arc& arc) : 
       
   497 	Arc(arc), digraph(&_digraph) {}
       
   498 
       
   499       InArcIt& operator++() { 
       
   500 	digraph->nextIn(*this);
       
   501 	return *this; 
       
   502       }
       
   503 
       
   504     };
       
   505 
       
   506 
       
   507     class EdgeIt : public Parent::Edge { 
       
   508       const Digraph* digraph;
       
   509     public:
       
   510 
       
   511       EdgeIt() { }
       
   512 
       
   513       EdgeIt(Invalid i) : Edge(i) { }
       
   514 
       
   515       explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
       
   516 	_digraph.first(static_cast<Edge&>(*this));
       
   517       }
       
   518 
       
   519       EdgeIt(const Digraph& _digraph, const Edge& e) : 
       
   520 	Edge(e), digraph(&_digraph) { }
       
   521 
       
   522       EdgeIt& operator++() { 
       
   523 	digraph->next(*this);
       
   524 	return *this; 
       
   525       }
       
   526 
       
   527     };
       
   528 
       
   529     class IncArcIt : public Parent::Edge {
       
   530       friend class GraphExtender;
       
   531       const Digraph* digraph;
       
   532       bool direction;
       
   533     public:
       
   534 
       
   535       IncArcIt() { }
       
   536 
       
   537       IncArcIt(Invalid i) : Edge(i), direction(false) { }
       
   538 
       
   539       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
       
   540 	_digraph.firstInc(*this, direction, n);
       
   541       }
       
   542 
       
   543       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
       
   544 	: digraph(&_digraph), Edge(ue) {
       
   545 	direction = (_digraph.source(ue) == n);
       
   546       }
       
   547 
       
   548       IncArcIt& operator++() {
       
   549 	digraph->nextInc(*this, direction);
       
   550 	return *this; 
       
   551       }
       
   552     };
       
   553 
       
   554     /// \brief Base node of the iterator
       
   555     ///
       
   556     /// Returns the base node (ie. the source in this case) of the iterator
       
   557     Node baseNode(const OutArcIt &e) const {
       
   558       return Parent::source(static_cast<const Arc&>(e));
       
   559     }
       
   560     /// \brief Running node of the iterator
       
   561     ///
       
   562     /// Returns the running node (ie. the target in this case) of the
       
   563     /// iterator
       
   564     Node runningNode(const OutArcIt &e) const {
       
   565       return Parent::target(static_cast<const Arc&>(e));
       
   566     }
       
   567 
       
   568     /// \brief Base node of the iterator
       
   569     ///
       
   570     /// Returns the base node (ie. the target in this case) of the iterator
       
   571     Node baseNode(const InArcIt &e) const {
       
   572       return Parent::target(static_cast<const Arc&>(e));
       
   573     }
       
   574     /// \brief Running node of the iterator
       
   575     ///
       
   576     /// Returns the running node (ie. the source in this case) of the
       
   577     /// iterator
       
   578     Node runningNode(const InArcIt &e) const {
       
   579       return Parent::source(static_cast<const Arc&>(e));
       
   580     }
       
   581 
       
   582     /// Base node of the iterator
       
   583     ///
       
   584     /// Returns the base node of the iterator
       
   585     Node baseNode(const IncArcIt &e) const {
       
   586       return e.direction ? source(e) : target(e);
       
   587     }
       
   588     /// Running node of the iterator
       
   589     ///
       
   590     /// Returns the running node of the iterator
       
   591     Node runningNode(const IncArcIt &e) const {
       
   592       return e.direction ? target(e) : source(e);
       
   593     }
       
   594 
       
   595     // Mappable extension
       
   596 
       
   597     template <typename _Value>
       
   598     class NodeMap 
       
   599       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
       
   600     public:
       
   601       typedef GraphExtender Digraph;
       
   602       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
       
   603 
       
   604       NodeMap(const Digraph& digraph) 
       
   605 	: Parent(digraph) {}
       
   606       NodeMap(const Digraph& digraph, const _Value& value) 
       
   607 	: Parent(digraph, value) {}
       
   608 
       
   609       NodeMap& operator=(const NodeMap& cmap) {
       
   610 	return operator=<NodeMap>(cmap);
       
   611       }
       
   612 
       
   613       template <typename CMap>
       
   614       NodeMap& operator=(const CMap& cmap) {
       
   615         Parent::operator=(cmap);
       
   616 	return *this;
       
   617       }
       
   618 
       
   619     };
       
   620 
       
   621     template <typename _Value>
       
   622     class ArcMap 
       
   623       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
       
   624     public:
       
   625       typedef GraphExtender Digraph;
       
   626       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
       
   627 
       
   628       ArcMap(const Digraph& digraph) 
       
   629 	: Parent(digraph) {}
       
   630       ArcMap(const Digraph& digraph, const _Value& value) 
       
   631 	: Parent(digraph, value) {}
       
   632 
       
   633       ArcMap& operator=(const ArcMap& cmap) {
       
   634 	return operator=<ArcMap>(cmap);
       
   635       }
       
   636 
       
   637       template <typename CMap>
       
   638       ArcMap& operator=(const CMap& cmap) {
       
   639         Parent::operator=(cmap);
       
   640 	return *this;
       
   641       }
       
   642     };
       
   643 
       
   644 
       
   645     template <typename _Value>
       
   646     class EdgeMap 
       
   647       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
       
   648     public:
       
   649       typedef GraphExtender Digraph;
       
   650       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
       
   651 
       
   652       EdgeMap(const Digraph& digraph) 
       
   653 	: Parent(digraph) {}
       
   654 
       
   655       EdgeMap(const Digraph& digraph, const _Value& value) 
       
   656 	: Parent(digraph, value) {}
       
   657 
       
   658       EdgeMap& operator=(const EdgeMap& cmap) {
       
   659 	return operator=<EdgeMap>(cmap);
       
   660       }
       
   661 
       
   662       template <typename CMap>
       
   663       EdgeMap& operator=(const CMap& cmap) {
       
   664         Parent::operator=(cmap);
       
   665 	return *this;
       
   666       }
       
   667 
       
   668     };
       
   669 
       
   670     // Alteration extension
       
   671 
       
   672     Node addNode() {
       
   673       Node node = Parent::addNode();
       
   674       notifier(Node()).add(node);
       
   675       return node;
       
   676     }
       
   677 
       
   678     Edge addEdge(const Node& from, const Node& to) {
       
   679       Edge edge = Parent::addEdge(from, to);
       
   680       notifier(Edge()).add(edge);
       
   681       std::vector<Arc> ev;
       
   682       ev.push_back(Parent::direct(edge, true));
       
   683       ev.push_back(Parent::direct(edge, false));      
       
   684       notifier(Arc()).add(ev);
       
   685       return edge;
       
   686     }
       
   687     
       
   688     void clear() {
       
   689       notifier(Arc()).clear();
       
   690       notifier(Edge()).clear();
       
   691       notifier(Node()).clear();
       
   692       Parent::clear();
       
   693     }
       
   694 
       
   695     template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
       
   696     void build(const Digraph& digraph, NodeRefMap& nodeRef, 
       
   697                EdgeRefMap& edgeRef) {
       
   698       Parent::build(digraph, nodeRef, edgeRef);
       
   699       notifier(Node()).build();
       
   700       notifier(Edge()).build();
       
   701       notifier(Arc()).build();
       
   702     }
       
   703 
       
   704     void erase(const Node& node) {
       
   705       Arc arc;
       
   706       Parent::firstOut(arc, node);
       
   707       while (arc != INVALID ) {
       
   708 	erase(arc);
       
   709 	Parent::firstOut(arc, node);
       
   710       } 
       
   711 
       
   712       Parent::firstIn(arc, node);
       
   713       while (arc != INVALID ) {
       
   714 	erase(arc);
       
   715 	Parent::firstIn(arc, node);
       
   716       }
       
   717 
       
   718       notifier(Node()).erase(node);
       
   719       Parent::erase(node);
       
   720     }
       
   721 
       
   722     void erase(const Edge& edge) {
       
   723       std::vector<Arc> ev;
       
   724       ev.push_back(Parent::direct(edge, true));
       
   725       ev.push_back(Parent::direct(edge, false));      
       
   726       notifier(Arc()).erase(ev);
       
   727       notifier(Edge()).erase(edge);
       
   728       Parent::erase(edge);
       
   729     }
       
   730 
       
   731     GraphExtender() {
       
   732       node_notifier.setContainer(*this); 
       
   733       arc_notifier.setContainer(*this);
       
   734       edge_notifier.setContainer(*this);
       
   735     } 
       
   736 
       
   737     ~GraphExtender() {
       
   738       edge_notifier.clear();
       
   739       arc_notifier.clear();
       
   740       node_notifier.clear(); 
       
   741     } 
       
   742 
       
   743   };
       
   744 
       
   745 }
       
   746 
       
   747 #endif