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