lemon-0.x: lemon/bits/iterable_graph

     1 // -*- c++ -*-

     2 #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H

     3 #define LEMON_ITERABLE_GRAPH_EXTENDER_H

     5 #include <lemon/invalid.h>

     6 #include <lemon/utility.h>

     8 namespace lemon {

    10   template <typename _Base>

    11   class IterableGraphExtender : public _Base {

    12   public:

    14     /// Indicates that the graph is undirected.

    16     ///\todo Better name?

    17     ///

    18     ///\bug Should it be here?

    19     typedef False UndirTag;

    21     typedef _Base Parent;

    22     typedef IterableGraphExtender<_Base> Graph;

    24     typedef typename Parent::Node Node;

    25     typedef typename Parent::Edge Edge;

    28     class NodeIt : public Node {

    29       const Graph* graph;

    30     public:

    32       NodeIt() {}

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

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

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

    38       }

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

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

    43       NodeIt& operator++() {

    44 	graph->next(*this);

    45 	return *this;

    46       }

    48     };

    51     class EdgeIt : public Edge {

    52       const Graph* graph;

    53     public:

    55       EdgeIt() { }

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

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

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

    61       }

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

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

    66       EdgeIt& operator++() {

    67 	graph->next(*this);

    68 	return *this;

    69       }

    71     };

    74     class OutEdgeIt : public Edge {

    75       const Graph* graph;

    76     public:

    78       OutEdgeIt() { }

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

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

    83 	: graph(&_graph) {

    84 	_graph.firstOut(*this, node);

    85       }

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

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

    90       OutEdgeIt& operator++() {

    91 	graph->nextOut(*this);

    92 	return *this;

    93       }

    95     };

    98     class InEdgeIt : public Edge {

    99       const Graph* graph;

   100     public:

   102       InEdgeIt() { }

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

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

   107 	: graph(&_graph) {

   108 	_graph.firstIn(*this, node);

   109       }

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

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

   114       InEdgeIt& operator++() {

   115 	graph->nextIn(*this);

   116 	return *this;

   117       }

   119     };

   121     /// \brief Base node of the iterator

   122     ///

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

   124     Node baseNode(const OutEdgeIt &e) const {

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

   126     }

   127     /// \brief Running node of the iterator

   128     ///

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

   130     /// iterator

   131     Node runningNode(const OutEdgeIt &e) const {

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

   133     }

   135     /// \brief Base node of the iterator

   136     ///

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

   138     Node baseNode(const InEdgeIt &e) const {

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

   140     }

   141     /// \brief Running node of the iterator

   142     ///

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

   144     /// iterator

   145     Node runningNode(const InEdgeIt &e) const {

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

   147     }

   149     using Parent::first;

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

   152     ///

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

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

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

   156 	return Parent::target(e);

   157       } else {

   158 	return Parent::source(e);

   159       }

   160     }

   162   private:

   164     // void first(NodeIt &) const;

   165     // void first(EdgeIt &) const;

   166     // void first(OutEdgeIt &) const;

   167     // void first(InEdgeIt &) const;

   169   };

   176   template <typename _Base>

   177   class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {

   178   public:

   180     /// Indicates that the graph is undirected.

   182     ///\todo Better name?

   183     ///

   184     ///\bug Should it be here?

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

   186     ///correctly.

   187     typedef True UndirTag;

   189     typedef IterableGraphExtender<_Base> Parent;

   190     typedef IterableUndirGraphExtender<_Base> Graph;

   191     typedef typename Parent::Node Node;

   192     typedef typename Parent::Edge Edge;

   193     typedef typename Parent::UndirEdge UndirEdge;

   195     class UndirEdgeIt : public Parent::UndirEdge {

   196       const Graph* graph;

   197     public:

   199       UndirEdgeIt() { }

   201       UndirEdgeIt(Invalid i) : UndirEdge(i) { }

   203       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {

   204 	_graph.first(*static_cast<UndirEdge*>(this));

   205       }

   207       UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :

   208 	UndirEdge(e), graph(&_graph) { }

   210       UndirEdgeIt& operator++() {

   211 	graph->next(*this);

   212 	return *this;

   213       }

   215     };

   217     class IncEdgeIt : public Parent::UndirEdge {

   218       const Graph* graph;

   219       bool direction;

   220       friend class IterableUndirGraphExtender;

   221     public:

   223       IncEdgeIt() { }

   225       IncEdgeIt(Invalid i) : UndirEdge(i), direction(false) { }

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

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

   229       }

   231       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)

   232 	: graph(&_graph), UndirEdge(ue) {

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

   234       }

   236       IncEdgeIt& operator++() {

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

   238 	return *this;

   239       }

   240     };

   242     using Parent::baseNode;

   243     using Parent::runningNode;

   245     /// Base node of the iterator

   246     ///

   247     /// Returns the base node of the iterator

   248     Node baseNode(const IncEdgeIt &e) const {

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

   250     }

   251     /// Running node of the iterator

   252     ///

   253     /// Returns the running node of the iterator

   254     Node runningNode(const IncEdgeIt &e) const {

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

   256     }

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

   259     ///

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

   261     Node oppositeNode(const Node& n, const UndirEdge& e) const {

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

   263 	return Parent::target(e);

   264       } else {

   265 	return Parent::source(e);

   266       }

   267     }

   269   };

   272   template <typename _Base>

   273   class IterableUndirBipartiteGraphExtender : public _Base {

   274   public:

   275     typedef _Base Parent;

   276     typedef IterableUndirBipartiteGraphExtender Graph;

   278     typedef typename Parent::Node Node;

   279     typedef typename Parent::UpperNode UpperNode;

   280     typedef typename Parent::LowerNode LowerNode;

   281     typedef typename Parent::Edge Edge;

   282     typedef typename Parent::UndirEdge UndirEdge;

   284     class NodeIt : public Node {

   285       const Graph* graph;

   286     public:

   288       NodeIt() { }

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

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

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

   294       }

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

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

   299       NodeIt& operator++() {

   300 	graph->next(*this);

   301 	return *this;

   302       }

   304     };

   306     class UpperNodeIt : public Node {

   307       friend class IterableUndirBipartiteGraphExtender;

   308       const Graph* graph;

   309     public:

   311       UpperNodeIt() { }

   313       UpperNodeIt(Invalid i) : Node(INVALID) { }

   315       explicit UpperNodeIt(const Graph& _graph) : graph(&_graph) {

   316 	graph->firstUpper(static_cast<Node&>(*this));

   317       }

   319       UpperNodeIt(const Graph& _graph, const Node& node)

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

   322       UpperNodeIt& operator++() {

   323 	graph->nextUpper(*this);

   324 	return *this;

   325       }

   326     };

   328     class LowerNodeIt : public Node {

   329       friend class IterableUndirBipartiteGraphExtender;

   330       const Graph* graph;

   331     public:

   333       LowerNodeIt() { }

   335       LowerNodeIt(Invalid i) : Node(INVALID) { }

   337       explicit LowerNodeIt(const Graph& _graph) : graph(&_graph) {

   338 	graph->firstLower(static_cast<Node&>(*this));

   339       }

   341       LowerNodeIt(const Graph& _graph, const Node& node)

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

   344       LowerNodeIt& operator++() {

   345 	graph->nextLower(*this);

   346 	return *this;

   347       }

   348     };

   350     class EdgeIt : public Edge {

   351       friend class IterableUndirBipartiteGraphExtender;

   352       const Graph* graph;

   353     public:

   355       EdgeIt() { }

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

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

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

   361       }

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

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

   366       EdgeIt& operator++() {

   367 	graph->next(*this);

   368 	return *this;

   369       }

   371     };

   373     class UndirEdgeIt : public UndirEdge {

   374       friend class IterableUndirBipartiteGraphExtender;

   375       const Graph* graph;

   376     public:

   378       UndirEdgeIt() { }

   380       UndirEdgeIt(Invalid i) : UndirEdge(INVALID) { }

   382       explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {

   383 	graph->first(static_cast<UndirEdge&>(*this));

   384       }

   386       UndirEdgeIt(const Graph& _graph, const UndirEdge& edge)

   387 	: UndirEdge(edge), graph(&_graph) { }

   389       UndirEdgeIt& operator++() {

   390 	graph->next(*this);

   391 	return *this;

   392       }

   393     };

   395     class OutEdgeIt : public Edge {

   396       friend class IterableUndirBipartiteGraphExtender;

   397       const Graph* graph;

   398     public:

   400       OutEdgeIt() { }

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

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

   405 	: graph(&_graph) {

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

   407       }

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

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

   412       OutEdgeIt& operator++() {

   413 	graph->nextOut(*this);

   414 	return *this;

   415       }

   417     };

   420     class InEdgeIt : public Edge {

   421       friend class IterableUndirBipartiteGraphExtender;

   422       const Graph* graph;

   423     public:

   425       InEdgeIt() { }

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

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

   430 	: graph(&_graph) {

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

   432       }

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

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

   437       InEdgeIt& operator++() {

   438 	graph->nextIn(*this);

   439 	return *this;

   440       }

   442     };

   444     /// \brief Base node of the iterator

   445     ///

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

   447     Node baseNode(const OutEdgeIt &e) const {

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

   449     }

   450     /// \brief Running node of the iterator

   451     ///

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

   453     /// iterator

   454     Node runningNode(const OutEdgeIt &e) const {

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

   456     }

   458     /// \brief Base node of the iterator

   459     ///

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

   461     Node baseNode(const InEdgeIt &e) const {

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

   463     }

   464     /// \brief Running node of the iterator

   465     ///

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

   467     /// iterator

   468     Node runningNode(const InEdgeIt &e) const {

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

   470     }

   472     class IncEdgeIt : public Parent::UndirEdge {

   473       friend class IterableUndirBipartiteGraphExtender;

   474       const Graph* graph;

   475       bool direction;

   476     public:

   478       IncEdgeIt() { }

   480       IncEdgeIt(Invalid i) : UndirEdge(i), direction(true) { }

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

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

   484       }

   486       IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)

   487 	: graph(&_graph), UndirEdge(ue) {

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

   489       }

   491       IncEdgeIt& operator++() {

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

   493 	return *this;

   494       }

   495     };

   498     /// Base node of the iterator

   499     ///

   500     /// Returns the base node of the iterator

   501     Node baseNode(const IncEdgeIt &e) const {

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

   503     }

   505     /// Running node of the iterator

   506     ///

   507     /// Returns the running node of the iterator

   508     Node runningNode(const IncEdgeIt &e) const {

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

   510     }

   512   };

   514 }

   516 #endif // LEMON_GRAPH_EXTENDER_H

author	alpar
	Thu, 26 Jan 2006 06:44:22 +0000
changeset 1908	e225719bde6b
parent 1704	467d7927a901
child 1909	2d806130e700
permissions	-rw-r--r--