COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 880:9d0bfd35b97c

Last change on this file since 880:9d0bfd35b97c was 880:9d0bfd35b97c, checked in by Alpar Juttner, 20 years ago
  • Name changing: XYZGraphSkeleton -> XYZGraph
  • Fix some bad \ref's in the doc.
File size: 10.1 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/default_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    /// Creating map registries.
77    CREATE_MAP_REGISTRIES;
78    /// Creating node and edge maps.
79    CREATE_MAPS(DefaultMap);
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      //template <typename T> friend class SymSmartGraph::SymEdgeMap;     
221      //friend Edge SymSmartGraph::opposite(Edge) const;
222     
223      friend class Node;
224      friend class NodeIt;
225    protected:
226      int n;
227      friend int SmartGraph::id(Edge e);
228
229    public:
230      /// An Edge with id \c n.
231
232      /// \bug It should be
233      /// obtained by a member function of the Graph.
234      Edge(int nn) {n=nn;}
235      Edge() { }
236      Edge (Invalid) { n=-1; }
237      bool operator==(const Edge i) const {return n==i.n;}
238      bool operator!=(const Edge i) const {return n!=i.n;}
239      bool operator<(const Edge i) const {return n<i.n;}
240      ///\bug This is a workaround until somebody tells me how to
241      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
242      int &idref() {return n;}
243      const int &idref() const {return n;}
244//       ///Validity check
245//       operator bool() { return n!=-1; }
246   };
247   
248    class EdgeIt : public Edge {
249      const SmartGraph *G;
250      friend class SmartGraph;
251    public:
252      EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
253      EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
254      EdgeIt (Invalid i) : Edge(i) { }
255      EdgeIt() : Edge() { }
256      ///\bug This is a workaround until somebody tells me how to
257      ///make class \c SymSmartGraph::SymEdgeMap friend of Edge
258      int &idref() {return n;}
259      EdgeIt &operator++() { --n; return *this; }
260//       ///Validity check
261//       operator bool() { return Edge::operator bool(); }     
262    };
263   
264    class OutEdgeIt : public Edge {
265      const SmartGraph *G;
266      friend class SmartGraph;
267    public:
268      OutEdgeIt() : Edge() { }
269      OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
270      OutEdgeIt (Invalid i) : Edge(i) { }
271
272      OutEdgeIt(const SmartGraph& _G,const Node v)
273        : Edge(_G.nodes[v.n].first_out), G(&_G) {}
274      OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
275//       ///Validity check
276//       operator bool() { return Edge::operator bool(); }     
277    };
278   
279    class InEdgeIt : public Edge {
280      const SmartGraph *G;
281      friend class SmartGraph;
282    public:
283      InEdgeIt() : Edge() { }
284      InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
285      InEdgeIt (Invalid i) : Edge(i) { }
286      InEdgeIt(const SmartGraph& _G,Node v)
287        : Edge(_G.nodes[v.n].first_in), G(&_G) { }
288      InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
289//       ///Validity check
290//       operator bool() { return Edge::operator bool(); }     
291    };
292
293  };
294
295  ///Graph for bidirectional edges.
296
297  ///The purpose of this graph structure is to handle graphs
298  ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
299  ///of oppositely directed edges.
300  ///There is a new edge map type called
301  ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
302  ///that complements this
303  ///feature by
304  ///storing shared values for the edge pairs. The usual
305  ///\ref Graph::EdgeMap "EdgeMap"
306  ///can be used
307  ///as well.
308  ///
309  ///The oppositely directed edge can also be obtained easily
310  ///using \ref opposite.
311  ///\warning It shares the similarity with \ref SmartGraph that
312  ///it is not possible to delete edges or nodes from the graph.
313  //\sa SmartGraph.
314
315  class SymSmartGraph : public SmartGraph
316  {
317  public:
318    typedef SymSmartGraph Graph;
319
320    /// Importing maps from the base class ListGraph.
321    KEEP_MAPS(SmartGraph, SymSmartGraph);
322
323    /// Creating symmetric map registry.
324    CREATE_SYM_EDGE_MAP_REGISTRY;
325    /// Creating symmetric edge map.
326    CREATE_SYM_EDGE_MAP(DefaultMap);
327
328
329    SymSmartGraph() : SmartGraph() { }
330    SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
331    ///Adds a pair of oppositely directed edges to the graph.
332    Edge addEdge(Node u, Node v)
333    {
334      Edge e = SmartGraph::addEdge(u,v);
335      Edge f = SmartGraph::addEdge(v,u);
336      sym_edge_maps.add(e);
337      sym_edge_maps.add(f);
338      return e;
339    }
340
341    ///The oppositely directed edge.
342
343    ///Returns the oppositely directed
344    ///pair of the edge \c e.
345    static Edge opposite(Edge e)
346    {
347      Edge f;
348      f.idref() = e.idref() - 2*(e.idref()%2) + 1;
349      return f;
350    }
351   
352
353  };
354 
355  /// @} 
356} //namespace hugo
357
358
359
360
361#endif //HUGO_SMART_GRAPH_H
Note: See TracBrowser for help on using the repository browser.