COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 221:64613d8fae28

Last change on this file since 221:64613d8fae28 was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

File size: 17.1 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/core.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 &node, const Arc &arc) const {
67      if (node == Parent::source(arc))
68        return Parent::target(arc);
69      else if(node == Parent::target(arc))
70        return Parent::source(arc);
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& arc) :
132        Arc(arc), _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 &arc) const {
193      return Parent::source(arc);
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 &arc) const {
200      return Parent::target(arc);
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 &arc) const {
207      return Parent::target(arc);
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 &arc) const {
214      return Parent::source(arc);
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 Graph;
335
336    typedef True UndirectedTag;
337
338    typedef typename Parent::Node Node;
339    typedef typename Parent::Arc Arc;
340    typedef typename Parent::Edge Edge;
341
342    // Graph extension
343
344    int maxId(Node) const {
345      return Parent::maxNodeId();
346    }
347
348    int maxId(Arc) const {
349      return Parent::maxArcId();
350    }
351
352    int maxId(Edge) const {
353      return Parent::maxEdgeId();
354    }
355
356    Node fromId(int id, Node) const {
357      return Parent::nodeFromId(id);
358    }
359
360    Arc fromId(int id, Arc) const {
361      return Parent::arcFromId(id);
362    }
363
364    Edge fromId(int id, Edge) const {
365      return Parent::edgeFromId(id);
366    }
367
368    Node oppositeNode(const Node &n, const Edge &e) const {
369      if( n == Parent::u(e))
370        return Parent::v(e);
371      else if( n == Parent::v(e))
372        return Parent::u(e);
373      else
374        return INVALID;
375    }
376
377    Arc oppositeArc(const Arc &arc) const {
378      return Parent::direct(arc, !Parent::direction(arc));
379    }
380
381    using Parent::direct;
382    Arc direct(const Edge &edge, const Node &node) const {
383      return Parent::direct(edge, Parent::u(edge) == node);
384    }
385
386    // Alterable extension
387
388    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
389    typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
390    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
391
392
393  protected:
394
395    mutable NodeNotifier node_notifier;
396    mutable ArcNotifier arc_notifier;
397    mutable EdgeNotifier edge_notifier;
398
399  public:
400
401    NodeNotifier& notifier(Node) const {
402      return node_notifier;
403    }
404
405    ArcNotifier& notifier(Arc) const {
406      return arc_notifier;
407    }
408
409    EdgeNotifier& notifier(Edge) const {
410      return edge_notifier;
411    }
412
413
414
415    class NodeIt : public Node {
416      const Graph* _graph;
417    public:
418
419      NodeIt() {}
420
421      NodeIt(Invalid i) : Node(i) { }
422
423      explicit NodeIt(const Graph& graph) : _graph(&graph) {
424        _graph->first(static_cast<Node&>(*this));
425      }
426
427      NodeIt(const Graph& graph, const Node& node)
428        : Node(node), _graph(&graph) {}
429
430      NodeIt& operator++() {
431        _graph->next(*this);
432        return *this;
433      }
434
435    };
436
437
438    class ArcIt : public Arc {
439      const Graph* _graph;
440    public:
441
442      ArcIt() { }
443
444      ArcIt(Invalid i) : Arc(i) { }
445
446      explicit ArcIt(const Graph& graph) : _graph(&graph) {
447        _graph->first(static_cast<Arc&>(*this));
448      }
449
450      ArcIt(const Graph& graph, const Arc& arc) :
451        Arc(arc), _graph(&graph) { }
452
453      ArcIt& operator++() {
454        _graph->next(*this);
455        return *this;
456      }
457
458    };
459
460
461    class OutArcIt : public Arc {
462      const Graph* _graph;
463    public:
464
465      OutArcIt() { }
466
467      OutArcIt(Invalid i) : Arc(i) { }
468
469      OutArcIt(const Graph& graph, const Node& node)
470        : _graph(&graph) {
471        _graph->firstOut(*this, node);
472      }
473
474      OutArcIt(const Graph& graph, const Arc& arc)
475        : Arc(arc), _graph(&graph) {}
476
477      OutArcIt& operator++() {
478        _graph->nextOut(*this);
479        return *this;
480      }
481
482    };
483
484
485    class InArcIt : public Arc {
486      const Graph* _graph;
487    public:
488
489      InArcIt() { }
490
491      InArcIt(Invalid i) : Arc(i) { }
492
493      InArcIt(const Graph& graph, const Node& node)
494        : _graph(&graph) {
495        _graph->firstIn(*this, node);
496      }
497
498      InArcIt(const Graph& graph, const Arc& arc) :
499        Arc(arc), _graph(&graph) {}
500
501      InArcIt& operator++() {
502        _graph->nextIn(*this);
503        return *this;
504      }
505
506    };
507
508
509    class EdgeIt : public Parent::Edge {
510      const Graph* _graph;
511    public:
512
513      EdgeIt() { }
514
515      EdgeIt(Invalid i) : Edge(i) { }
516
517      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
518        _graph->first(static_cast<Edge&>(*this));
519      }
520
521      EdgeIt(const Graph& graph, const Edge& edge) :
522        Edge(edge), _graph(&graph) { }
523
524      EdgeIt& operator++() {
525        _graph->next(*this);
526        return *this;
527      }
528
529    };
530
531    class IncEdgeIt : public Parent::Edge {
532      friend class GraphExtender;
533      const Graph* _graph;
534      bool _direction;
535    public:
536
537      IncEdgeIt() { }
538
539      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
540
541      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
542        _graph->firstInc(*this, _direction, node);
543      }
544
545      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
546        : _graph(&graph), Edge(edge) {
547        _direction = (_graph->source(edge) == node);
548      }
549
550      IncEdgeIt& operator++() {
551        _graph->nextInc(*this, _direction);
552        return *this;
553      }
554    };
555
556    /// \brief Base node of the iterator
557    ///
558    /// Returns the base node (ie. the source in this case) of the iterator
559    Node baseNode(const OutArcIt &arc) const {
560      return Parent::source(static_cast<const Arc&>(arc));
561    }
562    /// \brief Running node of the iterator
563    ///
564    /// Returns the running node (ie. the target in this case) of the
565    /// iterator
566    Node runningNode(const OutArcIt &arc) const {
567      return Parent::target(static_cast<const Arc&>(arc));
568    }
569
570    /// \brief Base node of the iterator
571    ///
572    /// Returns the base node (ie. the target in this case) of the iterator
573    Node baseNode(const InArcIt &arc) const {
574      return Parent::target(static_cast<const Arc&>(arc));
575    }
576    /// \brief Running node of the iterator
577    ///
578    /// Returns the running node (ie. the source in this case) of the
579    /// iterator
580    Node runningNode(const InArcIt &arc) const {
581      return Parent::source(static_cast<const Arc&>(arc));
582    }
583
584    /// Base node of the iterator
585    ///
586    /// Returns the base node of the iterator
587    Node baseNode(const IncEdgeIt &edge) const {
588      return edge._direction ? u(edge) : v(edge);
589    }
590    /// Running node of the iterator
591    ///
592    /// Returns the running node of the iterator
593    Node runningNode(const IncEdgeIt &edge) const {
594      return edge._direction ? v(edge) : u(edge);
595    }
596
597    // Mappable extension
598
599    template <typename _Value>
600    class NodeMap
601      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
602    public:
603      typedef GraphExtender Graph;
604      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
605
606      NodeMap(const Graph& graph)
607        : Parent(graph) {}
608      NodeMap(const Graph& graph, const _Value& value)
609        : Parent(graph, value) {}
610
611      NodeMap& operator=(const NodeMap& cmap) {
612        return operator=<NodeMap>(cmap);
613      }
614
615      template <typename CMap>
616      NodeMap& operator=(const CMap& cmap) {
617        Parent::operator=(cmap);
618        return *this;
619      }
620
621    };
622
623    template <typename _Value>
624    class ArcMap
625      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
626    public:
627      typedef GraphExtender Graph;
628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
629
630      ArcMap(const Graph& graph)
631        : Parent(graph) {}
632      ArcMap(const Graph& graph, const _Value& value)
633        : Parent(graph, value) {}
634
635      ArcMap& operator=(const ArcMap& cmap) {
636        return operator=<ArcMap>(cmap);
637      }
638
639      template <typename CMap>
640      ArcMap& operator=(const CMap& cmap) {
641        Parent::operator=(cmap);
642        return *this;
643      }
644    };
645
646
647    template <typename _Value>
648    class EdgeMap
649      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
650    public:
651      typedef GraphExtender Graph;
652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
653
654      EdgeMap(const Graph& graph)
655        : Parent(graph) {}
656
657      EdgeMap(const Graph& graph, const _Value& value)
658        : Parent(graph, value) {}
659
660      EdgeMap& operator=(const EdgeMap& cmap) {
661        return operator=<EdgeMap>(cmap);
662      }
663
664      template <typename CMap>
665      EdgeMap& operator=(const CMap& cmap) {
666        Parent::operator=(cmap);
667        return *this;
668      }
669
670    };
671
672    // Alteration extension
673
674    Node addNode() {
675      Node node = Parent::addNode();
676      notifier(Node()).add(node);
677      return node;
678    }
679
680    Edge addEdge(const Node& from, const Node& to) {
681      Edge edge = Parent::addEdge(from, to);
682      notifier(Edge()).add(edge);
683      std::vector<Arc> ev;
684      ev.push_back(Parent::direct(edge, true));
685      ev.push_back(Parent::direct(edge, false));
686      notifier(Arc()).add(ev);
687      return edge;
688    }
689
690    void clear() {
691      notifier(Arc()).clear();
692      notifier(Edge()).clear();
693      notifier(Node()).clear();
694      Parent::clear();
695    }
696
697    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
698    void build(const Graph& graph, NodeRefMap& nodeRef,
699               EdgeRefMap& edgeRef) {
700      Parent::build(graph, nodeRef, edgeRef);
701      notifier(Node()).build();
702      notifier(Edge()).build();
703      notifier(Arc()).build();
704    }
705
706    void erase(const Node& node) {
707      Arc arc;
708      Parent::firstOut(arc, node);
709      while (arc != INVALID ) {
710        erase(arc);
711        Parent::firstOut(arc, node);
712      }
713
714      Parent::firstIn(arc, node);
715      while (arc != INVALID ) {
716        erase(arc);
717        Parent::firstIn(arc, node);
718      }
719
720      notifier(Node()).erase(node);
721      Parent::erase(node);
722    }
723
724    void erase(const Edge& edge) {
725      std::vector<Arc> av;
726      av.push_back(Parent::direct(edge, true));
727      av.push_back(Parent::direct(edge, false));
728      notifier(Arc()).erase(av);
729      notifier(Edge()).erase(edge);
730      Parent::erase(edge);
731    }
732
733    GraphExtender() {
734      node_notifier.setContainer(*this);
735      arc_notifier.setContainer(*this);
736      edge_notifier.setContainer(*this);
737    }
738
739    ~GraphExtender() {
740      edge_notifier.clear();
741      arc_notifier.clear();
742      node_notifier.clear();
743    }
744
745  };
746
747}
748
749#endif
Note: See TracBrowser for help on using the repository browser.