lemon-0.x: lemon/bits/iterable_graph

     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_ITERABLE_GRAPH_EXTENDER_H

    20 #define LEMON_ITERABLE_GRAPH_EXTENDER_H

    22 #include <lemon/invalid.h>

    23 #include <lemon/utility.h>

    25 namespace lemon {

    27   template <typename _Base>

    28   class IterableGraphExtender : public _Base {

    29   public:

    31     /// Indicates that the graph is undirected.

    33     ///\todo Better name?

    34     ///

    35     ///\bug Should it be here?

    36     typedef False UTag;

    38     typedef _Base Parent;

    39     typedef IterableGraphExtender<_Base> Graph;

    41     typedef typename Parent::Node Node;

    42     typedef typename Parent::Edge Edge;

    45     class NodeIt : public Node {

    46       const Graph* graph;

    47     public:

    49       NodeIt() {}

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

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

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

    55       }

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

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

    60       NodeIt& operator++() {

    61 	graph->next(*this);

    62 	return *this;

    63       }

    65     };

    68     class EdgeIt : public Edge {

    69       const Graph* graph;

    70     public:

    72       EdgeIt() { }

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

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

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

    78       }

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

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

    83       EdgeIt& operator++() {

    84 	graph->next(*this);

    85 	return *this;

    86       }

    88     };

    91     class OutEdgeIt : public Edge {

    92       const Graph* graph;

    93     public:

    95       OutEdgeIt() { }

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

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

   100 	: graph(&_graph) {

   101 	_graph.firstOut(*this, node);

   102       }

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

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

   107       OutEdgeIt& operator++() {

   108 	graph->nextOut(*this);

   109 	return *this;

   110       }

   112     };

   115     class InEdgeIt : public Edge {

   116       const Graph* graph;

   117     public:

   119       InEdgeIt() { }

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

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

   124 	: graph(&_graph) {

   125 	_graph.firstIn(*this, node);

   126       }

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

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

   131       InEdgeIt& operator++() {

   132 	graph->nextIn(*this);

   133 	return *this;

   134       }

   136     };

   138     /// \brief Base node of the iterator

   139     ///

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

   141     Node baseNode(const OutEdgeIt &e) const {

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

   143     }

   144     /// \brief Running node of the iterator

   145     ///

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

   147     /// iterator

   148     Node runningNode(const OutEdgeIt &e) const {

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

   150     }

   152     /// \brief Base node of the iterator

   153     ///

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

   155     Node baseNode(const InEdgeIt &e) const {

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

   157     }

   158     /// \brief Running node of the iterator

   159     ///

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

   161     /// iterator

   162     Node runningNode(const InEdgeIt &e) const {

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

   164     }

   166     using Parent::first;

   168     /// \brief The opposite node on the given edge.

   169     ///

   170     /// Gives back the opposite on the given edge.

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

   172       if (Parent::source(e) == n) {

   173 	return Parent::target(e);

   174       } else {

   175 	return Parent::source(e);

   176       }

   177     }

   179   private:

   181     // void first(NodeIt &) const;

   182     // void first(EdgeIt &) const;

   183     // void first(OutEdgeIt &) const;

   184     // void first(InEdgeIt &) const;

   186   };

   193   template <typename _Base>

   194   class IterableUGraphExtender : public IterableGraphExtender<_Base> {

   195   public:

   197     /// Indicates that the graph is undirected.

   199     ///\todo Better name?

   200     ///

   201     ///\bug Should it be here?

   202     ///\bug Should be tested in the concept checker whether it is defined

   203     ///correctly.

   204     typedef True UTag;

   206     typedef IterableGraphExtender<_Base> Parent;

   207     typedef IterableUGraphExtender<_Base> Graph;

   208     typedef typename Parent::Node Node;

   209     typedef typename Parent::Edge Edge;

   210     typedef typename Parent::UEdge UEdge;

   212     class UEdgeIt : public Parent::UEdge {

   213       const Graph* graph;

   214     public:

   216       UEdgeIt() { }

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

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

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

   222       }

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

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

   227       UEdgeIt& operator++() {

   228 	graph->next(*this);

   229 	return *this;

   230       }

   232     };

   234     class IncEdgeIt : public Parent::UEdge {

   235       const Graph* graph;

   236       bool direction;

   237       friend class IterableUGraphExtender;

   238     public:

   240       IncEdgeIt() { }

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

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

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

   246       }

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

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

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

   251       }

   253       IncEdgeIt& operator++() {

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

   255 	return *this;

   256       }

   257     };

   259     using Parent::baseNode;

   260     using Parent::runningNode;

   262     /// Base node of the iterator

   263     ///

   264     /// Returns the base node of the iterator

   265     Node baseNode(const IncEdgeIt &e) const {

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

   267     }

   268     /// Running node of the iterator

   269     ///

   270     /// Returns the running node of the iterator

   271     Node runningNode(const IncEdgeIt &e) const {

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

   273     }

   275     /// \brief The opposite node on the given undirected edge.

   276     ///

   277     /// Gives back the opposite on the given undirected edge.

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

   279       if (Parent::source(e) == n) {

   280 	return Parent::target(e);

   281       } else {

   282 	return Parent::source(e);

   283       }

   284     }

   286   };

   289   template <typename _Base>

   290   class IterableBpUGraphExtender : public _Base {

   291   public:

   292     typedef _Base Parent;

   293     typedef IterableBpUGraphExtender Graph;

   295     typedef typename Parent::Node Node;

   296     typedef typename Parent::ANode ANode;

   297     typedef typename Parent::BNode BNode;

   298     typedef typename Parent::Edge Edge;

   299     typedef typename Parent::UEdge UEdge;

   301     class NodeIt : public Node {

   302       const Graph* graph;

   303     public:

   305       NodeIt() { }

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

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

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

   311       }

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

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

   316       NodeIt& operator++() {

   317 	graph->next(*this);

   318 	return *this;

   319       }

   321     };

   323     class ANodeIt : public Node {

   324       friend class IterableBpUGraphExtender;

   325       const Graph* graph;

   326     public:

   328       ANodeIt() { }

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

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

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

   334       }

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

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

   339       ANodeIt& operator++() {

   340 	graph->nextANode(*this);

   341 	return *this;

   342       }

   343     };

   345     class BNodeIt : public Node {

   346       friend class IterableBpUGraphExtender;

   347       const Graph* graph;

   348     public:

   350       BNodeIt() { }

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

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

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

   356       }

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

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

   361       BNodeIt& operator++() {

   362 	graph->nextBNode(*this);

   363 	return *this;

   364       }

   365     };

   367     class EdgeIt : public Edge {

   368       friend class IterableBpUGraphExtender;

   369       const Graph* graph;

   370     public:

   372       EdgeIt() { }

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

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

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

   378       }

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

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

   383       EdgeIt& operator++() {

   384 	graph->next(*this);

   385 	return *this;

   386       }

   388     };

   390     class UEdgeIt : public UEdge {

   391       friend class IterableBpUGraphExtender;

   392       const Graph* graph;

   393     public:

   395       UEdgeIt() { }

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

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

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

   401       }

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

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

   406       UEdgeIt& operator++() {

   407 	graph->next(*this);

   408 	return *this;

   409       }

   410     };

   412     class OutEdgeIt : public Edge {

   413       friend class IterableBpUGraphExtender;

   414       const Graph* graph;

   415     public:

   417       OutEdgeIt() { }

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

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

   422 	: graph(&_graph) {

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

   424       }

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

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

   429       OutEdgeIt& operator++() {

   430 	graph->nextOut(*this);

   431 	return *this;

   432       }

   434     };

   437     class InEdgeIt : public Edge {

   438       friend class IterableBpUGraphExtender;

   439       const Graph* graph;

   440     public:

   442       InEdgeIt() { }

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

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

   447 	: graph(&_graph) {

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

   449       }

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

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

   454       InEdgeIt& operator++() {

   455 	graph->nextIn(*this);

   456 	return *this;

   457       }

   459     };

   461     /// \brief Base node of the iterator

   462     ///

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

   464     Node baseNode(const OutEdgeIt &e) const {

   465       return Parent::source((Edge&)e);

   466     }

   467     /// \brief Running node of the iterator

   468     ///

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

   470     /// iterator

   471     Node runningNode(const OutEdgeIt &e) const {

   472       return Parent::target((Edge&)e);

   473     }

   475     /// \brief Base node of the iterator

   476     ///

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

   478     Node baseNode(const InEdgeIt &e) const {

   479       return Parent::target((Edge&)e);

   480     }

   481     /// \brief Running node of the iterator

   482     ///

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

   484     /// iterator

   485     Node runningNode(const InEdgeIt &e) const {

   486       return Parent::source((Edge&)e);

   487     }

   489     class IncEdgeIt : public Parent::UEdge {

   490       friend class IterableBpUGraphExtender;

   491       const Graph* graph;

   492       bool direction;

   493     public:

   495       IncEdgeIt() { }

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

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

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

   501       }

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

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

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

   506       }

   508       IncEdgeIt& operator++() {

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

   510 	return *this;

   511       }

   512     };

   515     /// Base node of the iterator

   516     ///

   517     /// Returns the base node of the iterator

   518     Node baseNode(const IncEdgeIt &e) const {

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

   520     }

   522     /// Running node of the iterator

   523     ///

   524     /// Returns the running node of the iterator

   525     Node runningNode(const IncEdgeIt &e) const {

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

   527     }

   529   };

   531 }

   533 #endif // LEMON_GRAPH_EXTENDER_H

author	deba
	Tue, 14 Feb 2006 10:41:16 +0000
changeset 1968	78e6e2d1fd96
parent 1934	272fa8a0b680
permissions	-rw-r--r--