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

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

    20 namespace lemon {

    22   template <typename Base>

    23   class EdgeSetExtender : public Base {

    24   public:

    26     typedef Base Parent;

    27     typedef EdgeSetExtender Graph;

    29     // Base extensions

    31     typedef typename Parent::Node Node;

    32     typedef typename Parent::Edge Edge;

    34     int maxId(Node) const {

    35       return Parent::maxNodeId();

    36     }

    38     int maxId(Edge) const {

    39       return Parent::maxEdgeId();

    40     }

    42     Node fromId(int id, Node) const {

    43       return Parent::nodeFromId(id);

    44     }

    46     Edge fromId(int id, Edge) const {

    47       return Parent::edgeFromId(id);

    48     }

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

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

    52 	return Parent::target(e);

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

    54 	return Parent::source(e);

    55       else

    56 	return INVALID;

    57     }

    60     // Alteration notifier extensions

    62     /// The edge observer registry.

    63     typedef AlterationNotifier<Edge> EdgeNotifier;

    65   protected:

    67     mutable EdgeNotifier edge_notifier;

    69   public:

    71     using Parent::getNotifier;

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

    74     ///

    75     /// Gives back the edge alteration notifier.

    76     EdgeNotifier& getNotifier(Edge) const {

    77       return edge_notifier;

    78     }

    80     // Iterable extensions

    82     class NodeIt : public Node {

    83       const Graph* graph;

    84     public:

    86       NodeIt() {}

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

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

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

    92       }

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

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

    97       NodeIt& operator++() {

    98 	graph->next(*this);

    99 	return *this;

   100       }

   102     };

   105     class EdgeIt : public Edge {

   106       const Graph* graph;

   107     public:

   109       EdgeIt() { }

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

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

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

   115       }

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

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

   120       EdgeIt& operator++() {

   121 	graph->next(*this);

   122 	return *this;

   123       }

   125     };

   128     class OutEdgeIt : public Edge {

   129       const Graph* graph;

   130     public:

   132       OutEdgeIt() { }

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

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

   137 	: graph(&_graph) {

   138 	_graph.firstOut(*this, node);

   139       }

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

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

   144       OutEdgeIt& operator++() {

   145 	graph->nextOut(*this);

   146 	return *this;

   147       }

   149     };

   152     class InEdgeIt : public Edge {

   153       const Graph* graph;

   154     public:

   156       InEdgeIt() { }

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

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

   161 	: graph(&_graph) {

   162 	_graph.firstIn(*this, node);

   163       }

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

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

   168       InEdgeIt& operator++() {

   169 	graph->nextIn(*this);

   170 	return *this;

   171       }

   173     };

   175     /// \brief Base node of the iterator

   176     ///

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

   178     Node baseNode(const OutEdgeIt &e) const {

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

   180     }

   181     /// \brief Running node of the iterator

   182     ///

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

   184     /// iterator

   185     Node runningNode(const OutEdgeIt &e) const {

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

   187     }

   189     /// \brief Base node of the iterator

   190     ///

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

   192     Node baseNode(const InEdgeIt &e) const {

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

   194     }

   195     /// \brief Running node of the iterator

   196     ///

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

   198     /// iterator

   199     Node runningNode(const InEdgeIt &e) const {

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

   201     }

   203     using Parent::first;

   205     // Mappable extension

   207     template <typename _Value>

   208     class EdgeMap

   209       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {

   210     public:

   211       typedef EdgeSetExtender Graph;

   212       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   214       EdgeMap(const Graph& _g)

   215 	: Parent(_g) {}

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

   217 	: Parent(_g, _v) {}

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

   220 	return operator=<EdgeMap>(cmap);

   221       }

   223       template <typename CMap>

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

   225 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   226 	const typename Parent::Graph* graph = Parent::getGraph();

   227 	Edge it;

   228 	for (graph->first(it); it != INVALID; graph->next(it)) {

   229 	  Parent::set(it, cmap[it]);

   230 	}

   231 	return *this;

   232       }

   233     };

   236     // Alteration extension

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

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

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

   241       return edge;

   242     }

   244     void clear() {

   245       getNotifier(Edge()).clear();

   246       Parent::clear();

   247     }

   249     void erase(const Edge& edge) {

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

   251       Parent::erase(edge);

   252     }

   255     ~EdgeSetExtender() {

   256       edge_notifier.clear();

   257     }

   259   };

   262   template <typename Base>

   263   class UEdgeSetExtender : public Base {

   265   public:

   267     typedef Base Parent;

   268     typedef UEdgeSetExtender Graph;

   270     typedef typename Parent::Node Node;

   271     typedef typename Parent::Edge Edge;

   272     typedef typename Parent::UEdge UEdge;

   275     int maxId(Node) const {

   276       return Parent::maxNodeId();

   277     }

   279     int maxId(Edge) const {

   280       return Parent::maxEdgeId();

   281     }

   283     int maxId(UEdge) const {

   284       return Parent::maxUEdgeId();

   285     }

   287     Node fromId(int id, Node) const {

   288       return Parent::nodeFromId(id);

   289     }

   291     Edge fromId(int id, Edge) const {

   292       return Parent::edgeFromId(id);

   293     }

   295     UEdge fromId(int id, UEdge) const {

   296       return Parent::uEdgeFromId(id);

   297     }

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

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

   301 	return Parent::target(e);

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

   303 	return Parent::source(e);

   304       else

   305 	return INVALID;

   306     }

   308     Edge oppositeEdge(const Edge &e) const {

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

   310     }

   312     using Parent::direct;

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

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

   315     }

   317     typedef AlterationNotifier<Edge> EdgeNotifier;

   318     typedef AlterationNotifier<UEdge> UEdgeNotifier;

   321   protected:

   323     mutable EdgeNotifier edge_notifier;

   324     mutable UEdgeNotifier uedge_notifier;

   326   public:

   328     using Parent::getNotifier;

   330     EdgeNotifier& getNotifier(Edge) const {

   331       return edge_notifier;

   332     }

   334     UEdgeNotifier& getNotifier(UEdge) const {

   335       return uedge_notifier;

   336     }

   339     class NodeIt : public Node {

   340       const Graph* graph;

   341     public:

   343       NodeIt() {}

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

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

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

   349       }

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

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

   354       NodeIt& operator++() {

   355 	graph->next(*this);

   356 	return *this;

   357       }

   359     };

   362     class EdgeIt : public Edge {

   363       const Graph* graph;

   364     public:

   366       EdgeIt() { }

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

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

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

   372       }

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

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

   377       EdgeIt& operator++() {

   378 	graph->next(*this);

   379 	return *this;

   380       }

   382     };

   385     class OutEdgeIt : public Edge {

   386       const Graph* graph;

   387     public:

   389       OutEdgeIt() { }

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

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

   394 	: graph(&_graph) {

   395 	_graph.firstOut(*this, node);

   396       }

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

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

   401       OutEdgeIt& operator++() {

   402 	graph->nextOut(*this);

   403 	return *this;

   404       }

   406     };

   409     class InEdgeIt : public Edge {

   410       const Graph* graph;

   411     public:

   413       InEdgeIt() { }

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

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

   418 	: graph(&_graph) {

   419 	_graph.firstIn(*this, node);

   420       }

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

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

   425       InEdgeIt& operator++() {

   426 	graph->nextIn(*this);

   427 	return *this;

   428       }

   430     };

   433     class UEdgeIt : public Parent::UEdge {

   434       const Graph* graph;

   435     public:

   437       UEdgeIt() { }

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

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

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

   443       }

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

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

   448       UEdgeIt& operator++() {

   449 	graph->next(*this);

   450 	return *this;

   451       }

   453     };

   455     class IncEdgeIt : public Parent::UEdge {

   456       friend class UEdgeSetExtender;

   457       const Graph* graph;

   458       bool direction;

   459     public:

   461       IncEdgeIt() { }

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

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

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

   467       }

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

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

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

   472       }

   474       IncEdgeIt& operator++() {

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

   476 	return *this;

   477       }

   478     };

   480     /// \brief Base node of the iterator

   481     ///

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

   483     Node baseNode(const OutEdgeIt &e) const {

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

   485     }

   486     /// \brief Running node of the iterator

   487     ///

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

   489     /// iterator

   490     Node runningNode(const OutEdgeIt &e) const {

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

   492     }

   494     /// \brief Base node of the iterator

   495     ///

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

   497     Node baseNode(const InEdgeIt &e) const {

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

   499     }

   500     /// \brief Running node of the iterator

   501     ///

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

   503     /// iterator

   504     Node runningNode(const InEdgeIt &e) const {

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

   506     }

   508     /// Base node of the iterator

   509     ///

   510     /// Returns the base node of the iterator

   511     Node baseNode(const IncEdgeIt &e) const {

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

   513     }

   514     /// Running node of the iterator

   515     ///

   516     /// Returns the running node of the iterator

   517     Node runningNode(const IncEdgeIt &e) const {

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

   519     }

   522     template <typename _Value>

   523     class EdgeMap

   524       : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {

   525     public:

   526       typedef UEdgeSetExtender Graph;

   527       typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   529       EdgeMap(const Graph& _g)

   530 	: Parent(_g) {}

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

   532 	: Parent(_g, _v) {}

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

   535 	return operator=<EdgeMap>(cmap);

   536       }

   538       template <typename CMap>

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

   540 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   541 	const typename Parent::Graph* graph = Parent::getGraph();

   542 	Edge it;

   543 	for (graph->first(it); it != INVALID; graph->next(it)) {

   544 	  Parent::set(it, cmap[it]);

   545 	}

   546 	return *this;

   547       }

   548     };

   551     template <typename _Value>

   552     class UEdgeMap

   553       : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {

   554     public:

   555       typedef UEdgeSetExtender Graph;

   556       typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;

   558       UEdgeMap(const Graph& _g)

   559 	: Parent(_g) {}

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

   561 	: Parent(_g, _v) {}

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

   564 	return operator=<UEdgeMap>(cmap);

   565       }

   567       template <typename CMap>

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

   569 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

   570 	const typename Parent::Graph* graph = Parent::getGraph();

   571 	UEdge it;

   572 	for (graph->first(it); it != INVALID; graph->next(it)) {

   573 	  Parent::set(it, cmap[it]);

   574 	}

   575 	return *this;

   576       }

   577     };

   580     // Alteration extension

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

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

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

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

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

   587       return uedge;

   588     }

   590     void clear() {

   591       getNotifier(Edge()).clear();

   592       getNotifier(UEdge()).clear();

   593       Parent::clear();

   594     }

   596     void erase(const UEdge& uedge) {

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

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

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

   600       Parent::erase(uedge);

   601     }

   604     ~UEdgeSetExtender() {

   605       getNotifier(Edge()).clear();

   606       getNotifier(UEdge()).clear();

   607     }

   609   };

   610 }

author	deba
	Thu, 02 Mar 2006 14:22:03 +0000
changeset 1995	c1fc2c14a3ae
parent 1979	c2992fd74dad
child 1996	5dc13b93f8b4
permissions	-rw-r--r--