lemon/bits/graph_extender.h
changeset 210 81cfc04531e8
parent 125 19e82bda606a
child 220 a5d8c039f218
equal deleted inserted replaced
4:00ef713fdf0c 5:698dd04ad4e1
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    64       return Parent::arcFromId(id);
    64       return Parent::arcFromId(id);
    65     }
    65     }
    66 
    66 
    67     Node oppositeNode(const Node &node, const Arc &arc) const {
    67     Node oppositeNode(const Node &node, const Arc &arc) const {
    68       if (node == Parent::source(arc))
    68       if (node == Parent::source(arc))
    69 	return Parent::target(arc);
    69         return Parent::target(arc);
    70       else if(node == Parent::target(arc))
    70       else if(node == Parent::target(arc))
    71 	return Parent::source(arc);
    71         return Parent::source(arc);
    72       else
    72       else
    73 	return INVALID;
    73         return INVALID;
    74     }
    74     }
    75 
    75 
    76     // Alterable extension
    76     // Alterable extension
    77 
    77 
    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    87   public:
    87   public:
    88 
    88 
    89     NodeNotifier& notifier(Node) const {
    89     NodeNotifier& notifier(Node) const {
    90       return node_notifier;
    90       return node_notifier;
    91     }
    91     }
    92     
    92 
    93     ArcNotifier& notifier(Arc) const {
    93     ArcNotifier& notifier(Arc) const {
    94       return arc_notifier;
    94       return arc_notifier;
    95     }
    95     }
    96 
    96 
    97     class NodeIt : public Node { 
    97     class NodeIt : public Node {
    98       const Digraph* _digraph;
    98       const Digraph* _digraph;
    99     public:
    99     public:
   100 
   100 
   101       NodeIt() {}
   101       NodeIt() {}
   102 
   102 
   103       NodeIt(Invalid i) : Node(i) { }
   103       NodeIt(Invalid i) : Node(i) { }
   104 
   104 
   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   106 	_digraph->first(static_cast<Node&>(*this));
   106         _digraph->first(static_cast<Node&>(*this));
   107       }
   107       }
   108 
   108 
   109       NodeIt(const Digraph& digraph, const Node& node) 
   109       NodeIt(const Digraph& digraph, const Node& node)
   110 	: Node(node), _digraph(&digraph) {}
   110         : Node(node), _digraph(&digraph) {}
   111 
   111 
   112       NodeIt& operator++() { 
   112       NodeIt& operator++() {
   113 	_digraph->next(*this);
   113         _digraph->next(*this);
   114 	return *this; 
   114         return *this;
   115       }
   115       }
   116 
   116 
   117     };
   117     };
   118 
   118 
   119 
   119 
   120     class ArcIt : public Arc { 
   120     class ArcIt : public Arc {
   121       const Digraph* _digraph;
   121       const Digraph* _digraph;
   122     public:
   122     public:
   123 
   123 
   124       ArcIt() { }
   124       ArcIt() { }
   125 
   125 
   126       ArcIt(Invalid i) : Arc(i) { }
   126       ArcIt(Invalid i) : Arc(i) { }
   127 
   127 
   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   129 	_digraph->first(static_cast<Arc&>(*this));
   129         _digraph->first(static_cast<Arc&>(*this));
   130       }
   130       }
   131 
   131 
   132       ArcIt(const Digraph& digraph, const Arc& arc) : 
   132       ArcIt(const Digraph& digraph, const Arc& arc) :
   133 	Arc(arc), _digraph(&digraph) { }
   133         Arc(arc), _digraph(&digraph) { }
   134 
   134 
   135       ArcIt& operator++() { 
   135       ArcIt& operator++() {
   136 	_digraph->next(*this);
   136         _digraph->next(*this);
   137 	return *this; 
   137         return *this;
   138       }
   138       }
   139 
   139 
   140     };
   140     };
   141 
   141 
   142 
   142 
   143     class OutArcIt : public Arc { 
   143     class OutArcIt : public Arc {
   144       const Digraph* _digraph;
   144       const Digraph* _digraph;
   145     public:
   145     public:
   146 
   146 
   147       OutArcIt() { }
   147       OutArcIt() { }
   148 
   148 
   149       OutArcIt(Invalid i) : Arc(i) { }
   149       OutArcIt(Invalid i) : Arc(i) { }
   150 
   150 
   151       OutArcIt(const Digraph& digraph, const Node& node) 
   151       OutArcIt(const Digraph& digraph, const Node& node)
   152 	: _digraph(&digraph) {
   152         : _digraph(&digraph) {
   153 	_digraph->firstOut(*this, node);
   153         _digraph->firstOut(*this, node);
   154       }
   154       }
   155 
   155 
   156       OutArcIt(const Digraph& digraph, const Arc& arc) 
   156       OutArcIt(const Digraph& digraph, const Arc& arc)
   157 	: Arc(arc), _digraph(&digraph) {}
   157         : Arc(arc), _digraph(&digraph) {}
   158 
   158 
   159       OutArcIt& operator++() { 
   159       OutArcIt& operator++() {
   160 	_digraph->nextOut(*this);
   160         _digraph->nextOut(*this);
   161 	return *this; 
   161         return *this;
   162       }
   162       }
   163 
   163 
   164     };
   164     };
   165 
   165 
   166 
   166 
   167     class InArcIt : public Arc { 
   167     class InArcIt : public Arc {
   168       const Digraph* _digraph;
   168       const Digraph* _digraph;
   169     public:
   169     public:
   170 
   170 
   171       InArcIt() { }
   171       InArcIt() { }
   172 
   172 
   173       InArcIt(Invalid i) : Arc(i) { }
   173       InArcIt(Invalid i) : Arc(i) { }
   174 
   174 
   175       InArcIt(const Digraph& digraph, const Node& node) 
   175       InArcIt(const Digraph& digraph, const Node& node)
   176 	: _digraph(&digraph) {
   176         : _digraph(&digraph) {
   177 	_digraph->firstIn(*this, node);
   177         _digraph->firstIn(*this, node);
   178       }
   178       }
   179 
   179 
   180       InArcIt(const Digraph& digraph, const Arc& arc) : 
   180       InArcIt(const Digraph& digraph, const Arc& arc) :
   181 	Arc(arc), _digraph(&digraph) {}
   181         Arc(arc), _digraph(&digraph) {}
   182 
   182 
   183       InArcIt& operator++() { 
   183       InArcIt& operator++() {
   184 	_digraph->nextIn(*this);
   184         _digraph->nextIn(*this);
   185 	return *this; 
   185         return *this;
   186       }
   186       }
   187 
   187 
   188     };
   188     };
   189 
   189 
   190     /// \brief Base node of the iterator
   190     /// \brief Base node of the iterator
   213     /// iterator
   213     /// iterator
   214     Node runningNode(const InArcIt &arc) const {
   214     Node runningNode(const InArcIt &arc) const {
   215       return Parent::source(arc);
   215       return Parent::source(arc);
   216     }
   216     }
   217 
   217 
   218     
   218 
   219     template <typename _Value>
   219     template <typename _Value>
   220     class NodeMap 
   220     class NodeMap
   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   222     public:
   222     public:
   223       typedef DigraphExtender Digraph;
   223       typedef DigraphExtender Digraph;
   224       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   224       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   225 
   225 
   226       explicit NodeMap(const Digraph& digraph) 
   226       explicit NodeMap(const Digraph& digraph)
   227 	: Parent(digraph) {}
   227         : Parent(digraph) {}
   228       NodeMap(const Digraph& digraph, const _Value& value) 
   228       NodeMap(const Digraph& digraph, const _Value& value)
   229 	: Parent(digraph, value) {}
   229         : Parent(digraph, value) {}
   230 
   230 
   231       NodeMap& operator=(const NodeMap& cmap) {
   231       NodeMap& operator=(const NodeMap& cmap) {
   232 	return operator=<NodeMap>(cmap);
   232         return operator=<NodeMap>(cmap);
   233       }
   233       }
   234 
   234 
   235       template <typename CMap>
   235       template <typename CMap>
   236       NodeMap& operator=(const CMap& cmap) {
   236       NodeMap& operator=(const CMap& cmap) {
   237         Parent::operator=(cmap);
   237         Parent::operator=(cmap);
   238 	return *this;
   238         return *this;
   239       }
   239       }
   240 
   240 
   241     };
   241     };
   242 
   242 
   243     template <typename _Value>
   243     template <typename _Value>
   244     class ArcMap 
   244     class ArcMap
   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   246     public:
   246     public:
   247       typedef DigraphExtender Digraph;
   247       typedef DigraphExtender Digraph;
   248       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   248       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   249 
   249 
   250       explicit ArcMap(const Digraph& digraph) 
   250       explicit ArcMap(const Digraph& digraph)
   251 	: Parent(digraph) {}
   251         : Parent(digraph) {}
   252       ArcMap(const Digraph& digraph, const _Value& value) 
   252       ArcMap(const Digraph& digraph, const _Value& value)
   253 	: Parent(digraph, value) {}
   253         : Parent(digraph, value) {}
   254 
   254 
   255       ArcMap& operator=(const ArcMap& cmap) {
   255       ArcMap& operator=(const ArcMap& cmap) {
   256 	return operator=<ArcMap>(cmap);
   256         return operator=<ArcMap>(cmap);
   257       }
   257       }
   258 
   258 
   259       template <typename CMap>
   259       template <typename CMap>
   260       ArcMap& operator=(const CMap& cmap) {
   260       ArcMap& operator=(const CMap& cmap) {
   261         Parent::operator=(cmap);
   261         Parent::operator=(cmap);
   262 	return *this;
   262         return *this;
   263       }
   263       }
   264     };
   264     };
   265 
   265 
   266 
   266 
   267     Node addNode() {
   267     Node addNode() {
   268       Node node = Parent::addNode();
   268       Node node = Parent::addNode();
   269       notifier(Node()).add(node);
   269       notifier(Node()).add(node);
   270       return node;
   270       return node;
   271     }
   271     }
   272     
   272 
   273     Arc addArc(const Node& from, const Node& to) {
   273     Arc addArc(const Node& from, const Node& to) {
   274       Arc arc = Parent::addArc(from, to);
   274       Arc arc = Parent::addArc(from, to);
   275       notifier(Arc()).add(arc);
   275       notifier(Arc()).add(arc);
   276       return arc;
   276       return arc;
   277     }
   277     }
   291 
   291 
   292     void erase(const Node& node) {
   292     void erase(const Node& node) {
   293       Arc arc;
   293       Arc arc;
   294       Parent::firstOut(arc, node);
   294       Parent::firstOut(arc, node);
   295       while (arc != INVALID ) {
   295       while (arc != INVALID ) {
   296 	erase(arc);
   296         erase(arc);
   297 	Parent::firstOut(arc, node);
   297         Parent::firstOut(arc, node);
   298       } 
   298       }
   299 
   299 
   300       Parent::firstIn(arc, node);
   300       Parent::firstIn(arc, node);
   301       while (arc != INVALID ) {
   301       while (arc != INVALID ) {
   302 	erase(arc);
   302         erase(arc);
   303 	Parent::firstIn(arc, node);
   303         Parent::firstIn(arc, node);
   304       }
   304       }
   305 
   305 
   306       notifier(Node()).erase(node);
   306       notifier(Node()).erase(node);
   307       Parent::erase(node);
   307       Parent::erase(node);
   308     }
   308     }
   309     
   309 
   310     void erase(const Arc& arc) {
   310     void erase(const Arc& arc) {
   311       notifier(Arc()).erase(arc);
   311       notifier(Arc()).erase(arc);
   312       Parent::erase(arc);
   312       Parent::erase(arc);
   313     }
   313     }
   314 
   314 
   315     DigraphExtender() {
   315     DigraphExtender() {
   316       node_notifier.setContainer(*this);
   316       node_notifier.setContainer(*this);
   317       arc_notifier.setContainer(*this);
   317       arc_notifier.setContainer(*this);
   318     } 
   318     }
   319     
   319 
   320 
   320 
   321     ~DigraphExtender() {
   321     ~DigraphExtender() {
   322       arc_notifier.clear();
   322       arc_notifier.clear();
   323       node_notifier.clear();
   323       node_notifier.clear();
   324     }
   324     }
   325   };
   325   };
   326 
   326 
   327   /// \ingroup _graphbits
   327   /// \ingroup _graphbits
   328   ///
   328   ///
   329   /// \brief Extender for the Graphs
   329   /// \brief Extender for the Graphs
   330   template <typename Base> 
   330   template <typename Base>
   331   class GraphExtender : public Base {
   331   class GraphExtender : public Base {
   332   public:
   332   public:
   333     
   333 
   334     typedef Base Parent;
   334     typedef Base Parent;
   335     typedef GraphExtender Graph;
   335     typedef GraphExtender Graph;
   336 
   336 
   337     typedef True UndirectedTag;
   337     typedef True UndirectedTag;
   338 
   338 
   339     typedef typename Parent::Node Node;
   339     typedef typename Parent::Node Node;
   340     typedef typename Parent::Arc Arc;
   340     typedef typename Parent::Arc Arc;
   341     typedef typename Parent::Edge Edge;
   341     typedef typename Parent::Edge Edge;
   342 
   342 
   343     // Graph extension    
   343     // Graph extension
   344 
   344 
   345     int maxId(Node) const {
   345     int maxId(Node) const {
   346       return Parent::maxNodeId();
   346       return Parent::maxNodeId();
   347     }
   347     }
   348 
   348 
   366       return Parent::edgeFromId(id);
   366       return Parent::edgeFromId(id);
   367     }
   367     }
   368 
   368 
   369     Node oppositeNode(const Node &n, const Edge &e) const {
   369     Node oppositeNode(const Node &n, const Edge &e) const {
   370       if( n == Parent::u(e))
   370       if( n == Parent::u(e))
   371 	return Parent::v(e);
   371         return Parent::v(e);
   372       else if( n == Parent::v(e))
   372       else if( n == Parent::v(e))
   373 	return Parent::u(e);
   373         return Parent::u(e);
   374       else
   374       else
   375 	return INVALID;
   375         return INVALID;
   376     }
   376     }
   377 
   377 
   378     Arc oppositeArc(const Arc &arc) const {
   378     Arc oppositeArc(const Arc &arc) const {
   379       return Parent::direct(arc, !Parent::direction(arc));
   379       return Parent::direct(arc, !Parent::direction(arc));
   380     }
   380     }
   400   public:
   400   public:
   401 
   401 
   402     NodeNotifier& notifier(Node) const {
   402     NodeNotifier& notifier(Node) const {
   403       return node_notifier;
   403       return node_notifier;
   404     }
   404     }
   405     
   405 
   406     ArcNotifier& notifier(Arc) const {
   406     ArcNotifier& notifier(Arc) const {
   407       return arc_notifier;
   407       return arc_notifier;
   408     }
   408     }
   409 
   409 
   410     EdgeNotifier& notifier(Edge) const {
   410     EdgeNotifier& notifier(Edge) const {
   411       return edge_notifier;
   411       return edge_notifier;
   412     }
   412     }
   413 
   413 
   414 
   414 
   415 
   415 
   416     class NodeIt : public Node { 
   416     class NodeIt : public Node {
   417       const Graph* _graph;
   417       const Graph* _graph;
   418     public:
   418     public:
   419 
   419 
   420       NodeIt() {}
   420       NodeIt() {}
   421 
   421 
   422       NodeIt(Invalid i) : Node(i) { }
   422       NodeIt(Invalid i) : Node(i) { }
   423 
   423 
   424       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   424       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   425 	_graph->first(static_cast<Node&>(*this));
   425         _graph->first(static_cast<Node&>(*this));
   426       }
   426       }
   427 
   427 
   428       NodeIt(const Graph& graph, const Node& node) 
   428       NodeIt(const Graph& graph, const Node& node)
   429 	: Node(node), _graph(&graph) {}
   429         : Node(node), _graph(&graph) {}
   430 
   430 
   431       NodeIt& operator++() { 
   431       NodeIt& operator++() {
   432 	_graph->next(*this);
   432         _graph->next(*this);
   433 	return *this; 
   433         return *this;
   434       }
   434       }
   435 
   435 
   436     };
   436     };
   437 
   437 
   438 
   438 
   439     class ArcIt : public Arc { 
   439     class ArcIt : public Arc {
   440       const Graph* _graph;
   440       const Graph* _graph;
   441     public:
   441     public:
   442 
   442 
   443       ArcIt() { }
   443       ArcIt() { }
   444 
   444 
   445       ArcIt(Invalid i) : Arc(i) { }
   445       ArcIt(Invalid i) : Arc(i) { }
   446 
   446 
   447       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   447       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   448 	_graph->first(static_cast<Arc&>(*this));
   448         _graph->first(static_cast<Arc&>(*this));
   449       }
   449       }
   450 
   450 
   451       ArcIt(const Graph& graph, const Arc& arc) : 
   451       ArcIt(const Graph& graph, const Arc& arc) :
   452 	Arc(arc), _graph(&graph) { }
   452         Arc(arc), _graph(&graph) { }
   453 
   453 
   454       ArcIt& operator++() { 
   454       ArcIt& operator++() {
   455 	_graph->next(*this);
   455         _graph->next(*this);
   456 	return *this; 
   456         return *this;
   457       }
   457       }
   458 
   458 
   459     };
   459     };
   460 
   460 
   461 
   461 
   462     class OutArcIt : public Arc { 
   462     class OutArcIt : public Arc {
   463       const Graph* _graph;
   463       const Graph* _graph;
   464     public:
   464     public:
   465 
   465 
   466       OutArcIt() { }
   466       OutArcIt() { }
   467 
   467 
   468       OutArcIt(Invalid i) : Arc(i) { }
   468       OutArcIt(Invalid i) : Arc(i) { }
   469 
   469 
   470       OutArcIt(const Graph& graph, const Node& node) 
   470       OutArcIt(const Graph& graph, const Node& node)
   471 	: _graph(&graph) {
   471         : _graph(&graph) {
   472 	_graph->firstOut(*this, node);
   472         _graph->firstOut(*this, node);
   473       }
   473       }
   474 
   474 
   475       OutArcIt(const Graph& graph, const Arc& arc) 
   475       OutArcIt(const Graph& graph, const Arc& arc)
   476 	: Arc(arc), _graph(&graph) {}
   476         : Arc(arc), _graph(&graph) {}
   477 
   477 
   478       OutArcIt& operator++() { 
   478       OutArcIt& operator++() {
   479 	_graph->nextOut(*this);
   479         _graph->nextOut(*this);
   480 	return *this; 
   480         return *this;
   481       }
   481       }
   482 
   482 
   483     };
   483     };
   484 
   484 
   485 
   485 
   486     class InArcIt : public Arc { 
   486     class InArcIt : public Arc {
   487       const Graph* _graph;
   487       const Graph* _graph;
   488     public:
   488     public:
   489 
   489 
   490       InArcIt() { }
   490       InArcIt() { }
   491 
   491 
   492       InArcIt(Invalid i) : Arc(i) { }
   492       InArcIt(Invalid i) : Arc(i) { }
   493 
   493 
   494       InArcIt(const Graph& graph, const Node& node) 
   494       InArcIt(const Graph& graph, const Node& node)
   495 	: _graph(&graph) {
   495         : _graph(&graph) {
   496 	_graph->firstIn(*this, node);
   496         _graph->firstIn(*this, node);
   497       }
   497       }
   498 
   498 
   499       InArcIt(const Graph& graph, const Arc& arc) : 
   499       InArcIt(const Graph& graph, const Arc& arc) :
   500 	Arc(arc), _graph(&graph) {}
   500         Arc(arc), _graph(&graph) {}
   501 
   501 
   502       InArcIt& operator++() { 
   502       InArcIt& operator++() {
   503 	_graph->nextIn(*this);
   503         _graph->nextIn(*this);
   504 	return *this; 
   504         return *this;
   505       }
   505       }
   506 
   506 
   507     };
   507     };
   508 
   508 
   509 
   509 
   510     class EdgeIt : public Parent::Edge { 
   510     class EdgeIt : public Parent::Edge {
   511       const Graph* _graph;
   511       const Graph* _graph;
   512     public:
   512     public:
   513 
   513 
   514       EdgeIt() { }
   514       EdgeIt() { }
   515 
   515 
   516       EdgeIt(Invalid i) : Edge(i) { }
   516       EdgeIt(Invalid i) : Edge(i) { }
   517 
   517 
   518       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   518       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   519 	_graph->first(static_cast<Edge&>(*this));
   519         _graph->first(static_cast<Edge&>(*this));
   520       }
   520       }
   521 
   521 
   522       EdgeIt(const Graph& graph, const Edge& edge) : 
   522       EdgeIt(const Graph& graph, const Edge& edge) :
   523 	Edge(edge), _graph(&graph) { }
   523         Edge(edge), _graph(&graph) { }
   524 
   524 
   525       EdgeIt& operator++() { 
   525       EdgeIt& operator++() {
   526 	_graph->next(*this);
   526         _graph->next(*this);
   527 	return *this; 
   527         return *this;
   528       }
   528       }
   529 
   529 
   530     };
   530     };
   531 
   531 
   532     class IncEdgeIt : public Parent::Edge {
   532     class IncEdgeIt : public Parent::Edge {
   538       IncEdgeIt() { }
   538       IncEdgeIt() { }
   539 
   539 
   540       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   540       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   541 
   541 
   542       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   542       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   543 	_graph->firstInc(*this, _direction, node);
   543         _graph->firstInc(*this, _direction, node);
   544       }
   544       }
   545 
   545 
   546       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   546       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   547 	: _graph(&graph), Edge(edge) {
   547         : _graph(&graph), Edge(edge) {
   548 	_direction = (_graph->source(edge) == node);
   548         _direction = (_graph->source(edge) == node);
   549       }
   549       }
   550 
   550 
   551       IncEdgeIt& operator++() {
   551       IncEdgeIt& operator++() {
   552 	_graph->nextInc(*this, _direction);
   552         _graph->nextInc(*this, _direction);
   553 	return *this; 
   553         return *this;
   554       }
   554       }
   555     };
   555     };
   556 
   556 
   557     /// \brief Base node of the iterator
   557     /// \brief Base node of the iterator
   558     ///
   558     ///
   596     }
   596     }
   597 
   597 
   598     // Mappable extension
   598     // Mappable extension
   599 
   599 
   600     template <typename _Value>
   600     template <typename _Value>
   601     class NodeMap 
   601     class NodeMap
   602       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   602       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   603     public:
   603     public:
   604       typedef GraphExtender Graph;
   604       typedef GraphExtender Graph;
   605       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   605       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   606 
   606 
   607       NodeMap(const Graph& graph) 
   607       NodeMap(const Graph& graph)
   608 	: Parent(graph) {}
   608         : Parent(graph) {}
   609       NodeMap(const Graph& graph, const _Value& value) 
   609       NodeMap(const Graph& graph, const _Value& value)
   610 	: Parent(graph, value) {}
   610         : Parent(graph, value) {}
   611 
   611 
   612       NodeMap& operator=(const NodeMap& cmap) {
   612       NodeMap& operator=(const NodeMap& cmap) {
   613 	return operator=<NodeMap>(cmap);
   613         return operator=<NodeMap>(cmap);
   614       }
   614       }
   615 
   615 
   616       template <typename CMap>
   616       template <typename CMap>
   617       NodeMap& operator=(const CMap& cmap) {
   617       NodeMap& operator=(const CMap& cmap) {
   618         Parent::operator=(cmap);
   618         Parent::operator=(cmap);
   619 	return *this;
   619         return *this;
   620       }
   620       }
   621 
   621 
   622     };
   622     };
   623 
   623 
   624     template <typename _Value>
   624     template <typename _Value>
   625     class ArcMap 
   625     class ArcMap
   626       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   626       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   627     public:
   627     public:
   628       typedef GraphExtender Graph;
   628       typedef GraphExtender Graph;
   629       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   629       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   630 
   630 
   631       ArcMap(const Graph& graph) 
   631       ArcMap(const Graph& graph)
   632 	: Parent(graph) {}
   632         : Parent(graph) {}
   633       ArcMap(const Graph& graph, const _Value& value) 
   633       ArcMap(const Graph& graph, const _Value& value)
   634 	: Parent(graph, value) {}
   634         : Parent(graph, value) {}
   635 
   635 
   636       ArcMap& operator=(const ArcMap& cmap) {
   636       ArcMap& operator=(const ArcMap& cmap) {
   637 	return operator=<ArcMap>(cmap);
   637         return operator=<ArcMap>(cmap);
   638       }
   638       }
   639 
   639 
   640       template <typename CMap>
   640       template <typename CMap>
   641       ArcMap& operator=(const CMap& cmap) {
   641       ArcMap& operator=(const CMap& cmap) {
   642         Parent::operator=(cmap);
   642         Parent::operator=(cmap);
   643 	return *this;
   643         return *this;
   644       }
   644       }
   645     };
   645     };
   646 
   646 
   647 
   647 
   648     template <typename _Value>
   648     template <typename _Value>
   649     class EdgeMap 
   649     class EdgeMap
   650       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   650       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   651     public:
   651     public:
   652       typedef GraphExtender Graph;
   652       typedef GraphExtender Graph;
   653       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   653       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   654 
   654 
   655       EdgeMap(const Graph& graph) 
   655       EdgeMap(const Graph& graph)
   656 	: Parent(graph) {}
   656         : Parent(graph) {}
   657 
   657 
   658       EdgeMap(const Graph& graph, const _Value& value) 
   658       EdgeMap(const Graph& graph, const _Value& value)
   659 	: Parent(graph, value) {}
   659         : Parent(graph, value) {}
   660 
   660 
   661       EdgeMap& operator=(const EdgeMap& cmap) {
   661       EdgeMap& operator=(const EdgeMap& cmap) {
   662 	return operator=<EdgeMap>(cmap);
   662         return operator=<EdgeMap>(cmap);
   663       }
   663       }
   664 
   664 
   665       template <typename CMap>
   665       template <typename CMap>
   666       EdgeMap& operator=(const CMap& cmap) {
   666       EdgeMap& operator=(const CMap& cmap) {
   667         Parent::operator=(cmap);
   667         Parent::operator=(cmap);
   668 	return *this;
   668         return *this;
   669       }
   669       }
   670 
   670 
   671     };
   671     };
   672 
   672 
   673     // Alteration extension
   673     // Alteration extension
   681     Edge addEdge(const Node& from, const Node& to) {
   681     Edge addEdge(const Node& from, const Node& to) {
   682       Edge edge = Parent::addEdge(from, to);
   682       Edge edge = Parent::addEdge(from, to);
   683       notifier(Edge()).add(edge);
   683       notifier(Edge()).add(edge);
   684       std::vector<Arc> ev;
   684       std::vector<Arc> ev;
   685       ev.push_back(Parent::direct(edge, true));
   685       ev.push_back(Parent::direct(edge, true));
   686       ev.push_back(Parent::direct(edge, false));      
   686       ev.push_back(Parent::direct(edge, false));
   687       notifier(Arc()).add(ev);
   687       notifier(Arc()).add(ev);
   688       return edge;
   688       return edge;
   689     }
   689     }
   690     
   690 
   691     void clear() {
   691     void clear() {
   692       notifier(Arc()).clear();
   692       notifier(Arc()).clear();
   693       notifier(Edge()).clear();
   693       notifier(Edge()).clear();
   694       notifier(Node()).clear();
   694       notifier(Node()).clear();
   695       Parent::clear();
   695       Parent::clear();
   696     }
   696     }
   697 
   697 
   698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   699     void build(const Graph& graph, NodeRefMap& nodeRef, 
   699     void build(const Graph& graph, NodeRefMap& nodeRef,
   700                EdgeRefMap& edgeRef) {
   700                EdgeRefMap& edgeRef) {
   701       Parent::build(graph, nodeRef, edgeRef);
   701       Parent::build(graph, nodeRef, edgeRef);
   702       notifier(Node()).build();
   702       notifier(Node()).build();
   703       notifier(Edge()).build();
   703       notifier(Edge()).build();
   704       notifier(Arc()).build();
   704       notifier(Arc()).build();
   706 
   706 
   707     void erase(const Node& node) {
   707     void erase(const Node& node) {
   708       Arc arc;
   708       Arc arc;
   709       Parent::firstOut(arc, node);
   709       Parent::firstOut(arc, node);
   710       while (arc != INVALID ) {
   710       while (arc != INVALID ) {
   711 	erase(arc);
   711         erase(arc);
   712 	Parent::firstOut(arc, node);
   712         Parent::firstOut(arc, node);
   713       } 
   713       }
   714 
   714 
   715       Parent::firstIn(arc, node);
   715       Parent::firstIn(arc, node);
   716       while (arc != INVALID ) {
   716       while (arc != INVALID ) {
   717 	erase(arc);
   717         erase(arc);
   718 	Parent::firstIn(arc, node);
   718         Parent::firstIn(arc, node);
   719       }
   719       }
   720 
   720 
   721       notifier(Node()).erase(node);
   721       notifier(Node()).erase(node);
   722       Parent::erase(node);
   722       Parent::erase(node);
   723     }
   723     }
   724 
   724 
   725     void erase(const Edge& edge) {
   725     void erase(const Edge& edge) {
   726       std::vector<Arc> av;
   726       std::vector<Arc> av;
   727       av.push_back(Parent::direct(edge, true));
   727       av.push_back(Parent::direct(edge, true));
   728       av.push_back(Parent::direct(edge, false));      
   728       av.push_back(Parent::direct(edge, false));
   729       notifier(Arc()).erase(av);
   729       notifier(Arc()).erase(av);
   730       notifier(Edge()).erase(edge);
   730       notifier(Edge()).erase(edge);
   731       Parent::erase(edge);
   731       Parent::erase(edge);
   732     }
   732     }
   733 
   733 
   734     GraphExtender() {
   734     GraphExtender() {
   735       node_notifier.setContainer(*this); 
   735       node_notifier.setContainer(*this);
   736       arc_notifier.setContainer(*this);
   736       arc_notifier.setContainer(*this);
   737       edge_notifier.setContainer(*this);
   737       edge_notifier.setContainer(*this);
   738     } 
   738     }
   739 
   739 
   740     ~GraphExtender() {
   740     ~GraphExtender() {
   741       edge_notifier.clear();
   741       edge_notifier.clear();
   742       arc_notifier.clear();
   742       arc_notifier.clear();
   743       node_notifier.clear(); 
   743       node_notifier.clear();
   744     } 
   744     }
   745 
   745 
   746   };
   746   };
   747 
   747 
   748 }
   748 }
   749 
   749