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@1092:  * Copyright (C) 2003-2013
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: 
ggab90@1130: #include <lemon/bits/stl_iterators.h>
ggab90@1130: 
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 {
kpeter@617:     typedef Base Parent;
kpeter@617: 
deba@57:   public:
deba@57: 
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: 
kpeter@778:     static Node fromId(int id, Node) {
deba@57:       return Parent::nodeFromId(id);
deba@57:     }
deba@57: 
kpeter@778:     static Arc fromId(int id, Arc) {
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: 
ggab90@1130:     LemonRangeWrapper1<NodeIt, Digraph> nodes() const {
ggab90@1130:       return LemonRangeWrapper1<NodeIt, Digraph>(*this);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper1<ArcIt, Digraph> arcs() const {
ggab90@1130:       return LemonRangeWrapper1<ArcIt, Digraph>(*this);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
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:       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
deba@57: 
kpeter@617:     public:
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:       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
deba@57: 
kpeter@617:     public:
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 {
kpeter@617:     typedef Base Parent;
kpeter@617: 
deba@57:   public:
alpar@209: 
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: 
kpeter@778:     static Node fromId(int id, Node) {
deba@57:       return Parent::nodeFromId(id);
deba@57:     }
deba@57: 
kpeter@778:     static Arc fromId(int id, Arc) {
deba@57:       return Parent::arcFromId(id);
deba@57:     }
deba@57: 
kpeter@778:     static Edge fromId(int id, Edge) {
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: 
ggab90@1130:     LemonRangeWrapper1<NodeIt, Graph> nodes() const {
ggab90@1130:       return LemonRangeWrapper1<NodeIt, Graph>(*this);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper1<ArcIt, Graph> arcs() const {
ggab90@1130:       return LemonRangeWrapper1<ArcIt, Graph>(*this);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper1<EdgeIt, Graph> edges() const {
ggab90@1130:       return LemonRangeWrapper1<EdgeIt, Graph>(*this);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
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: 
ggab90@1130:     LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
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 {
alpar@997:       return edge._direction ? this->u(edge) : this->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 {
alpar@997:       return edge._direction ? this->v(edge) : this->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@78:       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
deba@57: 
kpeter@617:     public:
kpeter@685:       explicit 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@78:       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
deba@57: 
kpeter@617:     public:
kpeter@685:       explicit 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@78:       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
deba@57: 
kpeter@617:     public:
kpeter@685:       explicit 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@1019:   // \ingroup _graphbits
deba@1019:   //
deba@1019:   // \brief Extender for the BpGraphs
deba@1019:   template <typename Base>
deba@1019:   class BpGraphExtender : public Base {
deba@1019:     typedef Base Parent;
deba@1019: 
deba@1019:   public:
deba@1019: 
deba@1019:     typedef BpGraphExtender BpGraph;
deba@1019: 
deba@1019:     typedef True UndirectedTag;
deba@1019: 
deba@1019:     typedef typename Parent::Node Node;
deba@1025:     typedef typename Parent::RedNode RedNode;
deba@1025:     typedef typename Parent::BlueNode BlueNode;
deba@1019:     typedef typename Parent::Arc Arc;
deba@1019:     typedef typename Parent::Edge Edge;
deba@1019: 
deba@1019:     // BpGraph extension
deba@1019: 
deba@1019:     using Parent::first;
deba@1019:     using Parent::next;
deba@1019:     using Parent::id;
deba@1019: 
deba@1019:     int maxId(Node) const {
deba@1019:       return Parent::maxNodeId();
deba@1019:     }
deba@1019: 
deba@1019:     int maxId(RedNode) const {
deba@1019:       return Parent::maxRedId();
deba@1019:     }
deba@1019: 
deba@1019:     int maxId(BlueNode) const {
deba@1019:       return Parent::maxBlueId();
deba@1019:     }
deba@1019: 
deba@1019:     int maxId(Arc) const {
deba@1019:       return Parent::maxArcId();
deba@1019:     }
deba@1019: 
deba@1019:     int maxId(Edge) const {
deba@1019:       return Parent::maxEdgeId();
deba@1019:     }
deba@1019: 
deba@1019:     static Node fromId(int id, Node) {
deba@1019:       return Parent::nodeFromId(id);
deba@1019:     }
deba@1019: 
deba@1019:     static Arc fromId(int id, Arc) {
deba@1019:       return Parent::arcFromId(id);
deba@1019:     }
deba@1019: 
deba@1019:     static Edge fromId(int id, Edge) {
deba@1019:       return Parent::edgeFromId(id);
deba@1019:     }
deba@1019: 
deba@1020:     Node u(Edge e) const { return this->redNode(e); }
deba@1020:     Node v(Edge e) const { return this->blueNode(e); }
deba@1020: 
deba@1019:     Node oppositeNode(const Node &n, const Edge &e) const {
deba@1020:       if( n == u(e))
deba@1020:         return v(e);
deba@1020:       else if( n == v(e))
deba@1020:         return u(e);
deba@1019:       else
deba@1019:         return INVALID;
deba@1019:     }
deba@1019: 
deba@1019:     Arc oppositeArc(const Arc &arc) const {
deba@1019:       return Parent::direct(arc, !Parent::direction(arc));
deba@1019:     }
deba@1019: 
deba@1019:     using Parent::direct;
deba@1019:     Arc direct(const Edge &edge, const Node &node) const {
deba@1020:       return Parent::direct(edge, Parent::redNode(edge) == node);
deba@1019:     }
deba@1019: 
deba@1025:     RedNode asRedNode(const Node& node) const {
deba@1025:       if (node == INVALID || Parent::blue(node)) {
deba@1025:         return INVALID;
deba@1025:       } else {
deba@1025:         return Parent::asRedNodeUnsafe(node);
deba@1025:       }
deba@1025:     }
deba@1025: 
deba@1025:     BlueNode asBlueNode(const Node& node) const {
deba@1025:       if (node == INVALID || Parent::red(node)) {
deba@1025:         return INVALID;
deba@1025:       } else {
deba@1025:         return Parent::asBlueNodeUnsafe(node);
deba@1025:       }
deba@1025:     }
deba@1025: 
deba@1019:     // Alterable extension
deba@1019: 
deba@1019:     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
alpar@1092:     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;
deba@1019:     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
deba@1019:     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
deba@1019:     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
deba@1019: 
deba@1019: 
deba@1019:   protected:
deba@1019: 
deba@1019:     mutable NodeNotifier node_notifier;
deba@1019:     mutable RedNodeNotifier red_node_notifier;
deba@1019:     mutable BlueNodeNotifier blue_node_notifier;
deba@1019:     mutable ArcNotifier arc_notifier;
deba@1019:     mutable EdgeNotifier edge_notifier;
deba@1019: 
deba@1019:   public:
deba@1019: 
deba@1019:     NodeNotifier& notifier(Node) const {
deba@1019:       return node_notifier;
deba@1019:     }
deba@1019: 
deba@1019:     RedNodeNotifier& notifier(RedNode) const {
deba@1019:       return red_node_notifier;
deba@1019:     }
deba@1019: 
deba@1019:     BlueNodeNotifier& notifier(BlueNode) const {
deba@1019:       return blue_node_notifier;
deba@1019:     }
deba@1019: 
deba@1019:     ArcNotifier& notifier(Arc) const {
deba@1019:       return arc_notifier;
deba@1019:     }
deba@1019: 
deba@1019:     EdgeNotifier& notifier(Edge) const {
deba@1019:       return edge_notifier;
deba@1019:     }
deba@1019: 
deba@1019: 
deba@1019: 
deba@1019:     class NodeIt : public Node {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1019:       NodeIt() {}
deba@1019: 
deba@1019:       NodeIt(Invalid i) : Node(i) { }
deba@1019: 
deba@1019:       explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1019:         _graph->first(static_cast<Node&>(*this));
deba@1019:       }
deba@1019: 
deba@1019:       NodeIt(const BpGraph& graph, const Node& node)
deba@1019:         : Node(node), _graph(&graph) {}
deba@1019: 
deba@1019:       NodeIt& operator++() {
deba@1019:         _graph->next(*this);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {
ggab90@1130:       return LemonRangeWrapper1<NodeIt, BpGraph>(*this);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
deba@1026:     class RedNodeIt : public RedNode {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1026:       RedNodeIt() {}
deba@1019: 
deba@1026:       RedNodeIt(Invalid i) : RedNode(i) { }
deba@1019: 
deba@1026:       explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1025:         _graph->first(static_cast<RedNode&>(*this));
deba@1019:       }
deba@1019: 
deba@1026:       RedNodeIt(const BpGraph& graph, const RedNode& node)
deba@1025:         : RedNode(node), _graph(&graph) {}
deba@1019: 
deba@1026:       RedNodeIt& operator++() {
deba@1025:         _graph->next(static_cast<RedNode&>(*this));
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {
ggab90@1130:       return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
deba@1026:     class BlueNodeIt : public BlueNode {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1026:       BlueNodeIt() {}
deba@1019: 
deba@1026:       BlueNodeIt(Invalid i) : BlueNode(i) { }
deba@1019: 
deba@1026:       explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
deba@1025:         _graph->first(static_cast<BlueNode&>(*this));
deba@1019:       }
deba@1019: 
deba@1026:       BlueNodeIt(const BpGraph& graph, const BlueNode& node)
deba@1025:         : BlueNode(node), _graph(&graph) {}
deba@1019: 
deba@1026:       BlueNodeIt& operator++() {
deba@1025:         _graph->next(static_cast<BlueNode&>(*this));
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {
ggab90@1130:       return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
deba@1019: 
deba@1019:     class ArcIt : public Arc {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1019:       ArcIt() { }
deba@1019: 
deba@1019:       ArcIt(Invalid i) : Arc(i) { }
deba@1019: 
deba@1019:       explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
deba@1019:         _graph->first(static_cast<Arc&>(*this));
deba@1019:       }
deba@1019: 
deba@1019:       ArcIt(const BpGraph& graph, const Arc& arc) :
deba@1019:         Arc(arc), _graph(&graph) { }
deba@1019: 
deba@1019:       ArcIt& operator++() {
deba@1019:         _graph->next(*this);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {
ggab90@1130:       return LemonRangeWrapper1<ArcIt, BpGraph>(*this);
ggab90@1130:     }
ggab90@1130: 
deba@1019: 
deba@1019:     class OutArcIt : public Arc {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1019:       OutArcIt() { }
deba@1019: 
deba@1019:       OutArcIt(Invalid i) : Arc(i) { }
deba@1019: 
deba@1019:       OutArcIt(const BpGraph& graph, const Node& node)
deba@1019:         : _graph(&graph) {
deba@1019:         _graph->firstOut(*this, node);
deba@1019:       }
deba@1019: 
deba@1019:       OutArcIt(const BpGraph& graph, const Arc& arc)
deba@1019:         : Arc(arc), _graph(&graph) {}
deba@1019: 
deba@1019:       OutArcIt& operator++() {
deba@1019:         _graph->nextOut(*this);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
deba@1019: 
deba@1019:     class InArcIt : public Arc {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1019:       InArcIt() { }
deba@1019: 
deba@1019:       InArcIt(Invalid i) : Arc(i) { }
deba@1019: 
deba@1019:       InArcIt(const BpGraph& graph, const Node& node)
deba@1019:         : _graph(&graph) {
deba@1019:         _graph->firstIn(*this, node);
deba@1019:       }
deba@1019: 
deba@1019:       InArcIt(const BpGraph& graph, const Arc& arc) :
deba@1019:         Arc(arc), _graph(&graph) {}
deba@1019: 
deba@1019:       InArcIt& operator++() {
deba@1019:         _graph->nextIn(*this);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
deba@1019: 
deba@1019:     class EdgeIt : public Parent::Edge {
deba@1019:       const BpGraph* _graph;
deba@1019:     public:
deba@1019: 
deba@1019:       EdgeIt() { }
deba@1019: 
deba@1019:       EdgeIt(Invalid i) : Edge(i) { }
deba@1019: 
deba@1019:       explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
deba@1019:         _graph->first(static_cast<Edge&>(*this));
deba@1019:       }
deba@1019: 
deba@1019:       EdgeIt(const BpGraph& graph, const Edge& edge) :
deba@1019:         Edge(edge), _graph(&graph) { }
deba@1019: 
deba@1019:       EdgeIt& operator++() {
deba@1019:         _graph->next(*this);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {
ggab90@1130:       return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
deba@1019:     class IncEdgeIt : public Parent::Edge {
deba@1019:       friend class BpGraphExtender;
deba@1019:       const BpGraph* _graph;
deba@1019:       bool _direction;
deba@1019:     public:
deba@1019: 
deba@1019:       IncEdgeIt() { }
deba@1019: 
deba@1019:       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
deba@1019: 
deba@1019:       IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
deba@1019:         _graph->firstInc(*this, _direction, node);
deba@1019:       }
deba@1019: 
deba@1019:       IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
deba@1019:         : _graph(&graph), Edge(edge) {
deba@1019:         _direction = (_graph->source(edge) == node);
deba@1019:       }
deba@1019: 
deba@1019:       IncEdgeIt& operator++() {
deba@1019:         _graph->nextInc(*this, _direction);
deba@1019:         return *this;
deba@1019:       }
deba@1019:     };
deba@1019: 
ggab90@1130:     LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {
ggab90@1130:       return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);
ggab90@1130:     }
ggab90@1130: 
ggab90@1130: 
deba@1019:     // \brief Base node of the iterator
deba@1019:     //
deba@1019:     // Returns the base node (ie. the source in this case) of the iterator
deba@1019:     Node baseNode(const OutArcIt &arc) const {
deba@1019:       return Parent::source(static_cast<const Arc&>(arc));
deba@1019:     }
deba@1019:     // \brief Running node of the iterator
deba@1019:     //
deba@1019:     // Returns the running node (ie. the target in this case) of the
deba@1019:     // iterator
deba@1019:     Node runningNode(const OutArcIt &arc) const {
deba@1019:       return Parent::target(static_cast<const Arc&>(arc));
deba@1019:     }
deba@1019: 
deba@1019:     // \brief Base node of the iterator
deba@1019:     //
deba@1019:     // Returns the base node (ie. the target in this case) of the iterator
deba@1019:     Node baseNode(const InArcIt &arc) const {
deba@1019:       return Parent::target(static_cast<const Arc&>(arc));
deba@1019:     }
deba@1019:     // \brief Running node of the iterator
deba@1019:     //
deba@1019:     // Returns the running node (ie. the source in this case) of the
deba@1019:     // iterator
deba@1019:     Node runningNode(const InArcIt &arc) const {
deba@1019:       return Parent::source(static_cast<const Arc&>(arc));
deba@1019:     }
deba@1019: 
deba@1019:     // Base node of the iterator
deba@1019:     //
deba@1019:     // Returns the base node of the iterator
deba@1019:     Node baseNode(const IncEdgeIt &edge) const {
deba@1019:       return edge._direction ? this->u(edge) : this->v(edge);
deba@1019:     }
deba@1019:     // Running node of the iterator
deba@1019:     //
deba@1019:     // Returns the running node of the iterator
deba@1019:     Node runningNode(const IncEdgeIt &edge) const {
deba@1019:       return edge._direction ? this->v(edge) : this->u(edge);
deba@1019:     }
deba@1019: 
deba@1019:     // Mappable extension
deba@1019: 
deba@1019:     template <typename _Value>
deba@1019:     class NodeMap
deba@1019:       : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
deba@1019:       typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
deba@1019: 
deba@1019:     public:
deba@1019:       explicit NodeMap(const BpGraph& bpgraph)
deba@1019:         : Parent(bpgraph) {}
deba@1019:       NodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019:         : Parent(bpgraph, value) {}
deba@1019: 
deba@1019:     private:
deba@1019:       NodeMap& operator=(const NodeMap& cmap) {
deba@1019:         return operator=<NodeMap>(cmap);
deba@1019:       }
deba@1019: 
deba@1019:       template <typename CMap>
deba@1019:       NodeMap& operator=(const CMap& cmap) {
deba@1019:         Parent::operator=(cmap);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
deba@1019:     template <typename _Value>
deba@1026:     class RedNodeMap
deba@1019:       : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
deba@1019:       typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
deba@1019: 
deba@1019:     public:
deba@1026:       explicit RedNodeMap(const BpGraph& bpgraph)
deba@1019:         : Parent(bpgraph) {}
deba@1026:       RedNodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019:         : Parent(bpgraph, value) {}
deba@1019: 
deba@1019:     private:
deba@1026:       RedNodeMap& operator=(const RedNodeMap& cmap) {
deba@1026:         return operator=<RedNodeMap>(cmap);
deba@1019:       }
deba@1019: 
deba@1019:       template <typename CMap>
deba@1026:       RedNodeMap& operator=(const CMap& cmap) {
deba@1019:         Parent::operator=(cmap);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
deba@1019:     template <typename _Value>
deba@1026:     class BlueNodeMap
deba@1019:       : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
deba@1019:       typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
deba@1019: 
deba@1019:     public:
deba@1026:       explicit BlueNodeMap(const BpGraph& bpgraph)
deba@1019:         : Parent(bpgraph) {}
deba@1026:       BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
deba@1019:         : Parent(bpgraph, value) {}
deba@1019: 
deba@1019:     private:
deba@1026:       BlueNodeMap& operator=(const BlueNodeMap& cmap) {
deba@1026:         return operator=<BlueNodeMap>(cmap);
deba@1019:       }
deba@1019: 
deba@1019:       template <typename CMap>
deba@1026:       BlueNodeMap& operator=(const CMap& cmap) {
deba@1019:         Parent::operator=(cmap);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
deba@1019:     template <typename _Value>
deba@1019:     class ArcMap
deba@1019:       : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
deba@1019:       typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
deba@1019: 
deba@1019:     public:
deba@1019:       explicit ArcMap(const BpGraph& graph)
deba@1019:         : Parent(graph) {}
deba@1019:       ArcMap(const BpGraph& graph, const _Value& value)
deba@1019:         : Parent(graph, value) {}
deba@1019: 
deba@1019:     private:
deba@1019:       ArcMap& operator=(const ArcMap& cmap) {
deba@1019:         return operator=<ArcMap>(cmap);
deba@1019:       }
deba@1019: 
deba@1019:       template <typename CMap>
deba@1019:       ArcMap& operator=(const CMap& cmap) {
deba@1019:         Parent::operator=(cmap);
deba@1019:         return *this;
deba@1019:       }
deba@1019:     };
deba@1019: 
deba@1019: 
deba@1019:     template <typename _Value>
deba@1019:     class EdgeMap
deba@1019:       : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
deba@1019:       typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
deba@1019: 
deba@1019:     public:
deba@1019:       explicit EdgeMap(const BpGraph& graph)
deba@1019:         : Parent(graph) {}
deba@1019: 
deba@1019:       EdgeMap(const BpGraph& graph, const _Value& value)
deba@1019:         : Parent(graph, value) {}
deba@1019: 
deba@1019:     private:
deba@1019:       EdgeMap& operator=(const EdgeMap& cmap) {
deba@1019:         return operator=<EdgeMap>(cmap);
deba@1019:       }
deba@1019: 
deba@1019:       template <typename CMap>
deba@1019:       EdgeMap& operator=(const CMap& cmap) {
deba@1019:         Parent::operator=(cmap);
deba@1019:         return *this;
deba@1019:       }
deba@1019: 
deba@1019:     };
deba@1019: 
deba@1019:     // Alteration extension
deba@1019: 
deba@1025:     RedNode addRedNode() {
deba@1025:       RedNode node = Parent::addRedNode();
deba@1019:       notifier(RedNode()).add(node);
deba@1019:       notifier(Node()).add(node);
deba@1019:       return node;
deba@1019:     }
deba@1019: 
deba@1025:     BlueNode addBlueNode() {
deba@1025:       BlueNode node = Parent::addBlueNode();
deba@1019:       notifier(BlueNode()).add(node);
deba@1019:       notifier(Node()).add(node);
deba@1019:       return node;
deba@1019:     }
deba@1019: 
deba@1025:     Edge addEdge(const RedNode& from, const BlueNode& to) {
deba@1019:       Edge edge = Parent::addEdge(from, to);
deba@1019:       notifier(Edge()).add(edge);
deba@1019:       std::vector<Arc> av;
deba@1019:       av.push_back(Parent::direct(edge, true));
deba@1019:       av.push_back(Parent::direct(edge, false));
deba@1019:       notifier(Arc()).add(av);
deba@1019:       return edge;
deba@1019:     }
deba@1019: 
deba@1019:     void clear() {
deba@1019:       notifier(Arc()).clear();
deba@1019:       notifier(Edge()).clear();
deba@1019:       notifier(Node()).clear();
deba@1019:       notifier(BlueNode()).clear();
deba@1019:       notifier(RedNode()).clear();
deba@1019:       Parent::clear();
deba@1019:     }
deba@1019: 
deba@1019:     template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
deba@1019:     void build(const BpGraph& graph, NodeRefMap& nodeRef,
deba@1019:                EdgeRefMap& edgeRef) {
deba@1019:       Parent::build(graph, nodeRef, edgeRef);
deba@1019:       notifier(RedNode()).build();
deba@1019:       notifier(BlueNode()).build();
deba@1019:       notifier(Node()).build();
deba@1019:       notifier(Edge()).build();
deba@1019:       notifier(Arc()).build();
deba@1019:     }
deba@1019: 
deba@1019:     void erase(const Node& node) {
deba@1019:       Arc arc;
deba@1019:       Parent::firstOut(arc, node);
deba@1019:       while (arc != INVALID ) {
deba@1019:         erase(arc);
deba@1019:         Parent::firstOut(arc, node);
deba@1019:       }
deba@1019: 
deba@1019:       Parent::firstIn(arc, node);
deba@1019:       while (arc != INVALID ) {
deba@1019:         erase(arc);
deba@1019:         Parent::firstIn(arc, node);
deba@1019:       }
deba@1019: 
deba@1019:       if (Parent::red(node)) {
deba@1025:         notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
deba@1019:       } else {
deba@1025:         notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
deba@1019:       }
deba@1019: 
deba@1019:       notifier(Node()).erase(node);
deba@1019:       Parent::erase(node);
deba@1019:     }
deba@1019: 
deba@1019:     void erase(const Edge& edge) {
deba@1019:       std::vector<Arc> av;
deba@1019:       av.push_back(Parent::direct(edge, true));
deba@1019:       av.push_back(Parent::direct(edge, false));
deba@1019:       notifier(Arc()).erase(av);
deba@1019:       notifier(Edge()).erase(edge);
deba@1019:       Parent::erase(edge);
deba@1019:     }
deba@1019: 
deba@1019:     BpGraphExtender() {
deba@1019:       red_node_notifier.setContainer(*this);
deba@1019:       blue_node_notifier.setContainer(*this);
deba@1019:       node_notifier.setContainer(*this);
deba@1019:       arc_notifier.setContainer(*this);
deba@1019:       edge_notifier.setContainer(*this);
deba@1019:     }
deba@1019: 
deba@1019:     ~BpGraphExtender() {
deba@1019:       edge_notifier.clear();
deba@1019:       arc_notifier.clear();
deba@1019:       node_notifier.clear();
deba@1019:       blue_node_notifier.clear();
deba@1019:       red_node_notifier.clear();
deba@1019:     }
deba@1019: 
deba@1019:   };
deba@1019: 
deba@57: }
deba@57: 
deba@57: #endif