lemon-main: lemon/bits/graph_extender.h@93d455c647be

     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 #include <lemon/bits/stl_iterators.h>

    32 //\ingroup graphbits

    33 //\file

    34 //\brief Extenders for the graph types

    35 namespace lemon {

    37   // \ingroup graphbits

    38   //

    39   // \brief Extender for the digraph implementations

    40   template <typename Base>

    41   class DigraphExtender : public Base {

    42     typedef Base Parent;

    44   public:

    46     typedef DigraphExtender Digraph;

    48     // Base extensions

    50     typedef typename Parent::Node Node;

    51     typedef typename Parent::Arc Arc;

    53     int maxId(Node) const {

    54       return Parent::maxNodeId();

    55     }

    57     int maxId(Arc) const {

    58       return Parent::maxArcId();

    59     }

    61     static Node fromId(int id, Node) {

    62       return Parent::nodeFromId(id);

    63     }

    65     static Arc fromId(int id, Arc) {

    66       return Parent::arcFromId(id);

    67     }

    69     Node oppositeNode(const Node &node, const Arc &arc) const {

    70       if (node == Parent::source(arc))

    71         return Parent::target(arc);

    72       else if(node == Parent::target(arc))

    73         return Parent::source(arc);

    74       else

    75         return INVALID;

    76     }

    78     // Alterable extension

    80     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    81     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

    84   protected:

    86     mutable NodeNotifier node_notifier;

    87     mutable ArcNotifier arc_notifier;

    89   public:

    91     NodeNotifier& notifier(Node) const {

    92       return node_notifier;

    93     }

    95     ArcNotifier& notifier(Arc) const {

    96       return arc_notifier;

    97     }

    99     class NodeIt : public Node {

   100       const Digraph* _digraph;

   101     public:

   103       NodeIt() {}

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

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

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

   109       }

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

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

   114       NodeIt& operator++() {

   115         _digraph->next(*this);

   116         return *this;

   117       }

   119     };

   121     LemonRangeWrapper1<NodeIt, Digraph> nodes() const {

   122       return LemonRangeWrapper1<NodeIt, Digraph>(*this);

   123     }

   126     class ArcIt : public Arc {

   127       const Digraph* _digraph;

   128     public:

   130       ArcIt() { }

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

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

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

   136       }

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

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

   141       ArcIt& operator++() {

   142         _digraph->next(*this);

   143         return *this;

   144       }

   146     };

   148     LemonRangeWrapper1<ArcIt, Digraph> arcs() const {

   149       return LemonRangeWrapper1<ArcIt, Digraph>(*this);

   150     }

   153     class OutArcIt : public Arc {

   154       const Digraph* _digraph;

   155     public:

   157       OutArcIt() { }

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

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

   162         : _digraph(&digraph) {

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

   164       }

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

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

   169       OutArcIt& operator++() {

   170         _digraph->nextOut(*this);

   171         return *this;

   172       }

   174     };

   176     LemonRangeWrapper2<OutArcIt, Digraph, Node> outArcs(const Node& u) const {

   177       return LemonRangeWrapper2<OutArcIt, Digraph, Node>(*this, u);

   178     }

   181     class InArcIt : public Arc {

   182       const Digraph* _digraph;

   183     public:

   185       InArcIt() { }

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

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

   190         : _digraph(&digraph) {

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

   192       }

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

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

   197       InArcIt& operator++() {

   198         _digraph->nextIn(*this);

   199         return *this;

   200       }

   202     };

   204     LemonRangeWrapper2<InArcIt, Digraph, Node> inArcs(const Node& u) const {

   205       return LemonRangeWrapper2<InArcIt, Digraph, Node>(*this, u);

   206     }

   208     // \brief Base node of the iterator

   209     //

   210     // Returns the base node (i.e. the source in this case) of the iterator

   211     Node baseNode(const OutArcIt &arc) const {

   212       return Parent::source(arc);

   213     }

   214     // \brief Running node of the iterator

   215     //

   216     // Returns the running node (i.e. the target in this case) of the

   217     // iterator

   218     Node runningNode(const OutArcIt &arc) const {

   219       return Parent::target(arc);

   220     }

   222     // \brief Base node of the iterator

   223     //

   224     // Returns the base node (i.e. the target in this case) of the iterator

   225     Node baseNode(const InArcIt &arc) const {

   226       return Parent::target(arc);

   227     }

   228     // \brief Running node of the iterator

   229     //

   230     // Returns the running node (i.e. the source in this case) of the

   231     // iterator

   232     Node runningNode(const InArcIt &arc) const {

   233       return Parent::source(arc);

   234     }

   237     template <typename _Value>

   238     class NodeMap

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

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

   242     public:

   243       explicit NodeMap(const Digraph& digraph)

   244         : Parent(digraph) {}

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

   246         : Parent(digraph, value) {}

   248     private:

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

   250         return operator=<NodeMap>(cmap);

   251       }

   253       template <typename CMap>

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

   255         Parent::operator=(cmap);

   256         return *this;

   257       }

   259     };

   261     template <typename _Value>

   262     class ArcMap

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

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

   266     public:

   267       explicit ArcMap(const Digraph& digraph)

   268         : Parent(digraph) {}

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

   270         : Parent(digraph, value) {}

   272     private:

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

   274         return operator=<ArcMap>(cmap);

   275       }

   277       template <typename CMap>

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

   279         Parent::operator=(cmap);

   280         return *this;

   281       }

   282     };

   285     Node addNode() {

   286       Node node = Parent::addNode();

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

   288       return node;

   289     }

   291     Arc addArc(const Node& from, const Node& to) {

   292       Arc arc = Parent::addArc(from, to);

   293       notifier(Arc()).add(arc);

   294       return arc;

   295     }

   297     void clear() {

   298       notifier(Arc()).clear();

   299       notifier(Node()).clear();

   300       Parent::clear();

   301     }

   303     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

   304     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

   305       Parent::build(digraph, nodeRef, arcRef);

   306       notifier(Node()).build();

   307       notifier(Arc()).build();

   308     }

   310     void erase(const Node& node) {

   311       Arc arc;

   312       Parent::firstOut(arc, node);

   313       while (arc != INVALID ) {

   314         erase(arc);

   315         Parent::firstOut(arc, node);

   316       }

   318       Parent::firstIn(arc, node);

   319       while (arc != INVALID ) {

   320         erase(arc);

   321         Parent::firstIn(arc, node);

   322       }

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

   325       Parent::erase(node);

   326     }

   328     void erase(const Arc& arc) {

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

   330       Parent::erase(arc);

   331     }

   333     DigraphExtender() {

   334       node_notifier.setContainer(*this);

   335       arc_notifier.setContainer(*this);

   336     }

   339     ~DigraphExtender() {

   340       arc_notifier.clear();

   341       node_notifier.clear();

   342     }

   343   };

   345   // \ingroup _graphbits

   346   //

   347   // \brief Extender for the Graphs

   348   template <typename Base>

   349   class GraphExtender : public Base {

   350     typedef Base Parent;

   352   public:

   354     typedef GraphExtender Graph;

   356     typedef True UndirectedTag;

   358     typedef typename Parent::Node Node;

   359     typedef typename Parent::Arc Arc;

   360     typedef typename Parent::Edge Edge;

   362     // Graph extension

   364     int maxId(Node) const {

   365       return Parent::maxNodeId();

   366     }

   368     int maxId(Arc) const {

   369       return Parent::maxArcId();

   370     }

   372     int maxId(Edge) const {

   373       return Parent::maxEdgeId();

   374     }

   376     static Node fromId(int id, Node) {

   377       return Parent::nodeFromId(id);

   378     }

   380     static Arc fromId(int id, Arc) {

   381       return Parent::arcFromId(id);

   382     }

   384     static Edge fromId(int id, Edge) {

   385       return Parent::edgeFromId(id);

   386     }

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

   389       if( n == Parent::u(e))

   390         return Parent::v(e);

   391       else if( n == Parent::v(e))

   392         return Parent::u(e);

   393       else

   394         return INVALID;

   395     }

   397     Arc oppositeArc(const Arc &arc) const {

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

   399     }

   401     using Parent::direct;

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

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

   404     }

   406     // Alterable extension

   408     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;

   409     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;

   410     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;

   413   protected:

   415     mutable NodeNotifier node_notifier;

   416     mutable ArcNotifier arc_notifier;

   417     mutable EdgeNotifier edge_notifier;

   419   public:

   421     NodeNotifier& notifier(Node) const {

   422       return node_notifier;

   423     }

   425     ArcNotifier& notifier(Arc) const {

   426       return arc_notifier;

   427     }

   429     EdgeNotifier& notifier(Edge) const {

   430       return edge_notifier;

   431     }

   435     class NodeIt : public Node {

   436       const Graph* _graph;

   437     public:

   439       NodeIt() {}

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

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

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

   445       }

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

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

   450       NodeIt& operator++() {

   451         _graph->next(*this);

   452         return *this;

   453       }

   455     };

   457     LemonRangeWrapper1<NodeIt, Graph> nodes() const {

   458       return LemonRangeWrapper1<NodeIt, Graph>(*this);

   459     }

   462     class ArcIt : public Arc {

   463       const Graph* _graph;

   464     public:

   466       ArcIt() { }

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

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

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

   472       }

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

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

   477       ArcIt& operator++() {

   478         _graph->next(*this);

   479         return *this;

   480       }

   482     };

   484     LemonRangeWrapper1<ArcIt, Graph> arcs() const {

   485       return LemonRangeWrapper1<ArcIt, Graph>(*this);

   486     }

   489     class OutArcIt : public Arc {

   490       const Graph* _graph;

   491     public:

   493       OutArcIt() { }

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

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

   498         : _graph(&graph) {

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

   500       }

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

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

   505       OutArcIt& operator++() {

   506         _graph->nextOut(*this);

   507         return *this;

   508       }

   510     };

   512     LemonRangeWrapper2<OutArcIt, Graph, Node> outArcs(const Node& u) const {

   513       return LemonRangeWrapper2<OutArcIt, Graph, Node>(*this, u);

   514     }

   517     class InArcIt : public Arc {

   518       const Graph* _graph;

   519     public:

   521       InArcIt() { }

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

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

   526         : _graph(&graph) {

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

   528       }

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

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

   533       InArcIt& operator++() {

   534         _graph->nextIn(*this);

   535         return *this;

   536       }

   538     };

   540     LemonRangeWrapper2<InArcIt, Graph, Node> inArcs(const Node& u) const {

   541       return LemonRangeWrapper2<InArcIt, Graph, Node>(*this, u);

   542     }

   545     class EdgeIt : public Parent::Edge {

   546       const Graph* _graph;

   547     public:

   549       EdgeIt() { }

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

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

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

   555       }

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

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

   560       EdgeIt& operator++() {

   561         _graph->next(*this);

   562         return *this;

   563       }

   565     };

   567     LemonRangeWrapper1<EdgeIt, Graph> edges() const {

   568       return LemonRangeWrapper1<EdgeIt, Graph>(*this);

   569     }

   572     class IncEdgeIt : public Parent::Edge {

   573       friend class GraphExtender;

   574       const Graph* _graph;

   575       bool _direction;

   576     public:

   578       IncEdgeIt() { }

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

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

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

   584       }

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

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

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

   589       }

   591       IncEdgeIt& operator++() {

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

   593         return *this;

   594       }

   595     };

   597     LemonRangeWrapper2<IncEdgeIt, Graph, Node> incEdges(const Node& u) const {

   598       return LemonRangeWrapper2<IncEdgeIt, Graph, Node>(*this, u);

   599     }

   602     // \brief Base node of the iterator

   603     //

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

   605     Node baseNode(const OutArcIt &arc) const {

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

   607     }

   608     // \brief Running node of the iterator

   609     //

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

   611     // iterator

   612     Node runningNode(const OutArcIt &arc) const {

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

   614     }

   616     // \brief Base node of the iterator

   617     //

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

   619     Node baseNode(const InArcIt &arc) const {

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

   621     }

   622     // \brief Running node of the iterator

   623     //

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

   625     // iterator

   626     Node runningNode(const InArcIt &arc) const {

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

   628     }

   630     // Base node of the iterator

   631     //

   632     // Returns the base node of the iterator

   633     Node baseNode(const IncEdgeIt &edge) const {

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

   635     }

   636     // Running node of the iterator

   637     //

   638     // Returns the running node of the iterator

   639     Node runningNode(const IncEdgeIt &edge) const {

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

   641     }

   643     // Mappable extension

   645     template <typename _Value>

   646     class NodeMap

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

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

   650     public:

   651       explicit NodeMap(const Graph& graph)

   652         : Parent(graph) {}

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

   654         : Parent(graph, value) {}

   656     private:

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

   658         return operator=<NodeMap>(cmap);

   659       }

   661       template <typename CMap>

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

   663         Parent::operator=(cmap);

   664         return *this;

   665       }

   667     };

   669     template <typename _Value>

   670     class ArcMap

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

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

   674     public:

   675       explicit ArcMap(const Graph& graph)

   676         : Parent(graph) {}

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

   678         : Parent(graph, value) {}

   680     private:

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

   682         return operator=<ArcMap>(cmap);

   683       }

   685       template <typename CMap>

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

   687         Parent::operator=(cmap);

   688         return *this;

   689       }

   690     };

   693     template <typename _Value>

   694     class EdgeMap

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

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

   698     public:

   699       explicit EdgeMap(const Graph& graph)

   700         : Parent(graph) {}

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

   703         : Parent(graph, value) {}

   705     private:

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

   707         return operator=<EdgeMap>(cmap);

   708       }

   710       template <typename CMap>

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

   712         Parent::operator=(cmap);

   713         return *this;

   714       }

   716     };

   718     // Alteration extension

   720     Node addNode() {

   721       Node node = Parent::addNode();

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

   723       return node;

   724     }

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

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

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

   729       std::vector<Arc> ev;

   730       ev.push_back(Parent::direct(edge, true));

   731       ev.push_back(Parent::direct(edge, false));

   732       notifier(Arc()).add(ev);

   733       return edge;

   734     }

   736     void clear() {

   737       notifier(Arc()).clear();

   738       notifier(Edge()).clear();

   739       notifier(Node()).clear();

   740       Parent::clear();

   741     }

   743     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>

   744     void build(const Graph& graph, NodeRefMap& nodeRef,

   745                EdgeRefMap& edgeRef) {

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

   747       notifier(Node()).build();

   748       notifier(Edge()).build();

   749       notifier(Arc()).build();

   750     }

   752     void erase(const Node& node) {

   753       Arc arc;

   754       Parent::firstOut(arc, node);

   755       while (arc != INVALID ) {

   756         erase(arc);

   757         Parent::firstOut(arc, node);

   758       }

   760       Parent::firstIn(arc, node);

   761       while (arc != INVALID ) {

   762         erase(arc);

   763         Parent::firstIn(arc, node);

   764       }

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

   767       Parent::erase(node);

   768     }

   770     void erase(const Edge& edge) {

   771       std::vector<Arc> av;

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

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

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

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

   776       Parent::erase(edge);

   777     }

   779     GraphExtender() {

   780       node_notifier.setContainer(*this);

   781       arc_notifier.setContainer(*this);

   782       edge_notifier.setContainer(*this);

   783     }

   785     ~GraphExtender() {

   786       edge_notifier.clear();

   787       arc_notifier.clear();

   788       node_notifier.clear();

   789     }

   791   };

   793   // \ingroup _graphbits

   794   //

   795   // \brief Extender for the BpGraphs

   796   template <typename Base>

   797   class BpGraphExtender : public Base {

   798     typedef Base Parent;

   800   public:

   802     typedef BpGraphExtender BpGraph;

   804     typedef True UndirectedTag;

   806     typedef typename Parent::Node Node;

   807     typedef typename Parent::RedNode RedNode;

   808     typedef typename Parent::BlueNode BlueNode;

   809     typedef typename Parent::Arc Arc;

   810     typedef typename Parent::Edge Edge;

   812     // BpGraph extension

   814     using Parent::first;

   815     using Parent::next;

   816     using Parent::id;

   818     int maxId(Node) const {

   819       return Parent::maxNodeId();

   820     }

   822     int maxId(RedNode) const {

   823       return Parent::maxRedId();

   824     }

   826     int maxId(BlueNode) const {

   827       return Parent::maxBlueId();

   828     }

   830     int maxId(Arc) const {

   831       return Parent::maxArcId();

   832     }

   834     int maxId(Edge) const {

   835       return Parent::maxEdgeId();

   836     }

   838     static Node fromId(int id, Node) {

   839       return Parent::nodeFromId(id);

   840     }

   842     static Arc fromId(int id, Arc) {

   843       return Parent::arcFromId(id);

   844     }

   846     static Edge fromId(int id, Edge) {

   847       return Parent::edgeFromId(id);

   848     }

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

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

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

   854       if( n == u(e))

   855         return v(e);

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

   857         return u(e);

   858       else

   859         return INVALID;

   860     }

   862     Arc oppositeArc(const Arc &arc) const {

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

   864     }

   866     using Parent::direct;

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

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

   869     }

   871     RedNode asRedNode(const Node& node) const {

   872       if (node == INVALID || Parent::blue(node)) {

   873         return INVALID;

   874       } else {

   875         return Parent::asRedNodeUnsafe(node);

   876       }

   877     }

   879     BlueNode asBlueNode(const Node& node) const {

   880       if (node == INVALID || Parent::red(node)) {

   881         return INVALID;

   882       } else {

   883         return Parent::asBlueNodeUnsafe(node);

   884       }

   885     }

   887     // Alterable extension

   889     typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;

   890     typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier;

   891     typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;

   892     typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;

   893     typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;

   896   protected:

   898     mutable NodeNotifier node_notifier;

   899     mutable RedNodeNotifier red_node_notifier;

   900     mutable BlueNodeNotifier blue_node_notifier;

   901     mutable ArcNotifier arc_notifier;

   902     mutable EdgeNotifier edge_notifier;

   904   public:

   906     NodeNotifier& notifier(Node) const {

   907       return node_notifier;

   908     }

   910     RedNodeNotifier& notifier(RedNode) const {

   911       return red_node_notifier;

   912     }

   914     BlueNodeNotifier& notifier(BlueNode) const {

   915       return blue_node_notifier;

   916     }

   918     ArcNotifier& notifier(Arc) const {

   919       return arc_notifier;

   920     }

   922     EdgeNotifier& notifier(Edge) const {

   923       return edge_notifier;

   924     }

   928     class NodeIt : public Node {

   929       const BpGraph* _graph;

   930     public:

   932       NodeIt() {}

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

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

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

   938       }

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

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

   943       NodeIt& operator++() {

   944         _graph->next(*this);

   945         return *this;

   946       }

   948     };

   950     LemonRangeWrapper1<NodeIt, BpGraph> nodes() const {

   951       return LemonRangeWrapper1<NodeIt, BpGraph>(*this);

   952     }

   955     class RedNodeIt : public RedNode {

   956       const BpGraph* _graph;

   957     public:

   959       RedNodeIt() {}

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

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

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

   965       }

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

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

   970       RedNodeIt& operator++() {

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

   972         return *this;

   973       }

   975     };

   977     LemonRangeWrapper1<RedNodeIt, BpGraph> redNodes() const {

   978       return LemonRangeWrapper1<RedNodeIt, BpGraph>(*this);

   979     }

   982     class BlueNodeIt : public BlueNode {

   983       const BpGraph* _graph;

   984     public:

   986       BlueNodeIt() {}

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

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

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

   992       }

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

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

   997       BlueNodeIt& operator++() {

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

   999         return *this;

  1000       }

  1002     };

  1004     LemonRangeWrapper1<BlueNodeIt, BpGraph> blueNodes() const {

  1005       return LemonRangeWrapper1<BlueNodeIt, BpGraph>(*this);

  1006     }

  1010     class ArcIt : public Arc {

  1011       const BpGraph* _graph;

  1012     public:

  1014       ArcIt() { }

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

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

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

  1020       }

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

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

  1025       ArcIt& operator++() {

  1026         _graph->next(*this);

  1027         return *this;

  1028       }

  1030     };

  1032     LemonRangeWrapper1<ArcIt, BpGraph> arcs() const {

  1033       return LemonRangeWrapper1<ArcIt, BpGraph>(*this);

  1034     }

  1037     class OutArcIt : public Arc {

  1038       const BpGraph* _graph;

  1039     public:

  1041       OutArcIt() { }

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

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

  1046         : _graph(&graph) {

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

  1048       }

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

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

  1053       OutArcIt& operator++() {

  1054         _graph->nextOut(*this);

  1055         return *this;

  1056       }

  1058     };

  1060     LemonRangeWrapper2<OutArcIt, BpGraph, Node> outArcs(const Node& u) const {

  1061       return LemonRangeWrapper2<OutArcIt, BpGraph, Node>(*this, u);

  1062     }

  1065     class InArcIt : public Arc {

  1066       const BpGraph* _graph;

  1067     public:

  1069       InArcIt() { }

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

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

  1074         : _graph(&graph) {

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

  1076       }

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

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

  1081       InArcIt& operator++() {

  1082         _graph->nextIn(*this);

  1083         return *this;

  1084       }

  1086     };

  1088     LemonRangeWrapper2<InArcIt, BpGraph, Node> inArcs(const Node& u) const {

  1089       return LemonRangeWrapper2<InArcIt, BpGraph, Node>(*this, u);

  1090     }

  1093     class EdgeIt : public Parent::Edge {

  1094       const BpGraph* _graph;

  1095     public:

  1097       EdgeIt() { }

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

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

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

  1103       }

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

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

  1108       EdgeIt& operator++() {

  1109         _graph->next(*this);

  1110         return *this;

  1111       }

  1113     };

  1115     LemonRangeWrapper1<EdgeIt, BpGraph> edges() const {

  1116       return LemonRangeWrapper1<EdgeIt, BpGraph>(*this);

  1117     }

  1120     class IncEdgeIt : public Parent::Edge {

  1121       friend class BpGraphExtender;

  1122       const BpGraph* _graph;

  1123       bool _direction;

  1124     public:

  1126       IncEdgeIt() { }

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

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

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

  1132       }

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

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

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

  1137       }

  1139       IncEdgeIt& operator++() {

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

  1141         return *this;

  1142       }

  1143     };

  1145     LemonRangeWrapper2<IncEdgeIt, BpGraph, Node> incEdges(const Node& u) const {

  1146       return LemonRangeWrapper2<IncEdgeIt, BpGraph, Node>(*this, u);

  1147     }

  1150     // \brief Base node of the iterator

  1151     //

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

  1153     Node baseNode(const OutArcIt &arc) const {

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

  1155     }

  1156     // \brief Running node of the iterator

  1157     //

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

  1159     // iterator

  1160     Node runningNode(const OutArcIt &arc) const {

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

  1162     }

  1164     // \brief Base node of the iterator

  1165     //

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

  1167     Node baseNode(const InArcIt &arc) const {

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

  1169     }

  1170     // \brief Running node of the iterator

  1171     //

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

  1173     // iterator

  1174     Node runningNode(const InArcIt &arc) const {

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

  1176     }

  1178     // Base node of the iterator

  1179     //

  1180     // Returns the base node of the iterator

  1181     Node baseNode(const IncEdgeIt &edge) const {

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

  1183     }

  1184     // Running node of the iterator

  1185     //

  1186     // Returns the running node of the iterator

  1187     Node runningNode(const IncEdgeIt &edge) const {

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

  1189     }

  1191     // Mappable extension

  1193     template <typename _Value>

  1194     class NodeMap

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

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

  1198     public:

  1199       explicit NodeMap(const BpGraph& bpgraph)

  1200         : Parent(bpgraph) {}

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

  1202         : Parent(bpgraph, value) {}

  1204     private:

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

  1206         return operator=<NodeMap>(cmap);

  1207       }

  1209       template <typename CMap>

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

  1211         Parent::operator=(cmap);

  1212         return *this;

  1213       }

  1215     };

  1217     template <typename _Value>

  1218     class RedNodeMap

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

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

  1222     public:

  1223       explicit RedNodeMap(const BpGraph& bpgraph)

  1224         : Parent(bpgraph) {}

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

  1226         : Parent(bpgraph, value) {}

  1228     private:

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

  1230         return operator=<RedNodeMap>(cmap);

  1231       }

  1233       template <typename CMap>

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

  1235         Parent::operator=(cmap);

  1236         return *this;

  1237       }

  1239     };

  1241     template <typename _Value>

  1242     class BlueNodeMap

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

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

  1246     public:

  1247       explicit BlueNodeMap(const BpGraph& bpgraph)

  1248         : Parent(bpgraph) {}

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

  1250         : Parent(bpgraph, value) {}

  1252     private:

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

  1254         return operator=<BlueNodeMap>(cmap);

  1255       }

  1257       template <typename CMap>

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

  1259         Parent::operator=(cmap);

  1260         return *this;

  1261       }

  1263     };

  1265     template <typename _Value>

  1266     class ArcMap

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

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

  1270     public:

  1271       explicit ArcMap(const BpGraph& graph)

  1272         : Parent(graph) {}

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

  1274         : Parent(graph, value) {}

  1276     private:

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

  1278         return operator=<ArcMap>(cmap);

  1279       }

  1281       template <typename CMap>

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

  1283         Parent::operator=(cmap);

  1284         return *this;

  1285       }

  1286     };

  1289     template <typename _Value>

  1290     class EdgeMap

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

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

  1294     public:

  1295       explicit EdgeMap(const BpGraph& graph)

  1296         : Parent(graph) {}

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

  1299         : Parent(graph, value) {}

  1301     private:

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

  1303         return operator=<EdgeMap>(cmap);

  1304       }

  1306       template <typename CMap>

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

  1308         Parent::operator=(cmap);

  1309         return *this;

  1310       }

  1312     };

  1314     // Alteration extension

  1316     RedNode addRedNode() {

  1317       RedNode node = Parent::addRedNode();

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

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

  1320       return node;

  1321     }

  1323     BlueNode addBlueNode() {

  1324       BlueNode node = Parent::addBlueNode();

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

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

  1327       return node;

  1328     }

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

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

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

  1333       std::vector<Arc> av;

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

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

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

  1337       return edge;

  1338     }

  1340     void clear() {

  1341       notifier(Arc()).clear();

  1342       notifier(Edge()).clear();

  1343       notifier(Node()).clear();

  1344       notifier(BlueNode()).clear();

  1345       notifier(RedNode()).clear();

  1346       Parent::clear();

  1347     }

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

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

  1351                EdgeRefMap& edgeRef) {

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

  1353       notifier(RedNode()).build();

  1354       notifier(BlueNode()).build();

  1355       notifier(Node()).build();

  1356       notifier(Edge()).build();

  1357       notifier(Arc()).build();

  1358     }

  1360     void erase(const Node& node) {

  1361       Arc arc;

  1362       Parent::firstOut(arc, node);

  1363       while (arc != INVALID ) {

  1364         erase(arc);

  1365         Parent::firstOut(arc, node);

  1366       }

  1368       Parent::firstIn(arc, node);

  1369       while (arc != INVALID ) {

  1370         erase(arc);

  1371         Parent::firstIn(arc, node);

  1372       }

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

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

  1376       } else {

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

  1378       }

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

  1381       Parent::erase(node);

  1382     }

  1384     void erase(const Edge& edge) {

  1385       std::vector<Arc> av;

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

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

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

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

  1390       Parent::erase(edge);

  1391     }

  1393     BpGraphExtender() {

  1394       red_node_notifier.setContainer(*this);

  1395       blue_node_notifier.setContainer(*this);

  1396       node_notifier.setContainer(*this);

  1397       arc_notifier.setContainer(*this);

  1398       edge_notifier.setContainer(*this);

  1399     }

  1401     ~BpGraphExtender() {

  1402       edge_notifier.clear();

  1403       arc_notifier.clear();

  1404       node_notifier.clear();

  1405       blue_node_notifier.clear();

  1406       red_node_notifier.clear();

  1407     }

  1409   };

  1411 }

  1413 #endif

author	Balazs Dezso <deba@google.com>
	Tue, 14 Apr 2015 16:36:45 +0200
changeset 1133	93d455c647be
parent 1092	dceba191c00d
permissions	-rw-r--r--