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 forward;

   220       friend class IterableUndirGraphExtender;

   221       template <typename G>

   222       friend class UndirGraphExtender;

   223     public:

   225       IncEdgeIt() { }

   227       IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }

   229       IncEdgeIt(const Graph& _graph, const Node &n)

   230 	: graph(&_graph)

   231       {

   232 	_graph._dirFirstOut(*this, n);

   233       }

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

   236 	: graph(&_graph), UndirEdge(ue)

   237       {

   238 	forward = (_graph.source(ue) == n);

   239       }

   241       IncEdgeIt& operator++() {

   242 	graph->_dirNextOut(*this);

   243 	return *this;

   244       }

   245     };

   247     using Parent::baseNode;

   248     using Parent::runningNode;

   250     /// Base node of the iterator

   251     ///

   252     /// Returns the base node of the iterator

   253     Node baseNode(const IncEdgeIt &e) const {

   254       return _dirSource(e);

   255     }

   256     /// Running node of the iterator

   257     ///

   258     /// Returns the running node of the iterator

   259     Node runningNode(const IncEdgeIt &e) const {

   260       return _dirTarget(e);

   261     }

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

   264     ///

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

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

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

   268 	return Parent::target(e);

   269       } else {

   270 	return Parent::source(e);

   271       }

   272     }

   274   };

   275 }

   277 #endif // LEMON_GRAPH_EXTENDER_H

author	alpar
	Tue, 16 Aug 2005 16:44:57 +0000
changeset 1630	f67737f5727a
parent 1564	16d316199cf6
child 1704	467d7927a901
permissions	-rw-r--r--