lemon-main: lemon/bits/edge_set_extender.h@2ca0cdb5f366

     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  */

    19 #ifndef LEMON_BITS_EDGE_SET_EXTENDER_H

    20 #define LEMON_BITS_EDGE_SET_EXTENDER_H

    22 #include <lemon/core.h>

    23 #include <lemon/error.h>

    24 #include <lemon/bits/default_map.h>

    25 #include <lemon/bits/map_extender.h>

    27 //\ingroup digraphbits

    28 //\file

    29 //\brief Extenders for the arc set types

    30 namespace lemon {

    32   // \ingroup digraphbits

    33   //

    34   // \brief Extender for the ArcSets

    35   template <typename Base>

    36   class ArcSetExtender : public Base {

    37   public:

    39     typedef Base Parent;

    40     typedef ArcSetExtender Digraph;

    42     // Base extensions

    44     typedef typename Parent::Node Node;

    45     typedef typename Parent::Arc Arc;

    47     int maxId(Node) const {

    48       return Parent::maxNodeId();

    49     }

    51     int maxId(Arc) const {

    52       return Parent::maxArcId();

    53     }

    55     Node fromId(int id, Node) const {

    56       return Parent::nodeFromId(id);

    57     }

    59     Arc fromId(int id, Arc) const {

    60       return Parent::arcFromId(id);

    61     }

    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     }

    73     // Alteration notifier extensions

    75     // The arc observer registry.

    76     typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;

    78   protected:

    80     mutable ArcNotifier arc_notifier;

    82   public:

    84     using Parent::notifier;

    86     // Gives back the arc alteration notifier.

    87     ArcNotifier& notifier(Arc) const {

    88       return arc_notifier;

    89     }

    91     // Iterable extensions

    93     class NodeIt : public Node {

    94       const Digraph* digraph;

    95     public:

    97       NodeIt() {}

    99       NodeIt(Invalid i) : Node(i) { }

   101       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {

   102 	_graph.first(static_cast<Node&>(*this));

   103       }

   105       NodeIt(const Digraph& _graph, const Node& node)

   106 	: Node(node), digraph(&_graph) {}

   108       NodeIt& operator++() {

   109 	digraph->next(*this);

   110 	return *this;

   111       }

   113     };

   116     class ArcIt : public Arc {

   117       const Digraph* digraph;

   118     public:

   120       ArcIt() { }

   122       ArcIt(Invalid i) : Arc(i) { }

   124       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {

   125 	_graph.first(static_cast<Arc&>(*this));

   126       }

   128       ArcIt(const Digraph& _graph, const Arc& e) :

   129 	Arc(e), digraph(&_graph) { }

   131       ArcIt& operator++() {

   132 	digraph->next(*this);

   133 	return *this;

   134       }

   136     };

   139     class OutArcIt : public Arc {

   140       const Digraph* digraph;

   141     public:

   143       OutArcIt() { }

   145       OutArcIt(Invalid i) : Arc(i) { }

   147       OutArcIt(const Digraph& _graph, const Node& node)

   148 	: digraph(&_graph) {

   149 	_graph.firstOut(*this, node);

   150       }

   152       OutArcIt(const Digraph& _graph, const Arc& arc)

   153 	: Arc(arc), digraph(&_graph) {}

   155       OutArcIt& operator++() {

   156 	digraph->nextOut(*this);

   157 	return *this;

   158       }

   160     };

   163     class InArcIt : public Arc {

   164       const Digraph* digraph;

   165     public:

   167       InArcIt() { }

   169       InArcIt(Invalid i) : Arc(i) { }

   171       InArcIt(const Digraph& _graph, const Node& node)

   172 	: digraph(&_graph) {

   173 	_graph.firstIn(*this, node);

   174       }

   176       InArcIt(const Digraph& _graph, const Arc& arc) :

   177 	Arc(arc), digraph(&_graph) {}

   179       InArcIt& operator++() {

   180 	digraph->nextIn(*this);

   181 	return *this;

   182       }

   184     };

   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     }

   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     }

   214     using Parent::first;

   216     // Mappable extension

   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;

   225       explicit ArcMap(const Digraph& _g)

   226 	: Parent(_g) {}

   227       ArcMap(const Digraph& _g, const _Value& _v)

   228 	: Parent(_g, _v) {}

   230       ArcMap& operator=(const ArcMap& cmap) {

   231 	return operator=<ArcMap>(cmap);

   232       }

   234       template <typename CMap>

   235       ArcMap& operator=(const CMap& cmap) {

   236         Parent::operator=(cmap);

   237 	return *this;

   238       }

   240     };

   243     // Alteration extension

   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     }

   251     void clear() {

   252       notifier(Arc()).clear();

   253       Parent::clear();

   254     }

   256     void erase(const Arc& arc) {

   257       notifier(Arc()).erase(arc);

   258       Parent::erase(arc);

   259     }

   261     ArcSetExtender() {

   262       arc_notifier.setContainer(*this);

   263     }

   265     ~ArcSetExtender() {

   266       arc_notifier.clear();

   267     }

   269   };

   272   // \ingroup digraphbits

   273   //

   274   // \brief Extender for the EdgeSets

   275   template <typename Base>

   276   class EdgeSetExtender : public Base {

   278   public:

   280     typedef Base Parent;

   281     typedef EdgeSetExtender Digraph;

   283     typedef typename Parent::Node Node;

   284     typedef typename Parent::Arc Arc;

   285     typedef typename Parent::Edge Edge;

   288     int maxId(Node) const {

   289       return Parent::maxNodeId();

   290     }

   292     int maxId(Arc) const {

   293       return Parent::maxArcId();

   294     }

   296     int maxId(Edge) const {

   297       return Parent::maxEdgeId();

   298     }

   300     Node fromId(int id, Node) const {

   301       return Parent::nodeFromId(id);

   302     }

   304     Arc fromId(int id, Arc) const {

   305       return Parent::arcFromId(id);

   306     }

   308     Edge fromId(int id, Edge) const {

   309       return Parent::edgeFromId(id);

   310     }

   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     }

   321     Arc oppositeArc(const Arc &e) const {

   322       return Parent::direct(e, !Parent::direction(e));

   323     }

   325     using Parent::direct;

   326     Arc direct(const Edge &e, const Node &s) const {

   327       return Parent::direct(e, Parent::u(e) == s);

   328     }

   330     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;

   331     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;

   334   protected:

   336     mutable ArcNotifier arc_notifier;

   337     mutable EdgeNotifier edge_notifier;

   339   public:

   341     using Parent::notifier;

   343     ArcNotifier& notifier(Arc) const {

   344       return arc_notifier;

   345     }

   347     EdgeNotifier& notifier(Edge) const {

   348       return edge_notifier;

   349     }

   352     class NodeIt : public Node {

   353       const Digraph* digraph;

   354     public:

   356       NodeIt() {}

   358       NodeIt(Invalid i) : Node(i) { }

   360       explicit NodeIt(const Digraph& _graph) : digraph(&_graph) {

   361 	_graph.first(static_cast<Node&>(*this));

   362       }

   364       NodeIt(const Digraph& _graph, const Node& node)

   365 	: Node(node), digraph(&_graph) {}

   367       NodeIt& operator++() {

   368 	digraph->next(*this);

   369 	return *this;

   370       }

   372     };

   375     class ArcIt : public Arc {

   376       const Digraph* digraph;

   377     public:

   379       ArcIt() { }

   381       ArcIt(Invalid i) : Arc(i) { }

   383       explicit ArcIt(const Digraph& _graph) : digraph(&_graph) {

   384 	_graph.first(static_cast<Arc&>(*this));

   385       }

   387       ArcIt(const Digraph& _graph, const Arc& e) :

   388 	Arc(e), digraph(&_graph) { }

   390       ArcIt& operator++() {

   391 	digraph->next(*this);

   392 	return *this;

   393       }

   395     };

   398     class OutArcIt : public Arc {

   399       const Digraph* digraph;

   400     public:

   402       OutArcIt() { }

   404       OutArcIt(Invalid i) : Arc(i) { }

   406       OutArcIt(const Digraph& _graph, const Node& node)

   407 	: digraph(&_graph) {

   408 	_graph.firstOut(*this, node);

   409       }

   411       OutArcIt(const Digraph& _graph, const Arc& arc)

   412 	: Arc(arc), digraph(&_graph) {}

   414       OutArcIt& operator++() {

   415 	digraph->nextOut(*this);

   416 	return *this;

   417       }

   419     };

   422     class InArcIt : public Arc {

   423       const Digraph* digraph;

   424     public:

   426       InArcIt() { }

   428       InArcIt(Invalid i) : Arc(i) { }

   430       InArcIt(const Digraph& _graph, const Node& node)

   431 	: digraph(&_graph) {

   432 	_graph.firstIn(*this, node);

   433       }

   435       InArcIt(const Digraph& _graph, const Arc& arc) :

   436 	Arc(arc), digraph(&_graph) {}

   438       InArcIt& operator++() {

   439 	digraph->nextIn(*this);

   440 	return *this;

   441       }

   443     };

   446     class EdgeIt : public Parent::Edge {

   447       const Digraph* digraph;

   448     public:

   450       EdgeIt() { }

   452       EdgeIt(Invalid i) : Edge(i) { }

   454       explicit EdgeIt(const Digraph& _graph) : digraph(&_graph) {

   455 	_graph.first(static_cast<Edge&>(*this));

   456       }

   458       EdgeIt(const Digraph& _graph, const Edge& e) :

   459 	Edge(e), digraph(&_graph) { }

   461       EdgeIt& operator++() {

   462 	digraph->next(*this);

   463 	return *this;

   464       }

   466     };

   468     class IncEdgeIt : public Parent::Edge {

   469       friend class EdgeSetExtender;

   470       const Digraph* digraph;

   471       bool direction;

   472     public:

   474       IncEdgeIt() { }

   476       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }

   478       IncEdgeIt(const Digraph& _graph, const Node &n) : digraph(&_graph) {

   479 	_graph.firstInc(*this, direction, n);

   480       }

   482       IncEdgeIt(const Digraph& _graph, const Edge &ue, const Node &n)

   483 	: digraph(&_graph), Edge(ue) {

   484 	direction = (_graph.source(ue) == n);

   485       }

   487       IncEdgeIt& operator++() {

   488 	digraph->nextInc(*this, direction);

   489 	return *this;

   490       }

   491     };

   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     }

   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     }

   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     }

   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;

   542       ArcMap(const Digraph& _g)

   543 	: Parent(_g) {}

   544       ArcMap(const Digraph& _g, const _Value& _v)

   545 	: Parent(_g, _v) {}

   547       ArcMap& operator=(const ArcMap& cmap) {

   548 	return operator=<ArcMap>(cmap);

   549       }

   551       template <typename CMap>

   552       ArcMap& operator=(const CMap& cmap) {

   553         Parent::operator=(cmap);

   554 	return *this;

   555       }

   557     };

   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;

   567       EdgeMap(const Digraph& _g)

   568 	: Parent(_g) {}

   570       EdgeMap(const Digraph& _g, const _Value& _v)

   571 	: Parent(_g, _v) {}

   573       EdgeMap& operator=(const EdgeMap& cmap) {

   574 	return operator=<EdgeMap>(cmap);

   575       }

   577       template <typename CMap>

   578       EdgeMap& operator=(const CMap& cmap) {

   579         Parent::operator=(cmap);

   580 	return *this;

   581       }

   583     };

   586     // Alteration extension

   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     }

   598     void clear() {

   599       notifier(Arc()).clear();

   600       notifier(Edge()).clear();

   601       Parent::clear();

   602     }

   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     }

   614     EdgeSetExtender() {

   615       arc_notifier.setContainer(*this);

   616       edge_notifier.setContainer(*this);

   617     }

   619     ~EdgeSetExtender() {

   620       edge_notifier.clear();

   621       arc_notifier.clear();

   622     }

   624   };

   626 }

   628 #endif

author	Balazs Dezso <deba@inf.elte.hu>
	Sat, 18 Apr 2009 21:01:12 +0200
changeset 597	2ca0cdb5f366
parent 519	c786cd201266
child 617	4137ef9aacc6
permissions	-rw-r--r--