COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 1956:a055123339d5

Last change on this file since 1956:a055123339d5 was 1956:a055123339d5, checked in by Alpar Juttner, 14 years ago

Unified copyright notices

File size: 9.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_EDGE_SET_H
20#define LEMON_EDGE_SET_H
21
22/// \ingroup graphs
23/// \file
24/// \brief EdgeSet classes.
25///
26/// Graphs which use another graph's node-set as own.
27
28namespace lemon {
29
30  template <typename _Graph>
31  class ListEdgeSetBase {
32  public:
33
34    typedef _Graph Graph;
35    typedef typename Graph::Node Node;
36    typedef typename Graph::NodeIt NodeIt;
37
38  protected:
39
40    struct NodeT {
41      int first_out, first_in;
42      NodeT() : first_out(-1), first_in(-1) {}
43    };
44
45    typedef typename Graph::template NodeMap<NodeT> NodesImplBase;
46
47    NodesImplBase* nodes;
48
49    struct EdgeT {
50      Node source, target;
51      int next_out, next_in;
52      int prev_out, prev_in;
53      EdgeT() : prev_out(-1), prev_in(-1) {}
54    };
55
56    std::vector<EdgeT> edges;
57
58    int first_edge;
59    int first_free_edge;
60
61    const Graph* graph;
62
63    void initalize(const Graph& _graph, NodesImplBase& _nodes) {
64      graph = &_graph;
65      nodes = &_nodes;
66    }
67   
68  public:
69
70    class Edge {
71      friend class ListEdgeSetBase<Graph>;
72    protected:
73      Edge(int _id) : id(_id) {}
74      int id;
75    public:
76      Edge() {}
77      Edge(Invalid) : id(-1) {}
78      bool operator==(const Edge& edge) const { return id == edge.id; }
79      bool operator!=(const Edge& edge) const { return id != edge.id; }
80      bool operator<(const Edge& edge) const { return id < edge.id; }
81    };
82
83    ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {}
84
85    Edge addEdge(const Node& source, const Node& target) {
86      int n;
87      if (first_free_edge == -1) {
88        n = edges.size();
89        edges.push_back(EdgeT());
90      } else {
91        n = first_free_edge;
92        first_free_edge = edges[first_free_edge].next_in;
93      }
94      edges[n].next_in = (*nodes)[target].first_in;
95      (*nodes)[target].first_in = n;
96      edges[n].next_out = (*nodes)[source].first_out;
97      (*nodes)[source].first_out = n;
98      edges[n].source = source;
99      edges[n].target = target;
100      return Edge(n);
101    }
102
103    void erase(const Edge& edge) {
104      int n = edge.id;
105      if (edges[n].prev_in != -1) {
106        edges[edges[n].prev_in].next_in = edges[n].next_in;
107      } else {
108        (*nodes)[edges[n].target].first_in = edges[n].next_in;
109      }
110      if (edges[n].next_in != -1) {
111        edges[edges[n].next_in].prev_in = edges[n].prev_in;
112      }
113
114      if (edges[n].prev_out != -1) {
115        edges[edges[n].prev_out].next_out = edges[n].next_out;
116      } else {
117        (*nodes)[edges[n].source].first_out = edges[n].next_out;
118      }
119      if (edges[n].next_out != -1) {
120        edges[edges[n].next_out].prev_out = edges[n].prev_out;
121      }
122           
123    }
124
125    void clear() {
126      edges.clear();
127      first_edge = -1;
128      first_free_edge = -1;
129    }
130
131    void first(Node& node) const {
132      graph->first(node);
133    }
134
135    void next(Node& node) const {
136      graph->next(node);
137    }
138
139    void first(Edge& edge) const {
140      Node node;
141      for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
142           next(node));
143      edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
144    }
145
146    void next(Edge& edge) const {
147      if (edges[edge.id].next_in != -1) {
148        edge.id = edges[edge.id].next_in;
149      } else {
150        Node node = edges[edge.id].target;
151        for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
152             next(node));
153        edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
154      }     
155    }
156
157    void firstOut(Edge& edge, const Node& node) const {
158      edge.id = (*nodes)[node].first_out;   
159    }
160   
161    void nextOut(Edge& edge) const {
162      edge.id = edges[edge.id].next_out;       
163    }
164
165    void firstIn(Edge& edge, const Node& node) const {
166      edge.id = (*nodes)[node].first_in;         
167    }
168
169    void nextIn(Edge& edge) const {
170      edge.id = edges[edge.id].next_in;   
171    }
172
173    int id(const Node& node) const { return graph->id(node); }
174    int id(const Edge& edge) const { return edge.id; }
175
176    Node nodeFromId(int id) const { return graph->fromId(id, Node()); }
177    Edge edgeFromId(int id) const { return Edge(id); }
178
179    int maxNodeId() const { return graph->maxId(Node()); };
180    int maxEdgeId() const { return edges.size() - 1; }
181
182    Node source(const Edge& edge) const { return edges[edge.id].source;}
183    Node target(const Edge& edge) const { return edges[edge.id].target;}
184
185    template <typename _Value>
186    class NodeMap : public Graph::template NodeMap<_Value> {
187    public:
188      typedef typename _Graph::template NodeMap<_Value> Parent;
189      explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset)
190        : Parent(*edgeset.graph) { }
191      NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
192        : Parent(*edgeset.graph, value) { }
193    };
194
195  };
196
197  /// \ingroup semi_adaptors
198  ///
199  /// \brief Graph using a node set of another graph and an
200  /// own edge set.
201  ///
202  /// This structure can be used to establish another graph over a node set
203  /// of an existing one. The node iterator will go through the nodes of the
204  /// original graph.
205  ///
206  /// \param _Graph The type of the graph which shares its node set with
207  /// this class. Its interface must conform to the \ref concept::StaticGraph
208  /// "StaticGraph" concept.
209  ///
210  /// In the edge extension and removing it conforms to the
211  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
212  template <typename _Graph>
213  class ListEdgeSet :
214    public ErasableEdgeSetExtender<
215    ClearableEdgeSetExtender<
216    ExtendableEdgeSetExtender<
217    MappableEdgeSetExtender<
218    IterableGraphExtender<
219    AlterableEdgeSetExtender<
220    GraphExtender<
221    ListEdgeSetBase<_Graph> > > > > > > > {
222
223  public:
224
225    typedef ErasableEdgeSetExtender<
226      ClearableEdgeSetExtender<
227      ExtendableEdgeSetExtender<
228      MappableEdgeSetExtender<
229      IterableGraphExtender<
230      AlterableEdgeSetExtender<
231      GraphExtender<
232      ListEdgeSetBase<_Graph> > > > > > > > Parent;
233   
234    typedef typename Parent::Node Node;
235    typedef typename Parent::Edge Edge;
236   
237    typedef _Graph Graph;
238
239
240    typedef typename Parent::NodesImplBase NodesImplBase;
241
242    void eraseNode(const Node& node) {
243      Edge edge;
244      Parent::firstOut(edge, node);
245      while (edge != INVALID ) {
246        erase(edge);
247        Parent::firstOut(edge, node);
248      }
249
250      Parent::firstIn(edge, node);
251      while (edge != INVALID ) {
252        erase(edge);
253        Parent::firstIn(edge, node);
254      }
255    }
256   
257    void clearNodes() {
258      Parent::clear();
259    }
260
261    class NodesImpl : public NodesImplBase {
262    public:
263      typedef NodesImplBase Parent;
264     
265      NodesImpl(const Graph& graph, ListEdgeSet& edgeset)
266        : Parent(graph), _edgeset(edgeset) {}
267     
268    protected:
269
270      virtual void erase(const Node& node) {
271        _edgeset.eraseNode(node);
272        Parent::erase(node);
273      }
274      virtual void clear() {
275        _edgeset.clearNodes();
276        Parent::clear();
277      }
278
279    private:
280      ListEdgeSet& _edgeset;
281    };
282
283    NodesImpl nodes;
284   
285  public:
286
287    /// \brief Constructor of the adaptor.
288    ///
289    /// Constructor of the adaptor.
290    ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
291      Parent::initalize(graph, nodes);
292    }
293   
294  };
295
296  /// \ingroup semi_adaptors
297  ///
298  /// \brief Graph using a node set of another graph and an
299  /// own uedge set.
300  ///
301  /// This structure can be used to establish another graph over a node set
302  /// of an existing one. The node iterator will go through the nodes of the
303  /// original graph.
304  ///
305  /// \param _Graph The type of the graph which shares its node set with
306  /// this class. Its interface must conform to the \ref concept::StaticGraph
307  /// "StaticGraph" concept.
308  ///
309  /// In the edge extension and removing it conforms to the
310  /// \ref concept::ExtendableGraph "ExtendableGraph" concept.
311  template <typename _Graph>
312  class ListUEdgeSet :
313    public ErasableUEdgeSetExtender<
314    ClearableUEdgeSetExtender<
315    ExtendableUEdgeSetExtender<
316    MappableUEdgeSetExtender<
317    IterableUGraphExtender<
318    AlterableUEdgeSetExtender<
319    UGraphExtender<
320    ListEdgeSetBase<_Graph> > > > > > > > {
321
322  public:
323
324    typedef ErasableUEdgeSetExtender<
325      ClearableUEdgeSetExtender<
326      ExtendableUEdgeSetExtender<
327      MappableUEdgeSetExtender<
328      IterableUGraphExtender<
329      AlterableUEdgeSetExtender<
330      UGraphExtender<
331      ListEdgeSetBase<_Graph> > > > > > > > Parent;
332   
333    typedef typename Parent::Node Node;
334    typedef typename Parent::Edge Edge;
335   
336    typedef _Graph Graph;
337
338
339    typedef typename Parent::NodesImplBase NodesImplBase;
340
341    void eraseNode(const Node& node) {
342      Edge edge;
343      Parent::firstOut(edge, node);
344      while (edge != INVALID ) {
345        erase(edge);
346        Parent::firstOut(edge, node);
347      }
348
349    }
350   
351    void clearNodes() {
352      Parent::clear();
353    }
354
355    class NodesImpl : public NodesImplBase {
356    public:
357      typedef NodesImplBase Parent;
358     
359      NodesImpl(const Graph& graph, ListUEdgeSet& edgeset)
360        : Parent(graph), _edgeset(edgeset) {}
361     
362    protected:
363
364      virtual void erase(const Node& node) {
365        _edgeset.eraseNode(node);
366        Parent::erase(node);
367      }
368      virtual void erase(const std::vector<Node>& nodes) {
369        for (int i = 0; i < nodes.size(); ++i) {
370          _edgeset.eraseNode(nodes[i]);
371        }
372        Parent::erase(nodes);
373      }
374      virtual void clear() {
375        _edgeset.clearNodes();
376        Parent::clear();
377      }
378
379    private:
380      ListUEdgeSet& _edgeset;
381    };
382
383    NodesImpl nodes;
384   
385  public:
386
387    /// \brief Constructor of the adaptor.
388    ///
389    /// Constructor of the adaptor.
390    ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
391      Parent::initalize(graph, nodes);
392    }
393   
394  };
395
396}
397
398#endif
Note: See TracBrowser for help on using the repository browser.