COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_extender.h @ 1868:24bf4b8299e7

Last change on this file since 1868:24bf4b8299e7 was 1868:24bf4b8299e7, checked in by Balazs Dezso, 14 years ago

Bug fix in bipartite graph

File size: 15.2 KB
Line 
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>
22#include <lemon/error.h>
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
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        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
478      }
479    }
480
481    void firstIn(Edge& edge, const Node& node) const {
482      if (Parent::lower(node)) {
483        Parent::firstUp(edge, node);
484        edge.forward = true;   
485      } else {
486        Parent::firstDown(edge, node);
487        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
488      }
489    }
490    void nextIn(Edge& edge) const {
491      if (edge.forward) {
492        Parent::nextUp(edge);
493      } else {
494        Parent::nextDown(edge);
495        edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
496      }
497    }
498
499    Node source(const Edge& edge) const {
500      return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);
501    }
502    Node target(const Edge& edge) const {
503      return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);
504    }
505
506    bool direction(const Edge& edge) const {
507      return edge.forward;
508    }
509
510    Edge direct(const UndirEdge& edge, const Node& node) const {
511      return Edge(edge, node == Parent::source(edge));
512    }
513
514    Edge direct(const UndirEdge& edge, bool direction) const {
515      return Edge(edge, direction);
516    }
517
518    Node oppositeNode(const UndirEdge& edge, const Node& node) const {
519      return source(edge) == node ?
520        target(edge) : source(edge);
521    }
522
523    Edge oppositeEdge(const Edge& edge) const {
524      return Edge(edge, !edge.forward);
525    }
526
527    int id(const Edge& edge) const {
528      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
529    }
530    Edge edgeFromId(int id) const {
531      return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
532    }
533    int maxEdgeId() const {
534      return (Parent::maxId(UndirEdge()) << 1) + 1;
535    }
536
537    class UpperNode : public Node {
538      friend class UndirBipartiteGraphExtender;
539    public:
540      UpperNode() {}
541      UpperNode(const Node& node) : Node(node) {
542        LEMON_ASSERT(Parent::upper(node) || node == INVALID,
543                     typename Parent::NodeSetError());
544      }
545      UpperNode(Invalid) : Node(INVALID) {}
546    };
547
548    void first(UpperNode& node) const {
549      Parent::firstUpper(static_cast<Node&>(node));
550    }
551    void next(UpperNode& node) const {
552      Parent::nextUpper(static_cast<Node&>(node));
553    }
554
555    int id(const UpperNode& node) const {
556      return Parent::upperId(node);
557    }
558
559    class LowerNode : public Node {
560      friend class UndirBipartiteGraphExtender;
561    public:
562      LowerNode() {}
563      LowerNode(const Node& node) : Node(node) {
564        LEMON_ASSERT(Parent::lower(node) || node == INVALID,
565                     typename Parent::NodeSetError());
566      }
567      LowerNode(Invalid) : Node(INVALID) {}
568    };
569
570    void first(LowerNode& node) const {
571      Parent::firstLower(static_cast<Node&>(node));
572    }
573    void next(LowerNode& node) const {
574      Parent::nextLower(static_cast<Node&>(node));
575    }
576 
577    int id(const LowerNode& node) const {
578      return Parent::upperId(node);
579    }
580
581
582
583    int maxId(Node) const {
584      return Parent::maxNodeId();
585    }
586    int maxId(LowerNode) const {
587      return Parent::maxLowerId();
588    }
589    int maxId(UpperNode) const {
590      return Parent::maxUpperId();
591    }
592    int maxId(Edge) const {
593      return maxEdgeId();
594    }
595    int maxId(UndirEdge) const {
596      return maxUndirEdgeId();
597    }
598
599
600    Node fromId(int id, Node) const {
601      return Parent::nodeFromId(id);
602    }
603    UpperNode fromId(int id, UpperNode) const {
604      return Parent::fromUpperId(id);
605    }
606    LowerNode fromId(int id, LowerNode) const {
607      return Parent::fromLowerId(id);
608    }
609    Edge fromId(int id, Edge) const {
610      return edgeFromId(id);
611    }
612    UndirEdge fromId(int id, UndirEdge) const {
613      return undirEdgeFromId(id);
614    }
615
616  };
617
618}
619
620#endif // LEMON_UNDIR_GRAPH_EXTENDER_H
Note: See TracBrowser for help on using the repository browser.