1 /* -*- C++ -*- |
|
2 * src/lemon/full_graph.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, 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 LEMON_FULL_GRAPH_H |
|
18 #define LEMON_FULL_GRAPH_H |
|
19 |
|
20 #include <cmath> |
|
21 |
|
22 |
|
23 #include <lemon/bits/iterable_graph_extender.h> |
|
24 #include <lemon/bits/alteration_notifier.h> |
|
25 #include <lemon/bits/default_map.h> |
|
26 |
|
27 #include <lemon/invalid.h> |
|
28 #include <lemon/utility.h> |
|
29 |
|
30 |
|
31 ///\ingroup graphs |
|
32 ///\file |
|
33 ///\brief FullGraph and SymFullGraph classes. |
|
34 |
|
35 |
|
36 namespace lemon { |
|
37 |
|
38 /// \addtogroup graphs |
|
39 /// @{ |
|
40 |
|
41 class FullGraphBase { |
|
42 int NodeNum; |
|
43 int EdgeNum; |
|
44 public: |
|
45 |
|
46 typedef FullGraphBase Graph; |
|
47 |
|
48 class Node; |
|
49 class Edge; |
|
50 |
|
51 public: |
|
52 |
|
53 FullGraphBase() {} |
|
54 |
|
55 |
|
56 ///Creates a full graph with \c n nodes. |
|
57 void construct(int n) { NodeNum = n; EdgeNum = n * n; } |
|
58 /// |
|
59 // FullGraphBase(const FullGraphBase &_g) |
|
60 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } |
|
61 |
|
62 typedef True NodeNumTag; |
|
63 typedef True EdgeNumTag; |
|
64 |
|
65 ///Number of nodes. |
|
66 int nodeNum() const { return NodeNum; } |
|
67 ///Number of edges. |
|
68 int edgeNum() const { return EdgeNum; } |
|
69 |
|
70 /// Maximum node ID. |
|
71 |
|
72 /// Maximum node ID. |
|
73 ///\sa id(Node) |
|
74 int maxId(Node = INVALID) const { return NodeNum-1; } |
|
75 /// Maximum edge ID. |
|
76 |
|
77 /// Maximum edge ID. |
|
78 ///\sa id(Edge) |
|
79 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
|
80 |
|
81 Node source(Edge e) const { return e.id % NodeNum; } |
|
82 Node target(Edge e) const { return e.id / NodeNum; } |
|
83 |
|
84 |
|
85 /// Node ID. |
|
86 |
|
87 /// The ID of a valid Node is a nonnegative integer not greater than |
|
88 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
89 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
90 /// |
|
91 /// The ID of the \ref INVALID node is -1. |
|
92 ///\return The ID of the node \c v. |
|
93 |
|
94 static int id(Node v) { return v.id; } |
|
95 /// Edge ID. |
|
96 |
|
97 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
98 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
99 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
100 /// |
|
101 /// The ID of the \ref INVALID edge is -1. |
|
102 ///\return The ID of the edge \c e. |
|
103 static int id(Edge e) { return e.id; } |
|
104 |
|
105 static Node fromId(int id, Node) { return Node(id);} |
|
106 |
|
107 static Edge fromId(int id, Edge) { return Edge(id);} |
|
108 |
|
109 /// Finds an edge between two nodes. |
|
110 |
|
111 /// Finds an edge from node \c u to node \c v. |
|
112 /// |
|
113 /// If \c prev is \ref INVALID (this is the default value), then |
|
114 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
115 /// the next edge from \c u to \c v after \c prev. |
|
116 /// \return The found edge or INVALID if there is no such an edge. |
|
117 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
118 { |
|
119 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; |
|
120 } |
|
121 |
|
122 |
|
123 class Node { |
|
124 friend class FullGraphBase; |
|
125 |
|
126 protected: |
|
127 int id; |
|
128 Node(int _id) { id = _id;} |
|
129 public: |
|
130 Node() {} |
|
131 Node (Invalid) { id = -1; } |
|
132 bool operator==(const Node node) const {return id == node.id;} |
|
133 bool operator!=(const Node node) const {return id != node.id;} |
|
134 bool operator<(const Node node) const {return id < node.id;} |
|
135 }; |
|
136 |
|
137 |
|
138 |
|
139 class Edge { |
|
140 friend class FullGraphBase; |
|
141 |
|
142 protected: |
|
143 int id; // NodeNum * target + source; |
|
144 |
|
145 Edge(int _id) : id(_id) {} |
|
146 |
|
147 Edge(const FullGraphBase& _graph, int source, int target) |
|
148 : id(_graph.NodeNum * target+source) {} |
|
149 public: |
|
150 Edge() { } |
|
151 Edge (Invalid) { id = -1; } |
|
152 bool operator==(const Edge edge) const {return id == edge.id;} |
|
153 bool operator!=(const Edge edge) const {return id != edge.id;} |
|
154 bool operator<(const Edge edge) const {return id < edge.id;} |
|
155 }; |
|
156 |
|
157 void first(Node& node) const { |
|
158 node.id = NodeNum-1; |
|
159 } |
|
160 |
|
161 static void next(Node& node) { |
|
162 --node.id; |
|
163 } |
|
164 |
|
165 void first(Edge& edge) const { |
|
166 edge.id = EdgeNum-1; |
|
167 } |
|
168 |
|
169 static void next(Edge& edge) { |
|
170 --edge.id; |
|
171 } |
|
172 |
|
173 void firstOut(Edge& edge, const Node& node) const { |
|
174 edge.id = EdgeNum + node.id - NodeNum; |
|
175 } |
|
176 |
|
177 void nextOut(Edge& edge) const { |
|
178 edge.id -= NodeNum; |
|
179 if (edge.id < 0) edge.id = -1; |
|
180 } |
|
181 |
|
182 void firstIn(Edge& edge, const Node& node) const { |
|
183 edge.id = node.id * NodeNum; |
|
184 } |
|
185 |
|
186 void nextIn(Edge& edge) const { |
|
187 ++edge.id; |
|
188 if (edge.id % NodeNum == 0) edge.id = -1; |
|
189 } |
|
190 |
|
191 }; |
|
192 |
|
193 |
|
194 typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase; |
|
195 typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase; |
|
196 typedef DefaultMappableGraphExtender<IterableFullGraphBase> MappableFullGraphBase; |
|
197 |
|
198 ///A full graph class. |
|
199 |
|
200 ///This is a simple and fast directed full graph implementation. |
|
201 ///It is completely static, so you can neither add nor delete either |
|
202 ///edges or nodes. |
|
203 ///Thus it conforms to |
|
204 ///the \ref concept::StaticGraph "StaticGraph" concept |
|
205 ///\sa concept::StaticGraph. |
|
206 /// |
|
207 ///\author Alpar Juttner |
|
208 class FullGraph : public MappableFullGraphBase { |
|
209 public: |
|
210 |
|
211 FullGraph(int n) { construct(n); } |
|
212 }; |
|
213 |
|
214 |
|
215 // Base graph class for UndirFullGraph. |
|
216 class UndirFullGraphBase { |
|
217 int NodeNum; |
|
218 int EdgeNum; |
|
219 public: |
|
220 |
|
221 typedef UndirFullGraphBase Graph; |
|
222 |
|
223 class Node; |
|
224 class Edge; |
|
225 |
|
226 public: |
|
227 |
|
228 UndirFullGraphBase() {} |
|
229 |
|
230 |
|
231 ///Creates a full graph with \c n nodes. |
|
232 void construct(int n) { NodeNum = n; EdgeNum = n * (n - 1) / 2; } |
|
233 /// |
|
234 // FullGraphBase(const FullGraphBase &_g) |
|
235 // : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { } |
|
236 |
|
237 typedef True NodeNumTag; |
|
238 typedef True EdgeNumTag; |
|
239 |
|
240 ///Number of nodes. |
|
241 int nodeNum() const { return NodeNum; } |
|
242 ///Number of edges. |
|
243 int edgeNum() const { return EdgeNum; } |
|
244 |
|
245 /// Maximum node ID. |
|
246 |
|
247 /// Maximum node ID. |
|
248 ///\sa id(Node) |
|
249 int maxId(Node = INVALID) const { return NodeNum-1; } |
|
250 /// Maximum edge ID. |
|
251 |
|
252 /// Maximum edge ID. |
|
253 ///\sa id(Edge) |
|
254 int maxId(Edge = INVALID) const { return EdgeNum-1; } |
|
255 |
|
256 Node source(Edge e) const { |
|
257 /// \todo we may do it faster |
|
258 return ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2; |
|
259 } |
|
260 |
|
261 Node target(Edge e) const { |
|
262 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
|
263 return e.id - (source) * (source - 1) / 2; |
|
264 } |
|
265 |
|
266 |
|
267 /// Node ID. |
|
268 |
|
269 /// The ID of a valid Node is a nonnegative integer not greater than |
|
270 /// \ref maxNodeId(). The range of the ID's is not surely continuous |
|
271 /// and the greatest node ID can be actually less then \ref maxNodeId(). |
|
272 /// |
|
273 /// The ID of the \ref INVALID node is -1. |
|
274 ///\return The ID of the node \c v. |
|
275 |
|
276 static int id(Node v) { return v.id; } |
|
277 /// Edge ID. |
|
278 |
|
279 /// The ID of a valid Edge is a nonnegative integer not greater than |
|
280 /// \ref maxEdgeId(). The range of the ID's is not surely continuous |
|
281 /// and the greatest edge ID can be actually less then \ref maxEdgeId(). |
|
282 /// |
|
283 /// The ID of the \ref INVALID edge is -1. |
|
284 ///\return The ID of the edge \c e. |
|
285 static int id(Edge e) { return e.id; } |
|
286 |
|
287 /// Finds an edge between two nodes. |
|
288 |
|
289 /// Finds an edge from node \c u to node \c v. |
|
290 /// |
|
291 /// If \c prev is \ref INVALID (this is the default value), then |
|
292 /// It finds the first edge from \c u to \c v. Otherwise it looks for |
|
293 /// the next edge from \c u to \c v after \c prev. |
|
294 /// \return The found edge or INVALID if there is no such an edge. |
|
295 Edge findEdge(Node u,Node v, Edge prev = INVALID) |
|
296 { |
|
297 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID; |
|
298 } |
|
299 |
|
300 |
|
301 class Node { |
|
302 friend class UndirFullGraphBase; |
|
303 |
|
304 protected: |
|
305 int id; |
|
306 Node(int _id) { id = _id;} |
|
307 public: |
|
308 Node() {} |
|
309 Node (Invalid) { id = -1; } |
|
310 bool operator==(const Node node) const {return id == node.id;} |
|
311 bool operator!=(const Node node) const {return id != node.id;} |
|
312 bool operator<(const Node node) const {return id < node.id;} |
|
313 }; |
|
314 |
|
315 |
|
316 |
|
317 class Edge { |
|
318 friend class UndirFullGraphBase; |
|
319 |
|
320 protected: |
|
321 int id; // NodeNum * target + source; |
|
322 |
|
323 Edge(int _id) : id(_id) {} |
|
324 |
|
325 Edge(const UndirFullGraphBase& _graph, int source, int target) |
|
326 : id(_graph.NodeNum * target+source) {} |
|
327 public: |
|
328 Edge() { } |
|
329 Edge (Invalid) { id = -1; } |
|
330 bool operator==(const Edge edge) const {return id == edge.id;} |
|
331 bool operator!=(const Edge edge) const {return id != edge.id;} |
|
332 bool operator<(const Edge edge) const {return id < edge.id;} |
|
333 }; |
|
334 |
|
335 void first(Node& node) const { |
|
336 node.id = NodeNum-1; |
|
337 } |
|
338 |
|
339 static void next(Node& node) { |
|
340 --node.id; |
|
341 } |
|
342 |
|
343 void first(Edge& edge) const { |
|
344 edge.id = EdgeNum-1; |
|
345 } |
|
346 |
|
347 static void next(Edge& edge) { |
|
348 --edge.id; |
|
349 } |
|
350 |
|
351 void firstOut(Edge& edge, const Node& node) const { |
|
352 edge.id = node.id != 0 ? node.id * (node.id - 1) / 2 : -1; |
|
353 } |
|
354 |
|
355 /// \todo with specialized iterators we can make faster iterating |
|
356 void nextOut(Edge& e) const { |
|
357 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
|
358 int target = e.id - (source) * (source - 1) / 2; |
|
359 ++target; |
|
360 e.id = target < source ? source * (source - 1) / 2 + target : -1; |
|
361 } |
|
362 |
|
363 void firstIn(Edge& edge, const Node& node) const { |
|
364 edge.id = node.id * (node.id + 1) / 2 - 1; |
|
365 } |
|
366 |
|
367 void nextIn(Edge& e) const { |
|
368 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;; |
|
369 int target = e.id - (source) * (source - 1) / 2; ++target; |
|
370 ++source; |
|
371 e.id = source < NodeNum ? source * (source - 1) / 2 + target : -1; |
|
372 } |
|
373 |
|
374 }; |
|
375 |
|
376 /// \todo UndirFullGraph from the UndirFullGraphBase |
|
377 |
|
378 |
|
379 |
|
380 /// @} |
|
381 |
|
382 } //namespace lemon |
|
383 |
|
384 |
|
385 #endif //LEMON_FULL_GRAPH_H |
|