COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 905:5be029d19c98

Last change on this file since 905:5be029d19c98 was 905:5be029d19c98, checked in by Alpar Juttner, 16 years ago

Some code cleaning in id related stuffs

File size: 9.5 KB
Line 
1// -*- mode:C++ -*-
2
3#ifndef HUGO_SMART_GRAPH_H
4#define HUGO_SMART_GRAPH_H
5
6///\ingroup graphs
7///\file
8///\brief SmartGraph and SymSmartGraph classes.
9
10#include <vector>
11#include <climits>
12
13#include <hugo/invalid.h>
14
15#include <hugo/array_map.h>
16#include <hugo/sym_map.h>
17
18#include <hugo/map_registry.h>
19
20#include <hugo/map_defines.h>
21
22namespace hugo {
23
24/// \addtogroup graphs
25/// @{
26//  class SymSmartGraph;
27
28  ///A smart graph class.
29
30  ///This is a simple and fast graph implementation.
31  ///It is also quite memory efficient, but at the price
32  ///that <b> it does not support node and edge deletion</b>.
33  ///It conforms to
34  ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept.
35  ///\sa skeleton::ExtendableGraph.
36  ///
37  ///\todo Some member functions could be \c static.
38  ///
39  ///\todo A possibly useful functionality: a function saveState() would
40  ///give back a data sturcture X and then the function restoreState(X)
41  ///would remove the nodes and edges added after the call of saveState().
42  ///Of course it should be used as a stack. (Maybe X is not necessary.)
43  ///
44  ///\author Alpar Juttner
45  class SmartGraph {
46
47    struct NodeT
48    {
49      int first_in,first_out;     
50      NodeT() : first_in(-1), first_out(-1) {}
51    };
52    struct EdgeT
53    {
54      int head, tail, next_in, next_out;     
55      //FIXME: is this necessary?
56      EdgeT() : next_in(-1), next_out(-1) {} 
57    };
58
59    std::vector<NodeT> nodes;
60
61    std::vector<EdgeT> edges;
62   
63   
64  public:
65
66    typedef SmartGraph Graph;
67
68    class Node;
69    class Edge;
70
71    class NodeIt;
72    class EdgeIt;
73    class OutEdgeIt;
74    class InEdgeIt;
75   
76    // Create map registries.
77    CREATE_MAP_REGISTRIES;
78    // Create node and edge maps.
79    CREATE_MAPS(ArrayMap);
80   
81  public:
82
83    SmartGraph() : nodes(), edges() { }
84    SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
85   
86    ///Number of nodes.
87    int nodeNum() const { return nodes.size(); }
88    ///Number of edges.
89    int edgeNum() const { return edges.size(); }
90
91    /// Maximum node ID.
92   
93    /// Maximum node ID.
94    ///\sa id(Node)
95    int maxNodeId() const { return nodes.size()-1; }
96    /// Maximum edge ID.
97   
98    /// Maximum edge ID.
99    ///\sa id(Edge)
100    int maxEdgeId() const { return edges.size()-1; }
101
102    Node tail(Edge e) const { return edges[e.n].tail; }
103    Node head(Edge e) const { return edges[e.n].head; }
104
105    NodeIt& first(NodeIt& v) const {
106      v=NodeIt(*this); return v; }
107    EdgeIt& first(EdgeIt& e) const {
108      e=EdgeIt(*this); return e; }
109    OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
110      e=OutEdgeIt(*this,v); return e; }
111    InEdgeIt& first(InEdgeIt& e, const Node v) const {
112      e=InEdgeIt(*this,v); return e; }
113
114    /// Node ID.
115   
116    /// The ID of a valid Node is a nonnegative integer not greater than
117    /// \ref maxNodeId(). The range of the ID's is not surely continuous
118    /// and the greatest node ID can be actually less then \ref maxNodeId().
119    ///
120    /// The ID of the \ref INVALID node is -1.
121    ///\return The ID of the node \c v.
122    static int id(Node v) { return v.n; }
123    /// Edge ID.
124   
125    /// The ID of a valid Edge is a nonnegative integer not greater than
126    /// \ref maxEdgeId(). The range of the ID's is not surely continuous
127    /// and the greatest edge ID can be actually less then \ref maxEdgeId().
128    ///
129    /// The ID of the \ref INVALID edge is -1.
130    ///\return The ID of the edge \c e.
131    static int id(Edge e) { return e.n; }
132
133    Node addNode() {
134      Node n; n.n=nodes.size();
135      nodes.push_back(NodeT()); //FIXME: Hmmm...
136
137     
138      node_maps.add(n);
139      return n;
140    }
141   
142    Edge addEdge(Node u, Node v) {
143      Edge e; e.n=edges.size(); edges.push_back(EdgeT()); //FIXME: Hmmm...
144      edges[e.n].tail=u.n; edges[e.n].head=v.n;
145      edges[e.n].next_out=nodes[u.n].first_out;
146      edges[e.n].next_in=nodes[v.n].first_in;
147      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
148
149      edge_maps.add(e);
150
151      return e;
152    }
153
154    /// Finds an edge between two nodes.
155
156    /// Finds an edge from node \c u to node \c v.
157    ///
158    /// If \c prev is \ref INVALID (this is the default value), then
159    /// It finds the first edge from \c u to \c v. Otherwise it looks for
160    /// the next edge from \c u to \c v after \c prev.
161    /// \return The found edge or INVALID if there is no such an edge.
162    Edge findEdge(Node u,Node v, Edge prev = INVALID)
163    {
164      int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
165      while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
166      prev.n=e;
167      return prev;
168    }
169   
170    void clear() {
171      edge_maps.clear();
172      edges.clear();
173      node_maps.clear();
174      nodes.clear();
175    }
176
177    class Node {
178      friend class SmartGraph;
179      template <typename T> friend class NodeMap;
180     
181      friend class Edge;
182      friend class OutEdgeIt;
183      friend class InEdgeIt;
184      friend class SymEdge;
185
186    protected:
187      int n;
188      friend int SmartGraph::id(Node v);
189      Node(int nn) {n=nn;}
190    public:
191      Node() {}
192      Node (Invalid) { n=-1; }
193      bool operator==(const Node i) const {return n==i.n;}
194      bool operator!=(const Node i) const {return n!=i.n;}
195      bool operator<(const Node i) const {return n<i.n;}
196      //      ///Validity check
197      //      operator bool() { return n!=-1; }
198    };
199   
200    class NodeIt : public Node {
201      const SmartGraph *G;
202      friend class SmartGraph;
203    public:
204      NodeIt() : Node() { }
205      NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
206      NodeIt(Invalid i) : Node(i) { }
207      NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
208      NodeIt &operator++() {
209        n=(n+2)%(G->nodes.size()+1)-1;
210        return *this;
211      }
212//       ///Validity check
213//       operator bool() { return Node::operator bool(); }     
214    };
215
216    class Edge {
217      friend class SmartGraph;
218      template <typename T> friend class EdgeMap;
219
220      friend class SymSmartGraph;
221     
222      friend class Node;
223      friend class NodeIt;
224    protected:
225      int n;
226      friend int SmartGraph::id(Edge e);
227      Edge(int nn) {n=nn;}
228    public:
229      /// An Edge with id \c n.
230
231      Edge() { }
232      Edge (Invalid) { n=-1; }
233      bool operator==(const Edge i) const {return n==i.n;}
234      bool operator!=(const Edge i) const {return n!=i.n;}
235      bool operator<(const Edge i) const {return n<i.n;}
236//       ///Validity check
237//       operator bool() { return n!=-1; }
238
239      ///Set the edge to that have ID \c ID.
240      void setToId(int id) { n=id; }
241   };
242   
243    class EdgeIt : public Edge {
244      const SmartGraph *G;
245      friend class SmartGraph;
246    public:
247      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
248      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
249      EdgeIt (Invalid i) : Edge(i) { }
250      EdgeIt() : Edge() { }
251      EdgeIt &operator++() { --n; return *this; }
252//       ///Validity check
253//       operator bool() { return Edge::operator bool(); }     
254    };
255   
256    class OutEdgeIt : public Edge {
257      const SmartGraph *G;
258      friend class SmartGraph;
259    public:
260      OutEdgeIt() : Edge() { }
261      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
262      OutEdgeIt (Invalid i) : Edge(i) { }
263
264      OutEdgeIt(const SmartGraph& _G,const Node v)
265        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
266      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
267//       ///Validity check
268//       operator bool() { return Edge::operator bool(); }     
269    };
270   
271    class InEdgeIt : public Edge {
272      const SmartGraph *G;
273      friend class SmartGraph;
274    public:
275      InEdgeIt() : Edge() { }
276      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
277      InEdgeIt (Invalid i) : Edge(i) { }
278      InEdgeIt(const SmartGraph& _G,Node v)
279        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
280      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
281//       ///Validity check
282//       operator bool() { return Edge::operator bool(); }     
283    };
284
285  };
286
287  ///Graph for bidirectional edges.
288
289  ///The purpose of this graph structure is to handle graphs
290  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
291  ///of oppositely directed edges.
292  ///There is a new edge map type called
293  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
294  ///that complements this
295  ///feature by
296  ///storing shared values for the edge pairs. The usual
297  ///\ref Graph::EdgeMap "EdgeMap"
298  ///can be used
299  ///as well.
300  ///
301  ///The oppositely directed edge can also be obtained easily
302  ///using \ref opposite.
303  ///\warning It shares the similarity with \ref SmartGraph that
304  ///it is not possible to delete edges or nodes from the graph.
305  //\sa SmartGraph.
306
307  class SymSmartGraph : public SmartGraph
308  {
309  public:
310    typedef SymSmartGraph Graph;
311
312    // Create symmetric map registry.
313    CREATE_SYM_EDGE_MAP_REGISTRY;
314    // Create symmetric edge map.
315    CREATE_SYM_EDGE_MAP(ArrayMap);
316
317
318    SymSmartGraph() : SmartGraph() { }
319    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
320    ///Adds a pair of oppositely directed edges to the graph.
321    Edge addEdge(Node u, Node v)
322    {
323      Edge e = SmartGraph::addEdge(u,v);
324      Edge f = SmartGraph::addEdge(v,u);
325      sym_edge_maps.add(e);
326      sym_edge_maps.add(f);
327      return e;
328    }
329
330    ///The oppositely directed edge.
331
332    ///Returns the oppositely directed
333    ///pair of the edge \c e.
334    static Edge opposite(Edge e)
335    {
336      Edge f;
337      f.n = e.n - 2*(e.n%2) + 1;
338      return f;
339    }
340   
341
342  };
343 
344  /// @} 
345} //namespace hugo
346
347
348
349
350#endif //HUGO_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.