lemon-main: lemon/bits/graph_extender.h@939ee6d1e525

     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::Arc Arc;

   764     typedef typename Parent::Edge Edge;

   766     // BpGraph extension

   768     class RedNode : public Node {

   769     public:

   770       RedNode() {}

   771       RedNode(const RedNode& node) : Node(node) {}

   772       RedNode(Invalid) : Node(INVALID){}

   773       RedNode(const Node& node) : Node(node) {}

   774     };

   775     class BlueNode : public Node {

   776     public:

   777       BlueNode() {}

   778       BlueNode(const BlueNode& node) : Node(node) {}

   779       BlueNode(Invalid) : Node(INVALID){}

   780       BlueNode(const Node& node) : Node(node) {}

   781     };

   783     using Parent::first;

   784     using Parent::next;

   786     void first(RedNode& node) const {

   787       Parent::firstRed(node);

   788     }

   790     void next(RedNode& node) const {

   791       Parent::nextRed(node);

   792     }

   794     void first(BlueNode& node) const {

   795       Parent::firstBlue(node);

   796     }

   798     void next(BlueNode& node) const {

   799       Parent::nextBlue(node);

   800     }

   802     using Parent::id;

   804     int id(const RedNode& node) const {

   805       return Parent::redId(node);

   806     }

   808     int id(const BlueNode& node) const {

   809       return Parent::blueId(node);

   810     }

   812     int maxId(Node) const {

   813       return Parent::maxNodeId();

   814     }

   816     int maxId(RedNode) const {

   817       return Parent::maxRedId();

   818     }

   820     int maxId(BlueNode) const {

   821       return Parent::maxBlueId();

   822     }

   824     int maxId(Arc) const {

   825       return Parent::maxArcId();

   826     }

   828     int maxId(Edge) const {

   829       return Parent::maxEdgeId();

   830     }

   832     static Node fromId(int id, Node) {

   833       return Parent::nodeFromId(id);

   834     }

   836     static Arc fromId(int id, Arc) {

   837       return Parent::arcFromId(id);

   838     }

   840     static Edge fromId(int id, Edge) {

   841       return Parent::edgeFromId(id);

   842     }

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

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

   847     Node oppositeNode(const Node &n, const Edge &e) const {

   848       if( n == u(e))

   849         return v(e);

   850       else if( n == v(e))

   851         return u(e);

   852       else

   853         return INVALID;

   854     }

   856     Arc oppositeArc(const Arc &arc) const {

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

   858     }

   860     using Parent::direct;

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

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

   863     }

   865     // Alterable extension

   867     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;

   868     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;

   869     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;

   870     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;

   871     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;

   874   protected:

   876     mutable NodeNotifier node_notifier;

   877     mutable RedNodeNotifier red_node_notifier;

   878     mutable BlueNodeNotifier blue_node_notifier;

   879     mutable ArcNotifier arc_notifier;

   880     mutable EdgeNotifier edge_notifier;

   882   public:

   884     NodeNotifier& notifier(Node) const {

   885       return node_notifier;

   886     }

   888     RedNodeNotifier& notifier(RedNode) const {

   889       return red_node_notifier;

   890     }

   892     BlueNodeNotifier& notifier(BlueNode) const {

   893       return blue_node_notifier;

   894     }

   896     ArcNotifier& notifier(Arc) const {

   897       return arc_notifier;

   898     }

   900     EdgeNotifier& notifier(Edge) const {

   901       return edge_notifier;

   902     }

   906     class NodeIt : public Node {

   907       const BpGraph* _graph;

   908     public:

   910       NodeIt() {}

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

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

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

   916       }

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

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

   921       NodeIt& operator++() {

   922         _graph->next(*this);

   923         return *this;

   924       }

   926     };

   928     class RedIt : public Node {

   929       const BpGraph* _graph;

   930     public:

   932       RedIt() {}

   934       RedIt(Invalid i) : Node(i) { }

   936       explicit RedIt(const BpGraph& graph) : _graph(&graph) {

   937         _graph->firstRed(static_cast<Node&>(*this));

   938       }

   940       RedIt(const BpGraph& graph, const Node& node)

   941         : Node(node), _graph(&graph) {

   942         LEMON_DEBUG(_graph->red(node), "Node has to be red.");

   943       }

   945       RedIt& operator++() {

   946         _graph->nextRed(*this);

   947         return *this;

   948       }

   950     };

   952     class BlueIt : public Node {

   953       const BpGraph* _graph;

   954     public:

   956       BlueIt() {}

   958       BlueIt(Invalid i) : Node(i) { }

   960       explicit BlueIt(const BpGraph& graph) : _graph(&graph) {

   961         _graph->firstBlue(static_cast<Node&>(*this));

   962       }

   964       BlueIt(const BpGraph& graph, const Node& node)

   965         : Node(node), _graph(&graph) {

   966         LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");

   967       }

   969       BlueIt& operator++() {

   970         _graph->nextBlue(*this);

   971         return *this;

   972       }

   974     };

   977     class ArcIt : public Arc {

   978       const BpGraph* _graph;

   979     public:

   981       ArcIt() { }

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

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

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

   987       }

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

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

   992       ArcIt& operator++() {

   993         _graph->next(*this);

   994         return *this;

   995       }

   997     };

  1000     class OutArcIt : public Arc {

  1001       const BpGraph* _graph;

  1002     public:

  1004       OutArcIt() { }

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

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

  1009         : _graph(&graph) {

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

  1011       }

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

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

  1016       OutArcIt& operator++() {

  1017         _graph->nextOut(*this);

  1018         return *this;

  1019       }

  1021     };

  1024     class InArcIt : public Arc {

  1025       const BpGraph* _graph;

  1026     public:

  1028       InArcIt() { }

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

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

  1033         : _graph(&graph) {

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

  1035       }

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

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

  1040       InArcIt& operator++() {

  1041         _graph->nextIn(*this);

  1042         return *this;

  1043       }

  1045     };

  1048     class EdgeIt : public Parent::Edge {

  1049       const BpGraph* _graph;

  1050     public:

  1052       EdgeIt() { }

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

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

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

  1058       }

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

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

  1063       EdgeIt& operator++() {

  1064         _graph->next(*this);

  1065         return *this;

  1066       }

  1068     };

  1070     class IncEdgeIt : public Parent::Edge {

  1071       friend class BpGraphExtender;

  1072       const BpGraph* _graph;

  1073       bool _direction;

  1074     public:

  1076       IncEdgeIt() { }

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

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

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

  1082       }

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

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

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

  1087       }

  1089       IncEdgeIt& operator++() {

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

  1091         return *this;

  1092       }

  1093     };

  1095     // \brief Base node of the iterator

  1096     //

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

  1098     Node baseNode(const OutArcIt &arc) const {

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

  1100     }

  1101     // \brief Running node of the iterator

  1102     //

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

  1104     // iterator

  1105     Node runningNode(const OutArcIt &arc) const {

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

  1107     }

  1109     // \brief Base node of the iterator

  1110     //

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

  1112     Node baseNode(const InArcIt &arc) const {

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

  1114     }

  1115     // \brief Running node of the iterator

  1116     //

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

  1118     // iterator

  1119     Node runningNode(const InArcIt &arc) const {

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

  1121     }

  1123     // Base node of the iterator

  1124     //

  1125     // Returns the base node of the iterator

  1126     Node baseNode(const IncEdgeIt &edge) const {

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

  1128     }

  1129     // Running node of the iterator

  1130     //

  1131     // Returns the running node of the iterator

  1132     Node runningNode(const IncEdgeIt &edge) const {

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

  1134     }

  1136     // Mappable extension

  1138     template <typename _Value>

  1139     class NodeMap

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

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

  1143     public:

  1144       explicit NodeMap(const BpGraph& bpgraph)

  1145         : Parent(bpgraph) {}

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

  1147         : Parent(bpgraph, value) {}

  1149     private:

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

  1151         return operator=<NodeMap>(cmap);

  1152       }

  1154       template <typename CMap>

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

  1156         Parent::operator=(cmap);

  1157         return *this;

  1158       }

  1160     };

  1162     template <typename _Value>

  1163     class RedMap

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

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

  1167     public:

  1168       explicit RedMap(const BpGraph& bpgraph)

  1169         : Parent(bpgraph) {}

  1170       RedMap(const BpGraph& bpgraph, const _Value& value)

  1171         : Parent(bpgraph, value) {}

  1173     private:

  1174       RedMap& operator=(const RedMap& cmap) {

  1175         return operator=<RedMap>(cmap);

  1176       }

  1178       template <typename CMap>

  1179       RedMap& operator=(const CMap& cmap) {

  1180         Parent::operator=(cmap);

  1181         return *this;

  1182       }

  1184     };

  1186     template <typename _Value>

  1187     class BlueMap

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

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

  1191     public:

  1192       explicit BlueMap(const BpGraph& bpgraph)

  1193         : Parent(bpgraph) {}

  1194       BlueMap(const BpGraph& bpgraph, const _Value& value)

  1195         : Parent(bpgraph, value) {}

  1197     private:

  1198       BlueMap& operator=(const BlueMap& cmap) {

  1199         return operator=<BlueMap>(cmap);

  1200       }

  1202       template <typename CMap>

  1203       BlueMap& operator=(const CMap& cmap) {

  1204         Parent::operator=(cmap);

  1205         return *this;

  1206       }

  1208     };

  1210     template <typename _Value>

  1211     class ArcMap

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

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

  1215     public:

  1216       explicit ArcMap(const BpGraph& graph)

  1217         : Parent(graph) {}

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

  1219         : Parent(graph, value) {}

  1221     private:

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

  1223         return operator=<ArcMap>(cmap);

  1224       }

  1226       template <typename CMap>

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

  1228         Parent::operator=(cmap);

  1229         return *this;

  1230       }

  1231     };

  1234     template <typename _Value>

  1235     class EdgeMap

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

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

  1239     public:

  1240       explicit EdgeMap(const BpGraph& graph)

  1241         : Parent(graph) {}

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

  1244         : Parent(graph, value) {}

  1246     private:

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

  1248         return operator=<EdgeMap>(cmap);

  1249       }

  1251       template <typename CMap>

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

  1253         Parent::operator=(cmap);

  1254         return *this;

  1255       }

  1257     };

  1259     // Alteration extension

  1261     Node addRedNode() {

  1262       Node node = Parent::addRedNode();

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

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

  1265       return node;

  1266     }

  1268     Node addBlueNode() {

  1269       Node node = Parent::addBlueNode();

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

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

  1272       return node;

  1273     }

  1275     Edge addEdge(const Node& from, const Node& to) {

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

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

  1278       std::vector<Arc> av;

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

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

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

  1282       return edge;

  1283     }

  1285     void clear() {

  1286       notifier(Arc()).clear();

  1287       notifier(Edge()).clear();

  1288       notifier(Node()).clear();

  1289       notifier(BlueNode()).clear();

  1290       notifier(RedNode()).clear();

  1291       Parent::clear();

  1292     }

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

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

  1296                EdgeRefMap& edgeRef) {

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

  1298       notifier(RedNode()).build();

  1299       notifier(BlueNode()).build();

  1300       notifier(Node()).build();

  1301       notifier(Edge()).build();

  1302       notifier(Arc()).build();

  1303     }

  1305     void erase(const Node& node) {

  1306       Arc arc;

  1307       Parent::firstOut(arc, node);

  1308       while (arc != INVALID ) {

  1309         erase(arc);

  1310         Parent::firstOut(arc, node);

  1311       }

  1313       Parent::firstIn(arc, node);

  1314       while (arc != INVALID ) {

  1315         erase(arc);

  1316         Parent::firstIn(arc, node);

  1317       }

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

  1320         notifier(RedNode()).erase(node);

  1321       } else {

  1322         notifier(BlueNode()).erase(node);

  1323       }

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

  1326       Parent::erase(node);

  1327     }

  1329     void erase(const Edge& edge) {

  1330       std::vector<Arc> av;

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

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

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

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

  1335       Parent::erase(edge);

  1336     }

  1338     BpGraphExtender() {

  1339       red_node_notifier.setContainer(*this);

  1340       blue_node_notifier.setContainer(*this);

  1341       node_notifier.setContainer(*this);

  1342       arc_notifier.setContainer(*this);

  1343       edge_notifier.setContainer(*this);

  1344     }

  1346     ~BpGraphExtender() {

  1347       edge_notifier.clear();

  1348       arc_notifier.clear();

  1349       node_notifier.clear();

  1350       blue_node_notifier.clear();

  1351       red_node_notifier.clear();

  1352     }

  1354   };

  1356 }

  1358 #endif

author	Balazs Dezso <deba@inf.elte.hu>
	Tue, 16 Nov 2010 08:19:11 +0100
changeset 1023	939ee6d1e525
parent 1019	4c89e925cfe2
child 1025	c8fa41fcc4a7
permissions	-rw-r--r--