lemon-0.x: lemon/bits/graph_adaptor_extender.h@054566ac0934

     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_GRAPH_ADAPTOR_EXTENDER_H

    20 #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H

    22 #include <lemon/bits/invalid.h>

    23 #include <lemon/error.h>

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

    28 ///\ingroup graphbits

    29 ///\file

    30 ///\brief Extenders for the graph adaptor types

    31 namespace lemon {

    33   /// \ingroup graphbits

    34   ///

    35   /// \brief Extender for the GraphAdaptors

    36   template <typename _Graph>

    37   class GraphAdaptorExtender : public _Graph {

    38   public:

    40     typedef _Graph Parent;

    41     typedef _Graph Graph;

    42     typedef GraphAdaptorExtender Adaptor;

    44     // Base extensions

    46     typedef typename Parent::Node Node;

    47     typedef typename Parent::Edge Edge;

    49     int maxId(Node) const {

    50       return Parent::maxNodeId();

    51     }

    53     int maxId(Edge) const {

    54       return Parent::maxEdgeId();

    55     }

    57     Node fromId(int id, Node) const {

    58       return Parent::nodeFromId(id);

    59     }

    61     Edge fromId(int id, Edge) const {

    62       return Parent::edgeFromId(id);

    63     }

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

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

    67 	return Parent::target(e);

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

    69 	return Parent::source(e);

    70       else

    71 	return INVALID;

    72     }

    74     class NodeIt : public Node {

    75       const Adaptor* graph;

    76     public:

    78       NodeIt() {}

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

    82       explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {

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

    84       }

    86       NodeIt(const Adaptor& _graph, const Node& node)

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

    89       NodeIt& operator++() {

    90 	graph->next(*this);

    91 	return *this;

    92       }

    94     };

    97     class EdgeIt : public Edge {

    98       const Adaptor* graph;

    99     public:

   101       EdgeIt() { }

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

   105       explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {

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

   107       }

   109       EdgeIt(const Adaptor& _graph, const Edge& e) :

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

   112       EdgeIt& operator++() {

   113 	graph->next(*this);

   114 	return *this;

   115       }

   117     };

   120     class OutEdgeIt : public Edge {

   121       const Adaptor* graph;

   122     public:

   124       OutEdgeIt() { }

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

   128       OutEdgeIt(const Adaptor& _graph, const Node& node)

   129 	: graph(&_graph) {

   130 	_graph.firstOut(*this, node);

   131       }

   133       OutEdgeIt(const Adaptor& _graph, const Edge& edge)

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

   136       OutEdgeIt& operator++() {

   137 	graph->nextOut(*this);

   138 	return *this;

   139       }

   141     };

   144     class InEdgeIt : public Edge {

   145       const Adaptor* graph;

   146     public:

   148       InEdgeIt() { }

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

   152       InEdgeIt(const Adaptor& _graph, const Node& node)

   153 	: graph(&_graph) {

   154 	_graph.firstIn(*this, node);

   155       }

   157       InEdgeIt(const Adaptor& _graph, const Edge& edge) :

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

   160       InEdgeIt& operator++() {

   161 	graph->nextIn(*this);

   162 	return *this;

   163       }

   165     };

   167     /// \brief Base node of the iterator

   168     ///

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

   170     Node baseNode(const OutEdgeIt &e) const {

   171       return Parent::source(e);

   172     }

   173     /// \brief Running node of the iterator

   174     ///

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

   176     /// iterator

   177     Node runningNode(const OutEdgeIt &e) const {

   178       return Parent::target(e);

   179     }

   181     /// \brief Base node of the iterator

   182     ///

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

   184     Node baseNode(const InEdgeIt &e) const {

   185       return Parent::target(e);

   186     }

   187     /// \brief Running node of the iterator

   188     ///

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

   190     /// iterator

   191     Node runningNode(const InEdgeIt &e) const {

   192       return Parent::source(e);

   193     }

   195   };

   198   /// \ingroup graphbits

   199   ///

   200   /// \brief Extender for the UGraphAdaptors

   201   template <typename _UGraph>

   202   class UGraphAdaptorExtender : public _UGraph {

   203   public:

   205     typedef _UGraph Parent;

   206     typedef _UGraph UGraph;

   207     typedef UGraphAdaptorExtender Adaptor;

   209     typedef typename Parent::Node Node;

   210     typedef typename Parent::Edge Edge;

   211     typedef typename Parent::UEdge UEdge;

   213     // UGraph extension

   215     int maxId(Node) const {

   216       return Parent::maxNodeId();

   217     }

   219     int maxId(Edge) const {

   220       return Parent::maxEdgeId();

   221     }

   223     int maxId(UEdge) const {

   224       return Parent::maxUEdgeId();

   225     }

   227     Node fromId(int id, Node) const {

   228       return Parent::nodeFromId(id);

   229     }

   231     Edge fromId(int id, Edge) const {

   232       return Parent::edgeFromId(id);

   233     }

   235     UEdge fromId(int id, UEdge) const {

   236       return Parent::uEdgeFromId(id);

   237     }

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

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

   241 	return Parent::target(e);

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

   243 	return Parent::source(e);

   244       else

   245 	return INVALID;

   246     }

   248     Edge oppositeEdge(const Edge &e) const {

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

   250     }

   252     using Parent::direct;

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

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

   255     }

   258     class NodeIt : public Node {

   259       const Adaptor* graph;

   260     public:

   262       NodeIt() {}

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

   266       explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {

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

   268       }

   270       NodeIt(const Adaptor& _graph, const Node& node)

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

   273       NodeIt& operator++() {

   274 	graph->next(*this);

   275 	return *this;

   276       }

   278     };

   281     class EdgeIt : public Edge {

   282       const Adaptor* graph;

   283     public:

   285       EdgeIt() { }

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

   289       explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {

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

   291       }

   293       EdgeIt(const Adaptor& _graph, const Edge& e) :

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

   296       EdgeIt& operator++() {

   297 	graph->next(*this);

   298 	return *this;

   299       }

   301     };

   304     class OutEdgeIt : public Edge {

   305       const Adaptor* graph;

   306     public:

   308       OutEdgeIt() { }

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

   312       OutEdgeIt(const Adaptor& _graph, const Node& node)

   313 	: graph(&_graph) {

   314 	_graph.firstOut(*this, node);

   315       }

   317       OutEdgeIt(const Adaptor& _graph, const Edge& edge)

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

   320       OutEdgeIt& operator++() {

   321 	graph->nextOut(*this);

   322 	return *this;

   323       }

   325     };

   328     class InEdgeIt : public Edge {

   329       const Adaptor* graph;

   330     public:

   332       InEdgeIt() { }

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

   336       InEdgeIt(const Adaptor& _graph, const Node& node)

   337 	: graph(&_graph) {

   338 	_graph.firstIn(*this, node);

   339       }

   341       InEdgeIt(const Adaptor& _graph, const Edge& edge) :

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

   344       InEdgeIt& operator++() {

   345 	graph->nextIn(*this);

   346 	return *this;

   347       }

   349     };

   351     class UEdgeIt : public Parent::UEdge {

   352       const Adaptor* graph;

   353     public:

   355       UEdgeIt() { }

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

   359       explicit UEdgeIt(const Adaptor& _graph) : graph(&_graph) {

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

   361       }

   363       UEdgeIt(const Adaptor& _graph, const UEdge& e) :

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

   366       UEdgeIt& operator++() {

   367 	graph->next(*this);

   368 	return *this;

   369       }

   371     };

   373     class IncEdgeIt : public Parent::UEdge {

   374       friend class UGraphAdaptorExtender;

   375       const Adaptor* graph;

   376       bool direction;

   377     public:

   379       IncEdgeIt() { }

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

   383       IncEdgeIt(const Adaptor& _graph, const Node &n) : graph(&_graph) {

   384 	_graph.firstInc(static_cast<UEdge&>(*this), direction, n);

   385       }

   387       IncEdgeIt(const Adaptor& _graph, const UEdge &ue, const Node &n)

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

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

   390       }

   392       IncEdgeIt& operator++() {

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

   394 	return *this;

   395       }

   396     };

   398     /// \brief Base node of the iterator

   399     ///

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

   401     Node baseNode(const OutEdgeIt &e) const {

   402       return Parent::source(static_cast<const Edge&>(e));

   403     }

   404     /// \brief Running node of the iterator

   405     ///

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

   407     /// iterator

   408     Node runningNode(const OutEdgeIt &e) const {

   409       return Parent::target(static_cast<const Edge&>(e));

   410     }

   412     /// \brief Base node of the iterator

   413     ///

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

   415     Node baseNode(const InEdgeIt &e) const {

   416       return Parent::target(static_cast<const Edge&>(e));

   417     }

   418     /// \brief Running node of the iterator

   419     ///

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

   421     /// iterator

   422     Node runningNode(const InEdgeIt &e) const {

   423       return Parent::source(static_cast<const Edge&>(e));

   424     }

   426     /// Base node of the iterator

   427     ///

   428     /// Returns the base node of the iterator

   429     Node baseNode(const IncEdgeIt &e) const {

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

   431     }

   432     /// Running node of the iterator

   433     ///

   434     /// Returns the running node of the iterator

   435     Node runningNode(const IncEdgeIt &e) const {

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

   437     }

   439   };

   441   /// \ingroup graphbits

   442   ///

   443   /// \brief Extender for the BpUGraphAdaptors

   444   template <typename Base>

   445   class BpUGraphAdaptorExtender : public Base {

   446   public:

   447     typedef Base Parent;

   448     typedef BpUGraphAdaptorExtender Graph;

   450     typedef typename Parent::Node Node;

   451     typedef typename Parent::BNode BNode;

   452     typedef typename Parent::ANode ANode;

   453     typedef typename Parent::Edge Edge;

   454     typedef typename Parent::UEdge UEdge;

   457     int maxId(Node) const {

   458       return Parent::maxNodeId();

   459     }

   460     int maxId(BNode) const {

   461       return Parent::maxBNodeId();

   462     }

   463     int maxId(ANode) const {

   464       return Parent::maxANodeId();

   465     }

   466     int maxId(Edge) const {

   467       return Parent::maxEdgeId();

   468     }

   469     int maxId(UEdge) const {

   470       return Parent::maxUEdgeId();

   471     }

   474     Node fromId(int id, Node) const {

   475       return Parent::nodeFromId(id);

   476     }

   477     ANode fromId(int id, ANode) const {

   478       return Parent::nodeFromANodeId(id);

   479     }

   480     BNode fromId(int id, BNode) const {

   481       return Parent::nodeFromBNodeId(id);

   482     }

   483     Edge fromId(int id, Edge) const {

   484       return Parent::edgeFromId(id);

   485     }

   486     UEdge fromId(int id, UEdge) const {

   487       return Parent::uEdgeFromId(id);

   488     }

   490     class NodeIt : public Node {

   491       const Graph* graph;

   492     public:

   494       NodeIt() { }

   496       NodeIt(Invalid i) : Node(INVALID) { }

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

   499 	graph->first(static_cast<Node&>(*this));

   500       }

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

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

   505       NodeIt& operator++() {

   506 	graph->next(*this);

   507 	return *this;

   508       }

   510     };

   512     class ANodeIt : public Node {

   513       friend class BpUGraphAdaptorExtender;

   514       const Graph* graph;

   515     public:

   517       ANodeIt() { }

   519       ANodeIt(Invalid i) : Node(INVALID) { }

   521       explicit ANodeIt(const Graph& _graph) : graph(&_graph) {

   522 	graph->firstANode(static_cast<Node&>(*this));

   523       }

   525       ANodeIt(const Graph& _graph, const Node& node)

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

   528       ANodeIt& operator++() {

   529 	graph->nextANode(*this);

   530 	return *this;

   531       }

   532     };

   534     class BNodeIt : public Node {

   535       friend class BpUGraphAdaptorExtender;

   536       const Graph* graph;

   537     public:

   539       BNodeIt() { }

   541       BNodeIt(Invalid i) : Node(INVALID) { }

   543       explicit BNodeIt(const Graph& _graph) : graph(&_graph) {

   544 	graph->firstBNode(static_cast<Node&>(*this));

   545       }

   547       BNodeIt(const Graph& _graph, const Node& node)

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

   550       BNodeIt& operator++() {

   551 	graph->nextBNode(*this);

   552 	return *this;

   553       }

   554     };

   556     class EdgeIt : public Edge {

   557       friend class BpUGraphAdaptorExtender;

   558       const Graph* graph;

   559     public:

   561       EdgeIt() { }

   563       EdgeIt(Invalid i) : Edge(INVALID) { }

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

   566 	graph->first(static_cast<Edge&>(*this));

   567       }

   569       EdgeIt(const Graph& _graph, const Edge& edge)

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

   572       EdgeIt& operator++() {

   573 	graph->next(*this);

   574 	return *this;

   575       }

   577     };

   579     class UEdgeIt : public UEdge {

   580       friend class BpUGraphAdaptorExtender;

   581       const Graph* graph;

   582     public:

   584       UEdgeIt() { }

   586       UEdgeIt(Invalid i) : UEdge(INVALID) { }

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

   589 	graph->first(static_cast<UEdge&>(*this));

   590       }

   592       UEdgeIt(const Graph& _graph, const UEdge& edge)

   593 	: UEdge(edge), graph(&_graph) { }

   595       UEdgeIt& operator++() {

   596 	graph->next(*this);

   597 	return *this;

   598       }

   599     };

   601     class OutEdgeIt : public Edge {

   602       friend class BpUGraphAdaptorExtender;

   603       const Graph* graph;

   604     public:

   606       OutEdgeIt() { }

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

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

   611 	: graph(&_graph) {

   612 	graph->firstOut(*this, node);

   613       }

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

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

   618       OutEdgeIt& operator++() {

   619 	graph->nextOut(*this);

   620 	return *this;

   621       }

   623     };

   626     class InEdgeIt : public Edge {

   627       friend class BpUGraphAdaptorExtender;

   628       const Graph* graph;

   629     public:

   631       InEdgeIt() { }

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

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

   636 	: graph(&_graph) {

   637 	graph->firstIn(*this, node);

   638       }

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

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

   643       InEdgeIt& operator++() {

   644 	graph->nextIn(*this);

   645 	return *this;

   646       }

   648     };

   650     /// \brief Base node of the iterator

   651     ///

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

   653     Node baseNode(const OutEdgeIt &e) const {

   654       return Parent::source(static_cast<const Edge&>(e));

   655     }

   656     /// \brief Running node of the iterator

   657     ///

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

   659     /// iterator

   660     Node runningNode(const OutEdgeIt &e) const {

   661       return Parent::target(static_cast<const Edge&>(e));

   662     }

   664     /// \brief Base node of the iterator

   665     ///

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

   667     Node baseNode(const InEdgeIt &e) const {

   668       return Parent::target(static_cast<const Edge&>(e));

   669     }

   670     /// \brief Running node of the iterator

   671     ///

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

   673     /// iterator

   674     Node runningNode(const InEdgeIt &e) const {

   675       return Parent::source(static_cast<const Edge&>(e));

   676     }

   678     class IncEdgeIt : public Parent::UEdge {

   679       friend class BpUGraphAdaptorExtender;

   680       const Graph* graph;

   681       bool direction;

   682     public:

   684       IncEdgeIt() { }

   686       IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }

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

   689 	graph->firstInc(*this, direction, n);

   690       }

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

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

   694 	direction = (graph->source(ue) == n);

   695       }

   697       IncEdgeIt& operator++() {

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

   699 	return *this;

   700       }

   701     };

   704     /// Base node of the iterator

   705     ///

   706     /// Returns the base node of the iterator

   707     Node baseNode(const IncEdgeIt &e) const {

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

   709     }

   711     /// Running node of the iterator

   712     ///

   713     /// Returns the running node of the iterator

   714     Node runningNode(const IncEdgeIt &e) const {

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

   716     }

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

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

   720 	return Parent::target(e);

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

   722 	return Parent::source(e);

   723       else

   724 	return INVALID;

   725     }

   727     Edge oppositeEdge(const Edge &e) const {

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

   729     }

   731     using Parent::direct;

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

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

   734     }

   736   };

   739 }

   742 #endif

author	kpeter
	Thu, 28 Feb 2008 02:54:27 +0000
changeset 2581	054566ac0934
parent 2391	14a343be7a5a
permissions	-rw-r--r--