COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/bits/graph_extender.h @ 800:28c7ad6f8d91

Last change on this file since 800:28c7ad6f8d91 was 778:a143f19f465b, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Make some graph member functions static (#311, #68)

File size: 17.0 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-2009
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    typedef Base Parent;
41
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    static Node fromId(int id, Node) {
60      return Parent::nodeFromId(id);
61    }
62
63    static Arc fromId(int id, Arc) {
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      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
223
224    public:
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      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
247
248    public:
249      explicit ArcMap(const Digraph& digraph)
250        : Parent(digraph) {}
251      ArcMap(const Digraph& digraph, const _Value& value)
252        : Parent(digraph, value) {}
253
254    private:
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    typedef Base Parent;
333
334  public:
335
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    static Node fromId(int id, Node) {
359      return Parent::nodeFromId(id);
360    }
361
362    static Arc fromId(int id, Arc) {
363      return Parent::arcFromId(id);
364    }
365
366    static Edge fromId(int id, Edge) {
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      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
605
606    public:
607      explicit NodeMap(const Graph& graph)
608        : Parent(graph) {}
609      NodeMap(const Graph& graph, const _Value& value)
610        : Parent(graph, value) {}
611
612    private:
613      NodeMap& operator=(const NodeMap& cmap) {
614        return operator=<NodeMap>(cmap);
615      }
616
617      template <typename CMap>
618      NodeMap& operator=(const CMap& cmap) {
619        Parent::operator=(cmap);
620        return *this;
621      }
622
623    };
624
625    template <typename _Value>
626    class ArcMap
627      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
628      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
629
630    public:
631      explicit ArcMap(const Graph& graph)
632        : Parent(graph) {}
633      ArcMap(const Graph& graph, const _Value& value)
634        : Parent(graph, value) {}
635
636    private:
637      ArcMap& operator=(const ArcMap& cmap) {
638        return operator=<ArcMap>(cmap);
639      }
640
641      template <typename CMap>
642      ArcMap& operator=(const CMap& cmap) {
643        Parent::operator=(cmap);
644        return *this;
645      }
646    };
647
648
649    template <typename _Value>
650    class EdgeMap
651      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
652      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
653
654    public:
655      explicit EdgeMap(const Graph& graph)
656        : Parent(graph) {}
657
658      EdgeMap(const Graph& graph, const _Value& value)
659        : Parent(graph, value) {}
660
661    private:
662      EdgeMap& operator=(const EdgeMap& cmap) {
663        return operator=<EdgeMap>(cmap);
664      }
665
666      template <typename CMap>
667      EdgeMap& operator=(const CMap& cmap) {
668        Parent::operator=(cmap);
669        return *this;
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));
687      ev.push_back(Parent::direct(edge, false));
688      notifier(Arc()).add(ev);
689      return edge;
690    }
691
692    void clear() {
693      notifier(Arc()).clear();
694      notifier(Edge()).clear();
695      notifier(Node()).clear();
696      Parent::clear();
697    }
698
699    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
700    void build(const Graph& graph, NodeRefMap& nodeRef,
701               EdgeRefMap& edgeRef) {
702      Parent::build(graph, nodeRef, edgeRef);
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 ) {
712        erase(arc);
713        Parent::firstOut(arc, node);
714      }
715
716      Parent::firstIn(arc, node);
717      while (arc != INVALID ) {
718        erase(arc);
719        Parent::firstIn(arc, node);
720      }
721
722      notifier(Node()).erase(node);
723      Parent::erase(node);
724    }
725
726    void erase(const Edge& edge) {
727      std::vector<Arc> av;
728      av.push_back(Parent::direct(edge, true));
729      av.push_back(Parent::direct(edge, false));
730      notifier(Arc()).erase(av);
731      notifier(Edge()).erase(edge);
732      Parent::erase(edge);
733    }
734
735    GraphExtender() {
736      node_notifier.setContainer(*this);
737      arc_notifier.setContainer(*this);
738      edge_notifier.setContainer(*this);
739    }
740
741    ~GraphExtender() {
742      edge_notifier.clear();
743      arc_notifier.clear();
744      node_notifier.clear();
745    }
746
747  };
748
749}
750
751#endif
Note: See TracBrowser for help on using the repository browser.