lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 30 Jul 2013 15:24:45 +0200
changeset 1071 879fcb781086
parent 1026 699c7eac2c6d
child 1092 dceba191c00d
permissions -rw-r--r--
Merge #454
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
    20 #define LEMON_BITS_GRAPH_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 
    24 #include <lemon/bits/map_extender.h>
    25 #include <lemon/bits/default_map.h>
    26 
    27 #include <lemon/concept_check.h>
    28 #include <lemon/concepts/maps.h>
    29 
    30 //\ingroup graphbits
    31 //\file
    32 //\brief Extenders for the graph types
    33 namespace lemon {
    34 
    35   // \ingroup graphbits
    36   //
    37   // \brief Extender for the digraph implementations
    38   template <typename Base>
    39   class DigraphExtender : public Base {
    40     typedef Base Parent;
    41 
    42   public:
    43 
    44     typedef DigraphExtender Digraph;
    45 
    46     // Base extensions
    47 
    48     typedef typename Parent::Node Node;
    49     typedef typename Parent::Arc Arc;
    50 
    51     int maxId(Node) const {
    52       return Parent::maxNodeId();
    53     }
    54 
    55     int maxId(Arc) const {
    56       return Parent::maxArcId();
    57     }
    58 
    59     static Node fromId(int id, Node) {
    60       return Parent::nodeFromId(id);
    61     }
    62 
    63     static Arc fromId(int id, Arc) {
    64       return Parent::arcFromId(id);
    65     }
    66 
    67     Node oppositeNode(const Node &node, const Arc &arc) const {
    68       if (node == Parent::source(arc))
    69         return Parent::target(arc);
    70       else if(node == Parent::target(arc))
    71         return Parent::source(arc);
    72       else
    73         return INVALID;
    74     }
    75 
    76     // Alterable extension
    77 
    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    79     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
    80 
    81 
    82   protected:
    83 
    84     mutable NodeNotifier node_notifier;
    85     mutable ArcNotifier arc_notifier;
    86 
    87   public:
    88 
    89     NodeNotifier& notifier(Node) const {
    90       return node_notifier;
    91     }
    92 
    93     ArcNotifier& notifier(Arc) const {
    94       return arc_notifier;
    95     }
    96 
    97     class NodeIt : public Node {
    98       const Digraph* _digraph;
    99     public:
   100 
   101       NodeIt() {}
   102 
   103       NodeIt(Invalid i) : Node(i) { }
   104 
   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   106         _digraph->first(static_cast<Node&>(*this));
   107       }
   108 
   109       NodeIt(const Digraph& digraph, const Node& node)
   110         : Node(node), _digraph(&digraph) {}
   111 
   112       NodeIt& operator++() {
   113         _digraph->next(*this);
   114         return *this;
   115       }
   116 
   117     };
   118 
   119 
   120     class ArcIt : public Arc {
   121       const Digraph* _digraph;
   122     public:
   123 
   124       ArcIt() { }
   125 
   126       ArcIt(Invalid i) : Arc(i) { }
   127 
   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   129         _digraph->first(static_cast<Arc&>(*this));
   130       }
   131 
   132       ArcIt(const Digraph& digraph, const Arc& arc) :
   133         Arc(arc), _digraph(&digraph) { }
   134 
   135       ArcIt& operator++() {
   136         _digraph->next(*this);
   137         return *this;
   138       }
   139 
   140     };
   141 
   142 
   143     class OutArcIt : public Arc {
   144       const Digraph* _digraph;
   145     public:
   146 
   147       OutArcIt() { }
   148 
   149       OutArcIt(Invalid i) : Arc(i) { }
   150 
   151       OutArcIt(const Digraph& digraph, const Node& node)
   152         : _digraph(&digraph) {
   153         _digraph->firstOut(*this, node);
   154       }
   155 
   156       OutArcIt(const Digraph& digraph, const Arc& arc)
   157         : Arc(arc), _digraph(&digraph) {}
   158 
   159       OutArcIt& operator++() {
   160         _digraph->nextOut(*this);
   161         return *this;
   162       }
   163 
   164     };
   165 
   166 
   167     class InArcIt : public Arc {
   168       const Digraph* _digraph;
   169     public:
   170 
   171       InArcIt() { }
   172 
   173       InArcIt(Invalid i) : Arc(i) { }
   174 
   175       InArcIt(const Digraph& digraph, const Node& node)
   176         : _digraph(&digraph) {
   177         _digraph->firstIn(*this, node);
   178       }
   179 
   180       InArcIt(const Digraph& digraph, const Arc& arc) :
   181         Arc(arc), _digraph(&digraph) {}
   182 
   183       InArcIt& operator++() {
   184         _digraph->nextIn(*this);
   185         return *this;
   186       }
   187 
   188     };
   189 
   190     // \brief Base node of the iterator
   191     //
   192     // Returns the base node (i.e. the source in this case) of the iterator
   193     Node baseNode(const OutArcIt &arc) const {
   194       return Parent::source(arc);
   195     }
   196     // \brief Running node of the iterator
   197     //
   198     // Returns the running node (i.e. the target in this case) of the
   199     // iterator
   200     Node runningNode(const OutArcIt &arc) const {
   201       return Parent::target(arc);
   202     }
   203 
   204     // \brief Base node of the iterator
   205     //
   206     // Returns the base node (i.e. the target in this case) of the iterator
   207     Node baseNode(const InArcIt &arc) const {
   208       return Parent::target(arc);
   209     }
   210     // \brief Running node of the iterator
   211     //
   212     // Returns the running node (i.e. the source in this case) of the
   213     // iterator
   214     Node runningNode(const InArcIt &arc) const {
   215       return Parent::source(arc);
   216     }
   217 
   218 
   219     template <typename _Value>
   220     class NodeMap
   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   222       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   223 
   224     public:
   225       explicit NodeMap(const Digraph& digraph)
   226         : Parent(digraph) {}
   227       NodeMap(const Digraph& digraph, const _Value& value)
   228         : Parent(digraph, value) {}
   229 
   230     private:
   231       NodeMap& operator=(const NodeMap& cmap) {
   232         return operator=<NodeMap>(cmap);
   233       }
   234 
   235       template <typename CMap>
   236       NodeMap& operator=(const CMap& cmap) {
   237         Parent::operator=(cmap);
   238         return *this;
   239       }
   240 
   241     };
   242 
   243     template <typename _Value>
   244     class ArcMap
   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   246       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   247 
   248     public:
   249       explicit ArcMap(const Digraph& digraph)
   250         : Parent(digraph) {}
   251       ArcMap(const Digraph& digraph, const _Value& value)
   252         : Parent(digraph, value) {}
   253 
   254     private:
   255       ArcMap& operator=(const ArcMap& cmap) {
   256         return operator=<ArcMap>(cmap);
   257       }
   258 
   259       template <typename CMap>
   260       ArcMap& operator=(const CMap& cmap) {
   261         Parent::operator=(cmap);
   262         return *this;
   263       }
   264     };
   265 
   266 
   267     Node addNode() {
   268       Node node = Parent::addNode();
   269       notifier(Node()).add(node);
   270       return node;
   271     }
   272 
   273     Arc addArc(const Node& from, const Node& to) {
   274       Arc arc = Parent::addArc(from, to);
   275       notifier(Arc()).add(arc);
   276       return arc;
   277     }
   278 
   279     void clear() {
   280       notifier(Arc()).clear();
   281       notifier(Node()).clear();
   282       Parent::clear();
   283     }
   284 
   285     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   286     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   287       Parent::build(digraph, nodeRef, arcRef);
   288       notifier(Node()).build();
   289       notifier(Arc()).build();
   290     }
   291 
   292     void erase(const Node& node) {
   293       Arc arc;
   294       Parent::firstOut(arc, node);
   295       while (arc != INVALID ) {
   296         erase(arc);
   297         Parent::firstOut(arc, node);
   298       }
   299 
   300       Parent::firstIn(arc, node);
   301       while (arc != INVALID ) {
   302         erase(arc);
   303         Parent::firstIn(arc, node);
   304       }
   305 
   306       notifier(Node()).erase(node);
   307       Parent::erase(node);
   308     }
   309 
   310     void erase(const Arc& arc) {
   311       notifier(Arc()).erase(arc);
   312       Parent::erase(arc);
   313     }
   314 
   315     DigraphExtender() {
   316       node_notifier.setContainer(*this);
   317       arc_notifier.setContainer(*this);
   318     }
   319 
   320 
   321     ~DigraphExtender() {
   322       arc_notifier.clear();
   323       node_notifier.clear();
   324     }
   325   };
   326 
   327   // \ingroup _graphbits
   328   //
   329   // \brief Extender for the Graphs
   330   template <typename Base>
   331   class GraphExtender : public Base {
   332     typedef Base Parent;
   333 
   334   public:
   335 
   336     typedef GraphExtender Graph;
   337 
   338     typedef True UndirectedTag;
   339 
   340     typedef typename Parent::Node Node;
   341     typedef typename Parent::Arc Arc;
   342     typedef typename Parent::Edge Edge;
   343 
   344     // Graph extension
   345 
   346     int maxId(Node) const {
   347       return Parent::maxNodeId();
   348     }
   349 
   350     int maxId(Arc) const {
   351       return Parent::maxArcId();
   352     }
   353 
   354     int maxId(Edge) const {
   355       return Parent::maxEdgeId();
   356     }
   357 
   358     static Node fromId(int id, Node) {
   359       return Parent::nodeFromId(id);
   360     }
   361 
   362     static Arc fromId(int id, Arc) {
   363       return Parent::arcFromId(id);
   364     }
   365 
   366     static Edge fromId(int id, Edge) {
   367       return Parent::edgeFromId(id);
   368     }
   369 
   370     Node oppositeNode(const Node &n, const Edge &e) const {
   371       if( n == Parent::u(e))
   372         return Parent::v(e);
   373       else if( n == Parent::v(e))
   374         return Parent::u(e);
   375       else
   376         return INVALID;
   377     }
   378 
   379     Arc oppositeArc(const Arc &arc) const {
   380       return Parent::direct(arc, !Parent::direction(arc));
   381     }
   382 
   383     using Parent::direct;
   384     Arc direct(const Edge &edge, const Node &node) const {
   385       return Parent::direct(edge, Parent::u(edge) == node);
   386     }
   387 
   388     // Alterable extension
   389 
   390     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   391     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   392     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   393 
   394 
   395   protected:
   396 
   397     mutable NodeNotifier node_notifier;
   398     mutable ArcNotifier arc_notifier;
   399     mutable EdgeNotifier edge_notifier;
   400 
   401   public:
   402 
   403     NodeNotifier& notifier(Node) const {
   404       return node_notifier;
   405     }
   406 
   407     ArcNotifier& notifier(Arc) const {
   408       return arc_notifier;
   409     }
   410 
   411     EdgeNotifier& notifier(Edge) const {
   412       return edge_notifier;
   413     }
   414 
   415 
   416 
   417     class NodeIt : public Node {
   418       const Graph* _graph;
   419     public:
   420 
   421       NodeIt() {}
   422 
   423       NodeIt(Invalid i) : Node(i) { }
   424 
   425       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   426         _graph->first(static_cast<Node&>(*this));
   427       }
   428 
   429       NodeIt(const Graph& graph, const Node& node)
   430         : Node(node), _graph(&graph) {}
   431 
   432       NodeIt& operator++() {
   433         _graph->next(*this);
   434         return *this;
   435       }
   436 
   437     };
   438 
   439 
   440     class ArcIt : public Arc {
   441       const Graph* _graph;
   442     public:
   443 
   444       ArcIt() { }
   445 
   446       ArcIt(Invalid i) : Arc(i) { }
   447 
   448       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   449         _graph->first(static_cast<Arc&>(*this));
   450       }
   451 
   452       ArcIt(const Graph& graph, const Arc& arc) :
   453         Arc(arc), _graph(&graph) { }
   454 
   455       ArcIt& operator++() {
   456         _graph->next(*this);
   457         return *this;
   458       }
   459 
   460     };
   461 
   462 
   463     class OutArcIt : public Arc {
   464       const Graph* _graph;
   465     public:
   466 
   467       OutArcIt() { }
   468 
   469       OutArcIt(Invalid i) : Arc(i) { }
   470 
   471       OutArcIt(const Graph& graph, const Node& node)
   472         : _graph(&graph) {
   473         _graph->firstOut(*this, node);
   474       }
   475 
   476       OutArcIt(const Graph& graph, const Arc& arc)
   477         : Arc(arc), _graph(&graph) {}
   478 
   479       OutArcIt& operator++() {
   480         _graph->nextOut(*this);
   481         return *this;
   482       }
   483 
   484     };
   485 
   486 
   487     class InArcIt : public Arc {
   488       const Graph* _graph;
   489     public:
   490 
   491       InArcIt() { }
   492 
   493       InArcIt(Invalid i) : Arc(i) { }
   494 
   495       InArcIt(const Graph& graph, const Node& node)
   496         : _graph(&graph) {
   497         _graph->firstIn(*this, node);
   498       }
   499 
   500       InArcIt(const Graph& graph, const Arc& arc) :
   501         Arc(arc), _graph(&graph) {}
   502 
   503       InArcIt& operator++() {
   504         _graph->nextIn(*this);
   505         return *this;
   506       }
   507 
   508     };
   509 
   510 
   511     class EdgeIt : public Parent::Edge {
   512       const Graph* _graph;
   513     public:
   514 
   515       EdgeIt() { }
   516 
   517       EdgeIt(Invalid i) : Edge(i) { }
   518 
   519       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   520         _graph->first(static_cast<Edge&>(*this));
   521       }
   522 
   523       EdgeIt(const Graph& graph, const Edge& edge) :
   524         Edge(edge), _graph(&graph) { }
   525 
   526       EdgeIt& operator++() {
   527         _graph->next(*this);
   528         return *this;
   529       }
   530 
   531     };
   532 
   533     class IncEdgeIt : public Parent::Edge {
   534       friend class GraphExtender;
   535       const Graph* _graph;
   536       bool _direction;
   537     public:
   538 
   539       IncEdgeIt() { }
   540 
   541       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   542 
   543       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   544         _graph->firstInc(*this, _direction, node);
   545       }
   546 
   547       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   548         : _graph(&graph), Edge(edge) {
   549         _direction = (_graph->source(edge) == node);
   550       }
   551 
   552       IncEdgeIt& operator++() {
   553         _graph->nextInc(*this, _direction);
   554         return *this;
   555       }
   556     };
   557 
   558     // \brief Base node of the iterator
   559     //
   560     // Returns the base node (ie. the source in this case) of the iterator
   561     Node baseNode(const OutArcIt &arc) const {
   562       return Parent::source(static_cast<const Arc&>(arc));
   563     }
   564     // \brief Running node of the iterator
   565     //
   566     // Returns the running node (ie. the target in this case) of the
   567     // iterator
   568     Node runningNode(const OutArcIt &arc) const {
   569       return Parent::target(static_cast<const Arc&>(arc));
   570     }
   571 
   572     // \brief Base node of the iterator
   573     //
   574     // Returns the base node (ie. the target in this case) of the iterator
   575     Node baseNode(const InArcIt &arc) const {
   576       return Parent::target(static_cast<const Arc&>(arc));
   577     }
   578     // \brief Running node of the iterator
   579     //
   580     // Returns the running node (ie. the source in this case) of the
   581     // iterator
   582     Node runningNode(const InArcIt &arc) const {
   583       return Parent::source(static_cast<const Arc&>(arc));
   584     }
   585 
   586     // Base node of the iterator
   587     //
   588     // Returns the base node of the iterator
   589     Node baseNode(const IncEdgeIt &edge) const {
   590       return edge._direction ? this->u(edge) : this->v(edge);
   591     }
   592     // Running node of the iterator
   593     //
   594     // Returns the running node of the iterator
   595     Node runningNode(const IncEdgeIt &edge) const {
   596       return edge._direction ? this->v(edge) : this->u(edge);
   597     }
   598 
   599     // Mappable extension
   600 
   601     template <typename _Value>
   602     class NodeMap
   603       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   604       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   605 
   606     public:
   607       explicit NodeMap(const Graph& graph)
   608         : Parent(graph) {}
   609       NodeMap(const Graph& graph, const _Value& value)
   610         : Parent(graph, value) {}
   611 
   612     private:
   613       NodeMap& operator=(const NodeMap& cmap) {
   614         return operator=<NodeMap>(cmap);
   615       }
   616 
   617       template <typename CMap>
   618       NodeMap& operator=(const CMap& cmap) {
   619         Parent::operator=(cmap);
   620         return *this;
   621       }
   622 
   623     };
   624 
   625     template <typename _Value>
   626     class ArcMap
   627       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   628       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   629 
   630     public:
   631       explicit ArcMap(const Graph& graph)
   632         : Parent(graph) {}
   633       ArcMap(const Graph& graph, const _Value& value)
   634         : Parent(graph, value) {}
   635 
   636     private:
   637       ArcMap& operator=(const ArcMap& cmap) {
   638         return operator=<ArcMap>(cmap);
   639       }
   640 
   641       template <typename CMap>
   642       ArcMap& operator=(const CMap& cmap) {
   643         Parent::operator=(cmap);
   644         return *this;
   645       }
   646     };
   647 
   648 
   649     template <typename _Value>
   650     class EdgeMap
   651       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   652       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   653 
   654     public:
   655       explicit EdgeMap(const Graph& graph)
   656         : Parent(graph) {}
   657 
   658       EdgeMap(const Graph& graph, const _Value& value)
   659         : Parent(graph, value) {}
   660 
   661     private:
   662       EdgeMap& operator=(const EdgeMap& cmap) {
   663         return operator=<EdgeMap>(cmap);
   664       }
   665 
   666       template <typename CMap>
   667       EdgeMap& operator=(const CMap& cmap) {
   668         Parent::operator=(cmap);
   669         return *this;
   670       }
   671 
   672     };
   673 
   674     // Alteration extension
   675 
   676     Node addNode() {
   677       Node node = Parent::addNode();
   678       notifier(Node()).add(node);
   679       return node;
   680     }
   681 
   682     Edge addEdge(const Node& from, const Node& to) {
   683       Edge edge = Parent::addEdge(from, to);
   684       notifier(Edge()).add(edge);
   685       std::vector<Arc> ev;
   686       ev.push_back(Parent::direct(edge, true));
   687       ev.push_back(Parent::direct(edge, false));
   688       notifier(Arc()).add(ev);
   689       return edge;
   690     }
   691 
   692     void clear() {
   693       notifier(Arc()).clear();
   694       notifier(Edge()).clear();
   695       notifier(Node()).clear();
   696       Parent::clear();
   697     }
   698 
   699     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   700     void build(const Graph& graph, NodeRefMap& nodeRef,
   701                EdgeRefMap& edgeRef) {
   702       Parent::build(graph, nodeRef, edgeRef);
   703       notifier(Node()).build();
   704       notifier(Edge()).build();
   705       notifier(Arc()).build();
   706     }
   707 
   708     void erase(const Node& node) {
   709       Arc arc;
   710       Parent::firstOut(arc, node);
   711       while (arc != INVALID ) {
   712         erase(arc);
   713         Parent::firstOut(arc, node);
   714       }
   715 
   716       Parent::firstIn(arc, node);
   717       while (arc != INVALID ) {
   718         erase(arc);
   719         Parent::firstIn(arc, node);
   720       }
   721 
   722       notifier(Node()).erase(node);
   723       Parent::erase(node);
   724     }
   725 
   726     void erase(const Edge& edge) {
   727       std::vector<Arc> av;
   728       av.push_back(Parent::direct(edge, true));
   729       av.push_back(Parent::direct(edge, false));
   730       notifier(Arc()).erase(av);
   731       notifier(Edge()).erase(edge);
   732       Parent::erase(edge);
   733     }
   734 
   735     GraphExtender() {
   736       node_notifier.setContainer(*this);
   737       arc_notifier.setContainer(*this);
   738       edge_notifier.setContainer(*this);
   739     }
   740 
   741     ~GraphExtender() {
   742       edge_notifier.clear();
   743       arc_notifier.clear();
   744       node_notifier.clear();
   745     }
   746 
   747   };
   748 
   749   // \ingroup _graphbits
   750   //
   751   // \brief Extender for the BpGraphs
   752   template <typename Base>
   753   class BpGraphExtender : public Base {
   754     typedef Base Parent;
   755 
   756   public:
   757 
   758     typedef BpGraphExtender BpGraph;
   759 
   760     typedef True UndirectedTag;
   761 
   762     typedef typename Parent::Node Node;
   763     typedef typename Parent::RedNode RedNode;
   764     typedef typename Parent::BlueNode BlueNode;
   765     typedef typename Parent::Arc Arc;
   766     typedef typename Parent::Edge Edge;
   767 
   768     // BpGraph extension
   769 
   770     using Parent::first;
   771     using Parent::next;
   772     using Parent::id;
   773 
   774     int maxId(Node) const {
   775       return Parent::maxNodeId();
   776     }
   777 
   778     int maxId(RedNode) const {
   779       return Parent::maxRedId();
   780     }
   781 
   782     int maxId(BlueNode) const {
   783       return Parent::maxBlueId();
   784     }
   785 
   786     int maxId(Arc) const {
   787       return Parent::maxArcId();
   788     }
   789 
   790     int maxId(Edge) const {
   791       return Parent::maxEdgeId();
   792     }
   793 
   794     static Node fromId(int id, Node) {
   795       return Parent::nodeFromId(id);
   796     }
   797 
   798     static Arc fromId(int id, Arc) {
   799       return Parent::arcFromId(id);
   800     }
   801 
   802     static Edge fromId(int id, Edge) {
   803       return Parent::edgeFromId(id);
   804     }
   805 
   806     Node u(Edge e) const { return this->redNode(e); }
   807     Node v(Edge e) const { return this->blueNode(e); }
   808 
   809     Node oppositeNode(const Node &n, const Edge &e) const {
   810       if( n == u(e))
   811         return v(e);
   812       else if( n == v(e))
   813         return u(e);
   814       else
   815         return INVALID;
   816     }
   817 
   818     Arc oppositeArc(const Arc &arc) const {
   819       return Parent::direct(arc, !Parent::direction(arc));
   820     }
   821 
   822     using Parent::direct;
   823     Arc direct(const Edge &edge, const Node &node) const {
   824       return Parent::direct(edge, Parent::redNode(edge) == node);
   825     }
   826 
   827     RedNode asRedNode(const Node& node) const {
   828       if (node == INVALID || Parent::blue(node)) {
   829         return INVALID;
   830       } else {
   831         return Parent::asRedNodeUnsafe(node);
   832       }
   833     }
   834 
   835     BlueNode asBlueNode(const Node& node) const {
   836       if (node == INVALID || Parent::red(node)) {
   837         return INVALID;
   838       } else {
   839         return Parent::asBlueNodeUnsafe(node);
   840       }
   841     }
   842 
   843     // Alterable extension
   844 
   845     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
   846     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; 
   847     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
   848     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
   849     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
   850 
   851 
   852   protected:
   853 
   854     mutable NodeNotifier node_notifier;
   855     mutable RedNodeNotifier red_node_notifier;
   856     mutable BlueNodeNotifier blue_node_notifier;
   857     mutable ArcNotifier arc_notifier;
   858     mutable EdgeNotifier edge_notifier;
   859 
   860   public:
   861 
   862     NodeNotifier& notifier(Node) const {
   863       return node_notifier;
   864     }
   865 
   866     RedNodeNotifier& notifier(RedNode) const {
   867       return red_node_notifier;
   868     }
   869 
   870     BlueNodeNotifier& notifier(BlueNode) const {
   871       return blue_node_notifier;
   872     }
   873 
   874     ArcNotifier& notifier(Arc) const {
   875       return arc_notifier;
   876     }
   877 
   878     EdgeNotifier& notifier(Edge) const {
   879       return edge_notifier;
   880     }
   881 
   882 
   883 
   884     class NodeIt : public Node {
   885       const BpGraph* _graph;
   886     public:
   887 
   888       NodeIt() {}
   889 
   890       NodeIt(Invalid i) : Node(i) { }
   891 
   892       explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
   893         _graph->first(static_cast<Node&>(*this));
   894       }
   895 
   896       NodeIt(const BpGraph& graph, const Node& node)
   897         : Node(node), _graph(&graph) {}
   898 
   899       NodeIt& operator++() {
   900         _graph->next(*this);
   901         return *this;
   902       }
   903 
   904     };
   905 
   906     class RedNodeIt : public RedNode {
   907       const BpGraph* _graph;
   908     public:
   909 
   910       RedNodeIt() {}
   911 
   912       RedNodeIt(Invalid i) : RedNode(i) { }
   913 
   914       explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {
   915         _graph->first(static_cast<RedNode&>(*this));
   916       }
   917 
   918       RedNodeIt(const BpGraph& graph, const RedNode& node)
   919         : RedNode(node), _graph(&graph) {}
   920 
   921       RedNodeIt& operator++() {
   922         _graph->next(static_cast<RedNode&>(*this));
   923         return *this;
   924       }
   925 
   926     };
   927 
   928     class BlueNodeIt : public BlueNode {
   929       const BpGraph* _graph;
   930     public:
   931 
   932       BlueNodeIt() {}
   933 
   934       BlueNodeIt(Invalid i) : BlueNode(i) { }
   935 
   936       explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {
   937         _graph->first(static_cast<BlueNode&>(*this));
   938       }
   939 
   940       BlueNodeIt(const BpGraph& graph, const BlueNode& node)
   941         : BlueNode(node), _graph(&graph) {}
   942 
   943       BlueNodeIt& operator++() {
   944         _graph->next(static_cast<BlueNode&>(*this));
   945         return *this;
   946       }
   947 
   948     };
   949 
   950 
   951     class ArcIt : public Arc {
   952       const BpGraph* _graph;
   953     public:
   954 
   955       ArcIt() { }
   956 
   957       ArcIt(Invalid i) : Arc(i) { }
   958 
   959       explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
   960         _graph->first(static_cast<Arc&>(*this));
   961       }
   962 
   963       ArcIt(const BpGraph& graph, const Arc& arc) :
   964         Arc(arc), _graph(&graph) { }
   965 
   966       ArcIt& operator++() {
   967         _graph->next(*this);
   968         return *this;
   969       }
   970 
   971     };
   972 
   973 
   974     class OutArcIt : public Arc {
   975       const BpGraph* _graph;
   976     public:
   977 
   978       OutArcIt() { }
   979 
   980       OutArcIt(Invalid i) : Arc(i) { }
   981 
   982       OutArcIt(const BpGraph& graph, const Node& node)
   983         : _graph(&graph) {
   984         _graph->firstOut(*this, node);
   985       }
   986 
   987       OutArcIt(const BpGraph& graph, const Arc& arc)
   988         : Arc(arc), _graph(&graph) {}
   989 
   990       OutArcIt& operator++() {
   991         _graph->nextOut(*this);
   992         return *this;
   993       }
   994 
   995     };
   996 
   997 
   998     class InArcIt : public Arc {
   999       const BpGraph* _graph;
  1000     public:
  1001 
  1002       InArcIt() { }
  1003 
  1004       InArcIt(Invalid i) : Arc(i) { }
  1005 
  1006       InArcIt(const BpGraph& graph, const Node& node)
  1007         : _graph(&graph) {
  1008         _graph->firstIn(*this, node);
  1009       }
  1010 
  1011       InArcIt(const BpGraph& graph, const Arc& arc) :
  1012         Arc(arc), _graph(&graph) {}
  1013 
  1014       InArcIt& operator++() {
  1015         _graph->nextIn(*this);
  1016         return *this;
  1017       }
  1018 
  1019     };
  1020 
  1021 
  1022     class EdgeIt : public Parent::Edge {
  1023       const BpGraph* _graph;
  1024     public:
  1025 
  1026       EdgeIt() { }
  1027 
  1028       EdgeIt(Invalid i) : Edge(i) { }
  1029 
  1030       explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
  1031         _graph->first(static_cast<Edge&>(*this));
  1032       }
  1033 
  1034       EdgeIt(const BpGraph& graph, const Edge& edge) :
  1035         Edge(edge), _graph(&graph) { }
  1036 
  1037       EdgeIt& operator++() {
  1038         _graph->next(*this);
  1039         return *this;
  1040       }
  1041 
  1042     };
  1043 
  1044     class IncEdgeIt : public Parent::Edge {
  1045       friend class BpGraphExtender;
  1046       const BpGraph* _graph;
  1047       bool _direction;
  1048     public:
  1049 
  1050       IncEdgeIt() { }
  1051 
  1052       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
  1053 
  1054       IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
  1055         _graph->firstInc(*this, _direction, node);
  1056       }
  1057 
  1058       IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
  1059         : _graph(&graph), Edge(edge) {
  1060         _direction = (_graph->source(edge) == node);
  1061       }
  1062 
  1063       IncEdgeIt& operator++() {
  1064         _graph->nextInc(*this, _direction);
  1065         return *this;
  1066       }
  1067     };
  1068 
  1069     // \brief Base node of the iterator
  1070     //
  1071     // Returns the base node (ie. the source in this case) of the iterator
  1072     Node baseNode(const OutArcIt &arc) const {
  1073       return Parent::source(static_cast<const Arc&>(arc));
  1074     }
  1075     // \brief Running node of the iterator
  1076     //
  1077     // Returns the running node (ie. the target in this case) of the
  1078     // iterator
  1079     Node runningNode(const OutArcIt &arc) const {
  1080       return Parent::target(static_cast<const Arc&>(arc));
  1081     }
  1082 
  1083     // \brief Base node of the iterator
  1084     //
  1085     // Returns the base node (ie. the target in this case) of the iterator
  1086     Node baseNode(const InArcIt &arc) const {
  1087       return Parent::target(static_cast<const Arc&>(arc));
  1088     }
  1089     // \brief Running node of the iterator
  1090     //
  1091     // Returns the running node (ie. the source in this case) of the
  1092     // iterator
  1093     Node runningNode(const InArcIt &arc) const {
  1094       return Parent::source(static_cast<const Arc&>(arc));
  1095     }
  1096 
  1097     // Base node of the iterator
  1098     //
  1099     // Returns the base node of the iterator
  1100     Node baseNode(const IncEdgeIt &edge) const {
  1101       return edge._direction ? this->u(edge) : this->v(edge);
  1102     }
  1103     // Running node of the iterator
  1104     //
  1105     // Returns the running node of the iterator
  1106     Node runningNode(const IncEdgeIt &edge) const {
  1107       return edge._direction ? this->v(edge) : this->u(edge);
  1108     }
  1109 
  1110     // Mappable extension
  1111 
  1112     template <typename _Value>
  1113     class NodeMap
  1114       : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
  1115       typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
  1116 
  1117     public:
  1118       explicit NodeMap(const BpGraph& bpgraph)
  1119         : Parent(bpgraph) {}
  1120       NodeMap(const BpGraph& bpgraph, const _Value& value)
  1121         : Parent(bpgraph, value) {}
  1122 
  1123     private:
  1124       NodeMap& operator=(const NodeMap& cmap) {
  1125         return operator=<NodeMap>(cmap);
  1126       }
  1127 
  1128       template <typename CMap>
  1129       NodeMap& operator=(const CMap& cmap) {
  1130         Parent::operator=(cmap);
  1131         return *this;
  1132       }
  1133 
  1134     };
  1135 
  1136     template <typename _Value>
  1137     class RedNodeMap
  1138       : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
  1139       typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
  1140 
  1141     public:
  1142       explicit RedNodeMap(const BpGraph& bpgraph)
  1143         : Parent(bpgraph) {}
  1144       RedNodeMap(const BpGraph& bpgraph, const _Value& value)
  1145         : Parent(bpgraph, value) {}
  1146 
  1147     private:
  1148       RedNodeMap& operator=(const RedNodeMap& cmap) {
  1149         return operator=<RedNodeMap>(cmap);
  1150       }
  1151 
  1152       template <typename CMap>
  1153       RedNodeMap& operator=(const CMap& cmap) {
  1154         Parent::operator=(cmap);
  1155         return *this;
  1156       }
  1157 
  1158     };
  1159 
  1160     template <typename _Value>
  1161     class BlueNodeMap
  1162       : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
  1163       typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
  1164 
  1165     public:
  1166       explicit BlueNodeMap(const BpGraph& bpgraph)
  1167         : Parent(bpgraph) {}
  1168       BlueNodeMap(const BpGraph& bpgraph, const _Value& value)
  1169         : Parent(bpgraph, value) {}
  1170 
  1171     private:
  1172       BlueNodeMap& operator=(const BlueNodeMap& cmap) {
  1173         return operator=<BlueNodeMap>(cmap);
  1174       }
  1175 
  1176       template <typename CMap>
  1177       BlueNodeMap& operator=(const CMap& cmap) {
  1178         Parent::operator=(cmap);
  1179         return *this;
  1180       }
  1181 
  1182     };
  1183 
  1184     template <typename _Value>
  1185     class ArcMap
  1186       : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
  1187       typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
  1188 
  1189     public:
  1190       explicit ArcMap(const BpGraph& graph)
  1191         : Parent(graph) {}
  1192       ArcMap(const BpGraph& graph, const _Value& value)
  1193         : Parent(graph, value) {}
  1194 
  1195     private:
  1196       ArcMap& operator=(const ArcMap& cmap) {
  1197         return operator=<ArcMap>(cmap);
  1198       }
  1199 
  1200       template <typename CMap>
  1201       ArcMap& operator=(const CMap& cmap) {
  1202         Parent::operator=(cmap);
  1203         return *this;
  1204       }
  1205     };
  1206 
  1207 
  1208     template <typename _Value>
  1209     class EdgeMap
  1210       : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
  1211       typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
  1212 
  1213     public:
  1214       explicit EdgeMap(const BpGraph& graph)
  1215         : Parent(graph) {}
  1216 
  1217       EdgeMap(const BpGraph& graph, const _Value& value)
  1218         : Parent(graph, value) {}
  1219 
  1220     private:
  1221       EdgeMap& operator=(const EdgeMap& cmap) {
  1222         return operator=<EdgeMap>(cmap);
  1223       }
  1224 
  1225       template <typename CMap>
  1226       EdgeMap& operator=(const CMap& cmap) {
  1227         Parent::operator=(cmap);
  1228         return *this;
  1229       }
  1230 
  1231     };
  1232 
  1233     // Alteration extension
  1234 
  1235     RedNode addRedNode() {
  1236       RedNode node = Parent::addRedNode();
  1237       notifier(RedNode()).add(node);
  1238       notifier(Node()).add(node);
  1239       return node;
  1240     }
  1241 
  1242     BlueNode addBlueNode() {
  1243       BlueNode node = Parent::addBlueNode();
  1244       notifier(BlueNode()).add(node);
  1245       notifier(Node()).add(node);
  1246       return node;
  1247     }
  1248 
  1249     Edge addEdge(const RedNode& from, const BlueNode& to) {
  1250       Edge edge = Parent::addEdge(from, to);
  1251       notifier(Edge()).add(edge);
  1252       std::vector<Arc> av;
  1253       av.push_back(Parent::direct(edge, true));
  1254       av.push_back(Parent::direct(edge, false));
  1255       notifier(Arc()).add(av);
  1256       return edge;
  1257     }
  1258 
  1259     void clear() {
  1260       notifier(Arc()).clear();
  1261       notifier(Edge()).clear();
  1262       notifier(Node()).clear();
  1263       notifier(BlueNode()).clear();
  1264       notifier(RedNode()).clear();
  1265       Parent::clear();
  1266     }
  1267 
  1268     template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
  1269     void build(const BpGraph& graph, NodeRefMap& nodeRef,
  1270                EdgeRefMap& edgeRef) {
  1271       Parent::build(graph, nodeRef, edgeRef);
  1272       notifier(RedNode()).build();
  1273       notifier(BlueNode()).build();
  1274       notifier(Node()).build();
  1275       notifier(Edge()).build();
  1276       notifier(Arc()).build();
  1277     }
  1278 
  1279     void erase(const Node& node) {
  1280       Arc arc;
  1281       Parent::firstOut(arc, node);
  1282       while (arc != INVALID ) {
  1283         erase(arc);
  1284         Parent::firstOut(arc, node);
  1285       }
  1286 
  1287       Parent::firstIn(arc, node);
  1288       while (arc != INVALID ) {
  1289         erase(arc);
  1290         Parent::firstIn(arc, node);
  1291       }
  1292 
  1293       if (Parent::red(node)) {
  1294         notifier(RedNode()).erase(this->asRedNodeUnsafe(node));
  1295       } else {
  1296         notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));
  1297       }
  1298 
  1299       notifier(Node()).erase(node);
  1300       Parent::erase(node);
  1301     }
  1302 
  1303     void erase(const Edge& edge) {
  1304       std::vector<Arc> av;
  1305       av.push_back(Parent::direct(edge, true));
  1306       av.push_back(Parent::direct(edge, false));
  1307       notifier(Arc()).erase(av);
  1308       notifier(Edge()).erase(edge);
  1309       Parent::erase(edge);
  1310     }
  1311 
  1312     BpGraphExtender() {
  1313       red_node_notifier.setContainer(*this);
  1314       blue_node_notifier.setContainer(*this);
  1315       node_notifier.setContainer(*this);
  1316       arc_notifier.setContainer(*this);
  1317       edge_notifier.setContainer(*this);
  1318     }
  1319 
  1320     ~BpGraphExtender() {
  1321       edge_notifier.clear();
  1322       arc_notifier.clear();
  1323       node_notifier.clear();
  1324       blue_node_notifier.clear();
  1325       red_node_notifier.clear();
  1326     }
  1327 
  1328   };
  1329 
  1330 }
  1331 
  1332 #endif