lemon-main: lemon/bits/edge_set_extender.h@eb2f9d453070

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library.

     4  *

     5  * Copyright (C) 2003-2010

     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 True UndirectedTag;

   285     typedef typename Parent::Node Node;

   286     typedef typename Parent::Arc Arc;

   287     typedef typename Parent::Edge Edge;

   289     int maxId(Node) const {

   290       return Parent::maxNodeId();

   291     }

   293     int maxId(Arc) const {

   294       return Parent::maxArcId();

   295     }

   297     int maxId(Edge) const {

   298       return Parent::maxEdgeId();

   299     }

   301     Node fromId(int id, Node) const {

   302       return Parent::nodeFromId(id);

   303     }

   305     Arc fromId(int id, Arc) const {

   306       return Parent::arcFromId(id);

   307     }

   309     Edge fromId(int id, Edge) const {

   310       return Parent::edgeFromId(id);

   311     }

   313     Node oppositeNode(const Node &n, const Edge &e) const {

   314       if( n == Parent::u(e))

   315         return Parent::v(e);

   316       else if( n == Parent::v(e))

   317         return Parent::u(e);

   318       else

   319         return INVALID;

   320     }

   322     Arc oppositeArc(const Arc &e) const {

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

   324     }

   326     using Parent::direct;

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

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

   329     }

   331     typedef AlterationNotifier<EdgeSetExtender, Arc> ArcNotifier;

   332     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;

   335   protected:

   337     mutable ArcNotifier arc_notifier;

   338     mutable EdgeNotifier edge_notifier;

   340   public:

   342     using Parent::notifier;

   344     ArcNotifier& notifier(Arc) const {

   345       return arc_notifier;

   346     }

   348     EdgeNotifier& notifier(Edge) const {

   349       return edge_notifier;

   350     }

   353     class NodeIt : public Node {

   354       const Graph* graph;

   355     public:

   357       NodeIt() {}

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

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

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

   363       }

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

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

   368       NodeIt& operator++() {

   369         graph->next(*this);

   370         return *this;

   371       }

   373     };

   376     class ArcIt : public Arc {

   377       const Graph* graph;

   378     public:

   380       ArcIt() { }

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

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

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

   386       }

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

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

   391       ArcIt& operator++() {

   392         graph->next(*this);

   393         return *this;

   394       }

   396     };

   399     class OutArcIt : public Arc {

   400       const Graph* graph;

   401     public:

   403       OutArcIt() { }

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

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

   408         : graph(&_graph) {

   409         _graph.firstOut(*this, node);

   410       }

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

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

   415       OutArcIt& operator++() {

   416         graph->nextOut(*this);

   417         return *this;

   418       }

   420     };

   423     class InArcIt : public Arc {

   424       const Graph* graph;

   425     public:

   427       InArcIt() { }

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

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

   432         : graph(&_graph) {

   433         _graph.firstIn(*this, node);

   434       }

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

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

   439       InArcIt& operator++() {

   440         graph->nextIn(*this);

   441         return *this;

   442       }

   444     };

   447     class EdgeIt : public Parent::Edge {

   448       const Graph* graph;

   449     public:

   451       EdgeIt() { }

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

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

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

   457       }

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

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

   462       EdgeIt& operator++() {

   463         graph->next(*this);

   464         return *this;

   465       }

   467     };

   469     class IncEdgeIt : public Parent::Edge {

   470       friend class EdgeSetExtender;

   471       const Graph* graph;

   472       bool direction;

   473     public:

   475       IncEdgeIt() { }

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

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

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

   481       }

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

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

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

   486       }

   488       IncEdgeIt& operator++() {

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

   490         return *this;

   491       }

   492     };

   494     // \brief Base node of the iterator

   495     //

   496     // Returns the base node (ie. the source in this case) of the iterator

   497     Node baseNode(const OutArcIt &e) const {

   498       return Parent::source(static_cast<const Arc&>(e));

   499     }

   500     // \brief Running node of the iterator

   501     //

   502     // Returns the running node (ie. the target in this case) of the

   503     // iterator

   504     Node runningNode(const OutArcIt &e) const {

   505       return Parent::target(static_cast<const Arc&>(e));

   506     }

   508     // \brief Base node of the iterator

   509     //

   510     // Returns the base node (ie. the target in this case) of the iterator

   511     Node baseNode(const InArcIt &e) const {

   512       return Parent::target(static_cast<const Arc&>(e));

   513     }

   514     // \brief Running node of the iterator

   515     //

   516     // Returns the running node (ie. the source in this case) of the

   517     // iterator

   518     Node runningNode(const InArcIt &e) const {

   519       return Parent::source(static_cast<const Arc&>(e));

   520     }

   522     // Base node of the iterator

   523     //

   524     // Returns the base node of the iterator

   525     Node baseNode(const IncEdgeIt &e) const {

   526       return e.direction ? this->u(e) : this->v(e);

   527     }

   528     // Running node of the iterator

   529     //

   530     // Returns the running node of the iterator

   531     Node runningNode(const IncEdgeIt &e) const {

   532       return e.direction ? this->v(e) : this->u(e);

   533     }

   536     template <typename _Value>

   537     class ArcMap

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

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

   541     public:

   542       explicit ArcMap(const Graph& _g)

   543         : Parent(_g) {}

   544       ArcMap(const Graph& _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<Graph, Edge, _Value> > {

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

   565     public:

   566       explicit EdgeMap(const Graph& _g)

   567         : Parent(_g) {}

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

   570         : Parent(_g, _v) {}

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

   573         return operator=<EdgeMap>(cmap);

   574       }

   576       template <typename CMap>

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

   578         Parent::operator=(cmap);

   579         return *this;

   580       }

   582     };

   585     // Alteration extension

   587     Edge addEdge(const Node& from, const Node& to) {

   588       Edge edge = Parent::addEdge(from, to);

   589       notifier(Edge()).add(edge);

   590       std::vector<Arc> arcs;

   591       arcs.push_back(Parent::direct(edge, true));

   592       arcs.push_back(Parent::direct(edge, false));

   593       notifier(Arc()).add(arcs);

   594       return edge;

   595     }

   597     void clear() {

   598       notifier(Arc()).clear();

   599       notifier(Edge()).clear();

   600       Parent::clear();

   601     }

   603     void erase(const Edge& edge) {

   604       std::vector<Arc> arcs;

   605       arcs.push_back(Parent::direct(edge, true));

   606       arcs.push_back(Parent::direct(edge, false));

   607       notifier(Arc()).erase(arcs);

   608       notifier(Edge()).erase(edge);

   609       Parent::erase(edge);

   610     }

   613     EdgeSetExtender() {

   614       arc_notifier.setContainer(*this);

   615       edge_notifier.setContainer(*this);

   616     }

   618     ~EdgeSetExtender() {

   619       edge_notifier.clear();

   620       arc_notifier.clear();

   621     }

   623   };

   625 }

   627 #endif

author	Peter Kovacs <kpeter@inf.elte.hu>
	Sat, 16 Mar 2013 14:11:32 +0100
changeset 1052	eb2f9d453070
parent 966	c8fce9beb46a
parent 998	7fdaa05a69a1
child 1092	dceba191c00d
permissions	-rw-r--r--