COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/base_extender.h @ 2031:080d51024ac5

Last change on this file since 2031:080d51024ac5 was 2031:080d51024ac5, checked in by Balazs Dezso, 14 years ago

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.

File size: 11.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BITS_BASE_EXTENDER_H
20#define LEMON_BITS_BASE_EXTENDER_H
21
22#include <lemon/bits/invalid.h>
23#include <lemon/error.h>
24
25#include <lemon/bits/map_extender.h>
26#include <lemon/bits/default_map.h>
27
28#include <lemon/concept_check.h>
29#include <lemon/concept/maps.h>
30
31///\ingroup graphbits
32///\file
33///\brief Extenders for the graph types
34namespace lemon {
35
36  /// \ingroup graphbits
37  ///
38  /// \brief BaseExtender for the UGraphs
39  template <typename Base>
40  class UGraphBaseExtender : public Base {
41
42  public:
43
44    typedef Base Parent;
45    typedef typename Parent::Edge UEdge;
46    typedef typename Parent::Node Node;
47
48    typedef True UndirectedTag;
49
50    class Edge : public UEdge {
51      friend class UGraphBaseExtender;
52
53    protected:
54      bool forward;
55
56      Edge(const UEdge &ue, bool _forward) :
57        UEdge(ue), forward(_forward) {}
58
59    public:
60      Edge() {}
61
62      /// Invalid edge constructor
63      Edge(Invalid i) : UEdge(i), forward(true) {}
64
65      bool operator==(const Edge &that) const {
66        return forward==that.forward && UEdge(*this)==UEdge(that);
67      }
68      bool operator!=(const Edge &that) const {
69        return forward!=that.forward || UEdge(*this)!=UEdge(that);
70      }
71      bool operator<(const Edge &that) const {
72        return forward<that.forward ||
73          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
74      }
75    };
76
77
78
79    using Parent::source;
80
81    /// Source of the given Edge.
82    Node source(const Edge &e) const {
83      return e.forward ? Parent::source(e) : Parent::target(e);
84    }
85
86    using Parent::target;
87
88    /// Target of the given Edge.
89    Node target(const Edge &e) const {
90      return e.forward ? Parent::target(e) : Parent::source(e);
91    }
92
93    /// \brief Directed edge from an undirected edge.
94    ///
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) {
99      return Edge(ue, d);
100    }
101
102    /// Returns whether the given directed edge is same orientation as the
103    /// corresponding undirected edge.
104    ///
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; }
108
109
110    using Parent::first;
111    using Parent::next;
112
113    void first(Edge &e) const {
114      Parent::first(e);
115      e.forward=true;
116    }
117
118    void next(Edge &e) const {
119      if( e.forward ) {
120        e.forward = false;
121      }
122      else {
123        Parent::next(e);
124        e.forward = true;
125      }
126    }
127
128    void firstOut(Edge &e, const Node &n) const {
129      Parent::firstIn(e,n);
130      if( UEdge(e) != INVALID ) {
131        e.forward = false;
132      }
133      else {
134        Parent::firstOut(e,n);
135        e.forward = true;
136      }
137    }
138    void nextOut(Edge &e) const {
139      if( ! e.forward ) {
140        Node n = Parent::target(e);
141        Parent::nextIn(e);
142        if( UEdge(e) == INVALID ) {
143          Parent::firstOut(e, n);
144          e.forward = true;
145        }
146      }
147      else {
148        Parent::nextOut(e);
149      }
150    }
151
152    void firstIn(Edge &e, const Node &n) const {
153      Parent::firstOut(e,n);
154      if( UEdge(e) != INVALID ) {
155        e.forward = false;
156      }
157      else {
158        Parent::firstIn(e,n);
159        e.forward = true;
160      }
161    }
162    void nextIn(Edge &e) const {
163      if( ! e.forward ) {
164        Node n = Parent::source(e);
165        Parent::nextOut(e);
166        if( UEdge(e) == INVALID ) {
167          Parent::firstIn(e, n);
168          e.forward = true;
169        }
170      }
171      else {
172        Parent::nextIn(e);
173      }
174    }
175
176    void firstInc(UEdge &e, bool &d, const Node &n) const {
177      d = true;
178      Parent::firstOut(e, n);
179      if (e != INVALID) return;
180      d = false;
181      Parent::firstIn(e, n);
182    }
183
184    void nextInc(UEdge &e, bool &d) const {
185      if (d) {
186        Node s = Parent::source(e);
187        Parent::nextOut(e);
188        if (e != INVALID) return;
189        d = false;
190        Parent::firstIn(e, s);
191      } else {
192        Parent::nextIn(e);
193      }
194    }
195
196    Node nodeFromId(int id) const {
197      return Parent::nodeFromId(id);
198    }
199
200    Edge edgeFromId(int id) const {
201      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
202    }
203
204    UEdge uEdgeFromId(int id) const {
205      return Parent::edgeFromId(id >> 1);
206    }
207
208    int id(const Node &n) const {
209      return Parent::id(n);
210    }
211
212    int id(const UEdge &e) const {
213      return Parent::id(e);
214    }
215
216    int id(const Edge &e) const {
217      return 2 * Parent::id(e) + int(e.forward);
218    }
219
220    int maxNodeId() const {
221      return Parent::maxNodeId();
222    }
223
224    int maxEdgeId() const {
225      return 2 * Parent::maxEdgeId() + 1;
226    }
227
228    int maxUEdgeId() const {
229      return Parent::maxEdgeId();
230    }
231
232
233    int edgeNum() const {
234      return 2 * Parent::edgeNum();
235    }
236
237    int uEdgeNum() const {
238      return Parent::edgeNum();
239    }
240
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);       
252      } else {
253        UEdge edge = Parent::findEdge(target, source, prev);
254        if (edge != INVALID) return direct(edge, false);             
255      }
256      return INVALID;
257    }
258
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;       
270      } else {
271        UEdge edge = Parent::findEdge(target, source, prev);
272        if (edge != INVALID) return edge;             
273      }
274      return INVALID;
275    }
276  };
277
278
279  /// \ingroup graphbits
280  ///
281  /// \brief BaseExtender for the BpUGraphs
282  template <typename Base>
283  class BpUGraphBaseExtender : public Base {
284  public:
285    typedef Base Parent;
286    typedef BpUGraphBaseExtender Graph;
287
288    typedef typename Parent::Node Node;
289    typedef typename Parent::Edge UEdge;
290
291
292    using Parent::first;
293    using Parent::next;
294
295    using Parent::id;
296
297    class ANode : public Node {
298      friend class BpUGraphBaseExtender;
299    public:
300      ANode() {}
301      ANode(const Node& node) : Node(node) {
302        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
303                     typename Parent::NodeSetError());
304      }
305      ANode(Invalid) : Node(INVALID) {}
306    };
307
308    void first(ANode& node) const {
309      Parent::firstANode(static_cast<Node&>(node));
310    }
311    void next(ANode& node) const {
312      Parent::nextANode(static_cast<Node&>(node));
313    }
314
315    int id(const ANode& node) const {
316      return Parent::aNodeId(node);
317    }
318
319    class BNode : public Node {
320      friend class BpUGraphBaseExtender;
321    public:
322      BNode() {}
323      BNode(const Node& node) : Node(node) {
324        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
325                     typename Parent::NodeSetError());
326      }
327      BNode(Invalid) : Node(INVALID) {}
328    };
329
330    void first(BNode& node) const {
331      Parent::firstBNode(static_cast<Node&>(node));
332    }
333    void next(BNode& node) const {
334      Parent::nextBNode(static_cast<Node&>(node));
335    }
336 
337    int id(const BNode& node) const {
338      return Parent::aNodeId(node);
339    }
340
341    Node source(const UEdge& edge) const {
342      return aNode(edge);
343    }
344    Node target(const UEdge& edge) const {
345      return bNode(edge);
346    }
347
348    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
349      if (Parent::aNode(node)) {
350        Parent::firstOut(edge, node);
351        direction = true;
352      } else {
353        Parent::firstIn(edge, node);
354        direction = static_cast<UEdge&>(edge) == INVALID;
355      }
356    }
357    void nextInc(UEdge& edge, bool& direction) const {
358      if (direction) {
359        Parent::nextOut(edge);
360      } else {
361        Parent::nextIn(edge);
362        if (edge == INVALID) direction = true;
363      }
364    }
365
366    int maxUEdgeId() const {
367      return Parent::maxEdgeId();
368    }
369
370    UEdge uEdgeFromId(int id) const {
371      return Parent::edgeFromId(id);
372    }
373
374    class Edge : public UEdge {
375      friend class BpUGraphBaseExtender;
376    protected:
377      bool forward;
378
379      Edge(const UEdge& edge, bool _forward)
380        : UEdge(edge), forward(_forward) {}
381
382    public:
383      Edge() {}
384      Edge (Invalid) : UEdge(INVALID), forward(true) {}
385      bool operator==(const Edge& i) const {
386        return UEdge::operator==(i) && forward == i.forward;
387      }
388      bool operator!=(const Edge& i) const {
389        return UEdge::operator!=(i) || forward != i.forward;
390      }
391      bool operator<(const Edge& i) const {
392        return UEdge::operator<(i) ||
393          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
394      }
395    };
396
397    void first(Edge& edge) const {
398      Parent::first(static_cast<UEdge&>(edge));
399      edge.forward = true;
400    }
401
402    void next(Edge& edge) const {
403      if (!edge.forward) {
404        Parent::next(static_cast<UEdge&>(edge));
405      }
406      edge.forward = !edge.forward;
407    }
408
409    void firstOut(Edge& edge, const Node& node) const {
410      if (Parent::aNode(node)) {
411        Parent::firstOut(edge, node);
412        edge.forward = true;
413      } else {
414        Parent::firstIn(edge, node);
415        edge.forward = static_cast<UEdge&>(edge) == INVALID;
416      }
417    }
418    void nextOut(Edge& edge) const {
419      if (edge.forward) {
420        Parent::nextOut(edge);
421      } else {
422        Parent::nextIn(edge);
423        edge.forward = static_cast<UEdge&>(edge) == INVALID;
424      }
425    }
426
427    void firstIn(Edge& edge, const Node& node) const {
428      if (Parent::bNode(node)) {
429        Parent::firstIn(edge, node);
430        edge.forward = true;   
431      } else {
432        Parent::firstOut(edge, node);
433        edge.forward = static_cast<UEdge&>(edge) == INVALID;
434      }
435    }
436    void nextIn(Edge& edge) const {
437      if (edge.forward) {
438        Parent::nextIn(edge);
439      } else {
440        Parent::nextOut(edge);
441        edge.forward = static_cast<UEdge&>(edge) == INVALID;
442      }
443    }
444
445    Node source(const Edge& edge) const {
446      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
447    }
448    Node target(const Edge& edge) const {
449      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
450    }
451
452    int id(const Edge& edge) const {
453      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
454    }
455    Edge edgeFromId(int id) const {
456      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
457    }
458    int maxEdgeId() const {
459      return (Parent::maxId(UEdge()) << 1) + 1;
460    }
461
462    bool direction(const Edge& edge) const {
463      return edge.forward;
464    }
465
466    Edge direct(const UEdge& edge, bool direction) const {
467      return Edge(edge, direction);
468    }
469
470    int edgeNum() const {
471      return 2 * Parent::edgeNum();
472    }
473
474    int uEdgeNum() const {
475      return Parent::edgeNum();
476    }
477
478  };
479
480}
481
482#endif
Note: See TracBrowser for help on using the repository browser.