COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/smart_graph.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: 9.2 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_SMART_GRAPH_H
20#define LEMON_SMART_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief SmartGraph class.
25
26#include <vector>
27
28#include <lemon/bits/invalid.h>
29
30#include <lemon/bits/graph_extender.h>
31
32#include <lemon/bits/utility.h>
33
34#include <lemon/bits/graph_extender.h>
35
36namespace lemon {
37
38  class SmartGraph;
39  ///Base of SmartGraph
40
41  ///Base of SmartGraph
42  ///
43  class SmartGraphBase {
44
45    friend class SmatGraph;
46
47  protected:
48    struct NodeT
49    {
50      int first_in,first_out;     
51      NodeT() : first_in(-1), first_out(-1) {}
52    };
53    struct EdgeT
54    {
55      int target, source, next_in, next_out;     
56      //FIXME: is this necessary?
57      EdgeT() : next_in(-1), next_out(-1) {} 
58    };
59
60    std::vector<NodeT> nodes;
61
62    std::vector<EdgeT> edges;
63   
64   
65  public:
66
67    typedef SmartGraphBase Graph;
68
69    class Node;
70    class Edge;
71
72   
73  public:
74
75    SmartGraphBase() : nodes(), edges() { }
76    SmartGraphBase(const SmartGraphBase &_g)
77      : nodes(_g.nodes), edges(_g.edges) { }
78   
79    typedef True NodeNumTag;
80    typedef True EdgeNumTag;
81
82    ///Number of nodes.
83    int nodeNum() const { return nodes.size(); }
84    ///Number of edges.
85    int edgeNum() const { return edges.size(); }
86
87    /// Maximum node ID.
88   
89    /// Maximum node ID.
90    ///\sa id(Node)
91    int maxNodeId() const { return nodes.size()-1; }
92    /// Maximum edge ID.
93   
94    /// Maximum edge ID.
95    ///\sa id(Edge)
96    int maxEdgeId() const { return edges.size()-1; }
97
98    Node source(Edge e) const { return edges[e.n].source; }
99    Node target(Edge e) const { return edges[e.n].target; }
100
101    /// Node ID.
102   
103    /// The ID of a valid Node is a nonnegative integer not greater than
104    /// \ref maxNodeId(). The range of the ID's is not surely continuous
105    /// and the greatest node ID can be actually less then \ref maxNodeId().
106    ///
107    /// The ID of the \ref INVALID node is -1.
108    ///\return The ID of the node \c v.
109    static int id(Node v) { return v.n; }
110    /// Edge ID.
111   
112    /// The ID of a valid Edge is a nonnegative integer not greater than
113    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
114    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
115    ///
116    /// The ID of the \ref INVALID edge is -1.
117    ///\return The ID of the edge \c e.
118    static int id(Edge e) { return e.n; }
119
120    /// \brief Returns the node from its \c id.
121    ///
122    /// Returns the node from its \c id. If there is not node
123    /// with the given id the effect of the function is undefinied.
124    static Node nodeFromId(int id) { return Node(id);}
125
126    /// \brief Returns the edge from its \c id.
127    ///
128    /// Returns the edge from its \c id. If there is not edge
129    /// with the given id the effect of the function is undefinied.
130    static Edge edgeFromId(int id) { return Edge(id);}
131
132    Node addNode() {
133      Node n; n.n=nodes.size();
134      nodes.push_back(NodeT()); //FIXME: Hmmm...
135      return n;
136    }
137   
138    Edge addEdge(Node u, Node v) {
139      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
140      edges[e.n].source=u.n; edges[e.n].target=v.n;
141      edges[e.n].next_out=nodes[u.n].first_out;
142      edges[e.n].next_in=nodes[v.n].first_in;
143      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
144
145      return e;
146    }
147
148    void clear() {
149      edges.clear();
150      nodes.clear();
151    }
152
153
154    class Node {
155      friend class SmartGraphBase;
156      friend class SmartGraph;
157
158    protected:
159      int n;
160      Node(int nn) {n=nn;}
161    public:
162      Node() {}
163      Node (Invalid) { n=-1; }
164      bool operator==(const Node i) const {return n==i.n;}
165      bool operator!=(const Node i) const {return n!=i.n;}
166      bool operator<(const Node i) const {return n<i.n;}
167    };
168   
169
170    class Edge {
171      friend class SmartGraphBase;
172      friend class SmartGraph;
173
174    protected:
175      int n;
176      Edge(int nn) {n=nn;}
177    public:
178      Edge() { }
179      Edge (Invalid) { n=-1; }
180      bool operator==(const Edge i) const {return n==i.n;}
181      bool operator!=(const Edge i) const {return n!=i.n;}
182      bool operator<(const Edge i) const {return n<i.n;}
183    };
184
185    void first(Node& node) const {
186      node.n = nodes.size() - 1;
187    }
188
189    static void next(Node& node) {
190      --node.n;
191    }
192
193    void first(Edge& edge) const {
194      edge.n = edges.size() - 1;
195    }
196
197    static void next(Edge& edge) {
198      --edge.n;
199    }
200
201    void firstOut(Edge& edge, const Node& node) const {
202      edge.n = nodes[node.n].first_out;
203    }
204
205    void nextOut(Edge& edge) const {
206      edge.n = edges[edge.n].next_out;
207    }
208
209    void firstIn(Edge& edge, const Node& node) const {
210      edge.n = nodes[node.n].first_in;
211    }
212   
213    void nextIn(Edge& edge) const {
214      edge.n = edges[edge.n].next_in;
215    }
216
217    Node _split(Node n, bool connect = true)
218    {
219      Node b = addNode();
220      nodes[b.n].first_out=nodes[n.n].first_out;
221      nodes[n.n].first_out=-1;
222      for(int i=nodes[b.n].first_out;i!=-1;i++) edges[i].source=b.n;
223      if(connect) addEdge(n,b);
224      return b;
225    }
226
227  };
228
229  typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
230
231  /// \ingroup graphs
232
233  ///A smart graph class.
234
235  ///This is a simple and fast graph implementation.
236  ///It is also quite memory efficient, but at the price
237  ///that <b> it does support only limited (only stack-like)
238  ///node and edge deletions</b>.
239  ///It conforms to
240  ///the \ref concept::Graph "Graph" concept.
241  ///\sa concept::Graph.
242  ///
243  ///\author Alpar Juttner
244  class SmartGraph : public ExtendedSmartGraphBase {
245  public:
246
247    typedef ExtendedSmartGraphBase Parent;
248
249    class Snapshot;
250    friend class Snapshot;
251
252  protected:
253    void restoreSnapshot(const Snapshot &s)
254    {
255      while(s.edge_num<edges.size()) {
256        Parent::getNotifier(Edge()).erase(Edge(edges.size()-1));
257        nodes[edges.back().target].first_in=edges.back().next_in;
258        nodes[edges.back().source].first_out=edges.back().next_out;
259        edges.pop_back();
260      }
261      //nodes.resize(s.nodes_num);
262      while(s.node_num<nodes.size()) {
263        Parent::getNotifier(Node()).erase(Node(nodes.size()-1));
264        nodes.pop_back();
265      }
266    }   
267
268  public:
269
270    ///Split a node.
271   
272    ///This function splits a node. First a new node is added to the graph,
273    ///then the source of each outgoing edge of \c n is moved to this new node.
274    ///If \c connect is \c true (this is the default value), then a new edge
275    ///from \c n to the newly created node is also added.
276    ///\return The newly created node.
277    ///
278    ///\note The <tt>Edge</tt>s
279    ///referencing a moved edge remain
280    ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
281    ///may be invalidated.
282    ///\warning This functionality cannot be used together with the Snapshot
283    ///feature.
284    ///\todo It could be implemented in a bit faster way.
285    Node split(Node n, bool connect = true)
286    {
287      Node b = _split(n,connect);
288      return b;
289    }
290 
291
292    ///Class to make a snapshot of the graph and to restrore to it later.
293
294    ///Class to make a snapshot of the graph and to restrore to it later.
295    ///
296    ///The newly added nodes and edges can be removed using the
297    ///restore() function.
298    ///\note After you restore a state, you cannot restore
299    ///a later state, in other word you cannot add again the edges deleted
300    ///by restore() using another Snapshot instance.
301    ///
302    class Snapshot
303    {
304      SmartGraph *g;
305    protected:
306      friend class SmartGraph;
307      unsigned int node_num;
308      unsigned int edge_num;
309    public:
310      ///Default constructor.
311     
312      ///Default constructor.
313      ///To actually make a snapshot you must call save().
314      ///
315      Snapshot() : g(0) {}
316      ///Constructor that immediately makes a snapshot
317     
318      ///This constructor immediately makes a snapshot of the graph.
319      ///\param _g The graph we make a snapshot of.
320      Snapshot(SmartGraph &_g) :g(&_g) {
321        node_num=g->nodes.size();
322        edge_num=g->edges.size();
323      }
324
325      ///Make a snapshot.
326
327      ///Make a snapshot of the graph.
328      ///
329      ///This function can be called more than once. In case of a repeated
330      ///call, the previous snapshot gets lost.
331      ///\param _g The graph we make the snapshot of.
332      void save(SmartGraph &_g)
333      {
334        g=&_g;
335        node_num=g->nodes.size();
336        edge_num=g->edges.size();
337      }
338
339      ///Undo the changes until a snapshot.
340     
341      ///Undo the changes until a snapshot created by save().
342      ///
343      ///\note After you restored a state, you cannot restore
344      ///a later state, in other word you cannot add again the edges deleted
345      ///by restore().
346      ///
347      ///\todo This function might be called undo().
348     
349      void restore()
350      {
351        g->restoreSnapshot(*this);
352      }
353    };
354  };
355
356
357} //namespace lemon
358
359
360#endif //LEMON_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.