lemon-main: lemon/bits/graph_extender.h@2126945deb6a

     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-2013

     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     // Alterable extension

   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;

   852   protected:

   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;

   860   public:

   862     NodeNotifier& notifier(Node) const {

   863       return node_notifier;

   864     }

   866     RedNodeNotifier& notifier(RedNode) const {

   867       return red_node_notifier;

   868     }

   870     BlueNodeNotifier& notifier(BlueNode) const {

   871       return blue_node_notifier;

   872     }

   874     ArcNotifier& notifier(Arc) const {

   875       return arc_notifier;

   876     }

   878     EdgeNotifier& notifier(Edge) const {

   879       return edge_notifier;

   880     }

   884     class NodeIt : public Node {

   885       const BpGraph* _graph;

   886     public:

   888       NodeIt() {}

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

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

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

   894       }

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

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

   899       NodeIt& operator++() {

   900         _graph->next(*this);

   901         return *this;

   902       }

   904     };

   906     class RedNodeIt : public RedNode {

   907       const BpGraph* _graph;

   908     public:

   910       RedNodeIt() {}

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

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

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

   916       }

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

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

   921       RedNodeIt& operator++() {

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

   923         return *this;

   924       }

   926     };

   928     class BlueNodeIt : public BlueNode {

   929       const BpGraph* _graph;

   930     public:

   932       BlueNodeIt() {}

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

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

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

   938       }

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

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

   943       BlueNodeIt& operator++() {

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

   945         return *this;

   946       }

   948     };

   951     class ArcIt : public Arc {

   952       const BpGraph* _graph;

   953     public:

   955       ArcIt() { }

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

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

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

   961       }

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

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

   966       ArcIt& operator++() {

   967         _graph->next(*this);

   968         return *this;

   969       }

   971     };

   974     class OutArcIt : public Arc {

   975       const BpGraph* _graph;

   976     public:

   978       OutArcIt() { }

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

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

   983         : _graph(&graph) {

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

   985       }

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

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

   990       OutArcIt& operator++() {

   991         _graph->nextOut(*this);

   992         return *this;

   993       }

   995     };

   998     class InArcIt : public Arc {

   999       const BpGraph* _graph;

  1000     public:

  1002       InArcIt() { }

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

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

  1007         : _graph(&graph) {

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

  1009       }

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

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

  1014       InArcIt& operator++() {

  1015         _graph->nextIn(*this);

  1016         return *this;

  1017       }

  1019     };

  1022     class EdgeIt : public Parent::Edge {

  1023       const BpGraph* _graph;

  1024     public:

  1026       EdgeIt() { }

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

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

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

  1032       }

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

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

  1037       EdgeIt& operator++() {

  1038         _graph->next(*this);

  1039         return *this;

  1040       }

  1042     };

  1044     class IncEdgeIt : public Parent::Edge {

  1045       friend class BpGraphExtender;

  1046       const BpGraph* _graph;

  1047       bool _direction;

  1048     public:

  1050       IncEdgeIt() { }

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

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

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

  1056       }

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

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

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

  1061       }

  1063       IncEdgeIt& operator++() {

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

  1065         return *this;

  1066       }

  1067     };

  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     }

  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     }

  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     }

  1110     // Mappable extension

  1112     template <typename _Value>

  1113     class NodeMap

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

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

  1117     public:

  1118       explicit NodeMap(const BpGraph& bpgraph)

  1119         : Parent(bpgraph) {}

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

  1121         : Parent(bpgraph, value) {}

  1123     private:

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

  1125         return operator=<NodeMap>(cmap);

  1126       }

  1128       template <typename CMap>

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

  1130         Parent::operator=(cmap);

  1131         return *this;

  1132       }

  1134     };

  1136     template <typename _Value>

  1137     class RedNodeMap

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

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

  1141     public:

  1142       explicit RedNodeMap(const BpGraph& bpgraph)

  1143         : Parent(bpgraph) {}

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

  1145         : Parent(bpgraph, value) {}

  1147     private:

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

  1149         return operator=<RedNodeMap>(cmap);

  1150       }

  1152       template <typename CMap>

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

  1154         Parent::operator=(cmap);

  1155         return *this;

  1156       }

  1158     };

  1160     template <typename _Value>

  1161     class BlueNodeMap

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

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

  1165     public:

  1166       explicit BlueNodeMap(const BpGraph& bpgraph)

  1167         : Parent(bpgraph) {}

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

  1169         : Parent(bpgraph, value) {}

  1171     private:

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

  1173         return operator=<BlueNodeMap>(cmap);

  1174       }

  1176       template <typename CMap>

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

  1178         Parent::operator=(cmap);

  1179         return *this;

  1180       }

  1182     };

  1184     template <typename _Value>

  1185     class ArcMap

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

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

  1189     public:

  1190       explicit ArcMap(const BpGraph& graph)

  1191         : Parent(graph) {}

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

  1193         : Parent(graph, value) {}

  1195     private:

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

  1197         return operator=<ArcMap>(cmap);

  1198       }

  1200       template <typename CMap>

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

  1202         Parent::operator=(cmap);

  1203         return *this;

  1204       }

  1205     };

  1208     template <typename _Value>

  1209     class EdgeMap

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

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

  1213     public:

  1214       explicit EdgeMap(const BpGraph& graph)

  1215         : Parent(graph) {}

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

  1218         : Parent(graph, value) {}

  1220     private:

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

  1222         return operator=<EdgeMap>(cmap);

  1223       }

  1225       template <typename CMap>

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

  1227         Parent::operator=(cmap);

  1228         return *this;

  1229       }

  1231     };

  1233     // Alteration extension

  1235     RedNode addRedNode() {

  1236       RedNode node = Parent::addRedNode();

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

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

  1239       return node;

  1240     }

  1242     BlueNode addBlueNode() {

  1243       BlueNode node = Parent::addBlueNode();

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

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

  1246       return node;

  1247     }

  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     }

  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     }

  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     }

  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       }

  1287       Parent::firstIn(arc, node);

  1288       while (arc != INVALID ) {

  1289         erase(arc);

  1290         Parent::firstIn(arc, node);

  1291       }

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

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

  1295       } else {

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

  1297       }

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

  1300       Parent::erase(node);

  1301     }

  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     }

  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     }

  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     }

  1328   };

  1330 }

  1332 #endif

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 22 May 2015 17:47:18 +0200
changeset 1148	2126945deb6a
parent 1027	8b2b9e61d8ce
child 1130	0759d974de81
permissions	-rw-r--r--