COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 14.7 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_GRAPH_EXTENDER_H
20#define LEMON_GRAPH_EXTENDER_H
21
22#include <lemon/invalid.h>
23#include <lemon/error.h>
24
25namespace lemon {
26
27  template <typename _Base>
28  class GraphExtender : public _Base {
29  public:
30
31    typedef _Base Parent;
32    typedef GraphExtender Graph;
33
34    typedef typename Parent::Node Node;
35    typedef typename Parent::Edge Edge;
36
37    int maxId(Node) const {
38      return Parent::maxNodeId();
39    }
40
41    int maxId(Edge) const {
42      return Parent::maxEdgeId();
43    }
44
45    Node fromId(int id, Node) const {
46      return Parent::nodeFromId(id);
47    }
48
49    Edge fromId(int id, Edge) const {
50      return Parent::edgeFromId(id);
51    }
52
53    Node oppositeNode(const Node &n, const Edge &e) const {
54      if (n == Parent::source(e))
55        return Parent::target(e);
56      else if(n==Parent::target(e))
57        return Parent::source(e);
58      else
59        return INVALID;
60    }
61
62  };
63
64  template <typename _Base>
65  class UGraphExtender : public _Base {
66    typedef _Base Parent;
67    typedef UGraphExtender Graph;
68
69  public:
70
71    typedef typename Parent::Edge UEdge;
72    typedef typename Parent::Node Node;
73
74    class Edge : public UEdge {
75      friend class UGraphExtender;
76
77    protected:
78      // FIXME: Marci use opposite logic in his graph adaptors. It would
79      // be reasonable to syncronize...
80      bool forward;
81
82      Edge(const UEdge &ue, bool _forward) :
83        UEdge(ue), forward(_forward) {}
84
85    public:
86      Edge() {}
87
88      /// Invalid edge constructor
89      Edge(Invalid i) : UEdge(i), forward(true) {}
90
91      bool operator==(const Edge &that) const {
92        return forward==that.forward && UEdge(*this)==UEdge(that);
93      }
94      bool operator!=(const Edge &that) const {
95        return forward!=that.forward || UEdge(*this)!=UEdge(that);
96      }
97      bool operator<(const Edge &that) const {
98        return forward<that.forward ||
99          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
100      }
101    };
102
103
104    /// \brief Edge of opposite direction.
105    ///
106    /// Returns the Edge of opposite direction.
107    Edge oppositeEdge(const Edge &e) const {
108      return Edge(e,!e.forward);
109    }
110
111  public:
112    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
113    /// or something???
114    using Parent::source;
115
116    /// Source of the given Edge.
117    Node source(const Edge &e) const {
118      return e.forward ? Parent::source(e) : Parent::target(e);
119    }
120
121    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
122    /// or something???
123    using Parent::target;
124
125    /// Target of the given Edge.
126    Node target(const Edge &e) const {
127      return e.forward ? Parent::target(e) : Parent::source(e);
128    }
129
130    Node oppositeNode(const Node &n, const UEdge &e) const {
131      if( n == Parent::source(e))
132        return Parent::target(e);
133      else if( n == Parent::target(e))
134        return Parent::source(e);
135      else
136        return INVALID;
137    }
138
139    /// \brief Directed edge from an undirected edge and a source node.
140    ///
141    /// Returns a (directed) Edge corresponding to the specified UEdge
142    /// and source Node.
143    ///
144    Edge direct(const UEdge &ue, const Node &s) const {
145      return Edge(ue, s == source(ue));
146    }
147
148    /// \brief Directed edge from an undirected edge.
149    ///
150    /// Returns a directed edge corresponding to the specified UEdge.
151    /// If the given bool is true the given undirected edge and the
152    /// returned edge have the same source node.
153    Edge direct(const UEdge &ue, bool d) const {
154      return Edge(ue, d);
155    }
156
157    /// Returns whether the given directed edge is same orientation as the
158    /// corresponding undirected edge.
159    ///
160    /// \todo reference to the corresponding point of the undirected graph
161    /// concept. "What does the direction of an undirected edge mean?"
162    bool direction(const Edge &e) const { return e.forward; }
163
164
165    using Parent::first;
166    void first(Edge &e) const {
167      Parent::first(e);
168      e.forward=true;
169    }
170
171    using Parent::next;
172    void next(Edge &e) const {
173      if( e.forward ) {
174        e.forward = false;
175      }
176      else {
177        Parent::next(e);
178        e.forward = true;
179      }
180    }
181
182  public:
183
184    void firstOut(Edge &e, const Node &n) const {
185      Parent::firstIn(e,n);
186      if( UEdge(e) != INVALID ) {
187        e.forward = false;
188      }
189      else {
190        Parent::firstOut(e,n);
191        e.forward = true;
192      }
193    }
194    void nextOut(Edge &e) const {
195      if( ! e.forward ) {
196        Node n = Parent::target(e);
197        Parent::nextIn(e);
198        if( UEdge(e) == INVALID ) {
199          Parent::firstOut(e, n);
200          e.forward = true;
201        }
202      }
203      else {
204        Parent::nextOut(e);
205      }
206    }
207
208    void firstIn(Edge &e, const Node &n) const {
209      Parent::firstOut(e,n);
210      if( UEdge(e) != INVALID ) {
211        e.forward = false;
212      }
213      else {
214        Parent::firstIn(e,n);
215        e.forward = true;
216      }
217    }
218    void nextIn(Edge &e) const {
219      if( ! e.forward ) {
220        Node n = Parent::source(e);
221        Parent::nextOut(e);
222        if( UEdge(e) == INVALID ) {
223          Parent::firstIn(e, n);
224          e.forward = true;
225        }
226      }
227      else {
228        Parent::nextIn(e);
229      }
230    }
231
232    void firstInc(UEdge &e, const Node &n) const {
233      Parent::firstOut(e, n);
234      if (e != INVALID) return;
235      Parent::firstIn(e, n);
236    }
237    void nextInc(UEdge &e, const Node &n) const {
238      if (Parent::source(e) == n) {
239        Parent::nextOut(e);
240        if (e != INVALID) return;
241        Parent::firstIn(e, n);
242      } else {
243        Parent::nextIn(e);
244      }
245    }
246
247    void firstInc(UEdge &e, bool &d, const Node &n) const {
248      d = true;
249      Parent::firstOut(e, n);
250      if (e != INVALID) return;
251      d = false;
252      Parent::firstIn(e, n);
253    }
254    void nextInc(UEdge &e, bool &d) const {
255      if (d) {
256        Node s = Parent::source(e);
257        Parent::nextOut(e);
258        if (e != INVALID) return;
259        d = false;
260        Parent::firstIn(e, s);
261      } else {
262        Parent::nextIn(e);
263      }
264    }
265
266    // Miscellaneous stuff:
267
268    /// \todo these methods (id, maxEdgeId) should be moved into separate
269    /// Extender
270
271    // using Parent::id;
272    // Using "using" is not a good idea, cause it could be that there is
273    // no "id" in Parent...
274
275    int id(const Node &n) const {
276      return Parent::id(n);
277    }
278
279    int id(const UEdge &e) const {
280      return Parent::id(e);
281    }
282
283    int id(const Edge &e) const {
284      return 2 * Parent::id(e) + int(e.forward);
285    }
286
287    int maxNodeId() const {
288      return Parent::maxNodeId();
289    }
290
291    int maxEdgeId() const {
292      return 2 * Parent::maxEdgeId() + 1;
293    }
294
295    int maxUEdgeId() const {
296      return Parent::maxEdgeId();
297    }
298
299    int maxId(Node) const {
300      return maxNodeId();
301    }
302
303    int maxId(Edge) const {
304      return maxEdgeId();
305    }
306    int maxId(UEdge) const {
307      return maxUEdgeId();
308    }
309
310    int edgeNum() const {
311      return 2 * Parent::edgeNum();
312    }
313
314    int uEdgeNum() const {
315      return Parent::edgeNum();
316    }
317
318    Node nodeFromId(int id) const {
319      return Parent::nodeFromId(id);
320    }
321
322    Edge edgeFromId(int id) const {
323      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
324    }
325
326    UEdge uEdgeFromId(int id) const {
327      return Parent::edgeFromId(id >> 1);
328    }
329
330    Node fromId(int id, Node) const {
331      return nodeFromId(id);
332    }
333
334    Edge fromId(int id, Edge) const {
335      return edgeFromId(id);
336    }
337
338    UEdge fromId(int id, UEdge) const {
339      return uEdgeFromId(id);
340    }
341
342
343    Edge findEdge(Node source, Node target, Edge prev) const {
344      if (prev == INVALID) {
345        UEdge edge = Parent::findEdge(source, target);
346        if (edge != INVALID) return direct(edge, true);
347        edge = Parent::findEdge(target, source);
348        if (edge != INVALID) return direct(edge, false);
349      } else if (direction(prev)) {
350        UEdge edge = Parent::findEdge(source, target, prev);
351        if (edge != INVALID) return direct(edge, true);
352        edge = Parent::findEdge(target, source);
353        if (edge != INVALID) return direct(edge, false);       
354      } else {
355        UEdge edge = Parent::findEdge(target, source, prev);
356        if (edge != INVALID) return direct(edge, false);             
357      }
358      return INVALID;
359    }
360
361    UEdge findUEdge(Node source, Node target, UEdge prev) const {
362      if (prev == INVALID) {
363        UEdge edge = Parent::findEdge(source, target);
364        if (edge != INVALID) return edge;
365        edge = Parent::findEdge(target, source);
366        if (edge != INVALID) return edge;
367      } else if (Parent::source(prev) == source) {
368        UEdge edge = Parent::findEdge(source, target, prev);
369        if (edge != INVALID) return edge;
370        edge = Parent::findEdge(target, source);
371        if (edge != INVALID) return edge;       
372      } else {
373        UEdge edge = Parent::findEdge(target, source, prev);
374        if (edge != INVALID) return edge;             
375      }
376      return INVALID;
377    }
378
379  };
380
381
382  template <typename _Base>
383  class BpUGraphExtender : public _Base {
384  public:
385    typedef _Base Parent;
386    typedef BpUGraphExtender Graph;
387
388    typedef typename Parent::Node Node;
389    typedef typename Parent::Edge UEdge;
390
391    using Parent::first;
392    using Parent::next;
393
394    using Parent::id;
395
396    Node source(const UEdge& edge) const {
397      return aNode(edge);
398    }
399    Node target(const UEdge& edge) const {
400      return bNode(edge);
401    }
402
403    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
404      if (Parent::aNode(node)) {
405        Parent::firstOut(edge, node);
406        direction = true;
407      } else {
408        Parent::firstIn(edge, node);
409        direction = static_cast<UEdge&>(edge) == INVALID;
410      }
411    }
412    void nextInc(UEdge& edge, bool& direction) const {
413      if (direction) {
414        Parent::nextOut(edge);
415      } else {
416        Parent::nextIn(edge);
417        if (edge == INVALID) direction = true;
418      }
419    }
420
421    int maxUEdgeId() const {
422      return Parent::maxEdgeId();
423    }
424
425    UEdge uEdgeFromId(int id) const {
426      return Parent::edgeFromId(id);
427    }
428
429    class Edge : public UEdge {
430      friend class BpUGraphExtender;
431    protected:
432      bool forward;
433
434      Edge(const UEdge& edge, bool _forward)
435        : UEdge(edge), forward(_forward) {}
436
437    public:
438      Edge() {}
439      Edge (Invalid) : UEdge(INVALID), forward(true) {}
440      bool operator==(const Edge& i) const {
441        return UEdge::operator==(i) && forward == i.forward;
442      }
443      bool operator!=(const Edge& i) const {
444        return UEdge::operator!=(i) || forward != i.forward;
445      }
446      bool operator<(const Edge& i) const {
447        return UEdge::operator<(i) ||
448          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
449      }
450    };
451
452    void first(Edge& edge) const {
453      Parent::first(static_cast<UEdge&>(edge));
454      edge.forward = true;
455    }
456
457    void next(Edge& edge) const {
458      if (!edge.forward) {
459        Parent::next(static_cast<UEdge&>(edge));
460      }
461      edge.forward = !edge.forward;
462    }
463
464    void firstOut(Edge& edge, const Node& node) const {
465      if (Parent::aNode(node)) {
466        Parent::firstOut(edge, node);
467        edge.forward = true;
468      } else {
469        Parent::firstIn(edge, node);
470        edge.forward = static_cast<UEdge&>(edge) == INVALID;
471      }
472    }
473    void nextOut(Edge& edge) const {
474      if (edge.forward) {
475        Parent::nextOut(edge);
476      } else {
477        Parent::nextIn(edge);
478        edge.forward = static_cast<UEdge&>(edge) == INVALID;
479      }
480    }
481
482    void firstIn(Edge& edge, const Node& node) const {
483      if (Parent::bNode(node)) {
484        Parent::firstIn(edge, node);
485        edge.forward = true;   
486      } else {
487        Parent::firstOut(edge, node);
488        edge.forward = static_cast<UEdge&>(edge) == INVALID;
489      }
490    }
491    void nextIn(Edge& edge) const {
492      if (edge.forward) {
493        Parent::nextIn(edge);
494      } else {
495        Parent::nextOut(edge);
496        edge.forward = static_cast<UEdge&>(edge) == INVALID;
497      }
498    }
499
500    Node source(const Edge& edge) const {
501      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
502    }
503    Node target(const Edge& edge) const {
504      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
505    }
506
507    bool direction(const Edge& edge) const {
508      return edge.forward;
509    }
510
511    Edge direct(const UEdge& edge, const Node& node) const {
512      return Edge(edge, node == Parent::source(edge));
513    }
514
515    Edge direct(const UEdge& edge, bool direction) const {
516      return Edge(edge, direction);
517    }
518
519    Node oppositeNode(const UEdge& edge, const Node& node) const {
520      return source(edge) == node ?
521        target(edge) : source(edge);
522    }
523
524    Edge oppositeEdge(const Edge& edge) const {
525      return Edge(edge, !edge.forward);
526    }
527
528    int id(const Edge& edge) const {
529      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
530    }
531    Edge edgeFromId(int id) const {
532      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
533    }
534    int maxEdgeId() const {
535      return (Parent::maxId(UEdge()) << 1) + 1;
536    }
537
538    class ANode : public Node {
539      friend class BpUGraphExtender;
540    public:
541      ANode() {}
542      ANode(const Node& node) : Node(node) {
543        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
544                     typename Parent::NodeSetError());
545      }
546      ANode(Invalid) : Node(INVALID) {}
547    };
548
549    void first(ANode& node) const {
550      Parent::firstANode(static_cast<Node&>(node));
551    }
552    void next(ANode& node) const {
553      Parent::nextANode(static_cast<Node&>(node));
554    }
555
556    int id(const ANode& node) const {
557      return Parent::aNodeId(node);
558    }
559
560    class BNode : public Node {
561      friend class BpUGraphExtender;
562    public:
563      BNode() {}
564      BNode(const Node& node) : Node(node) {
565        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
566                     typename Parent::NodeSetError());
567      }
568      BNode(Invalid) : Node(INVALID) {}
569    };
570
571    void first(BNode& node) const {
572      Parent::firstBNode(static_cast<Node&>(node));
573    }
574    void next(BNode& node) const {
575      Parent::nextBNode(static_cast<Node&>(node));
576    }
577 
578    int id(const BNode& node) const {
579      return Parent::aNodeId(node);
580    }
581
582
583
584    int maxId(Node) const {
585      return Parent::maxNodeId();
586    }
587    int maxId(BNode) const {
588      return Parent::maxBNodeId();
589    }
590    int maxId(ANode) const {
591      return Parent::maxANodeId();
592    }
593    int maxId(Edge) const {
594      return maxEdgeId();
595    }
596    int maxId(UEdge) const {
597      return maxUEdgeId();
598    }
599
600
601    Node fromId(int id, Node) const {
602      return Parent::nodeFromId(id);
603    }
604    ANode fromId(int id, ANode) const {
605      return Parent::fromANodeId(id);
606    }
607    BNode fromId(int id, BNode) const {
608      return Parent::fromBNodeId(id);
609    }
610    Edge fromId(int id, Edge) const {
611      return edgeFromId(id);
612    }
613    UEdge fromId(int id, UEdge) const {
614      return uEdgeFromId(id);
615    }
616
617  };
618
619}
620
621#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.