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.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_BITS_BASE_EXTENDER_H
20 #define LEMON_BITS_BASE_EXTENDER_H
22 #include <lemon/bits/invalid.h>
23 #include <lemon/error.h>
25 #include <lemon/bits/map_extender.h>
26 #include <lemon/bits/default_map.h>
28 #include <lemon/concept_check.h>
29 #include <lemon/concept/maps.h>
33 ///\brief Extenders for the graph types
36 /// \ingroup graphbits
38 /// \brief BaseExtender for the UGraphs
39 template <typename Base>
40 class UGraphBaseExtender : public Base {
45 typedef typename Parent::Edge UEdge;
46 typedef typename Parent::Node Node;
48 typedef True UndirectedTag;
50 class Edge : public UEdge {
51 friend class UGraphBaseExtender;
56 Edge(const UEdge &ue, bool _forward) :
57 UEdge(ue), forward(_forward) {}
62 /// Invalid edge constructor
63 Edge(Invalid i) : UEdge(i), forward(true) {}
65 bool operator==(const Edge &that) const {
66 return forward==that.forward && UEdge(*this)==UEdge(that);
68 bool operator!=(const Edge &that) const {
69 return forward!=that.forward || UEdge(*this)!=UEdge(that);
71 bool operator<(const Edge &that) const {
72 return forward<that.forward ||
73 (!(that.forward<forward) && UEdge(*this)<UEdge(that));
81 /// Source of the given Edge.
82 Node source(const Edge &e) const {
83 return e.forward ? Parent::source(e) : Parent::target(e);
88 /// Target of the given Edge.
89 Node target(const Edge &e) const {
90 return e.forward ? Parent::target(e) : Parent::source(e);
93 /// \brief Directed edge from an undirected edge.
95 /// Returns a directed edge corresponding to the specified UEdge.
96 /// If the given bool is true the given undirected edge and the
97 /// returned edge have the same source node.
98 static Edge direct(const UEdge &ue, bool d) {
102 /// Returns whether the given directed edge is same orientation as the
103 /// corresponding undirected edge.
105 /// \todo reference to the corresponding point of the undirected graph
106 /// concept. "What does the direction of an undirected edge mean?"
107 static bool direction(const Edge &e) { return e.forward; }
113 void first(Edge &e) const {
118 void next(Edge &e) const {
128 void firstOut(Edge &e, const Node &n) const {
129 Parent::firstIn(e,n);
130 if( UEdge(e) != INVALID ) {
134 Parent::firstOut(e,n);
138 void nextOut(Edge &e) const {
140 Node n = Parent::target(e);
142 if( UEdge(e) == INVALID ) {
143 Parent::firstOut(e, n);
152 void firstIn(Edge &e, const Node &n) const {
153 Parent::firstOut(e,n);
154 if( UEdge(e) != INVALID ) {
158 Parent::firstIn(e,n);
162 void nextIn(Edge &e) const {
164 Node n = Parent::source(e);
166 if( UEdge(e) == INVALID ) {
167 Parent::firstIn(e, n);
176 void firstInc(UEdge &e, bool &d, const Node &n) const {
178 Parent::firstOut(e, n);
179 if (e != INVALID) return;
181 Parent::firstIn(e, n);
184 void nextInc(UEdge &e, bool &d) const {
186 Node s = Parent::source(e);
188 if (e != INVALID) return;
190 Parent::firstIn(e, s);
196 Node nodeFromId(int id) const {
197 return Parent::nodeFromId(id);
200 Edge edgeFromId(int id) const {
201 return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
204 UEdge uEdgeFromId(int id) const {
205 return Parent::edgeFromId(id >> 1);
208 int id(const Node &n) const {
209 return Parent::id(n);
212 int id(const UEdge &e) const {
213 return Parent::id(e);
216 int id(const Edge &e) const {
217 return 2 * Parent::id(e) + int(e.forward);
220 int maxNodeId() const {
221 return Parent::maxNodeId();
224 int maxEdgeId() const {
225 return 2 * Parent::maxEdgeId() + 1;
228 int maxUEdgeId() const {
229 return Parent::maxEdgeId();
233 int edgeNum() const {
234 return 2 * Parent::edgeNum();
237 int uEdgeNum() const {
238 return Parent::edgeNum();
241 Edge findEdge(Node source, Node target, Edge prev) const {
242 if (prev == INVALID) {
243 UEdge edge = Parent::findEdge(source, target);
244 if (edge != INVALID) return direct(edge, true);
245 edge = Parent::findEdge(target, source);
246 if (edge != INVALID) return direct(edge, false);
247 } else if (direction(prev)) {
248 UEdge edge = Parent::findEdge(source, target, prev);
249 if (edge != INVALID) return direct(edge, true);
250 edge = Parent::findEdge(target, source);
251 if (edge != INVALID) return direct(edge, false);
253 UEdge edge = Parent::findEdge(target, source, prev);
254 if (edge != INVALID) return direct(edge, false);
259 UEdge findUEdge(Node source, Node target, UEdge prev) const {
260 if (prev == INVALID) {
261 UEdge edge = Parent::findEdge(source, target);
262 if (edge != INVALID) return edge;
263 edge = Parent::findEdge(target, source);
264 if (edge != INVALID) return edge;
265 } else if (Parent::source(prev) == source) {
266 UEdge edge = Parent::findEdge(source, target, prev);
267 if (edge != INVALID) return edge;
268 edge = Parent::findEdge(target, source);
269 if (edge != INVALID) return edge;
271 UEdge edge = Parent::findEdge(target, source, prev);
272 if (edge != INVALID) return edge;
279 /// \ingroup graphbits
281 /// \brief BaseExtender for the BpUGraphs
282 template <typename Base>
283 class BpUGraphBaseExtender : public Base {
286 typedef BpUGraphBaseExtender Graph;
288 typedef typename Parent::Node Node;
289 typedef typename Parent::Edge UEdge;
297 class ANode : public Node {
298 friend class BpUGraphBaseExtender;
301 ANode(const Node& node) : Node(node) {
302 LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
303 typename Parent::NodeSetError());
305 ANode(Invalid) : Node(INVALID) {}
308 void first(ANode& node) const {
309 Parent::firstANode(static_cast<Node&>(node));
311 void next(ANode& node) const {
312 Parent::nextANode(static_cast<Node&>(node));
315 int id(const ANode& node) const {
316 return Parent::aNodeId(node);
319 class BNode : public Node {
320 friend class BpUGraphBaseExtender;
323 BNode(const Node& node) : Node(node) {
324 LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
325 typename Parent::NodeSetError());
327 BNode(Invalid) : Node(INVALID) {}
330 void first(BNode& node) const {
331 Parent::firstBNode(static_cast<Node&>(node));
333 void next(BNode& node) const {
334 Parent::nextBNode(static_cast<Node&>(node));
337 int id(const BNode& node) const {
338 return Parent::aNodeId(node);
341 Node source(const UEdge& edge) const {
344 Node target(const UEdge& edge) const {
348 void firstInc(UEdge& edge, bool& direction, const Node& node) const {
349 if (Parent::aNode(node)) {
350 Parent::firstOut(edge, node);
353 Parent::firstIn(edge, node);
354 direction = static_cast<UEdge&>(edge) == INVALID;
357 void nextInc(UEdge& edge, bool& direction) const {
359 Parent::nextOut(edge);
361 Parent::nextIn(edge);
362 if (edge == INVALID) direction = true;
366 int maxUEdgeId() const {
367 return Parent::maxEdgeId();
370 UEdge uEdgeFromId(int id) const {
371 return Parent::edgeFromId(id);
374 class Edge : public UEdge {
375 friend class BpUGraphBaseExtender;
379 Edge(const UEdge& edge, bool _forward)
380 : UEdge(edge), forward(_forward) {}
384 Edge (Invalid) : UEdge(INVALID), forward(true) {}
385 bool operator==(const Edge& i) const {
386 return UEdge::operator==(i) && forward == i.forward;
388 bool operator!=(const Edge& i) const {
389 return UEdge::operator!=(i) || forward != i.forward;
391 bool operator<(const Edge& i) const {
392 return UEdge::operator<(i) ||
393 (!(i.forward<forward) && UEdge(*this)<UEdge(i));
397 void first(Edge& edge) const {
398 Parent::first(static_cast<UEdge&>(edge));
402 void next(Edge& edge) const {
404 Parent::next(static_cast<UEdge&>(edge));
406 edge.forward = !edge.forward;
409 void firstOut(Edge& edge, const Node& node) const {
410 if (Parent::aNode(node)) {
411 Parent::firstOut(edge, node);
414 Parent::firstIn(edge, node);
415 edge.forward = static_cast<UEdge&>(edge) == INVALID;
418 void nextOut(Edge& edge) const {
420 Parent::nextOut(edge);
422 Parent::nextIn(edge);
423 edge.forward = static_cast<UEdge&>(edge) == INVALID;
427 void firstIn(Edge& edge, const Node& node) const {
428 if (Parent::bNode(node)) {
429 Parent::firstIn(edge, node);
432 Parent::firstOut(edge, node);
433 edge.forward = static_cast<UEdge&>(edge) == INVALID;
436 void nextIn(Edge& edge) const {
438 Parent::nextIn(edge);
440 Parent::nextOut(edge);
441 edge.forward = static_cast<UEdge&>(edge) == INVALID;
445 Node source(const Edge& edge) const {
446 return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
448 Node target(const Edge& edge) const {
449 return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
452 int id(const Edge& edge) const {
453 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
455 Edge edgeFromId(int id) const {
456 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
458 int maxEdgeId() const {
459 return (Parent::maxId(UEdge()) << 1) + 1;
462 bool direction(const Edge& edge) const {
466 Edge direct(const UEdge& edge, bool direction) const {
467 return Edge(edge, direction);
470 int edgeNum() const {
471 return 2 * Parent::edgeNum();
474 int uEdgeNum() const {
475 return Parent::edgeNum();