lemon/bits/edge_set_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 26 Apr 2009 16:44:53 +0200
changeset 625 029a48052c67
parent 559 c5fd2d996909
child 685 a27356ceb5bd
child 882 ece1f8a3052d
permissions -rw-r--r--
Modify the interface of MinCostArborescence + improvements (#267)

- Rename arborescenceValue() to arborescenceCost().
- Rename DefXyz template named paramaters to SetXyz.
- Rearrange public functions (for better doc).
- Doc improvements.
- Extend the test file with interface checking.
     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     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 typename Parent::Node Node;
   284     typedef typename Parent::Arc Arc;
   285     typedef typename Parent::Edge Edge;
   286 
   287     int maxId(Node) const {
   288       return Parent::maxNodeId();
   289     }
   290 
   291     int maxId(Arc) const {
   292       return Parent::maxArcId();
   293     }
   294 
   295     int maxId(Edge) const {
   296       return Parent::maxEdgeId();
   297     }
   298 
   299     Node fromId(int id, Node) const {
   300       return Parent::nodeFromId(id);
   301     }
   302 
   303     Arc fromId(int id, Arc) const {
   304       return Parent::arcFromId(id);
   305     }
   306 
   307     Edge fromId(int id, Edge) const {
   308       return Parent::edgeFromId(id);
   309     }
   310 
   311     Node oppositeNode(const Node &n, const Edge &e) const {
   312       if( n == Parent::u(e))
   313 	return Parent::v(e);
   314       else if( n == Parent::v(e))
   315 	return Parent::u(e);
   316       else
   317 	return INVALID;
   318     }
   319 
   320     Arc oppositeArc(const Arc &e) const {
   321       return Parent::direct(e, !Parent::direction(e));
   322     }
   323 
   324     using Parent::direct;
   325     Arc direct(const Edge &e, const Node &s) const {
   326       return Parent::direct(e, Parent::u(e) == s);
   327     }
   328 
   329     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;
   330     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;
   331 
   332 
   333   protected:
   334 
   335     mutable ArcNotifier arc_notifier;
   336     mutable EdgeNotifier edge_notifier;
   337 
   338   public:
   339 
   340     using Parent::notifier;
   341     
   342     ArcNotifier& notifier(Arc) const {
   343       return arc_notifier;
   344     }
   345 
   346     EdgeNotifier& notifier(Edge) const {
   347       return edge_notifier;
   348     }
   349 
   350 
   351     class NodeIt : public Node { 
   352       const Graph* graph;
   353     public:
   354 
   355       NodeIt() {}
   356 
   357       NodeIt(Invalid i) : Node(i) { }
   358 
   359       explicit NodeIt(const Graph& _graph) : graph(&_graph) {
   360 	_graph.first(static_cast<Node&>(*this));
   361       }
   362 
   363       NodeIt(const Graph& _graph, const Node& node) 
   364 	: Node(node), graph(&_graph) {}
   365 
   366       NodeIt& operator++() { 
   367 	graph->next(*this);
   368 	return *this; 
   369       }
   370 
   371     };
   372 
   373 
   374     class ArcIt : public Arc { 
   375       const Graph* graph;
   376     public:
   377 
   378       ArcIt() { }
   379 
   380       ArcIt(Invalid i) : Arc(i) { }
   381 
   382       explicit ArcIt(const Graph& _graph) : graph(&_graph) {
   383 	_graph.first(static_cast<Arc&>(*this));
   384       }
   385 
   386       ArcIt(const Graph& _graph, const Arc& e) : 
   387 	Arc(e), graph(&_graph) { }
   388 
   389       ArcIt& operator++() { 
   390 	graph->next(*this);
   391 	return *this; 
   392       }
   393 
   394     };
   395 
   396 
   397     class OutArcIt : public Arc { 
   398       const Graph* graph;
   399     public:
   400 
   401       OutArcIt() { }
   402 
   403       OutArcIt(Invalid i) : Arc(i) { }
   404 
   405       OutArcIt(const Graph& _graph, const Node& node) 
   406 	: graph(&_graph) {
   407 	_graph.firstOut(*this, node);
   408       }
   409 
   410       OutArcIt(const Graph& _graph, const Arc& arc) 
   411 	: Arc(arc), graph(&_graph) {}
   412 
   413       OutArcIt& operator++() { 
   414 	graph->nextOut(*this);
   415 	return *this; 
   416       }
   417 
   418     };
   419 
   420 
   421     class InArcIt : public Arc { 
   422       const Graph* graph;
   423     public:
   424 
   425       InArcIt() { }
   426 
   427       InArcIt(Invalid i) : Arc(i) { }
   428 
   429       InArcIt(const Graph& _graph, const Node& node) 
   430 	: graph(&_graph) {
   431 	_graph.firstIn(*this, node);
   432       }
   433 
   434       InArcIt(const Graph& _graph, const Arc& arc) : 
   435 	Arc(arc), graph(&_graph) {}
   436 
   437       InArcIt& operator++() { 
   438 	graph->nextIn(*this);
   439 	return *this; 
   440       }
   441 
   442     };
   443 
   444 
   445     class EdgeIt : public Parent::Edge { 
   446       const Graph* graph;
   447     public:
   448 
   449       EdgeIt() { }
   450 
   451       EdgeIt(Invalid i) : Edge(i) { }
   452 
   453       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
   454 	_graph.first(static_cast<Edge&>(*this));
   455       }
   456 
   457       EdgeIt(const Graph& _graph, const Edge& e) : 
   458 	Edge(e), graph(&_graph) { }
   459 
   460       EdgeIt& operator++() { 
   461 	graph->next(*this);
   462 	return *this; 
   463       }
   464 
   465     };
   466 
   467     class IncEdgeIt : public Parent::Edge {
   468       friend class EdgeSetExtender;
   469       const Graph* graph;
   470       bool direction;
   471     public:
   472 
   473       IncEdgeIt() { }
   474 
   475       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   476 
   477       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
   478 	_graph.firstInc(*this, direction, n);
   479       }
   480 
   481       IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)
   482 	: graph(&_graph), Edge(ue) {
   483 	direction = (_graph.source(ue) == n);
   484       }
   485 
   486       IncEdgeIt& operator++() {
   487 	graph->nextInc(*this, direction);
   488 	return *this; 
   489       }
   490     };
   491 
   492     // \brief Base node of the iterator
   493     //
   494     // Returns the base node (ie. the source in this case) of the iterator
   495     Node baseNode(const OutArcIt &e) const {
   496       return Parent::source(static_cast<const Arc&>(e));
   497     }
   498     // \brief Running node of the iterator
   499     //
   500     // Returns the running node (ie. the target in this case) of the
   501     // iterator
   502     Node runningNode(const OutArcIt &e) const {
   503       return Parent::target(static_cast<const Arc&>(e));
   504     }
   505 
   506     // \brief Base node of the iterator
   507     //
   508     // Returns the base node (ie. the target in this case) of the iterator
   509     Node baseNode(const InArcIt &e) const {
   510       return Parent::target(static_cast<const Arc&>(e));
   511     }
   512     // \brief Running node of the iterator
   513     //
   514     // Returns the running node (ie. the source in this case) of the
   515     // iterator
   516     Node runningNode(const InArcIt &e) const {
   517       return Parent::source(static_cast<const Arc&>(e));
   518     }
   519 
   520     // Base node of the iterator
   521     //
   522     // Returns the base node of the iterator
   523     Node baseNode(const IncEdgeIt &e) const {
   524       return e.direction ? u(e) : v(e);
   525     }
   526     // Running node of the iterator
   527     //
   528     // Returns the running node of the iterator
   529     Node runningNode(const IncEdgeIt &e) const {
   530       return e.direction ? v(e) : u(e);
   531     }
   532 
   533 
   534     template <typename _Value>
   535     class ArcMap 
   536       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   537       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   538 
   539     public:
   540       ArcMap(const Graph& _g) 
   541 	: Parent(_g) {}
   542       ArcMap(const Graph& _g, const _Value& _v) 
   543 	: Parent(_g, _v) {}
   544 
   545       ArcMap& operator=(const ArcMap& cmap) {
   546 	return operator=<ArcMap>(cmap);
   547       }
   548 
   549       template <typename CMap>
   550       ArcMap& operator=(const CMap& cmap) {
   551         Parent::operator=(cmap);
   552 	return *this;
   553       }
   554 
   555     };
   556 
   557 
   558     template <typename _Value>
   559     class EdgeMap 
   560       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   561       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   562 
   563     public:
   564       EdgeMap(const Graph& _g) 
   565 	: Parent(_g) {}
   566 
   567       EdgeMap(const Graph& _g, const _Value& _v) 
   568 	: Parent(_g, _v) {}
   569 
   570       EdgeMap& operator=(const EdgeMap& cmap) {
   571 	return operator=<EdgeMap>(cmap);
   572       }
   573 
   574       template <typename CMap>
   575       EdgeMap& operator=(const CMap& cmap) {
   576         Parent::operator=(cmap);
   577 	return *this;
   578       }
   579 
   580     };
   581 
   582 
   583     // Alteration extension
   584 
   585     Edge addEdge(const Node& from, const Node& to) {
   586       Edge edge = Parent::addEdge(from, to);
   587       notifier(Edge()).add(edge);
   588       std::vector<Arc> arcs;
   589       arcs.push_back(Parent::direct(edge, true));
   590       arcs.push_back(Parent::direct(edge, false));
   591       notifier(Arc()).add(arcs);
   592       return edge;
   593     }
   594     
   595     void clear() {
   596       notifier(Arc()).clear();
   597       notifier(Edge()).clear();
   598       Parent::clear();
   599     }
   600 
   601     void erase(const Edge& edge) {
   602       std::vector<Arc> arcs;
   603       arcs.push_back(Parent::direct(edge, true));
   604       arcs.push_back(Parent::direct(edge, false));
   605       notifier(Arc()).erase(arcs);
   606       notifier(Edge()).erase(edge);
   607       Parent::erase(edge);
   608     }
   609 
   610 
   611     EdgeSetExtender() {
   612       arc_notifier.setContainer(*this);
   613       edge_notifier.setContainer(*this);
   614     }
   615 
   616     ~EdgeSetExtender() {
   617       edge_notifier.clear();
   618       arc_notifier.clear();
   619     }
   620     
   621   };
   622 
   623 }
   624 
   625 #endif