lemon/bits/edge_set_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 15 Apr 2009 12:01:14 +0200
changeset 590 b61354458b59
parent 519 c786cd201266
child 617 4137ef9aacc6
permissions -rw-r--r--
Imporvements for the matching algorithms (#264)
     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     // 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