COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_extender.h @ 220:a5d8c039f218

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