src/lemon/iterable_graph_extender.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1030 c8a41699e613
child 1230 daf41fe81728
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
klao@946
     1
// -*- c++ -*-
klao@946
     2
#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
klao@946
     3
#define LEMON_ITERABLE_GRAPH_EXTENDER_H
klao@946
     4
klao@946
     5
#include <lemon/invalid.h>
klao@946
     6
klao@946
     7
namespace lemon {
klao@946
     8
  
klao@946
     9
  template <typename _Base>
klao@946
    10
  class IterableGraphExtender : public _Base {
klao@962
    11
  public:
klao@946
    12
klao@946
    13
    typedef _Base Parent;
klao@946
    14
    typedef IterableGraphExtender<_Base> Graph;
klao@946
    15
klao@946
    16
    typedef typename Parent::Node Node;
klao@946
    17
    typedef typename Parent::Edge Edge;
klao@946
    18
klao@946
    19
klao@946
    20
    class NodeIt : public Node { 
klao@946
    21
      const Graph* graph;
klao@946
    22
    public:
klao@946
    23
klao@946
    24
      NodeIt() {}
klao@946
    25
klao@946
    26
      NodeIt(Invalid i) : Node(i) { }
klao@946
    27
klao@962
    28
      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
klao@946
    29
	_graph.first(*static_cast<Node*>(this));
klao@946
    30
      }
klao@946
    31
klao@946
    32
      NodeIt(const Graph& _graph, const Node& node) 
klao@946
    33
	: Node(node), graph(&_graph) {}
klao@946
    34
klao@946
    35
      NodeIt& operator++() { 
klao@946
    36
	graph->next(*this);
klao@946
    37
	return *this; 
klao@946
    38
      }
klao@946
    39
klao@946
    40
    };
klao@946
    41
klao@946
    42
klao@946
    43
    class EdgeIt : public Edge { 
klao@946
    44
      const Graph* graph;
klao@946
    45
    public:
klao@946
    46
klao@946
    47
      EdgeIt() { }
klao@946
    48
klao@946
    49
      EdgeIt(Invalid i) : Edge(i) { }
klao@946
    50
klao@962
    51
      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
klao@946
    52
	_graph.first(*static_cast<Edge*>(this));
klao@946
    53
      }
klao@946
    54
klao@946
    55
      EdgeIt(const Graph& _graph, const Edge& e) : 
klao@946
    56
	Edge(e), graph(&_graph) { }
klao@946
    57
klao@946
    58
      EdgeIt& operator++() { 
klao@946
    59
	graph->next(*this);
klao@946
    60
	return *this; 
klao@946
    61
      }
klao@946
    62
klao@946
    63
    };
klao@946
    64
klao@946
    65
klao@946
    66
    class OutEdgeIt : public Edge { 
klao@946
    67
      const Graph* graph;
klao@946
    68
    public:
klao@946
    69
klao@946
    70
      OutEdgeIt() { }
klao@946
    71
klao@946
    72
      OutEdgeIt(Invalid i) : Edge(i) { }
klao@946
    73
klao@946
    74
      OutEdgeIt(const Graph& _graph, const Node& node) 
klao@962
    75
	: graph(&_graph) {
klao@946
    76
	_graph.firstOut(*this, node);
klao@946
    77
      }
klao@946
    78
klao@946
    79
      OutEdgeIt(const Graph& _graph, const Edge& edge) 
klao@946
    80
	: Edge(edge), graph(&_graph) {}
klao@946
    81
klao@946
    82
      OutEdgeIt& operator++() { 
klao@946
    83
	graph->nextOut(*this);
klao@946
    84
	return *this; 
klao@946
    85
      }
klao@946
    86
klao@946
    87
    };
klao@946
    88
klao@946
    89
klao@946
    90
    class InEdgeIt : public Edge { 
klao@946
    91
      const Graph* graph;
klao@946
    92
    public:
klao@946
    93
klao@946
    94
      InEdgeIt() { }
klao@946
    95
klao@946
    96
      InEdgeIt(Invalid i) : Edge(i) { }
klao@946
    97
klao@946
    98
      InEdgeIt(const Graph& _graph, const Node& node) 
klao@962
    99
	: graph(&_graph) {
klao@946
   100
	_graph.firstIn(*this, node);
klao@946
   101
      }
klao@946
   102
klao@946
   103
      InEdgeIt(const Graph& _graph, const Edge& edge) : 
klao@946
   104
	Edge(edge), graph(&_graph) {}
klao@946
   105
klao@946
   106
      InEdgeIt& operator++() { 
klao@946
   107
	graph->nextIn(*this);
klao@946
   108
	return *this; 
klao@946
   109
      }
klao@946
   110
klao@946
   111
    };
klao@946
   112
klao@1158
   113
    /// Base node of the iterator
klao@1158
   114
    ///
klao@1158
   115
    /// Returns the base node (ie. the source in this case) of the iterator
klao@1158
   116
    ///
klao@1158
   117
    /// \todo Document in the concept!
klao@1158
   118
    Node baseNode(const OutEdgeIt &e) const {
klao@1158
   119
      return source(e);
klao@1158
   120
    }
klao@1158
   121
    /// Running node of the iterator
klao@1158
   122
    ///
klao@1158
   123
    /// Returns the running node (ie. the target in this case) of the
klao@1158
   124
    /// iterator
klao@1158
   125
    ///
klao@1158
   126
    /// \todo Document in the concept!
