Unionfind changes induced some bugs here. Also some augmentations made.
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
24 #include <lemon/bits/base_extender.h>
25 #include <lemon/bits/graph_extender.h>
27 #include <lemon/bits/invalid.h>
28 #include <lemon/bits/utility.h>
33 ///\brief FullGraph and FullUGraph classes.
38 /// \brief Base of the FullGrpah.
40 /// Base of the FullGrpah.
46 typedef FullGraphBase Graph;
56 ///Creates a full graph with \c n nodes.
57 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
59 typedef True NodeNumTag;
60 typedef True EdgeNumTag;
62 /// \brief Returns the node with the given index.
64 /// Returns the node with the given index. Because it is a
65 /// static size graph the node's of the graph can be indiced
66 /// by the range from 0 to \e nodeNum()-1 and the index of
67 /// the node can accessed by the \e index() member.
68 Node operator()(int index) const { return Node(index); }
70 /// \brief Returns the index of the node.
72 /// Returns the index of the node. Because it is a
73 /// static size graph the node's of the graph can be indiced
74 /// by the range from 0 to \e nodeNum()-1 and the index of
75 /// the node can accessed by the \e index() member.
76 int index(const Node& node) const { return node.id; }
79 int nodeNum() const { return _nodeNum; }
81 int edgeNum() const { return _edgeNum; }
87 int maxNodeId() const { return _nodeNum-1; }
92 int maxEdgeId() const { return _edgeNum-1; }
94 Node source(Edge e) const { return e.id % _nodeNum; }
95 Node target(Edge e) const { return e.id / _nodeNum; }
100 /// The ID of a valid Node is a nonnegative integer not greater than
101 /// \ref maxNodeId(). The range of the ID's is not surely continuous
102 /// and the greatest node ID can be actually less then \ref maxNodeId().
104 /// The ID of the \ref INVALID node is -1.
105 ///\return The ID of the node \c v.
107 static int id(Node v) { return v.id; }
110 /// The ID of a valid Edge is a nonnegative integer not greater than
111 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
112 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
114 /// The ID of the \ref INVALID edge is -1.
115 ///\return The ID of the edge \c e.
116 static int id(Edge e) { return e.id; }
118 static Node nodeFromId(int id) { return Node(id);}
120 static Edge edgeFromId(int id) { return Edge(id);}
122 typedef True FindEdgeTag;
124 /// Finds an edge between two nodes.
126 /// Finds an edge from node \c u to node \c v.
128 /// If \c prev is \ref INVALID (this is the default value), then
129 /// It finds the first edge from \c u to \c v. Otherwise it looks for
130 /// the next edge from \c u to \c v after \c prev.
131 /// \return The found edge or INVALID if there is no such an edge.
132 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
133 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
138 friend class FullGraphBase;
142 Node(int _id) : id(_id) {}
145 Node (Invalid) : id(-1) {}
146 bool operator==(const Node node) const {return id == node.id;}
147 bool operator!=(const Node node) const {return id != node.id;}
148 bool operator<(const Node node) const {return id < node.id;}
154 friend class FullGraphBase;
157 int id; // _nodeNum * target + source;
159 Edge(int _id) : id(_id) {}
161 Edge(const FullGraphBase& _graph, int source, int target)
162 : id(_graph._nodeNum * target+source) {}
165 Edge (Invalid) { id = -1; }
166 bool operator==(const Edge edge) const {return id == edge.id;}
167 bool operator!=(const Edge edge) const {return id != edge.id;}
168 bool operator<(const Edge edge) const {return id < edge.id;}
171 void first(Node& node) const {
172 node.id = _nodeNum-1;
175 static void next(Node& node) {
179 void first(Edge& edge) const {
180 edge.id = _edgeNum-1;
183 static void next(Edge& edge) {
187 void firstOut(Edge& edge, const Node& node) const {
188 edge.id = _edgeNum + node.id - _nodeNum;
191 void nextOut(Edge& edge) const {
193 if (edge.id < 0) edge.id = -1;
196 void firstIn(Edge& edge, const Node& node) const {
197 edge.id = node.id * _nodeNum;
200 void nextIn(Edge& edge) const {
202 if (edge.id % _nodeNum == 0) edge.id = -1;
207 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
211 /// \brief A full graph class.
213 /// This is a simple and fast directed full graph implementation.
214 /// It is completely static, so you can neither add nor delete either
216 /// Thus it conforms to
217 /// the \ref concept::StaticGraph "StaticGraph" concept
218 /// \sa concept::StaticGraph.
220 /// \sa FullGraphBase
223 /// \author Alpar Juttner
224 class FullGraph : public ExtendedFullGraphBase {
227 typedef ExtendedFullGraphBase Parent;
229 /// \brief Constructor
230 FullGraph() { construct(0); }
232 /// \brief Constructor
234 FullGraph(int n) { construct(n); }
236 /// \brief Resize the graph
238 /// Resize the graph. The function will fully destroy and build the graph.
239 /// This cause that the maps of the graph will reallocated
240 /// automatically and the previous values will be lost.
242 Parent::getNotifier(Edge()).clear();
243 Parent::getNotifier(Node()).clear();
245 Parent::getNotifier(Node()).build();
246 Parent::getNotifier(Edge()).build();
251 /// \brief Base of the FullUGrpah.
253 /// Base of the FullUGrpah.
254 class FullUGraphBase {
259 typedef FullUGraphBase Graph;
269 ///Creates a full graph with \c n nodes.
270 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
272 /// \brief Returns the node with the given index.
274 /// Returns the node with the given index. Because it is a
275 /// static size graph the node's of the graph can be indiced
276 /// by the range from 0 to \e nodeNum()-1 and the index of
277 /// the node can accessed by the \e index() member.
278 Node operator()(int index) const { return Node(index); }
280 /// \brief Returns the index of the node.
282 /// Returns the index of the node. Because it is a
283 /// static size graph the node's of the graph can be indiced
284 /// by the range from 0 to \e nodeNum()-1 and the index of
285 /// the node can accessed by the \e index() member.
286 int index(const Node& node) const { return node.id; }
288 typedef True NodeNumTag;
289 typedef True EdgeNumTag;
292 int nodeNum() const { return _nodeNum; }
294 int edgeNum() const { return _edgeNum; }
300 int maxNodeId() const { return _nodeNum-1; }
305 int maxEdgeId() const { return _edgeNum-1; }
307 Node source(Edge e) const {
308 /// \todo we may do it faster
309 return Node(((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2);
312 Node target(Edge e) const {
313 int source = ((int)sqrt((double)(1 + 8 * e.id)) + 1) / 2;;
314 return Node(e.id - (source) * (source - 1) / 2);
320 /// The ID of a valid Node is a nonnegative integer not greater than
321 /// \ref maxNodeId(). The range of the ID's is not surely continuous
322 /// and the greatest node ID can be actually less then \ref maxNodeId().
324 /// The ID of the \ref INVALID node is -1.
325 /// \return The ID of the node \c v.
327 static int id(Node v) { return v.id; }
331 /// The ID of a valid Edge is a nonnegative integer not greater than
332 /// \ref maxEdgeId(). The range of the ID's is not surely continuous
333 /// and the greatest edge ID can be actually less then \ref maxEdgeId().
335 /// The ID of the \ref INVALID edge is -1.
336 ///\return The ID of the edge \c e.
337 static int id(Edge e) { return e.id; }
339 /// \brief Finds an edge between two nodes.
341 /// Finds an edge from node \c u to node \c v.
343 /// If \c prev is \ref INVALID (this is the default value), then
344 /// It finds the first edge from \c u to \c v. Otherwise it looks for
345 /// the next edge from \c u to \c v after \c prev.
346 /// \return The found edge or INVALID if there is no such an edge.
347 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
348 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
349 return Edge(u.id * (u.id - 1) / 2 + v.id);
352 typedef True FindEdgeTag;
356 friend class FullUGraphBase;
360 Node(int _id) { id = _id;}
363 Node (Invalid) { id = -1; }
364 bool operator==(const Node node) const {return id == node.id;}
365 bool operator!=(const Node node) const {return id != node.id;}
366 bool operator<(const Node node) const {return id < node.id;}
372 friend class FullUGraphBase;
375 int id; // _nodeNum * target + source;
377 Edge(int _id) : id(_id) {}
381 Edge (Invalid) { id = -1; }
382 bool operator==(const Edge edge) const {return id == edge.id;}
383 bool operator!=(const Edge edge) const {return id != edge.id;}
384 bool operator<(const Edge edge) const {return id < edge.id;}
387 void first(Node& node) const {
388 node.id = _nodeNum - 1;
391 static void next(Node& node) {
395 void first(Edge& edge) const {
396 edge.id = _edgeNum - 1;
399 static void next(Edge& edge) {
403 void firstOut(Edge& edge, const Node& node) const {
406 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
409 /// \todo with specialized iterators we can make faster iterating
410 void nextOut(Edge& edge) const {
411 int src = source(edge).id;
412 int trg = target(edge).id;
414 edge.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
417 void firstIn(Edge& edge, const Node& node) const {
418 int src = node.id + 1;
420 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
423 void nextIn(Edge& edge) const {
424 int src = source(edge).id;
425 int trg = target(edge).id;
427 edge.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
432 typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
433 ExtendedFullUGraphBase;
437 /// \brief An undirected full graph class.
439 /// This is a simple and fast undirected full graph implementation.
440 /// It is completely static, so you can neither add nor delete either
443 /// The main difference beetween the \e FullGraph and \e FullUGraph class
444 /// is that this class conforms to the undirected graph concept and
445 /// it does not contain the loop edges.
447 /// \sa FullUGraphBase
450 /// \author Balazs Dezso
451 class FullUGraph : public ExtendedFullUGraphBase {
454 typedef ExtendedFullUGraphBase Parent;
456 /// \brief Constructor
457 FullUGraph() { construct(0); }
459 /// \brief Constructor
460 FullUGraph(int n) { construct(n); }
462 /// \brief Resize the graph
464 /// Resize the graph. The function will fully destroy and build the graph.
465 /// This cause that the maps of the graph will reallocated
466 /// automatically and the previous values will be lost.
468 Parent::getNotifier(Edge()).clear();
469 Parent::getNotifier(UEdge()).clear();
470 Parent::getNotifier(Node()).clear();
472 Parent::getNotifier(Node()).build();
473 Parent::getNotifier(UEdge()).build();
474 Parent::getNotifier(Edge()).build();
479 class FullBpUGraphBase {
489 class NodeSetError : public LogicError {
490 virtual const char* exceptionName() const {
491 return "lemon::FullBpUGraph::NodeSetError";
496 friend class FullBpUGraphBase;
500 Node(int _id) : id(_id) {}
503 Node(Invalid) { id = -1; }
504 bool operator==(const Node i) const {return id==i.id;}
505 bool operator!=(const Node i) const {return id!=i.id;}
506 bool operator<(const Node i) const {return id<i.id;}
510 friend class FullBpUGraphBase;
514 Edge(int _id) { id = _id;}
517 Edge (Invalid) { id = -1; }
518 bool operator==(const Edge i) const {return id==i.id;}
519 bool operator!=(const Edge i) const {return id!=i.id;}
520 bool operator<(const Edge i) const {return id<i.id;}
523 void construct(int aNodeNum, int bNodeNum) {
524 _aNodeNum = aNodeNum;
525 _bNodeNum = bNodeNum;
526 _edgeNum = aNodeNum * bNodeNum;
529 void firstANode(Node& node) const {
530 node.id = 2 * _aNodeNum - 2;
531 if (node.id < 0) node.id = -1;
533 void nextANode(Node& node) const {
535 if (node.id < 0) node.id = -1;
538 void firstBNode(Node& node) const {
539 node.id = 2 * _bNodeNum - 1;
541 void nextBNode(Node& node) const {
545 void first(Node& node) const {
547 node.id = 2 * _aNodeNum - 2;
549 node.id = 2 * _bNodeNum - 1;
552 void next(Node& node) const {
555 node.id = 2 * _bNodeNum - 1;
559 void first(Edge& edge) const {
560 edge.id = _edgeNum - 1;
562 void next(Edge& edge) const {
566 void firstOut(Edge& edge, const Node& node) const {
567 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
568 edge.id = (node.id >> 1) * _bNodeNum;
570 void nextOut(Edge& edge) const {
572 if (edge.id % _bNodeNum == 0) edge.id = -1;
575 void firstIn(Edge& edge, const Node& node) const {
576 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
577 edge.id = (node.id >> 1);
579 void nextIn(Edge& edge) const {
580 edge.id += _bNodeNum;
581 if (edge.id >= _edgeNum) edge.id = -1;
584 static int id(const Node& node) {
587 static Node nodeFromId(int id) {
590 int maxNodeId() const {
591 return _aNodeNum > _bNodeNum ?
592 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
595 static int id(const Edge& edge) {
598 static Edge edgeFromId(int id) {
601 int maxEdgeId() const {
605 static int aNodeId(const Node& node) {
608 static Node fromANodeId(int id) {
609 return Node(id << 1);
611 int maxANodeId() const {
615 static int bNodeId(const Node& node) {
618 static Node fromBNodeId(int id) {
619 return Node((id << 1) + 1);
621 int maxBNodeId() const {
625 Node aNode(const Edge& edge) const {
626 return Node((edge.id / _bNodeNum) << 1);
628 Node bNode(const Edge& edge) const {
629 return Node(((edge.id % _bNodeNum) << 1) + 1);
632 static bool aNode(const Node& node) {
633 return (node.id & 1) == 0;
636 static bool bNode(const Node& node) {
637 return (node.id & 1) == 1;
640 static Node aNode(int index) {
641 return Node(index << 1);
644 static Node bNode(int index) {
645 return Node((index << 1) + 1);
651 typedef BpUGraphExtender< BpUGraphBaseExtender<
652 FullBpUGraphBase> > ExtendedFullBpUGraphBase;
657 /// \brief An undirected full bipartite graph class.
659 /// This is a simple and fast bipartite undirected full graph implementation.
660 /// It is completely static, so you can neither add nor delete either
663 /// \sa FullUGraphBase
666 /// \author Balazs Dezso
668 public ExtendedFullBpUGraphBase {
671 typedef ExtendedFullBpUGraphBase Parent;
674 Parent::construct(0, 0);
677 FullBpUGraph(int aNodeNum, int bNodeNum) {
678 Parent::construct(aNodeNum, bNodeNum);
681 /// \brief Resize the graph
683 void resize(int n, int m) {
684 Parent::getNotifier(Edge()).clear();
685 Parent::getNotifier(UEdge()).clear();
686 Parent::getNotifier(Node()).clear();
687 Parent::getNotifier(ANode()).clear();
688 Parent::getNotifier(BNode()).clear();
690 Parent::getNotifier(ANode()).build();
691 Parent::getNotifier(BNode()).build();
692 Parent::getNotifier(Node()).build();
693 Parent::getNotifier(UEdge()).build();
694 Parent::getNotifier(Edge()).build();
701 #endif //LEMON_FULL_GRAPH_H