Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
1.1 --- a/lemon/Makefile.am Mon Apr 03 09:24:38 2006 +0000
1.2 +++ b/lemon/Makefile.am Mon Apr 03 09:45:23 2006 +0000
1.3 @@ -27,6 +27,7 @@
1.4 bfs.h \
1.5 dfs.h \
1.6 bin_heap.h \
1.7 + bpugraph_adaptor.h \
1.8 color.h \
1.9 config.h \
1.10 counter.h \
2.1 --- a/lemon/bits/array_map.h Mon Apr 03 09:24:38 2006 +0000
2.2 +++ b/lemon/bits/array_map.h Mon Apr 03 09:45:23 2006 +0000
2.3 @@ -23,6 +23,8 @@
2.4
2.5 #include <lemon/bits/traits.h>
2.6 #include <lemon/bits/alteration_notifier.h>
2.7 +#include <lemon/concept_check.h>
2.8 +#include <lemon/concept/maps.h>
2.9
2.10 /// \ingroup graphbits
2.11 /// \file
2.12 @@ -119,6 +121,35 @@
2.13 }
2.14 }
2.15
2.16 + /// \brief Assign operator.
2.17 + ///
2.18 + /// This operator assigns for each item in the map the
2.19 + /// value mapped to the same item in the copied map.
2.20 + /// The parameter map should be indiced with the same
2.21 + /// itemset because this assign operator does not change
2.22 + /// the container of the map.
2.23 + ArrayMap& operator=(const ArrayMap& cmap) {
2.24 + return operator=<ArrayMap>(cmap);
2.25 + }
2.26 +
2.27 +
2.28 + /// \brief Template assign operator.
2.29 + ///
2.30 + /// The given parameter should be conform to the ReadMap
2.31 + /// concecpt and could be indiced by the current item set of
2.32 + /// the NodeMap. In this case the value for each item
2.33 + /// is assigned by the value of the given ReadMap.
2.34 + template <typename CMap>
2.35 + ArrayMap& operator=(const CMap& cmap) {
2.36 + checkConcept<concept::ReadMap<Key, _Value>, CMap>();
2.37 + const typename Parent::Notifier* notifier = Parent::getNotifier();
2.38 + Item it;
2.39 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
2.40 + set(it, cmap[it]);
2.41 + }
2.42 + return *this;
2.43 + }
2.44 +
2.45 /// \brief The destructor of the map.
2.46 ///
2.47 /// The destructor of the map.
2.48 @@ -129,10 +160,6 @@
2.49 }
2.50 }
2.51
2.52 - private:
2.53 -
2.54 - ArrayMap& operator=(const ArrayMap&);
2.55 -
2.56 protected:
2.57
2.58 using Parent::attach;
3.1 --- a/lemon/bits/base_extender.h Mon Apr 03 09:24:38 2006 +0000
3.2 +++ b/lemon/bits/base_extender.h Mon Apr 03 09:45:23 2006 +0000
3.3 @@ -466,6 +466,15 @@
3.4 Edge direct(const UEdge& edge, bool direction) const {
3.5 return Edge(edge, direction);
3.6 }
3.7 +
3.8 + int edgeNum() const {
3.9 + return 2 * Parent::edgeNum();
3.10 + }
3.11 +
3.12 + int uEdgeNum() const {
3.13 + return Parent::edgeNum();
3.14 + }
3.15 +
3.16 };
3.17
3.18 }
4.1 --- a/lemon/bits/default_map.h Mon Apr 03 09:24:38 2006 +0000
4.2 +++ b/lemon/bits/default_map.h Mon Apr 03 09:45:23 2006 +0000
4.3 @@ -163,6 +163,16 @@
4.4 DefaultMap(const Graph& graph, const Value& value)
4.5 : Parent(graph, value) {}
4.6
4.7 + DefaultMap& operator=(const DefaultMap& cmap) {
4.8 + return operator=<DefaultMap>(cmap);
4.9 + }
4.10 +
4.11 + template <typename CMap>
4.12 + DefaultMap& operator=(const CMap& cmap) {
4.13 + Parent::operator=(cmap);
4.14 + return *this;
4.15 + }
4.16 +
4.17 };
4.18
4.19 }
5.1 --- a/lemon/bits/edge_set_extender.h Mon Apr 03 09:24:38 2006 +0000
5.2 +++ b/lemon/bits/edge_set_extender.h Mon Apr 03 09:45:23 2006 +0000
5.3 @@ -101,7 +101,7 @@
5.4 NodeIt(Invalid i) : Node(i) { }
5.5
5.6 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
5.7 - _graph.first(*static_cast<Node*>(this));
5.8 + _graph.first(static_cast<Node&>(*this));
5.9 }
5.10
5.11 NodeIt(const Graph& _graph, const Node& node)
5.12 @@ -124,7 +124,7 @@
5.13 EdgeIt(Invalid i) : Edge(i) { }
5.14
5.15 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
5.16 - _graph.first(*static_cast<Edge*>(this));
5.17 + _graph.first(static_cast<Edge&>(*this));
5.18 }
5.19
5.20 EdgeIt(const Graph& _graph, const Edge& e) :
5.21 @@ -235,14 +235,10 @@
5.22
5.23 template <typename CMap>
5.24 EdgeMap& operator=(const CMap& cmap) {
5.25 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
5.26 - const typename Parent::Graph* graph = Parent::getGraph();
5.27 - Edge it;
5.28 - for (graph->first(it); it != INVALID; graph->next(it)) {
5.29 - Parent::set(it, cmap[it]);
5.30 - }
5.31 + Parent::operator=(cmap);
5.32 return *this;
5.33 }
5.34 +
5.35 };
5.36
5.37
5.38 @@ -364,7 +360,7 @@
5.39 NodeIt(Invalid i) : Node(i) { }
5.40
5.41 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
5.42 - _graph.first(*static_cast<Node*>(this));
5.43 + _graph.first(static_cast<Node&>(*this));
5.44 }
5.45
5.46 NodeIt(const Graph& _graph, const Node& node)
5.47 @@ -387,7 +383,7 @@
5.48 EdgeIt(Invalid i) : Edge(i) { }
5.49
5.50 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
5.51 - _graph.first(*static_cast<Edge*>(this));
5.52 + _graph.first(static_cast<Edge&>(*this));
5.53 }
5.54
5.55 EdgeIt(const Graph& _graph, const Edge& e) :
5.56 @@ -458,7 +454,7 @@
5.57 UEdgeIt(Invalid i) : UEdge(i) { }
5.58
5.59 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
5.60 - _graph.first(*static_cast<UEdge*>(this));
5.61 + _graph.first(static_cast<UEdge&>(*this));
5.62 }
5.63
5.64 UEdgeIt(const Graph& _graph, const UEdge& e) :
5.65 @@ -556,14 +552,10 @@
5.66
5.67 template <typename CMap>
5.68 EdgeMap& operator=(const CMap& cmap) {
5.69 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
5.70 - const typename Parent::Graph* graph = Parent::getGraph();
5.71 - Edge it;
5.72 - for (graph->first(it); it != INVALID; graph->next(it)) {
5.73 - Parent::set(it, cmap[it]);
5.74 - }
5.75 + Parent::operator=(cmap);
5.76 return *this;
5.77 }
5.78 +
5.79 };
5.80
5.81
5.82 @@ -576,6 +568,7 @@
5.83
5.84 UEdgeMap(const Graph& _g)
5.85 : Parent(_g) {}
5.86 +
5.87 UEdgeMap(const Graph& _g, const _Value& _v)
5.88 : Parent(_g, _v) {}
5.89
5.90 @@ -585,14 +578,10 @@
5.91
5.92 template <typename CMap>
5.93 UEdgeMap& operator=(const CMap& cmap) {
5.94 - checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
5.95 - const typename Parent::Graph* graph = Parent::getGraph();
5.96 - UEdge it;
5.97 - for (graph->first(it); it != INVALID; graph->next(it)) {
5.98 - Parent::set(it, cmap[it]);
5.99 - }
5.100 + Parent::operator=(cmap);
5.101 return *this;
5.102 }
5.103 +
5.104 };
5.105
5.106
6.1 --- a/lemon/bits/graph_adaptor_extender.h Mon Apr 03 09:24:38 2006 +0000
6.2 +++ b/lemon/bits/graph_adaptor_extender.h Mon Apr 03 09:45:23 2006 +0000
6.3 @@ -33,12 +33,13 @@
6.4 /// \ingroup graphbits
6.5 ///
6.6 /// \brief Extender for the GraphAdaptors
6.7 - template <typename Base>
6.8 - class GraphAdaptorExtender : public Base {
6.9 + template <typename _Graph>
6.10 + class GraphAdaptorExtender : public _Graph {
6.11 public:
6.12
6.13 - typedef Base Parent;
6.14 - typedef GraphAdaptorExtender Graph;
6.15 + typedef _Graph Parent;
6.16 + typedef _Graph Graph;
6.17 + typedef GraphAdaptorExtender Adaptor;
6.18
6.19 // Base extensions
6.20
6.21 @@ -71,18 +72,18 @@
6.22 }
6.23
6.24 class NodeIt : public Node {
6.25 - const Graph* graph;
6.26 + const Adaptor* graph;
6.27 public:
6.28
6.29 NodeIt() {}
6.30
6.31 NodeIt(Invalid i) : Node(i) { }
6.32
6.33 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
6.34 - _graph.first(*static_cast<Node*>(this));
6.35 + explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
6.36 + _graph.first(static_cast<Node&>(*this));
6.37 }
6.38
6.39 - NodeIt(const Graph& _graph, const Node& node)
6.40 + NodeIt(const Adaptor& _graph, const Node& node)
6.41 : Node(node), graph(&_graph) {}
6.42
6.43 NodeIt& operator++() {
6.44 @@ -94,18 +95,18 @@
6.45
6.46
6.47 class EdgeIt : public Edge {
6.48 - const Graph* graph;
6.49 + const Adaptor* graph;
6.50 public:
6.51
6.52 EdgeIt() { }
6.53
6.54 EdgeIt(Invalid i) : Edge(i) { }
6.55
6.56 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
6.57 - _graph.first(*static_cast<Edge*>(this));
6.58 + explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
6.59 + _graph.first(static_cast<Edge&>(*this));
6.60 }
6.61
6.62 - EdgeIt(const Graph& _graph, const Edge& e) :
6.63 + EdgeIt(const Adaptor& _graph, const Edge& e) :
6.64 Edge(e), graph(&_graph) { }
6.65
6.66 EdgeIt& operator++() {
6.67 @@ -117,19 +118,19 @@
6.68
6.69
6.70 class OutEdgeIt : public Edge {
6.71 - const Graph* graph;
6.72 + const Adaptor* graph;
6.73 public:
6.74
6.75 OutEdgeIt() { }
6.76
6.77 OutEdgeIt(Invalid i) : Edge(i) { }
6.78
6.79 - OutEdgeIt(const Graph& _graph, const Node& node)
6.80 + OutEdgeIt(const Adaptor& _graph, const Node& node)
6.81 : graph(&_graph) {
6.82 _graph.firstOut(*this, node);
6.83 }
6.84
6.85 - OutEdgeIt(const Graph& _graph, const Edge& edge)
6.86 + OutEdgeIt(const Adaptor& _graph, const Edge& edge)
6.87 : Edge(edge), graph(&_graph) {}
6.88
6.89 OutEdgeIt& operator++() {
6.90 @@ -141,19 +142,19 @@
6.91
6.92
6.93 class InEdgeIt : public Edge {
6.94 - const Graph* graph;
6.95 + const Adaptor* graph;
6.96 public:
6.97
6.98 InEdgeIt() { }
6.99
6.100 InEdgeIt(Invalid i) : Edge(i) { }
6.101
6.102 - InEdgeIt(const Graph& _graph, const Node& node)
6.103 + InEdgeIt(const Adaptor& _graph, const Node& node)
6.104 : graph(&_graph) {
6.105 _graph.firstIn(*this, node);
6.106 }
6.107
6.108 - InEdgeIt(const Graph& _graph, const Edge& edge) :
6.109 + InEdgeIt(const Adaptor& _graph, const Edge& edge) :
6.110 Edge(edge), graph(&_graph) {}
6.111
6.112 InEdgeIt& operator++() {
6.113 @@ -197,12 +198,13 @@
6.114 /// \ingroup graphbits
6.115 ///
6.116 /// \brief Extender for the UGraphAdaptors
6.117 - template <typename Base>
6.118 - class UGraphAdaptorExtender : public Base {
6.119 + template <typename _UGraph>
6.120 + class UGraphAdaptorExtender : public _UGraph {
6.121 public:
6.122
6.123 - typedef Base Parent;
6.124 - typedef UGraphAdaptorExtender Graph;
6.125 + typedef _UGraph Parent;
6.126 + typedef _UGraph UGraph;
6.127 + typedef UGraphAdaptorExtender Adaptor;
6.128
6.129 typedef typename Parent::Node Node;
6.130 typedef typename Parent::Edge Edge;
6.131 @@ -254,18 +256,18 @@
6.132
6.133
6.134 class NodeIt : public Node {
6.135 - const Graph* graph;
6.136 + const Adaptor* graph;
6.137 public:
6.138
6.139 NodeIt() {}
6.140
6.141 NodeIt(Invalid i) : Node(i) { }
6.142
6.143 - explicit NodeIt(const Graph& _graph) : graph(&_graph) {
6.144 - _graph.first(*static_cast<Node*>(this));
6.145 + explicit NodeIt(const Adaptor& _graph) : graph(&_graph) {
6.146 + _graph.first(static_cast<Node&>(*this));
6.147 }
6.148
6.149 - NodeIt(const Graph& _graph, const Node& node)
6.150 + NodeIt(const Adaptor& _graph, const Node& node)
6.151 : Node(node), graph(&_graph) {}
6.152
6.153 NodeIt& operator++() {
6.154 @@ -277,18 +279,18 @@
6.155
6.156
6.157 class EdgeIt : public Edge {
6.158 - const Graph* graph;
6.159 + const Adaptor* graph;
6.160 public:
6.161
6.162 EdgeIt() { }
6.163
6.164 EdgeIt(Invalid i) : Edge(i) { }
6.165
6.166 - explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
6.167 - _graph.first(*static_cast<Edge*>(this));
6.168 + explicit EdgeIt(const Adaptor& _graph) : graph(&_graph) {
6.169 + _graph.first(static_cast<Edge&>(*this));
6.170 }
6.171
6.172 - EdgeIt(const Graph& _graph, const Edge& e) :
6.173 + EdgeIt(const Adaptor& _graph, const Edge& e) :
6.174 Edge(e), graph(&_graph) { }
6.175
6.176 EdgeIt& operator++() {
6.177 @@ -300,19 +302,19 @@
6.178
6.179
6.180 class OutEdgeIt : public Edge {
6.181 - const Graph* graph;
6.182 + const Adaptor* graph;
6.183 public:
6.184
6.185 OutEdgeIt() { }
6.186
6.187 OutEdgeIt(Invalid i) : Edge(i) { }
6.188
6.189 - OutEdgeIt(const Graph& _graph, const Node& node)
6.190 + OutEdgeIt(const Adaptor& _graph, const Node& node)
6.191 : graph(&_graph) {
6.192 _graph.firstOut(*this, node);
6.193 }
6.194
6.195 - OutEdgeIt(const Graph& _graph, const Edge& edge)
6.196 + OutEdgeIt(const Adaptor& _graph, const Edge& edge)
6.197 : Edge(edge), graph(&_graph) {}
6.198
6.199 OutEdgeIt& operator++() {
6.200 @@ -324,19 +326,19 @@
6.201
6.202
6.203 class InEdgeIt : public Edge {
6.204 - const Graph* graph;
6.205 + const Adaptor* graph;
6.206 public:
6.207
6.208 InEdgeIt() { }
6.209
6.210 InEdgeIt(Invalid i) : Edge(i) { }
6.211
6.212 - InEdgeIt(const Graph& _graph, const Node& node)
6.213 + InEdgeIt(const Adaptor& _graph, const Node& node)
6.214 : graph(&_graph) {
6.215 _graph.firstIn(*this, node);
6.216 }
6.217
6.218 - InEdgeIt(const Graph& _graph, const Edge& edge) :
6.219 + InEdgeIt(const Adaptor& _graph, const Edge& edge) :
6.220 Edge(edge), graph(&_graph) {}
6.221
6.222 InEdgeIt& operator++() {
6.223 @@ -347,18 +349,18 @@
6.224 };
6.225
6.226 class UEdgeIt : public Parent::UEdge {
6.227 - const Graph* graph;
6.228 + const Adaptor* graph;
6.229 public:
6.230
6.231 UEdgeIt() { }
6.232
6.233 UEdgeIt(Invalid i) : UEdge(i) { }
6.234
6.235 - explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
6.236 - _graph.first(*static_cast<UEdge*>(this));
6.237 + explicit UEdgeIt(const Adaptor& _graph) : graph(&_graph) {
6.238 + _graph.first(static_cast<UEdge&>(*this));
6.239 }
6.240
6.241 - UEdgeIt(const Graph& _graph, const UEdge& e) :
6.242 + UEdgeIt(const Adaptor& _graph, const UEdge& e) :
6.243 UEdge(e), graph(&_graph) { }
6.244
6.245 UEdgeIt& operator++() {
6.246 @@ -370,7 +372,7 @@
6.247
6.248 class IncEdgeIt : public Parent::UEdge {
6.249 friend class UGraphAdaptorExtender;
6.250 - const Graph* graph;
6.251 + const Adaptor* graph;
6.252 bool direction;
6.253 public:
6.254
6.255 @@ -378,11 +380,11 @@
6.256
6.257 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
6.258
6.259 - IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
6.260 + IncEdgeIt(const Adaptor& _graph, const Node &n) : graph(&_graph) {
6.261 _graph.firstInc(static_cast<UEdge&>(*this), direction, n);
6.262 }
6.263
6.264 - IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
6.265 + IncEdgeIt(const Adaptor& _graph, const UEdge &ue, const Node &n)
6.266 : graph(&_graph), UEdge(ue) {
6.267 direction = (_graph.source(ue) == n);
6.268 }
6.269 @@ -436,6 +438,290 @@
6.270
6.271 };
6.272
6.273 + /// \ingroup graphbits
6.274 + ///
6.275 + /// \brief Extender for the BpUGraphAdaptors
6.276 + template <typename Base>
6.277 + class BpUGraphAdaptorExtender : public Base {
6.278 + public:
6.279 + typedef Base Parent;
6.280 + typedef BpUGraphAdaptorExtender Graph;
6.281 +
6.282 + typedef typename Parent::Node Node;
6.283 + typedef typename Parent::BNode BNode;
6.284 + typedef typename Parent::ANode ANode;
6.285 + typedef typename Parent::Edge Edge;
6.286 + typedef typename Parent::UEdge UEdge;
6.287 +
6.288 + Node oppositeNode(const UEdge& edge, const Node& node) const {
6.289 + return source(edge) == node ?
6.290 + target(edge) : source(edge);
6.291 + }
6.292 +
6.293 +
6.294 + int maxId(Node) const {
6.295 + return Parent::maxNodeId();
6.296 + }
6.297 + int maxId(BNode) const {
6.298 + return Parent::maxBNodeId();
6.299 + }
6.300 + int maxId(ANode) const {
6.301 + return Parent::maxANodeId();
6.302 + }
6.303 + int maxId(Edge) const {
6.304 + return Parent::maxEdgeId();
6.305 + }
6.306 + int maxId(UEdge) const {
6.307 + return Parent::maxUEdgeId();
6.308 + }
6.309 +
6.310 +
6.311 + Node fromId(int id, Node) const {
6.312 + return Parent::nodeFromId(id);
6.313 + }
6.314 + ANode fromId(int id, ANode) const {
6.315 + return Parent::fromANodeId(id);
6.316 + }
6.317 + BNode fromId(int id, BNode) const {
6.318 + return Parent::fromBNodeId(id);
6.319 + }
6.320 + Edge fromId(int id, Edge) const {
6.321 + return Parent::edgeFromId(id);
6.322 + }
6.323 + UEdge fromId(int id, UEdge) const {
6.324 + return Parent::uEdgeFromId(id);
6.325 + }
6.326 +
6.327 + class NodeIt : public Node {
6.328 + const Graph* graph;
6.329 + public:
6.330 +
6.331 + NodeIt() { }
6.332 +
6.333 + NodeIt(Invalid i) : Node(INVALID) { }
6.334 +
6.335 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
6.336 + graph->first(static_cast<Node&>(*this));
6.337 + }
6.338 +
6.339 + NodeIt(const Graph& _graph, const Node& node)
6.340 + : Node(node), graph(&_graph) { }
6.341 +
6.342 + NodeIt& operator++() {
6.343 + graph->next(*this);
6.344 + return *this;
6.345 + }
6.346 +
6.347 + };
6.348 +
6.349 + class ANodeIt : public Node {
6.350 + friend class BpUGraphAdaptorExtender;
6.351 + const Graph* graph;
6.352 + public:
6.353 +
6.354 + ANodeIt() { }
6.355 +
6.356 + ANodeIt(Invalid i) : Node(INVALID) { }
6.357 +
6.358 + explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
6.359 + graph->firstANode(static_cast<Node&>(*this));
6.360 + }
6.361 +
6.362 + ANodeIt(const Graph& _graph, const Node& node)
6.363 + : Node(node), graph(&_graph) {}
6.364 +
6.365 + ANodeIt& operator++() {
6.366 + graph->nextANode(*this);
6.367 + return *this;
6.368 + }
6.369 + };
6.370 +
6.371 + class BNodeIt : public Node {
6.372 + friend class BpUGraphAdaptorExtender;
6.373 + const Graph* graph;
6.374 + public:
6.375 +
6.376 + BNodeIt() { }
6.377 +
6.378 + BNodeIt(Invalid i) : Node(INVALID) { }
6.379 +
6.380 + explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
6.381 + graph->firstBNode(static_cast<Node&>(*this));
6.382 + }
6.383 +
6.384 + BNodeIt(const Graph& _graph, const Node& node)
6.385 + : Node(node), graph(&_graph) {}
6.386 +
6.387 + BNodeIt& operator++() {
6.388 + graph->nextBNode(*this);
6.389 + return *this;
6.390 + }
6.391 + };
6.392 +
6.393 + class EdgeIt : public Edge {
6.394 + friend class BpUGraphAdaptorExtender;
6.395 + const Graph* graph;
6.396 + public:
6.397 +
6.398 + EdgeIt() { }
6.399 +
6.400 + EdgeIt(Invalid i) : Edge(INVALID) { }
6.401 +
6.402 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
6.403 + graph->first(static_cast<Edge&>(*this));
6.404 + }
6.405 +
6.406 + EdgeIt(const Graph& _graph, const Edge& edge)
6.407 + : Edge(edge), graph(&_graph) { }
6.408 +
6.409 + EdgeIt& operator++() {
6.410 + graph->next(*this);
6.411 + return *this;
6.412 + }
6.413 +
6.414 + };
6.415 +
6.416 + class UEdgeIt : public UEdge {
6.417 + friend class BpUGraphAdaptorExtender;
6.418 + const Graph* graph;
6.419 + public:
6.420 +
6.421 + UEdgeIt() { }
6.422 +
6.423 + UEdgeIt(Invalid i) : UEdge(INVALID) { }
6.424 +
6.425 + explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
6.426 + graph->first(static_cast<UEdge&>(*this));
6.427 + }
6.428 +
6.429 + UEdgeIt(const Graph& _graph, const UEdge& edge)
6.430 + : UEdge(edge), graph(&_graph) { }
6.431 +
6.432 + UEdgeIt& operator++() {
6.433 + graph->next(*this);
6.434 + return *this;
6.435 + }
6.436 + };
6.437 +
6.438 + class OutEdgeIt : public Edge {
6.439 + friend class BpUGraphAdaptorExtender;
6.440 + const Graph* graph;
6.441 + public:
6.442 +
6.443 + OutEdgeIt() { }
6.444 +
6.445 + OutEdgeIt(Invalid i) : Edge(i) { }
6.446 +
6.447 + OutEdgeIt(const Graph& _graph, const Node& node)
6.448 + : graph(&_graph) {
6.449 + graph->firstOut(*this, node);
6.450 + }
6.451 +
6.452 + OutEdgeIt(const Graph& _graph, const Edge& edge)
6.453 + : Edge(edge), graph(&_graph) {}
6.454 +
6.455 + OutEdgeIt& operator++() {
6.456 + graph->nextOut(*this);
6.457 + return *this;
6.458 + }
6.459 +
6.460 + };
6.461 +
6.462 +
6.463 + class InEdgeIt : public Edge {
6.464 + friend class BpUGraphAdaptorExtender;
6.465 + const Graph* graph;
6.466 + public:
6.467 +
6.468 + InEdgeIt() { }
6.469 +
6.470 + InEdgeIt(Invalid i) : Edge(i) { }
6.471 +
6.472 + InEdgeIt(const Graph& _graph, const Node& node)
6.473 + : graph(&_graph) {
6.474 + graph->firstIn(*this, node);
6.475 + }
6.476 +
6.477 + InEdgeIt(const Graph& _graph, const Edge& edge) :
6.478 + Edge(edge), graph(&_graph) {}
6.479 +
6.480 + InEdgeIt& operator++() {
6.481 + graph->nextIn(*this);
6.482 + return *this;
6.483 + }
6.484 +
6.485 + };
6.486 +
6.487 + /// \brief Base node of the iterator
6.488 + ///
6.489 + /// Returns the base node (ie. the source in this case) of the iterator
6.490 + Node baseNode(const OutEdgeIt &e) const {
6.491 + return Parent::source((Edge&)e);
6.492 + }
6.493 + /// \brief Running node of the iterator
6.494 + ///
6.495 + /// Returns the running node (ie. the target in this case) of the
6.496 + /// iterator
6.497 + Node runningNode(const OutEdgeIt &e) const {
6.498 + return Parent::target((Edge&)e);
6.499 + }
6.500 +
6.501 + /// \brief Base node of the iterator
6.502 + ///
6.503 + /// Returns the base node (ie. the target in this case) of the iterator
6.504 + Node baseNode(const InEdgeIt &e) const {
6.505 + return Parent::target((Edge&)e);
6.506 + }
6.507 + /// \brief Running node of the iterator
6.508 + ///
6.509 + /// Returns the running node (ie. the source in this case) of the
6.510 + /// iterator
6.511 + Node runningNode(const InEdgeIt &e) const {
6.512 + return Parent::source((Edge&)e);
6.513 + }
6.514 +
6.515 + class IncEdgeIt : public Parent::UEdge {
6.516 + friend class BpUGraphAdaptorExtender;
6.517 + const Graph* graph;
6.518 + bool direction;
6.519 + public:
6.520 +
6.521 + IncEdgeIt() { }
6.522 +
6.523 + IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
6.524 +
6.525 + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
6.526 + graph->firstInc(*this, direction, n);
6.527 + }
6.528 +
6.529 + IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
6.530 + : graph(&_graph), UEdge(ue) {
6.531 + direction = (graph->source(ue) == n);
6.532 + }
6.533 +
6.534 + IncEdgeIt& operator++() {
6.535 + graph->nextInc(*this, direction);
6.536 + return *this;
6.537 + }
6.538 + };
6.539 +
6.540 +
6.541 + /// Base node of the iterator
6.542 + ///
6.543 + /// Returns the base node of the iterator
6.544 + Node baseNode(const IncEdgeIt &e) const {
6.545 + return e.direction ? source(e) : target(e);
6.546 + }
6.547 +
6.548 + /// Running node of the iterator
6.549 + ///
6.550 + /// Returns the running node of the iterator
6.551 + Node runningNode(const IncEdgeIt &e) const {
6.552 + return e.direction ? target(e) : source(e);
6.553 + }
6.554 +
6.555 + };
6.556 +
6.557
6.558 }
6.559
7.1 --- a/lemon/bits/graph_extender.h Mon Apr 03 09:24:38 2006 +0000
7.2 +++ b/lemon/bits/graph_extender.h Mon Apr 03 09:45:23 2006 +0000
7.3 @@ -103,7 +103,7 @@
7.4 NodeIt(Invalid i) : Node(i) { }
7.5
7.6 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
7.7 - _graph.first(*static_cast<Node*>(this));
7.8 + _graph.first(static_cast<Node&>(*this));
7.9 }
7.10
7.11 NodeIt(const Graph& _graph, const Node& node)
7.12 @@ -126,7 +126,7 @@
7.13 EdgeIt(Invalid i) : Edge(i) { }
7.14
7.15 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
7.16 - _graph.first(*static_cast<Edge*>(this));
7.17 + _graph.first(static_cast<Edge&>(*this));
7.18 }
7.19
7.20 EdgeIt(const Graph& _graph, const Edge& e) :
7.21 @@ -232,21 +232,9 @@
7.22 return operator=<NodeMap>(cmap);
7.23 }
7.24
7.25 -
7.26 - /// \brief Template assign operator.
7.27 - ///
7.28 - /// The given parameter should be conform to the ReadMap
7.29 - /// concecpt and could be indiced by the current item set of
7.30 - /// the NodeMap. In this case the value for each item
7.31 - /// is assigned by the value of the given ReadMap.
7.32 template <typename CMap>
7.33 NodeMap& operator=(const CMap& cmap) {
7.34 - checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.35 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.36 - Node it;
7.37 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.38 - Parent::set(it, cmap[it]);
7.39 - }
7.40 + Parent::operator=(cmap);
7.41 return *this;
7.42 }
7.43
7.44 @@ -270,12 +258,7 @@
7.45
7.46 template <typename CMap>
7.47 EdgeMap& operator=(const CMap& cmap) {
7.48 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.49 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.50 - Edge it;
7.51 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.52 - Parent::set(it, cmap[it]);
7.53 - }
7.54 + Parent::operator=(cmap);
7.55 return *this;
7.56 }
7.57 };
7.58 @@ -431,7 +414,7 @@
7.59 NodeIt(Invalid i) : Node(i) { }
7.60
7.61 explicit NodeIt(const Graph& _graph) : graph(&_graph) {
7.62 - _graph.first(*static_cast<Node*>(this));
7.63 + _graph.first(static_cast<Node&>(*this));
7.64 }
7.65
7.66 NodeIt(const Graph& _graph, const Node& node)
7.67 @@ -454,7 +437,7 @@
7.68 EdgeIt(Invalid i) : Edge(i) { }
7.69
7.70 explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
7.71 - _graph.first(*static_cast<Edge*>(this));
7.72 + _graph.first(static_cast<Edge&>(*this));
7.73 }
7.74
7.75 EdgeIt(const Graph& _graph, const Edge& e) :
7.76 @@ -525,7 +508,7 @@
7.77 UEdgeIt(Invalid i) : UEdge(i) { }
7.78
7.79 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
7.80 - _graph.first(*static_cast<UEdge*>(this));
7.81 + _graph.first(static_cast<UEdge&>(*this));
7.82 }
7.83
7.84 UEdgeIt(const Graph& _graph, const UEdge& e) :
7.85 @@ -622,21 +605,9 @@
7.86 return operator=<NodeMap>(cmap);
7.87 }
7.88
7.89 -
7.90 - /// \brief Template assign operator.
7.91 - ///
7.92 - /// The given parameter should be conform to the ReadMap
7.93 - /// concecpt and could be indiced by the current item set of
7.94 - /// the NodeMap. In this case the value for each item
7.95 - /// is assigned by the value of the given ReadMap.
7.96 template <typename CMap>
7.97 NodeMap& operator=(const CMap& cmap) {
7.98 - checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.99 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.100 - Node it;
7.101 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.102 - Parent::set(it, cmap[it]);
7.103 - }
7.104 + Parent::operator=(cmap);
7.105 return *this;
7.106 }
7.107
7.108 @@ -660,12 +631,7 @@
7.109
7.110 template <typename CMap>
7.111 EdgeMap& operator=(const CMap& cmap) {
7.112 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.113 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.114 - Edge it;
7.115 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.116 - Parent::set(it, cmap[it]);
7.117 - }
7.118 + Parent::operator=(cmap);
7.119 return *this;
7.120 }
7.121 };
7.122 @@ -680,6 +646,7 @@
7.123
7.124 UEdgeMap(const Graph& graph)
7.125 : Parent(graph) {}
7.126 +
7.127 UEdgeMap(const Graph& graph, const _Value& value)
7.128 : Parent(graph, value) {}
7.129
7.130 @@ -689,14 +656,10 @@
7.131
7.132 template <typename CMap>
7.133 UEdgeMap& operator=(const CMap& cmap) {
7.134 - checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
7.135 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.136 - Edge it;
7.137 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.138 - Parent::set(it, cmap[it]);
7.139 - }
7.140 + Parent::operator=(cmap);
7.141 return *this;
7.142 }
7.143 +
7.144 };
7.145
7.146 // Alteration extension
7.147 @@ -1104,21 +1067,9 @@
7.148 return operator=<ANodeMap>(cmap);
7.149 }
7.150
7.151 -
7.152 - /// \brief Template assign operator.
7.153 - ///
7.154 - /// The given parameter should be conform to the ReadMap
7.155 - /// concept and could be indiced by the current item set of
7.156 - /// the ANodeMap. In this case the value for each item
7.157 - /// is assigned by the value of the given ReadMap.
7.158 template <typename CMap>
7.159 ANodeMap& operator=(const CMap& cmap) {
7.160 - checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
7.161 - const typename Parent::Graph* graph = Parent::getGraph();
7.162 - ANode it;
7.163 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.164 - Parent::set(it, cmap[it]);
7.165 - }
7.166 + Parent::operator=(cmap);
7.167 return *this;
7.168 }
7.169
7.170 @@ -1140,30 +1091,18 @@
7.171 return operator=<BNodeMap>(cmap);
7.172 }
7.173
7.174 -
7.175 - /// \brief Template assign operator.
7.176 - ///
7.177 - /// The given parameter should be conform to the ReadMap
7.178 - /// concept and could be indiced by the current item set of
7.179 - /// the BNodeMap. In this case the value for each item
7.180 - /// is assigned by the value of the given ReadMap.
7.181 template <typename CMap>
7.182 BNodeMap& operator=(const CMap& cmap) {
7.183 - checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
7.184 - const typename Parent::Graph* graph = Parent::getGraph();
7.185 - BNode it;
7.186 - for (graph->first(it); it != INVALID; graph->next(it)) {
7.187 - Parent::set(it, cmap[it]);
7.188 - }
7.189 + Parent::operator=(cmap);
7.190 return *this;
7.191 }
7.192
7.193 };
7.194
7.195 - protected:
7.196 + public:
7.197
7.198 template <typename _Value>
7.199 - class NodeMapBase {
7.200 + class NodeMap {
7.201 public:
7.202 typedef BpUGraphExtender Graph;
7.203
7.204 @@ -1177,10 +1116,25 @@
7.205
7.206 typedef True ReferenceMapTag;
7.207
7.208 - NodeMapBase(const Graph& graph)
7.209 - : aNodeMap(graph), bNodeMap(graph) {}
7.210 - NodeMapBase(const Graph& graph, const _Value& value)
7.211 - : aNodeMap(graph, value), bNodeMap(graph, value) {}
7.212 + NodeMap(const Graph& _graph)
7.213 + : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
7.214 + NodeMap(const Graph& _graph, const _Value& _value)
7.215 + : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
7.216 +
7.217 + NodeMap& operator=(const NodeMap& cmap) {
7.218 + return operator=<NodeMap>(cmap);
7.219 + }
7.220 +
7.221 + template <typename CMap>
7.222 + NodeMap& operator=(const CMap& cmap) {
7.223 + checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.224 + const typename Parent::Notifier* notifier = Parent::getNotifier();
7.225 + Edge it;
7.226 + for (graph.first(it); it != INVALID; graph.next(it)) {
7.227 + Parent::set(it, cmap[it]);
7.228 + }
7.229 + return *this;
7.230 + }
7.231
7.232 ConstReference operator[](const Key& node) const {
7.233 if (Parent::aNode(node)) {
7.234 @@ -1206,54 +1160,62 @@
7.235 }
7.236 }
7.237
7.238 - const Graph* getGraph() const {
7.239 - return aNodeMap.getGraph();
7.240 - }
7.241 + class MapIt : public NodeIt {
7.242 + public:
7.243
7.244 + typedef NodeIt Parent;
7.245 +
7.246 + explicit MapIt(NodeMap& _map)
7.247 + : Parent(_map.graph), map(_map) {}
7.248 +
7.249 + typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
7.250 + return map[*this];
7.251 + }
7.252 +
7.253 + typename MapTraits<NodeMap>::ReturnValue operator*() {
7.254 + return map[*this];
7.255 + }
7.256 +
7.257 + void set(const Value& value) {
7.258 + map.set(*this, value);
7.259 + }
7.260 +
7.261 + private:
7.262 + NodeMap& map;
7.263 + };
7.264 +
7.265 + class ConstMapIt : public NodeIt {
7.266 + public:
7.267 +
7.268 + typedef NodeIt Parent;
7.269 +
7.270 + explicit ConstMapIt(const NodeMap& _map)
7.271 + : Parent(_map.graph), map(_map) {}
7.272 +
7.273 + typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
7.274 + return map[*this];
7.275 + }
7.276 +
7.277 + private:
7.278 + const NodeMap& map;
7.279 + };
7.280 +
7.281 + class ItemIt : public NodeIt {
7.282 + public:
7.283 +
7.284 + typedef NodeIt Parent;
7.285 +
7.286 + explicit ItemIt(const NodeMap& _map)
7.287 + : Parent(_map.graph) {}
7.288 +
7.289 + };
7.290 +
7.291 private:
7.292 + const Graph& graph;
7.293 ANodeMap<_Value> aNodeMap;
7.294 BNodeMap<_Value> bNodeMap;
7.295 };
7.296
7.297 - public:
7.298 -
7.299 - template <typename _Value>
7.300 - class NodeMap
7.301 - : public MapExtender<NodeMapBase<_Value> > {
7.302 - public:
7.303 - typedef BpUGraphExtender Graph;
7.304 - typedef MapExtender< NodeMapBase<_Value> > Parent;
7.305 -
7.306 - NodeMap(const Graph& graph)
7.307 - : Parent(graph) {}
7.308 - NodeMap(const Graph& graph, const _Value& value)
7.309 - : Parent(graph, value) {}
7.310 -
7.311 - NodeMap& operator=(const NodeMap& cmap) {
7.312 - return operator=<NodeMap>(cmap);
7.313 - }
7.314 -
7.315 -
7.316 - /// \brief Template assign operator.
7.317 - ///
7.318 - /// The given parameter should be conform to the ReadMap
7.319 - /// concept and could be indiced by the current item set of
7.320 - /// the NodeMap. In this case the value for each item
7.321 - /// is assigned by the value of the given ReadMap.
7.322 - template <typename CMap>
7.323 - NodeMap& operator=(const CMap& cmap) {
7.324 - checkConcept<concept::ReadMap<Node, _Value>, CMap>();
7.325 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.326 - Edge it;
7.327 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.328 - Parent::set(it, cmap[it]);
7.329 - }
7.330 - return *this;
7.331 - }
7.332 -
7.333 - };
7.334 -
7.335 -
7.336
7.337 template <typename _Value>
7.338 class EdgeMap
7.339 @@ -1273,12 +1235,7 @@
7.340
7.341 template <typename CMap>
7.342 EdgeMap& operator=(const CMap& cmap) {
7.343 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
7.344 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.345 - Edge it;
7.346 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.347 - Parent::set(it, cmap[it]);
7.348 - }
7.349 + Parent::operator=(cmap);
7.350 return *this;
7.351 }
7.352 };
7.353 @@ -1301,12 +1258,7 @@
7.354
7.355 template <typename CMap>
7.356 UEdgeMap& operator=(const CMap& cmap) {
7.357 - checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
7.358 - const typename Parent::Notifier* notifier = Parent::getNotifier();
7.359 - Edge it;
7.360 - for (notifier->first(it); it != INVALID; notifier->next(it)) {
7.361 - Parent::set(it, cmap[it]);
7.362 - }
7.363 + Parent::operator=(cmap);
7.364 return *this;
7.365 }
7.366 };
8.1 --- a/lemon/bits/map_extender.h Mon Apr 03 09:24:38 2006 +0000
8.2 +++ b/lemon/bits/map_extender.h Mon Apr 03 09:45:23 2006 +0000
8.3 @@ -23,6 +23,9 @@
8.4
8.5 #include <lemon/bits/traits.h>
8.6
8.7 +#include <lemon/concept_check.h>
8.8 +#include <lemon/concept/maps.h>
8.9 +
8.10 ///\file
8.11 ///\brief Extenders for iterable maps.
8.12
8.13 @@ -59,6 +62,15 @@
8.14 MapExtender(const Graph& graph, const Value& value)
8.15 : Parent(graph, value) {}
8.16
8.17 + MapExtender& operator=(const MapExtender& cmap) {
8.18 + return operator=<MapExtender>(cmap);
8.19 + }
8.20 +
8.21 + template <typename CMap>
8.22 + MapExtender& operator=(const CMap& cmap) {
8.23 + Parent::operator=(cmap);
8.24 + return *this;
8.25 + }
8.26
8.27 class MapIt : public Item {
8.28 public:
8.29 @@ -130,7 +142,7 @@
8.30 const Map& map;
8.31 };
8.32
8.33 - class ItemIt : Item {
8.34 + class ItemIt : public Item {
8.35 public:
8.36
8.37 typedef Item Parent;
8.38 @@ -140,7 +152,7 @@
8.39 ItemIt(Invalid i) : Parent(i) { }
8.40
8.41 explicit ItemIt(Map& _map) : map(_map) {
8.42 - map->getNotifier()->first(*this);
8.43 + map.getNotifier()->first(*this);
8.44 }
8.45
8.46 ItemIt(const Map& _map, const Item& item)
8.47 @@ -157,6 +169,153 @@
8.48 };
8.49 };
8.50
8.51 + /// \ingroup graphbits
8.52 + ///
8.53 + /// \brief Extender for maps which use a subset of the items.
8.54 + template <typename _Graph, typename _Map>
8.55 + class SubMapExtender : public _Map {
8.56 + public:
8.57 +
8.58 + typedef _Map Parent;
8.59 + typedef SubMapExtender Map;
8.60 +
8.61 + typedef _Graph Graph;
8.62 +
8.63 + typedef typename Parent::Key Item;
8.64 +
8.65 + typedef typename Parent::Key Key;
8.66 + typedef typename Parent::Value Value;
8.67 +
8.68 + class MapIt;
8.69 + class ConstMapIt;
8.70 +
8.71 + friend class MapIt;
8.72 + friend class ConstMapIt;
8.73 +
8.74 + public:
8.75 +
8.76 + SubMapExtender(const Graph& _graph)
8.77 + : Parent(_graph), graph(_graph) {}
8.78 +
8.79 + SubMapExtender(const Graph& _graph, const Value& _value)
8.80 + : Parent(_graph, _value), graph(_graph) {}
8.81 +
8.82 + SubMapExtender& operator=(const SubMapExtender& cmap) {
8.83 + return operator=<MapExtender>(cmap);
8.84 + }
8.85 +
8.86 + template <typename CMap>
8.87 + SubMapExtender& operator=(const CMap& cmap) {
8.88 + checkConcept<concept::ReadMap<Key, Value>, CMap>();
8.89 + Item it;
8.90 + for (graph.first(it); it != INVALID; graph.next(it)) {
8.91 + Parent::set(it, cmap[it]);
8.92 + }
8.93 + return *this;
8.94 + }
8.95 +
8.96 + class MapIt : public Item {
8.97 + public:
8.98 +
8.99 + typedef Item Parent;
8.100 + typedef typename Map::Value Value;
8.101 +
8.102 + MapIt() {}
8.103 +
8.104 + MapIt(Invalid i) : Parent(i) { }
8.105 +
8.106 + explicit MapIt(Map& _map) : map(_map) {
8.107 + map.graph.first(*this);
8.108 + }
8.109 +
8.110 + MapIt(const Map& _map, const Item& item)
8.111 + : Parent(item), map(_map) {}
8.112 +
8.113 + MapIt& operator++() {
8.114 + map.graph.next(*this);
8.115 + return *this;
8.116 + }
8.117 +
8.118 + typename MapTraits<Map>::ConstReturnValue operator*() const {
8.119 + return map[*this];
8.120 + }
8.121 +
8.122 + typename MapTraits<Map>::ReturnValue operator*() {
8.123 + return map[*this];
8.124 + }
8.125 +
8.126 + void set(const Value& value) {
8.127 + map.set(*this, value);
8.128 + }
8.129 +
8.130 + protected:
8.131 + Map& map;
8.132 +
8.133 + };
8.134 +
8.135 + class ConstMapIt : public Item {
8.136 + public:
8.137 +
8.138 + typedef Item Parent;
8.139 +
8.140 + typedef typename Map::Value Value;
8.141 +
8.142 + ConstMapIt() {}
8.143 +
8.144 + ConstMapIt(Invalid i) : Parent(i) { }
8.145 +
8.146 + explicit ConstMapIt(Map& _map) : map(_map) {
8.147 + map.graph.first(*this);
8.148 + }
8.149 +
8.150 + ConstMapIt(const Map& _map, const Item& item)
8.151 + : Parent(item), map(_map) {}
8.152 +
8.153 + ConstMapIt& operator++() {
8.154 + map.graph.next(*this);
8.155 + return *this;
8.156 + }
8.157 +
8.158 + typename MapTraits<Map>::ConstReturnValue operator*() const {
8.159 + return map[*this];
8.160 + }
8.161 +
8.162 + protected:
8.163 + const Map& map;
8.164 + };
8.165 +
8.166 + class ItemIt : public Item {
8.167 + public:
8.168 +
8.169 + typedef Item Parent;
8.170 +
8.171 + ItemIt() {}
8.172 +
8.173 + ItemIt(Invalid i) : Parent(i) { }
8.174 +
8.175 + explicit ItemIt(Map& _map) : map(_map) {
8.176 + map.graph.first(*this);
8.177 + }
8.178 +
8.179 + ItemIt(const Map& _map, const Item& item)
8.180 + : Parent(item), map(_map) {}
8.181 +
8.182 + ItemIt& operator++() {
8.183 + map.graph.next(*this);
8.184 + return *this;
8.185 + }
8.186 +
8.187 + protected:
8.188 + const Map& map;
8.189 +
8.190 + };
8.191 +
8.192 + private:
8.193 +
8.194 + const Graph& graph;
8.195 +
8.196 + };
8.197 +
8.198 }
8.199
8.200 #endif
9.1 --- a/lemon/bits/vector_map.h Mon Apr 03 09:24:38 2006 +0000
9.2 +++ b/lemon/bits/vector_map.h Mon Apr 03 09:45:23 2006 +0000
9.3 @@ -27,6 +27,9 @@
9.4
9.5 #include <lemon/bits/alteration_notifier.h>
9.6
9.7 +#include <lemon/concept_check.h>
9.8 +#include <lemon/concept/maps.h>
9.9 +
9.10 ///\ingroup graphbits
9.11 ///
9.12 ///\file
9.13 @@ -112,10 +115,35 @@
9.14 }
9.15 }
9.16
9.17 - private:
9.18 + /// \brief Assign operator.
9.19 + ///
9.20 + /// This operator assigns for each item in the map the
9.21 + /// value mapped to the same item in the copied map.
9.22 + /// The parameter map should be indiced with the same
9.23 + /// itemset because this assign operator does not change
9.24 + /// the container of the map.
9.25 + VectorMap& operator=(const VectorMap& cmap) {
9.26 + return operator=<VectorMap>(cmap);
9.27 + }
9.28
9.29 - VectorMap& operator=(const VectorMap&);
9.30
9.31 + /// \brief Template assign operator.
9.32 + ///
9.33 + /// The given parameter should be conform to the ReadMap
9.34 + /// concecpt and could be indiced by the current item set of
9.35 + /// the NodeMap. In this case the value for each item
9.36 + /// is assigned by the value of the given ReadMap.
9.37 + template <typename CMap>
9.38 + VectorMap& operator=(const CMap& cmap) {
9.39 + checkConcept<concept::ReadMap<Key, _Value>, CMap>();
9.40 + const typename Parent::Notifier* notifier = Parent::getNotifier();
9.41 + Item it;
9.42 + for (notifier->first(it); it != INVALID; notifier->next(it)) {
9.43 + set(it, cmap[it]);
9.44 + }
9.45 + return *this;
9.46 + }
9.47 +
9.48 public:
9.49
9.50 /// \brief The subcript operator.
10.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
10.2 +++ b/lemon/bpugraph_adaptor.h Mon Apr 03 09:45:23 2006 +0000
10.3 @@ -0,0 +1,412 @@
10.4 +/* -*- C++ -*-
10.5 + *
10.6 + * This file is a part of LEMON, a generic C++ optimization library
10.7 + *
10.8 + * Copyright (C) 2003-2006
10.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
10.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
10.11 + *
10.12 + * Permission to use, modify and distribute this software is granted
10.13 + * provided that this copyright notice appears in all copies. For
10.14 + * precise terms see the accompanying LICENSE file.
10.15 + *
10.16 + * This software is provided "AS IS" with no warranty of any kind,
10.17 + * express or implied, and with no claim as to its suitability for any
10.18 + * purpose.
10.19 + *
10.20 + */
10.21 +
10.22 +#ifndef LEMON_BPUGRAPH_ADAPTOR_H
10.23 +#define LEMON_BPUGRAPH_ADAPTOR_H
10.24 +
10.25 +#include <lemon/bits/invalid.h>
10.26 +#include <lemon/maps.h>
10.27 +
10.28 +#include <lemon/bits/graph_adaptor_extender.h>
10.29 +
10.30 +#include <lemon/bits/traits.h>
10.31 +
10.32 +#include <iostream>
10.33 +
10.34 +///\ingroup graph_adaptors
10.35 +///\file
10.36 +///\brief Several graph adaptors.
10.37 +///
10.38 +///This file contains several useful bpugraph adaptor functions.
10.39 +///
10.40 +///\author Balazs Dezso
10.41 +
10.42 +namespace lemon {
10.43 +
10.44 + /// \ingroup graph_adaptors
10.45 + ///
10.46 + /// \brief Base type for the Bipartite Undirected Graph Adaptors
10.47 + ///
10.48 + /// This is the base type for most of LEMON bpugraph adaptors.
10.49 + /// This class implements a trivial graph adaptor i.e. it only wraps the
10.50 + /// functions and types of the graph. The purpose of this class is to
10.51 + /// make easier implementing graph adaptors. E.g. if an adaptor is
10.52 + /// considered which differs from the wrapped graph only in some of its
10.53 + /// functions or types, then it can be derived from BpUGraphAdaptor, and
10.54 + /// only the differences should be implemented.
10.55 + ///
10.56 + /// \author Balazs Dezso
10.57 + template<typename _BpUGraph>
10.58 + class BpUGraphAdaptorBase {
10.59 + public:
10.60 + typedef _BpUGraph Graph;
10.61 + typedef Graph ParentGraph;
10.62 +
10.63 + protected:
10.64 + Graph* graph;
10.65 +
10.66 + BpUGraphAdaptorBase() : graph(0) {}
10.67 +
10.68 + void setGraph(Graph& _graph) { graph = &_graph; }
10.69 +
10.70 + Graph& getGraph() { return *graph; }
10.71 + const Graph& getGraph() const { return *graph; }
10.72 +
10.73 + public:
10.74 +
10.75 + BpUGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
10.76 +
10.77 + typedef typename Graph::Node Node;
10.78 + typedef typename Graph::ANode ANode;
10.79 + typedef typename Graph::BNode BNode;
10.80 + typedef typename Graph::Edge Edge;
10.81 + typedef typename Graph::UEdge UEdge;
10.82 +
10.83 + void first(Node& i) const { graph->first(i); }
10.84 + void firstANode(Node& i) const { graph->firstANode(i); }
10.85 + void firstBNode(Node& i) const { graph->firstBNode(i); }
10.86 + void first(Edge& i) const { graph->first(i); }
10.87 + void first(UEdge& i) const { graph->first(i); }
10.88 + void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
10.89 + void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
10.90 + void firstInc(UEdge &i, bool &d, const Node &n) const {
10.91 + graph->firstInc(i, d, n);
10.92 + }
10.93 +
10.94 + void next(Node& i) const { graph->next(i); }
10.95 + void nextANode(Node& i) const { graph->nextANode(i); }
10.96 + void nextBNode(Node& i) const { graph->nextBNode(i); }
10.97 + void next(Edge& i) const { graph->next(i); }
10.98 + void next(UEdge& i) const { graph->next(i); }
10.99 + void nextIn(Edge& i) const { graph->nextIn(i); }
10.100 + void nextOut(Edge& i) const { graph->nextOut(i); }
10.101 + void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
10.102 +
10.103 + Node source(const UEdge& e) const { return graph->source(e); }
10.104 + Node target(const UEdge& e) const { return graph->target(e); }
10.105 +
10.106 + Node source(const Edge& e) const { return graph->source(e); }
10.107 + Node target(const Edge& e) const { return graph->target(e); }
10.108 +
10.109 + typedef NodeNumTagIndicator<Graph> NodeNumTag;
10.110 + int nodeNum() const { return graph->nodeNum(); }
10.111 + int aNodeNum() const { return graph->aNodeNum(); }
10.112 + int bNodeNum() const { return graph->bNodeNum(); }
10.113 +
10.114 + typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
10.115 + int edgeNum() const { return graph->edgeNum(); }
10.116 + int uEdgeNum() const { return graph->uEdgeNum(); }
10.117 +
10.118 + typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
10.119 + Edge findEdge(const Node& source, const Node& target,
10.120 + const Edge& prev = INVALID) {
10.121 + return graph->findEdge(source, target, prev);
10.122 + }
10.123 + UEdge findUEdge(const Node& source, const Node& target,
10.124 + const UEdge& prev = INVALID) {
10.125 + return graph->findUEdge(source, target, prev);
10.126 + }
10.127 +
10.128 + Node addNode() const { return graph->addNode(); }
10.129 + UEdge addEdge(const Node& source, const Node& target) const {
10.130 + return graph->addEdge(source, target);
10.131 + }
10.132 +
10.133 + void erase(const Node& i) const { graph->erase(i); }
10.134 + void erase(const UEdge& i) const { graph->erase(i); }
10.135 +
10.136 + void clear() const { graph->clear(); }
10.137 +
10.138 + bool direction(const Edge& e) const { return graph->direction(e); }
10.139 + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
10.140 +
10.141 + int id(const Node& v) const { return graph->id(v); }
10.142 + int id(const ANode& v) const { return graph->id(v); }
10.143 + int id(const BNode& v) const { return graph->id(v); }
10.144 + int id(const Edge& e) const { return graph->id(e); }
10.145 + int id(const UEdge& e) const { return graph->id(e); }
10.146 +
10.147 + Node fromNodeId(int id) const { return graph->fromNodeId(id); }
10.148 + ANode fromANodeId(int id) const { return graph->fromANodeId(id); }
10.149 + BNode fromBNodeId(int id) const { return graph->fromBNodeId(id); }
10.150 + Edge fromEdgeId(int id) const { return graph->fromEdgeId(id); }
10.151 + UEdge fromUEdgeId(int id) const { return graph->fromUEdgeId(id); }
10.152 +
10.153 + int maxNodeId() const { return graph->maxNodeId(); }
10.154 + int maxANodeId() const { return graph->maxANodeId(); }
10.155 + int maxBNodeId() const { return graph->maxBNodeId(); }
10.156 + int maxEdgeId() const { return graph->maxEdgeId(); }
10.157 + int maxUEdgeId() const { return graph->maxEdgeId(); }
10.158 +
10.159 + typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
10.160 + NodeNotifier& getNotifier(Node) const {
10.161 + return graph->getNotifier(Node());
10.162 + }
10.163 +
10.164 + typedef typename ItemSetTraits<Graph, ANode>::ItemNotifier ANodeNotifier;
10.165 + ANodeNotifier& getNotifier(ANode) const {
10.166 + return graph->getNotifier(ANode());
10.167 + }
10.168 +
10.169 + typedef typename ItemSetTraits<Graph, BNode>::ItemNotifier BNodeNotifier;
10.170 + BNodeNotifier& getNotifier(BNode) const {
10.171 + return graph->getNotifier(BNode());
10.172 + }
10.173 +
10.174 + typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;
10.175 + EdgeNotifier& getNotifier(Edge) const {
10.176 + return graph->getNotifier(Edge());
10.177 + }
10.178 +
10.179 + typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;
10.180 + UEdgeNotifier& getNotifier(UEdge) const {
10.181 + return graph->getNotifier(UEdge());
10.182 + }
10.183 +
10.184 + template <typename _Value>
10.185 + class NodeMap : public Graph::template NodeMap<_Value> {
10.186 + public:
10.187 + typedef typename Graph::template NodeMap<_Value> Parent;
10.188 + explicit NodeMap(const BpUGraphAdaptorBase<Graph>& ga)
10.189 + : Parent(*ga.graph) {}
10.190 + NodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
10.191 + : Parent(*ga.graph, value) {}
10.192 +
10.193 + NodeMap& operator=(const NodeMap& cmap) {
10.194 + return operator=<NodeMap>(cmap);
10.195 + }
10.196 +
10.197 + template <typename CMap>
10.198 + NodeMap& operator=(const CMap& cmap) {
10.199 + Parent::operator=(cmap);
10.200 + return *this;
10.201 + }
10.202 + };
10.203 +
10.204 + template <typename _Value>
10.205 + class ANodeMap : public Graph::template ANodeMap<_Value> {
10.206 + public:
10.207 + typedef typename Graph::template ANodeMap<_Value> Parent;
10.208 + explicit ANodeMap(const BpUGraphAdaptorBase& ga)
10.209 + : Parent(*ga.graph) {}
10.210 + ANodeMap(const BpUGraphAdaptorBase& ga, const _Value& value)
10.211 + : Parent(*ga.graph, value) {}
10.212 +
10.213 + ANodeMap& operator=(const ANodeMap& cmap) {
10.214 + return operator=<ANodeMap>(cmap);
10.215 + }
10.216 +
10.217 + template <typename CMap>
10.218 + ANodeMap& operator=(const CMap& cmap) {
10.219 + Parent::operator=(cmap);
10.220 + return *this;
10.221 + }
10.222 + };
10.223 +
10.224 + template <typename _Value>
10.225 + class BNodeMap : public Graph::template BNodeMap<_Value> {
10.226 + public:
10.227 + typedef typename Graph::template BNodeMap<_Value> Parent;
10.228 + explicit BNodeMap(const BpUGraphAdaptorBase<Graph>& ga)
10.229 + : Parent(*ga.graph) {}
10.230 + BNodeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
10.231 + : Parent(*ga.graph, value) {}
10.232 +
10.233 + BNodeMap& operator=(const BNodeMap& cmap) {
10.234 + return operator=<BNodeMap>(cmap);
10.235 + }
10.236 +
10.237 + template <typename CMap>
10.238 + BNodeMap& operator=(const CMap& cmap) {
10.239 + Parent::operator=(cmap);
10.240 + return *this;
10.241 + }
10.242 + };
10.243 +
10.244 + template <typename _Value>
10.245 + class EdgeMap : public Graph::template EdgeMap<_Value> {
10.246 + public:
10.247 + typedef typename Graph::template EdgeMap<_Value> Parent;
10.248 + explicit EdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
10.249 + : Parent(*ga.graph) {}
10.250 + EdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
10.251 + : Parent(*ga.graph, value) {}
10.252 +
10.253 + EdgeMap& operator=(const EdgeMap& cmap) {
10.254 + return operator=<EdgeMap>(cmap);
10.255 + }
10.256 +
10.257 + template <typename CMap>
10.258 + EdgeMap& operator=(const CMap& cmap) {
10.259 + Parent::operator=(cmap);
10.260 + return *this;
10.261 + }
10.262 + };
10.263 +
10.264 + template <typename _Value>
10.265 + class UEdgeMap : public Graph::template UEdgeMap<_Value> {
10.266 + public:
10.267 + typedef typename Graph::template UEdgeMap<_Value> Parent;
10.268 + explicit UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga)
10.269 + : Parent(*ga.graph) {}
10.270 + UEdgeMap(const BpUGraphAdaptorBase<Graph>& ga, const _Value& value)
10.271 + : Parent(*ga.graph, value) {}
10.272 +
10.273 + UEdgeMap& operator=(const UEdgeMap& cmap) {
10.274 + return operator=<UEdgeMap>(cmap);
10.275 + }
10.276 +
10.277 + template <typename CMap>
10.278 + UEdgeMap& operator=(const CMap& cmap) {
10.279 + Parent::operator=(cmap);
10.280 + return *this;
10.281 + }
10.282 + };
10.283 +
10.284 + };
10.285 +
10.286 + /// \ingroup graph_adaptors
10.287 + template <typename _BpUGraph>
10.288 + class BpUGraphAdaptor
10.289 + : public BpUGraphAdaptorExtender< BpUGraphAdaptorBase<_BpUGraph> > {
10.290 + public:
10.291 + typedef _BpUGraph Graph;
10.292 + typedef BpUGraphAdaptorExtender<BpUGraphAdaptorBase<_BpUGraph> > Parent;
10.293 + protected:
10.294 + BpUGraphAdaptor() : Parent() {}
10.295 +
10.296 + public:
10.297 + explicit BpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
10.298 + };
10.299 +
10.300 + template <typename _BpUGraph>
10.301 + class SwapBpUGraphAdaptorBase : public BpUGraphAdaptorBase<_BpUGraph> {
10.302 + public:
10.303 +
10.304 + typedef _BpUGraph Graph;
10.305 + typedef BpUGraphAdaptorBase<_BpUGraph> Parent;
10.306 +
10.307 + protected:
10.308 +
10.309 + SwapBpUGraphAdaptorBase() {}
10.310 +
10.311 + public:
10.312 +
10.313 + typedef typename Parent::Node Node;
10.314 + typedef typename Parent::BNode ANode;
10.315 + typedef typename Parent::ANode BNode;
10.316 +
10.317 + void firstANode(Node& i) const { Parent::firstBNode(i); }
10.318 + void firstBNode(Node& i) const { Parent::firstANode(i); }
10.319 +
10.320 + void nextANode(Node& i) const { Parent::nextBNode(i); }
10.321 + void nextBNode(Node& i) const { Parent::nextANode(i); }
10.322 +
10.323 + int id(const ANode& v) const { return Parent::id(v); }
10.324 + int id(const BNode& v) const { return Parent::id(v); }
10.325 +
10.326 + ANode fromANodeId(int id) const { return Parent::fromBNodeId(id); }
10.327 + BNode fromBNodeId(int id) const { return Parent::fromANodeId(id); }
10.328 +
10.329 + int maxANodeId() const { return Parent::maxBNodeId(); }
10.330 + int maxBNodeId() const { return Parent::maxANodeId(); }
10.331 +
10.332 + int aNodeNum() const { return Parent::bNodeNum(); }
10.333 + int bNodeNum() const { return Parent::aNodeNum(); }
10.334 +
10.335 + typedef typename Parent::BNodeNotifier ANodeNotifier;
10.336 + ANodeNotifier& getNotifier(ANode) const {
10.337 + return Parent::getNotifier(typename Parent::BNode());
10.338 + }
10.339 +
10.340 + typedef typename Parent::ANodeNotifier BNodeNotifier;
10.341 + BNodeNotifier& getNotifier(BNode) const {
10.342 + return Parent::getNotifier(typename Parent::ANode());
10.343 + }
10.344 +
10.345 + template <typename _Value>
10.346 + class ANodeMap : public Graph::template BNodeMap<_Value> {
10.347 + public:
10.348 + typedef typename Graph::template BNodeMap<_Value> Parent;
10.349 + explicit ANodeMap(const SwapBpUGraphAdaptorBase& ga)
10.350 + : Parent(*ga.graph) {}
10.351 + ANodeMap(const SwapBpUGraphAdaptorBase& ga, const _Value& value)
10.352 + : Parent(*ga.graph, value) {}
10.353 +
10.354 + ANodeMap& operator=(const ANodeMap& cmap) {
10.355 + return operator=<ANodeMap>(cmap);
10.356 + }
10.357 +
10.358 + template <typename CMap>
10.359 + ANodeMap& operator=(const CMap& cmap) {
10.360 + Parent::operator=(cmap);
10.361 + return *this;
10.362 + }
10.363 + };
10.364 +
10.365 + template <typename _Value>
10.366 + class BNodeMap : public Graph::template ANodeMap<_Value> {
10.367 + public:
10.368 + typedef typename Graph::template ANodeMap<_Value> Parent;
10.369 + explicit BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga)
10.370 + : Parent(*ga.graph) {}
10.371 + BNodeMap(const SwapBpUGraphAdaptorBase<Graph>& ga, const _Value& value)
10.372 + : Parent(*ga.graph, value) {}
10.373 +
10.374 + BNodeMap& operator=(const BNodeMap& cmap) {
10.375 + return operator=<BNodeMap>(cmap);
10.376 + }
10.377 +
10.378 + template <typename CMap>
10.379 + BNodeMap& operator=(const CMap& cmap) {
10.380 + Parent::operator=(cmap);
10.381 + return *this;
10.382 + }
10.383 + };
10.384 +
10.385 + };
10.386 +
10.387 + /// \ingroup graph_adaptors
10.388 + ///
10.389 + /// \brief Bipartite graph adaptor which swaps the two nodeset.
10.390 + ///
10.391 + /// Bipartite graph adaptor which swaps the two nodeset. The adaptor's
10.392 + /// a-nodeset will be the original graph's b-nodeset and the adaptor's
10.393 + /// b-nodeset will be the original graph's a-nodeset.
10.394 + template <typename _BpUGraph>
10.395 + class SwapBpUGraphAdaptor
10.396 + : public BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> > {
10.397 + public:
10.398 +
10.399 + typedef _BpUGraph Graph;
10.400 + typedef BpUGraphAdaptorExtender<SwapBpUGraphAdaptorBase<_BpUGraph> >
10.401 + Parent;
10.402 +
10.403 + protected:
10.404 + SwapBpUGraphAdaptor() : Parent() {}
10.405 +
10.406 + public:
10.407 +
10.408 + explicit SwapBpUGraphAdaptor(Graph& _graph) { setGraph(_graph); }
10.409 +
10.410 + };
10.411 +
10.412 +
10.413 +}
10.414 +
10.415 +#endif
11.1 --- a/lemon/edge_set.h Mon Apr 03 09:24:38 2006 +0000
11.2 +++ b/lemon/edge_set.h Mon Apr 03 09:45:23 2006 +0000
11.3 @@ -206,11 +206,24 @@
11.4 template <typename _Value>
11.5 class NodeMap : public Graph::template NodeMap<_Value> {
11.6 public:
11.7 +
11.8 typedef typename _Graph::template NodeMap<_Value> Parent;
11.9 +
11.10 explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
11.11 - : Parent(*edgeset.graph) { }
11.12 + : Parent(*edgeset.graph) {}
11.13 +
11.14 NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
11.15 - : Parent(*edgeset.graph, value) { }
11.16 + : Parent(*edgeset.graph, value) {}
11.17 +
11.18 + NodeMap& operator=(const NodeMap& cmap) {
11.19 + return operator=<NodeMap>(cmap);
11.20 + }
11.21 +
11.22 + template <typename CMap>
11.23 + NodeMap& operator=(const CMap& cmap) {
11.24 + Parent::operator=(cmap);
11.25 + return *this;
11.26 + }
11.27 };
11.28
11.29 };
11.30 @@ -521,11 +534,24 @@
11.31 template <typename _Value>
11.32 class NodeMap : public Graph::template NodeMap<_Value> {
11.33 public:
11.34 +
11.35 typedef typename _Graph::template NodeMap<_Value> Parent;
11.36 +
11.37 explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset)
11.38 : Parent(*edgeset.graph) { }
11.39 +
11.40 NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
11.41 : Parent(*edgeset.graph, value) { }
11.42 +
11.43 + NodeMap& operator=(const NodeMap& cmap) {
11.44 + return operator=<NodeMap>(cmap);
11.45 + }
11.46 +
11.47 + template <typename CMap>
11.48 + NodeMap& operator=(const CMap& cmap) {
11.49 + Parent::operator=(cmap);
11.50 + return *this;
11.51 + }
11.52 };
11.53
11.54 };
11.55 @@ -667,7 +693,7 @@
11.56 typedef typename Parent::NodesImplBase NodesImplBase;
11.57
11.58 void eraseNode(const Node& node) {
11.59 - if (Parent::IncEdgeIt(*this, node) == INVALID) {
11.60 + if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
11.61 return;
11.62 }
11.63 throw UnsupportedOperation();
12.1 --- a/lemon/full_graph.h Mon Apr 03 09:24:38 2006 +0000
12.2 +++ b/lemon/full_graph.h Mon Apr 03 09:45:23 2006 +0000
12.3 @@ -645,6 +645,14 @@
12.4 return Node((index << 1) + 1);
12.5 }
12.6
12.7 + typedef True NodeNumTag;
12.8 + int nodeNum() const { return _aNodeNum + _bNodeNum; }
12.9 + int aNodeNum() const { return _aNodeNum; }
12.10 + int bNodeNum() const { return _bNodeNum; }
12.11 +
12.12 + typedef True EdgeNumTag;
12.13 + int edgeNum() const { return _edgeNum; }
12.14 +
12.15 };
12.16
12.17
13.1 --- a/lemon/graph_adaptor.h Mon Apr 03 09:24:38 2006 +0000
13.2 +++ b/lemon/graph_adaptor.h Mon Apr 03 09:45:23 2006 +0000
13.3 @@ -19,13 +19,13 @@
13.4 #ifndef LEMON_GRAPH_ADAPTOR_H
13.5 #define LEMON_GRAPH_ADAPTOR_H
13.6
13.7 -///\ingroup graph_adaptors
13.8 -///\file
13.9 -///\brief Several graph adaptors.
13.10 +/// \ingroup graph_adaptors
13.11 +/// \file
13.12 +/// \brief Several graph adaptors.
13.13 ///
13.14 -///This file contains several useful graph adaptor functions.
13.15 +/// This file contains several useful graph adaptor functions.
13.16 ///
13.17 -///\author Marton Makai
13.18 +/// \author Marton Makai and Balazs Dezso
13.19
13.20 #include <lemon/bits/invalid.h>
13.21 #include <lemon/maps.h>
13.22 @@ -61,6 +61,7 @@
13.23 class GraphAdaptorBase {
13.24 public:
13.25 typedef _Graph Graph;
13.26 + typedef GraphAdaptorBase Adaptor;
13.27 typedef Graph ParentGraph;
13.28
13.29 protected:
13.30 @@ -115,6 +116,14 @@
13.31 int id(const Node& v) const { return graph->id(v); }
13.32 int id(const Edge& e) const { return graph->id(e); }
13.33
13.34 + Node fromNodeId(int id) const {
13.35 + return graph->fromNodeId(id);
13.36 + }
13.37 +
13.38 + Edge fromEdgeId(int id) const {
13.39 + return graph->fromEdgeId(id);
13.40 + }
13.41 +
13.42 int maxNodeId() const {
13.43 return graph->maxNodeId();
13.44 }
13.45 @@ -136,23 +145,51 @@
13.46 }
13.47
13.48 template <typename _Value>
13.49 - class NodeMap : public _Graph::template NodeMap<_Value> {
13.50 + class NodeMap : public Graph::template NodeMap<_Value> {
13.51 public:
13.52 - typedef typename _Graph::template NodeMap<_Value> Parent;
13.53 - explicit NodeMap(const GraphAdaptorBase<_Graph>& ga)
13.54 - : Parent(*ga.graph) { }
13.55 - NodeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
13.56 +
13.57 + typedef typename Graph::template NodeMap<_Value> Parent;
13.58 +
13.59 + explicit NodeMap(const Adaptor& ga)
13.60 + : Parent(*ga.graph) {}
13.61 +
13.62 + NodeMap(const Adaptor& ga, const _Value& value)
13.63 : Parent(*ga.graph, value) { }
13.64 +
13.65 + NodeMap& operator=(const NodeMap& cmap) {
13.66 + return operator=<NodeMap>(cmap);
13.67 + }
13.68 +
13.69 + template <typename CMap>
13.70 + NodeMap& operator=(const CMap& cmap) {
13.71 + Parent::operator=(cmap);
13.72 + return *this;
13.73 + }
13.74 +
13.75 };
13.76
13.77 template <typename _Value>
13.78 - class EdgeMap : public _Graph::template EdgeMap<_Value> {
13.79 + class EdgeMap : public Graph::template EdgeMap<_Value> {
13.80 public:
13.81 - typedef typename _Graph::template EdgeMap<_Value> Parent;
13.82 - explicit EdgeMap(const GraphAdaptorBase<_Graph>& ga)
13.83 - : Parent(*ga.graph) { }
13.84 - EdgeMap(const GraphAdaptorBase<_Graph>& ga, const _Value& value)
13.85 - : Parent(*ga.graph, value) { }
13.86 +
13.87 + typedef typename Graph::template EdgeMap<_Value> Parent;
13.88 +
13.89 + explicit EdgeMap(const Adaptor& ga)
13.90 + : Parent(*ga.graph) {}
13.91 +
13.92 + EdgeMap(const Adaptor& ga, const _Value& value)
13.93 + : Parent(*ga.graph, value) {}
13.94 +
13.95 + EdgeMap& operator=(const EdgeMap& cmap) {
13.96 + return operator=<EdgeMap>(cmap);
13.97 + }
13.98 +
13.99 + template <typename CMap>
13.100 + EdgeMap& operator=(const CMap& cmap) {
13.101 + Parent::operator=(cmap);
13.102 + return *this;
13.103 + }
13.104 +
13.105 };
13.106
13.107 };
13.108 @@ -255,6 +292,7 @@
13.109 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
13.110 public:
13.111 typedef _Graph Graph;
13.112 + typedef SubGraphAdaptorBase Adaptor;
13.113 typedef GraphAdaptorBase<_Graph> Parent;
13.114 protected:
13.115 NodeFilterMap* node_filter_map;
13.116 @@ -377,6 +415,59 @@
13.117 }
13.118 return edge;
13.119 }
13.120 +
13.121 + template <typename _Value>
13.122 + class NodeMap
13.123 + : public SubMapExtender<Adaptor,
13.124 + typename Parent::template NodeMap<_Value> >
13.125 + {
13.126 + public:
13.127 + typedef Adaptor Graph;
13.128 + typedef SubMapExtender<Adaptor, typename Parent::
13.129 + template NodeMap<_Value> > Parent;
13.130 +
13.131 + NodeMap(const Graph& graph)
13.132 + : Parent(graph) {}
13.133 + NodeMap(const Graph& graph, const _Value& value)
13.134 + : Parent(graph, value) {}
13.135 +
13.136 + NodeMap& operator=(const NodeMap& cmap) {
13.137 + return operator=<NodeMap>(cmap);
13.138 + }
13.139 +
13.140 + template <typename CMap>
13.141 + NodeMap& operator=(const CMap& cmap) {
13.142 + Parent::operator=(cmap);
13.143 + return *this;
13.144 + }
13.145 + };
13.146 +
13.147 + template <typename _Value>
13.148 + class EdgeMap
13.149 + : public SubMapExtender<Adaptor,
13.150 + typename Parent::template EdgeMap<_Value> >
13.151 + {
13.152 + public:
13.153 + typedef Adaptor Graph;
13.154 + typedef SubMapExtender<Adaptor, typename Parent::
13.155 + template EdgeMap<_Value> > Parent;
13.156 +
13.157 + EdgeMap(const Graph& graph)
13.158 + : Parent(graph) {}
13.159 + EdgeMap(const Graph& graph, const _Value& value)
13.160 + : Parent(graph, value) {}
13.161 +
13.162 + EdgeMap& operator=(const EdgeMap& cmap) {
13.163 + return operator=<EdgeMap>(cmap);
13.164 + }
13.165 +
13.166 + template <typename CMap>
13.167 + EdgeMap& operator=(const CMap& cmap) {
13.168 + Parent::operator=(cmap);
13.169 + return *this;
13.170 + }
13.171 + };
13.172 +
13.173 };
13.174
13.175 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
13.176 @@ -384,6 +475,7 @@
13.177 : public GraphAdaptorBase<_Graph> {
13.178 public:
13.179 typedef _Graph Graph;
13.180 + typedef SubGraphAdaptorBase Adaptor;
13.181 typedef GraphAdaptorBase<_Graph> Parent;
13.182 protected:
13.183 NodeFilterMap* node_filter_map;
13.184 @@ -496,6 +588,59 @@
13.185 }
13.186 return edge;
13.187 }
13.188 +
13.189 + template <typename _Value>
13.190 + class NodeMap
13.191 + : public SubMapExtender<Adaptor,
13.192 + typename Parent::template NodeMap<_Value> >
13.193 + {
13.194 + public:
13.195 + typedef Adaptor Graph;
13.196 + typedef SubMapExtender<Adaptor, typename Parent::
13.197 + template NodeMap<_Value> > Parent;
13.198 +
13.199 + NodeMap(const Graph& graph)
13.200 + : Parent(graph) {}
13.201 + NodeMap(const Graph& graph, const _Value& value)
13.202 + : Parent(graph, value) {}
13.203 +
13.204 + NodeMap& operator=(const NodeMap& cmap) {
13.205 + return operator=<NodeMap>(cmap);
13.206 + }
13.207 +
13.208 + template <typename CMap>
13.209 + NodeMap& operator=(const CMap& cmap) {
13.210 + Parent::operator=(cmap);
13.211 + return *this;
13.212 + }
13.213 + };
13.214 +
13.215 + template <typename _Value>
13.216 + class EdgeMap
13.217 + : public SubMapExtender<Adaptor,
13.218 + typename Parent::template EdgeMap<_Value> >
13.219 + {
13.220 + public:
13.221 + typedef Adaptor Graph;
13.222 + typedef SubMapExtender<Adaptor, typename Parent::
13.223 + template EdgeMap<_Value> > Parent;
13.224 +
13.225 + EdgeMap(const Graph& graph)
13.226 + : Parent(graph) {}
13.227 + EdgeMap(const Graph& graph, const _Value& value)
13.228 + : Parent(graph, value) {}
13.229 +
13.230 + EdgeMap& operator=(const EdgeMap& cmap) {
13.231 + return operator=<EdgeMap>(cmap);
13.232 + }
13.233 +
13.234 + template <typename CMap>
13.235 + EdgeMap& operator=(const CMap& cmap) {
13.236 + Parent::operator=(cmap);
13.237 + return *this;
13.238 + }
13.239 + };
13.240 +
13.241 };
13.242
13.243 /// \brief A graph adaptor for hiding nodes and edges from a graph.
13.244 @@ -566,17 +711,21 @@
13.245 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
13.246 public:
13.247 typedef _Graph Graph;
13.248 - typedef GraphAdaptorExtender<
13.249 - SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
13.250 + typedef GraphAdaptorExtender< SubGraphAdaptorBase<_Graph, NodeFilterMap,
13.251 + EdgeFilterMap, checked> >
13.252 + Parent;
13.253 +
13.254 protected:
13.255 SubGraphAdaptor() { }
13.256 public:
13.257 +
13.258 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
13.259 EdgeFilterMap& _edge_filter_map) {
13.260 setGraph(_graph);
13.261 setNodeFilterMap(_node_filter_map);
13.262 setEdgeFilterMap(_edge_filter_map);
13.263 }
13.264 +
13.265 };
13.266
13.267 /// \brief Just gives back a sub graph adaptor
13.268 @@ -635,8 +784,11 @@
13.269 public SubGraphAdaptor<Graph, NodeFilterMap,
13.270 ConstMap<typename Graph::Edge,bool>, checked> {
13.271 public:
13.272 +
13.273 typedef SubGraphAdaptor<Graph, NodeFilterMap,
13.274 - ConstMap<typename Graph::Edge,bool> > Parent;
13.275 + ConstMap<typename Graph::Edge,bool>, checked >
13.276 + Parent;
13.277 +
13.278 protected:
13.279 ConstMap<typename Graph::Edge, bool> const_true_map;
13.280
13.281 @@ -645,12 +797,14 @@
13.282 }
13.283
13.284 public:
13.285 +
13.286 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
13.287 Parent(), const_true_map(true) {
13.288 Parent::setGraph(_graph);
13.289 Parent::setNodeFilterMap(_node_filter_map);
13.290 Parent::setEdgeFilterMap(const_true_map);
13.291 }
13.292 +
13.293 };
13.294
13.295
13.296 @@ -820,12 +974,14 @@
13.297 }
13.298
13.299 public:
13.300 +
13.301 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
13.302 Parent(), const_true_map(true) {
13.303 Parent::setGraph(_graph);
13.304 Parent::setNodeFilterMap(const_true_map);
13.305 Parent::setEdgeFilterMap(_edge_filter_map);
13.306 }
13.307 +
13.308 };
13.309
13.310 /// \brief Just gives back an edge sub graph adaptor
13.311 @@ -848,6 +1004,7 @@
13.312 public UGraphBaseExtender<GraphAdaptorBase<_Graph> > {
13.313 public:
13.314 typedef _Graph Graph;
13.315 + typedef UndirGraphAdaptorBase Adaptor;
13.316 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
13.317
13.318 protected:
13.319 @@ -859,9 +1016,10 @@
13.320 typedef typename Parent::UEdge UEdge;
13.321 typedef typename Parent::Edge Edge;
13.322
13.323 + private:
13.324
13.325 template <typename _Value>
13.326 - class EdgeMap {
13.327 + class EdgeMapBase {
13.328 private:
13.329
13.330 typedef typename _Graph::template EdgeMap<_Value> MapImpl;
13.331 @@ -873,11 +1031,11 @@
13.332 typedef _Value Value;
13.333 typedef Edge Key;
13.334
13.335 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
13.336 - forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
13.337 + EdgeMapBase(const Adaptor& adaptor) :
13.338 + forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
13.339
13.340 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
13.341 - : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
13.342 + EdgeMapBase(const Adaptor& adaptor, const Value& v)
13.343 + : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
13.344
13.345 void set(const Edge& e, const Value& a) {
13.346 if (Parent::direction(e)) {
13.347 @@ -908,19 +1066,55 @@
13.348 MapImpl forward_map, backward_map;
13.349
13.350 };
13.351 +
13.352 + public:
13.353 +
13.354 + template <typename _Value>
13.355 + class EdgeMap
13.356 + : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
13.357 + {
13.358 + public:
13.359 + typedef Adaptor Graph;
13.360 + typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
13.361 +
13.362 + EdgeMap(const Graph& graph)
13.363 + : Parent(graph) {}
13.364 + EdgeMap(const Graph& graph, const _Value& value)
13.365 + : Parent(graph, value) {}
13.366 +
13.367 + EdgeMap& operator=(const EdgeMap& cmap) {
13.368 + return operator=<EdgeMap>(cmap);
13.369 + }
13.370 +
13.371 + template <typename CMap>
13.372 + EdgeMap& operator=(const CMap& cmap) {
13.373 + Parent::operator=(cmap);
13.374 + return *this;
13.375 + }
13.376 + };
13.377
13.378 template <typename _Value>
13.379 - class UEdgeMap : public _Graph::template EdgeMap<_Value> {
13.380 + class UEdgeMap : public Graph::template EdgeMap<_Value> {
13.381 public:
13.382 +
13.383 + typedef typename Graph::template EdgeMap<_Value> Parent;
13.384 +
13.385 + explicit UEdgeMap(const Adaptor& ga)
13.386 + : Parent(*ga.graph) {}
13.387
13.388 - typedef typename _Graph::template EdgeMap<_Value> Parent;
13.389 + UEdgeMap(const Adaptor& ga, const _Value& value)
13.390 + : Parent(*ga.graph, value) {}
13.391
13.392 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
13.393 - : Parent(*(g.graph)) {}
13.394 + UEdgeMap& operator=(const UEdgeMap& cmap) {
13.395 + return operator=<UEdgeMap>(cmap);
13.396 + }
13.397
13.398 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
13.399 - : Parent(*(g.graph), a) {}
13.400 -
13.401 + template <typename CMap>
13.402 + UEdgeMap& operator=(const CMap& cmap) {
13.403 + Parent::operator=(cmap);
13.404 + return *this;
13.405 + }
13.406 +
13.407 };
13.408
13.409 };
13.410 @@ -933,6 +1127,7 @@
13.411 public:
13.412
13.413 typedef _Graph Graph;
13.414 + typedef UndirGraphAdaptorBase Adaptor;
13.415 typedef UGraphBaseExtender<GraphAdaptorBase<_Graph> > Parent;
13.416
13.417 protected:
13.418 @@ -1033,11 +1228,10 @@
13.419 mutable EdgeNotifier edge_notifier;
13.420 NotifierProxy edge_notifier_proxy;
13.421
13.422 - public:
13.423 -
13.424 + private:
13.425
13.426 template <typename _Value>
13.427 - class EdgeMap {
13.428 + class EdgeMapBase {
13.429 private:
13.430
13.431 typedef typename _Graph::template EdgeMap<_Value> MapImpl;
13.432 @@ -1049,11 +1243,11 @@
13.433 typedef _Value Value;
13.434 typedef Edge Key;
13.435
13.436 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) :
13.437 - forward_map(*(_g.graph)), backward_map(*(_g.graph)) {}
13.438 + EdgeMapBase(const Adaptor& adaptor) :
13.439 + forward_map(*adaptor.graph), backward_map(*adaptor.graph) {}
13.440
13.441 - EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, const Value& a)
13.442 - : forward_map(*(_g.graph), a), backward_map(*(_g.graph), a) {}
13.443 + EdgeMapBase(const Adaptor& adaptor, const Value& v)
13.444 + : forward_map(*adaptor.graph, v), backward_map(*adaptor.graph, v) {}
13.445
13.446 void set(const Edge& e, const Value& a) {
13.447 if (Parent::direction(e)) {
13.448 @@ -1063,8 +1257,7 @@
13.449 }
13.450 }
13.451
13.452 - typename MapTraits<MapImpl>::ConstReturnValue
13.453 - operator[](const Edge& e) const {
13.454 + typename MapTraits<MapImpl>::ConstReturnValue operator[](Edge e) const {
13.455 if (Parent::direction(e)) {
13.456 return forward_map[e];
13.457 } else {
13.458 @@ -1072,8 +1265,7 @@
13.459 }
13.460 }
13.461
13.462 - typename MapTraits<MapImpl>::ReturnValue
13.463 - operator[](const Edge& e) {
13.464 + typename MapTraits<MapImpl>::ReturnValue operator[](Edge e) {
13.465 if (Parent::direction(e)) {
13.466 return forward_map[e];
13.467 } else {
13.468 @@ -1086,19 +1278,55 @@
13.469 MapImpl forward_map, backward_map;
13.470
13.471 };
13.472 +
13.473 + public:
13.474 +
13.475 + template <typename _Value>
13.476 + class EdgeMap
13.477 + : public SubMapExtender<Adaptor, EdgeMapBase<_Value> >
13.478 + {
13.479 + public:
13.480 + typedef Adaptor Graph;
13.481 + typedef SubMapExtender<Adaptor, EdgeMapBase<_Value> > Parent;
13.482 +
13.483 + EdgeMap(const Graph& graph)
13.484 + : Parent(graph) {}
13.485 + EdgeMap(const Graph& graph, const _Value& value)
13.486 + : Parent(graph, value) {}
13.487 +
13.488 + EdgeMap& operator=(const EdgeMap& cmap) {
13.489 + return operator=<EdgeMap>(cmap);
13.490 + }
13.491 +
13.492 + template <typename CMap>
13.493 + EdgeMap& operator=(const CMap& cmap) {
13.494 + Parent::operator=(cmap);
13.495 + return *this;
13.496 + }
13.497 + };
13.498
13.499 template <typename _Value>
13.500 - class UEdgeMap : public _Graph::template EdgeMap<_Value> {
13.501 + class UEdgeMap : public Graph::template EdgeMap<_Value> {
13.502 public:
13.503 +
13.504 + typedef typename Graph::template EdgeMap<_Value> Parent;
13.505 +
13.506 + explicit UEdgeMap(const Adaptor& ga)
13.507 + : Parent(*ga.graph) {}
13.508
13.509 - typedef typename _Graph::template EdgeMap<_Value> Parent;
13.510 + UEdgeMap(const Adaptor& ga, const _Value& value)
13.511 + : Parent(*ga.graph, value) {}
13.512
13.513 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g)
13.514 - : Parent(*(g.graph)) {}
13.515 + UEdgeMap& operator=(const UEdgeMap& cmap) {
13.516 + return operator=<UEdgeMap>(cmap);
13.517 + }
13.518
13.519 - UEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, const _Value& a)
13.520 - : Parent(*(g.graph), a) {}
13.521 -
13.522 + template <typename CMap>
13.523 + UEdgeMap& operator=(const CMap& cmap) {
13.524 + Parent::operator=(cmap);
13.525 + return *this;
13.526 + }
13.527 +
13.528 };
13.529
13.530 };
14.1 --- a/lemon/graph_utils.h Mon Apr 03 09:24:38 2006 +0000
14.2 +++ b/lemon/graph_utils.h Mon Apr 03 09:45:23 2006 +0000
14.3 @@ -48,8 +48,7 @@
14.4
14.5 ///This \c \#define creates convenience typedefs for the following types
14.6 ///of \c Graph: \c Node, \c NodeIt, \c Edge, \c EdgeIt, \c InEdgeIt,
14.7 - ///\c OutEdgeIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
14.8 - ///\c BoolEdgeMap, \c IntEdgeMap, \c DoubleEdgeMap.
14.9 + ///\c OutEdgeIt
14.10 ///\note If \c G it a template parameter, it should be used in this way.
14.11 ///\code
14.12 /// GRAPH_TYPEDEFS(typename G)
14.13 @@ -64,19 +63,12 @@
14.14 typedef Graph:: EdgeIt EdgeIt; \
14.15 typedef Graph:: InEdgeIt InEdgeIt; \
14.16 typedef Graph::OutEdgeIt OutEdgeIt;
14.17 -// typedef Graph::template NodeMap<bool> BoolNodeMap;
14.18 -// typedef Graph::template NodeMap<int> IntNodeMap;
14.19 -// typedef Graph::template NodeMap<double> DoubleNodeMap;
14.20 -// typedef Graph::template EdgeMap<bool> BoolEdgeMap;
14.21 -// typedef Graph::template EdgeMap<int> IntEdgeMap;
14.22 -// typedef Graph::template EdgeMap<double> DoubleEdgeMap;
14.23 -
14.24 +
14.25 ///Creates convenience typedefs for the undirected graph types and iterators
14.26
14.27 ///This \c \#define creates the same convenience typedefs as defined by
14.28 ///\ref GRAPH_TYPEDEFS(Graph) and three more, namely it creates
14.29 ///\c UEdge, \c UEdgeIt, \c IncEdgeIt,
14.30 - ///\c BoolUEdgeMap, \c IntUEdgeMap, \c DoubleUEdgeMap.
14.31 ///
14.32 ///\note If \c G it a template parameter, it should be used in this way.
14.33 ///\code
14.34 @@ -93,8 +85,25 @@
14.35 // typedef Graph::template UEdgeMap<bool> BoolUEdgeMap;
14.36 // typedef Graph::template UEdgeMap<int> IntUEdgeMap;
14.37 // typedef Graph::template UEdgeMap<double> DoubleUEdgeMap;
14.38 -
14.39
14.40 + ///\brief Creates convenience typedefs for the bipartite undirected graph
14.41 + ///types and iterators
14.42 +
14.43 + ///This \c \#define creates the same convenience typedefs as defined by
14.44 + ///\ref UGRAPH_TYPEDEFS(Graph) and two more, namely it creates
14.45 + ///\c ANodeIt, \c BNodeIt,
14.46 + ///
14.47 + ///\note If \c G it a template parameter, it should be used in this way.
14.48 + ///\code
14.49 + /// BPUGRAPH_TYPEDEFS(typename G)
14.50 + ///\endcode
14.51 + ///
14.52 + ///\warning There are no typedefs for the graph maps because of the lack of
14.53 + ///template typedefs in C++.
14.54 +#define BPUGRAPH_TYPEDEFS(Graph) \
14.55 + UGRAPH_TYPEDEFS(Graph) \
14.56 + typedef Graph::ANodeIt ANodeIt; \
14.57 + typedef Graph::BNodeIt BNodeIt;
14.58
14.59 /// \brief Function to count the items in the graph.
14.60 ///
14.61 @@ -430,7 +439,7 @@
14.62 bool b;
14.63 if (u != v) {
14.64 if (e == INVALID) {
14.65 - g.firstInc(e, u, b);
14.66 + g.firstInc(e, b, u);
14.67 } else {
14.68 b = g.source(e) == u;
14.69 g.nextInc(e, b);
14.70 @@ -440,7 +449,7 @@
14.71 }
14.72 } else {
14.73 if (e == INVALID) {
14.74 - g.firstInc(e, u, b);
14.75 + g.firstInc(e, b, u);
14.76 } else {
14.77 b = true;
14.78 g.nextInc(e, b);
14.79 @@ -485,11 +494,11 @@
14.80 /// }
14.81 ///\endcode
14.82 template <typename Graph>
14.83 - inline typename Graph::UEdge findEdge(const Graph &g,
14.84 - typename Graph::Node u,
14.85 - typename Graph::Node v,
14.86 - typename Graph::UEdge prev = INVALID) {
14.87 - return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, prev);
14.88 + inline typename Graph::UEdge findUEdge(const Graph &g,
14.89 + typename Graph::Node u,
14.90 + typename Graph::Node v,
14.91 + typename Graph::UEdge p = INVALID) {
14.92 + return _graph_utils_bits::FindUEdgeSelector<Graph>::find(g, u, v, p);
14.93 }
14.94
14.95 /// \brief Iterator for iterating on uedges connected the same nodes.
15.1 --- a/lemon/iterable_maps.h Mon Apr 03 09:24:38 2006 +0000
15.2 +++ b/lemon/iterable_maps.h Mon Apr 03 09:45:23 2006 +0000
15.3 @@ -20,6 +20,7 @@
15.4 #include <lemon/bits/invalid.h>
15.5
15.6 #include <lemon/bits/default_map.h>
15.7 +#include <lemon/bits/map_extender.h>
15.8
15.9 #include <vector>
15.10 #include <map>
15.11 @@ -400,12 +401,11 @@
15.12 /// \param _Item One of the graph's item type, the key of the map.
15.13 template <typename _Graph, typename _Item>
15.14 class IterableIntMap
15.15 - : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.16 - IterableIntMapNode<_Item> > {
15.17 + : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.18 + IterableIntMapNode<_Item> > >{
15.19 public:
15.20 - typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.21 - IterableIntMapNode<_Item> >
15.22 - Parent;
15.23 + typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.24 + IterableIntMapNode<_Item> > > Parent;
15.25
15.26 /// The key type
15.27 typedef _Item Key;
15.28 @@ -689,11 +689,12 @@
15.29 /// \param _Value Any comparable value type.
15.30 template <typename _Graph, typename _Item, typename _Value>
15.31 class IterableValueMap
15.32 - : protected DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.33 - IterableValueMapNode<_Item, _Value> > {
15.34 + : protected MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.35 + IterableValueMapNode<_Item, _Value> > >{
15.36 public:
15.37 - typedef DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.38 - IterableValueMapNode<_Item, _Value> > Parent;
15.39 + typedef MapExtender<DefaultMap<_Graph, _Item, _iterable_maps_bits::
15.40 + IterableValueMapNode<_Item, _Value> > >
15.41 + Parent;
15.42
15.43 /// The key type
15.44 typedef _Item Key;
15.45 @@ -702,10 +703,6 @@
15.46 /// The graph type
15.47 typedef _Graph Graph;
15.48
15.49 - protected:
15.50 -
15.51 - typedef typename ItemSetTraits<_Graph, Key>::ItemIt KeyIt;
15.52 -
15.53 public:
15.54
15.55 /// \brief Constructor of the Map with a given value.
15.56 @@ -715,7 +712,7 @@
15.57 const Value& value = Value())
15.58 : Parent(graph, _iterable_maps_bits::
15.59 IterableValueMapNode<_Item, _Value>(value)) {
15.60 - for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) {
15.61 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
15.62 lace(it);
15.63 }
15.64 }
15.65 @@ -903,7 +900,7 @@
15.66
15.67 virtual void build() {
15.68 Parent::build();
15.69 - for (KeyIt it(*Parent::getGraph()); it != INVALID; ++it) {
15.70 + for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
15.71 lace(it);
15.72 }
15.73 }
16.1 --- a/lemon/list_graph.h Mon Apr 03 09:24:38 2006 +0000
16.2 +++ b/lemon/list_graph.h Mon Apr 03 09:45:23 2006 +0000
16.3 @@ -66,7 +66,7 @@
16.4 protected:
16.5
16.6 int id;
16.7 - Node(int pid) { id = pid;}
16.8 + explicit Node(int pid) { id = pid;}
16.9
16.10 public:
16.11 Node() {}
16.12 @@ -81,7 +81,7 @@
16.13 protected:
16.14
16.15 int id;
16.16 - Edge(int pid) { id = pid;}
16.17 + explicit Edge(int pid) { id = pid;}
16.18
16.19 public:
16.20 Edge() {}
16.21 @@ -110,8 +110,8 @@
16.22 ///\sa id(Edge)
16.23 int maxEdgeId() const { return edges.size()-1; }
16.24
16.25 - Node source(Edge e) const { return edges[e.id].source; }
16.26 - Node target(Edge e) const { return edges[e.id].target; }
16.27 + Node source(Edge e) const { return Node(edges[e.id].source); }
16.28 + Node target(Edge e) const { return Node(edges[e.id].target); }
16.29
16.30
16.31 void first(Node& node) const {
16.32 @@ -676,7 +676,7 @@
16.33 protected:
16.34 int id;
16.35
16.36 - Node(int _id) : id(_id) {}
16.37 + explicit Node(int _id) : id(_id) {}
16.38 public:
16.39 Node() {}
16.40 Node(Invalid) { id = -1; }
16.41 @@ -690,7 +690,7 @@
16.42 protected:
16.43 int id;
16.44
16.45 - Edge(int _id) { id = _id;}
16.46 + explicit Edge(int _id) { id = _id;}
16.47 public:
16.48 Edge() {}
16.49 Edge (Invalid) { id = -1; }
17.1 --- a/lemon/smart_graph.h Mon Apr 03 09:24:38 2006 +0000
17.2 +++ b/lemon/smart_graph.h Mon Apr 03 09:45:23 2006 +0000
17.3 @@ -575,6 +575,14 @@
17.4 edges.clear();
17.5 }
17.6
17.7 + typedef True NodeNumTag;
17.8 + int nodeNum() const { return aNodes.size() + bNodes.size(); }
17.9 + int aNodeNum() const { return aNodes.size(); }
17.10 + int bNodeNum() const { return bNodes.size(); }
17.11 +
17.12 + typedef True EdgeNumTag;
17.13 + int edgeNum() const { return edges.size(); }
17.14 +
17.15 };
17.16
17.17
18.1 --- a/lemon/ugraph_adaptor.h Mon Apr 03 09:24:38 2006 +0000
18.2 +++ b/lemon/ugraph_adaptor.h Mon Apr 03 09:45:23 2006 +0000
18.3 @@ -101,6 +101,7 @@
18.4
18.5 typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
18.6 int edgeNum() const { return graph->edgeNum(); }
18.7 + int uEdgeNum() const { return graph->uEdgeNum(); }
18.8
18.9 typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
18.10 Edge findEdge(const Node& source, const Node& target,
18.11 @@ -118,15 +119,28 @@
18.12 }
18.13
18.14 void erase(const Node& i) const { graph->erase(i); }
18.15 - void erase(const Edge& i) const { graph->erase(i); }
18.16 + void erase(const UEdge& i) const { graph->erase(i); }
18.17
18.18 void clear() const { graph->clear(); }
18.19
18.20 + bool direction(const Edge& e) const { return graph->direction(e); }
18.21 + Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
18.22 +
18.23 int id(const Node& v) const { return graph->id(v); }
18.24 + int id(const Edge& e) const { return graph->id(e); }
18.25 int id(const UEdge& e) const { return graph->id(e); }
18.26
18.27 - bool direction(const Edge& e) const { return graph->direction(e); }
18.28 - Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
18.29 + Node fromNodeId(int id) const {
18.30 + return graph->fromNodeId(id);
18.31 + }
18.32 +
18.33 + Edge fromEdgeId(int id) const {
18.34 + return graph->fromEdgeId(id);
18.35 + }
18.36 +
18.37 + UEdge fromUEdgeId(int id) const {
18.38 + return graph->fromUEdgeId(id);
18.39 + }
18.40
18.41 int maxNodeId() const {
18.42 return graph->maxNodeId();
18.43 @@ -173,14 +187,10 @@
18.44
18.45 template <typename CMap>
18.46 NodeMap& operator=(const CMap& cmap) {
18.47 - checkConcept<concept::ReadMap<Node, _Value>, CMap>();
18.48 - const typename Parent::Graph* graph = Parent::getGraph();
18.49 - Node it;
18.50 - for (graph->first(it); it != INVALID; graph->next(it)) {
18.51 - Parent::set(it, cmap[it]);
18.52 - }
18.53 - return *this;
18.54 + Parent::operator=(cmap);
18.55 + return *this;
18.56 }
18.57 +
18.58 };
18.59
18.60 template <typename _Value>
18.61 @@ -198,12 +208,7 @@
18.62
18.63 template <typename CMap>
18.64 EdgeMap& operator=(const CMap& cmap) {
18.65 - checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
18.66 - const typename Parent::Graph* graph = Parent::getGraph();
18.67 - Edge it;
18.68 - for (graph->first(it); it != INVALID; graph->next(it)) {
18.69 - Parent::set(it, cmap[it]);
18.70 - }
18.71 + Parent::operator=(cmap);
18.72 return *this;
18.73 }
18.74 };
18.75 @@ -223,13 +228,8 @@
18.76
18.77 template <typename CMap>
18.78 UEdgeMap& operator=(const CMap& cmap) {
18.79 - checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
18.80 - const typename Parent::Graph* graph = Parent::getGraph();
18.81 - UEdge it;
18.82 - for (graph->first(it); it != INVALID; graph->next(it)) {
18.83 - Parent::set(it, cmap[it]);
18.84 - }
18.85 - return *this;
18.86 + Parent::operator=(cmap);
18.87 + return *this;
18.88 }
18.89 };
18.90
18.91 @@ -254,6 +254,7 @@
18.92 class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
18.93 public:
18.94 typedef _UGraph Graph;
18.95 + typedef SubUGraphAdaptorBase Adaptor;
18.96 typedef UGraphAdaptorBase<_UGraph> Parent;
18.97 protected:
18.98
18.99 @@ -416,6 +417,85 @@
18.100 }
18.101 return uedge;
18.102 }
18.103 +
18.104 + template <typename _Value>
18.105 + class NodeMap
18.106 + : public SubMapExtender<Adaptor,
18.107 + typename Parent::template NodeMap<_Value> >
18.108 + {
18.109 + public:
18.110 + typedef Adaptor Graph;
18.111 + typedef SubMapExtender<Adaptor, typename Parent::
18.112 + template NodeMap<_Value> > Parent;
18.113 +
18.114 + NodeMap(const Graph& graph)
18.115 + : Parent(graph) {}
18.116 + NodeMap(const Graph& graph, const _Value& value)
18.117 + : Parent(graph, value) {}
18.118 +
18.119 + NodeMap& operator=(const NodeMap& cmap) {
18.120 + return operator=<NodeMap>(cmap);
18.121 + }
18.122 +
18.123 + template <typename CMap>
18.124 + NodeMap& operator=(const CMap& cmap) {
18.125 + Parent::operator=(cmap);
18.126 + return *this;
18.127 + }
18.128 + };
18.129 +
18.130 + template <typename _Value>
18.131 + class EdgeMap
18.132 + : public SubMapExtender<Adaptor,
18.133 + typename Parent::template EdgeMap<_Value> >
18.134 + {
18.135 + public:
18.136 + typedef Adaptor Graph;
18.137 + typedef SubMapExtender<Adaptor, typename Parent::
18.138 + template EdgeMap<_Value> > Parent;
18.139 +
18.140 + EdgeMap(const Graph& graph)
18.141 + : Parent(graph) {}
18.142 + EdgeMap(const Graph& graph, const _Value& value)
18.143 + : Parent(graph, value) {}
18.144 +
18.145 + EdgeMap& operator=(const EdgeMap& cmap) {
18.146 + return operator=<EdgeMap>(cmap);
18.147 + }
18.148 +
18.149 + template <typename CMap>
18.150 + EdgeMap& operator=(const CMap& cmap) {
18.151 + Parent::operator=(cmap);
18.152 + return *this;
18.153 + }
18.154 + };
18.155 +
18.156 + template <typename _Value>
18.157 + class UEdgeMap
18.158 + : public SubMapExtender<Adaptor,
18.159 + typename Parent::template UEdgeMap<_Value> >
18.160 + {
18.161 + public:
18.162 + typedef Adaptor Graph;
18.163 + typedef SubMapExtender<Adaptor, typename Parent::
18.164 + template UEdgeMap<_Value> > Parent;
18.165 +
18.166 + UEdgeMap(const Graph& graph)
18.167 + : Parent(graph) {}
18.168 + UEdgeMap(const Graph& graph, const _Value& value)
18.169 + : Parent(graph, value) {}
18.170 +
18.171 + UEdgeMap& operator=(const UEdgeMap& cmap) {
18.172 + return operator=<UEdgeMap>(cmap);
18.173 + }
18.174 +
18.175 + template <typename CMap>
18.176 + UEdgeMap& operator=(const CMap& cmap) {
18.177 + Parent::operator=(cmap);
18.178 + return *this;
18.179 + }
18.180 + };
18.181 +
18.182 };
18.183
18.184 template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
18.185 @@ -423,6 +503,7 @@
18.186 : public UGraphAdaptorBase<_UGraph> {
18.187 public:
18.188 typedef _UGraph Graph;
18.189 + typedef SubUGraphAdaptorBase Adaptor;
18.190 typedef UGraphAdaptorBase<_UGraph> Parent;
18.191 protected:
18.192 NodeFilterMap* node_filter_map;
18.193 @@ -559,6 +640,84 @@
18.194 }
18.195 return uedge;
18.196 }
18.197 +
18.198 + template <typename _Value>
18.199 + class NodeMap
18.200 + : public SubMapExtender<Adaptor,
18.201 + typename Parent::template NodeMap<_Value> >
18.202 + {
18.203 + public:
18.204 + typedef Adaptor Graph;
18.205 + typedef SubMapExtender<Adaptor, typename Parent::
18.206 + template NodeMap<_Value> > Parent;
18.207 +
18.208 + NodeMap(const Graph& graph)
18.209 + : Parent(graph) {}
18.210 + NodeMap(const Graph& graph, const _Value& value)
18.211 + : Parent(graph, value) {}
18.212 +
18.213 + NodeMap& operator=(const NodeMap& cmap) {
18.214 + return operator=<NodeMap>(cmap);
18.215 + }
18.216 +
18.217 + template <typename CMap>
18.218 + NodeMap& operator=(const CMap& cmap) {
18.219 + Parent::operator=(cmap);
18.220 + return *this;
18.221 + }
18.222 + };
18.223 +
18.224 + template <typename _Value>
18.225 + class EdgeMap
18.226 + : public SubMapExtender<Adaptor,
18.227 + typename Parent::template EdgeMap<_Value> >
18.228 + {
18.229 + public:
18.230 + typedef Adaptor Graph;
18.231 + typedef SubMapExtender<Adaptor, typename Parent::
18.232 + template EdgeMap<_Value> > Parent;
18.233 +
18.234 + EdgeMap(const Graph& graph)
18.235 + : Parent(graph) {}
18.236 + EdgeMap(const Graph& graph, const _Value& value)
18.237 + : Parent(graph, value) {}
18.238 +
18.239 + EdgeMap& operator=(const EdgeMap& cmap) {
18.240 + return operator=<EdgeMap>(cmap);
18.241 + }
18.242 +
18.243 + template <typename CMap>
18.244 + EdgeMap& operator=(const CMap& cmap) {
18.245 + Parent::operator=(cmap);
18.246 + return *this;
18.247 + }
18.248 + };
18.249 +
18.250 + template <typename _Value>
18.251 + class UEdgeMap
18.252 + : public SubMapExtender<Adaptor,
18.253 + typename Parent::template UEdgeMap<_Value> >
18.254 + {
18.255 + public:
18.256 + typedef Adaptor Graph;
18.257 + typedef SubMapExtender<Adaptor, typename Parent::
18.258 + template UEdgeMap<_Value> > Parent;
18.259 +
18.260 + UEdgeMap(const Graph& graph)
18.261 + : Parent(graph) {}
18.262 + UEdgeMap(const Graph& graph, const _Value& value)
18.263 + : Parent(graph, value) {}
18.264 +
18.265 + UEdgeMap& operator=(const UEdgeMap& cmap) {
18.266 + return operator=<UEdgeMap>(cmap);
18.267 + }
18.268 +
18.269 + template <typename CMap>
18.270 + UEdgeMap& operator=(const CMap& cmap) {
18.271 + Parent::operator=(cmap);
18.272 + return *this;
18.273 + }
18.274 + };
18.275 };
18.276
18.277 /// \ingroup graph_adaptors
18.278 @@ -678,7 +837,6 @@
18.279 return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
18.280 }
18.281
18.282 -
18.283 /// \brief An adaptor for hiding undirected edges from an undirected graph.
18.284 ///
18.285 /// \warning Graph adaptors are in even more experimental state
18.286 @@ -704,12 +862,14 @@
18.287 }
18.288
18.289 public:
18.290 +
18.291 EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
18.292 Parent(), const_true_map(true) {
18.293 Parent::setGraph(_graph);
18.294 Parent::setNodeFilterMap(const_true_map);
18.295 Parent::setUEdgeFilterMap(_uedge_filter_map);
18.296 }
18.297 +
18.298 };
18.299
18.300 template<typename UGraph, typename EdgeFilterMap>
18.301 @@ -837,21 +997,48 @@
18.302 template <typename _Value>
18.303 class NodeMap : public _UGraph::template NodeMap<_Value> {
18.304 public:
18.305 +
18.306 typedef typename _UGraph::template NodeMap<_Value> Parent;
18.307 +
18.308 explicit NodeMap(const DirUGraphAdaptorBase& ga)
18.309 - : Parent(*ga.graph) { }
18.310 + : Parent(*ga.graph) {}
18.311 +
18.312 NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
18.313 - : Parent(*ga.graph, value) { }
18.314 + : Parent(*ga.graph, value) {}
18.315 +
18.316 + NodeMap& operator=(const NodeMap& cmap) {
18.317 + return operator=<NodeMap>(cmap);
18.318 + }
18.319 +
18.320 + template <typename CMap>
18.321 + NodeMap& operator=(const CMap& cmap) {
18.322 + Parent::operator=(cmap);
18.323 + return *this;
18.324 + }
18.325 +
18.326 };
18.327
18.328 template <typename _Value>
18.329 class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
18.330 public:
18.331 +
18.332 typedef typename _UGraph::template UEdgeMap<_Value> Parent;
18.333 +
18.334 explicit EdgeMap(const DirUGraphAdaptorBase& ga)
18.335 : Parent(*ga.graph) { }
18.336 +
18.337 EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
18.338 : Parent(*ga.graph, value) { }
18.339 +
18.340 + EdgeMap& operator=(const EdgeMap& cmap) {
18.341 + return operator=<EdgeMap>(cmap);
18.342 + }
18.343 +
18.344 + template <typename CMap>
18.345 + EdgeMap& operator=(const CMap& cmap) {
18.346 + Parent::operator=(cmap);
18.347 + return *this;
18.348 + }
18.349 };
18.350
18.351