deba@57: /* -*- C++ -*-
deba@57:  *
deba@57:  * This file is a part of LEMON, a generic C++ optimization library
deba@57:  *
deba@57:  * Copyright (C) 2003-2007
deba@57:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@57:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@57:  *
deba@57:  * Permission to use, modify and distribute this software is granted
deba@57:  * provided that this copyright notice appears in all copies. For
deba@57:  * precise terms see the accompanying LICENSE file.
deba@57:  *
deba@57:  * This software is provided "AS IS" with no warranty of any kind,
deba@57:  * express or implied, and with no claim as to its suitability for any
deba@57:  * purpose.
deba@57:  *
deba@57:  */
deba@57: 
deba@57: #ifndef LEMON_BITS_GRAPH_EXTENDER_H
deba@57: #define LEMON_BITS_GRAPH_EXTENDER_H
deba@57: 
deba@57: #include <lemon/bits/invalid.h>
deba@57: 
deba@57: #include <lemon/bits/map_extender.h>
deba@57: #include <lemon/bits/default_map.h>
deba@57: 
deba@57: #include <lemon/concept_check.h>
deba@57: #include <lemon/concepts/maps.h>
deba@57: 
deba@57: ///\ingroup graphbits
deba@57: ///\file
deba@57: ///\brief Extenders for the digraph types
deba@57: namespace lemon {
deba@57: 
deba@57:   /// \ingroup graphbits
deba@57:   ///
deba@57:   /// \brief Extender for the Digraphs
deba@57:   template <typename Base>
deba@57:   class DigraphExtender : public Base {
deba@57:   public:
deba@57: 
deba@57:     typedef Base Parent;
deba@57:     typedef DigraphExtender Digraph;
deba@57: 
deba@57:     // Base extensions
deba@57: 
deba@57:     typedef typename Parent::Node Node;
deba@57:     typedef typename Parent::Arc Arc;
deba@57: 
deba@57:     int maxId(Node) const {
deba@57:       return Parent::maxNodeId();
deba@57:     }
deba@57: 
deba@57:     int maxId(Arc) const {
deba@57:       return Parent::maxArcId();
deba@57:     }
deba@57: 
deba@57:     Node fromId(int id, Node) const {
deba@57:       return Parent::nodeFromId(id);
deba@57:     }
deba@57: 
deba@57:     Arc fromId(int id, Arc) const {
deba@57:       return Parent::arcFromId(id);
deba@57:     }
deba@57: 
deba@57:     Node oppositeNode(const Node &n, const Arc &e) const {
deba@57:       if (n == Parent::source(e))
deba@57: 	return Parent::target(e);
deba@57:       else if(n==Parent::target(e))
deba@57: 	return Parent::source(e);
deba@57:       else
deba@57: 	return INVALID;
deba@57:     }
deba@57: 
deba@57:     // Alterable extension
deba@57: 
deba@57:     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
deba@57:     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
deba@57: 
deba@57: 
deba@57:   protected:
deba@57: 
deba@57:     mutable NodeNotifier node_notifier;
deba@57:     mutable ArcNotifier arc_notifier;
deba@57: 
deba@57:   public:
deba@57: 
deba@57:     NodeNotifier& notifier(Node) const {
deba@57:       return node_notifier;
deba@57:     }
deba@57:     
deba@57:     ArcNotifier& notifier(Arc) const {
deba@57:       return arc_notifier;
deba@57:     }
deba@57: 
deba@57:     class NodeIt : public Node { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       NodeIt() {}
deba@57: 
deba@57:       NodeIt(Invalid i) : Node(i) { }
deba@57: 
deba@57:       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57: 	_digraph.first(static_cast<Node&>(*this));
deba@57:       }
deba@57: 
deba@57:       NodeIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: Node(node), digraph(&_digraph) {}
deba@57: 
deba@57:       NodeIt& operator++() { 
deba@57: 	digraph->next(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class ArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       ArcIt() { }
deba@57: 
deba@57:       ArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57: 	_digraph.first(static_cast<Arc&>(*this));
deba@57:       }
deba@57: 
deba@57:       ArcIt(const Digraph& _digraph, const Arc& e) : 
deba@57: 	Arc(e), digraph(&_digraph) { }
deba@57: 
deba@57:       ArcIt& operator++() { 
deba@57: 	digraph->next(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class OutArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       OutArcIt() { }
deba@57: 
deba@57:       OutArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       OutArcIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: digraph(&_digraph) {
deba@57: 	_digraph.firstOut(*this, node);
deba@57:       }
deba@57: 
deba@57:       OutArcIt(const Digraph& _digraph, const Arc& arc) 
deba@57: 	: Arc(arc), digraph(&_digraph) {}
deba@57: 
deba@57:       OutArcIt& operator++() { 
deba@57: 	digraph->nextOut(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class InArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       InArcIt() { }
deba@57: 
deba@57:       InArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       InArcIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: digraph(&_digraph) {
deba@57: 	_digraph.firstIn(*this, node);
deba@57:       }
deba@57: 
deba@57:       InArcIt(const Digraph& _digraph, const Arc& arc) : 
deba@57: 	Arc(arc), digraph(&_digraph) {}
deba@57: 
deba@57:       InArcIt& operator++() { 
deba@57: 	digraph->nextIn(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     /// \brief Base node of the iterator
deba@57:     ///
deba@57:     /// Returns the base node (i.e. the source in this case) of the iterator
deba@57:     Node baseNode(const OutArcIt &e) const {
deba@57:       return Parent::source(e);
deba@57:     }
deba@57:     /// \brief Running node of the iterator
deba@57:     ///
deba@57:     /// Returns the running node (i.e. the target in this case) of the
deba@57:     /// iterator
deba@57:     Node runningNode(const OutArcIt &e) const {
deba@57:       return Parent::target(e);
deba@57:     }
deba@57: 
deba@57:     /// \brief Base node of the iterator
deba@57:     ///
deba@57:     /// Returns the base node (i.e. the target in this case) of the iterator
deba@57:     Node baseNode(const InArcIt &e) const {
deba@57:       return Parent::target(e);
deba@57:     }
deba@57:     /// \brief Running node of the iterator
deba@57:     ///
deba@57:     /// Returns the running node (i.e. the source in this case) of the
deba@57:     /// iterator
deba@57:     Node runningNode(const InArcIt &e) const {
deba@57:       return Parent::source(e);
deba@57:     }
deba@57: 
deba@57:     
deba@57:     template <typename _Value>
deba@57:     class NodeMap 
deba@57:       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
deba@57:     public:
deba@57:       typedef DigraphExtender Digraph;
deba@57:       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57: 
deba@57:       explicit NodeMap(const Digraph& digraph) 
deba@57: 	: Parent(digraph) {}
deba@57:       NodeMap(const Digraph& digraph, const _Value& value) 
deba@57: 	: Parent(digraph, value) {}
deba@57: 
deba@57:       NodeMap& operator=(const NodeMap& cmap) {
deba@57: 	return operator=<NodeMap>(cmap);
deba@57:       }
deba@57: 
deba@57:       template <typename CMap>
deba@57:       NodeMap& operator=(const CMap& cmap) {
deba@57:         Parent::operator=(cmap);
deba@57: 	return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     template <typename _Value>
deba@57:     class ArcMap 
deba@57:       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
deba@57:     public:
deba@57:       typedef DigraphExtender Digraph;
deba@57:       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57: 
deba@57:       explicit ArcMap(const Digraph& digraph) 
deba@57: 	: Parent(digraph) {}
deba@57:       ArcMap(const Digraph& digraph, const _Value& value) 
deba@57: 	: Parent(digraph, value) {}
deba@57: 
deba@57:       ArcMap& operator=(const ArcMap& cmap) {
deba@57: 	return operator=<ArcMap>(cmap);
deba@57:       }
deba@57: 
deba@57:       template <typename CMap>
deba@57:       ArcMap& operator=(const CMap& cmap) {
deba@57:         Parent::operator=(cmap);
deba@57: 	return *this;
deba@57:       }
deba@57:     };
deba@57: 
deba@57: 
deba@57:     Node addNode() {
deba@57:       Node node = Parent::addNode();
deba@57:       notifier(Node()).add(node);
deba@57:       return node;
deba@57:     }
deba@57:     
deba@57:     Arc addArc(const Node& from, const Node& to) {
deba@57:       Arc arc = Parent::addArc(from, to);
deba@57:       notifier(Arc()).add(arc);
deba@57:       return arc;
deba@57:     }
deba@57: 
deba@57:     void clear() {
deba@57:       notifier(Arc()).clear();
deba@57:       notifier(Node()).clear();
deba@57:       Parent::clear();
deba@57:     }
deba@57: 
deba@57:     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
deba@57:     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
deba@57:       Parent::build(digraph, nodeRef, arcRef);
deba@57:       notifier(Node()).build();
deba@57:       notifier(Arc()).build();
deba@57:     }
deba@57: 
deba@57:     void erase(const Node& node) {
deba@57:       Arc arc;
deba@57:       Parent::firstOut(arc, node);
deba@57:       while (arc != INVALID ) {
deba@57: 	erase(arc);
deba@57: 	Parent::firstOut(arc, node);
deba@57:       } 
deba@57: 
deba@57:       Parent::firstIn(arc, node);
deba@57:       while (arc != INVALID ) {
deba@57: 	erase(arc);
deba@57: 	Parent::firstIn(arc, node);
deba@57:       }
deba@57: 
deba@57:       notifier(Node()).erase(node);
deba@57:       Parent::erase(node);
deba@57:     }
deba@57:     
deba@57:     void erase(const Arc& arc) {
deba@57:       notifier(Arc()).erase(arc);
deba@57:       Parent::erase(arc);
deba@57:     }
deba@57: 
deba@57:     DigraphExtender() {
deba@57:       node_notifier.setContainer(*this);
deba@57:       arc_notifier.setContainer(*this);
deba@57:     } 
deba@57:     
deba@57: 
deba@57:     ~DigraphExtender() {
deba@57:       arc_notifier.clear();
deba@57:       node_notifier.clear();
deba@57:     }
deba@57:   };
deba@57: 
deba@57:   /// \ingroup graphbits
deba@57:   ///
deba@57:   /// \brief Extender for the Graphs
deba@57:   template <typename Base> 
deba@57:   class GraphExtender : public Base {
deba@57:   public:
deba@57:     
deba@57:     typedef Base Parent;
deba@57:     typedef GraphExtender Digraph;
deba@57: 
deba@57:     typedef typename Parent::Node Node;
deba@57:     typedef typename Parent::Arc Arc;
deba@57:     typedef typename Parent::Edge Edge;
deba@57: 
deba@57:     // Graph extension    
deba@57: 
deba@57:     int maxId(Node) const {
deba@57:       return Parent::maxNodeId();
deba@57:     }
deba@57: 
deba@57:     int maxId(Arc) const {
deba@57:       return Parent::maxArcId();
deba@57:     }
deba@57: 
deba@57:     int maxId(Edge) const {
deba@57:       return Parent::maxEdgeId();
deba@57:     }
deba@57: 
deba@57:     Node fromId(int id, Node) const {
deba@57:       return Parent::nodeFromId(id);
deba@57:     }
deba@57: 
deba@57:     Arc fromId(int id, Arc) const {
deba@57:       return Parent::arcFromId(id);
deba@57:     }
deba@57: 
deba@57:     Edge fromId(int id, Edge) const {
deba@57:       return Parent::edgeFromId(id);
deba@57:     }
deba@57: 
deba@57:     Node oppositeNode(const Node &n, const Edge &e) const {
deba@57:       if( n == Parent::source(e))
deba@57: 	return Parent::target(e);
deba@57:       else if( n == Parent::target(e))
deba@57: 	return Parent::source(e);
deba@57:       else
deba@57: 	return INVALID;
deba@57:     }
deba@57: 
deba@57:     Arc oppositeArc(const Arc &e) const {
deba@57:       return Parent::direct(e, !Parent::direction(e));
deba@57:     }
deba@57: 
deba@57:     using Parent::direct;
deba@57:     Arc direct(const Edge &ue, const Node &s) const {
deba@57:       return Parent::direct(ue, Parent::source(ue) == s);
deba@57:     }
deba@57: 
deba@57:     // Alterable extension
deba@57: 
deba@57:     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
deba@57:     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
deba@57:     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
deba@57: 
deba@57: 
deba@57:   protected:
deba@57: 
deba@57:     mutable NodeNotifier node_notifier;
deba@57:     mutable ArcNotifier arc_notifier;
deba@57:     mutable EdgeNotifier edge_notifier;
deba@57: 
deba@57:   public:
deba@57: 
deba@57:     NodeNotifier& notifier(Node) const {
deba@57:       return node_notifier;
deba@57:     }
deba@57:     
deba@57:     ArcNotifier& notifier(Arc) const {
deba@57:       return arc_notifier;
deba@57:     }
deba@57: 
deba@57:     EdgeNotifier& notifier(Edge) const {
deba@57:       return edge_notifier;
deba@57:     }
deba@57: 
deba@57: 
deba@57: 
deba@57:     class NodeIt : public Node { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       NodeIt() {}
deba@57: 
deba@57:       NodeIt(Invalid i) : Node(i) { }
deba@57: 
deba@57:       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57: 	_digraph.first(static_cast<Node&>(*this));
deba@57:       }
deba@57: 
deba@57:       NodeIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: Node(node), digraph(&_digraph) {}
deba@57: 
deba@57:       NodeIt& operator++() { 
deba@57: 	digraph->next(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class ArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       ArcIt() { }
deba@57: 
deba@57:       ArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57: 	_digraph.first(static_cast<Arc&>(*this));
deba@57:       }
deba@57: 
deba@57:       ArcIt(const Digraph& _digraph, const Arc& e) : 
deba@57: 	Arc(e), digraph(&_digraph) { }
deba@57: 
deba@57:       ArcIt& operator++() { 
deba@57: 	digraph->next(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class OutArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       OutArcIt() { }
deba@57: 
deba@57:       OutArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       OutArcIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: digraph(&_digraph) {
deba@57: 	_digraph.firstOut(*this, node);
deba@57:       }
deba@57: 
deba@57:       OutArcIt(const Digraph& _digraph, const Arc& arc) 
deba@57: 	: Arc(arc), digraph(&_digraph) {}
deba@57: 
deba@57:       OutArcIt& operator++() { 
deba@57: 	digraph->nextOut(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class InArcIt : public Arc { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       InArcIt() { }
deba@57: 
deba@57:       InArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@57:       InArcIt(const Digraph& _digraph, const Node& node) 
deba@57: 	: digraph(&_digraph) {
deba@57: 	_digraph.firstIn(*this, node);
deba@57:       }
deba@57: 
deba@57:       InArcIt(const Digraph& _digraph, const Arc& arc) : 
deba@57: 	Arc(arc), digraph(&_digraph) {}
deba@57: 
deba@57:       InArcIt& operator++() { 
deba@57: 	digraph->nextIn(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
deba@57:     class EdgeIt : public Parent::Edge { 
deba@57:       const Digraph* digraph;
deba@57:     public:
deba@57: 
deba@57:       EdgeIt() { }
deba@57: 
deba@57:       EdgeIt(Invalid i) : Edge(i) { }
deba@57: 
deba@57:       explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
deba@57: 	_digraph.first(static_cast<Edge&>(*this));
deba@57:       }
deba@57: 
deba@57:       EdgeIt(const Digraph& _digraph, const Edge& e) : 
deba@57: 	Edge(e), digraph(&_digraph) { }
deba@57: 
deba@57:       EdgeIt& operator++() { 
deba@57: 	digraph->next(*this);
deba@57: 	return *this; 
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     class IncArcIt : public Parent::Edge {
deba@57:       friend class GraphExtender;
deba@57:       const Digraph* digraph;
deba@57:       bool direction;
deba@57:     public:
deba@57: 
deba@57:       IncArcIt() { }
deba@57: 
deba@57:       IncArcIt(Invalid i) : Edge(i), direction(false) { }
deba@57: 
deba@57:       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
deba@57: 	_digraph.firstInc(*this, direction, n);
deba@57:       }
deba@57: 
deba@57:       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
deba@57: 	: digraph(&_digraph), Edge(ue) {
deba@57: 	direction = (_digraph.source(ue) == n);
deba@57:       }
deba@57: 
deba@57:       IncArcIt& operator++() {
deba@57: 	digraph->nextInc(*this, direction);
deba@57: 	return *this; 
deba@57:       }
deba@57:     };
deba@57: 
deba@57:     /// \brief Base node of the iterator
deba@57:     ///
deba@57:     /// Returns the base node (ie. the source in this case) of the iterator
deba@57:     Node baseNode(const OutArcIt &e) const {
deba@57:       return Parent::source(static_cast<const Arc&>(e));
deba@57:     }
deba@57:     /// \brief Running node of the iterator
deba@57:     ///
deba@57:     /// Returns the running node (ie. the target in this case) of the
deba@57:     /// iterator
deba@57:     Node runningNode(const OutArcIt &e) const {
deba@57:       return Parent::target(static_cast<const Arc&>(e));
deba@57:     }
deba@57: 
deba@57:     /// \brief Base node of the iterator
deba@57:     ///
deba@57:     /// Returns the base node (ie. the target in this case) of the iterator
deba@57:     Node baseNode(const InArcIt &e) const {
deba@57:       return Parent::target(static_cast<const Arc&>(e));
deba@57:     }
deba@57:     /// \brief Running node of the iterator
deba@57:     ///
deba@57:     /// Returns the running node (ie. the source in this case) of the
deba@57:     /// iterator
deba@57:     Node runningNode(const InArcIt &e) const {
deba@57:       return Parent::source(static_cast<const Arc&>(e));
deba@57:     }
deba@57: 
deba@57:     /// Base node of the iterator
deba@57:     ///
deba@57:     /// Returns the base node of the iterator
deba@57:     Node baseNode(const IncArcIt &e) const {
deba@57:       return e.direction ? source(e) : target(e);
deba@57:     }
deba@57:     /// Running node of the iterator
deba@57:     ///
deba@57:     /// Returns the running node of the iterator
deba@57:     Node runningNode(const IncArcIt &e) const {
deba@57:       return e.direction ? target(e) : source(e);
deba@57:     }
deba@57: 
deba@57:     // Mappable extension
deba@57: 
deba@57:     template <typename _Value>
deba@57:     class NodeMap 
deba@57:       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
deba@57:     public:
deba@57:       typedef GraphExtender Digraph;
deba@57:       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57: 
deba@57:       NodeMap(const Digraph& digraph) 
deba@57: 	: Parent(digraph) {}
deba@57:       NodeMap(const Digraph& digraph, const _Value& value) 
deba@57: 	: Parent(digraph, value) {}
deba@57: 
deba@57:       NodeMap& operator=(const NodeMap& cmap) {
deba@57: 	return operator=<NodeMap>(cmap);
deba@57:       }
deba@57: 
deba@57:       template <typename CMap>
deba@57:       NodeMap& operator=(const CMap& cmap) {
deba@57:         Parent::operator=(cmap);
deba@57: 	return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     template <typename _Value>
deba@57:     class ArcMap 
deba@57:       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
deba@57:     public:
deba@57:       typedef GraphExtender Digraph;
deba@57:       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57: 
deba@57:       ArcMap(const Digraph& digraph) 
deba@57: 	: Parent(digraph) {}
deba@57:       ArcMap(const Digraph& digraph, const _Value& value) 
deba@57: 	: Parent(digraph, value) {}
deba@57: 
deba@57:       ArcMap& operator=(const ArcMap& cmap) {
deba@57: 	return operator=<ArcMap>(cmap);
deba@57:       }
deba@57: 
deba@57:       template <typename CMap>
deba@57:       ArcMap& operator=(const CMap& cmap) {
deba@57:         Parent::operator=(cmap);
deba@57: 	return *this;
deba@57:       }
deba@57:     };
deba@57: 
deba@57: 
deba@57:     template <typename _Value>
deba@57:     class EdgeMap 
deba@57:       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
deba@57:     public:
deba@57:       typedef GraphExtender Digraph;
deba@57:       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
deba@57: 
deba@57:       EdgeMap(const Digraph& digraph) 
deba@57: 	: Parent(digraph) {}
deba@57: 
deba@57:       EdgeMap(const Digraph& digraph, const _Value& value) 
deba@57: 	: Parent(digraph, value) {}
deba@57: 
deba@57:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@57: 	return operator=<EdgeMap>(cmap);
deba@57:       }
deba@57: 
deba@57:       template <typename CMap>
deba@57:       EdgeMap& operator=(const CMap& cmap) {
deba@57:         Parent::operator=(cmap);
deba@57: 	return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     // Alteration extension
deba@57: 
deba@57:     Node addNode() {
deba@57:       Node node = Parent::addNode();
deba@57:       notifier(Node()).add(node);
deba@57:       return node;
deba@57:     }
deba@57: 
deba@57:     Edge addEdge(const Node& from, const Node& to) {
deba@57:       Edge edge = Parent::addEdge(from, to);
deba@57:       notifier(Edge()).add(edge);
deba@57:       std::vector<Arc> ev;
deba@57:       ev.push_back(Parent::direct(edge, true));
deba@57:       ev.push_back(Parent::direct(edge, false));      
deba@57:       notifier(Arc()).add(ev);
deba@57:       return edge;
deba@57:     }
deba@57:     
deba@57:     void clear() {
deba@57:       notifier(Arc()).clear();
deba@57:       notifier(Edge()).clear();
deba@57:       notifier(Node()).clear();
deba@57:       Parent::clear();
deba@57:     }
deba@57: 
deba@57:     template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
deba@57:     void build(const Digraph& digraph, NodeRefMap& nodeRef, 
deba@57:                EdgeRefMap& edgeRef) {
deba@57:       Parent::build(digraph, nodeRef, edgeRef);
deba@57:       notifier(Node()).build();
deba@57:       notifier(Edge()).build();
deba@57:       notifier(Arc()).build();
deba@57:     }
deba@57: 
deba@57:     void erase(const Node& node) {
deba@57:       Arc arc;
deba@57:       Parent::firstOut(arc, node);
deba@57:       while (arc != INVALID ) {
deba@57: 	erase(arc);
deba@57: 	Parent::firstOut(arc, node);
deba@57:       } 
deba@57: 
deba@57:       Parent::firstIn(arc, node);
deba@57:       while (arc != INVALID ) {
deba@57: 	erase(arc);
deba@57: 	Parent::firstIn(arc, node);
deba@57:       }
deba@57: 
deba@57:       notifier(Node()).erase(node);
deba@57:       Parent::erase(node);
deba@57:     }
deba@57: 
deba@57:     void erase(const Edge& edge) {
deba@57:       std::vector<Arc> ev;
deba@57:       ev.push_back(Parent::direct(edge, true));
deba@57:       ev.push_back(Parent::direct(edge, false));      
deba@57:       notifier(Arc()).erase(ev);
deba@57:       notifier(Edge()).erase(edge);
deba@57:       Parent::erase(edge);
deba@57:     }
deba@57: 
deba@57:     GraphExtender() {
deba@57:       node_notifier.setContainer(*this); 
deba@57:       arc_notifier.setContainer(*this);
deba@57:       edge_notifier.setContainer(*this);
deba@57:     } 
deba@57: 
deba@57:     ~GraphExtender() {
deba@57:       edge_notifier.clear();
deba@57:       arc_notifier.clear();
deba@57:       node_notifier.clear(); 
deba@57:     } 
deba@57: 
deba@57:   };
deba@57: 
deba@57: }
deba@57: 
deba@57: #endif