COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bits/graph_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: 6.9 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_GRAPH_EXTENDER_H
20#define LEMON_BITS_GRAPH_EXTENDER_H
21
22#include <lemon/bits/invalid.h>
23
24#include <lemon/bits/map_extender.h>
25#include <lemon/bits/default_map.h>
26
27///\ingroup graphbits
28///\file
29///\brief Extenders for the graph types
30namespace lemon {
31
32  /// \ingroup graphbits
33  ///
34  /// \brief Extender for the Graphs
35  template <typename Base>
36  class GraphExtender : public Base {
37  public:
38
39    typedef Base Parent;
40    typedef GraphExtender Graph;
41
42    // Base extensions
43
44    typedef typename Parent::Node Node;
45    typedef typename Parent::Edge Edge;
46
47    int maxId(Node) const {
48      return Parent::maxNodeId();
49    }
50
51    int maxId(Edge) const {
52      return Parent::maxEdgeId();
53    }
54
55    Node fromId(int id, Node) const {
56      return Parent::nodeFromId(id);
57    }
58
59    Edge fromId(int id, Edge) const {
60      return Parent::edgeFromId(id);
61    }
62
63    Node oppositeNode(const Node &n, const Edge &e) const {
64      if (n == Parent::source(e))
65        return Parent::target(e);
66      else if(n==Parent::target(e))
67        return Parent::source(e);
68      else
69        return INVALID;
70    }
71
72    // Alterable extension
73
74    typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
75    typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
76
77
78  protected:
79
80    mutable NodeNotifier node_notifier;
81    mutable EdgeNotifier edge_notifier;
82
83  public:
84
85    NodeNotifier& getNotifier(Node) const {
86      return node_notifier;
87    }
88   
89    EdgeNotifier& getNotifier(Edge) const {
90      return edge_notifier;
91    }
92
93    class NodeIt : public Node {
94      const Graph* graph;
95    public:
96
97      NodeIt() {}
98
99      NodeIt(Invalid i) : Node(i) { }
100
101      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
102        _graph.first(static_cast<Node&>(*this));
103      }
104
105      NodeIt(const Graph& _graph, const Node& node)
106        : Node(node), graph(&_graph) {}
107
108      NodeIt& operator++() {
109        graph->next(*this);
110        return *this;
111      }
112
113    };
114
115
116    class EdgeIt : public Edge {
117      const Graph* graph;
118    public:
119
120      EdgeIt() { }
121
122      EdgeIt(Invalid i) : Edge(i) { }
123
124      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
125        _graph.first(static_cast<Edge&>(*this));
126      }
127
128      EdgeIt(const Graph& _graph, const Edge& e) :
129        Edge(e), graph(&_graph) { }
130
131      EdgeIt& operator++() {
132        graph->next(*this);
133        return *this;
134      }
135
136    };
137
138
139    class OutEdgeIt : public Edge {
140      const Graph* graph;
141    public:
142
143      OutEdgeIt() { }
144
145      OutEdgeIt(Invalid i) : Edge(i) { }
146
147      OutEdgeIt(const Graph& _graph, const Node& node)
148        : graph(&_graph) {
149        _graph.firstOut(*this, node);
150      }
151
152      OutEdgeIt(const Graph& _graph, const Edge& edge)
153        : Edge(edge), graph(&_graph) {}
154
155      OutEdgeIt& operator++() {
156        graph->nextOut(*this);
157        return *this;
158      }
159
160    };
161
162
163    class InEdgeIt : public Edge {
164      const Graph* graph;
165    public:
166
167      InEdgeIt() { }
168
169      InEdgeIt(Invalid i) : Edge(i) { }
170
171      InEdgeIt(const Graph& _graph, const Node& node)
172        : graph(&_graph) {
173        _graph.firstIn(*this, node);
174      }
175
176      InEdgeIt(const Graph& _graph, const Edge& edge) :
177        Edge(edge), graph(&_graph) {}
178
179      InEdgeIt& operator++() {
180        graph->nextIn(*this);
181        return *this;
182      }
183
184    };
185
186    /// \brief Base node of the iterator
187    ///
188    /// Returns the base node (i.e. the source in this case) of the iterator
189    Node baseNode(const OutEdgeIt &e) const {
190      return Parent::source(e);
191    }
192    /// \brief Running node of the iterator
193    ///
194    /// Returns the running node (i.e. the target in this case) of the
195    /// iterator
196    Node runningNode(const OutEdgeIt &e) const {
197      return Parent::target(e);
198    }
199
200    /// \brief Base node of the iterator
201    ///
202    /// Returns the base node (i.e. the target in this case) of the iterator
203    Node baseNode(const InEdgeIt &e) const {
204      return Parent::target(e);
205    }
206    /// \brief Running node of the iterator
207    ///
208    /// Returns the running node (i.e. the source in this case) of the
209    /// iterator
210    Node runningNode(const InEdgeIt &e) const {
211      return Parent::source(e);
212    }
213
214   
215    template <typename _Value>
216    class NodeMap
217      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
218    public:
219      typedef GraphExtender Graph;
220      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
221
222      explicit NodeMap(const Graph& graph)
223        : Parent(graph) {}
224      NodeMap(const Graph& graph, const _Value& value)
225        : Parent(graph, value) {}
226
227      NodeMap& operator=(const NodeMap& cmap) {
228        return operator=<NodeMap>(cmap);
229      }
230
231      template <typename CMap>
232      NodeMap& operator=(const CMap& cmap) {
233        Parent::operator=(cmap);
234        return *this;
235      }
236
237    };
238
239    template <typename _Value>
240    class EdgeMap
241      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
242    public:
243      typedef GraphExtender Graph;
244      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
245
246      explicit EdgeMap(const Graph& graph)
247        : Parent(graph) {}
248      EdgeMap(const Graph& graph, const _Value& value)
249        : Parent(graph, value) {}
250
251      EdgeMap& operator=(const EdgeMap& cmap) {
252        return operator=<EdgeMap>(cmap);
253      }
254
255      template <typename CMap>
256      EdgeMap& operator=(const CMap& cmap) {
257        Parent::operator=(cmap);
258        return *this;
259      }
260    };
261
262
263    Node addNode() {
264      Node node = Parent::addNode();
265      getNotifier(Node()).add(node);
266      return node;
267    }
268   
269    Edge addEdge(const Node& from, const Node& to) {
270      Edge edge = Parent::addEdge(from, to);
271      getNotifier(Edge()).add(edge);
272      return edge;
273    }
274
275    void clear() {
276      getNotifier(Edge()).clear();
277      getNotifier(Node()).clear();
278      Parent::clear();
279    }
280
281
282    void erase(const Node& node) {
283      Edge edge;
284      Parent::firstOut(edge, node);
285      while (edge != INVALID ) {
286        erase(edge);
287        Parent::firstOut(edge, node);
288      }
289
290      Parent::firstIn(edge, node);
291      while (edge != INVALID ) {
292        erase(edge);
293        Parent::firstIn(edge, node);
294      }
295
296      getNotifier(Node()).erase(node);
297      Parent::erase(node);
298    }
299   
300    void erase(const Edge& edge) {
301      getNotifier(Edge()).erase(edge);
302      Parent::erase(edge);
303    }
304
305    GraphExtender() {
306      node_notifier.setContainer(*this);
307      edge_notifier.setContainer(*this);
308    }
309   
310
311    ~GraphExtender() {
312      edge_notifier.clear();
313      node_notifier.clear();
314    }
315  };
316
317}
318
319#endif
Note: See TracBrowser for help on using the repository browser.