lemon/bits/graph_extender.h
author klao
Wed, 31 May 2006 16:48:31 +0000
changeset 2099 eb126f29038c
parent 2076 10681ee9d8ae
child 2102 eb73ab0e4c74
permissions -rw-r--r--
benchmark: radix_sort-bench was not compiled
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     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 #include <lemon/error.h>
    24 
    25 #include <lemon/bits/map_extender.h>
    26 #include <lemon/bits/default_map.h>
    27 
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concept/maps.h>
    30 
    31 ///\ingroup graphbits
    32 ///\file
    33 ///\brief Extenders for the graph types
    34 namespace lemon {
    35 
    36   /// \ingroup graphbits
    37   ///
    38   /// \brief Extender for the Graphs
    39   template <typename Base>
    40   class GraphExtender : public Base {
    41   public:
    42 
    43     typedef Base Parent;
    44     typedef GraphExtender Graph;
    45 
    46     // Base extensions
    47 
    48     typedef typename Parent::Node Node;
    49     typedef typename Parent::Edge Edge;
    50 
    51     int maxId(Node) const {
    52       return Parent::maxNodeId();
    53     }
    54 
    55     int maxId(Edge) const {
    56       return Parent::maxEdgeId();
    57     }
    58 
    59     Node fromId(int id, Node) const {
    60       return Parent::nodeFromId(id);
    61     }
    62 
    63     Edge fromId(int id, Edge) const {
    64       return Parent::edgeFromId(id);
    65     }
    66 
    67     Node oppositeNode(const Node &n, const Edge &e) const {
    68       if (n == Parent::source(e))
    69 	return Parent::target(e);
    70       else if(n==Parent::target(e))
    71 	return Parent::source(e);
    72       else
    73 	return INVALID;
    74     }
    75 
    76     // Alterable extension
    77 
    78     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
    79     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
    80 
    81 
    82   protected:
    83 
    84     mutable NodeNotifier node_notifier;
    85     mutable EdgeNotifier edge_notifier;
    86 
    87   public:
    88 
    89     NodeNotifier& getNotifier(Node) const {
    90       return node_notifier;
    91     }
    92     
    93     EdgeNotifier& getNotifier(Edge) const {
    94       return edge_notifier;
    95     }
    96 
    97     class NodeIt : public Node { 
    98       const Graph* graph;
    99     public:
   100 
   101       NodeIt() {}
   102 
   103       NodeIt(Invalid i) : Node(i) { }
   104 
   105       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
   106 	_graph.first(static_cast<Node&>(*this));
   107       }
   108 
   109       NodeIt(const Graph& _graph, const Node& node) 
   110 	: Node(node), graph(&_graph) {}
   111 
   112       NodeIt& operator++() { 
   113 	graph->next(*this);
   114 	return *this; 
   115       }
   116 
   117     };
   118 
   119 
   120     class EdgeIt : public Edge { 
   121       const Graph* graph;
   122     public:
   123 
   124       EdgeIt() { }
   125 
   126       EdgeIt(Invalid i) : Edge(i) { }
   127 
   128       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
   129 	_graph.first(static_cast<Edge&>(*this));
   130       }
   131 
   132       EdgeIt(const Graph& _graph, const Edge& e) : 
   133 	Edge(e), graph(&_graph) { }
   134 
   135       EdgeIt& operator++() { 
   136 	graph->next(*this);
   137 	return *this; 
   138       }
   139 
   140     };
   141 
   142 
   143     class OutEdgeIt : public Edge { 
   144       const Graph* graph;
   145     public:
   146 
   147       OutEdgeIt() { }
   148 
   149       OutEdgeIt(Invalid i) : Edge(i) { }
   150 
   151       OutEdgeIt(const Graph& _graph, const Node& node) 
   152 	: graph(&_graph) {
   153 	_graph.firstOut(*this, node);
   154       }
   155 
   156       OutEdgeIt(const Graph& _graph, const Edge& edge) 
   157 	: Edge(edge), graph(&_graph) {}
   158 
   159       OutEdgeIt& operator++() { 
   160 	graph->nextOut(*this);
   161 	return *this; 
   162       }
   163 
   164     };
   165 
   166 
   167     class InEdgeIt : public Edge { 
   168       const Graph* graph;
   169     public:
   170 
   171       InEdgeIt() { }
   172 
   173       InEdgeIt(Invalid i) : Edge(i) { }
   174 
   175       InEdgeIt(const Graph& _graph, const Node& node) 
   176 	: graph(&_graph) {
   177 	_graph.firstIn(*this, node);
   178       }
   179 
   180       InEdgeIt(const Graph& _graph, const Edge& edge) : 
   181 	Edge(edge), graph(&_graph) {}
   182 
   183       InEdgeIt& operator++() { 
   184 	graph->nextIn(*this);
   185 	return *this; 
   186       }
   187 
   188     };
   189 
   190     /// \brief Base node of the iterator
   191     ///
   192     /// Returns the base node (ie. the source in this case) of the iterator
   193     Node baseNode(const OutEdgeIt &e) const {
   194       return Parent::source(e);
   195     }
   196     /// \brief Running node of the iterator
   197     ///
   198     /// Returns the running node (ie. the target in this case) of the
   199     /// iterator
   200     Node runningNode(const OutEdgeIt &e) const {
   201       return Parent::target(e);
   202     }
   203 
   204     /// \brief Base node of the iterator
   205     ///
   206     /// Returns the base node (ie. the target in this case) of the iterator
   207     Node baseNode(const InEdgeIt &e) const {
   208       return Parent::target(e);
   209     }
   210     /// \brief Running node of the iterator
   211     ///
   212     /// Returns the running node (ie. the source in this case) of the
   213     /// iterator
   214     Node runningNode(const InEdgeIt &e) const {
   215       return Parent::source(e);
   216     }
   217 
   218     
   219     template <typename _Value>
   220     class NodeMap 
   221       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   222     public:
   223       typedef GraphExtender Graph;
   224       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   225 
   226       explicit NodeMap(const Graph& graph) 
   227 	: Parent(graph) {}
   228       NodeMap(const Graph& graph, const _Value& value) 
   229 	: Parent(graph, value) {}
   230 
   231       NodeMap& operator=(const NodeMap& cmap) {
   232 	return operator=<NodeMap>(cmap);
   233       }
   234 
   235       template <typename CMap>
   236       NodeMap& operator=(const CMap& cmap) {
   237         Parent::operator=(cmap);
   238 	return *this;
   239       }
   240 
   241     };
   242 
   243     template <typename _Value>
   244     class EdgeMap 
   245       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   246     public:
   247       typedef GraphExtender Graph;
   248       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   249 
   250       explicit EdgeMap(const Graph& graph) 
   251 	: Parent(graph) {}
   252       EdgeMap(const Graph& graph, const _Value& value) 
   253 	: Parent(graph, value) {}
   254 
   255       EdgeMap& operator=(const EdgeMap& cmap) {
   256 	return operator=<EdgeMap>(cmap);
   257       }
   258 
   259       template <typename CMap>
   260       EdgeMap& operator=(const CMap& cmap) {
   261         Parent::operator=(cmap);
   262 	return *this;
   263       }
   264     };
   265 
   266 
   267     Node addNode() {
   268       Node node = Parent::addNode();
   269       getNotifier(Node()).add(node);
   270       return node;
   271     }
   272     
   273     Edge addEdge(const Node& from, const Node& to) {
   274       Edge edge = Parent::addEdge(from, to);
   275       getNotifier(Edge()).add(edge);
   276       return edge;
   277     }
   278 
   279     void clear() {
   280       getNotifier(Edge()).clear();
   281       getNotifier(Node()).clear();
   282       Parent::clear();
   283     }
   284 
   285 
   286     void erase(const Node& node) {
   287       Edge edge;
   288       Parent::firstOut(edge, node);
   289       while (edge != INVALID ) {
   290 	erase(edge);
   291 	Parent::firstOut(edge, node);
   292       } 
   293 
   294       Parent::firstIn(edge, node);
   295       while (edge != INVALID ) {
   296 	erase(edge);
   297 	Parent::firstIn(edge, node);
   298       }
   299 
   300       getNotifier(Node()).erase(node);
   301       Parent::erase(node);
   302     }
   303     
   304     void erase(const Edge& edge) {
   305       getNotifier(Edge()).erase(edge);
   306       Parent::erase(edge);
   307     }
   308 
   309     GraphExtender() {
   310       node_notifier.setContainer(*this);
   311       edge_notifier.setContainer(*this);
   312     } 
   313     
   314 
   315     ~GraphExtender() {
   316       edge_notifier.clear();
   317       node_notifier.clear();
   318     }
   319   };
   320 
   321   /// \ingroup graphbits
   322   ///
   323   /// \brief Extender for the UGraphs
   324   template <typename Base> 
   325   class UGraphExtender : public Base {
   326   public:
   327     
   328     typedef Base Parent;
   329     typedef UGraphExtender Graph;
   330 
   331     typedef typename Parent::Node Node;
   332     typedef typename Parent::Edge Edge;
   333     typedef typename Parent::UEdge UEdge;
   334 
   335     // UGraph extension    
   336 
   337     int maxId(Node) const {
   338       return Parent::maxNodeId();
   339     }
   340 
   341     int maxId(Edge) const {
   342       return Parent::maxEdgeId();
   343     }
   344 
   345     int maxId(UEdge) const {
   346       return Parent::maxUEdgeId();
   347     }
   348 
   349     Node fromId(int id, Node) const {
   350       return Parent::nodeFromId(id);
   351     }
   352 
   353     Edge fromId(int id, Edge) const {
   354       return Parent::edgeFromId(id);
   355     }
   356 
   357     UEdge fromId(int id, UEdge) const {
   358       return Parent::uEdgeFromId(id);
   359     }
   360 
   361     Node oppositeNode(const Node &n, const UEdge &e) const {
   362       if( n == Parent::source(e))
   363 	return Parent::target(e);
   364       else if( n == Parent::target(e))
   365 	return Parent::source(e);
   366       else
   367 	return INVALID;
   368     }
   369 
   370     Edge oppositeEdge(const Edge &e) const {
   371       return Parent::direct(e, !Parent::direction(e));
   372     }
   373 
   374     using Parent::direct;
   375     Edge direct(const UEdge &ue, const Node &s) const {
   376       return Parent::direct(ue, Parent::source(ue) == s);
   377     }
   378 
   379     // Alterable extension
   380 
   381     typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
   382     typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
   383     typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
   384 
   385 
   386   protected:
   387 
   388     mutable NodeNotifier node_notifier;
   389     mutable EdgeNotifier edge_notifier;
   390     mutable UEdgeNotifier uedge_notifier;
   391 
   392   public:
   393 
   394     NodeNotifier& getNotifier(Node) const {
   395       return node_notifier;
   396     }
   397     
   398     EdgeNotifier& getNotifier(Edge) const {
   399       return edge_notifier;
   400     }
   401 
   402     UEdgeNotifier& getNotifier(UEdge) const {
   403       return uedge_notifier;
   404     }
   405 
   406 
   407 
   408     class NodeIt : public Node { 
   409       const Graph* graph;
   410     public:
   411 
   412       NodeIt() {}
   413 
   414       NodeIt(Invalid i) : Node(i) { }
   415 
   416       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
   417 	_graph.first(static_cast<Node&>(*this));
   418       }
   419 
   420       NodeIt(const Graph& _graph, const Node& node) 
   421 	: Node(node), graph(&_graph) {}
   422 
   423       NodeIt& operator++() { 
   424 	graph->next(*this);
   425 	return *this; 
   426       }
   427 
   428     };
   429 
   430 
   431     class EdgeIt : public Edge { 
   432       const Graph* graph;
   433     public:
   434 
   435       EdgeIt() { }
   436 
   437       EdgeIt(Invalid i) : Edge(i) { }
   438 
   439       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
   440 	_graph.first(static_cast<Edge&>(*this));
   441       }
   442 
   443       EdgeIt(const Graph& _graph, const Edge& e) : 
   444 	Edge(e), graph(&_graph) { }
   445 
   446       EdgeIt& operator++() { 
   447 	graph->next(*this);
   448 	return *this; 
   449       }
   450 
   451     };
   452 
   453 
   454     class OutEdgeIt : public Edge { 
   455       const Graph* graph;
   456     public:
   457 
   458       OutEdgeIt() { }
   459 
   460       OutEdgeIt(Invalid i) : Edge(i) { }
   461 
   462       OutEdgeIt(const Graph& _graph, const Node& node) 
   463 	: graph(&_graph) {
   464 	_graph.firstOut(*this, node);
   465       }
   466 
   467       OutEdgeIt(const Graph& _graph, const Edge& edge) 
   468 	: Edge(edge), graph(&_graph) {}
   469 
   470       OutEdgeIt& operator++() { 
   471 	graph->nextOut(*this);
   472 	return *this; 
   473       }
   474 
   475     };
   476 
   477 
   478     class InEdgeIt : public Edge { 
   479       const Graph* graph;
   480     public:
   481 
   482       InEdgeIt() { }
   483 
   484       InEdgeIt(Invalid i) : Edge(i) { }
   485 
   486       InEdgeIt(const Graph& _graph, const Node& node) 
   487 	: graph(&_graph) {
   488 	_graph.firstIn(*this, node);
   489       }
   490 
   491       InEdgeIt(const Graph& _graph, const Edge& edge) : 
   492 	Edge(edge), graph(&_graph) {}
   493 
   494       InEdgeIt& operator++() { 
   495 	graph->nextIn(*this);
   496 	return *this; 
   497       }
   498 
   499     };
   500 
   501 
   502     class UEdgeIt : public Parent::UEdge { 
   503       const Graph* graph;
   504     public:
   505 
   506       UEdgeIt() { }
   507 
   508       UEdgeIt(Invalid i) : UEdge(i) { }
   509 
   510       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
   511 	_graph.first(static_cast<UEdge&>(*this));
   512       }
   513 
   514       UEdgeIt(const Graph& _graph, const UEdge& e) : 
   515 	UEdge(e), graph(&_graph) { }
   516 
   517       UEdgeIt& operator++() { 
   518 	graph->next(*this);
   519 	return *this; 
   520       }
   521 
   522     };
   523 
   524     class IncEdgeIt : public Parent::UEdge {
   525       friend class UGraphExtender;
   526       const Graph* graph;
   527       bool direction;
   528     public:
   529 
   530       IncEdgeIt() { }
   531 
   532       IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
   533 
   534       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
   535 	_graph.firstInc(*this, direction, n);
   536       }
   537 
   538       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
   539 	: graph(&_graph), UEdge(ue) {
   540 	direction = (_graph.source(ue) == n);
   541       }
   542 
   543       IncEdgeIt& operator++() {
   544 	graph->nextInc(*this, direction);
   545 	return *this; 
   546       }
   547     };
   548 
   549     /// \brief Base node of the iterator
   550     ///
   551     /// Returns the base node (ie. the source in this case) of the iterator
   552     Node baseNode(const OutEdgeIt &e) const {
   553       return Parent::source((Edge)e);
   554     }
   555     /// \brief Running node of the iterator
   556     ///
   557     /// Returns the running node (ie. the target in this case) of the
   558     /// iterator
   559     Node runningNode(const OutEdgeIt &e) const {
   560       return Parent::target((Edge)e);
   561     }
   562 
   563     /// \brief Base node of the iterator
   564     ///
   565     /// Returns the base node (ie. the target in this case) of the iterator
   566     Node baseNode(const InEdgeIt &e) const {
   567       return Parent::target((Edge)e);
   568     }
   569     /// \brief Running node of the iterator
   570     ///
   571     /// Returns the running node (ie. the source in this case) of the
   572     /// iterator
   573     Node runningNode(const InEdgeIt &e) const {
   574       return Parent::source((Edge)e);
   575     }
   576 
   577     /// Base node of the iterator
   578     ///
   579     /// Returns the base node of the iterator
   580     Node baseNode(const IncEdgeIt &e) const {
   581       return e.direction ? source(e) : target(e);
   582     }
   583     /// Running node of the iterator
   584     ///
   585     /// Returns the running node of the iterator
   586     Node runningNode(const IncEdgeIt &e) const {
   587       return e.direction ? target(e) : source(e);
   588     }
   589 
   590     // Mappable extension
   591 
   592     template <typename _Value>
   593     class NodeMap 
   594       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   595     public:
   596       typedef UGraphExtender Graph;
   597       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   598 
   599       NodeMap(const Graph& graph) 
   600 	: Parent(graph) {}
   601       NodeMap(const Graph& graph, const _Value& value) 
   602 	: Parent(graph, value) {}
   603 
   604       NodeMap& operator=(const NodeMap& cmap) {
   605 	return operator=<NodeMap>(cmap);
   606       }
   607 
   608       template <typename CMap>
   609       NodeMap& operator=(const CMap& cmap) {
   610         Parent::operator=(cmap);
   611 	return *this;
   612       }
   613 
   614     };
   615 
   616     template <typename _Value>
   617     class EdgeMap 
   618       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   619     public:
   620       typedef UGraphExtender Graph;
   621       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   622 
   623       EdgeMap(const Graph& graph) 
   624 	: Parent(graph) {}
   625       EdgeMap(const Graph& graph, const _Value& value) 
   626 	: Parent(graph, value) {}
   627 
   628       EdgeMap& operator=(const EdgeMap& cmap) {
   629 	return operator=<EdgeMap>(cmap);
   630       }
   631 
   632       template <typename CMap>
   633       EdgeMap& operator=(const CMap& cmap) {
   634         Parent::operator=(cmap);
   635 	return *this;
   636       }
   637     };
   638 
   639 
   640     template <typename _Value>
   641     class UEdgeMap 
   642       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
   643     public:
   644       typedef UGraphExtender Graph;
   645       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
   646 
   647       UEdgeMap(const Graph& graph) 
   648 	: Parent(graph) {}
   649 
   650       UEdgeMap(const Graph& graph, const _Value& value) 
   651 	: Parent(graph, value) {}
   652 
   653       UEdgeMap& operator=(const UEdgeMap& cmap) {
   654 	return operator=<UEdgeMap>(cmap);
   655       }
   656 
   657       template <typename CMap>
   658       UEdgeMap& operator=(const CMap& cmap) {
   659         Parent::operator=(cmap);
   660 	return *this;
   661       }
   662 
   663     };
   664 
   665     // Alteration extension
   666 
   667     Node addNode() {
   668       Node node = Parent::addNode();
   669       getNotifier(Node()).add(node);
   670       return node;
   671     }
   672 
   673     UEdge addEdge(const Node& from, const Node& to) {
   674       UEdge uedge = Parent::addEdge(from, to);
   675       getNotifier(UEdge()).add(uedge);
   676       getNotifier(Edge()).add(Parent::direct(uedge, true));
   677       getNotifier(Edge()).add(Parent::direct(uedge, false));
   678       return uedge;
   679     }
   680     
   681     void clear() {
   682       getNotifier(Edge()).clear();
   683       getNotifier(UEdge()).clear();
   684       getNotifier(Node()).clear();
   685       Parent::clear();
   686     }
   687 
   688     void erase(const Node& node) {
   689       Edge edge;
   690       Parent::firstOut(edge, node);
   691       while (edge != INVALID ) {
   692 	erase(edge);
   693 	Parent::firstOut(edge, node);
   694       } 
   695 
   696       Parent::firstIn(edge, node);
   697       while (edge != INVALID ) {
   698 	erase(edge);
   699 	Parent::firstIn(edge, node);
   700       }
   701 
   702       getNotifier(Node()).erase(node);
   703       Parent::erase(node);
   704     }
   705 
   706     void erase(const UEdge& uedge) {
   707       getNotifier(Edge()).erase(Parent::direct(uedge, true));
   708       getNotifier(Edge()).erase(Parent::direct(uedge, false));
   709       getNotifier(UEdge()).erase(uedge);
   710       Parent::erase(uedge);
   711     }
   712 
   713     UGraphExtender() {
   714       node_notifier.setContainer(*this); 
   715       edge_notifier.setContainer(*this);
   716       uedge_notifier.setContainer(*this);
   717     } 
   718 
   719     ~UGraphExtender() {
   720       uedge_notifier.clear();
   721       edge_notifier.clear();
   722       node_notifier.clear(); 
   723     } 
   724 
   725   };
   726 
   727   /// \ingroup graphbits
   728   ///
   729   /// \brief Extender for the BpUGraphs
   730   template <typename Base>
   731   class BpUGraphExtender : public Base {
   732   public:
   733     typedef Base Parent;
   734     typedef BpUGraphExtender Graph;
   735 
   736     typedef typename Parent::Node Node;
   737     typedef typename Parent::UEdge UEdge;
   738 
   739 
   740     using Parent::first;
   741     using Parent::next;
   742 
   743     using Parent::id;
   744 
   745     class ANode : public Node {
   746       friend class BpUGraphExtender;
   747     public:
   748       ANode() {}
   749       ANode(const Node& node) : Node(node) {
   750 	LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 
   751 		     typename Parent::NodeSetError());
   752       }
   753       ANode(Invalid) : Node(INVALID) {}
   754     };
   755 
   756     void first(ANode& node) const {
   757       Parent::firstANode(static_cast<Node&>(node));
   758     }
   759     void next(ANode& node) const {
   760       Parent::nextANode(static_cast<Node&>(node));
   761     }
   762 
   763     int id(const ANode& node) const {
   764       return Parent::aNodeId(node);
   765     }
   766 
   767     class BNode : public Node {
   768       friend class BpUGraphExtender;
   769     public:
   770       BNode() {}
   771       BNode(const Node& node) : Node(node) {
   772 	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
   773 		     typename Parent::NodeSetError());
   774       }
   775       BNode(Invalid) : Node(INVALID) {}
   776     };
   777 
   778     void first(BNode& node) const {
   779       Parent::firstBNode(static_cast<Node&>(node));
   780     }
   781     void next(BNode& node) const {
   782       Parent::nextBNode(static_cast<Node&>(node));
   783     }
   784   
   785     int id(const BNode& node) const {
   786       return Parent::aNodeId(node);
   787     }
   788 
   789     Node source(const UEdge& edge) const {
   790       return aNode(edge);
   791     }
   792     Node target(const UEdge& edge) const {
   793       return bNode(edge);
   794     }
   795 
   796     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
   797       if (Parent::aNode(node)) {
   798 	Parent::firstFromANode(edge, node);
   799 	direction = true;
   800       } else {
   801 	Parent::firstFromBNode(edge, node);
   802 	direction = static_cast<UEdge&>(edge) == INVALID;
   803       }
   804     }
   805     void nextInc(UEdge& edge, bool& direction) const {
   806       if (direction) {
   807 	Parent::nextFromANode(edge);
   808       } else {
   809 	Parent::nextFromBNode(edge);
   810 	if (edge == INVALID) direction = true;
   811       }
   812     }
   813 
   814     class Edge : public UEdge {
   815       friend class BpUGraphExtender;
   816     protected:
   817       bool forward;
   818 
   819       Edge(const UEdge& edge, bool _forward)
   820 	: UEdge(edge), forward(_forward) {}
   821 
   822     public:
   823       Edge() {}
   824       Edge (Invalid) : UEdge(INVALID), forward(true) {}
   825       bool operator==(const Edge& i) const {
   826 	return UEdge::operator==(i) && forward == i.forward;
   827       }
   828       bool operator!=(const Edge& i) const {
   829 	return UEdge::operator!=(i) || forward != i.forward;
   830       }
   831       bool operator<(const Edge& i) const {
   832 	return UEdge::operator<(i) || 
   833 	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));
   834       }
   835     };
   836 
   837     void first(Edge& edge) const {
   838       Parent::first(static_cast<UEdge&>(edge));
   839       edge.forward = true;
   840     }
   841 
   842     void next(Edge& edge) const {
   843       if (!edge.forward) {
   844 	Parent::next(static_cast<UEdge&>(edge));
   845       }
   846       edge.forward = !edge.forward;
   847     }
   848 
   849     void firstOut(Edge& edge, const Node& node) const {
   850       if (Parent::aNode(node)) {
   851 	Parent::firstFromANode(edge, node);
   852 	edge.forward = true;
   853       } else {
   854 	Parent::firstFromBNode(edge, node);
   855 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
   856       }
   857     }
   858     void nextOut(Edge& edge) const {
   859       if (edge.forward) {
   860 	Parent::nextFromANode(edge);
   861       } else {
   862 	Parent::nextFromBNode(edge);
   863         edge.forward = static_cast<UEdge&>(edge) == INVALID;
   864       }
   865     }
   866 
   867     void firstIn(Edge& edge, const Node& node) const {
   868       if (Parent::bNode(node)) {
   869 	Parent::firstFromBNode(edge, node);
   870 	edge.forward = true;	
   871       } else {
   872 	Parent::firstFromANode(edge, node);
   873 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
   874       }
   875     }
   876     void nextIn(Edge& edge) const {
   877       if (edge.forward) {
   878 	Parent::nextFromBNode(edge);
   879       } else {
   880 	Parent::nextFromANode(edge);
   881 	edge.forward = static_cast<UEdge&>(edge) == INVALID;
   882       }
   883     }
   884 
   885     Node source(const Edge& edge) const {
   886       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
   887     }
   888     Node target(const Edge& edge) const {
   889       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
   890     }
   891 
   892     int id(const Edge& edge) const {
   893       return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 
   894         (edge.forward ? 0 : 1);
   895     }
   896     Edge edgeFromId(int id) const {
   897       return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
   898     }
   899     int maxEdgeId() const {
   900       return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
   901     }
   902 
   903     bool direction(const Edge& edge) const {
   904       return edge.forward;
   905     }
   906 
   907     Edge direct(const UEdge& edge, bool direction) const {
   908       return Edge(edge, direction);
   909     }
   910 
   911     int edgeNum() const {
   912       return 2 * Parent::uEdgeNum();
   913     }
   914 
   915     int uEdgeNum() const {
   916       return Parent::uEdgeNum();
   917     }
   918 
   919     Node oppositeNode(const UEdge& edge, const Node& node) const {
   920       return source(edge) == node ? 
   921 	target(edge) : source(edge);
   922     }
   923 
   924     Edge direct(const UEdge& edge, const Node& node) const {
   925       return Edge(edge, node == Parent::source(edge));
   926     }
   927 
   928     Edge oppositeEdge(const Edge& edge) const {
   929       return Parent::direct(edge, !Parent::direction(edge));
   930     }
   931 
   932 
   933     int maxId(Node) const {
   934       return Parent::maxNodeId();
   935     }
   936     int maxId(BNode) const {
   937       return Parent::maxBNodeId();
   938     }
   939     int maxId(ANode) const {
   940       return Parent::maxANodeId();
   941     }
   942     int maxId(Edge) const {
   943       return maxEdgeId();
   944     }
   945     int maxId(UEdge) const {
   946       return Parent::maxUEdgeId();
   947     }
   948 
   949 
   950     Node fromId(int id, Node) const {
   951       return Parent::nodeFromId(id);
   952     }
   953     ANode fromId(int id, ANode) const {
   954       return Parent::fromANodeId(id);
   955     }
   956     BNode fromId(int id, BNode) const {
   957       return Parent::fromBNodeId(id);
   958     }
   959     Edge fromId(int id, Edge) const {
   960       return Parent::edgeFromId(id);
   961     }
   962     UEdge fromId(int id, UEdge) const {
   963       return Parent::uEdgeFromId(id);
   964     }  
   965   
   966     typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
   967     typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
   968     typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
   969     typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
   970     typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
   971 
   972   protected:
   973 
   974     mutable ANodeNotifier anode_notifier;
   975     mutable BNodeNotifier bnode_notifier;
   976     mutable NodeNotifier node_notifier;
   977     mutable EdgeNotifier edge_notifier;
   978     mutable UEdgeNotifier uedge_notifier;
   979 
   980   public:
   981 
   982     NodeNotifier& getNotifier(Node) const {
   983       return node_notifier;
   984     }
   985 
   986     ANodeNotifier& getNotifier(ANode) const {
   987       return anode_notifier;
   988     }
   989 
   990     BNodeNotifier& getNotifier(BNode) const {
   991       return bnode_notifier;
   992     }
   993 
   994     EdgeNotifier& getNotifier(Edge) const {
   995       return edge_notifier;
   996     }
   997 
   998     UEdgeNotifier& getNotifier(UEdge) const {
   999       return uedge_notifier;
  1000     }
  1001 
  1002     class NodeIt : public Node { 
  1003       const Graph* graph;
  1004     public:
  1005     
  1006       NodeIt() { }
  1007     
  1008       NodeIt(Invalid i) : Node(INVALID) { }
  1009     
  1010       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
  1011 	graph->first(static_cast<Node&>(*this));
  1012       }
  1013 
  1014       NodeIt(const Graph& _graph, const Node& node) 
  1015 	: Node(node), graph(&_graph) { }
  1016     
  1017       NodeIt& operator++() { 
  1018 	graph->next(*this);
  1019 	return *this; 
  1020       }
  1021 
  1022     };
  1023 
  1024     class ANodeIt : public Node { 
  1025       friend class BpUGraphExtender;
  1026       const Graph* graph;
  1027     public:
  1028     
  1029       ANodeIt() { }
  1030     
  1031       ANodeIt(Invalid i) : Node(INVALID) { }
  1032     
  1033       explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
  1034 	graph->firstANode(static_cast<Node&>(*this));
  1035       }
  1036 
  1037       ANodeIt(const Graph& _graph, const Node& node) 
  1038 	: Node(node), graph(&_graph) {}
  1039     
  1040       ANodeIt& operator++() { 
  1041 	graph->nextANode(*this);
  1042 	return *this; 
  1043       }
  1044     };
  1045 
  1046     class BNodeIt : public Node { 
  1047       friend class BpUGraphExtender;
  1048       const Graph* graph;
  1049     public:
  1050     
  1051       BNodeIt() { }
  1052     
  1053       BNodeIt(Invalid i) : Node(INVALID) { }
  1054     
  1055       explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
  1056 	graph->firstBNode(static_cast<Node&>(*this));
  1057       }
  1058 
  1059       BNodeIt(const Graph& _graph, const Node& node) 
  1060 	: Node(node), graph(&_graph) {}
  1061     
  1062       BNodeIt& operator++() { 
  1063 	graph->nextBNode(*this);
  1064 	return *this; 
  1065       }
  1066     };
  1067 
  1068     class EdgeIt : public Edge { 
  1069       friend class BpUGraphExtender;
  1070       const Graph* graph;
  1071     public:
  1072     
  1073       EdgeIt() { }
  1074     
  1075       EdgeIt(Invalid i) : Edge(INVALID) { }
  1076     
  1077       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
  1078 	graph->first(static_cast<Edge&>(*this));
  1079       }
  1080 
  1081       EdgeIt(const Graph& _graph, const Edge& edge) 
  1082 	: Edge(edge), graph(&_graph) { }
  1083     
  1084       EdgeIt& operator++() { 
  1085 	graph->next(*this);
  1086 	return *this; 
  1087       }
  1088 
  1089     };
  1090 
  1091     class UEdgeIt : public UEdge { 
  1092       friend class BpUGraphExtender;
  1093       const Graph* graph;
  1094     public:
  1095     
  1096       UEdgeIt() { }
  1097     
  1098       UEdgeIt(Invalid i) : UEdge(INVALID) { }
  1099     
  1100       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
  1101 	graph->first(static_cast<UEdge&>(*this));
  1102       }
  1103 
  1104       UEdgeIt(const Graph& _graph, const UEdge& edge) 
  1105 	: UEdge(edge), graph(&_graph) { }
  1106     
  1107       UEdgeIt& operator++() { 
  1108 	graph->next(*this);
  1109 	return *this; 
  1110       }
  1111     };
  1112 
  1113     class OutEdgeIt : public Edge { 
  1114       friend class BpUGraphExtender;
  1115       const Graph* graph;
  1116     public:
  1117     
  1118       OutEdgeIt() { }
  1119     
  1120       OutEdgeIt(Invalid i) : Edge(i) { }
  1121     
  1122       OutEdgeIt(const Graph& _graph, const Node& node) 
  1123 	: graph(&_graph) {
  1124 	graph->firstOut(*this, node);
  1125       }
  1126     
  1127       OutEdgeIt(const Graph& _graph, const Edge& edge) 
  1128 	: Edge(edge), graph(&_graph) {}
  1129     
  1130       OutEdgeIt& operator++() { 
  1131 	graph->nextOut(*this);
  1132 	return *this; 
  1133       }
  1134 
  1135     };
  1136 
  1137 
  1138     class InEdgeIt : public Edge { 
  1139       friend class BpUGraphExtender;
  1140       const Graph* graph;
  1141     public:
  1142     
  1143       InEdgeIt() { }
  1144     
  1145       InEdgeIt(Invalid i) : Edge(i) { }
  1146     
  1147       InEdgeIt(const Graph& _graph, const Node& node) 
  1148 	: graph(&_graph) {
  1149 	graph->firstIn(*this, node);
  1150       }
  1151     
  1152       InEdgeIt(const Graph& _graph, const Edge& edge) : 
  1153 	Edge(edge), graph(&_graph) {}
  1154     
  1155       InEdgeIt& operator++() { 
  1156 	graph->nextIn(*this);
  1157 	return *this; 
  1158       }
  1159 
  1160     };
  1161   
  1162     /// \brief Base node of the iterator
  1163     ///
  1164     /// Returns the base node (ie. the source in this case) of the iterator
  1165     Node baseNode(const OutEdgeIt &e) const {
  1166       return Parent::source((Edge&)e);
  1167     }
  1168     /// \brief Running node of the iterator
  1169     ///
  1170     /// Returns the running node (ie. the target in this case) of the
  1171     /// iterator
  1172     Node runningNode(const OutEdgeIt &e) const {
  1173       return Parent::target((Edge&)e);
  1174     }
  1175   
  1176     /// \brief Base node of the iterator
  1177     ///
  1178     /// Returns the base node (ie. the target in this case) of the iterator
  1179     Node baseNode(const InEdgeIt &e) const {
  1180       return Parent::target((Edge&)e);
  1181     }
  1182     /// \brief Running node of the iterator
  1183     ///
  1184     /// Returns the running node (ie. the source in this case) of the
  1185     /// iterator
  1186     Node runningNode(const InEdgeIt &e) const {
  1187       return Parent::source((Edge&)e);
  1188     }
  1189   
  1190     class IncEdgeIt : public Parent::UEdge { 
  1191       friend class BpUGraphExtender;
  1192       const Graph* graph;
  1193       bool direction;
  1194     public:
  1195     
  1196       IncEdgeIt() { }
  1197     
  1198       IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
  1199     
  1200       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
  1201 	graph->firstInc(*this, direction, n);
  1202       }
  1203 
  1204       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
  1205 	: graph(&_graph), UEdge(ue) {
  1206 	direction = (graph->source(ue) == n);
  1207       }
  1208 
  1209       IncEdgeIt& operator++() {
  1210 	graph->nextInc(*this, direction);
  1211 	return *this; 
  1212       }
  1213     };
  1214   
  1215 
  1216     /// Base node of the iterator
  1217     ///
  1218     /// Returns the base node of the iterator
  1219     Node baseNode(const IncEdgeIt &e) const {
  1220       return e.direction ? source(e) : target(e);
  1221     }
  1222 
  1223     /// Running node of the iterator
  1224     ///
  1225     /// Returns the running node of the iterator
  1226     Node runningNode(const IncEdgeIt &e) const {
  1227       return e.direction ? target(e) : source(e);
  1228     }
  1229 
  1230     template <typename _Value>
  1231     class ANodeMap 
  1232       : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
  1233     public:
  1234       typedef BpUGraphExtender Graph;
  1235       typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
  1236     
  1237       ANodeMap(const Graph& graph) 
  1238 	: Parent(graph) {}
  1239       ANodeMap(const Graph& graph, const _Value& value) 
  1240 	: Parent(graph, value) {}
  1241     
  1242       ANodeMap& operator=(const ANodeMap& cmap) {
  1243 	return operator=<ANodeMap>(cmap);
  1244       }
  1245     
  1246       template <typename CMap>
  1247       ANodeMap& operator=(const CMap& cmap) {
  1248         Parent::operator=(cmap);
  1249 	return *this;
  1250       }
  1251     
  1252     };
  1253 
  1254     template <typename _Value>
  1255     class BNodeMap 
  1256       : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
  1257     public:
  1258       typedef BpUGraphExtender Graph;
  1259       typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
  1260     
  1261       BNodeMap(const Graph& graph) 
  1262 	: Parent(graph) {}
  1263       BNodeMap(const Graph& graph, const _Value& value) 
  1264 	: Parent(graph, value) {}
  1265     
  1266       BNodeMap& operator=(const BNodeMap& cmap) {
  1267 	return operator=<BNodeMap>(cmap);
  1268       }
  1269     
  1270       template <typename CMap>
  1271       BNodeMap& operator=(const CMap& cmap) {
  1272         Parent::operator=(cmap);
  1273 	return *this;
  1274       }
  1275     
  1276     };
  1277 
  1278   public:
  1279 
  1280     template <typename _Value>
  1281     class NodeMap {
  1282     public:
  1283       typedef BpUGraphExtender Graph;
  1284 
  1285       typedef Node Key;
  1286       typedef _Value Value;
  1287 
  1288       /// The reference type of the map;
  1289       typedef typename ANodeMap<_Value>::Reference Reference;
  1290       /// The const reference type of the map;
  1291       typedef typename ANodeMap<_Value>::ConstReference ConstReference;
  1292 
  1293       typedef True ReferenceMapTag;
  1294 
  1295       NodeMap(const Graph& _graph) 
  1296 	: graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
  1297       NodeMap(const Graph& _graph, const _Value& _value) 
  1298 	: graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
  1299 
  1300       NodeMap& operator=(const NodeMap& cmap) {
  1301 	return operator=<NodeMap>(cmap);
  1302       }
  1303     
  1304       template <typename CMap>
  1305       NodeMap& operator=(const CMap& cmap) {
  1306 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();
  1307 	const typename Parent::Notifier* notifier = Parent::getNotifier();
  1308 	Edge it;
  1309 	for (graph.first(it); it != INVALID; graph.next(it)) {
  1310 	  Parent::set(it, cmap[it]);
  1311 	}
  1312 	return *this;
  1313       }
  1314 
  1315       ConstReference operator[](const Key& node) const {
  1316 	if (Parent::aNode(node)) {
  1317 	  return aNodeMap[node];
  1318 	} else {
  1319 	  return bNodeMap[node];
  1320 	}
  1321       } 
  1322 
  1323       Reference operator[](const Key& node) {
  1324 	if (Parent::aNode(node)) {
  1325 	  return aNodeMap[node];
  1326 	} else {
  1327 	  return bNodeMap[node];
  1328 	}
  1329       }
  1330 
  1331       void set(const Key& node, const Value& value) {
  1332 	if (Parent::aNode(node)) {
  1333 	  aNodeMap.set(node, value);
  1334 	} else {
  1335 	  bNodeMap.set(node, value);
  1336 	}
  1337       }
  1338 
  1339       class MapIt : public NodeIt {
  1340       public:
  1341 
  1342         typedef NodeIt Parent;
  1343         
  1344         explicit MapIt(NodeMap& _map) 
  1345           : Parent(_map.graph), map(_map) {}
  1346         
  1347         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
  1348           return map[*this];
  1349         }
  1350         
  1351         typename MapTraits<NodeMap>::ReturnValue operator*() {
  1352           return map[*this];
  1353         }
  1354         
  1355         void set(const Value& value) {
  1356           map.set(*this, value);
  1357         }
  1358 
  1359       private:
  1360         NodeMap& map;
  1361       };
  1362 
  1363       class ConstMapIt : public NodeIt {
  1364       public:
  1365 
  1366         typedef NodeIt Parent;
  1367         
  1368         explicit ConstMapIt(const NodeMap& _map) 
  1369           : Parent(_map.graph), map(_map) {}
  1370         
  1371         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
  1372           return map[*this];
  1373         }
  1374         
  1375       private:
  1376         const NodeMap& map;
  1377       };
  1378 
  1379       class ItemIt : public NodeIt {
  1380       public:
  1381 
  1382         typedef NodeIt Parent;
  1383 
  1384         explicit ItemIt(const NodeMap& _map)
  1385           : Parent(_map.graph) {}
  1386         
  1387       };
  1388       
  1389     private:
  1390       const Graph& graph;
  1391       ANodeMap<_Value> aNodeMap;
  1392       BNodeMap<_Value> bNodeMap;
  1393     };
  1394     
  1395 
  1396     template <typename _Value>
  1397     class EdgeMap 
  1398       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
  1399     public:
  1400       typedef BpUGraphExtender Graph;
  1401       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
  1402     
  1403       EdgeMap(const Graph& graph) 
  1404 	: Parent(graph) {}
  1405       EdgeMap(const Graph& graph, const _Value& value) 
  1406 	: Parent(graph, value) {}
  1407     
  1408       EdgeMap& operator=(const EdgeMap& cmap) {
  1409 	return operator=<EdgeMap>(cmap);
  1410       }
  1411     
  1412       template <typename CMap>
  1413       EdgeMap& operator=(const CMap& cmap) {
  1414         Parent::operator=(cmap);
  1415 	return *this;
  1416       }
  1417     };
  1418 
  1419     template <typename _Value>
  1420     class UEdgeMap 
  1421       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
  1422     public:
  1423       typedef BpUGraphExtender Graph;
  1424       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
  1425     
  1426       UEdgeMap(const Graph& graph) 
  1427 	: Parent(graph) {}
  1428       UEdgeMap(const Graph& graph, const _Value& value) 
  1429 	: Parent(graph, value) {}
  1430     
  1431       UEdgeMap& operator=(const UEdgeMap& cmap) {
  1432 	return operator=<UEdgeMap>(cmap);
  1433       }
  1434     
  1435       template <typename CMap>
  1436       UEdgeMap& operator=(const CMap& cmap) {
  1437         Parent::operator=(cmap);
  1438 	return *this;
  1439       }
  1440     };
  1441 
  1442   
  1443     Node addANode() {
  1444       Node node = Parent::addANode();
  1445       getNotifier(ANode()).add(node);
  1446       getNotifier(Node()).add(node);
  1447       return node;
  1448     }
  1449 
  1450     Node addBNode() {
  1451       Node node = Parent::addBNode();
  1452       getNotifier(BNode()).add(node);
  1453       getNotifier(Node()).add(node);
  1454       return node;
  1455     }
  1456   
  1457     UEdge addEdge(const Node& source, const Node& target) {
  1458       UEdge uedge = Parent::addEdge(source, target);
  1459       getNotifier(UEdge()).add(uedge);
  1460     
  1461       std::vector<Edge> edges;
  1462       edges.push_back(direct(uedge, true));
  1463       edges.push_back(direct(uedge, false));
  1464       getNotifier(Edge()).add(edges);
  1465     
  1466       return uedge;
  1467     }
  1468 
  1469     void clear() {
  1470       getNotifier(Edge()).clear();
  1471       getNotifier(UEdge()).clear();
  1472       getNotifier(Node()).clear();
  1473       getNotifier(BNode()).clear();
  1474       getNotifier(ANode()).clear();
  1475       Parent::clear();
  1476     }
  1477 
  1478     void erase(const Node& node) {
  1479       UEdge uedge;
  1480       if (Parent::aNode(node)) {
  1481         Parent::firstFromANode(uedge, node);
  1482         while (uedge != INVALID) {
  1483           erase(uedge);
  1484           Parent::firstFromANode(uedge, node);
  1485         }
  1486       } else {
  1487         Parent::firstFromBNode(uedge, node);
  1488         while (uedge != INVALID) {
  1489           erase(uedge);
  1490           Parent::firstFromBNode(uedge, node);
  1491         }
  1492       }
  1493 
  1494       getNotifier(Node()).erase(node);
  1495       Parent::erase(node);
  1496     }
  1497     
  1498     void erase(const UEdge& uedge) {
  1499       std::vector<Edge> edges;
  1500       edges.push_back(direct(uedge, true));
  1501       edges.push_back(direct(uedge, false));
  1502       getNotifier(Edge()).erase(edges);
  1503       getNotifier(UEdge()).erase(uedge);
  1504       Parent::erase(uedge);
  1505     }
  1506 
  1507 
  1508     BpUGraphExtender() {
  1509       anode_notifier.setContainer(*this); 
  1510       bnode_notifier.setContainer(*this); 
  1511       node_notifier.setContainer(*this); 
  1512       edge_notifier.setContainer(*this); 
  1513       uedge_notifier.setContainer(*this);
  1514     } 
  1515 
  1516     ~BpUGraphExtender() {
  1517       uedge_notifier.clear();
  1518       edge_notifier.clear(); 
  1519       node_notifier.clear(); 
  1520       anode_notifier.clear(); 
  1521       bnode_notifier.clear(); 
  1522     }
  1523 
  1524 
  1525   };
  1526 
  1527 }
  1528 
  1529 #endif