alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@57:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
deba@57:  *
alpar@107:  * Copyright (C) 2003-2008
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@220: #include <lemon/core.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: 
kpeter@314: //\ingroup graphbits
kpeter@314: //\file
kpeter@361: //\brief Extenders for the graph types
deba@57: namespace lemon {
deba@57: 
kpeter@314:   // \ingroup graphbits
kpeter@314:   //
kpeter@361:   // \brief Extender for the digraph implementations
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@78:     Node oppositeNode(const Node &node, const Arc &arc) const {
deba@78:       if (node == Parent::source(arc))
alpar@209:         return Parent::target(arc);
deba@78:       else if(node == Parent::target(arc))
alpar@209:         return Parent::source(arc);
deba@57:       else
alpar@209:         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:     }
alpar@209: 
deba@57:     ArcNotifier& notifier(Arc) const {
deba@57:       return arc_notifier;
deba@57:     }
deba@57: 
alpar@209:     class NodeIt : public Node {
deba@78:       const Digraph* _digraph;
deba@57:     public:
deba@57: 
deba@57:       NodeIt() {}
deba@57: 
deba@57:       NodeIt(Invalid i) : Node(i) { }
deba@57: 
deba@78:       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
alpar@209:         _digraph->first(static_cast<Node&>(*this));
deba@57:       }
deba@57: 
alpar@209:       NodeIt(const Digraph& digraph, const Node& node)
alpar@209:         : Node(node), _digraph(&digraph) {}
deba@57: 
alpar@209:       NodeIt& operator++() {
alpar@209:         _digraph->next(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class ArcIt : public Arc {
deba@78:       const Digraph* _digraph;
deba@57:     public:
deba@57: 
deba@57:       ArcIt() { }
deba@57: 
deba@57:       ArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@78:       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
alpar@209:         _digraph->first(static_cast<Arc&>(*this));
deba@57:       }
deba@57: 
alpar@209:       ArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209:         Arc(arc), _digraph(&digraph) { }
deba@57: 
alpar@209:       ArcIt& operator++() {
alpar@209:         _digraph->next(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class OutArcIt : public Arc {
deba@78:       const Digraph* _digraph;
deba@57:     public:
deba@57: 
deba@57:       OutArcIt() { }
deba@57: 
deba@57:       OutArcIt(Invalid i) : Arc(i) { }
deba@57: 
alpar@209:       OutArcIt(const Digraph& digraph, const Node& node)
alpar@209:         : _digraph(&digraph) {
alpar@209:         _digraph->firstOut(*this, node);
deba@57:       }
deba@57: 
alpar@209:       OutArcIt(const Digraph& digraph, const Arc& arc)
alpar@209:         : Arc(arc), _digraph(&digraph) {}
deba@57: 
alpar@209:       OutArcIt& operator++() {
alpar@209:         _digraph->nextOut(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class InArcIt : public Arc {
deba@78:       const Digraph* _digraph;
deba@57:     public:
deba@57: 
deba@57:       InArcIt() { }
deba@57: 
deba@57:       InArcIt(Invalid i) : Arc(i) { }
deba@57: 
alpar@209:       InArcIt(const Digraph& digraph, const Node& node)
alpar@209:         : _digraph(&digraph) {
alpar@209:         _digraph->firstIn(*this, node);
deba@57:       }
deba@57: 
alpar@209:       InArcIt(const Digraph& digraph, const Arc& arc) :
alpar@209:         Arc(arc), _digraph(&digraph) {}
deba@57: 
alpar@209:       InArcIt& operator++() {
alpar@209:         _digraph->nextIn(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
kpeter@314:     // \brief Base node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the base node (i.e. the source in this case) of the iterator
deba@78:     Node baseNode(const OutArcIt &arc) const {
deba@78:       return Parent::source(arc);
deba@57:     }
kpeter@314:     // \brief Running node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the running node (i.e. the target in this case) of the
kpeter@314:     // iterator
deba@78:     Node runningNode(const OutArcIt &arc) const {
deba@78:       return Parent::target(arc);
deba@57:     }
deba@57: 
kpeter@314:     // \brief Base node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the base node (i.e. the target in this case) of the iterator
deba@78:     Node baseNode(const InArcIt &arc) const {
deba@78:       return Parent::target(arc);
deba@57:     }
kpeter@314:     // \brief Running node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the running node (i.e. the source in this case) of the
kpeter@314:     // iterator
deba@78:     Node runningNode(const InArcIt &arc) const {
deba@78:       return Parent::source(arc);
deba@57:     }
deba@57: 
alpar@209: 
deba@57:     template <typename _Value>
alpar@209:     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: 
alpar@209:       explicit NodeMap(const Digraph& digraph)
alpar@209:         : Parent(digraph) {}
alpar@209:       NodeMap(const Digraph& digraph, const _Value& value)
alpar@209:         : Parent(digraph, value) {}
deba@57: 
kpeter@263:     private:
deba@57:       NodeMap& operator=(const NodeMap& cmap) {
alpar@209:         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);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     template <typename _Value>
alpar@209:     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: 
alpar@209:       explicit ArcMap(const Digraph& digraph)
alpar@209:         : Parent(digraph) {}
alpar@209:       ArcMap(const Digraph& digraph, const _Value& value)
alpar@209:         : Parent(digraph, value) {}
deba@57: 
kpeter@263:     private:
deba@57:       ArcMap& operator=(const ArcMap& cmap) {
alpar@209:         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);
alpar@209:         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:     }
alpar@209: 
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 ) {
alpar@209:         erase(arc);
alpar@209:         Parent::firstOut(arc, node);
alpar@209:       }
deba@57: 
deba@57:       Parent::firstIn(arc, node);
deba@57:       while (arc != INVALID ) {
alpar@209:         erase(arc);
alpar@209:         Parent::firstIn(arc, node);
deba@57:       }
deba@57: 
deba@57:       notifier(Node()).erase(node);
deba@57:       Parent::erase(node);
deba@57:     }
alpar@209: 
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);
alpar@209:     }
alpar@209: 
deba@57: 
deba@57:     ~DigraphExtender() {
deba@57:       arc_notifier.clear();
deba@57:       node_notifier.clear();
deba@57:     }
deba@57:   };
deba@57: 
kpeter@314:   // \ingroup _graphbits
kpeter@314:   //
kpeter@314:   // \brief Extender for the Graphs
alpar@209:   template <typename Base>
deba@57:   class GraphExtender : public Base {
deba@57:   public:
alpar@209: 
deba@57:     typedef Base Parent;
deba@78:     typedef GraphExtender Graph;
deba@57: 
deba@77:     typedef True UndirectedTag;
deba@77: 
deba@57:     typedef typename Parent::Node Node;
deba@57:     typedef typename Parent::Arc Arc;
deba@57:     typedef typename Parent::Edge Edge;
deba@57: 
alpar@209:     // 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@125:       if( n == Parent::u(e))
alpar@209:         return Parent::v(e);
deba@125:       else if( n == Parent::v(e))
alpar@209:         return Parent::u(e);
deba@57:       else
alpar@209:         return INVALID;
deba@57:     }
deba@57: 
deba@78:     Arc oppositeArc(const Arc &arc) const {
deba@78:       return Parent::direct(arc, !Parent::direction(arc));
deba@57:     }
deba@57: 
deba@57:     using Parent::direct;
deba@78:     Arc direct(const Edge &edge, const Node &node) const {
deba@125:       return Parent::direct(edge, Parent::u(edge) == node);
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:     }
alpar@209: 
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: 
alpar@209:     class NodeIt : public Node {
deba@78:       const Graph* _graph;
deba@57:     public:
deba@57: 
deba@57:       NodeIt() {}
deba@57: 
deba@57:       NodeIt(Invalid i) : Node(i) { }
deba@57: 
deba@78:       explicit NodeIt(const Graph& graph) : _graph(&graph) {
alpar@209:         _graph->first(static_cast<Node&>(*this));
deba@57:       }
deba@57: 
alpar@209:       NodeIt(const Graph& graph, const Node& node)
alpar@209:         : Node(node), _graph(&graph) {}
deba@57: 
alpar@209:       NodeIt& operator++() {
alpar@209:         _graph->next(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class ArcIt : public Arc {
deba@78:       const Graph* _graph;
deba@57:     public:
deba@57: 
deba@57:       ArcIt() { }
deba@57: 
deba@57:       ArcIt(Invalid i) : Arc(i) { }
deba@57: 
deba@78:       explicit ArcIt(const Graph& graph) : _graph(&graph) {
alpar@209:         _graph->first(static_cast<Arc&>(*this));
deba@57:       }
deba@57: 
alpar@209:       ArcIt(const Graph& graph, const Arc& arc) :
alpar@209:         Arc(arc), _graph(&graph) { }
deba@57: 
alpar@209:       ArcIt& operator++() {
alpar@209:         _graph->next(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class OutArcIt : public Arc {
deba@78:       const Graph* _graph;
deba@57:     public:
deba@57: 
deba@57:       OutArcIt() { }
deba@57: 
deba@57:       OutArcIt(Invalid i) : Arc(i) { }
deba@57: 
alpar@209:       OutArcIt(const Graph& graph, const Node& node)
alpar@209:         : _graph(&graph) {
alpar@209:         _graph->firstOut(*this, node);
deba@57:       }
deba@57: 
alpar@209:       OutArcIt(const Graph& graph, const Arc& arc)
alpar@209:         : Arc(arc), _graph(&graph) {}
deba@57: 
alpar@209:       OutArcIt& operator++() {
alpar@209:         _graph->nextOut(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class InArcIt : public Arc {
deba@78:       const Graph* _graph;
deba@57:     public:
deba@57: 
deba@57:       InArcIt() { }
deba@57: 
deba@57:       InArcIt(Invalid i) : Arc(i) { }
deba@57: 
alpar@209:       InArcIt(const Graph& graph, const Node& node)
alpar@209:         : _graph(&graph) {
alpar@209:         _graph->firstIn(*this, node);
deba@57:       }
deba@57: 
alpar@209:       InArcIt(const Graph& graph, const Arc& arc) :
alpar@209:         Arc(arc), _graph(&graph) {}
deba@57: 
alpar@209:       InArcIt& operator++() {
alpar@209:         _graph->nextIn(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57: 
alpar@209:     class EdgeIt : public Parent::Edge {
deba@78:       const Graph* _graph;
deba@57:     public:
deba@57: 
deba@57:       EdgeIt() { }
deba@57: 
deba@57:       EdgeIt(Invalid i) : Edge(i) { }
deba@57: 
deba@78:       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
alpar@209:         _graph->first(static_cast<Edge&>(*this));
deba@57:       }
deba@57: 
alpar@209:       EdgeIt(const Graph& graph, const Edge& edge) :
alpar@209:         Edge(edge), _graph(&graph) { }
deba@57: 
alpar@209:       EdgeIt& operator++() {
alpar@209:         _graph->next(*this);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@78:     class IncEdgeIt : public Parent::Edge {
deba@57:       friend class GraphExtender;
deba@78:       const Graph* _graph;
deba@78:       bool _direction;
deba@57:     public:
deba@57: 
deba@78:       IncEdgeIt() { }
deba@57: 
deba@78:       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
deba@57: 
deba@78:       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
alpar@209:         _graph->firstInc(*this, _direction, node);
deba@57:       }
deba@57: 
deba@78:       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
alpar@209:         : _graph(&graph), Edge(edge) {
alpar@209:         _direction = (_graph->source(edge) == node);
deba@57:       }
deba@57: 
deba@78:       IncEdgeIt& operator++() {
alpar@209:         _graph->nextInc(*this, _direction);
alpar@209:         return *this;
deba@57:       }
deba@57:     };
deba@57: 
kpeter@314:     // \brief Base node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the base node (ie. the source in this case) of the iterator
deba@78:     Node baseNode(const OutArcIt &arc) const {
deba@78:       return Parent::source(static_cast<const Arc&>(arc));
deba@57:     }
kpeter@314:     // \brief Running node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the running node (ie. the target in this case) of the
kpeter@314:     // iterator
deba@78:     Node runningNode(const OutArcIt &arc) const {
deba@78:       return Parent::target(static_cast<const Arc&>(arc));
deba@57:     }
deba@57: 
kpeter@314:     // \brief Base node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the base node (ie. the target in this case) of the iterator
deba@78:     Node baseNode(const InArcIt &arc) const {
deba@78:       return Parent::target(static_cast<const Arc&>(arc));
deba@57:     }
kpeter@314:     // \brief Running node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the running node (ie. the source in this case) of the
kpeter@314:     // iterator
deba@78:     Node runningNode(const InArcIt &arc) const {
deba@78:       return Parent::source(static_cast<const Arc&>(arc));
deba@57:     }
deba@57: 
kpeter@314:     // Base node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the base node of the iterator
deba@78:     Node baseNode(const IncEdgeIt &edge) const {
deba@125:       return edge._direction ? u(edge) : v(edge);
deba@57:     }
kpeter@314:     // Running node of the iterator
kpeter@314:     //
kpeter@314:     // Returns the running node of the iterator
deba@78:     Node runningNode(const IncEdgeIt &edge) const {
deba@125:       return edge._direction ? v(edge) : u(edge);
deba@57:     }
deba@57: 
deba@57:     // Mappable extension
deba@57: 
deba@57:     template <typename _Value>
alpar@209:     class NodeMap
deba@78:       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
deba@57:     public:
deba@78:       typedef GraphExtender Graph;
deba@78:       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
deba@57: 
alpar@209:       NodeMap(const Graph& graph)
alpar@209:         : Parent(graph) {}
alpar@209:       NodeMap(const Graph& graph, const _Value& value)
alpar@209:         : Parent(graph, value) {}
deba@57: 
kpeter@263:     private:
deba@57:       NodeMap& operator=(const NodeMap& cmap) {
alpar@209:         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);
alpar@209:         return *this;
deba@57:       }
deba@57: 
deba@57:     };
deba@57: 
deba@57:     template <typename _Value>
alpar@209:     class ArcMap
deba@78:       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
deba@57:     public:
deba@78:       typedef GraphExtender Graph;
deba@78:       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
deba@57: 
alpar@209:       ArcMap(const Graph& graph)
alpar@209:         : Parent(graph) {}
alpar@209:       ArcMap(const Graph& graph, const _Value& value)
alpar@209:         : Parent(graph, value) {}
deba@57: 
kpeter@263:     private:
deba@57:       ArcMap& operator=(const ArcMap& cmap) {
alpar@209:         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);
alpar@209:         return *this;
deba@57:       }
deba@57:     };
deba@57: 
deba@57: 
deba@57:     template <typename _Value>
alpar@209:     class EdgeMap
deba@78:       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
deba@57:     public:
deba@78:       typedef GraphExtender Graph;
deba@78:       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
deba@57: 
alpar@209:       EdgeMap(const Graph& graph)
alpar@209:         : Parent(graph) {}
deba@57: 
alpar@209:       EdgeMap(const Graph& graph, const _Value& value)
alpar@209:         : Parent(graph, value) {}
deba@57: 
kpeter@263:     private:
deba@57:       EdgeMap& operator=(const EdgeMap& cmap) {
alpar@209:         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);
alpar@209:         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));
alpar@209:       ev.push_back(Parent::direct(edge, false));
deba@57:       notifier(Arc()).add(ev);
deba@57:       return edge;
deba@57:     }
alpar@209: 
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@78:     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
alpar@209:     void build(const Graph& graph, NodeRefMap& nodeRef,
deba@57:                EdgeRefMap& edgeRef) {
deba@78:       Parent::build(graph, 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 ) {
alpar@209:         erase(arc);
alpar@209:         Parent::firstOut(arc, node);
alpar@209:       }
deba@57: 
deba@57:       Parent::firstIn(arc, node);
deba@57:       while (arc != INVALID ) {
alpar@209:         erase(arc);
alpar@209:         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@78:       std::vector<Arc> av;
deba@78:       av.push_back(Parent::direct(edge, true));
alpar@209:       av.push_back(Parent::direct(edge, false));
deba@78:       notifier(Arc()).erase(av);
deba@57:       notifier(Edge()).erase(edge);
deba@57:       Parent::erase(edge);
deba@57:     }
deba@57: 
deba@57:     GraphExtender() {
alpar@209:       node_notifier.setContainer(*this);
deba@57:       arc_notifier.setContainer(*this);
deba@57:       edge_notifier.setContainer(*this);
alpar@209:     }
deba@57: 
deba@57:     ~GraphExtender() {
deba@57:       edge_notifier.clear();
deba@57:       arc_notifier.clear();
alpar@209:       node_notifier.clear();
alpar@209:     }
deba@57: 
deba@57:   };
deba@57: 
deba@57: }
deba@57: 
deba@57: #endif