COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_extender.h @ 57:c1acf0018c0a

Last change on this file since 57:c1acf0018c0a was 57:c1acf0018c0a, checked in by Balazs Dezso <deba@…>, 16 years ago

Port ListDigraph? and ListGraph? from svn -r 3433
Details:

  • port Digraph and Graph concepts
  • port ListDigraph? and ListGraph?
  • port Basic graph constructing tools
  • port Digraph and Graph tests
File size: 16.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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_GRAPH_EXTENDER_H
20#define LEMON_BITS_GRAPH_EXTENDER_H
21
22#include <lemon/bits/invalid.h>
23
24#include <lemon/bits/map_extender.h>
25#include <lemon/bits/default_map.h>
26
27#include <lemon/concept_check.h>
28#include <lemon/concepts/maps.h>
29
30///\ingroup graphbits
31///\file
32///\brief Extenders for the digraph types
33namespace lemon {
34
35  /// \ingroup graphbits
36  ///
37  /// \brief Extender for the Digraphs
38  template <typename Base>
39  class DigraphExtender : public Base {
40  public:
41
42    typedef Base Parent;
43    typedef DigraphExtender Digraph;
44
45    // Base extensions
46
47    typedef typename Parent::Node Node;
48    typedef typename Parent::Arc Arc;
49
50    int maxId(Node) const {
51      return Parent::maxNodeId();
52    }
53
54    int maxId(Arc) const {
55      return Parent::maxArcId();
56    }
57
58    Node fromId(int id, Node) const {
59      return Parent::nodeFromId(id);
60    }
61
62    Arc fromId(int id, Arc) const {
63      return Parent::arcFromId(id);
64    }
65
66    Node oppositeNode(const Node &n, const Arc &e) const {
67      if (n == Parent::source(e))
68        return Parent::target(e);
69      else if(n==Parent::target(e))
70        return Parent::source(e);
71      else
72        return INVALID;
73    }
74
75    // Alterable extension
76
77    typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
78    typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
79
80
81  protected:
82
83    mutable NodeNotifier node_notifier;
84    mutable ArcNotifier arc_notifier;
85
86  public:
87
88    NodeNotifier& notifier(Node) const {
89      return node_notifier;
90    }
91   
92    ArcNotifier& notifier(Arc) const {
93      return arc_notifier;
94    }
95
96    class NodeIt : public Node {
97      const Digraph* digraph;
98    public:
99
100      NodeIt() {}
101
102      NodeIt(Invalid i) : Node(i) { }
103
104      explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
105        _digraph.first(static_cast<Node&>(*this));
106      }
107
108      NodeIt(const Digraph& _digraph, const Node& node)
109        : Node(node), digraph(&_digraph) {}
110
111      NodeIt& operator++() {
112        digraph->next(*this);
113        return *this;
114      }
115
116    };
117
118
119    class ArcIt : public Arc {
120      const Digraph* digraph;
121    public:
122
123      ArcIt() { }
124
125      ArcIt(Invalid i) : Arc(i) { }
126
127      explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
128        _digraph.first(static_cast<Arc&>(*this));
129      }
130
131      ArcIt(const Digraph& _digraph, const Arc& e) :
132        Arc(e), digraph(&_digraph) { }
133
134      ArcIt& operator++() {
135        digraph->next(*this);
136        return *this;
137      }
138
139    };
140
141
142    class OutArcIt : public Arc {
143      const Digraph* digraph;
144    public:
145
146      OutArcIt() { }
147
148      OutArcIt(Invalid i) : Arc(i) { }
149
150      OutArcIt(const Digraph& _digraph, const Node& node)
151        : digraph(&_digraph) {
152        _digraph.firstOut(*this, node);
153      }
154
155      OutArcIt(const Digraph& _digraph, const Arc& arc)
156        : Arc(arc), digraph(&_digraph) {}
157
158      OutArcIt& operator++() {
159        digraph->nextOut(*this);
160        return *this;
161      }
162
163    };
164
165
166    class InArcIt : public Arc {
167      const Digraph* digraph;
168    public:
169
170      InArcIt() { }
171
172      InArcIt(Invalid i) : Arc(i) { }
173
174      InArcIt(const Digraph& _digraph, const Node& node)
175        : digraph(&_digraph) {
176        _digraph.firstIn(*this, node);
177      }
178
179      InArcIt(const Digraph& _digraph, const Arc& arc) :
180        Arc(arc), digraph(&_digraph) {}
181
182      InArcIt& operator++() {
183        digraph->nextIn(*this);
184        return *this;
185      }
186
187    };
188
189    /// \brief Base node of the iterator
190    ///
191    /// Returns the base node (i.e. the source in this case) of the iterator
192    Node baseNode(const OutArcIt &e) const {
193      return Parent::source(e);
194    }
195    /// \brief Running node of the iterator
196    ///
197    /// Returns the running node (i.e. the target in this case) of the
198    /// iterator
199    Node runningNode(const OutArcIt &e) const {
200      return Parent::target(e);
201    }
202
203    /// \brief Base node of the iterator
204    ///
205    /// Returns the base node (i.e. the target in this case) of the iterator
206    Node baseNode(const InArcIt &e) const {
207      return Parent::target(e);
208    }
209    /// \brief Running node of the iterator
210    ///
211    /// Returns the running node (i.e. the source in this case) of the
212    /// iterator
213    Node runningNode(const InArcIt &e) const {
214      return Parent::source(e);
215    }
216
217   
218    template <typename _Value>
219    class NodeMap
220      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
221    public:
222      typedef DigraphExtender Digraph;
223      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
224
225      explicit NodeMap(const Digraph& digraph)
226        : Parent(digraph) {}
227      NodeMap(const Digraph& digraph, const _Value& value)
228        : Parent(digraph, value) {}
229
230      NodeMap& operator=(const NodeMap& cmap) {
231        return operator=<NodeMap>(cmap);
232      }
233
234      template <typename CMap>
235      NodeMap& operator=(const CMap& cmap) {
236        Parent::operator=(cmap);
237        return *this;
238      }
239
240    };
241
242    template <typename _Value>
243    class ArcMap
244      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
245    public:
246      typedef DigraphExtender Digraph;
247      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
248
249      explicit ArcMap(const Digraph& digraph)
250        : Parent(digraph) {}
251      ArcMap(const Digraph& digraph, const _Value& value)
252        : Parent(digraph, value) {}
253
254      ArcMap& operator=(const ArcMap& cmap) {
255        return operator=<ArcMap>(cmap);
256      }
257
258      template <typename CMap>
259      ArcMap& operator=(const CMap& cmap) {
260        Parent::operator=(cmap);
261        return *this;
262      }
263    };
264
265
266    Node addNode() {
267      Node node = Parent::addNode();
268      notifier(Node()).add(node);
269      return node;
270    }
271   
272    Arc addArc(const Node& from, const Node& to) {
273      Arc arc = Parent::addArc(from, to);
274      notifier(Arc()).add(arc);
275      return arc;
276    }
277
278    void clear() {
279      notifier(Arc()).clear();
280      notifier(Node()).clear();
281      Parent::clear();
282    }
283
284    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
285    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
286      Parent::build(digraph, nodeRef, arcRef);
287      notifier(Node()).build();
288      notifier(Arc()).build();
289    }
290
291    void erase(const Node& node) {
292      Arc arc;
293      Parent::firstOut(arc, node);
294      while (arc != INVALID ) {
295        erase(arc);
296        Parent::firstOut(arc, node);
297      }
298
299      Parent::firstIn(arc, node);
300      while (arc != INVALID ) {
301        erase(arc);
302        Parent::firstIn(arc, node);
303      }
304
305      notifier(Node()).erase(node);
306      Parent::erase(node);
307    }
308   
309    void erase(const Arc& arc) {
310      notifier(Arc()).erase(arc);
311      Parent::erase(arc);
312    }
313
314    DigraphExtender() {
315      node_notifier.setContainer(*this);
316      arc_notifier.setContainer(*this);
317    }
318   
319
320    ~DigraphExtender() {
321      arc_notifier.clear();
322      node_notifier.clear();
323    }
324  };
325
326  /// \ingroup graphbits
327  ///
328  /// \brief Extender for the Graphs
329  template <typename Base>
330  class GraphExtender : public Base {
331  public:
332   
333    typedef Base Parent;
334    typedef GraphExtender Digraph;
335
336    typedef typename Parent::Node Node;
337    typedef typename Parent::Arc Arc;
338    typedef typename Parent::Edge Edge;
339
340    // Graph extension   
341
342    int maxId(Node) const {
343      return Parent::maxNodeId();
344    }
345
346    int maxId(Arc) const {
347      return Parent::maxArcId();
348    }
349
350    int maxId(Edge) const {
351      return Parent::maxEdgeId();
352    }
353
354    Node fromId(int id, Node) const {
355      return Parent::nodeFromId(id);
356    }
357
358    Arc fromId(int id, Arc) const {
359      return Parent::arcFromId(id);
360    }
361
362    Edge fromId(int id, Edge) const {
363      return Parent::edgeFromId(id);
364    }
365
366    Node oppositeNode(const Node &n, const Edge &e) const {
367      if( n == Parent::source(e))
368        return Parent::target(e);
369      else if( n == Parent::target(e))
370        return Parent::source(e);
371      else
372        return INVALID;
373    }
374
375    Arc oppositeArc(const Arc &e) const {
376      return Parent::direct(e, !Parent::direction(e));
377    }
378
379    using Parent::direct;
380    Arc direct(const Edge &ue, const Node &s) const {
381      return Parent::direct(ue, Parent::source(ue) == s);
382    }
383
384    // Alterable extension
385
386    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
387    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
388    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
389
390
391  protected:
392
393    mutable NodeNotifier node_notifier;
394    mutable ArcNotifier arc_notifier;
395    mutable EdgeNotifier edge_notifier;
396
397  public:
398
399    NodeNotifier& notifier(Node) const {
400      return node_notifier;
401    }
402   
403    ArcNotifier& notifier(Arc) const {
404      return arc_notifier;
405    }
406
407    EdgeNotifier& notifier(Edge) const {
408      return edge_notifier;
409    }
410
411
412
413    class NodeIt : public Node {
414      const Digraph* digraph;
415    public:
416
417      NodeIt() {}
418
419      NodeIt(Invalid i) : Node(i) { }
420
421      explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
422        _digraph.first(static_cast<Node&>(*this));
423      }
424
425      NodeIt(const Digraph& _digraph, const Node& node)
426        : Node(node), digraph(&_digraph) {}
427
428      NodeIt& operator++() {
429        digraph->next(*this);
430        return *this;
431      }
432
433    };
434
435
436    class ArcIt : public Arc {
437      const Digraph* digraph;
438    public:
439
440      ArcIt() { }
441
442      ArcIt(Invalid i) : Arc(i) { }
443
444      explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
445        _digraph.first(static_cast<Arc&>(*this));
446      }
447
448      ArcIt(const Digraph& _digraph, const Arc& e) :
449        Arc(e), digraph(&_digraph) { }
450
451      ArcIt& operator++() {
452        digraph->next(*this);
453        return *this;
454      }
455
456    };
457
458
459    class OutArcIt : public Arc {
460      const Digraph* digraph;
461    public:
462
463      OutArcIt() { }
464
465      OutArcIt(Invalid i) : Arc(i) { }
466
467      OutArcIt(const Digraph& _digraph, const Node& node)
468        : digraph(&_digraph) {
469        _digraph.firstOut(*this, node);
470      }
471
472      OutArcIt(const Digraph& _digraph, const Arc& arc)
473        : Arc(arc), digraph(&_digraph) {}
474
475      OutArcIt& operator++() {
476        digraph->nextOut(*this);
477        return *this;
478      }
479
480    };
481
482
483    class InArcIt : public Arc {
484      const Digraph* digraph;
485    public:
486
487      InArcIt() { }
488
489      InArcIt(Invalid i) : Arc(i) { }
490
491      InArcIt(const Digraph& _digraph, const Node& node)
492        : digraph(&_digraph) {
493        _digraph.firstIn(*this, node);
494      }
495
496      InArcIt(const Digraph& _digraph, const Arc& arc) :
497        Arc(arc), digraph(&_digraph) {}
498
499      InArcIt& operator++() {
500        digraph->nextIn(*this);
501        return *this;
502      }
503
504    };
505
506
507    class EdgeIt : public Parent::Edge {
508      const Digraph* digraph;
509    public:
510
511      EdgeIt() { }
512
513      EdgeIt(Invalid i) : Edge(i) { }
514
515      explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
516        _digraph.first(static_cast<Edge&>(*this));
517      }
518
519      EdgeIt(const Digraph& _digraph, const Edge& e) :
520        Edge(e), digraph(&_digraph) { }
521
522      EdgeIt& operator++() {
523        digraph->next(*this);
524        return *this;
525      }
526
527    };
528
529    class IncArcIt : public Parent::Edge {
530      friend class GraphExtender;
531      const Digraph* digraph;
532      bool direction;
533    public:
534
535      IncArcIt() { }
536
537      IncArcIt(Invalid i) : Edge(i), direction(false) { }
538
539      IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
540        _digraph.firstInc(*this, direction, n);
541      }
542
543      IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
544        : digraph(&_digraph), Edge(ue) {
545        direction = (_digraph.source(ue) == n);
546      }
547
548      IncArcIt& operator++() {
549        digraph->nextInc(*this, direction);
550        return *this;
551      }
552    };
553
554    /// \brief Base node of the iterator
555    ///
556    /// Returns the base node (ie. the source in this case) of the iterator
557    Node baseNode(const OutArcIt &e) const {
558      return Parent::source(static_cast<const Arc&>(e));
559    }
560    /// \brief Running node of the iterator
561    ///
562    /// Returns the running node (ie. the target in this case) of the
563    /// iterator
564    Node runningNode(const OutArcIt &e) const {
565      return Parent::target(static_cast<const Arc&>(e));
566    }
567
568    /// \brief Base node of the iterator
569    ///
570    /// Returns the base node (ie. the target in this case) of the iterator
571    Node baseNode(const InArcIt &e) const {
572      return Parent::target(static_cast<const Arc&>(e));
573    }
574    /// \brief Running node of the iterator
575    ///
576    /// Returns the running node (ie. the source in this case) of the
577    /// iterator
578    Node runningNode(const InArcIt &e) const {
579      return Parent::source(static_cast<const Arc&>(e));
580    }
581
582    /// Base node of the iterator
583    ///
584    /// Returns the base node of the iterator
585    Node baseNode(const IncArcIt &e) const {
586      return e.direction ? source(e) : target(e);
587    }
588    /// Running node of the iterator
589    ///
590    /// Returns the running node of the iterator
591    Node runningNode(const IncArcIt &e) const {
592      return e.direction ? target(e) : source(e);
593    }
594
595    // Mappable extension
596
597    template <typename _Value>
598    class NodeMap
599      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
600    public:
601      typedef GraphExtender Digraph;
602      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
603
604      NodeMap(const Digraph& digraph)
605        : Parent(digraph) {}
606      NodeMap(const Digraph& digraph, const _Value& value)
607        : Parent(digraph, value) {}
608
609      NodeMap& operator=(const NodeMap& cmap) {
610        return operator=<NodeMap>(cmap);
611      }
612
613      template <typename CMap>
614      NodeMap& operator=(const CMap& cmap) {
615        Parent::operator=(cmap);
616        return *this;
617      }
618
619    };
620
621    template <typename _Value>
622    class ArcMap
623      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
624    public:
625      typedef GraphExtender Digraph;
626      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
627
628      ArcMap(const Digraph& digraph)
629        : Parent(digraph) {}
630      ArcMap(const Digraph& digraph, const _Value& value)
631        : Parent(digraph, value) {}
632
633      ArcMap& operator=(const ArcMap& cmap) {
634        return operator=<ArcMap>(cmap);
635      }
636
637      template <typename CMap>
638      ArcMap& operator=(const CMap& cmap) {
639        Parent::operator=(cmap);
640        return *this;
641      }
642    };
643
644
645    template <typename _Value>
646    class EdgeMap
647      : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
648    public:
649      typedef GraphExtender Digraph;
650      typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
651
652      EdgeMap(const Digraph& digraph)
653        : Parent(digraph) {}
654
655      EdgeMap(const Digraph& digraph, const _Value& value)
656        : Parent(digraph, value) {}
657
658      EdgeMap& operator=(const EdgeMap& cmap) {
659        return operator=<EdgeMap>(cmap);
660      }
661
662      template <typename CMap>
663      EdgeMap& operator=(const CMap& cmap) {
664        Parent::operator=(cmap);
665        return *this;
666      }
667
668    };
669
670    // Alteration extension
671
672    Node addNode() {
673      Node node = Parent::addNode();
674      notifier(Node()).add(node);
675      return node;
676    }
677
678    Edge addEdge(const Node& from, const Node& to) {
679      Edge edge = Parent::addEdge(from, to);
680      notifier(Edge()).add(edge);
681      std::vector<Arc> ev;
682      ev.push_back(Parent::direct(edge, true));
683      ev.push_back(Parent::direct(edge, false));     
684      notifier(Arc()).add(ev);
685      return edge;
686    }
687   
688    void clear() {
689      notifier(Arc()).clear();
690      notifier(Edge()).clear();
691      notifier(Node()).clear();
692      Parent::clear();
693    }
694
695    template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
696    void build(const Digraph& digraph, NodeRefMap& nodeRef,
697               EdgeRefMap& edgeRef) {
698      Parent::build(digraph, nodeRef, edgeRef);
699      notifier(Node()).build();
700      notifier(Edge()).build();
701      notifier(Arc()).build();
702    }
703
704    void erase(const Node& node) {
705      Arc arc;
706      Parent::firstOut(arc, node);
707      while (arc != INVALID ) {
708        erase(arc);
709        Parent::firstOut(arc, node);
710      }
711
712      Parent::firstIn(arc, node);
713      while (arc != INVALID ) {
714        erase(arc);
715        Parent::firstIn(arc, node);
716      }
717
718      notifier(Node()).erase(node);
719      Parent::erase(node);
720    }
721
722    void erase(const Edge& edge) {
723      std::vector<Arc> ev;
724      ev.push_back(Parent::direct(edge, true));
725      ev.push_back(Parent::direct(edge, false));     
726      notifier(Arc()).erase(ev);
727      notifier(Edge()).erase(edge);
728      Parent::erase(edge);
729    }
730
731    GraphExtender() {
732      node_notifier.setContainer(*this);
733      arc_notifier.setContainer(*this);
734      edge_notifier.setContainer(*this);
735    }
736
737    ~GraphExtender() {
738      edge_notifier.clear();
739      arc_notifier.clear();
740      node_notifier.clear();
741    }
742
743  };
744
745}
746
747#endif
Note: See TracBrowser for help on using the repository browser.