lemon-main: lemon/bits/edge_set_extender.h@22bb98ca0101

     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     typedef Base Parent;

    39   public:

    41     typedef ArcSetExtender Digraph;

    43     // Base extensions

    45     typedef typename Parent::Node Node;

    46     typedef typename Parent::Arc Arc;

    48     int maxId(Node) const {

    49       return Parent::maxNodeId();

    50     }

    52     int maxId(Arc) const {

    53       return Parent::maxArcId();

    54     }

    56     Node fromId(int id, Node) const {

    57       return Parent::nodeFromId(id);

    58     }

    60     Arc fromId(int id, Arc) const {

    61       return Parent::arcFromId(id);

    62     }

    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     }

    74     // Alteration notifier extensions

    76     // The arc observer registry.

    77     typedef AlterationNotifier<ArcSetExtender, Arc> ArcNotifier;

    79   protected:

    81     mutable ArcNotifier arc_notifier;

    83   public:

    85     using Parent::notifier;

    87     // Gives back the arc alteration notifier.

    88     ArcNotifier& notifier(Arc) const {

    89       return arc_notifier;

    90     }

    92     // Iterable extensions

    94     class NodeIt : public Node {

    95       const Digraph* digraph;

    96     public:

    98       NodeIt() {}

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

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

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

   104       }

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

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

   109       NodeIt& operator++() {

   110 	digraph->next(*this);

   111 	return *this;

   112       }

   114     };

   117     class ArcIt : public Arc {

   118       const Digraph* digraph;

   119     public:

   121       ArcIt() { }

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

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

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

   127       }

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

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

   132       ArcIt& operator++() {

   133 	digraph->next(*this);

   134 	return *this;

   135       }

   137     };

   140     class OutArcIt : public Arc {

   141       const Digraph* digraph;

   142     public:

   144       OutArcIt() { }

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

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

   149 	: digraph(&_graph) {

   150 	_graph.firstOut(*this, node);

   151       }

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

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

   156       OutArcIt& operator++() {

   157 	digraph->nextOut(*this);

   158 	return *this;

   159       }

   161     };

   164     class InArcIt : public Arc {

   165       const Digraph* digraph;

   166     public:

   168       InArcIt() { }

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

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

   173 	: digraph(&_graph) {

   174 	_graph.firstIn(*this, node);

   175       }

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

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

   180       InArcIt& operator++() {

   181 	digraph->nextIn(*this);

   182 	return *this;

   183       }

   185     };

   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     }

   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     }

   215     using Parent::first;

   217     // Mappable extension

   219     template <typename _Value>

   220     class ArcMap

   221       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {

   222       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;

   224     public:

   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 {

   277     typedef Base Parent;

   279   public:

   281     typedef EdgeSetExtender Graph;

   283     typedef typename Parent::Node Node;

   284     typedef typename Parent::Arc Arc;

   285     typedef typename Parent::Edge Edge;

   287     int maxId(Node) const {

   288       return Parent::maxNodeId();

   289     }

   291     int maxId(Arc) const {

   292       return Parent::maxArcId();

   293     }

   295     int maxId(Edge) const {

   296       return Parent::maxEdgeId();

   297     }

   299     Node fromId(int id, Node) const {

   300       return Parent::nodeFromId(id);

   301     }

   303     Arc fromId(int id, Arc) const {

   304       return Parent::arcFromId(id);

   305     }

   307     Edge fromId(int id, Edge) const {

   308       return Parent::edgeFromId(id);

   309     }

   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     }

   320     Arc oppositeArc(const Arc &e) const {

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

   322     }

   324     using Parent::direct;

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

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

   327     }

   329     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;

   330     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;

   333   protected:

   335     mutable ArcNotifier arc_notifier;

   336     mutable EdgeNotifier edge_notifier;

   338   public:

   340     using Parent::notifier;

   342     ArcNotifier& notifier(Arc) const {

   343       return arc_notifier;

   344     }

   346     EdgeNotifier& notifier(Edge) const {

   347       return edge_notifier;

   348     }

   351     class NodeIt : public Node {

   352       const Graph* graph;

   353     public:

   355       NodeIt() {}

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

   359       explicit NodeIt(const Graph& _graph) : graph(&_graph) {

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

   361       }

   363       NodeIt(const Graph& _graph, const Node& node)

   364 	: Node(node), graph(&_graph) {}

   366       NodeIt& operator++() {

   367 	graph->next(*this);

   368 	return *this;

   369       }

   371     };

   374     class ArcIt : public Arc {

   375       const Graph* graph;

   376     public:

   378       ArcIt() { }

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

   382       explicit ArcIt(const Graph& _graph) : graph(&_graph) {

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

   384       }

   386       ArcIt(const Graph& _graph, const Arc& e) :

   387 	Arc(e), graph(&_graph) { }

   389       ArcIt& operator++() {

   390 	graph->next(*this);

   391 	return *this;

   392       }

   394     };

   397     class OutArcIt : public Arc {

   398       const Graph* graph;

   399     public:

   401       OutArcIt() { }

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

   405       OutArcIt(const Graph& _graph, const Node& node)

   406 	: graph(&_graph) {

   407 	_graph.firstOut(*this, node);

   408       }

   410       OutArcIt(const Graph& _graph, const Arc& arc)

   411 	: Arc(arc), graph(&_graph) {}

   413       OutArcIt& operator++() {

   414 	graph->nextOut(*this);

   415 	return *this;

   416       }

   418     };

   421     class InArcIt : public Arc {

   422       const Graph* graph;

   423     public:

   425       InArcIt() { }

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

   429       InArcIt(const Graph& _graph, const Node& node)

   430 	: graph(&_graph) {

   431 	_graph.firstIn(*this, node);

   432       }

   434       InArcIt(const Graph& _graph, const Arc& arc) :

   435 	Arc(arc), graph(&_graph) {}

   437       InArcIt& operator++() {

   438 	graph->nextIn(*this);

   439 	return *this;

   440       }

   442     };

   445     class EdgeIt : public Parent::Edge {

   446       const Graph* graph;

   447     public:

   449       EdgeIt() { }

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

   453       explicit EdgeIt(const Graph& _graph) : graph(&_graph) {

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

   455       }

   457       EdgeIt(const Graph& _graph, const Edge& e) :

   458 	Edge(e), graph(&_graph) { }

   460       EdgeIt& operator++() {

   461 	graph->next(*this);

   462 	return *this;

   463       }

   465     };

   467     class IncEdgeIt : public Parent::Edge {

   468       friend class EdgeSetExtender;

   469       const Graph* graph;

   470       bool direction;

   471     public:

   473       IncEdgeIt() { }

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

   477       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {

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

   479       }

   481       IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n)

   482 	: graph(&_graph), Edge(ue) {

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

   484       }

   486       IncEdgeIt& operator++() {

   487 	graph->nextInc(*this, direction);

   488 	return *this;

   489       }

   490     };

   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     }

   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     }

   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     }

   534     template <typename _Value>

   535     class ArcMap

   536       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

   537       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

   539     public:

   540       explicit ArcMap(const Graph& _g)

   541 	: Parent(_g) {}

   542       ArcMap(const Graph& _g, const _Value& _v)

   543 	: Parent(_g, _v) {}

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

   546 	return operator=<ArcMap>(cmap);

   547       }

   549       template <typename CMap>

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

   551         Parent::operator=(cmap);

   552 	return *this;

   553       }

   555     };

   558     template <typename _Value>

   559     class EdgeMap

   560       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

   561       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   563     public:

   564       explicit EdgeMap(const Graph& _g)

   565 	: Parent(_g) {}

   567       EdgeMap(const Graph& _g, const _Value& _v)

   568 	: Parent(_g, _v) {}

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

   571 	return operator=<EdgeMap>(cmap);

   572       }

   574       template <typename CMap>

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

   576         Parent::operator=(cmap);

   577 	return *this;

   578       }

   580     };

   583     // Alteration extension

   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     }

   595     void clear() {

   596       notifier(Arc()).clear();

   597       notifier(Edge()).clear();

   598       Parent::clear();

   599     }

   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     }

   611     EdgeSetExtender() {

   612       arc_notifier.setContainer(*this);

   613       edge_notifier.setContainer(*this);

   614     }

   616     ~EdgeSetExtender() {

   617       edge_notifier.clear();

   618       arc_notifier.clear();

   619     }

   621   };

   623 }

   625 #endif

author	Peter Kovacs <kpeter@inf.elte.hu>
	Thu, 12 Nov 2009 23:30:45 +0100
changeset 809	22bb98ca0101
parent 617	4137ef9aacc6
child 877	141f9c0db4a3
child 962	4efe7b32b134
permissions	-rw-r--r--