COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/list_graph.h @ 1012:2bfbe3f4307c

Last change on this file since 1012:2bfbe3f4307c was 1012:2bfbe3f4307c, checked in by Alpar Juttner, 16 years ago

ObserverRegistry? base classed in SnapShot? has changed to be protected

File size: 12.7 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/iterable_graph_extender.h>
29
30#include <lemon/alteration_observer_registry.h>
31
32#include <lemon/default_map.h>
33
34#include <list>
35
36namespace lemon {
37
38  class ListGraphBase {
39
40  protected:
41    struct NodeT {
42      int first_in,first_out;
43      int prev, next;
44    };
45 
46    struct EdgeT {
47      int target, source;
48      int prev_in, prev_out;
49      int next_in, next_out;
50    };
51
52    std::vector<NodeT> nodes;
53
54    int first_node;
55
56    int first_free_node;
57
58    std::vector<EdgeT> edges;
59
60    int first_free_edge;
61   
62  public:
63   
64    typedef ListGraphBase Graph;
65   
66    class Node {
67      friend class ListGraphBase;
68    protected:
69
70      int id;
71      Node(int pid) { id = pid;}
72
73    public:
74      Node() {}
75      Node (Invalid) { id = -1; }
76      bool operator==(const Node& node) const {return id == node.id;}
77      bool operator!=(const Node& node) const {return id != node.id;}
78      bool operator<(const Node& node) const {return id < node.id;}
79    };
80
81    class Edge {
82      friend class ListGraphBase;
83    protected:
84
85      int id;
86      Edge(int pid) { id = pid;}
87
88    public:
89      Edge() {}
90      Edge (Invalid) { id = -1; }
91      bool operator==(const Edge& edge) const {return id == edge.id;}
92      bool operator!=(const Edge& edge) const {return id != edge.id;}
93      bool operator<(const Edge& edge) const {return id < edge.id;}
94    };
95
96
97
98    ListGraphBase()
99      : nodes(), first_node(-1),
100        first_free_node(-1), edges(), first_free_edge(-1) {}
101
102   
103    /// Maximum node ID.
104   
105    /// Maximum node ID.
106    ///\sa id(Node)
107    int maxId(Node = INVALID) const { return nodes.size()-1; }
108
109    /// Maximum edge ID.
110   
111    /// Maximum edge ID.
112    ///\sa id(Edge)
113    int maxId(Edge = INVALID) const { return edges.size()-1; }
114
115    Node source(Edge e) const { return edges[e.id].source; }
116    Node target(Edge e) const { return edges[e.id].target; }
117
118
119    void first(Node& node) const {
120      node.id = first_node;
121    }
122
123    void next(Node& node) const {
124      node.id = nodes[node.id].next;
125    }
126
127
128    void first(Edge& e) const {
129      int n;
130      for(n = first_node;
131          n!=-1 && nodes[n].first_in == -1;
132          n = nodes[n].next);
133      e.id = (n == -1) ? -1 : nodes[n].first_in;
134    }
135
136    void next(Edge& edge) const {
137      if (edges[edge.id].next_in != -1) {
138        edge.id = edges[edge.id].next_in;
139      } else {
140        int n;
141        for(n = nodes[edges[edge.id].target].next;
142          n!=-1 && nodes[n].first_in == -1;
143          n = nodes[n].next);
144        edge.id = (n == -1) ? -1 : nodes[n].first_in;
145      }     
146    }
147
148    void firstOut(Edge &e, const Node& v) const {
149      e.id = nodes[v.id].first_out;
150    }
151    void nextOut(Edge &e) const {
152      e.id=edges[e.id].next_out;
153    }
154
155    void firstIn(Edge &e, const Node& v) const {
156      e.id = nodes[v.id].first_in;
157    }
158    void nextIn(Edge &e) const {
159      e.id=edges[e.id].next_in;
160    }
161
162   
163    static int id(Node v) { return v.id; }
164    static int id(Edge e) { return e.id; }
165
166    /// Adds a new node to the graph.
167
168    /// \warning It adds the new node to the front of the list.
169    /// (i.e. the lastly added node becomes the first.)
170    Node addNode() {     
171      int n;
172     
173      if(first_free_node==-1) {
174        n = nodes.size();
175        nodes.push_back(NodeT());
176      } else {
177        n = first_free_node;
178        first_free_node = nodes[n].next;
179      }
180     
181      nodes[n].next = first_node;
182      if(first_node != -1) nodes[first_node].prev = n;
183      first_node = n;
184      nodes[n].prev = -1;
185     
186      nodes[n].first_in = nodes[n].first_out = -1;
187     
188      return Node(n);
189    }
190   
191    Edge addEdge(Node u, Node v) {
192      int n;     
193
194      if (first_free_edge == -1) {
195        n = edges.size();
196        edges.push_back(EdgeT());
197      } else {
198        n = first_free_edge;
199        first_free_edge = edges[n].next_in;
200      }
201     
202      edges[n].source = u.id;
203      edges[n].target = v.id;
204
205      edges[n].next_out = nodes[u.id].first_out;
206      if(nodes[u.id].first_out != -1) {
207        edges[nodes[u.id].first_out].prev_out = n;
208      }
209     
210      edges[n].next_in = nodes[v.id].first_in;
211      if(nodes[v.id].first_in != -1) {
212        edges[nodes[v.id].first_in].prev_in = n;
213      }
214     
215      edges[n].prev_in = edges[n].prev_out = -1;
216       
217      nodes[u.id].first_out = nodes[v.id].first_in = n;
218
219      return Edge(n);
220    }
221   
222    void erase(const Node& node) {
223      int n = node.id;
224     
225      if(nodes[n].next != -1) {
226        nodes[nodes[n].next].prev = nodes[n].prev;
227      }
228     
229      if(nodes[n].prev != -1) {
230        nodes[nodes[n].prev].next = nodes[n].next;
231      } else {
232        first_node = nodes[n].next;
233      }
234     
235      nodes[n].next = first_free_node;
236      first_free_node = n;
237
238    }
239   
240    void erase(const Edge& edge) {
241      int n = edge.id;
242     
243      if(edges[n].next_in!=-1) {
244        edges[edges[n].next_in].prev_in = edges[n].prev_in;
245      }
246
247      if(edges[n].prev_in!=-1) {
248        edges[edges[n].prev_in].next_in = edges[n].next_in;
249      } else {
250        nodes[edges[n].target].first_in = edges[n].next_in;
251      }
252
253     
254      if(edges[n].next_out!=-1) {
255        edges[edges[n].next_out].prev_out = edges[n].prev_out;
256      }
257
258      if(edges[n].prev_out!=-1) {
259        edges[edges[n].prev_out].next_out = edges[n].next_out;
260      } else {
261        nodes[edges[n].source].first_out = edges[n].next_out;
262      }
263     
264      edges[n].next_in = first_free_edge;
265      first_free_edge = n;     
266
267    }
268
269    void clear() {
270      edges.clear();
271      nodes.clear();
272      first_node = first_free_node = first_free_edge = -1;
273    }
274
275  protected:
276    void _moveTarget(Edge e, Node n)
277    {
278      if(edges[e.id].next_in != -1)
279        edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
280      if(edges[e.id].prev_in != -1)
281        edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
282      else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
283      edges[e.id].target = n.id;
284      edges[e.id].prev_in = -1;
285      edges[e.id].next_in = nodes[n.id].first_in;
286      nodes[n.id].first_in = e.id;
287    }
288    void _moveSource(Edge e, Node n)
289    {
290      if(edges[e.id].next_out != -1)
291        edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
292      if(edges[e.id].prev_out != -1)
293        edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
294      else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
295      edges[e.id].source = n.id;
296      edges[e.id].prev_out = -1;
297      edges[e.id].next_out = nodes[n.id].first_out;
298      nodes[n.id].first_out = e.id;
299    }
300
301  };
302
303  typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
304  typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
305  typedef DefaultMappableGraphExtender<IterableListGraphBase> MappableListGraphBase;
306  typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
307  typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
308  typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
309
310/// \addtogroup graphs
311/// @{
312
313  ///A list graph class.
314
315  ///This is a simple and fast erasable graph implementation.
316  ///
317  ///It addition that it conforms to the
318  ///\ref concept::ErasableGraph "ErasableGraph" concept,
319  ///it also provides several additional useful extra functionalities.
320  ///\sa concept::ErasableGraph.
321
322  class ListGraph : public ErasableListGraphBase
323  {
324  public:
325    /// Moves the target of \c e to \c n
326
327    /// Moves the target of \c e to \c n
328    ///
329    ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
330    ///referencing the moved edge remain
331    ///valid. However <tt>InEdge</tt>'s are invalidated.
332    void moveTarget(Edge e, Node n) { _moveTarget(e,n); }
333    /// Moves the source of \c e to \c n
334
335    /// Moves the source of \c e to \c n
336    ///
337    ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
338    ///referencing the moved edge remain
339    ///valid. However <tt>OutEdge</tt>'s are invalidated.
340    void moveSource(Edge e, Node n) { _moveSource(e,n); }
341
342    /// Invert the direction of an edge.
343
344    ///\note The <tt>Edge</tt>'s
345    ///referencing the moved edge remain
346    ///valid. However <tt>OutEdge</tt>'s  and <tt>InEdge</tt>'s are invalidated.
347    void reverseEdge(Edge e) {
348      Node t=target(e);
349      _moveTarget(e,source(e));
350      _moveSource(e,t);
351    }
352
353    ///Using this it possible to avoid the superfluous memory allocation.
354
355    ///Using this it possible to avoid the superfluous memory allocation.
356    ///\todo more docs...
357    void reserveEdge(int n) { edges.reserve(n); };
358
359    ///Contract two nodes.
360
361    ///This function contracts two nodes.
362    ///
363    ///Node \p b will be removed but instead of deleting
364    ///its neighboring edges, they will be joined to \p a.
365    ///The last parameter \p r controls whether to remove loops. \c true
366    ///means that loops will be removed.
367    ///
368    ///\note The <tt>Edge</tt>s
369    ///referencing the moved edge remain
370    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
371    ///may be invalidated.
372    void contract(Node a,Node b,bool r=true)
373    {
374      for(OutEdgeIt e(*this,b);e!=INVALID;) {
375        OutEdgeIt f=e;
376        ++f;
377        if(r && target(e)==a) erase(e);
378        else moveSource(e,b);
379        e=f;
380      }
381      for(InEdgeIt e(*this,b);e!=INVALID;) {
382        InEdgeIt f=e;
383        ++f;
384        if(r && source(e)==a) erase(e);
385        else moveTarget(e,b);
386        e=f;
387      }
388      erase(b);
389    }
390
391
392    ///Class to make a snapshot of the graph and to restrore to it later.
393
394    ///Class to make a snapshot of the graph and to restrore to it later.
395    ///
396    ///The newly added nodes and edges can be removed using the
397    ///restore() function.
398    ///
399    ///\warning Edge and node deletions cannot be restored.
400    ///\warning SnapShots cannot be nested.
401    ///\ingroup graphs
402    class SnapShot : protected AlterationObserverRegistry<Node>::ObserverBase,
403                     protected AlterationObserverRegistry<Edge>::ObserverBase
404    {
405      protected:
406     
407      ListGraph *g;
408      std::list<Node> added_nodes;
409      std::list<Edge> added_edges;
410     
411      bool active;
412      virtual void add(const Node& n) {
413        added_nodes.push_back(n);
414      };
415      ///\bug Exception...
416      ///
417      virtual void erase(const Node&)
418      {
419        exit(1);
420      }
421      virtual void add(const Edge& n) {
422        added_edges.push_back(n);
423      };
424      ///\bug Exception...
425      ///
426      virtual void erase(const Edge&)
427      {
428        exit(1);
429      }
430
431      void regist(ListGraph &_g) {
432        g=&_g;
433        AlterationObserverRegistry<Node>::ObserverBase::
434          attach(g->node_observers);
435        AlterationObserverRegistry<Edge>::ObserverBase::
436          attach(g->edge_observers);
437      }
438           
439      void deregist() {
440        AlterationObserverRegistry<Node>::ObserverBase::
441          detach();
442        AlterationObserverRegistry<Edge>::ObserverBase::
443          detach();
444        g=0;
445      }
446           
447    public:
448      ///Default constructur.
449     
450      ///Default constructur.
451      ///To actually make a snapshot you must call save().
452      ///
453      SnapShot() : g(0) {}
454      ///Constructor that immediately makes a snapshot.
455     
456      ///This constructor immediately makes a snapshot of the graph.
457      ///\param _g The graph we make a snapshot of.
458      SnapShot(ListGraph &_g) {
459        regist(_g);
460      }
461      ///\bug Is it necessary?
462      ///
463      ~SnapShot()
464      {
465        if(g) deregist();
466      }
467     
468      ///Make a snapshot.
469
470      ///Make a snapshot of the graph.
471      ///
472      ///This function can be called more than once. In case of a repeated
473      ///call, the previous snapshot gets lost.
474      ///\param _g The graph we make the snapshot of.
475      void save(ListGraph &_g)
476      {
477        if(g!=&_g) {
478          if(g) deregist();
479          regist(_g);
480        }
481        added_nodes.clear();
482        added_edges.clear();
483      }
484     
485    ///Undo the changes until the last snapshot.
486
487    ///Undo the changes until last snapshot created by save().
488    ///
489    ///\todo This function might be called undo().
490      void restore() {
491        deregist();
492        while(!added_edges.empty()) {
493          g->erase(added_edges.front());
494          added_edges.pop_front();
495        }
496        while(!added_nodes.empty()) {
497          g->erase(added_nodes.front());
498          added_nodes.pop_front();
499        }
500      }
501    };
502   
503  };
504 
505  /// @} 
506} //namespace lemon
507 
508
509#endif
Note: See TracBrowser for help on using the repository browser.