1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_FULL_GRAPH_H
20 #define LEMON_FULL_GRAPH_H
22 #include <lemon/math.h>
24 #include <lemon/core.h>
25 #include <lemon/bits/graph_extender.h>
29 ///\brief FullDigraph and FullGraph classes.
32 class FullDigraphBase {
35 typedef FullDigraphBase Graph;
47 void construct(int n) { _node_num = n; _arc_num = n * n; }
51 typedef True NodeNumTag;
52 typedef True ArcNumTag;
54 Node operator()(int ix) const { return Node(ix); }
55 int index(const Node& node) const { return node._id; }
57 Arc arc(const Node& s, const Node& t) const {
58 return Arc(s._id * _node_num + t._id);
61 int nodeNum() const { return _node_num; }
62 int arcNum() const { return _arc_num; }
64 int maxNodeId() const { return _node_num - 1; }
65 int maxArcId() const { return _arc_num - 1; }
67 Node source(Arc arc) const { return arc._id / _node_num; }
68 Node target(Arc arc) const { return arc._id % _node_num; }
71 static int id(Node node) { return node._id; }
72 static int id(Arc arc) { return arc._id; }
74 static Node nodeFromId(int id) { return Node(id);}
76 static Arc arcFromId(int id) { return Arc(id);}
78 typedef True FindArcTag;
80 Arc findArc(Node s, Node t, Arc prev = INVALID) const {
81 return prev != INVALID ? arc(s, t) : INVALID;
86 friend class FullDigraphBase;
90 Node(int id) : _id(id) {}
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;}
100 friend class FullDigraphBase;
103 int _id; // _node_num * source + target;
105 Arc(int id) : _id(id) {}
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;}
115 void first(Node& node) const {
116 node._id = _node_num - 1;
119 static void next(Node& node) {
123 void first(Arc& arc) const {
124 arc._id = _arc_num - 1;
127 static void next(Arc& arc) {
131 void firstOut(Arc& arc, const Node& node) const {
132 arc._id = (node._id + 1) * _node_num - 1;
135 void nextOut(Arc& arc) const {
136 if (arc._id % _node_num == 0) arc._id = 0;
140 void firstIn(Arc& arc, const Node& node) const {
141 arc._id = _arc_num + node._id - _node_num;
144 void nextIn(Arc& arc) const {
145 arc._id -= _node_num;
146 if (arc._id < 0) arc._id = -1;
151 typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
155 /// \brief A full digraph class.
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.
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.
170 class FullDigraph : public ExtendedFullDigraphBase {
173 typedef ExtendedFullDigraphBase Parent;
175 /// \brief Constructor
176 FullDigraph() { construct(0); }
178 /// \brief Constructor
180 /// \param n The number of the nodes.
181 FullDigraph(int n) { construct(n); }
183 /// \brief Resize the digraph
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
190 Parent::notifier(Arc()).clear();
191 Parent::notifier(Node()).clear();
193 Parent::notifier(Node()).build();
194 Parent::notifier(Arc()).build();
197 /// \brief Returns the node with the given index.
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); }
205 /// \brief Returns the index of the node.
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); }
213 /// \brief Returns the arc connects the given nodes.
215 /// Returns the arc connects the given nodes.
216 Arc arc(const Node& u, const Node& v) const {
217 return Parent::arc(u, v);
220 /// \brief Number of nodes.
221 int nodeNum() const { return Parent::nodeNum(); }
222 /// \brief Number of arcs.
223 int arcNum() const { return Parent::arcNum(); }
227 class FullGraphBase {
232 typedef FullGraphBase Graph;
242 void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
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;
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;
256 void _uvid(int e, int& u, int& v) const {
260 u = _node_num - 2 - u;
261 v = _node_num - 1 - v;
265 void _stid(int a, int& s, int& t) const {
273 int _eid(int u, int v) const {
274 if (u < (_node_num - 1) / 2) {
275 return u * _node_num + v;
277 return (_node_num - 1 - u) * _node_num - v - 1;
284 Node operator()(int ix) const { return Node(ix); }
285 int index(const Node& node) const { return node._id; }
287 Edge edge(const Node& u, const Node& v) const {
289 return Edge(_eid(u._id, v._id));
290 } else if (u._id != v._id) {
291 return Edge(_eid(v._id, u._id));
297 Arc arc(const Node& s, const Node& t) const {
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);
307 typedef True NodeNumTag;
308 typedef True EdgeNumTag;
310 int nodeNum() const { return _node_num; }
311 int arcNum() const { return 2 * _edge_num; }
312 int edgeNum() const { return _edge_num; }
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; }
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; }
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);}
326 Node u(Edge edge) const {
327 return Node(_uid(edge._id));
330 Node v(Edge edge) const {
331 return Node(_vid(edge._id));
334 Node source(Arc arc) const {
335 return Node((arc._id & 1) == 1 ?
336 _uid(arc._id >> 1) : _vid(arc._id >> 1));
339 Node target(Arc arc) const {
340 return Node((arc._id & 1) == 1 ?
341 _vid(arc._id >> 1) : _uid(arc._id >> 1));
344 typedef True FindEdgeTag;
346 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
347 return prev != INVALID ? INVALID : edge(u, v);
350 Arc findArc(Node s, Node t, Arc prev = INVALID) const {
351 return prev != INVALID ? INVALID : arc(s, t);
355 friend class FullGraphBase;
359 Node(int id) : _id(id) {}
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;}
369 friend class FullGraphBase;
374 Edge(int id) : _id(id) {}
378 Edge (Invalid) { _id = -1; }
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;}
386 friend class FullGraphBase;
391 Arc(int id) : _id(id) {}
395 Arc (Invalid) { _id = -1; }
397 operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
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;}
404 static bool direction(Arc arc) {
405 return (arc._id & 1) == 1;
408 static Arc direct(Edge edge, bool dir) {
409 return Arc((edge._id << 1) | (dir ? 1 : 0));
412 void first(Node& node) const {
413 node._id = _node_num - 1;
416 static void next(Node& node) {
420 void first(Arc& arc) const {
421 arc._id = (_edge_num << 1) - 1;
424 static void next(Arc& arc) {
428 void first(Edge& edge) const {
429 edge._id = _edge_num - 1;
432 static void next(Edge& edge) {
436 void firstOut(Arc& arc, const Node& node) const {
437 int s = node._id, t = _node_num - 1;
439 arc._id = (_eid(s, t) << 1) | 1;
442 arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
446 void nextOut(Arc& arc) const {
448 _stid(arc._id, s, t);
451 arc._id = (_eid(s, t) << 1) | 1;
454 arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
458 void firstIn(Arc& arc, const Node& node) const {
459 int s = _node_num - 1, t = node._id;
461 arc._id = (_eid(t, s) << 1);
464 arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
468 void nextIn(Arc& arc) const {
470 _stid(arc._id, s, t);
473 arc._id = (_eid(t, s) << 1);
476 arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
480 void firstInc(Edge& edge, bool& dir, const Node& node) const {
481 int u = node._id, v = _node_num - 1;
483 edge._id = _eid(u, v);
487 edge._id = (v != -1 ? _eid(v, u) : -1);
492 void nextInc(Edge& edge, bool& dir) const {
495 _uvid(edge._id, u, v);
498 edge._id = _eid(u, v);
501 edge._id = (v != -1 ? _eid(v, u) : -1);
505 _uvid(edge._id, v, u);
507 edge._id = (v != -1 ? _eid(v, u) : -1);
513 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
517 /// \brief An undirected full graph class.
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
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.
533 /// It also has an important extra feature that its maps are real
534 /// \ref concepts::ReferenceMap "reference map"s.
537 class FullGraph : public ExtendedFullGraphBase {
540 typedef ExtendedFullGraphBase Parent;
542 /// \brief Constructor
543 FullGraph() { construct(0); }
545 /// \brief Constructor
547 /// \param n The number of the nodes.
548 FullGraph(int n) { construct(n); }
550 /// \brief Resize the graph
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
557 Parent::notifier(Arc()).clear();
558 Parent::notifier(Edge()).clear();
559 Parent::notifier(Node()).clear();
561 Parent::notifier(Node()).build();
562 Parent::notifier(Edge()).build();
563 Parent::notifier(Arc()).build();
566 /// \brief Returns the node with the given index.
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); }
574 /// \brief Returns the index of the node.
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); }
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(); }
589 /// \brief Returns the arc connects the given nodes.
591 /// Returns the arc connects the given nodes.
592 Arc arc(const Node& s, const Node& t) const {
593 return Parent::arc(s, t);
596 /// \brief Returns the edge connects the given nodes.
598 /// Returns the edge connects the given nodes.
599 Edge edge(const Node& u, const Node& v) const {
600 return Parent::edge(u, v);
608 #endif //LEMON_FULL_GRAPH_H