klao@1158
   127
    Node runningNode(const OutEdgeIt &e) const {
klao@1158
   128
      return target(e);
klao@1158
   129
    }
klao@1158
   130
klao@1158
   131
    /// Base node of the iterator
klao@1158
   132
    ///
klao@1158
   133
    /// Returns the base node (ie. the target in this case) of the iterator
klao@1158
   134
    ///
klao@1158
   135
    /// \todo Document in the concept!
klao@1158
   136
    Node baseNode(const InEdgeIt &e) const {
klao@1158
   137
      return target(e);
klao@1158
   138
    }
klao@1158
   139
    /// Running node of the iterator
klao@1158
   140
    ///
klao@1158
   141
    /// Returns the running node (ie. the source in this case) of the
klao@1158
   142
    /// iterator
klao@1158
   143
    ///
klao@1158
   144
    /// \todo Document in the concept!
klao@1158
   145
    Node runningNode(const InEdgeIt &e) const {
klao@1158
   146
      return source(e);
klao@1158
   147
    }
klao@1158
   148
klao@946
   149
    using Parent::first;
klao@946
   150
klao@946
   151
  private:
klao@946
   152
klao@946
   153
    /// \todo When (and if) we change the iterators concept to use operator*,
klao@946
   154
    /// then the following shadowed methods will become superfluous.
klao@946
   155
    /// But for now these are important safety measures.
klao@946
   156
klao@946
   157
    void first(NodeIt &) const;
klao@946
   158
    void first(EdgeIt &) const;
klao@946
   159
    void first(OutEdgeIt &) const;
klao@946
   160
    void first(InEdgeIt &) const;
klao@946
   161
klao@946
   162
  };
klao@1158
   163
klao@1158
   164
klao@1158
   165
klao@1158
   166
klao@1158
   167
klao@946
   168
  
klao@962
   169
  template <typename _Base>
klao@962
   170
  class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
klao@962
   171
  public:
klao@962
   172
klao@962
   173
    typedef IterableGraphExtender<_Base> Parent;
klao@962
   174
    typedef IterableUndirGraphExtender<_Base> Graph;
klao@1021
   175
    typedef typename Parent::Node Node;
klao@962
   176
klao@962
   177
    typedef typename Parent::UndirEdge UndirEdge;
klao@962
   178
klao@962
   179
    class UndirEdgeIt : public UndirEdge { 
klao@962
   180
      const Graph* graph;
klao@962
   181
    public:
klao@962
   182
klao@962
   183
      UndirEdgeIt() { }
klao@962
   184
klao@962
   185
      UndirEdgeIt(Invalid i) : UndirEdge(i) { }
klao@962
   186
klao@962
   187
      explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
klao@962
   188
	_graph.first(*static_cast<UndirEdge*>(this));
klao@962
   189
      }
klao@962
   190
klao@962
   191
      UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : 
klao@962
   192
	UndirEdge(e), graph(&_graph) { }
klao@962
   193
klao@962
   194
      UndirEdgeIt& operator++() { 
klao@962
   195
	graph->next(*this);
klao@962
   196
	return *this; 
klao@962
   197
      }
klao@962
   198
klao@962
   199
    };
klao@962
   200
klao@1030
   201
    class IncEdgeIt : public UndirEdge { 
klao@1021
   202
      const Graph* graph;
klao@1021
   203
      bool forward;
klao@1021
   204
      friend class IterableUndirGraphExtender;
klao@1021
   205
      template <typename G>
klao@1021
   206
      friend class UndirGraphExtender;
klao@1021
   207
    public:
klao@1021
   208
klao@1030
   209
      IncEdgeIt() { }
klao@1021
   210
klao@1030
   211
      IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
klao@1021
   212
klao@1158
   213
      IncEdgeIt(const Graph& _graph, const Node &n)
klao@1021
   214
	: graph(&_graph)
klao@1021
   215
      {
klao@1021
   216
	_graph._dirFirstOut(*this, n);
klao@1021
   217
      }
klao@1021
   218
klao@1158
   219
      IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
klao@1158
   220
	: graph(&_graph), UndirEdge(ue)
klao@1158
   221
      {
klao@1158
   222
	forward = (_graph.source(ue) == n);
klao@1158
   223
      }
klao@1021
   224
klao@1030
   225
      IncEdgeIt& operator++() {
klao@1021
   226
	graph->_dirNextOut(*this);
klao@1021
   227
	return *this; 
klao@1021
   228
      }
klao@1021
   229
    };
klao@1021
   230
klao@1158
   231
    using Parent::baseNode;
klao@1158
   232
    using Parent::runningNode;
klao@1158
   233
klao@1158
   234
    /// Base node of the iterator
klao@1158
   235
    ///
klao@1158
   236
    /// Returns the base node of the iterator
klao@1158
   237
    Node baseNode(const IncEdgeIt &e) const {
klao@1021
   238
      return _dirSource(e);
klao@1021
   239
    }
klao@1158
   240
    /// Running node of the iterator
klao@1158
   241
    ///
klao@1158
   242
    /// Returns the running node of the iterator
klao@1158
   243
    Node runningNode(const IncEdgeIt &e) const {
klao@1021
   244
      return _dirTarget(e);
klao@1021
   245
    }
klao@1021
   246
klao@962
   247
  };
klao@946
   248
}
klao@946
   249
klao@946
   250
#endif // LEMON_GRAPH_EXTENDER_H