COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/list_graph.h @ 949:b16a10926781

Last change on this file since 949:b16a10926781 was 949:b16a10926781, checked in by Alpar Juttner, 16 years ago

ListGraph? compilation bug fixed.

File size: 8.4 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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_LIST_GRAPH_H
18#define LEMON_LIST_GRAPH_H
19
20///\ingroup graphs
21///\file
22///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
23
24#include <lemon/erasable_graph_extender.h>
25#include <lemon/clearable_graph_extender.h>
26#include <lemon/extendable_graph_extender.h>
27
28#include <lemon/idmappable_graph_extender.h>
29
30#include <lemon/iterable_graph_extender.h>
31
32#include <lemon/alteration_observer_registry.h>
33
34#include <lemon/default_map.h>
35
36
37namespace lemon {
38
39  class ListGraphBase {
40
41  protected:
42    struct NodeT {
43      int first_in,first_out;
44      int prev, next;
45    };
46 
47    struct EdgeT {
48      int head, tail;
49      int prev_in, prev_out;
50      int next_in, next_out;
51    };
52
53    std::vector<NodeT> nodes;
54
55    int first_node;
56
57    int first_free_node;
58
59    std::vector<EdgeT> edges;
60
61    int first_free_edge;
62   
63  public:
64   
65    typedef ListGraphBase Graph;
66   
67    class Node {
68      friend class Graph;
69    protected:
70
71      int id;
72      Node(int pid) { id = pid;}
73
74    public:
75      Node() {}
76      Node (Invalid) { id = -1; }
77      bool operator==(const Node& node) const {return id == node.id;}
78      bool operator!=(const Node& node) const {return id != node.id;}
79      bool operator<(const Node& node) const {return id < node.id;}
80    };
81
82    class Edge {
83      friend class Graph;
84    protected:
85
86      int id;
87      Edge(int pid) { id = pid;}
88
89    public:
90      Edge() {}
91      Edge (Invalid) { id = -1; }
92      bool operator==(const Edge& edge) const {return id == edge.id;}
93      bool operator!=(const Edge& edge) const {return id != edge.id;}
94      bool operator<(const Edge& edge) const {return id < edge.id;}
95    };
96
97
98
99    ListGraphBase()
100      : nodes(), first_node(-1),
101        first_free_node(-1), edges(), first_free_edge(-1) {}
102
103   
104    /// Maximum node ID.
105   
106    /// Maximum node ID.
107    ///\sa id(Node)
108    int maxNodeId() const { return nodes.size()-1; }
109
110    /// Maximum edge ID.
111   
112    /// Maximum edge ID.
113    ///\sa id(Edge)
114    int maxEdgeId() const { return edges.size()-1; }
115
116    Node tail(Edge e) const { return edges[e.id].tail; }
117    Node head(Edge e) const { return edges[e.id].head; }
118
119
120    void first(Node& node) const {
121      node.id = first_node;
122    }
123
124    void next(Node& node) const {
125      node.id = nodes[node.id].next;
126    }
127
128
129    void first(Edge& e) const {
130      int n;
131      for(n = first_node;
132          n!=-1 && nodes[n].first_in == -1;
133          n = nodes[n].next);
134      e.id = (n == -1) ? -1 : nodes[n].first_in;
135    }
136
137    void next(Edge& edge) const {
138      if (edges[edge.id].next_in != -1) {
139        edge.id = edges[edge.id].next_in;
140      } else {
141        int n;
142        for(n = nodes[edges[edge.id].head].next;
143          n!=-1 && nodes[n].first_in == -1;
144          n = nodes[n].next);
145        edge.id = (n == -1) ? -1 : nodes[n].first_in;
146      }     
147    }
148
149    void firstOut(Edge &e, const Node& v) const {
150      e.id = nodes[v.id].first_out;
151    }
152    void nextOut(Edge &e) const {
153      e.id=edges[e.id].next_out;
154    }
155
156    void firstIn(Edge &e, const Node& v) const {
157      e.id = nodes[v.id].first_in;
158    }
159    void nextIn(Edge &e) const {
160      e.id=edges[e.id].next_in;
161    }
162
163   
164    static int id(Node v) { return v.id; }
165    static int id(Edge e) { return e.id; }
166
167    /// Adds a new node to the graph.
168
169    /// \warning It adds the new node to the front of the list.
170    /// (i.e. the lastly added node becomes the first.)
171    Node addNode() {     
172      int n;
173     
174      if(first_free_node==-1) {
175        n = nodes.size();
176        nodes.push_back(NodeT());
177      } else {
178        n = first_free_node;
179        first_free_node = nodes[n].next;
180      }
181     
182      nodes[n].next = first_node;
183      if(first_node != -1) nodes[first_node].prev = n;
184      first_node = n;
185      nodes[n].prev = -1;
186     
187      nodes[n].first_in = nodes[n].first_out = -1;
188     
189      return Node(n);
190    }
191   
192    Edge addEdge(Node u, Node v) {
193      int n;     
194
195      if (first_free_edge == -1) {
196        n = edges.size();
197        edges.push_back(EdgeT());
198      } else {
199        n = first_free_edge;
200        first_free_edge = edges[n].next_in;
201      }
202     
203      edges[n].tail = u.id;
204      edges[n].head = v.id;
205
206      edges[n].next_out = nodes[u.id].first_out;
207      if(nodes[u.id].first_out != -1) {
208        edges[nodes[u.id].first_out].prev_out = n;
209      }
210     
211      edges[n].next_in = nodes[v.id].first_in;
212      if(nodes[v.id].first_in != -1) {
213        edges[nodes[v.id].first_in].prev_in = n;
214      }
215     
216      edges[n].prev_in = edges[n].prev_out = -1;
217       
218      nodes[u.id].first_out = nodes[v.id].first_in = n;
219
220      return Edge(n);
221    }
222   
223    void erase(const Node& node) {
224      int n = node.id;
225     
226      if(nodes[n].next != -1) {
227        nodes[nodes[n].next].prev = nodes[n].prev;
228      }
229     
230      if(nodes[n].prev != -1) {
231        nodes[nodes[n].prev].next = nodes[n].next;
232      } else {
233        first_node = nodes[n].next;
234      }
235     
236      nodes[n].next = first_free_node;
237      first_free_node = n;
238
239    }
240   
241    void erase(const Edge& edge) {
242      int n = edge.id;
243     
244      if(edges[n].next_in!=-1) {
245        edges[edges[n].next_in].prev_in = edges[n].prev_in;
246      }
247
248      if(edges[n].prev_in!=-1) {
249        edges[edges[n].prev_in].next_in = edges[n].next_in;
250      } else {
251        nodes[edges[n].head].first_in = edges[n].next_in;
252      }
253
254     
255      if(edges[n].next_out!=-1) {
256        edges[edges[n].next_out].prev_out = edges[n].prev_out;
257      }
258
259      if(edges[n].prev_out!=-1) {
260        edges[edges[n].prev_out].next_out = edges[n].next_out;
261      } else {
262        nodes[edges[n].tail].first_out = edges[n].next_out;
263      }
264     
265      edges[n].next_in = first_free_edge;
266      first_free_edge = n;     
267
268    }
269
270    void clear() {
271      edges.clear();
272      nodes.clear();
273      first_node = first_free_node = first_free_edge = -1;
274    }
275
276  protected:
277    void _moveHead(Edge e, Node n)
278    {
279      if(edges[e.id].next_in != -1)
280        edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
281      if(edges[e.id].prev_in != -1)
282        edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
283      else nodes[edges[e.id].head].first_in = edges[e.id].next_in;
284      edges[e.id].head = n.id;
285      edges[e.id].prev_in = -1;
286      edges[e.id].next_in = nodes[n.id].first_in;
287      nodes[n.id].first_in = e.id;
288    }
289    void _moveTail(Edge e, Node n)
290    {
291      if(edges[e.id].next_out != -1)
292        edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
293      if(edges[e.id].prev_out != -1)
294        edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
295      else nodes[edges[e.id].tail].first_out = edges[e.id].next_out;
296      edges[e.id].tail = n.id;
297      edges[e.id].prev_out = -1;
298      edges[e.id].next_out = nodes[n.id].first_out;
299      nodes[n.id].first_out = e.id;
300    }
301
302  };
303
304  typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
305  typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
306  typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
307  typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
308  typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
309  typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
310  typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
311
312/// \addtogroup graphs
313/// @{
314
315  ///A list graph class.
316
317  ///This is a simple and fast erasable graph implementation.
318  ///
319  ///It conforms to the
320  ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
321  ///\sa skeleton::ErasableGraph.
322
323  class ListGraph : public ErasableListGraphBase
324  {
325  public:
326    /// Moves the head of \c e to \c n
327
328    /// Moves the head of \c e to \c n
329    ///
330    void moveHead(Edge e, Node n) { _moveHead(e,n); }
331    /// Moves the tail of \c e to \c n
332
333    /// Moves the tail of \c e to \c n
334    ///
335    void moveTail(Edge e, Node n) { _moveTail(e,n); }
336
337    ///Using this it possible to avoid the superfluous memory allocation.
338    ///\todo more docs...
339    void reserveEdge(int n) { edges.reserve(n); };
340   
341  };
342 
343  /// @} 
344} //namespace lemon
345 
346
347#endif
Note: See TracBrowser for help on using the repository browser.