COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/edge_set_extender.h @ 1979:c2992fd74dad

Last change on this file since 1979:c2992fd74dad was 1979:c2992fd74dad, checked in by Balazs Dezso, 14 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File size: 13.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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
20namespace lemon {
21
22  template <typename Base>
23  class EdgeSetExtender : public Base {
24  public:
25
26    typedef Base Parent;
27    typedef EdgeSetExtender Graph;
28
29    // Base extensions
30
31    typedef typename Parent::Node Node;
32    typedef typename Parent::Edge Edge;
33
34    int maxId(Node) const {
35      return Parent::maxNodeId();
36    }
37
38    int maxId(Edge) const {
39      return Parent::maxEdgeId();
40    }
41
42    Node fromId(int id, Node) const {
43      return Parent::nodeFromId(id);
44    }
45
46    Edge fromId(int id, Edge) const {
47      return Parent::edgeFromId(id);
48    }
49
50    Node oppositeNode(const Node &n, const Edge &e) const {
51      if (n == Parent::source(e))
52        return Parent::target(e);
53      else if(n==Parent::target(e))
54        return Parent::source(e);
55      else
56        return INVALID;
57    }
58
59
60    // Alteration notifier extensions
61
62    /// The edge observer registry.
63    typedef AlterationNotifier<Edge> EdgeNotifier;
64
65  protected:
66
67    mutable EdgeNotifier edge_notifier;
68
69  public:
70
71    /// \brief Gives back the edge alteration notifier.
72    ///
73    /// Gives back the edge alteration notifier.
74    EdgeNotifier& getNotifier(Edge) const {
75      return edge_notifier;
76    }
77
78    // Iterable extensions
79
80    class NodeIt : public Node {
81      const Graph* graph;
82    public:
83
84      NodeIt() {}
85
86      NodeIt(Invalid i) : Node(i) { }
87
88      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
89        _graph.first(*static_cast<Node*>(this));
90      }
91
92      NodeIt(const Graph& _graph, const Node& node)
93        : Node(node), graph(&_graph) {}
94
95      NodeIt& operator++() {
96        graph->next(*this);
97        return *this;
98      }
99
100    };
101
102
103    class EdgeIt : public Edge {
104      const Graph* graph;
105    public:
106
107      EdgeIt() { }
108
109      EdgeIt(Invalid i) : Edge(i) { }
110
111      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
112        _graph.first(*static_cast<Edge*>(this));
113      }
114
115      EdgeIt(const Graph& _graph, const Edge& e) :
116        Edge(e), graph(&_graph) { }
117
118      EdgeIt& operator++() {
119        graph->next(*this);
120        return *this;
121      }
122
123    };
124
125
126    class OutEdgeIt : public Edge {
127      const Graph* graph;
128    public:
129
130      OutEdgeIt() { }
131
132      OutEdgeIt(Invalid i) : Edge(i) { }
133
134      OutEdgeIt(const Graph& _graph, const Node& node)
135        : graph(&_graph) {
136        _graph.firstOut(*this, node);
137      }
138
139      OutEdgeIt(const Graph& _graph, const Edge& edge)
140        : Edge(edge), graph(&_graph) {}
141
142      OutEdgeIt& operator++() {
143        graph->nextOut(*this);
144        return *this;
145      }
146
147    };
148
149
150    class InEdgeIt : public Edge {
151      const Graph* graph;
152    public:
153
154      InEdgeIt() { }
155
156      InEdgeIt(Invalid i) : Edge(i) { }
157
158      InEdgeIt(const Graph& _graph, const Node& node)
159        : graph(&_graph) {
160        _graph.firstIn(*this, node);
161      }
162
163      InEdgeIt(const Graph& _graph, const Edge& edge) :
164        Edge(edge), graph(&_graph) {}
165
166      InEdgeIt& operator++() {
167        graph->nextIn(*this);
168        return *this;
169      }
170
171    };
172
173    /// \brief Base node of the iterator
174    ///
175    /// Returns the base node (ie. the source in this case) of the iterator
176    Node baseNode(const OutEdgeIt &e) const {
177      return Parent::source((Edge)e);
178    }
179    /// \brief Running node of the iterator
180    ///
181    /// Returns the running node (ie. the target in this case) of the
182    /// iterator
183    Node runningNode(const OutEdgeIt &e) const {
184      return Parent::target((Edge)e);
185    }
186
187    /// \brief Base node of the iterator
188    ///
189    /// Returns the base node (ie. the target in this case) of the iterator
190    Node baseNode(const InEdgeIt &e) const {
191      return Parent::target((Edge)e);
192    }
193    /// \brief Running node of the iterator
194    ///
195    /// Returns the running node (ie. the source in this case) of the
196    /// iterator
197    Node runningNode(const InEdgeIt &e) const {
198      return Parent::source((Edge)e);
199    }
200
201    using Parent::first;
202
203    // Mappable extension
204   
205    template <typename _Value>
206    class EdgeMap
207      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
208    public:
209      typedef EdgeSetExtender Graph;
210      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
211
212      EdgeMap(const Graph& _g)
213        : Parent(_g) {}
214      EdgeMap(const Graph& _g, const _Value& _v)
215        : Parent(_g, _v) {}
216
217      EdgeMap& operator=(const EdgeMap& cmap) {
218        return operator=<EdgeMap>(cmap);
219      }
220
221      template <typename CMap>
222      EdgeMap& operator=(const CMap& cmap) {
223        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
224        const typename Parent::Graph* graph = Parent::getGraph();
225        Edge it;
226        for (graph->first(it); it != INVALID; graph->next(it)) {
227          Parent::set(it, cmap[it]);
228        }
229        return *this;
230      }
231    };
232
233
234    // Alteration extension
235
236    Edge addEdge(const Node& from, const Node& to) {
237      Edge edge = Parent::addEdge(from, to);
238      getNotifier(Edge()).add(edge);
239      return edge;
240    }
241   
242    void clear() {
243      getNotifier(Edge()).clear();
244      Parent::clear();
245    }
246
247    void erase(const Edge& edge) {
248      getNotifier(Edge()).erase(edge);
249      Parent::erase(edge);
250    }
251
252
253    ~EdgeSetExtender() {
254      edge_notifier.clear();
255    }
256
257  };
258
259
260  template <typename Base>
261  class UEdgeSetExtender : public Base {
262
263  public:
264
265    typedef Base Parent;
266    typedef UEdgeSetExtender Graph;
267
268    typedef typename Parent::Node Node;
269    typedef typename Parent::Edge Edge;
270    typedef typename Parent::UEdge UEdge;
271
272
273    int maxId(Node) const {
274      return Parent::maxNodeId();
275    }
276
277    int maxId(Edge) const {
278      return Parent::maxEdgeId();
279    }
280
281    int maxId(UEdge) const {
282      return Parent::maxUEdgeId();
283    }
284
285    Node fromId(int id, Node) const {
286      return Parent::nodeFromId(id);
287    }
288
289    Edge fromId(int id, Edge) const {
290      return Parent::edgeFromId(id);
291    }
292
293    UEdge fromId(int id, UEdge) const {
294      return Parent::uEdgeFromId(id);
295    }
296
297    Node oppositeNode(const Node &n, const UEdge &e) const {
298      if( n == Parent::source(e))
299        return Parent::target(e);
300      else if( n == Parent::target(e))
301        return Parent::source(e);
302      else
303        return INVALID;
304    }
305
306    Edge oppositeEdge(const Edge &e) const {
307      return Parent::direct(e, !Parent::direction(e));
308    }
309
310    using Parent::direct;
311    Edge direct(const UEdge &ue, const Node &s) const {
312      return Parent::direct(ue, Parent::source(ue) == s);
313    }
314
315    typedef AlterationNotifier<Edge> EdgeNotifier;
316    typedef AlterationNotifier<UEdge> UEdgeNotifier;
317
318
319  protected:
320
321    mutable EdgeNotifier edge_notifier;
322    mutable UEdgeNotifier uedge_notifier;
323
324  public:
325   
326    EdgeNotifier& getNotifier(Edge) const {
327      return edge_notifier;
328    }
329
330    UEdgeNotifier& getNotifier(UEdge) const {
331      return uedge_notifier;
332    }
333
334
335    class NodeIt : public Node {
336      const Graph* graph;
337    public:
338
339      NodeIt() {}
340
341      NodeIt(Invalid i) : Node(i) { }
342
343      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
344        _graph.first(*static_cast<Node*>(this));
345      }
346
347      NodeIt(const Graph& _graph, const Node& node)
348        : Node(node), graph(&_graph) {}
349
350      NodeIt& operator++() {
351        graph->next(*this);
352        return *this;
353      }
354
355    };
356
357
358    class EdgeIt : public Edge {
359      const Graph* graph;
360    public:
361
362      EdgeIt() { }
363
364      EdgeIt(Invalid i) : Edge(i) { }
365
366      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
367        _graph.first(*static_cast<Edge*>(this));
368      }
369
370      EdgeIt(const Graph& _graph, const Edge& e) :
371        Edge(e), graph(&_graph) { }
372
373      EdgeIt& operator++() {
374        graph->next(*this);
375        return *this;
376      }
377
378    };
379
380
381    class OutEdgeIt : public Edge {
382      const Graph* graph;
383    public:
384
385      OutEdgeIt() { }
386
387      OutEdgeIt(Invalid i) : Edge(i) { }
388
389      OutEdgeIt(const Graph& _graph, const Node& node)
390        : graph(&_graph) {
391        _graph.firstOut(*this, node);
392      }
393
394      OutEdgeIt(const Graph& _graph, const Edge& edge)
395        : Edge(edge), graph(&_graph) {}
396
397      OutEdgeIt& operator++() {
398        graph->nextOut(*this);
399        return *this;
400      }
401
402    };
403
404
405    class InEdgeIt : public Edge {
406      const Graph* graph;
407    public:
408
409      InEdgeIt() { }
410
411      InEdgeIt(Invalid i) : Edge(i) { }
412
413      InEdgeIt(const Graph& _graph, const Node& node)
414        : graph(&_graph) {
415        _graph.firstIn(*this, node);
416      }
417
418      InEdgeIt(const Graph& _graph, const Edge& edge) :
419        Edge(edge), graph(&_graph) {}
420
421      InEdgeIt& operator++() {
422        graph->nextIn(*this);
423        return *this;
424      }
425
426    };
427
428
429    class UEdgeIt : public Parent::UEdge {
430      const Graph* graph;
431    public:
432
433      UEdgeIt() { }
434
435      UEdgeIt(Invalid i) : UEdge(i) { }
436
437      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
438        _graph.first(*static_cast<UEdge*>(this));
439      }
440
441      UEdgeIt(const Graph& _graph, const UEdge& e) :
442        UEdge(e), graph(&_graph) { }
443
444      UEdgeIt& operator++() {
445        graph->next(*this);
446        return *this;
447      }
448
449    };
450
451    class IncEdgeIt : public Parent::UEdge {
452      friend class UEdgeSetExtender;
453      const Graph* graph;
454      bool direction;
455    public:
456
457      IncEdgeIt() { }
458
459      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
460
461      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
462        _graph.firstInc(*this, direction, n);
463      }
464
465      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
466        : graph(&_graph), UEdge(ue) {
467        direction = (_graph.source(ue) == n);
468      }
469
470      IncEdgeIt& operator++() {
471        graph->nextInc(*this, direction);
472        return *this;
473      }
474    };
475
476    /// \brief Base node of the iterator
477    ///
478    /// Returns the base node (ie. the source in this case) of the iterator
479    Node baseNode(const OutEdgeIt &e) const {
480      return Parent::source((Edge)e);
481    }
482    /// \brief Running node of the iterator
483    ///
484    /// Returns the running node (ie. the target in this case) of the
485    /// iterator
486    Node runningNode(const OutEdgeIt &e) const {
487      return Parent::target((Edge)e);
488    }
489
490    /// \brief Base node of the iterator
491    ///
492    /// Returns the base node (ie. the target in this case) of the iterator
493    Node baseNode(const InEdgeIt &e) const {
494      return Parent::target((Edge)e);
495    }
496    /// \brief Running node of the iterator
497    ///
498    /// Returns the running node (ie. the source in this case) of the
499    /// iterator
500    Node runningNode(const InEdgeIt &e) const {
501      return Parent::source((Edge)e);
502    }
503
504    /// Base node of the iterator
505    ///
506    /// Returns the base node of the iterator
507    Node baseNode(const IncEdgeIt &e) const {
508      return e.direction ? source(e) : target(e);
509    }
510    /// Running node of the iterator
511    ///
512    /// Returns the running node of the iterator
513    Node runningNode(const IncEdgeIt &e) const {
514      return e.direction ? target(e) : source(e);
515    }
516
517
518    template <typename _Value>
519    class EdgeMap
520      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
521    public:
522      typedef UEdgeSetExtender Graph;
523      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
524
525      EdgeMap(const Graph& _g)
526        : Parent(_g) {}
527      EdgeMap(const Graph& _g, const _Value& _v)
528        : Parent(_g, _v) {}
529
530      EdgeMap& operator=(const EdgeMap& cmap) {
531        return operator=<EdgeMap>(cmap);
532      }
533
534      template <typename CMap>
535      EdgeMap& operator=(const CMap& cmap) {
536        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
537        const typename Parent::Graph* graph = Parent::getGraph();
538        Edge it;
539        for (graph->first(it); it != INVALID; graph->next(it)) {
540          Parent::set(it, cmap[it]);
541        }
542        return *this;
543      }
544    };
545
546
547    template <typename _Value>
548    class UEdgeMap
549      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
550    public:
551      typedef UEdgeSetExtender Graph;
552      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
553
554      UEdgeMap(const Graph& _g)
555        : Parent(_g) {}
556      UEdgeMap(const Graph& _g, const _Value& _v)
557        : Parent(_g, _v) {}
558
559      UEdgeMap& operator=(const UEdgeMap& cmap) {
560        return operator=<UEdgeMap>(cmap);
561      }
562
563      template <typename CMap>
564      UEdgeMap& operator=(const CMap& cmap) {
565        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
566        const typename Parent::Graph* graph = Parent::getGraph();
567        UEdge it;
568        for (graph->first(it); it != INVALID; graph->next(it)) {
569          Parent::set(it, cmap[it]);
570        }
571        return *this;
572      }
573    };
574
575
576    // Alteration extension
577
578    UEdge addEdge(const Node& from, const Node& to) {
579      UEdge uedge = Parent::addEdge(from, to);
580      getNotifier(UEdge()).add(uedge);
581      getNotifier(Edge()).add(Parent::direct(uedge, true));
582      getNotifier(Edge()).add(Parent::direct(uedge, false));
583      return uedge;
584    }
585   
586    void clear() {
587      getNotifier(Edge()).clear();
588      getNotifier(UEdge()).clear();
589      Parent::clear();
590    }
591
592    void erase(const UEdge& uedge) {
593      getNotifier(Edge()).erase(Parent::direct(uedge, true));
594      getNotifier(Edge()).erase(Parent::direct(uedge, false));
595      getNotifier(UEdge()).erase(uedge);
596      Parent::erase(uedge);
597    }
598
599
600    ~UEdgeSetExtender() {
601      getNotifier(Edge()).clear();
602      getNotifier(UEdge()).clear();
603    }
604   
605  };
606}
Note: See TracBrowser for help on using the repository browser.