lemon/bits/graph_extender.h
changeset 91 e28fc773f3c0
parent 77 2de55e4f57a7
child 107 31a2e6d28f61
equal deleted inserted replaced
1:4327a15d97f5 2:1b9fc79dc990
    62 
    62 
    63     Arc fromId(int id, Arc) const {
    63     Arc fromId(int id, Arc) const {
    64       return Parent::arcFromId(id);
    64       return Parent::arcFromId(id);
    65     }
    65     }
    66 
    66 
    67     Node oppositeNode(const Node &n, const Arc &e) const {
    67     Node oppositeNode(const Node &node, const Arc &arc) const {
    68       if (n == Parent::source(e))
    68       if (node == Parent::source(arc))
    69 	return Parent::target(e);
    69 	return Parent::target(arc);
    70       else if(n==Parent::target(e))
    70       else if(node == Parent::target(arc))
    71 	return Parent::source(e);
    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
    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& e) : 
   132       ArcIt(const Digraph& digraph, const Arc& arc) : 
   133 	Arc(e), 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
   191     ///
   191     ///
   192     /// Returns the base node (i.e. the source in this case) of the iterator
   192     /// Returns the base node (i.e. the source in this case) of the iterator
   193     Node baseNode(const OutArcIt &e) const {
   193     Node baseNode(const OutArcIt &arc) const {
   194       return Parent::source(e);
   194       return Parent::source(arc);
   195     }
   195     }
   196     /// \brief Running node of the iterator
   196     /// \brief Running node of the iterator
   197     ///
   197     ///
   198     /// Returns the running node (i.e. the target in this case) of the
   198     /// Returns the running node (i.e. the target in this case) of the
   199     /// iterator
   199     /// iterator
   200     Node runningNode(const OutArcIt &e) const {
   200     Node runningNode(const OutArcIt &arc) const {
   201       return Parent::target(e);
   201       return Parent::target(arc);
   202     }
   202     }
   203 
   203 
   204     /// \brief Base node of the iterator
   204     /// \brief Base node of the iterator
   205     ///
   205     ///
   206     /// Returns the base node (i.e. the target in this case) of the iterator
   206     /// Returns the base node (i.e. the target in this case) of the iterator
   207     Node baseNode(const InArcIt &e) const {
   207     Node baseNode(const InArcIt &arc) const {
   208       return Parent::target(e);
   208       return Parent::target(arc);
   209     }
   209     }
   210     /// \brief Running node of the iterator
   210     /// \brief Running node of the iterator
   211     ///
   211     ///
   212     /// Returns the running node (i.e. the source in this case) of the
   212     /// Returns the running node (i.e. the source in this case) of the
   213     /// iterator
   213     /// iterator
   214     Node runningNode(const InArcIt &e) const {
   214     Node runningNode(const InArcIt &arc) const {
   215       return Parent::source(e);
   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 
   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 Digraph;
   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;
   373 	return Parent::source(e);
   373 	return Parent::source(e);
   374       else
   374       else
   375 	return INVALID;
   375 	return INVALID;
   376     }
   376     }
   377 
   377 
   378     Arc oppositeArc(const Arc &e) const {
   378     Arc oppositeArc(const Arc &arc) const {
   379       return Parent::direct(e, !Parent::direction(e));
   379       return Parent::direct(arc, !Parent::direction(arc));
   380     }
   380     }
   381 
   381 
   382     using Parent::direct;
   382     using Parent::direct;
   383     Arc direct(const Edge &ue, const Node &s) const {
   383     Arc direct(const Edge &edge, const Node &node) const {
   384       return Parent::direct(ue, Parent::source(ue) == s);
   384       return Parent::direct(edge, Parent::source(edge) == node);
   385     }
   385     }
   386 
   386 
   387     // Alterable extension
   387     // Alterable extension
   388 
   388 
   389     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   389     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   412     }
   412     }
   413 
   413 
   414 
   414 
   415 
   415 
   416     class NodeIt : public Node { 
   416     class NodeIt : public Node { 
   417       const Digraph* digraph;
   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 Digraph& _digraph) : digraph(&_digraph) {
   424       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   425 	_digraph.first(static_cast<Node&>(*this));
   425 	_graph->first(static_cast<Node&>(*this));
   426       }
   426       }
   427 
   427 
   428       NodeIt(const Digraph& _digraph, const Node& node) 
   428       NodeIt(const Graph& graph, const Node& node) 
   429 	: Node(node), digraph(&_digraph) {}
   429 	: Node(node), _graph(&graph) {}
   430 
   430 
   431       NodeIt& operator++() { 
   431       NodeIt& operator++() { 
   432 	digraph->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 Digraph* digraph;
   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 Digraph& _digraph) : digraph(&_digraph) {
   447       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   448 	_digraph.first(static_cast<Arc&>(*this));
   448 	_graph->first(static_cast<Arc&>(*this));
   449       }
   449       }
   450 
   450 
   451       ArcIt(const Digraph& _digraph, const Arc& e) : 
   451       ArcIt(const Graph& graph, const Arc& arc) : 
   452 	Arc(e), digraph(&_digraph) { }
   452 	Arc(arc), _graph(&graph) { }
   453 
   453 
   454       ArcIt& operator++() { 
   454       ArcIt& operator++() { 
   455 	digraph->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 Digraph* digraph;
   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 Digraph& _digraph, const Node& node) 
   470       OutArcIt(const Graph& graph, const Node& node) 
   471 	: digraph(&_digraph) {
   471 	: _graph(&graph) {
   472 	_digraph.firstOut(*this, node);
   472 	_graph->firstOut(*this, node);
   473       }
   473       }
   474 
   474 
   475       OutArcIt(const Digraph& _digraph, const Arc& arc) 
   475       OutArcIt(const Graph& graph, const Arc& arc) 
   476 	: Arc(arc), digraph(&_digraph) {}
   476 	: Arc(arc), _graph(&graph) {}
   477 
   477 
   478       OutArcIt& operator++() { 
   478       OutArcIt& operator++() { 
   479 	digraph->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 Digraph* digraph;
   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 Digraph& _digraph, const Node& node) 
   494       InArcIt(const Graph& graph, const Node& node) 
   495 	: digraph(&_digraph) {
   495 	: _graph(&graph) {
   496 	_digraph.firstIn(*this, node);
   496 	_graph->firstIn(*this, node);
   497       }
   497       }
   498 
   498 
   499       InArcIt(const Digraph& _digraph, const Arc& arc) : 
   499       InArcIt(const Graph& graph, const Arc& arc) : 
   500 	Arc(arc), digraph(&_digraph) {}
   500 	Arc(arc), _graph(&graph) {}
   501 
   501 
   502       InArcIt& operator++() { 
   502       InArcIt& operator++() { 
   503 	digraph->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 Digraph* digraph;
   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 Digraph& _digraph) : digraph(&_digraph) {
   518       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   519 	_digraph.first(static_cast<Edge&>(*this));
   519 	_graph->first(static_cast<Edge&>(*this));
   520       }
   520       }
   521 
   521 
   522       EdgeIt(const Digraph& _digraph, const Edge& e) : 
   522       EdgeIt(const Graph& graph, const Edge& edge) : 
   523 	Edge(e), digraph(&_digraph) { }
   523 	Edge(edge), _graph(&graph) { }
   524 
   524 
   525       EdgeIt& operator++() { 
   525       EdgeIt& operator++() { 
   526 	digraph->next(*this);
   526 	_graph->next(*this);
   527 	return *this; 
   527 	return *this; 
   528       }
   528       }
   529 
   529 
   530     };
   530     };
   531 
   531 
   532     class IncArcIt : public Parent::Edge {
   532     class IncEdgeIt : public Parent::Edge {
   533       friend class GraphExtender;
   533       friend class GraphExtender;
   534       const Digraph* digraph;
   534       const Graph* _graph;
   535       bool direction;
   535       bool _direction;
   536     public:
   536     public:
   537 
   537 
   538       IncArcIt() { }
   538       IncEdgeIt() { }
   539 
   539 
   540       IncArcIt(Invalid i) : Edge(i), direction(false) { }
   540       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   541 
   541 
   542       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
   542       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   543 	_digraph.firstInc(*this, direction, n);
   543 	_graph->firstInc(*this, _direction, node);
   544       }
   544       }
   545 
   545 
   546       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
   546       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   547 	: digraph(&_digraph), Edge(ue) {
   547 	: _graph(&graph), Edge(edge) {
   548 	direction = (_digraph.source(ue) == n);
   548 	_direction = (_graph->source(edge) == node);
   549       }
   549       }
   550 
   550 
   551       IncArcIt& operator++() {
   551       IncEdgeIt& operator++() {
   552 	digraph->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     ///
   559     /// Returns the base node (ie. the source in this case) of the iterator
   559     /// Returns the base node (ie. the source in this case) of the iterator
   560     Node baseNode(const OutArcIt &e) const {
   560     Node baseNode(const OutArcIt &arc) const {
   561       return Parent::source(static_cast<const Arc&>(e));
   561       return Parent::source(static_cast<const Arc&>(arc));
   562     }
   562     }
   563     /// \brief Running node of the iterator
   563     /// \brief Running node of the iterator
   564     ///
   564     ///
   565     /// Returns the running node (ie. the target in this case) of the
   565     /// Returns the running node (ie. the target in this case) of the
   566     /// iterator
   566     /// iterator
   567     Node runningNode(const OutArcIt &e) const {
   567     Node runningNode(const OutArcIt &arc) const {
   568       return Parent::target(static_cast<const Arc&>(e));
   568       return Parent::target(static_cast<const Arc&>(arc));
   569     }
   569     }
   570 
   570 
   571     /// \brief Base node of the iterator
   571     /// \brief Base node of the iterator
   572     ///
   572     ///
   573     /// Returns the base node (ie. the target in this case) of the iterator
   573     /// Returns the base node (ie. the target in this case) of the iterator
   574     Node baseNode(const InArcIt &e) const {
   574     Node baseNode(const InArcIt &arc) const {
   575       return Parent::target(static_cast<const Arc&>(e));
   575       return Parent::target(static_cast<const Arc&>(arc));
   576     }
   576     }
   577     /// \brief Running node of the iterator
   577     /// \brief Running node of the iterator
   578     ///
   578     ///
   579     /// Returns the running node (ie. the source in this case) of the
   579     /// Returns the running node (ie. the source in this case) of the
   580     /// iterator
   580     /// iterator
   581     Node runningNode(const InArcIt &e) const {
   581     Node runningNode(const InArcIt &arc) const {
   582       return Parent::source(static_cast<const Arc&>(e));
   582       return Parent::source(static_cast<const Arc&>(arc));
   583     }
   583     }
   584 
   584 
   585     /// Base node of the iterator
   585     /// Base node of the iterator
   586     ///
   586     ///
   587     /// Returns the base node of the iterator
   587     /// Returns the base node of the iterator
   588     Node baseNode(const IncArcIt &e) const {
   588     Node baseNode(const IncEdgeIt &edge) const {
   589       return e.direction ? source(e) : target(e);
   589       return edge._direction ? source(edge) : target(edge);
   590     }
   590     }
   591     /// Running node of the iterator
   591     /// Running node of the iterator
   592     ///
   592     ///
   593     /// Returns the running node of the iterator
   593     /// Returns the running node of the iterator
   594     Node runningNode(const IncArcIt &e) const {
   594     Node runningNode(const IncEdgeIt &edge) const {
   595       return e.direction ? target(e) : source(e);
   595       return edge._direction ? target(edge) : source(edge);
   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<Digraph, Node, _Value> > {
   602       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   603     public:
   603     public:
   604       typedef GraphExtender Digraph;
   604       typedef GraphExtender Graph;
   605       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   605       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   606 
   606 
   607       NodeMap(const Digraph& digraph) 
   607       NodeMap(const Graph& graph) 
   608 	: Parent(digraph) {}
   608 	: Parent(graph) {}
   609       NodeMap(const Digraph& digraph, const _Value& value) 
   609       NodeMap(const Graph& graph, const _Value& value) 
   610 	: Parent(digraph, 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 
   621 
   621 
   622     };
   622     };
   623 
   623 
   624     template <typename _Value>
   624     template <typename _Value>
   625     class ArcMap 
   625     class ArcMap 
   626       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   626       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   627     public:
   627     public:
   628       typedef GraphExtender Digraph;
   628       typedef GraphExtender Graph;
   629       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   629       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   630 
   630 
   631       ArcMap(const Digraph& digraph) 
   631       ArcMap(const Graph& graph) 
   632 	: Parent(digraph) {}
   632 	: Parent(graph) {}
   633       ArcMap(const Digraph& digraph, const _Value& value) 
   633       ArcMap(const Graph& graph, const _Value& value) 
   634 	: Parent(digraph, 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 
   645     };
   645     };
   646 
   646 
   647 
   647 
   648     template <typename _Value>
   648     template <typename _Value>
   649     class EdgeMap 
   649     class EdgeMap 
   650       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
   650       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   651     public:
   651     public:
   652       typedef GraphExtender Digraph;
   652       typedef GraphExtender Graph;
   653       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
   653       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   654 
   654 
   655       EdgeMap(const Digraph& digraph) 
   655       EdgeMap(const Graph& graph) 
   656 	: Parent(digraph) {}
   656 	: Parent(graph) {}
   657 
   657 
   658       EdgeMap(const Digraph& digraph, const _Value& value) 
   658       EdgeMap(const Graph& graph, const _Value& value) 
   659 	: Parent(digraph, 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 
   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 Digraph, typename NodeRefMap, typename EdgeRefMap>
   698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   699     void build(const Digraph& digraph, NodeRefMap& nodeRef, 
   699     void build(const Graph& graph, NodeRefMap& nodeRef, 
   700                EdgeRefMap& edgeRef) {
   700                EdgeRefMap& edgeRef) {
   701       Parent::build(digraph, 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();
   705     }
   705     }
   706 
   706 
   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> ev;
   726       std::vector<Arc> av;
   727       ev.push_back(Parent::direct(edge, true));
   727       av.push_back(Parent::direct(edge, true));
   728       ev.push_back(Parent::direct(edge, false));      
   728       av.push_back(Parent::direct(edge, false));      
   729       notifier(Arc()).erase(ev);
   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() {