lemon/bits/edge_set_extender.h
changeset 507 e6ae4999cf22
child 519 c786cd201266
equal deleted inserted replaced
-1:000000000000 0:ba38682aa963
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     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/error.h>
       
    23 #include <lemon/bits/default_map.h>
       
    24 
       
    25 ///\ingroup digraphbits
       
    26 ///\file
       
    27 ///\brief Extenders for the arc set types
       
    28 namespace lemon {
       
    29 
       
    30   /// \ingroup digraphbits
       
    31   ///
       
    32   /// \brief Extender for the ArcSets
       
    33   template <typename Base>
       
    34   class ArcSetExtender : public Base {
       
    35   public:
       
    36 
       
    37     typedef Base Parent;
       
    38     typedef ArcSetExtender Digraph;
       
    39 
       
    40     // Base extensions
       
    41 
       
    42     typedef typename Parent::Node Node;
       
    43     typedef typename Parent::Arc Arc;
       
    44 
       
    45     int maxId(Node) const {
       
    46       return Parent::maxNodeId();
       
    47     }
       
    48 
       
    49     int maxId(Arc) const {
       
    50       return Parent::maxArcId();
       
    51     }
       
    52 
       
    53     Node fromId(int id, Node) const {
       
    54       return Parent::nodeFromId(id);
       
    55     }
       
    56 
       
    57     Arc fromId(int id, Arc) const {
       
    58       return Parent::arcFromId(id);
       
    59     }
       
    60 
       
    61     Node oppositeNode(const Node &n, const Arc &e) const {
       
    62       if (n == Parent::source(e))
       
    63 	return Parent::target(e);
       
    64       else if(n==Parent::target(e))
       
    65 	return Parent::source(e);
       
    66       else
       
    67 	return INVALID;
       
    68     }
       
    69 
       
    70 
       
    71     // Alteration notifier extensions
       
    72 
       
    73     /// The arc observer registry.
       
    74     typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;
       
    75 
       
    76   protected:
       
    77 
       
    78     mutable ArcNotifier arc_notifier;
       
    79 
       
    80   public:
       
    81 
       
    82     using Parent::notifier;
       
    83 
       
    84     /// \brief Gives back the arc alteration notifier.
       
    85     ///
       
    86     /// Gives back the arc alteration notifier.
       
    87     ArcNotifier& notifier(Arc) const {
       
    88       return arc_notifier;
       
    89     }
       
    90 
       
    91     // Iterable extensions
       
    92 
       
    93     class NodeIt : public Node { 
       
    94       const Digraph* digraph;
       
    95     public:
       
    96 
       
    97       NodeIt() {}
       
    98 
       
    99       NodeIt(Invalid i) : Node(i) { }
       
   100 
       
   101       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
       
   102 	_graph.first(static_cast<Node&>(*this));
       
   103       }
       
   104 
       
   105       NodeIt(const Digraph& _graph, const Node& node) 
       
   106 	: Node(node), digraph(&_graph) {}
       
   107 
       
   108       NodeIt& operator++() { 
       
   109 	digraph->next(*this);
       
   110 	return *this; 
       
   111       }
       
   112 
       
   113     };
       
   114 
       
   115 
       
   116     class ArcIt : public Arc { 
       
   117       const Digraph* digraph;
       
   118     public:
       
   119 
       
   120       ArcIt() { }
       
   121 
       
   122       ArcIt(Invalid i) : Arc(i) { }
       
   123 
       
   124       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
       
   125 	_graph.first(static_cast<Arc&>(*this));
       
   126       }
       
   127 
       
   128       ArcIt(const Digraph& _graph, const Arc& e) : 
       
   129 	Arc(e), digraph(&_graph) { }
       
   130 
       
   131       ArcIt& operator++() { 
       
   132 	digraph->next(*this);
       
   133 	return *this; 
       
   134       }
       
   135 
       
   136     };
       
   137 
       
   138 
       
   139     class OutArcIt : public Arc { 
       
   140       const Digraph* digraph;
       
   141     public:
       
   142 
       
   143       OutArcIt() { }
       
   144 
       
   145       OutArcIt(Invalid i) : Arc(i) { }
       
   146 
       
   147       OutArcIt(const Digraph& _graph, const Node& node) 
       
   148 	: digraph(&_graph) {
       
   149 	_graph.firstOut(*this, node);
       
   150       }
       
   151 
       
   152       OutArcIt(const Digraph& _graph, const Arc& arc) 
       
   153 	: Arc(arc), digraph(&_graph) {}
       
   154 
       
   155       OutArcIt& operator++() { 
       
   156 	digraph->nextOut(*this);
       
   157 	return *this; 
       
   158       }
       
   159 
       
   160     };
       
   161 
       
   162 
       
   163     class InArcIt : public Arc { 
       
   164       const Digraph* digraph;
       
   165     public:
       
   166 
       
   167       InArcIt() { }
       
   168 
       
   169       InArcIt(Invalid i) : Arc(i) { }
       
   170 
       
   171       InArcIt(const Digraph& _graph, const Node& node) 
       
   172 	: digraph(&_graph) {
       
   173 	_graph.firstIn(*this, node);
       
   174       }
       
   175 
       
   176       InArcIt(const Digraph& _graph, const Arc& arc) : 
       
   177 	Arc(arc), digraph(&_graph) {}
       
   178 
       
   179       InArcIt& operator++() { 
       
   180 	digraph->nextIn(*this);
       
   181 	return *this; 
       
   182       }
       
   183 
       
   184     };
       
   185 
       
   186     /// \brief Base node of the iterator
       
   187     ///
       
   188     /// Returns the base node (ie. the source in this case) of the iterator
       
   189     Node baseNode(const OutArcIt &e) const {
       
   190       return Parent::source(static_cast<const Arc&>(e));
       
   191     }
       
   192     /// \brief Running node of the iterator
       
   193     ///
       
   194     /// Returns the running node (ie. the target in this case) of the
       
   195     /// iterator
       
   196     Node runningNode(const OutArcIt &e) const {
       
   197       return Parent::target(static_cast<const Arc&>(e));
       
   198     }
       
   199 
       
   200     /// \brief Base node of the iterator
       
   201     ///
       
   202     /// Returns the base node (ie. the target in this case) of the iterator
       
   203     Node baseNode(const InArcIt &e) const {
       
   204       return Parent::target(static_cast<const Arc&>(e));
       
   205     }
       
   206     /// \brief Running node of the iterator
       
   207     ///
       
   208     /// Returns the running node (ie. the source in this case) of the
       
   209     /// iterator
       
   210     Node runningNode(const InArcIt &e) const {
       
   211       return Parent::source(static_cast<const Arc&>(e));
       
   212     }
       
   213 
       
   214     using Parent::first;
       
   215 
       
   216     // Mappable extension
       
   217     
       
   218     template <typename _Value>
       
   219     class ArcMap 
       
   220       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
       
   221     public:
       
   222       typedef ArcSetExtender Digraph;
       
   223       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
       
   224 
       
   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 
       
   278   public:
       
   279 
       
   280     typedef Base Parent;
       
   281     typedef EdgeSetExtender Digraph;
       
   282 
       
   283     typedef typename Parent::Node Node;
       
   284     typedef typename Parent::Arc Arc;
       
   285     typedef typename Parent::Edge Edge;
       
   286 
       
   287 
       
   288     int maxId(Node) const {
       
   289       return Parent::maxNodeId();
       
   290     }
       
   291 
       
   292     int maxId(Arc) const {
       
   293       return Parent::maxArcId();
       
   294     }
       
   295 
       
   296     int maxId(Edge) const {
       
   297       return Parent::maxEdgeId();
       
   298     }
       
   299 
       
   300     Node fromId(int id, Node) const {
       
   301       return Parent::nodeFromId(id);
       
   302     }
       
   303 
       
   304     Arc fromId(int id, Arc) const {
       
   305       return Parent::arcFromId(id);
       
   306     }
       
   307 
       
   308     Edge fromId(int id, Edge) const {
       
   309       return Parent::edgeFromId(id);
       
   310     }
       
   311 
       
   312     Node oppositeNode(const Node &n, const Edge &e) const {
       
   313       if( n == Parent::u(e))
       
   314 	return Parent::v(e);
       
   315       else if( n == Parent::v(e))
       
   316 	return Parent::u(e);
       
   317       else
       
   318 	return INVALID;
       
   319     }
       
   320 
       
   321     Arc oppositeArc(const Arc &e) const {
       
   322       return Parent::direct(e, !Parent::direction(e));
       
   323     }
       
   324 
       
   325     using Parent::direct;
       
   326     Arc direct(const Edge &e, const Node &s) const {
       
   327       return Parent::direct(e, Parent::u(e) == s);
       
   328     }
       
   329 
       
   330     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
       
   331     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
       
   332 
       
   333 
       
   334   protected:
       
   335 
       
   336     mutable ArcNotifier arc_notifier;
       
   337     mutable EdgeNotifier edge_notifier;
       
   338 
       
   339   public:
       
   340 
       
   341     using Parent::notifier;
       
   342     
       
   343     ArcNotifier& notifier(Arc) const {
       
   344       return arc_notifier;
       
   345     }
       
   346 
       
   347     EdgeNotifier& notifier(Edge) const {
       
   348       return edge_notifier;
       
   349     }
       
   350 
       
   351 
       
   352     class NodeIt : public Node { 
       
   353       const Digraph* digraph;
       
   354     public:
       
   355 
       
   356       NodeIt() {}
       
   357 
       
   358       NodeIt(Invalid i) : Node(i) { }
       
   359 
       
   360       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {
       
   361 	_graph.first(static_cast<Node&>(*this));
       
   362       }
       
   363 
       
   364       NodeIt(const Digraph& _graph, const Node& node) 
       
   365 	: Node(node), digraph(&_graph) {}
       
   366 
       
   367       NodeIt& operator++() { 
       
   368 	digraph->next(*this);
       
   369 	return *this; 
       
   370       }
       
   371 
       
   372     };
       
   373 
       
   374 
       
   375     class ArcIt : public Arc { 
       
   376       const Digraph* digraph;
       
   377     public:
       
   378 
       
   379       ArcIt() { }
       
   380 
       
   381       ArcIt(Invalid i) : Arc(i) { }
       
   382 
       
   383       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {
       
   384 	_graph.first(static_cast<Arc&>(*this));
       
   385       }
       
   386 
       
   387       ArcIt(const Digraph& _graph, const Arc& e) : 
       
   388 	Arc(e), digraph(&_graph) { }
       
   389 
       
   390       ArcIt& operator++() { 
       
   391 	digraph->next(*this);
       
   392 	return *this; 
       
   393       }
       
   394 
       
   395     };
       
   396 
       
   397 
       
   398     class OutArcIt : public Arc { 
       
   399       const Digraph* digraph;
       
   400     public:
       
   401 
       
   402       OutArcIt() { }
       
   403 
       
   404       OutArcIt(Invalid i) : Arc(i) { }
       
   405 
       
   406       OutArcIt(const Digraph& _graph, const Node& node) 
       
   407 	: digraph(&_graph) {
       
   408 	_graph.firstOut(*this, node);
       
   409       }
       
   410 
       
   411       OutArcIt(const Digraph& _graph, const Arc& arc) 
       
   412 	: Arc(arc), digraph(&_graph) {}
       
   413 
       
   414       OutArcIt& operator++() { 
       
   415 	digraph->nextOut(*this);
       
   416 	return *this; 
       
   417       }
       
   418 
       
   419     };
       
   420 
       
   421 
       
   422     class InArcIt : public Arc { 
       
   423       const Digraph* digraph;
       
   424     public:
       
   425 
       
   426       InArcIt() { }
       
   427 
       
   428       InArcIt(Invalid i) : Arc(i) { }
       
   429 
       
   430       InArcIt(const Digraph& _graph, const Node& node) 
       
   431 	: digraph(&_graph) {
       
   432 	_graph.firstIn(*this, node);
       
   433       }
       
   434 
       
   435       InArcIt(const Digraph& _graph, const Arc& arc) : 
       
   436 	Arc(arc), digraph(&_graph) {}
       
   437 
       
   438       InArcIt& operator++() { 
       
   439 	digraph->nextIn(*this);
       
   440 	return *this; 
       
   441       }
       
   442 
       
   443     };
       
   444 
       
   445 
       
   446     class EdgeIt : public Parent::Edge { 
       
   447       const Digraph* digraph;
       
   448     public:
       
   449 
       
   450       EdgeIt() { }
       
   451 
       
   452       EdgeIt(Invalid i) : Edge(i) { }
       
   453 
       
   454       explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {
       
   455 	_graph.first(static_cast<Edge&>(*this));
       
   456       }
       
   457 
       
   458       EdgeIt(const Digraph& _graph, const Edge& e) : 
       
   459 	Edge(e), digraph(&_graph) { }
       
   460 
       
   461       EdgeIt& operator++() { 
       
   462 	digraph->next(*this);
       
   463 	return *this; 
       
   464       }
       
   465 
       
   466     };
       
   467 
       
   468     class IncEdgeIt : public Parent::Edge {
       
   469       friend class EdgeSetExtender;
       
   470       const Digraph* digraph;
       
   471       bool direction;
       
   472     public:
       
   473 
       
   474       IncEdgeIt() { }
       
   475 
       
   476       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
       
   477 
       
   478       IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {
       
   479 	_graph.firstInc(*this, direction, n);
       
   480       }
       
   481 
       
   482       IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)
       
   483 	: digraph(&_graph), Edge(ue) {
       
   484 	direction = (_graph.source(ue) == n);
       
   485       }
       
   486 
       
   487       IncEdgeIt& operator++() {
       
   488 	digraph->nextInc(*this, direction);
       
   489 	return *this; 
       
   490       }
       
   491     };
       
   492 
       
   493     /// \brief Base node of the iterator
       
   494     ///
       
   495     /// Returns the base node (ie. the source in this case) of the iterator
       
   496     Node baseNode(const OutArcIt &e) const {
       
   497       return Parent::source(static_cast<const Arc&>(e));
       
   498     }
       
   499     /// \brief Running node of the iterator
       
   500     ///
       
   501     /// Returns the running node (ie. the target in this case) of the
       
   502     /// iterator
       
   503     Node runningNode(const OutArcIt &e) const {
       
   504       return Parent::target(static_cast<const Arc&>(e));
       
   505     }
       
   506 
       
   507     /// \brief Base node of the iterator
       
   508     ///
       
   509     /// Returns the base node (ie. the target in this case) of the iterator
       
   510     Node baseNode(const InArcIt &e) const {
       
   511       return Parent::target(static_cast<const Arc&>(e));
       
   512     }
       
   513     /// \brief Running node of the iterator
       
   514     ///
       
   515     /// Returns the running node (ie. the source in this case) of the
       
   516     /// iterator
       
   517     Node runningNode(const InArcIt &e) const {
       
   518       return Parent::source(static_cast<const Arc&>(e));
       
   519     }
       
   520 
       
   521     /// Base node of the iterator
       
   522     ///
       
   523     /// Returns the base node of the iterator
       
   524     Node baseNode(const IncEdgeIt &e) const {
       
   525       return e.direction ? u(e) : v(e);
       
   526     }
       
   527     /// Running node of the iterator
       
   528     ///
       
   529     /// Returns the running node of the iterator
       
   530     Node runningNode(const IncEdgeIt &e) const {
       
   531       return e.direction ? v(e) : u(e);
       
   532     }
       
   533 
       
   534 
       
   535     template <typename _Value>
       
   536     class ArcMap 
       
   537       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
       
   538     public:
       
   539       typedef EdgeSetExtender Digraph;
       
   540       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
       
   541 
       
   542       ArcMap(const Digraph& _g) 
       
   543 	: Parent(_g) {}
       
   544       ArcMap(const Digraph& _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<Digraph, Edge, _Value> > {
       
   563     public:
       
   564       typedef EdgeSetExtender Digraph;
       
   565       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
       
   566 
       
   567       EdgeMap(const Digraph& _g) 
       
   568 	: Parent(_g) {}
       
   569 
       
   570       EdgeMap(const Digraph& _g, const _Value& _v) 
       
   571 	: Parent(_g, _v) {}
       
   572 
       
   573       EdgeMap& operator=(const EdgeMap& cmap) {
       
   574 	return operator=<EdgeMap>(cmap);
       
   575       }
       
   576 
       
   577       template <typename CMap>
       
   578       EdgeMap& operator=(const CMap& cmap) {
       
   579         Parent::operator=(cmap);
       
   580 	return *this;
       
   581       }
       
   582 
       
   583     };
       
   584 
       
   585 
       
   586     // Alteration extension
       
   587 
       
   588     Edge addEdge(const Node& from, const Node& to) {
       
   589       Edge edge = Parent::addEdge(from, to);
       
   590       notifier(Edge()).add(edge);
       
   591       std::vector<Arc> arcs;
       
   592       arcs.push_back(Parent::direct(edge, true));
       
   593       arcs.push_back(Parent::direct(edge, false));
       
   594       notifier(Arc()).add(arcs);
       
   595       return edge;
       
   596     }
       
   597     
       
   598     void clear() {
       
   599       notifier(Arc()).clear();
       
   600       notifier(Edge()).clear();
       
   601       Parent::clear();
       
   602     }
       
   603 
       
   604     void erase(const Edge& edge) {
       
   605       std::vector<Arc> arcs;
       
   606       arcs.push_back(Parent::direct(edge, true));
       
   607       arcs.push_back(Parent::direct(edge, false));
       
   608       notifier(Arc()).erase(arcs);
       
   609       notifier(Edge()).erase(edge);
       
   610       Parent::erase(edge);
       
   611     }
       
   612 
       
   613 
       
   614     EdgeSetExtender() {
       
   615       arc_notifier.setContainer(*this);
       
   616       edge_notifier.setContainer(*this);
       
   617     }
       
   618 
       
   619     ~EdgeSetExtender() {
       
   620       edge_notifier.clear();
       
   621       arc_notifier.clear();
       
   622     }
       
   623     
       
   624   };
       
   625 
       
   626 }
       
   627 
       
   628 #endif