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