COIN-OR::LEMON - Graph Library

source: lemon/lemon/bits/graph_extender.h @ 451:09e416d35896

Last change on this file since 451:09e416d35896 was 373:f58410582b9b, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc improvements for the graph related tools in lemon/bits

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