lemon: lemon/bits/graph_extender.h@699c7eac2c6d

     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  */

    19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H

    20 #define LEMON_BITS_GRAPH_EXTENDER_H

    22 #include <lemon/core.h>

    24 #include <lemon/bits/map_extender.h>

    25 #include <lemon/bits/default_map.h>

    27 #include <lemon/concept_check.h>

    28 #include <lemon/concepts/maps.h>

    30 //\ingroup graphbits

    31 //\file

    32 //\brief Extenders for the graph types

    33 namespace lemon {

    35   // \ingroup graphbits

    36   //

    37   // \brief Extender for the digraph implementations

    38   template <typename Base>

    39   class DigraphExtender : public Base {

    40     typedef Base Parent;

    42   public:

    44     typedef DigraphExtender Digraph;

    46     // Base extensions

    48     typedef typename Parent::Node Node;

    49     typedef typename Parent::Arc Arc;

    51     int maxId(Node) const {

    52       return Parent::maxNodeId();

    53     }

    55     int maxId(Arc) const {

    56       return Parent::maxArcId();

    57     }

    59     static Node fromId(int id, Node) {

    60       return Parent::nodeFromId(id);

    61     }

    63     static Arc fromId(int id, Arc) {

    64       return Parent::arcFromId(id);

    65     }

    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     }

    76     // Alterable extension

    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    79     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

    82   protected:

    84     mutable NodeNotifier node_notifier;

    85     mutable ArcNotifier arc_notifier;

    87   public:

    89     NodeNotifier& notifier(Node) const {

    90       return node_notifier;

    91     }

    93     ArcNotifier& notifier(Arc) const {

    94       return arc_notifier;

    95     }

    97     class NodeIt : public Node {

    98       const Digraph* _digraph;

    99     public:

   101       NodeIt() {}

   103       NodeIt(Invalid i) : Node(i) { }

   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {

   106         _digraph->first(static_cast<Node&>(*this));

   107       }

   109       NodeIt(const Digraph& digraph, const Node& node)

   110         : Node(node), _digraph(&digraph) {}

   112       NodeIt& operator++() {

   113         _digraph->next(*this);

   114         return *this;

   115       }

   117     };

   120     class ArcIt : public Arc {

   121       const Digraph* _digraph;

   122     public:

   124       ArcIt() { }

   126       ArcIt(Invalid i) : Arc(i) { }

   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {

   129         _digraph->first(static_cast<Arc&>(*this));

   130       }

   132       ArcIt(const Digraph& digraph, const Arc& arc) :

   133         Arc(arc), _digraph(&digraph) { }

   135       ArcIt& operator++() {

   136         _digraph->next(*this);

   137         return *this;

   138       }

   140     };

   143     class OutArcIt : public Arc {

   144       const Digraph* _digraph;

   145     public:

   147       OutArcIt() { }

   149       OutArcIt(Invalid i) : Arc(i) { }

   151       OutArcIt(const Digraph& digraph, const Node& node)

   152         : _digraph(&digraph) {

   153         _digraph->firstOut(*this, node);

   154       }

   156       OutArcIt(const Digraph& digraph, const Arc& arc)

   157         : Arc(arc), _digraph(&digraph) {}

   159       OutArcIt& operator++() {

   160         _digraph->nextOut(*this);

   161         return *this;

   162       }

   164     };

   167     class InArcIt : public Arc {

   168       const Digraph* _digraph;

   169     public:

   171       InArcIt() { }

   173       InArcIt(Invalid i) : Arc(i) { }

   175       InArcIt(const Digraph& digraph, const Node& node)

   176         : _digraph(&digraph) {

   177         _digraph->firstIn(*this, node);

   178       }

   180       InArcIt(const Digraph& digraph, const Arc& arc) :

   181         Arc(arc), _digraph(&digraph) {}

   183       InArcIt& operator++() {

   184         _digraph->nextIn(*this);

   185         return *this;

   186       }

   188     };

   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     }

   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     }

   219     template <typename _Value>

   220     class NodeMap

   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {

   222       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;

   224     public:

   225       explicit NodeMap(const Digraph& digraph)

   226         : Parent(digraph) {}

   227       NodeMap(const Digraph& digraph, const _Value& value)

   228         : Parent(digraph, value) {}

   230     private:

   231       NodeMap& operator=(const NodeMap& cmap) {

   232         return operator=<NodeMap>(cmap);

   233       }

   235       template <typename CMap>

   236       NodeMap& operator=(const CMap& cmap) {

   237         Parent::operator=(cmap);

   238         return *this;

   239       }

   241     };

   243     template <typename _Value>

   244     class ArcMap

   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {

   246       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;

   248     public:

   249       explicit ArcMap(const Digraph& digraph)

   250         : Parent(digraph) {}

   251       ArcMap(const Digraph& digraph, const _Value& value)

   252         : Parent(digraph, value) {}

   254     private:

   255       ArcMap& operator=(const ArcMap& cmap) {

   256         return operator=<ArcMap>(cmap);

   257       }

   259       template <typename CMap>

   260       ArcMap& operator=(const CMap& cmap) {

   261         Parent::operator=(cmap);

   262         return *this;

   263       }

   264     };

   267     Node addNode() {

   268       Node node = Parent::addNode();

   269       notifier(Node()).add(node);

   270       return node;

   271     }

   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     }

   279     void clear() {

   280       notifier(Arc()).clear();

   281       notifier(Node()).clear();

   282       Parent::clear();

   283     }

   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     }

   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       }

   300       Parent::firstIn(arc, node);

   301       while (arc != INVALID ) {

   302         erase(arc);

   303         Parent::firstIn(arc, node);

   304       }

   306       notifier(Node()).erase(node);

   307       Parent::erase(node);

   308     }

   310     void erase(const Arc& arc) {

   311       notifier(Arc()).erase(arc);

   312       Parent::erase(arc);

   313     }

   315     DigraphExtender() {

   316       node_notifier.setContainer(*this);

   317       arc_notifier.setContainer(*this);

   318     }

   321     ~DigraphExtender() {

   322       arc_notifier.clear();

   323       node_notifier.clear();

   324     }

   325   };

   327   // \ingroup _graphbits

   328   //

   329   // \brief Extender for the Graphs

   330   template <typename Base>

   331   class GraphExtender : public Base {

   332     typedef Base Parent;

   334   public:

   336     typedef GraphExtender Graph;

   338     typedef True UndirectedTag;

   340     typedef typename Parent::Node Node;

   341     typedef typename Parent::Arc Arc;

   342     typedef typename Parent::Edge Edge;

   344     // Graph extension

   346     int maxId(Node) const {

   347       return Parent::maxNodeId();

   348     }

   350     int maxId(Arc) const {

   351       return Parent::maxArcId();

   352     }

   354     int maxId(Edge) const {

   355       return Parent::maxEdgeId();

   356     }

   358     static Node fromId(int id, Node) {

   359       return Parent::nodeFromId(id);

   360     }

   362     static Arc fromId(int id, Arc) {

   363       return Parent::arcFromId(id);

   364     }

   366     static Edge fromId(int id, Edge) {

   367       return Parent::edgeFromId(id);

   368     }

   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     }

   379     Arc oppositeArc(const Arc &arc) const {

   380       return Parent::direct(arc, !Parent::direction(arc));

   381     }

   383     using Parent::direct;

   384     Arc direct(const Edge &edge, const Node &node) const {

   385       return Parent::direct(edge, Parent::u(edge) == node);

   386     }

   388     // Alterable extension

   390     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;

   391     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;

   392     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;

   395   protected:

   397     mutable NodeNotifier node_notifier;

   398     mutable ArcNotifier arc_notifier;

   399     mutable EdgeNotifier edge_notifier;

   401   public:

   403     NodeNotifier& notifier(Node) const {

   404       return node_notifier;

   405     }

   407     ArcNotifier& notifier(Arc) const {

   408       return arc_notifier;

   409     }

   411     EdgeNotifier& notifier(Edge) const {

   412       return edge_notifier;

   413     }

   417     class NodeIt : public Node {

   418       const Graph* _graph;

   419     public:

   421       NodeIt() {}

   423       NodeIt(Invalid i) : Node(i) { }

   425       explicit NodeIt(const Graph& graph) : _graph(&graph) {

   426         _graph->first(static_cast<Node&>(*this));

   427       }

   429       NodeIt(const Graph& graph, const Node& node)

   430         : Node(node), _graph(&graph) {}

   432       NodeIt& operator++() {

   433         _graph->next(*this);

   434         return *this;

   435       }

   437     };

   440     class ArcIt : public Arc {

   441       const Graph* _graph;

   442     public:

   444       ArcIt() { }

   446       ArcIt(Invalid i) : Arc(i) { }

   448       explicit ArcIt(const Graph& graph) : _graph(&graph) {

   449         _graph->first(static_cast<Arc&>(*this));

   450       }

   452       ArcIt(const Graph& graph, const Arc& arc) :

   453         Arc(arc), _graph(&graph) { }

   455       ArcIt& operator++() {

   456         _graph->next(*this);

   457         return *this;

   458       }

   460     };

   463     class OutArcIt : public Arc {

   464       const Graph* _graph;

   465     public:

   467       OutArcIt() { }

   469       OutArcIt(Invalid i) : Arc(i) { }

   471       OutArcIt(const Graph& graph, const Node& node)

   472         : _graph(&graph) {

   473         _graph->firstOut(*this, node);

   474       }

   476       OutArcIt(const Graph& graph, const Arc& arc)

   477         : Arc(arc), _graph(&graph) {}

   479       OutArcIt& operator++() {

   480         _graph->nextOut(*this);

   481         return *this;

   482       }

   484     };

   487     class InArcIt : public Arc {

   488       const Graph* _graph;

   489     public:

   491       InArcIt() { }

   493       InArcIt(Invalid i) : Arc(i) { }

   495       InArcIt(const Graph& graph, const Node& node)

   496         : _graph(&graph) {

   497         _graph->firstIn(*this, node);

   498       }

   500       InArcIt(const Graph& graph, const Arc& arc) :

   501         Arc(arc), _graph(&graph) {}

   503       InArcIt& operator++() {

   504         _graph->nextIn(*this);

   505         return *this;

   506       }

   508     };

   511     class EdgeIt : public Parent::Edge {

   512       const Graph* _graph;

   513     public:

   515       EdgeIt() { }

   517       EdgeIt(Invalid i) : Edge(i) { }

   519       explicit EdgeIt(const Graph& graph) : _graph(&graph) {

   520         _graph->first(static_cast<Edge&>(*this));

   521       }

   523       EdgeIt(const Graph& graph, const Edge& edge) :

   524         Edge(edge), _graph(&graph) { }

   526       EdgeIt& operator++() {

   527         _graph->next(*this);

   528         return *this;

   529       }

   531     };

   533     class IncEdgeIt : public Parent::Edge {

   534       friend class GraphExtender;

   535       const Graph* _graph;

   536       bool _direction;

   537     public:

   539       IncEdgeIt() { }

   541       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }

   543       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {

   544         _graph->firstInc(*this, _direction, node);

   545       }

   547       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)

   548         : _graph(&graph), Edge(edge) {

   549         _direction = (_graph->source(edge) == node);

   550       }

   552       IncEdgeIt& operator++() {

   553         _graph->nextInc(*this, _direction);

   554         return *this;

   555       }

   556     };

   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     }

   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     }

   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     }

   599     // Mappable extension

   601     template <typename _Value>

   602     class NodeMap

   603       : public MapExtender<DefaultMap<Graph, Node, _Value> > {

   604       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;

   606     public:

   607       explicit NodeMap(const Graph& graph)

   608         : Parent(graph) {}

   609       NodeMap(const Graph& graph, const _Value& value)

   610         : Parent(graph, value) {}

   612     private:

   613       NodeMap& operator=(const NodeMap& cmap) {

   614         return operator=<NodeMap>(cmap);

   615       }

   617       template <typename CMap>

   618       NodeMap& operator=(const CMap& cmap) {

   619         Parent::operator=(cmap);

   620         return *this;

   621       }

   623     };

   625     template <typename _Value>

   626     class ArcMap

   627       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

   628       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

   630     public:

   631       explicit ArcMap(const Graph& graph)

   632         : Parent(graph) {}

   633       ArcMap(const Graph& graph, const _Value& value)

   634         : Parent(graph, value) {}

   636     private:

   637       ArcMap& operator=(const ArcMap& cmap) {

   638         return operator=<ArcMap>(cmap);

   639       }

   641       template <typename CMap>

   642       ArcMap& operator=(const CMap& cmap) {

   643         Parent::operator=(cmap);

   644         return *this;

   645       }

   646     };

   649     template <typename _Value>

   650     class EdgeMap

   651       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

   652       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   654     public:

   655       explicit EdgeMap(const Graph& graph)

   656         : Parent(graph) {}

   658       EdgeMap(const Graph& graph, const _Value& value)

   659         : Parent(graph, value) {}

   661     private:

   662       EdgeMap& operator=(const EdgeMap& cmap) {

   663         return operator=<EdgeMap>(cmap);

   664       }

   666       template <typename CMap>

   667       EdgeMap& operator=(const CMap& cmap) {

   668         Parent::operator=(cmap);

   669         return *this;

   670       }

   672     };

   674     // Alteration extension

   676     Node addNode() {

   677       Node node = Parent::addNode();

   678       notifier(Node()).add(node);

   679       return node;

   680     }

   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     }

   692     void clear() {

   693       notifier(Arc()).clear();

   694       notifier(Edge()).clear();

   695       notifier(Node()).clear();

   696       Parent::clear();

   697     }

   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     }

   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       }

   716       Parent::firstIn(arc, node);

   717       while (arc != INVALID ) {

   718         erase(arc);

   719         Parent::firstIn(arc, node);

   720       }

   722       notifier(Node()).erase(node);

   723       Parent::erase(node);

   724     }

   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     }

   735     GraphExtender() {

   736       node_notifier.setContainer(*this);

   737       arc_notifier.setContainer(*this);

   738       edge_notifier.setContainer(*this);

   739     }

   741     ~GraphExtender() {

   742       edge_notifier.clear();

   743       arc_notifier.clear();

   744       node_notifier.clear();

   745     }

   747   };

   749   // \ingroup _graphbits

   750   //

   751   // \brief Extender for the BpGraphs

   752   template <typename Base>

   753   class BpGraphExtender : public Base {

   754     typedef Base Parent;

   756   public:

   758     typedef BpGraphExtender BpGraph;

   760     typedef True UndirectedTag;

   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;

   768     // BpGraph extension

   770     using Parent::first;

   771     using Parent::next;

   772     using Parent::id;

   774     int maxId(Node) const {

   775       return Parent::maxNodeId();

   776     }

   778     int maxId(RedNode) const {

   779       return Parent::maxRedId();

   780     }

   782     int maxId(BlueNode) const {

   783       return Parent::maxBlueId();

   784     }

   786     int maxId(Arc) const {

   787       return Parent::maxArcId();

   788     }

   790     int maxId(Edge) const {

   791       return Parent::maxEdgeId();

   792     }

   794     static Node fromId(int id, Node) {

   795       return Parent::nodeFromId(id);

   796     }

   798     static Arc fromId(int id, Arc) {

   799       return Parent::arcFromId(id);

   800     }

   802     static Edge fromId(int id, Edge) {

   803       return Parent::edgeFromId(id);

   804     }

   806     Node u(Edge e) const { return this->redNode(e); }

   807     Node v(Edge e) const { return this->blueNode(e); }

   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     }

   818     Arc oppositeArc(const Arc &arc) const {

   819       return Parent::direct(arc, !Parent::direction(arc));

   820     }

   822     using Parent::direct;

   823     Arc direct(const Edge &edge, const Node &node) const {

   824       return Parent::direct(edge, Parent::redNode(edge) == node);

   825     }

   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     }

   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     }

   843     std::pair<RedNode, BlueNode> asRedBlueNode(const Node& node) const {

   844       if (node == INVALID) {

   845         return std::make_pair(RedNode(INVALID), BlueNode(INVALID));

   846       } else if (Parent::red(node)) {

   847         return std::make_pair(Parent::asRedNodeUnsafe(node), BlueNode(INVALID));

   848       } else {

   849         return std::make_pair(RedNode(INVALID), Parent::asBlueNodeUnsafe(node));

   850       }

   851     }

   853     // Alterable extension

   855     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;

   856     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;

   857     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;

   858     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;

   859     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;

   862   protected:

   864     mutable NodeNotifier node_notifier;

   865     mutable RedNodeNotifier red_node_notifier;

   866     mutable BlueNodeNotifier blue_node_notifier;

   867     mutable ArcNotifier arc_notifier;

   868     mutable EdgeNotifier edge_notifier;

   870   public:

   872     NodeNotifier& notifier(Node) const {

   873       return node_notifier;

   874     }

   876     RedNodeNotifier& notifier(RedNode) const {

   877       return red_node_notifier;

   878     }

   880     BlueNodeNotifier& notifier(BlueNode) const {

   881       return blue_node_notifier;

   882     }

   884     ArcNotifier& notifier(Arc) const {

   885       return arc_notifier;

   886     }

   888     EdgeNotifier& notifier(Edge) const {

   889       return edge_notifier;

   890     }

   894     class NodeIt : public Node {

   895       const BpGraph* _graph;

   896     public:

   898       NodeIt() {}

   900       NodeIt(Invalid i) : Node(i) { }

   902       explicit NodeIt(const BpGraph& graph) : _graph(&graph) {

   903         _graph->first(static_cast<Node&>(*this));

   904       }

   906       NodeIt(const BpGraph& graph, const Node& node)

   907         : Node(node), _graph(&graph) {}

   909       NodeIt& operator++() {

   910         _graph->next(*this);

   911         return *this;

   912       }

   914     };

   916     class RedNodeIt : public RedNode {

   917       const BpGraph* _graph;

   918     public:

   920       RedNodeIt() {}

   922       RedNodeIt(Invalid i) : RedNode(i) { }

   924       explicit RedNodeIt(const BpGraph& graph) : _graph(&graph) {

   925         _graph->first(static_cast<RedNode&>(*this));

   926       }

   928       RedNodeIt(const BpGraph& graph, const RedNode& node)

   929         : RedNode(node), _graph(&graph) {}

   931       RedNodeIt& operator++() {

   932         _graph->next(static_cast<RedNode&>(*this));

   933         return *this;

   934       }

   936     };

   938     class BlueNodeIt : public BlueNode {

   939       const BpGraph* _graph;

   940     public:

   942       BlueNodeIt() {}

   944       BlueNodeIt(Invalid i) : BlueNode(i) { }

   946       explicit BlueNodeIt(const BpGraph& graph) : _graph(&graph) {

   947         _graph->first(static_cast<BlueNode&>(*this));

   948       }

   950       BlueNodeIt(const BpGraph& graph, const BlueNode& node)

   951         : BlueNode(node), _graph(&graph) {}

   953       BlueNodeIt& operator++() {

   954         _graph->next(static_cast<BlueNode&>(*this));

   955         return *this;

   956       }

   958     };

   961     class ArcIt : public Arc {

   962       const BpGraph* _graph;

   963     public:

   965       ArcIt() { }

   967       ArcIt(Invalid i) : Arc(i) { }

   969       explicit ArcIt(const BpGraph& graph) : _graph(&graph) {

   970         _graph->first(static_cast<Arc&>(*this));

   971       }

   973       ArcIt(const BpGraph& graph, const Arc& arc) :

   974         Arc(arc), _graph(&graph) { }

   976       ArcIt& operator++() {

   977         _graph->next(*this);

   978         return *this;

   979       }

   981     };

   984     class OutArcIt : public Arc {

   985       const BpGraph* _graph;

   986     public:

   988       OutArcIt() { }

   990       OutArcIt(Invalid i) : Arc(i) { }

   992       OutArcIt(const BpGraph& graph, const Node& node)

   993         : _graph(&graph) {

   994         _graph->firstOut(*this, node);

   995       }

   997       OutArcIt(const BpGraph& graph, const Arc& arc)

   998         : Arc(arc), _graph(&graph) {}

  1000       OutArcIt& operator++() {

  1001         _graph->nextOut(*this);

  1002         return *this;

  1003       }

  1005     };

  1008     class InArcIt : public Arc {

  1009       const BpGraph* _graph;

  1010     public:

  1012       InArcIt() { }

  1014       InArcIt(Invalid i) : Arc(i) { }

  1016       InArcIt(const BpGraph& graph, const Node& node)

  1017         : _graph(&graph) {

  1018         _graph->firstIn(*this, node);

  1019       }

  1021       InArcIt(const BpGraph& graph, const Arc& arc) :

  1022         Arc(arc), _graph(&graph) {}

  1024       InArcIt& operator++() {

  1025         _graph->nextIn(*this);

  1026         return *this;

  1027       }

  1029     };

  1032     class EdgeIt : public Parent::Edge {

  1033       const BpGraph* _graph;

  1034     public:

  1036       EdgeIt() { }

  1038       EdgeIt(Invalid i) : Edge(i) { }

  1040       explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {

  1041         _graph->first(static_cast<Edge&>(*this));

  1042       }

  1044       EdgeIt(const BpGraph& graph, const Edge& edge) :

  1045         Edge(edge), _graph(&graph) { }

  1047       EdgeIt& operator++() {

  1048         _graph->next(*this);

  1049         return *this;

  1050       }

  1052     };

  1054     class IncEdgeIt : public Parent::Edge {

  1055       friend class BpGraphExtender;

  1056       const BpGraph* _graph;

  1057       bool _direction;

  1058     public:

  1060       IncEdgeIt() { }

  1062       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }

  1064       IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {

  1065         _graph->firstInc(*this, _direction, node);

  1066       }

  1068       IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)

  1069         : _graph(&graph), Edge(edge) {

  1070         _direction = (_graph->source(edge) == node);

  1071       }

  1073       IncEdgeIt& operator++() {

  1074         _graph->nextInc(*this, _direction);

  1075         return *this;

  1076       }

  1077     };

  1079     // \brief Base node of the iterator

  1080     //

  1081     // Returns the base node (ie. the source in this case) of the iterator

  1082     Node baseNode(const OutArcIt &arc) const {

  1083       return Parent::source(static_cast<const Arc&>(arc));

  1084     }

  1085     // \brief Running node of the iterator

  1086     //

  1087     // Returns the running node (ie. the target in this case) of the

  1088     // iterator

  1089     Node runningNode(const OutArcIt &arc) const {

  1090       return Parent::target(static_cast<const Arc&>(arc));

  1091     }

  1093     // \brief Base node of the iterator

  1094     //

  1095     // Returns the base node (ie. the target in this case) of the iterator

  1096     Node baseNode(const InArcIt &arc) const {

  1097       return Parent::target(static_cast<const Arc&>(arc));

  1098     }

  1099     // \brief Running node of the iterator

  1100     //

  1101     // Returns the running node (ie. the source in this case) of the

  1102     // iterator

  1103     Node runningNode(const InArcIt &arc) const {

  1104       return Parent::source(static_cast<const Arc&>(arc));

  1105     }

  1107     // Base node of the iterator

  1108     //

  1109     // Returns the base node of the iterator

  1110     Node baseNode(const IncEdgeIt &edge) const {

  1111       return edge._direction ? this->u(edge) : this->v(edge);

  1112     }

  1113     // Running node of the iterator

  1114     //

  1115     // Returns the running node of the iterator

  1116     Node runningNode(const IncEdgeIt &edge) const {

  1117       return edge._direction ? this->v(edge) : this->u(edge);

  1118     }

  1120     // Mappable extension

  1122     template <typename _Value>

  1123     class NodeMap

  1124       : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {

  1125       typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;

  1127     public:

  1128       explicit NodeMap(const BpGraph& bpgraph)

  1129         : Parent(bpgraph) {}

  1130       NodeMap(const BpGraph& bpgraph, const _Value& value)

  1131         : Parent(bpgraph, value) {}

  1133     private:

  1134       NodeMap& operator=(const NodeMap& cmap) {

  1135         return operator=<NodeMap>(cmap);

  1136       }

  1138       template <typename CMap>

  1139       NodeMap& operator=(const CMap& cmap) {

  1140         Parent::operator=(cmap);

  1141         return *this;

  1142       }

  1144     };

  1146     template <typename _Value>

  1147     class RedNodeMap

  1148       : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {

  1149       typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;

  1151     public:

  1152       explicit RedNodeMap(const BpGraph& bpgraph)

  1153         : Parent(bpgraph) {}

  1154       RedNodeMap(const BpGraph& bpgraph, const _Value& value)

  1155         : Parent(bpgraph, value) {}

  1157     private:

  1158       RedNodeMap& operator=(const RedNodeMap& cmap) {

  1159         return operator=<RedNodeMap>(cmap);

  1160       }

  1162       template <typename CMap>

  1163       RedNodeMap& operator=(const CMap& cmap) {

  1164         Parent::operator=(cmap);

  1165         return *this;

  1166       }

  1168     };

  1170     template <typename _Value>

  1171     class BlueNodeMap

  1172       : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {

  1173       typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;

  1175     public:

  1176       explicit BlueNodeMap(const BpGraph& bpgraph)

  1177         : Parent(bpgraph) {}

  1178       BlueNodeMap(const BpGraph& bpgraph, const _Value& value)

  1179         : Parent(bpgraph, value) {}

  1181     private:

  1182       BlueNodeMap& operator=(const BlueNodeMap& cmap) {

  1183         return operator=<BlueNodeMap>(cmap);

  1184       }

  1186       template <typename CMap>

  1187       BlueNodeMap& operator=(const CMap& cmap) {

  1188         Parent::operator=(cmap);

  1189         return *this;

  1190       }

  1192     };

  1194     template <typename _Value>

  1195     class ArcMap

  1196       : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {

  1197       typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;

  1199     public:

  1200       explicit ArcMap(const BpGraph& graph)

  1201         : Parent(graph) {}

  1202       ArcMap(const BpGraph& graph, const _Value& value)

  1203         : Parent(graph, value) {}

  1205     private:

  1206       ArcMap& operator=(const ArcMap& cmap) {

  1207         return operator=<ArcMap>(cmap);

  1208       }

  1210       template <typename CMap>

  1211       ArcMap& operator=(const CMap& cmap) {

  1212         Parent::operator=(cmap);

  1213         return *this;

  1214       }

  1215     };

  1218     template <typename _Value>

  1219     class EdgeMap

  1220       : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {

  1221       typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;

  1223     public:

  1224       explicit EdgeMap(const BpGraph& graph)

  1225         : Parent(graph) {}

  1227       EdgeMap(const BpGraph& graph, const _Value& value)

  1228         : Parent(graph, value) {}

  1230     private:

  1231       EdgeMap& operator=(const EdgeMap& cmap) {

  1232         return operator=<EdgeMap>(cmap);

  1233       }

  1235       template <typename CMap>

  1236       EdgeMap& operator=(const CMap& cmap) {

  1237         Parent::operator=(cmap);

  1238         return *this;

  1239       }

  1241     };

  1243     // Alteration extension

  1245     RedNode addRedNode() {

  1246       RedNode node = Parent::addRedNode();

  1247       notifier(RedNode()).add(node);

  1248       notifier(Node()).add(node);

  1249       return node;

  1250     }

  1252     BlueNode addBlueNode() {

  1253       BlueNode node = Parent::addBlueNode();

  1254       notifier(BlueNode()).add(node);

  1255       notifier(Node()).add(node);

  1256       return node;

  1257     }

  1259     Edge addEdge(const RedNode& from, const BlueNode& to) {

  1260       Edge edge = Parent::addEdge(from, to);

  1261       notifier(Edge()).add(edge);

  1262       std::vector<Arc> av;

  1263       av.push_back(Parent::direct(edge, true));

  1264       av.push_back(Parent::direct(edge, false));

  1265       notifier(Arc()).add(av);

  1266       return edge;

  1267     }

  1269     void clear() {

  1270       notifier(Arc()).clear();

  1271       notifier(Edge()).clear();

  1272       notifier(Node()).clear();

  1273       notifier(BlueNode()).clear();

  1274       notifier(RedNode()).clear();

  1275       Parent::clear();

  1276     }

  1278     template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>

  1279     void build(const BpGraph& graph, NodeRefMap& nodeRef,

  1280                EdgeRefMap& edgeRef) {

  1281       Parent::build(graph, nodeRef, edgeRef);

  1282       notifier(RedNode()).build();

  1283       notifier(BlueNode()).build();

  1284       notifier(Node()).build();

  1285       notifier(Edge()).build();

  1286       notifier(Arc()).build();

  1287     }

  1289     void erase(const Node& node) {

  1290       Arc arc;

  1291       Parent::firstOut(arc, node);

  1292       while (arc != INVALID ) {

  1293         erase(arc);

  1294         Parent::firstOut(arc, node);

  1295       }

  1297       Parent::firstIn(arc, node);

  1298       while (arc != INVALID ) {

  1299         erase(arc);

  1300         Parent::firstIn(arc, node);

  1301       }

  1303       if (Parent::red(node)) {

  1304         notifier(RedNode()).erase(this->asRedNodeUnsafe(node));

  1305       } else {

  1306         notifier(BlueNode()).erase(this->asBlueNodeUnsafe(node));

  1307       }

  1309       notifier(Node()).erase(node);

  1310       Parent::erase(node);

  1311     }

  1313     void erase(const Edge& edge) {

  1314       std::vector<Arc> av;

  1315       av.push_back(Parent::direct(edge, true));

  1316       av.push_back(Parent::direct(edge, false));

  1317       notifier(Arc()).erase(av);

  1318       notifier(Edge()).erase(edge);

  1319       Parent::erase(edge);

  1320     }

  1322     BpGraphExtender() {

  1323       red_node_notifier.setContainer(*this);

  1324       blue_node_notifier.setContainer(*this);

  1325       node_notifier.setContainer(*this);

  1326       arc_notifier.setContainer(*this);

  1327       edge_notifier.setContainer(*this);

  1328     }

  1330     ~BpGraphExtender() {

  1331       edge_notifier.clear();

  1332       arc_notifier.clear();

  1333       node_notifier.clear();

  1334       blue_node_notifier.clear();

  1335       red_node_notifier.clear();

  1336     }

  1338   };

  1340 }

  1342 #endif

author	Balazs Dezso <deba@inf.elte.hu>
	Wed, 11 Jan 2012 22:21:07 +0100
changeset 1194	699c7eac2c6d
parent 1193	c8fa41fcc4a7
child 1195	8b2b9e61d8ce
permissions	-rw-r--r--