COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/ugraph_extender.h @ 2115:4cd528a30ec1

Last change on this file since 2115:4cd528a30ec1 was 2115:4cd528a30ec1, checked in by Balazs Dezso, 13 years ago

Splitted graph files

File size: 10.0 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#ifndef LEMON_BITS_UGRAPH_EXTENDER_H
20#define LEMON_BITS_UGRAPH_EXTENDER_H
21
22#include <lemon/bits/invalid.h>
23#include <lemon/error.h>
24
25#include <lemon/bits/map_extender.h>
26#include <lemon/bits/default_map.h>
27
28#include <lemon/concept_check.h>
29#include <lemon/concept/maps.h>
30
31///\ingroup graphbits
32///\file
33///\brief Extenders for the graph types
34namespace lemon {
35
36  /// \ingroup graphbits
37  ///
38  /// \brief Extender for the UGraphs
39  template <typename Base>
40  class UGraphExtender : public Base {
41  public:
42   
43    typedef Base Parent;
44    typedef UGraphExtender Graph;
45
46    typedef typename Parent::Node Node;
47    typedef typename Parent::Edge Edge;
48    typedef typename Parent::UEdge UEdge;
49
50    // UGraph extension   
51
52    int maxId(Node) const {
53      return Parent::maxNodeId();
54    }
55
56    int maxId(Edge) const {
57      return Parent::maxEdgeId();
58    }
59
60    int maxId(UEdge) const {
61      return Parent::maxUEdgeId();
62    }
63
64    Node fromId(int id, Node) const {
65      return Parent::nodeFromId(id);
66    }
67
68    Edge fromId(int id, Edge) const {
69      return Parent::edgeFromId(id);
70    }
71
72    UEdge fromId(int id, UEdge) const {
73      return Parent::uEdgeFromId(id);
74    }
75
76    Node oppositeNode(const Node &n, const UEdge &e) const {
77      if( n == Parent::source(e))
78        return Parent::target(e);
79      else if( n == Parent::target(e))
80        return Parent::source(e);
81      else
82        return INVALID;
83    }
84
85    Edge oppositeEdge(const Edge &e) const {
86      return Parent::direct(e, !Parent::direction(e));
87    }
88
89    using Parent::direct;
90    Edge direct(const UEdge &ue, const Node &s) const {
91      return Parent::direct(ue, Parent::source(ue) == s);
92    }
93
94    // Alterable extension
95
96    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
97    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
98    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
99
100
101  protected:
102
103    mutable NodeNotifier node_notifier;
104    mutable EdgeNotifier edge_notifier;
105    mutable UEdgeNotifier uedge_notifier;
106
107  public:
108
109    NodeNotifier& getNotifier(Node) const {
110      return node_notifier;
111    }
112   
113    EdgeNotifier& getNotifier(Edge) const {
114      return edge_notifier;
115    }
116
117    UEdgeNotifier& getNotifier(UEdge) const {
118      return uedge_notifier;
119    }
120
121
122
123    class NodeIt : public Node {
124      const Graph* graph;
125    public:
126
127      NodeIt() {}
128
129      NodeIt(Invalid i) : Node(i) { }
130
131      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
132        _graph.first(static_cast<Node&>(*this));
133      }
134
135      NodeIt(const Graph& _graph, const Node& node)
136        : Node(node), graph(&_graph) {}
137
138      NodeIt& operator++() {
139        graph->next(*this);
140        return *this;
141      }
142
143    };
144
145
146    class EdgeIt : public Edge {
147      const Graph* graph;
148    public:
149
150      EdgeIt() { }
151
152      EdgeIt(Invalid i) : Edge(i) { }
153
154      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
155        _graph.first(static_cast<Edge&>(*this));
156      }
157
158      EdgeIt(const Graph& _graph, const Edge& e) :
159        Edge(e), graph(&_graph) { }
160
161      EdgeIt& operator++() {
162        graph->next(*this);
163        return *this;
164      }
165
166    };
167
168
169    class OutEdgeIt : public Edge {
170      const Graph* graph;
171    public:
172
173      OutEdgeIt() { }
174
175      OutEdgeIt(Invalid i) : Edge(i) { }
176
177      OutEdgeIt(const Graph& _graph, const Node& node)
178        : graph(&_graph) {
179        _graph.firstOut(*this, node);
180      }
181
182      OutEdgeIt(const Graph& _graph, const Edge& edge)
183        : Edge(edge), graph(&_graph) {}
184
185      OutEdgeIt& operator++() {
186        graph->nextOut(*this);
187        return *this;
188      }
189
190    };
191
192
193    class InEdgeIt : public Edge {
194      const Graph* graph;
195    public:
196
197      InEdgeIt() { }
198
199      InEdgeIt(Invalid i) : Edge(i) { }
200
201      InEdgeIt(const Graph& _graph, const Node& node)
202        : graph(&_graph) {
203        _graph.firstIn(*this, node);
204      }
205
206      InEdgeIt(const Graph& _graph, const Edge& edge) :
207        Edge(edge), graph(&_graph) {}
208
209      InEdgeIt& operator++() {
210        graph->nextIn(*this);
211        return *this;
212      }
213
214    };
215
216
217    class UEdgeIt : public Parent::UEdge {
218      const Graph* graph;
219    public:
220
221      UEdgeIt() { }
222
223      UEdgeIt(Invalid i) : UEdge(i) { }
224
225      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
226        _graph.first(static_cast<UEdge&>(*this));
227      }
228
229      UEdgeIt(const Graph& _graph, const UEdge& e) :
230        UEdge(e), graph(&_graph) { }
231
232      UEdgeIt& operator++() {
233        graph->next(*this);
234        return *this;
235      }
236
237    };
238
239    class IncEdgeIt : public Parent::UEdge {
240      friend class UGraphExtender;
241      const Graph* graph;
242      bool direction;
243    public:
244
245      IncEdgeIt() { }
246
247      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
248
249      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
250        _graph.firstInc(*this, direction, n);
251      }
252
253      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
254        : graph(&_graph), UEdge(ue) {
255        direction = (_graph.source(ue) == n);
256      }
257
258      IncEdgeIt& operator++() {
259        graph->nextInc(*this, direction);
260        return *this;
261      }
262    };
263
264    /// \brief Base node of the iterator
265    ///
266    /// Returns the base node (ie. the source in this case) of the iterator
267    Node baseNode(const OutEdgeIt &e) const {
268      return Parent::source((Edge)e);
269    }
270    /// \brief Running node of the iterator
271    ///
272    /// Returns the running node (ie. the target in this case) of the
273    /// iterator
274    Node runningNode(const OutEdgeIt &e) const {
275      return Parent::target((Edge)e);
276    }
277
278    /// \brief Base node of the iterator
279    ///
280    /// Returns the base node (ie. the target in this case) of the iterator
281    Node baseNode(const InEdgeIt &e) const {
282      return Parent::target((Edge)e);
283    }
284    /// \brief Running node of the iterator
285    ///
286    /// Returns the running node (ie. the source in this case) of the
287    /// iterator
288    Node runningNode(const InEdgeIt &e) const {
289      return Parent::source((Edge)e);
290    }
291
292    /// Base node of the iterator
293    ///
294    /// Returns the base node of the iterator
295    Node baseNode(const IncEdgeIt &e) const {
296      return e.direction ? source(e) : target(e);
297    }
298    /// Running node of the iterator
299    ///
300    /// Returns the running node of the iterator
301    Node runningNode(const IncEdgeIt &e) const {
302      return e.direction ? target(e) : source(e);
303    }
304
305    // Mappable extension
306
307    template <typename _Value>
308    class NodeMap
309      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
310    public:
311      typedef UGraphExtender Graph;
312      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
313
314      NodeMap(const Graph& graph)
315        : Parent(graph) {}
316      NodeMap(const Graph& graph, const _Value& value)
317        : Parent(graph, value) {}
318
319      NodeMap& operator=(const NodeMap& cmap) {
320        return operator=<NodeMap>(cmap);
321      }
322
323      template <typename CMap>
324      NodeMap& operator=(const CMap& cmap) {
325        Parent::operator=(cmap);
326        return *this;
327      }
328
329    };
330
331    template <typename _Value>
332    class EdgeMap
333      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
334    public:
335      typedef UGraphExtender Graph;
336      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
337
338      EdgeMap(const Graph& graph)
339        : Parent(graph) {}
340      EdgeMap(const Graph& graph, const _Value& value)
341        : Parent(graph, value) {}
342
343      EdgeMap& operator=(const EdgeMap& cmap) {
344        return operator=<EdgeMap>(cmap);
345      }
346
347      template <typename CMap>
348      EdgeMap& operator=(const CMap& cmap) {
349        Parent::operator=(cmap);
350        return *this;
351      }
352    };
353
354
355    template <typename _Value>
356    class UEdgeMap
357      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
358    public:
359      typedef UGraphExtender Graph;
360      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
361
362      UEdgeMap(const Graph& graph)
363        : Parent(graph) {}
364
365      UEdgeMap(const Graph& graph, const _Value& value)
366        : Parent(graph, value) {}
367
368      UEdgeMap& operator=(const UEdgeMap& cmap) {
369        return operator=<UEdgeMap>(cmap);
370      }
371
372      template <typename CMap>
373      UEdgeMap& operator=(const CMap& cmap) {
374        Parent::operator=(cmap);
375        return *this;
376      }
377
378    };
379
380    // Alteration extension
381
382    Node addNode() {
383      Node node = Parent::addNode();
384      getNotifier(Node()).add(node);
385      return node;
386    }
387
388    UEdge addEdge(const Node& from, const Node& to) {
389      UEdge uedge = Parent::addEdge(from, to);
390      getNotifier(UEdge()).add(uedge);
391      getNotifier(Edge()).add(Parent::direct(uedge, true));
392      getNotifier(Edge()).add(Parent::direct(uedge, false));
393      return uedge;
394    }
395   
396    void clear() {
397      getNotifier(Edge()).clear();
398      getNotifier(UEdge()).clear();
399      getNotifier(Node()).clear();
400      Parent::clear();
401    }
402
403    void erase(const Node& node) {
404      Edge edge;
405      Parent::firstOut(edge, node);
406      while (edge != INVALID ) {
407        erase(edge);
408        Parent::firstOut(edge, node);
409      }
410
411      Parent::firstIn(edge, node);
412      while (edge != INVALID ) {
413        erase(edge);
414        Parent::firstIn(edge, node);
415      }
416
417      getNotifier(Node()).erase(node);
418      Parent::erase(node);
419    }
420
421    void erase(const UEdge& uedge) {
422      getNotifier(Edge()).erase(Parent::direct(uedge, true));
423      getNotifier(Edge()).erase(Parent::direct(uedge, false));
424      getNotifier(UEdge()).erase(uedge);
425      Parent::erase(uedge);
426    }
427
428    UGraphExtender() {
429      node_notifier.setContainer(*this);
430      edge_notifier.setContainer(*this);
431      uedge_notifier.setContainer(*this);
432    }
433
434    ~UGraphExtender() {
435      uedge_notifier.clear();
436      edge_notifier.clear();
437      node_notifier.clear();
438    }
439
440  };
441
442}
443
444#endif
Note: See TracBrowser for help on using the repository browser.