|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_FULL_GRAPH_H |
|
20 #define LEMON_FULL_GRAPH_H |
|
21 |
|
22 #include <lemon/math.h> |
|
23 |
|
24 #include <lemon/core.h> |
|
25 #include <lemon/bits/graph_extender.h> |
|
26 |
|
27 ///\ingroup graphs |
|
28 ///\file |
|
29 ///\brief FullDigraph and FullGraph classes. |
|
30 namespace lemon { |
|
31 |
|
32 class FullDigraphBase { |
|
33 public: |
|
34 |
|
35 typedef FullDigraphBase Graph; |
|
36 |
|
37 class Node; |
|
38 class Arc; |
|
39 |
|
40 protected: |
|
41 |
|
42 int _node_num; |
|
43 int _arc_num; |
|
44 |
|
45 FullDigraphBase() {} |
|
46 |
|
47 void construct(int n) { _node_num = n; _arc_num = n * n; } |
|
48 |
|
49 public: |
|
50 |
|
51 typedef True NodeNumTag; |
|
52 typedef True ArcNumTag; |
|
53 |
|
54 Node operator()(int ix) const { return Node(ix); } |
|
55 int index(const Node& node) const { return node._id; } |
|
56 |
|
57 Arc arc(const Node& s, const Node& t) const { |
|
58 return Arc(s._id * _node_num + t._id); |
|
59 } |
|
60 |
|
61 int nodeNum() const { return _node_num; } |
|
62 int arcNum() const { return _arc_num; } |
|
63 |
|
64 int maxNodeId() const { return _node_num - 1; } |
|
65 int maxArcId() const { return _arc_num - 1; } |
|
66 |
|
67 Node source(Arc arc) const { return arc._id / _node_num; } |
|
68 Node target(Arc arc) const { return arc._id % _node_num; } |
|
69 |
|
70 |
|
71 static int id(Node node) { return node._id; } |
|
72 static int id(Arc arc) { return arc._id; } |
|
73 |
|
74 static Node nodeFromId(int id) { return Node(id);} |
|
75 |
|
76 static Arc arcFromId(int id) { return Arc(id);} |
|
77 |
|
78 typedef True FindArcTag; |
|
79 |
|
80 Arc findArc(Node s, Node t, Arc prev = INVALID) const { |
|
81 return prev != INVALID ? arc(s, t) : INVALID; |
|
82 } |
|
83 |
|
84 |
|
85 class Node { |
|
86 friend class FullDigraphBase; |
|
87 |
|
88 protected: |
|
89 int _id; |
|
90 Node(int id) : _id(id) {} |
|
91 public: |
|
92 Node() {} |
|
93 Node (Invalid) : _id(-1) {} |
|
94 bool operator==(const Node node) const {return _id == node._id;} |
|
95 bool operator!=(const Node node) const {return _id != node._id;} |
|
96 bool operator<(const Node node) const {return _id < node._id;} |
|
97 }; |
|
98 |
|
99 class Arc { |
|
100 friend class FullDigraphBase; |
|
101 |
|
102 protected: |
|
103 int _id; // _node_num * source + target; |
|
104 |
|
105 Arc(int id) : _id(id) {} |
|
106 |
|
107 public: |
|
108 Arc() { } |
|
109 Arc (Invalid) { _id = -1; } |
|
110 bool operator==(const Arc arc) const {return _id == arc._id;} |
|
111 bool operator!=(const Arc arc) const {return _id != arc._id;} |
|
112 bool operator<(const Arc arc) const {return _id < arc._id;} |
|
113 }; |
|
114 |
|
115 void first(Node& node) const { |
|
116 node._id = _node_num - 1; |
|
117 } |
|
118 |
|
119 static void next(Node& node) { |
|
120 --node._id; |
|
121 } |
|
122 |
|
123 void first(Arc& arc) const { |
|
124 arc._id = _arc_num - 1; |
|
125 } |
|
126 |
|
127 static void next(Arc& arc) { |
|
128 --arc._id; |
|
129 } |
|
130 |
|
131 void firstOut(Arc& arc, const Node& node) const { |
|
132 arc._id = (node._id + 1) * _node_num - 1; |
|
133 } |
|
134 |
|
135 void nextOut(Arc& arc) const { |
|
136 if (arc._id % _node_num == 0) arc._id = 0; |
|
137 --arc._id; |
|
138 } |
|
139 |
|
140 void firstIn(Arc& arc, const Node& node) const { |
|
141 arc._id = _arc_num + node._id - _node_num; |
|
142 } |
|
143 |
|
144 void nextIn(Arc& arc) const { |
|
145 arc._id -= _node_num; |
|
146 if (arc._id < 0) arc._id = -1; |
|
147 } |
|
148 |
|
149 }; |
|
150 |
|
151 typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase; |
|
152 |
|
153 /// \ingroup graphs |
|
154 /// |
|
155 /// \brief A full digraph class. |
|
156 /// |
|
157 /// This is a simple and fast directed full graph implementation. |
|
158 /// From each node go arcs to each node (including the source node), |
|
159 /// therefore the number of the arcs in the digraph is the square of |
|
160 /// the node number. The digraph is completely static, so you can |
|
161 /// neither add nor delete either arcs or nodes, and it needs just |
|
162 /// constant space in memory. |
|
163 /// |
|
164 /// Thus it conforms to the \ref concepts::Digraph "Digraph" concept |
|
165 /// and it also has an important extra feature that its maps are |
|
166 /// real \ref concepts::ReferenceMap "reference map"s. |
|
167 /// \sa concepts::Digraph. |
|
168 /// |
|
169 /// \sa FullGraph |
|
170 class FullDigraph : public ExtendedFullDigraphBase { |
|
171 public: |
|
172 |
|
173 typedef ExtendedFullDigraphBase Parent; |
|
174 |
|
175 /// \brief Constructor |
|
176 FullDigraph() { construct(0); } |
|
177 |
|
178 /// \brief Constructor |
|
179 /// |
|
180 /// \param n The number of the nodes. |
|
181 FullDigraph(int n) { construct(n); } |
|
182 |
|
183 /// \brief Resize the digraph |
|
184 /// |
|
185 /// Resize the digraph. The function will fully destroy and |
|
186 /// rebuild the digraph. This cause that the maps of the digraph |
|
187 /// will reallocated automatically and the previous values will be |
|
188 /// lost. |
|
189 void resize(int n) { |
|
190 Parent::notifier(Arc()).clear(); |
|
191 Parent::notifier(Node()).clear(); |
|
192 construct(n); |
|
193 Parent::notifier(Node()).build(); |
|
194 Parent::notifier(Arc()).build(); |
|
195 } |
|
196 |
|
197 /// \brief Returns the node with the given index. |
|
198 /// |
|
199 /// Returns the node with the given index. Because it is a |
|
200 /// static size digraph the node's of the digraph can be indexed |
|
201 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of |
|
202 /// the node can accessed by the \e index() member. |
|
203 Node operator()(int ix) const { return Parent::operator()(ix); } |
|
204 |
|
205 /// \brief Returns the index of the node. |
|
206 /// |
|
207 /// Returns the index of the node. Because it is a |
|
208 /// static size digraph the node's of the digraph can be indexed |
|
209 /// in the range <tt>[0..nodeNum()-1]</tt> and the index of |
|
210 /// the node can accessed by the \e index() member. |
|
211 int index(const Node& node) const { return Parent::index(node); } |
|
212 |
|
213 /// \brief Returns the arc connects the given nodes. |
|
214 /// |
|
215 /// Returns the arc connects the given nodes. |
|
216 Arc arc(const Node& u, const Node& v) const { |
|
217 return Parent::arc(u, v); |
|
218 } |
|
219 |
|
220 /// \brief Number of nodes. |
|
221 int nodeNum() const { return Parent::nodeNum(); } |
|
222 /// \brief Number of arcs. |
|
223 int arcNum() const { return Parent::arcNum(); } |
|
224 }; |
|
225 |
|
226 |
|
227 class FullGraphBase { |
|
228 int _node_num; |
|
229 int _edge_num; |
|
230 public: |
|
231 |
|
232 typedef FullGraphBase Graph; |
|
233 |
|
234 class Node; |
|
235 class Arc; |
|
236 class Edge; |
|
237 |
|
238 protected: |
|
239 |
|
240 FullGraphBase() {} |
|
241 |
|
242 void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; } |
|
243 |
|
244 int _uid(int e) const { |
|
245 int u = e / _node_num; |
|
246 int v = e % _node_num; |
|
247 return u < v ? u : _node_num - 2 - u; |
|
248 } |
|
249 |
|
250 int _vid(int e) const { |
|
251 int u = e / _node_num; |
|
252 int v = e % _node_num; |
|
253 return u < v ? v : _node_num - 1 - v; |
|
254 } |
|
255 |
|
256 void _uvid(int e, int& u, int& v) const { |
|
257 u = e / _node_num; |
|
258 v = e % _node_num; |
|
259 if (u >= v) { |
|
260 u = _node_num - 2 - u; |
|
261 v = _node_num - 1 - v; |
|
262 } |
|
263 } |
|
264 |
|
265 void _stid(int a, int& s, int& t) const { |
|
266 if ((a & 1) == 1) { |
|
267 _uvid(a >> 1, s, t); |
|
268 } else { |
|
269 _uvid(a >> 1, t, s); |
|
270 } |
|
271 } |
|
272 |
|
273 int _eid(int u, int v) const { |
|
274 if (u < (_node_num - 1) / 2) { |
|
275 return u * _node_num + v; |
|
276 } else { |
|
277 return (_node_num - 1 - u) * _node_num - v - 1; |
|
278 } |
|
279 } |
|
280 |
|
281 public: |
|
282 |
|
283 |
|
284 Node operator()(int ix) const { return Node(ix); } |
|
285 int index(const Node& node) const { return node._id; } |
|
286 |
|
287 Edge edge(const Node& u, const Node& v) const { |
|
288 if (u._id < v._id) { |
|
289 return Edge(_eid(u._id, v._id)); |
|
290 } else if (u._id != v._id) { |
|
291 return Edge(_eid(v._id, u._id)); |
|
292 } else { |
|
293 return INVALID; |
|
294 } |
|
295 } |
|
296 |
|
297 Arc arc(const Node& s, const Node& t) const { |
|
298 if (s._id < t._id) { |
|
299 return Arc((_eid(s._id, t._id) << 1) | 1); |
|
300 } else if (s._id != t._id) { |
|
301 return Arc(_eid(t._id, s._id) << 1); |
|
302 } else { |
|
303 return INVALID; |
|
304 } |
|
305 } |
|
306 |
|
307 typedef True NodeNumTag; |
|
308 typedef True EdgeNumTag; |
|
309 |
|
310 int nodeNum() const { return _node_num; } |
|
311 int arcNum() const { return 2 * _edge_num; } |
|
312 int edgeNum() const { return _edge_num; } |
|
313 |
|
314 static int id(Node node) { return node._id; } |
|
315 static int id(Arc arc) { return arc._id; } |
|
316 static int id(Edge edge) { return edge._id; } |
|
317 |
|
318 int maxNodeId() const { return _node_num-1; } |
|
319 int maxArcId() const { return 2 * _edge_num-1; } |
|
320 int maxEdgeId() const { return _edge_num-1; } |
|
321 |
|
322 static Node nodeFromId(int id) { return Node(id);} |
|
323 static Arc arcFromId(int id) { return Arc(id);} |
|
324 static Edge edgeFromId(int id) { return Edge(id);} |
|
325 |
|
326 Node u(Edge edge) const { |
|
327 return Node(_uid(edge._id)); |
|
328 } |
|
329 |
|
330 Node v(Edge edge) const { |
|
331 return Node(_vid(edge._id)); |
|
332 } |
|
333 |
|
334 Node source(Arc arc) const { |
|
335 return Node((arc._id & 1) == 1 ? |
|
336 _uid(arc._id >> 1) : _vid(arc._id >> 1)); |
|
337 } |
|
338 |
|
339 Node target(Arc arc) const { |
|
340 return Node((arc._id & 1) == 1 ? |
|
341 _vid(arc._id >> 1) : _uid(arc._id >> 1)); |
|
342 } |
|
343 |
|
344 typedef True FindEdgeTag; |
|
345 |
|
346 Edge findEdge(Node u, Node v, Edge prev = INVALID) const { |
|
347 return prev != INVALID ? INVALID : edge(u, v); |
|
348 } |
|
349 |
|
350 Arc findArc(Node s, Node t, Arc prev = INVALID) const { |
|
351 return prev != INVALID ? INVALID : arc(s, t); |
|
352 } |
|
353 |
|
354 class Node { |
|
355 friend class FullGraphBase; |
|
356 |
|
357 protected: |
|
358 int _id; |
|
359 Node(int id) : _id(id) {} |
|
360 public: |
|
361 Node() {} |
|
362 Node (Invalid) { _id = -1; } |
|
363 bool operator==(const Node node) const {return _id == node._id;} |
|
364 bool operator!=(const Node node) const {return _id != node._id;} |
|
365 bool operator<(const Node node) const {return _id < node._id;} |
|
366 }; |
|
367 |
|
368 class Edge { |
|
369 friend class FullGraphBase; |
|
370 |
|
371 protected: |
|
372 int _id; |
|
373 |
|
374 Edge(int id) : _id(id) {} |
|
375 |
|
376 public: |
|
377 Edge() { } |
|
378 Edge (Invalid) { _id = -1; } |
|
379 |
|
380 bool operator==(const Edge edge) const {return _id == edge._id;} |
|
381 bool operator!=(const Edge edge) const {return _id != edge._id;} |
|
382 bool operator<(const Edge edge) const {return _id < edge._id;} |
|
383 }; |
|
384 |
|
385 class Arc { |
|
386 friend class FullGraphBase; |
|
387 |
|
388 protected: |
|
389 int _id; |
|
390 |
|
391 Arc(int id) : _id(id) {} |
|
392 |
|
393 public: |
|
394 Arc() { } |
|
395 Arc (Invalid) { _id = -1; } |
|
396 |
|
397 operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); } |
|
398 |
|
399 bool operator==(const Arc arc) const {return _id == arc._id;} |
|
400 bool operator!=(const Arc arc) const {return _id != arc._id;} |
|
401 bool operator<(const Arc arc) const {return _id < arc._id;} |
|
402 }; |
|
403 |
|
404 static bool direction(Arc arc) { |
|
405 return (arc._id & 1) == 1; |
|
406 } |
|
407 |
|
408 static Arc direct(Edge edge, bool dir) { |
|
409 return Arc((edge._id << 1) | (dir ? 1 : 0)); |
|
410 } |
|
411 |
|
412 void first(Node& node) const { |
|
413 node._id = _node_num - 1; |
|
414 } |
|
415 |
|
416 static void next(Node& node) { |
|
417 --node._id; |
|
418 } |
|
419 |
|
420 void first(Arc& arc) const { |
|
421 arc._id = (_edge_num << 1) - 1; |
|
422 } |
|
423 |
|
424 static void next(Arc& arc) { |
|
425 --arc._id; |
|
426 } |
|
427 |
|
428 void first(Edge& edge) const { |
|
429 edge._id = _edge_num - 1; |
|
430 } |
|
431 |
|
432 static void next(Edge& edge) { |
|
433 --edge._id; |
|
434 } |
|
435 |
|
436 void firstOut(Arc& arc, const Node& node) const { |
|
437 int s = node._id, t = _node_num - 1; |
|
438 if (s < t) { |
|
439 arc._id = (_eid(s, t) << 1) | 1; |
|
440 } else { |
|
441 --t; |
|
442 arc._id = (t != -1 ? (_eid(t, s) << 1) : -1); |
|
443 } |
|
444 } |
|
445 |
|
446 void nextOut(Arc& arc) const { |
|
447 int s, t; |
|
448 _stid(arc._id, s, t); |
|
449 --t; |
|
450 if (s < t) { |
|
451 arc._id = (_eid(s, t) << 1) | 1; |
|
452 } else { |
|
453 if (s == t) --t; |
|
454 arc._id = (t != -1 ? (_eid(t, s) << 1) : -1); |
|
455 } |
|
456 } |
|
457 |
|
458 void firstIn(Arc& arc, const Node& node) const { |
|
459 int s = _node_num - 1, t = node._id; |
|
460 if (s > t) { |
|
461 arc._id = (_eid(t, s) << 1); |
|
462 } else { |
|
463 --s; |
|
464 arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1); |
|
465 } |
|
466 } |
|
467 |
|
468 void nextIn(Arc& arc) const { |
|
469 int s, t; |
|
470 _stid(arc._id, s, t); |
|
471 --s; |
|
472 if (s > t) { |
|
473 arc._id = (_eid(t, s) << 1); |
|
474 } else { |
|
475 if (s == t) --s; |
|
476 arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1); |
|
477 } |
|
478 } |
|
479 |
|
480 void firstInc(Edge& edge, bool& dir, const Node& node) const { |
|
481 int u = node._id, v = _node_num - 1; |
|
482 if (u < v) { |
|
483 edge._id = _eid(u, v); |
|
484 dir = true; |
|
485 } else { |
|
486 --v; |
|
487 edge._id = (v != -1 ? _eid(v, u) : -1); |
|
488 dir = false; |
|
489 } |
|
490 } |
|
491 |
|
492 void nextInc(Edge& edge, bool& dir) const { |
|
493 int u, v; |
|
494 if (dir) { |
|
495 _uvid(edge._id, u, v); |
|
496 --v; |
|
497 if (u < v) { |
|
498 edge._id = _eid(u, v); |
|
499 } else { |
|
500 --v; |
|
501 edge._id = (v != -1 ? _eid(v, u) : -1); |
|
502 dir = false; |
|
503 } |
|
504 } else { |
|
505 _uvid(edge._id, v, u); |
|
506 --v; |
|
507 edge._id = (v != -1 ? _eid(v, u) : -1); |
|
508 } |
|
509 } |
|
510 |
|
511 }; |
|
512 |
|
513 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase; |
|
514 |
|
515 /// \ingroup graphs |
|
516 /// |
|
517 /// \brief An undirected full graph class. |
|
518 /// |
|
519 /// This is a simple and fast undirected full graph |
|
520 /// implementation. From each node go edge to each other node, |
|
521 /// therefore the number of edges in the graph is |
|
522 /// <tt>n(n-1)/2</tt>. It is completely static, so you can neither |
|
523 /// add nor delete either edges or nodes, and it needs just constant |
|
524 /// space in memory. |
|
525 /// |
|
526 /// The \e FullDigraph and \e FullGraph classes are very similar, |
|
527 /// but there are two differences. While the \e FullDigraph class is |
|
528 /// conform just to the \ref concepts::Digraph "Digraph" concept, |
|
529 /// this class is conform to the \ref concepts::Graph "Graph" |
|
530 /// concept. In addition, the \e FullGraph class does not contain a |
|
531 /// loop arc from each node as the \e FullDigraph does. |
|
532 /// |
|
533 /// It also has an important extra feature that its maps are real |
|
534 /// \ref concepts::ReferenceMap "reference map"s. |
|
535 /// |
|
536 /// \sa FullDigraph |
|
537 class FullGraph : public ExtendedFullGraphBase { |
|
538 public: |
|
539 |
|
540 typedef ExtendedFullGraphBase Parent; |
|
541 |
|
542 /// \brief Constructor |
|
543 FullGraph() { construct(0); } |
|
544 |
|
545 /// \brief Constructor |
|
546 /// |
|
547 /// \param n The number of the nodes. |
|
548 FullGraph(int n) { construct(n); } |
|
549 |
|
550 /// \brief Resize the graph |
|
551 /// |
|
552 /// Resize the graph. The function will fully destroy and rebuild |
|
553 /// the graph. This cause that the maps of the graph will |
|
554 /// reallocated automatically and the previous values will be |
|
555 /// lost. |
|
556 void resize(int n) { |
|
557 Parent::notifier(Arc()).clear(); |
|
558 Parent::notifier(Edge()).clear(); |
|
559 Parent::notifier(Node()).clear(); |
|
560 construct(n); |
|
561 Parent::notifier(Node()).build(); |
|
562 Parent::notifier(Edge()).build(); |
|
563 Parent::notifier(Arc()).build(); |
|
564 } |
|
565 |
|
566 /// \brief Returns the node with the given index. |
|
567 /// |
|
568 /// Returns the node with the given index. Because it is a static |
|
569 /// size graph the node's of the graph can be indexed in the range |
|
570 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can |
|
571 /// accessed by the \e index() member. |
|
572 Node operator()(int ix) const { return Parent::operator()(ix); } |
|
573 |
|
574 /// \brief Returns the index of the node. |
|
575 /// |
|
576 /// Returns the index of the node. Because it is a static size |
|
577 /// graph the node's of the graph can be indexed in the range |
|
578 /// <tt>[0..nodeNum()-1]</tt> and the index of the node can |
|
579 /// accessed by the \e index() member. |
|
580 int index(const Node& node) const { return Parent::index(node); } |
|
581 |
|
582 /// \brief Number of nodes. |
|
583 int nodeNum() const { return Parent::nodeNum(); } |
|
584 /// \brief Number of arcs. |
|
585 int arcNum() const { return Parent::arcNum(); } |
|
586 /// \brief Number of edges. |
|
587 int edgeNum() const { return Parent::edgeNum(); } |
|
588 |
|
589 /// \brief Returns the arc connects the given nodes. |
|
590 /// |
|
591 /// Returns the arc connects the given nodes. |
|
592 Arc arc(const Node& s, const Node& t) const { |
|
593 return Parent::arc(s, t); |
|
594 } |
|
595 |
|
596 /// \brief Returns the edge connects the given nodes. |
|
597 /// |
|
598 /// Returns the edge connects the given nodes. |
|
599 Edge edge(const Node& u, const Node& v) const { |
|
600 return Parent::edge(u, v); |
|
601 } |
|
602 }; |
|
603 |
|
604 |
|
605 } //namespace lemon |
|
606 |
|
607 |
|
608 #endif //LEMON_FULL_GRAPH_H |