lemon/bits/edge_set_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Mar 2013 01:13:54 +0100
changeset 1046 387483bf0a56
parent 966 c8fce9beb46a
parent 998 7fdaa05a69a1
child 1092 dceba191c00d
permissions -rw-r--r--
Adjust image sizes in the documentation (#411)
     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-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_EDGE_SET_EXTENDER_H
    20 #define LEMON_BITS_EDGE_SET_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 #include <lemon/error.h>
    24 #include <lemon/bits/default_map.h>
    25 #include <lemon/bits/map_extender.h>
    26 
    27 //\ingroup digraphbits
    28 //\file
    29 //\brief Extenders for the arc set types
    30 namespace lemon {
    31 
    32   // \ingroup digraphbits
    33   //
    34   // \brief Extender for the ArcSets
    35   template <typename Base>
    36   class ArcSetExtender : public Base {
    37     typedef Base Parent;
    38 
    39   public:
    40 
    41     typedef ArcSetExtender Digraph;
    42 
    43     // Base extensions
    44 
    45     typedef typename Parent::Node Node;
    46     typedef typename Parent::Arc Arc;
    47 
    48     int maxId(Node) const {
    49       return Parent::maxNodeId();
    50     }
    51 
    52     int maxId(Arc) const {
    53       return Parent::maxArcId();
    54     }
    55 
    56     Node fromId(int id, Node) const {
    57       return Parent::nodeFromId(id);
    58     }
    59 
    60     Arc fromId(int id, Arc) const {
    61       return Parent::arcFromId(id);
    62     }
    63 
    64     Node oppositeNode(const Node &n, const Arc &e) const {
    65       if (n == Parent::source(e))
    66         return Parent::target(e);
    67       else if(n==Parent::target(e))
    68         return Parent::source(e);
    69       else
    70         return INVALID;
    71     }
    72 
    73 
    74     // Alteration notifier extensions
    75 
    76     // The arc observer registry.
    77     typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
    78 
    79   protected:
    80 
    81     mutable ArcNotifier arc_notifier;
    82 
    83   public:
    84 
    85     using Parent::notifier;
    86 
    87     // Gives back the arc alteration notifier.
    88     ArcNotifier& notifier(Arc) const {
    89       return arc_notifier;
    90     }
    91 
    92     // Iterable extensions
    93 
    94     class NodeIt : public Node {
    95       const Digraph* digraph;
    96     public:
    97 
    98       NodeIt() {}
    99 
   100       NodeIt(Invalid i) : Node(i) { }
   101 
   102       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
   103         _graph.first(static_cast<Node&>(*this));
   104       }
   105 
   106       NodeIt(const Digraph& _graph, const Node& node)
   107         : Node(node), digraph(&_graph) {}
   108 
   109       NodeIt& operator++() {
   110         digraph->next(*this);
   111         return *this;
   112       }
   113 
   114     };
   115 
   116 
   117     class ArcIt : public Arc {
   118       const Digraph* digraph;
   119     public:
   120 
   121       ArcIt() { }
   122 
   123       ArcIt(Invalid i) : Arc(i) { }
   124 
   125       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
   126         _graph.first(static_cast<Arc&>(*this));
   127       }
   128 
   129       ArcIt(const Digraph& _graph, const Arc& e) :
   130         Arc(e), digraph(&_graph) { }
   131 
   132       ArcIt& operator++() {
   133         digraph->next(*this);
   134         return *this;
   135       }
   136 
   137     };
   138 
   139 
   140     class OutArcIt : public Arc {
   141       const Digraph* digraph;
   142     public:
   143 
   144       OutArcIt() { }
   145 
   146       OutArcIt(Invalid i) : Arc(i) { }
   147 
   148       OutArcIt(const Digraph& _graph, const Node& node)
   149         : digraph(&_graph) {
   150         _graph.firstOut(*this, node);
   151       }
   152 
   153       OutArcIt(const Digraph& _graph, const Arc& arc)
   154         : Arc(arc), digraph(&_graph) {}
   155 
   156       OutArcIt& operator++() {
   157         digraph->nextOut(*this);
   158         return *this;
   159       }
   160 
   161     };
   162 
   163 
   164     class InArcIt : public Arc {
   165       const Digraph* digraph;
   166     public:
   167 
   168       InArcIt() { }
   169 
   170       InArcIt(Invalid i) : Arc(i) { }
   171 
   172       InArcIt(const Digraph& _graph, const Node& node)
   173         : digraph(&_graph) {
   174         _graph.firstIn(*this, node);
   175       }
   176 
   177       InArcIt(const Digraph& _graph, const Arc& arc) :
   178         Arc(arc), digraph(&_graph) {}
   179 
   180       InArcIt& operator++() {
   181         digraph->nextIn(*this);
   182         return *this;
   183       }
   184 
   185     };
   186 
   187     // \brief Base node of the iterator
   188     //
   189     // Returns the base node (ie. the source in this case) of the iterator
   190     Node baseNode(const OutArcIt &e) const {
   191       return Parent::source(static_cast<const Arc&>(e));
   192     }
   193     // \brief Running node of the iterator
   194     //
   195     // Returns the running node (ie. the target in this case) of the
   196     // iterator
   197     Node runningNode(const OutArcIt &e) const {
   198       return Parent::target(static_cast<const Arc&>(e));
   199     }
   200 
   201     // \brief Base node of the iterator
   202     //
   203     // Returns the base node (ie. the target in this case) of the iterator
   204     Node baseNode(const InArcIt &e) const {
   205       return Parent::target(static_cast<const Arc&>(e));
   206     }
   207     // \brief Running node of the iterator
   208     //
   209     // Returns the running node (ie. the source in this case) of the
   210     // iterator
   211     Node runningNode(const InArcIt &e) const {
   212       return Parent::source(static_cast<const Arc&>(e));
   213     }
   214 
   215     using Parent::first;
   216 
   217     // Mappable extension
   218 
   219     template <typename _Value>
   220     class ArcMap
   221       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   222       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   223 
   224     public:
   225       explicit ArcMap(const Digraph& _g)
   226         : Parent(_g) {}
   227       ArcMap(const Digraph& _g, const _Value& _v)
   228         : Parent(_g, _v) {}
   229 
   230       ArcMap& operator=(const ArcMap& cmap) {
   231         return operator=<ArcMap>(cmap);
   232       }
   233 
   234       template <typename CMap>
   235       ArcMap& operator=(const CMap& cmap) {
   236         Parent::operator=(cmap);
   237         return *this;
   238       }
   239 
   240     };
   241 
   242 
   243     // Alteration extension
   244 
   245     Arc addArc(const Node& from, const Node& to) {
   246       Arc arc = Parent::addArc(from, to);
   247       notifier(Arc()).add(arc);
   248       return arc;
   249     }
   250 
   251     void clear() {
   252       notifier(Arc()).clear();
   253       Parent::clear();
   254     }
   255 
   256     void erase(const Arc& arc) {
   257       notifier(Arc()).erase(arc);
   258       Parent::erase(arc);
   259     }
   260 
   261     ArcSetExtender() {
   262       arc_notifier.setContainer(*this);
   263     }
   264 
   265     ~ArcSetExtender() {
   266       arc_notifier.clear();
   267     }
   268 
   269   };
   270 
   271 
   272   // \ingroup digraphbits
   273   //
   274   // \brief Extender for the EdgeSets
   275   template <typename Base>
   276   class EdgeSetExtender : public Base {
   277     typedef Base Parent;
   278 
   279   public:
   280 
   281     typedef EdgeSetExtender Graph;
   282 
   283     typedef True UndirectedTag;
   284 
   285     typedef typename Parent::Node Node;
   286     typedef typename Parent::Arc Arc;
   287     typedef typename Parent::Edge Edge;
   288 
   289     int maxId(Node) const {
   290       return Parent::maxNodeId();
   291     }
   292 
   293     int maxId(Arc) const {
   294       return Parent::maxArcId();
   295     }
   296 
   297     int maxId(Edge) const {
   298       return Parent::maxEdgeId();
   299     }
   300 
   301     Node fromId(int id, Node) const {
   302       return Parent::nodeFromId(id);
   303     }
   304 
   305     Arc fromId(int id, Arc) const {
   306       return Parent::arcFromId(id);
   307     }
   308 
   309     Edge fromId(int id, Edge) const {
   310       return Parent::edgeFromId(id);
   311     }
   312 
   313     Node oppositeNode(const Node &n, const Edge &e) const {
   314       if( n == Parent::u(e))
   315         return Parent::v(e);
   316       else if( n == Parent::v(e))
   317         return Parent::u(e);
   318       else
   319         return INVALID;
   320     }
   321 
   322     Arc oppositeArc(const Arc &e) const {
   323       return Parent::direct(e, !Parent::direction(e));
   324     }
   325 
   326     using Parent::direct;
   327     Arc direct(const Edge &e, const Node &s) const {
   328       return Parent::direct(e, Parent::u(e) == s);
   329     }
   330 
   331     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
   332     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
   333 
   334 
   335   protected:
   336 
   337     mutable ArcNotifier arc_notifier;
   338     mutable EdgeNotifier edge_notifier;
   339 
   340   public:
   341 
   342     using Parent::notifier;
   343 
   344     ArcNotifier& notifier(Arc) const {
   345       return arc_notifier;
   346     }
   347 
   348     EdgeNotifier& notifier(Edge) const {
   349       return edge_notifier;
   350     }
   351 
   352 
   353     class NodeIt : public Node {
   354       const Graph* graph;
   355     public:
   356 
   357       NodeIt() {}
   358 
   359       NodeIt(Invalid i) : Node(i) { }
   360 
   361       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
   362         _graph.first(static_cast<Node&>(*this));
   363       }
   364 
   365       NodeIt(const Graph& _graph, const Node& node)
   366         : Node(node), graph(&_graph) {}
   367 
   368       NodeIt& operator++() {
   369         graph->next(*this);
   370         return *this;
   371       }
   372 
   373     };
   374 
   375 
   376     class ArcIt : public Arc {
   377       const Graph* graph;
   378     public:
   379 
   380       ArcIt() { }
   381 
   382       ArcIt(Invalid i) : Arc(i) { }
   383 
   384       explicit ArcIt(const Graph& _graph) : graph(&_graph) {
   385         _graph.first(static_cast<Arc&>(*this));
   386       }
   387 
   388       ArcIt(const Graph& _graph, const Arc& e) :
   389         Arc(e), graph(&_graph) { }
   390 
   391       ArcIt& operator++() {
   392         graph->next(*this);
   393         return *this;
   394       }
   395 
   396     };
   397 
   398 
   399     class OutArcIt : public Arc {
   400       const Graph* graph;
   401     public:
   402 
   403       OutArcIt() { }
   404 
   405       OutArcIt(Invalid i) : Arc(i) { }
   406 
   407       OutArcIt(const Graph& _graph, const Node& node)
   408         : graph(&_graph) {
   409         _graph.firstOut(*this, node);
   410       }
   411 
   412       OutArcIt(const Graph& _graph, const Arc& arc)
   413         : Arc(arc), graph(&_graph) {}
   414 
   415       OutArcIt& operator++() {
   416         graph->nextOut(*this);
   417         return *this;
   418       }
   419 
   420     };
   421 
   422 
   423     class InArcIt : public Arc {
   424       const Graph* graph;
   425     public:
   426 
   427       InArcIt() { }
   428 
   429       InArcIt(Invalid i) : Arc(i) { }
   430 
   431       InArcIt(const Graph& _graph, const Node& node)
   432         : graph(&_graph) {
   433         _graph.firstIn(*this, node);
   434       }
   435 
   436       InArcIt(const Graph& _graph, const Arc& arc) :
   437         Arc(arc), graph(&_graph) {}
   438 
   439       InArcIt& operator++() {
   440         graph->nextIn(*this);
   441         return *this;
   442       }
   443 
   444     };
   445 
   446 
   447     class EdgeIt : public Parent::Edge {
   448       const Graph* graph;
   449     public:
   450 
   451       EdgeIt() { }
   452 
   453       EdgeIt(Invalid i) : Edge(i) { }
   454 
   455       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
   456         _graph.first(static_cast<Edge&>(*this));
   457       }
   458 
   459       EdgeIt(const Graph& _graph, const Edge& e) :
   460         Edge(e), graph(&_graph) { }
   461 
   462       EdgeIt& operator++() {
   463         graph->next(*this);
   464         return *this;
   465       }
   466 
   467     };
   468 
   469     class IncEdgeIt : public Parent::Edge {
   470       friend class EdgeSetExtender;
   471       const Graph* graph;
   472       bool direction;
   473     public:
   474 
   475       IncEdgeIt() { }
   476 
   477       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   478 
   479       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
   480         _graph.firstInc(*this, direction, n);
   481       }
   482 
   483       IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
   484         : graph(&_graph), Edge(ue) {
   485         direction = (_graph.source(ue) == n);
   486       }
   487 
   488       IncEdgeIt& operator++() {
   489         graph->nextInc(*this, direction);
   490         return *this;
   491       }
   492     };
   493 
   494     // \brief Base node of the iterator
   495     //
   496     // Returns the base node (ie. the source in this case) of the iterator
   497     Node baseNode(const OutArcIt &e) const {
   498       return Parent::source(static_cast<const Arc&>(e));
   499     }
   500     // \brief Running node of the iterator
   501     //
   502     // Returns the running node (ie. the target in this case) of the
   503     // iterator
   504     Node runningNode(const OutArcIt &e) const {
   505       return Parent::target(static_cast<const Arc&>(e));
   506     }
   507 
   508     // \brief Base node of the iterator
   509     //
   510     // Returns the base node (ie. the target in this case) of the iterator
   511     Node baseNode(const InArcIt &e) const {
   512       return Parent::target(static_cast<const Arc&>(e));
   513     }
   514     // \brief Running node of the iterator
   515     //
   516     // Returns the running node (ie. the source in this case) of the
   517     // iterator
   518     Node runningNode(const InArcIt &e) const {
   519       return Parent::source(static_cast<const Arc&>(e));
   520     }
   521 
   522     // Base node of the iterator
   523     //
   524     // Returns the base node of the iterator
   525     Node baseNode(const IncEdgeIt &e) const {
   526       return e.direction ? this->u(e) : this->v(e);
   527     }
   528     // Running node of the iterator
   529     //
   530     // Returns the running node of the iterator
   531     Node runningNode(const IncEdgeIt &e) const {
   532       return e.direction ? this->v(e) : this->u(e);
   533     }
   534 
   535 
   536     template <typename _Value>
   537     class ArcMap
   538       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   539       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   540 
   541     public:
   542       explicit ArcMap(const Graph& _g)
   543         : Parent(_g) {}
   544       ArcMap(const Graph& _g, const _Value& _v)
   545         : Parent(_g, _v) {}
   546 
   547       ArcMap& operator=(const ArcMap& cmap) {
   548         return operator=<ArcMap>(cmap);
   549       }
   550 
   551       template <typename CMap>
   552       ArcMap& operator=(const CMap& cmap) {
   553         Parent::operator=(cmap);
   554         return *this;
   555       }
   556 
   557     };
   558 
   559 
   560     template <typename _Value>
   561     class EdgeMap
   562       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   563       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   564 
   565     public:
   566       explicit EdgeMap(const Graph& _g)
   567         : Parent(_g) {}
   568 
   569       EdgeMap(const Graph& _g, const _Value& _v)
   570         : Parent(_g, _v) {}
   571 
   572       EdgeMap& operator=(const EdgeMap& cmap) {
   573         return operator=<EdgeMap>(cmap);
   574       }
   575 
   576       template <typename CMap>
   577       EdgeMap& operator=(const CMap& cmap) {
   578         Parent::operator=(cmap);
   579         return *this;
   580       }
   581 
   582     };
   583 
   584 
   585     // Alteration extension
   586 
   587     Edge addEdge(const Node& from, const Node& to) {
   588       Edge edge = Parent::addEdge(from, to);
   589       notifier(Edge()).add(edge);
   590       std::vector<Arc> arcs;
   591       arcs.push_back(Parent::direct(edge, true));
   592       arcs.push_back(Parent::direct(edge, false));
   593       notifier(Arc()).add(arcs);
   594       return edge;
   595     }
   596 
   597     void clear() {
   598       notifier(Arc()).clear();
   599       notifier(Edge()).clear();
   600       Parent::clear();
   601     }
   602 
   603     void erase(const Edge& edge) {
   604       std::vector<Arc> arcs;
   605       arcs.push_back(Parent::direct(edge, true));
   606       arcs.push_back(Parent::direct(edge, false));
   607       notifier(Arc()).erase(arcs);
   608       notifier(Edge()).erase(edge);
   609       Parent::erase(edge);
   610     }
   611 
   612 
   613     EdgeSetExtender() {
   614       arc_notifier.setContainer(*this);
   615       edge_notifier.setContainer(*this);
   616     }
   617 
   618     ~EdgeSetExtender() {
   619       edge_notifier.clear();
   620       arc_notifier.clear();
   621     }
   622 
   623   };
   624 
   625 }
   626 
   627 #endif