COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 209:765619b7cbb2

Last change on this file since 209:765619b7cbb2 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Apply unify-sources.sh to the source tree

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