lemon-0.x: lemon/bits/edge_set_extender.h@ac729a29120e

     1 /* -*- C++ -*-

     2  *

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

     4  *

     5  * Copyright (C) 2003-2006

     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/bits/invalid.h>

    23 #include <lemon/error.h>

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

    27 ///\ingroup graphbits

    28 ///\file

    29 ///\brief Extenders for the edge set types

    30 namespace lemon {

    32   /// \ingroup graphbits

    33   ///

    34   /// \brief Extender for the EdgeSets

    35   template <typename Base>

    36   class EdgeSetExtender : public Base {

    37   public:

    39     typedef Base Parent;

    40     typedef EdgeSetExtender Graph;

    42     // Base extensions

    44     typedef typename Parent::Node Node;

    45     typedef typename Parent::Edge Edge;

    47     int maxId(Node) const {

    48       return Parent::maxNodeId();

    49     }

    51     int maxId(Edge) const {

    52       return Parent::maxEdgeId();

    53     }

    55     Node fromId(int id, Node) const {

    56       return Parent::nodeFromId(id);

    57     }

    59     Edge fromId(int id, Edge) const {

    60       return Parent::edgeFromId(id);

    61     }

    63     Node oppositeNode(const Node &n, const Edge &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 edge observer registry.

    76     typedef AlterationNotifier<EdgeSetExtender, Edge> EdgeNotifier;

    78   protected:

    80     mutable EdgeNotifier edge_notifier;

    82   public:

    84     using Parent::getNotifier;

    86     /// \brief Gives back the edge alteration notifier.

    87     ///

    88     /// Gives back the edge alteration notifier.

    89     EdgeNotifier& getNotifier(Edge) const {

    90       return edge_notifier;

    91     }

    93     // Iterable extensions

    95     class NodeIt : public Node {

    96       const Graph* graph;

    97     public:

    99       NodeIt() {}

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

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

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

   105       }

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

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

   110       NodeIt& operator++() {

   111 	graph->next(*this);

   112 	return *this;

   113       }

   115     };

   118     class EdgeIt : public Edge {

   119       const Graph* graph;

   120     public:

   122       EdgeIt() { }

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

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

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

   128       }

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

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

   133       EdgeIt& operator++() {

   134 	graph->next(*this);

   135 	return *this;

   136       }

   138     };

   141     class OutEdgeIt : public Edge {

   142       const Graph* graph;

   143     public:

   145       OutEdgeIt() { }

   147       OutEdgeIt(Invalid i) : Edge(i) { }

   149       OutEdgeIt(const Graph& _graph, const Node& node)

   150 	: graph(&_graph) {

   151 	_graph.firstOut(*this, node);

   152       }

   154       OutEdgeIt(const Graph& _graph, const Edge& edge)

   155 	: Edge(edge), graph(&_graph) {}

   157       OutEdgeIt& operator++() {

   158 	graph->nextOut(*this);

   159 	return *this;

   160       }

   162     };

   165     class InEdgeIt : public Edge {

   166       const Graph* graph;

   167     public:

   169       InEdgeIt() { }

   171       InEdgeIt(Invalid i) : Edge(i) { }

   173       InEdgeIt(const Graph& _graph, const Node& node)

   174 	: graph(&_graph) {

   175 	_graph.firstIn(*this, node);

   176       }

   178       InEdgeIt(const Graph& _graph, const Edge& edge) :

   179 	Edge(edge), graph(&_graph) {}

   181       InEdgeIt& operator++() {

   182 	graph->nextIn(*this);

   183 	return *this;

   184       }

   186     };

   188     /// \brief Base node of the iterator

   189     ///

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

   191     Node baseNode(const OutEdgeIt &e) const {

   192       return Parent::source((Edge)e);

   193     }

   194     /// \brief Running node of the iterator

   195     ///

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

   197     /// iterator

   198     Node runningNode(const OutEdgeIt &e) const {

   199       return Parent::target((Edge)e);

   200     }

   202     /// \brief Base node of the iterator

   203     ///

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

   205     Node baseNode(const InEdgeIt &e) const {

   206       return Parent::target((Edge)e);

   207     }

   208     /// \brief Running node of the iterator

   209     ///

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

   211     /// iterator

   212     Node runningNode(const InEdgeIt &e) const {

   213       return Parent::source((Edge)e);

   214     }

   216     using Parent::first;

   218     // Mappable extension

   220     template <typename _Value>

   221     class EdgeMap

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

   223     public:

   224       typedef EdgeSetExtender Graph;

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

   227       explicit EdgeMap(const Graph& _g)

   228 	: Parent(_g) {}

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

   230 	: Parent(_g, _v) {}

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

   233 	return operator=<EdgeMap>(cmap);

   234       }

   236       template <typename CMap>

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

   238         Parent::operator=(cmap);

   239 	return *this;

   240       }

   242     };

   245     // Alteration extension

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

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

   249       getNotifier(Edge()).add(edge);

   250       return edge;

   251     }

   253     void clear() {

   254       getNotifier(Edge()).clear();

   255       Parent::clear();

   256     }

   258     void erase(const Edge& edge) {

   259       getNotifier(Edge()).erase(edge);

   260       Parent::erase(edge);

   261     }

   263     EdgeSetExtender() {

   264       edge_notifier.setContainer(*this);

   265     }

   267     ~EdgeSetExtender() {

   268       edge_notifier.clear();

   269     }

   271   };

   274   /// \ingroup graphbits

   275   ///

   276   /// \brief Extender for the UEdgeSets

   277   template <typename Base>

   278   class UEdgeSetExtender : public Base {

   280   public:

   282     typedef Base Parent;

   283     typedef UEdgeSetExtender Graph;

   285     typedef typename Parent::Node Node;

   286     typedef typename Parent::Edge Edge;

   287     typedef typename Parent::UEdge UEdge;

   290     int maxId(Node) const {

   291       return Parent::maxNodeId();

   292     }

   294     int maxId(Edge) const {

   295       return Parent::maxEdgeId();

   296     }

   298     int maxId(UEdge) const {

   299       return Parent::maxUEdgeId();

   300     }

   302     Node fromId(int id, Node) const {

   303       return Parent::nodeFromId(id);

   304     }

   306     Edge fromId(int id, Edge) const {

   307       return Parent::edgeFromId(id);

   308     }

   310     UEdge fromId(int id, UEdge) const {

   311       return Parent::uEdgeFromId(id);

   312     }

   314     Node oppositeNode(const Node &n, const UEdge &e) const {

   315       if( n == Parent::source(e))

   316 	return Parent::target(e);

   317       else if( n == Parent::target(e))

   318 	return Parent::source(e);

   319       else

   320 	return INVALID;

   321     }

   323     Edge oppositeEdge(const Edge &e) const {

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

   325     }

   327     using Parent::direct;

   328     Edge direct(const UEdge &ue, const Node &s) const {

   329       return Parent::direct(ue, Parent::source(ue) == s);

   330     }

   332     typedef AlterationNotifier<UEdgeSetExtender, Edge> EdgeNotifier;

   333     typedef AlterationNotifier<UEdgeSetExtender, UEdge> UEdgeNotifier;

   336   protected:

   338     mutable EdgeNotifier edge_notifier;

   339     mutable UEdgeNotifier uedge_notifier;

   341   public:

   343     using Parent::getNotifier;

   345     EdgeNotifier& getNotifier(Edge) const {

   346       return edge_notifier;

   347     }

   349     UEdgeNotifier& getNotifier(UEdge) const {

   350       return uedge_notifier;

   351     }

   354     class NodeIt : public Node {

   355       const Graph* graph;

   356     public:

   358       NodeIt() {}

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

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

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

   364       }

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

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

   369       NodeIt& operator++() {

   370 	graph->next(*this);

   371 	return *this;

   372       }

   374     };

   377     class EdgeIt : public Edge {

   378       const Graph* graph;

   379     public:

   381       EdgeIt() { }

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

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

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

   387       }

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

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

   392       EdgeIt& operator++() {

   393 	graph->next(*this);

   394 	return *this;

   395       }

   397     };

   400     class OutEdgeIt : public Edge {

   401       const Graph* graph;

   402     public:

   404       OutEdgeIt() { }

   406       OutEdgeIt(Invalid i) : Edge(i) { }

   408       OutEdgeIt(const Graph& _graph, const Node& node)

   409 	: graph(&_graph) {

   410 	_graph.firstOut(*this, node);

   411       }

   413       OutEdgeIt(const Graph& _graph, const Edge& edge)

   414 	: Edge(edge), graph(&_graph) {}

   416       OutEdgeIt& operator++() {

   417 	graph->nextOut(*this);

   418 	return *this;

   419       }

   421     };

   424     class InEdgeIt : public Edge {

   425       const Graph* graph;

   426     public:

   428       InEdgeIt() { }

   430       InEdgeIt(Invalid i) : Edge(i) { }

   432       InEdgeIt(const Graph& _graph, const Node& node)

   433 	: graph(&_graph) {

   434 	_graph.firstIn(*this, node);

   435       }

   437       InEdgeIt(const Graph& _graph, const Edge& edge) :

   438 	Edge(edge), graph(&_graph) {}

   440       InEdgeIt& operator++() {

   441 	graph->nextIn(*this);

   442 	return *this;

   443       }

   445     };

   448     class UEdgeIt : public Parent::UEdge {

   449       const Graph* graph;

   450     public:

   452       UEdgeIt() { }

   454       UEdgeIt(Invalid i) : UEdge(i) { }

   456       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {

   457 	_graph.first(static_cast<UEdge&>(*this));

   458       }

   460       UEdgeIt(const Graph& _graph, const UEdge& e) :

   461 	UEdge(e), graph(&_graph) { }

   463       UEdgeIt& operator++() {

   464 	graph->next(*this);

   465 	return *this;

   466       }

   468     };

   470     class IncEdgeIt : public Parent::UEdge {

   471       friend class UEdgeSetExtender;

   472       const Graph* graph;

   473       bool direction;

   474     public:

   476       IncEdgeIt() { }

   478       IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }

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

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

   482       }

   484       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)

   485 	: graph(&_graph), UEdge(ue) {

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

   487       }

   489       IncEdgeIt& operator++() {

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

   491 	return *this;

   492       }

   493     };

   495     /// \brief Base node of the iterator

   496     ///

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

   498     Node baseNode(const OutEdgeIt &e) const {

   499       return Parent::source((Edge)e);

   500     }

   501     /// \brief Running node of the iterator

   502     ///

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

   504     /// iterator

   505     Node runningNode(const OutEdgeIt &e) const {

   506       return Parent::target((Edge)e);

   507     }

   509     /// \brief Base node of the iterator

   510     ///

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

   512     Node baseNode(const InEdgeIt &e) const {

   513       return Parent::target((Edge)e);

   514     }

   515     /// \brief Running node of the iterator

   516     ///

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

   518     /// iterator

   519     Node runningNode(const InEdgeIt &e) const {

   520       return Parent::source((Edge)e);

   521     }

   523     /// Base node of the iterator

   524     ///

   525     /// Returns the base node of the iterator

   526     Node baseNode(const IncEdgeIt &e) const {

   527       return e.direction ? source(e) : target(e);

   528     }

   529     /// Running node of the iterator

   530     ///

   531     /// Returns the running node of the iterator

   532     Node runningNode(const IncEdgeIt &e) const {

   533       return e.direction ? target(e) : source(e);

   534     }

   537     template <typename _Value>

   538     class EdgeMap

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

   540     public:

   541       typedef UEdgeSetExtender Graph;

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

   544       EdgeMap(const Graph& _g)

   545 	: Parent(_g) {}

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

   547 	: Parent(_g, _v) {}

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

   550 	return operator=<EdgeMap>(cmap);

   551       }

   553       template <typename CMap>

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

   555         Parent::operator=(cmap);

   556 	return *this;

   557       }

   559     };

   562     template <typename _Value>

   563     class UEdgeMap

   564       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {

   565     public:

   566       typedef UEdgeSetExtender Graph;

   567       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;

   569       UEdgeMap(const Graph& _g)

   570 	: Parent(_g) {}

   572       UEdgeMap(const Graph& _g, const _Value& _v)

   573 	: Parent(_g, _v) {}

   575       UEdgeMap& operator=(const UEdgeMap& cmap) {

   576 	return operator=<UEdgeMap>(cmap);

   577       }

   579       template <typename CMap>

   580       UEdgeMap& operator=(const CMap& cmap) {

   581         Parent::operator=(cmap);

   582 	return *this;

   583       }

   585     };

   588     // Alteration extension

   590     UEdge addEdge(const Node& from, const Node& to) {

   591       UEdge uedge = Parent::addEdge(from, to);

   592       getNotifier(UEdge()).add(uedge);

   593       getNotifier(Edge()).add(Parent::direct(uedge, true));

   594       getNotifier(Edge()).add(Parent::direct(uedge, false));

   595       return uedge;

   596     }

   598     void clear() {

   599       getNotifier(Edge()).clear();

   600       getNotifier(UEdge()).clear();

   601       Parent::clear();

   602     }

   604     void erase(const UEdge& uedge) {

   605       getNotifier(Edge()).erase(Parent::direct(uedge, true));

   606       getNotifier(Edge()).erase(Parent::direct(uedge, false));

   607       getNotifier(UEdge()).erase(uedge);

   608       Parent::erase(uedge);

   609     }

   612     UEdgeSetExtender() {

   613       edge_notifier.setContainer(*this);

   614       uedge_notifier.setContainer(*this);

   615     }

   617     ~UEdgeSetExtender() {

   618       uedge_notifier.clear();

   619       edge_notifier.clear();

   620     }

   622   };

   624 }

   626 #endif

author	alpar
	Mon, 30 Oct 2006 12:25:43 +0000
changeset 2270	ac729a29120e
parent 2031	080d51024ac5
child 2384	805c5a2a36dd
permissions	-rw-r--r--