COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1820:22099ef840d7

Last change on this file since 1820:22099ef840d7 was 1820:22099ef840d7, checked in by Balazs Dezso, 14 years ago

Undir Bipartite Graph/Full? and Smart/ without concept, doc and concept
checking

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