COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_extender.h @ 685:a27356ceb5bd

Last change on this file since 685:a27356ceb5bd was 685:a27356ceb5bd, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Add missing 'explicit' keywords (#311)

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