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

     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     /// \brief Gives back the edge alteration notifier.

    72     ///

    73     /// Gives back the edge alteration notifier.

    74     EdgeNotifier& getNotifier(Edge) const {

    75       return edge_notifier;

    76     }

    78     // Iterable extensions

    80     class NodeIt : public Node {

    81       const Graph* graph;

    82     public:

    84       NodeIt() {}

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

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

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

    90       }

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

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

    95       NodeIt& operator++() {

    96 	graph->next(*this);

    97 	return *this;

    98       }

   100     };

   103     class EdgeIt : public Edge {

   104       const Graph* graph;

   105     public:

   107       EdgeIt() { }

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

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

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

   113       }

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

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

   118       EdgeIt& operator++() {

   119 	graph->next(*this);

   120 	return *this;

   121       }

   123     };

   126     class OutEdgeIt : public Edge {

   127       const Graph* graph;

   128     public:

   130       OutEdgeIt() { }

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

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

   135 	: graph(&_graph) {

   136 	_graph.firstOut(*this, node);

   137       }

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

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

   142       OutEdgeIt& operator++() {

   143 	graph->nextOut(*this);

   144 	return *this;

   145       }

   147     };

   150     class InEdgeIt : public Edge {

   151       const Graph* graph;

   152     public:

   154       InEdgeIt() { }

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

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

   159 	: graph(&_graph) {

   160 	_graph.firstIn(*this, node);

   161       }

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

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

   166       InEdgeIt& operator++() {

   167 	graph->nextIn(*this);

   168 	return *this;

   169       }

   171     };

   173     /// \brief Base node of the iterator

   174     ///

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

   176     Node baseNode(const OutEdgeIt &e) const {

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

   178     }

   179     /// \brief Running node of the iterator

   180     ///

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

   182     /// iterator

   183     Node runningNode(const OutEdgeIt &e) const {

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

   185     }

   187     /// \brief Base node of the iterator

   188     ///

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

   190     Node baseNode(const InEdgeIt &e) const {

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

   192     }

   193     /// \brief Running node of the iterator

   194     ///

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

   196     /// iterator

   197     Node runningNode(const InEdgeIt &e) const {

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

   199     }

   201     using Parent::first;

   203     // Mappable extension

   205     template <typename _Value>

   206     class EdgeMap

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

   208     public:

   209       typedef EdgeSetExtender Graph;

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

   212       EdgeMap(const Graph& _g)

   213 	: Parent(_g) {}

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

   215 	: Parent(_g, _v) {}

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

   218 	return operator=<EdgeMap>(cmap);

   219       }

   221       template <typename CMap>

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

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

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

   225 	Edge it;

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

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

   228 	}

   229 	return *this;

   230       }

   231     };

   234     // Alteration extension

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

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

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

   239       return edge;

   240     }

   242     void clear() {

   243       getNotifier(Edge()).clear();

   244       Parent::clear();

   245     }

   247     void erase(const Edge& edge) {

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

   249       Parent::erase(edge);

   250     }

   253     ~EdgeSetExtender() {

   254       edge_notifier.clear();

   255     }

   257   };

   260   template <typename Base>

   261   class UEdgeSetExtender : public Base {

   263   public:

   265     typedef Base Parent;

   266     typedef UEdgeSetExtender Graph;

   268     typedef typename Parent::Node Node;

   269     typedef typename Parent::Edge Edge;

   270     typedef typename Parent::UEdge UEdge;

   273     int maxId(Node) const {

   274       return Parent::maxNodeId();

   275     }

   277     int maxId(Edge) const {

   278       return Parent::maxEdgeId();

   279     }

   281     int maxId(UEdge) const {

   282       return Parent::maxUEdgeId();

   283     }

   285     Node fromId(int id, Node) const {

   286       return Parent::nodeFromId(id);

   287     }

   289     Edge fromId(int id, Edge) const {

   290       return Parent::edgeFromId(id);

   291     }

   293     UEdge fromId(int id, UEdge) const {

   294       return Parent::uEdgeFromId(id);

   295     }

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

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

   299 	return Parent::target(e);

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

   301 	return Parent::source(e);

   302       else

   303 	return INVALID;

   304     }

   306     Edge oppositeEdge(const Edge &e) const {

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

   308     }

   310     using Parent::direct;

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

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

   313     }

   315     typedef AlterationNotifier<Edge> EdgeNotifier;

   316     typedef AlterationNotifier<UEdge> UEdgeNotifier;

   319   protected:

   321     mutable EdgeNotifier edge_notifier;

   322     mutable UEdgeNotifier uedge_notifier;

   324   public:

   326     EdgeNotifier& getNotifier(Edge) const {

   327       return edge_notifier;

   328     }

   330     UEdgeNotifier& getNotifier(UEdge) const {

   331       return uedge_notifier;

   332     }

   335     class NodeIt : public Node {

   336       const Graph* graph;

   337     public:

   339       NodeIt() {}

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

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

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

   345       }

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

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

   350       NodeIt& operator++() {

   351 	graph->next(*this);

   352 	return *this;

   353       }

   355     };

   358     class EdgeIt : public Edge {

   359       const Graph* graph;

   360     public:

   362       EdgeIt() { }

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

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

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

   368       }

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

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

   373       EdgeIt& operator++() {

   374 	graph->next(*this);

   375 	return *this;

   376       }

   378     };

   381     class OutEdgeIt : public Edge {

   382       const Graph* graph;

   383     public:

   385       OutEdgeIt() { }

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

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

   390 	: graph(&_graph) {

   391 	_graph.firstOut(*this, node);

   392       }

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

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

   397       OutEdgeIt& operator++() {

   398 	graph->nextOut(*this);

   399 	return *this;

   400       }

   402     };

   405     class InEdgeIt : public Edge {

   406       const Graph* graph;

   407     public:

   409       InEdgeIt() { }

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

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

   414 	: graph(&_graph) {

   415 	_graph.firstIn(*this, node);

   416       }

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

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

   421       InEdgeIt& operator++() {

   422 	graph->nextIn(*this);

   423 	return *this;

   424       }

   426     };

   429     class UEdgeIt : public Parent::UEdge {

   430       const Graph* graph;

   431     public:

   433       UEdgeIt() { }

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

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

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

   439       }

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

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

   444       UEdgeIt& operator++() {

   445 	graph->next(*this);

   446 	return *this;

   447       }

   449     };

   451     class IncEdgeIt : public Parent::UEdge {

   452       friend class UEdgeSetExtender;

   453       const Graph* graph;

   454       bool direction;

   455     public:

   457       IncEdgeIt() { }

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

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

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

   463       }

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

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

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

   468       }

   470       IncEdgeIt& operator++() {

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

   472 	return *this;

   473       }

   474     };

   476     /// \brief Base node of the iterator

   477     ///

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

   479     Node baseNode(const OutEdgeIt &e) const {

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

   481     }

   482     /// \brief Running node of the iterator

   483     ///

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

   485     /// iterator

   486     Node runningNode(const OutEdgeIt &e) const {

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

   488     }

   490     /// \brief Base node of the iterator

   491     ///

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

   493     Node baseNode(const InEdgeIt &e) const {

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

   495     }

   496     /// \brief Running node of the iterator

   497     ///

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

   499     /// iterator

   500     Node runningNode(const InEdgeIt &e) const {

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

   502     }

   504     /// Base node of the iterator

   505     ///

   506     /// Returns the base node of the iterator

   507     Node baseNode(const IncEdgeIt &e) const {

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

   509     }

   510     /// Running node of the iterator

   511     ///

   512     /// Returns the running node of the iterator

   513     Node runningNode(const IncEdgeIt &e) const {

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

   515     }

   518     template <typename _Value>

   519     class EdgeMap

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

   521     public:

   522       typedef UEdgeSetExtender Graph;

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

   525       EdgeMap(const Graph& _g)

   526 	: Parent(_g) {}

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

   528 	: Parent(_g, _v) {}

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

   531 	return operator=<EdgeMap>(cmap);

   532       }

   534       template <typename CMap>

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

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

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

   538 	Edge it;

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

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

   541 	}

   542 	return *this;

   543       }

   544     };

   547     template <typename _Value>

   548     class UEdgeMap

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

   550     public:

   551       typedef UEdgeSetExtender Graph;

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

   554       UEdgeMap(const Graph& _g)

   555 	: Parent(_g) {}

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

   557 	: Parent(_g, _v) {}

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

   560 	return operator=<UEdgeMap>(cmap);

   561       }

   563       template <typename CMap>

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

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

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

   567 	UEdge it;

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

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

   570 	}

   571 	return *this;

   572       }

   573     };

   576     // Alteration extension

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

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

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

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

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

   583       return uedge;

   584     }

   586     void clear() {

   587       getNotifier(Edge()).clear();

   588       getNotifier(UEdge()).clear();

   589       Parent::clear();

   590     }

   592     void erase(const UEdge& uedge) {

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

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

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

   596       Parent::erase(uedge);

   597     }

   600     ~UEdgeSetExtender() {

   601       getNotifier(Edge()).clear();

   602       getNotifier(UEdge()).clear();

   603     }

   605   };

   606 }

author	deba
	Thu, 23 Feb 2006 15:10:45 +0000
changeset 1982	f0eb6b79dcdf
child 1991	d7442141d9ef
permissions	-rw-r--r--