COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/smart_graph.h @ 822:88226d9fe821

Last change on this file since 822:88226d9fe821 was 822:88226d9fe821, checked in by Balazs Dezso, 16 years ago

The MapFactories? have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.

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 the graph interface documented under
34  ///the description of \ref GraphSkeleton.
35  ///\sa \ref GraphSkeleton.
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 GraphSkeleton::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 \ref 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.