COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edge_set.h @ 1909:2d806130e700

Last change on this file since 1909:2d806130e700 was 1909:2d806130e700, checked in by Mihaly Barasz, 14 years ago

Undir -> U transition

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