lemon/bits/edge_set_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 27 Mar 2009 18:49:25 +0100
changeset 558 f53d641aa967
parent 468 68fe66e2b34a
child 559 c5fd2d996909
permissions -rw-r--r--
Improve timer and counter tests (#253)

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