vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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
25 #include <lemon/bits/iterable_graph_extender.h>
26 #include <lemon/bits/alteration_notifier.h>
27 #include <lemon/bits/static_map.h>
28 #include <lemon/bits/graph_extender.h>
30 #include <lemon/invalid.h>
31 #include <lemon/utility.h>
36 ///\brief FullGraph and FullUGraph classes.
46 typedef FullGraphBase Graph;
56 ///Creates a full graph with \c n nodes.
57 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
59 // FullGraphBase(const FullGraphBase &_g)
60 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
62 typedef True NodeNumTag;
63 typedef True EdgeNumTag;
66 int nodeNum() const { return _nodeNum; }
68 int edgeNum() const { return _edgeNum; }
74 int maxNodeId() const { return _nodeNum-1; }
79 int maxEdgeId() const { return _edgeNum-1; }
81 Node source(Edge e) const { return e.id % _nodeNum; }
82 Node target(Edge e) const { return e.id / _nodeNum; }
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().
91 /// The ID of the \ref INVALID node is -1.
92 ///\return The ID of the node \c v.
94 static int id(Node v) { return v.id; }
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().
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; }
105 static Node nodeFromId(int id) { return Node(id);}
107 static Edge edgeFromId(int id) { return Edge(id);}
109 typedef True FindEdgeTag;
111 /// Finds an edge between two nodes.
113 /// Finds an edge from node \c u to node \c v.
115 /// If \c prev is \ref INVALID (this is the default value), then
116 /// It finds the first edge from \c u to \c v. Otherwise it looks for
117 /// the next edge from \c u to \c v after \c prev.
118 /// \return The found edge or INVALID if there is no such an edge.
119 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
120 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
125 friend class FullGraphBase;
129 Node(int _id) : id(_id) {}
132 Node (Invalid) : id(-1) {}
133 bool operator==(const Node node) const {return id == node.id;}
134 bool operator!=(const Node node) const {return id != node.id;}
135 bool operator<(const Node node) const {return id < node.id;}
141 friend class FullGraphBase;
144 int id; // _nodeNum * target + source;
146 Edge(int _id) : id(_id) {}
148 Edge(const FullGraphBase& _graph, int source, int target)
149 : id(_graph._nodeNum * target+source) {}
152 Edge (Invalid) { id = -1; }
153 bool operator==(const Edge edge) const {return id == edge.id;}
154 bool operator!=(const Edge edge) const {return id != edge.id;}
155 bool operator<(const Edge edge) const {return id < edge.id;}
158 void first(Node& node) const {
159 node.id = _nodeNum-1;
162 static void next(Node& node) {
166 void first(Edge& edge) const {
167 edge.id = _edgeNum-1;
170 static void next(Edge& edge) {
174 void firstOut(Edge& edge, const Node& node) const {
175 edge.id = _edgeNum + node.id - _nodeNum;
178 void nextOut(Edge& edge) const {
180 if (edge.id < 0) edge.id = -1;
183 void firstIn(Edge& edge, const Node& node) const {
184 edge.id = node.id * _nodeNum;
187 void nextIn(Edge& edge) const {
189 if (edge.id % _nodeNum == 0) edge.id = -1;
194 typedef StaticMappableGraphExtender<
195 IterableGraphExtender<
196 AlterableGraphExtender<
197 GraphExtender<FullGraphBase> > > > ExtendedFullGraphBase;
201 /// \brief A full graph class.
203 /// This is a simple and fast directed full graph implementation.
204 /// It is completely static, so you can neither add nor delete either
206 /// Thus it conforms to
207 /// the \ref concept::StaticGraph "StaticGraph" concept
208 /// \sa concept::StaticGraph.
210 /// \author Alpar Juttner
211 class FullGraph : public ExtendedFullGraphBase {
214 FullGraph(int n) { construct(n); }
218 class FullUGraphBase {
223 typedef FullUGraphBase Graph;
233 ///Creates a full graph with \c n nodes.
234 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
236 // FullGraphBase(const FullGraphBase &_g)
237 // : _nodeNum(_g.nodeNum()), _edgeNum(_nodeNum*_nodeNum) { }
239 typedef True NodeNumTag;
240 typedef True EdgeNumTag;
243 int nodeNum() const { return _nodeNum; }
245 int edgeNum() const { return _edgeNum; }
251 int maxNodeId() const { return _nodeNum-1; }
256 int maxEdgeId() const { return _edgeNum-1; }
258 Node source(Edge e) const {
259 /// \todo we may do it faster
260 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
263 Node target(Edge e) const {
264 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
265 return Node(e.id - (source) * (source - 1) / 2);
271 /// The ID of a valid Node is a nonnegative integer not greater than
272 /// \ref maxNodeId(). The range of the ID's is not surely continuous
273 /// and the greatest node ID can be actually less then \ref maxNodeId().
275 /// The ID of the \ref INVALID node is -1.
276 ///\return The ID of the node \c v.
278 static int id(Node v) { return v.id; }
281 /// The ID of a valid Edge is a nonnegative integer not greater than
282 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
283 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
285 /// The ID of the \ref INVALID edge is -1.
286 ///\return The ID of the edge \c e.
287 static int id(Edge e) { return e.id; }
289 /// Finds an edge between two nodes.
291 /// Finds an edge from node \c u to node \c v.
293 /// If \c prev is \ref INVALID (this is the default value), then
294 /// It finds the first edge from \c u to \c v. Otherwise it looks for
295 /// the next edge from \c u to \c v after \c prev.
296 /// \return The found edge or INVALID if there is no such an edge.
297 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
298 if (prev.id != -1 || u.id <= v.id) return -1;
299 return Edge(u.id * (u.id - 1) / 2 + v.id);
302 typedef True FindEdgeTag;
306 friend class FullUGraphBase;
310 Node(int _id) { id = _id;}
313 Node (Invalid) { id = -1; }
314 bool operator==(const Node node) const {return id == node.id;}
315 bool operator!=(const Node node) const {return id != node.id;}
316 bool operator<(const Node node) const {return id < node.id;}
322 friend class FullUGraphBase;
325 int id; // _nodeNum * target + source;
327 Edge(int _id) : id(_id) {}
331 Edge (Invalid) { id = -1; }
332 bool operator==(const Edge edge) const {return id == edge.id;}
333 bool operator!=(const Edge edge) const {return id != edge.id;}
334 bool operator<(const Edge edge) const {return id < edge.id;}
337 void first(Node& node) const {
338 node.id = _nodeNum - 1;
341 static void next(Node& node) {
345 void first(Edge& edge) const {
346 edge.id = _edgeNum - 1;
349 static void next(Edge& edge) {
353 void firstOut(Edge& edge, const Node& node) const {
356 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
359 /// \todo with specialized iterators we can make faster iterating
360 void nextOut(Edge& edge) const {
361 int src = source(edge).id;
362 int trg = target(edge).id;
364 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
367 void firstIn(Edge& edge, const Node& node) const {
368 int src = node.id + 1;
370 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
373 void nextIn(Edge& edge) const {
374 int src = source(edge).id;
375 int trg = target(edge).id;
377 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
382 typedef StaticMappableUGraphExtender<
383 IterableUGraphExtender<
384 AlterableUGraphExtender<
385 UGraphExtender<FullUGraphBase> > > > ExtendedFullUGraphBase;
389 /// \brief An undirected full graph class.
391 /// This is a simple and fast undirected full graph implementation.
392 /// It is completely static, so you can neither add nor delete either
395 /// The main difference beetween the \e FullGraph and \e FullUGraph class
396 /// is that this class conforms to the undirected graph concept and
397 /// it does not contain the loop edges.
401 /// \author Balazs Dezso
402 class FullUGraph : public ExtendedFullUGraphBase {
404 FullUGraph(int n) { construct(n); }
408 class FullBpUGraphBase {
418 class NodeSetError : public LogicError {
419 virtual const char* exceptionName() const {
420 return "lemon::FullBpUGraph::NodeSetError";
425 friend class FullBpUGraphBase;
429 Node(int _id) : id(_id) {}
432 Node(Invalid) { id = -1; }
433 bool operator==(const Node i) const {return id==i.id;}
434 bool operator!=(const Node i) const {return id!=i.id;}
435 bool operator<(const Node i) const {return id<i.id;}
439 friend class FullBpUGraphBase;
443 Edge(int _id) { id = _id;}
446 Edge (Invalid) { id = -1; }
447 bool operator==(const Edge i) const {return id==i.id;}
448 bool operator!=(const Edge i) const {return id!=i.id;}
449 bool operator<(const Edge i) const {return id<i.id;}
452 void construct(int aNodeNum, int bNodeNum) {
453 _aNodeNum = aNodeNum;
454 _bNodeNum = bNodeNum;
455 _edgeNum = aNodeNum * bNodeNum;
458 void firstANode(Node& node) const {
459 node.id = 2 * _aNodeNum - 2;
460 if (node.id < 0) node.id = -1;
462 void nextANode(Node& node) const {
464 if (node.id < 0) node.id = -1;
467 void firstBNode(Node& node) const {
468 node.id = 2 * _bNodeNum - 1;
470 void nextBNode(Node& node) const {
474 void first(Node& node) const {
476 node.id = 2 * _aNodeNum - 2;
478 node.id = 2 * _bNodeNum - 1;
481 void next(Node& node) const {
484 node.id = 2 * _bNodeNum - 1;
488 void first(Edge& edge) const {
489 edge.id = _edgeNum - 1;
491 void next(Edge& edge) const {
495 void firstOut(Edge& edge, const Node& node) const {
496 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
497 edge.id = (node.id >> 1) * _bNodeNum;
499 void nextOut(Edge& edge) const {
501 if (edge.id % _bNodeNum == 0) edge.id = -1;
504 void firstIn(Edge& edge, const Node& node) const {
505 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
506 edge.id = (node.id >> 1);
508 void nextIn(Edge& edge) const {
509 edge.id += _bNodeNum;
510 if (edge.id >= _edgeNum) edge.id = -1;
513 static int id(const Node& node) {
516 static Node nodeFromId(int id) {
519 int maxNodeId() const {
520 return _aNodeNum > _bNodeNum ?
521 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
524 static int id(const Edge& edge) {
527 static Edge edgeFromId(int id) {
530 int maxEdgeId() const {
534 static int aNodeId(const Node& node) {
537 static Node fromANodeId(int id, Node) {
538 return Node(id << 1);
540 int maxANodeId() const {
544 static int bNodeId(const Node& node) {
547 static Node fromBNodeId(int id) {
548 return Node((id << 1) + 1);
550 int maxBNodeId() const {
554 Node aNode(const Edge& edge) const {
555 return Node((edge.id / _bNodeNum) << 1);
557 Node bNode(const Edge& edge) const {
558 return Node(((edge.id % _bNodeNum) << 1) + 1);
561 static bool aNode(const Node& node) {
562 return (node.id & 1) == 0;
565 static bool bNode(const Node& node) {
566 return (node.id & 1) == 1;
569 static Node aNode(int index) {
570 return Node(index << 1);
573 static Node bNode(int index) {
574 return Node((index << 1) + 1);
580 typedef StaticMappableBpUGraphExtender<
581 IterableBpUGraphExtender<
582 AlterableBpUGraphExtender<
584 FullBpUGraphBase> > > >
585 ExtendedFullBpUGraphBase;
590 /// \brief An undirected full bipartite graph class.
592 /// This is a simple and fast bipartite undirected full graph implementation.
593 /// It is completely static, so you can neither add nor delete either
598 /// \author Balazs Dezso
600 public ExtendedFullBpUGraphBase {
602 typedef ExtendedFullBpUGraphBase Parent;
603 FullBpUGraph(int aNodeNum, int bNodeNum) {
604 Parent::construct(aNodeNum, bNodeNum);
611 #endif //LEMON_FULL_GRAPH_H