Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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.
43 typedef FullGraphBase Graph;
52 void construct(int n) { _nodeNum = n; _edgeNum = n * n; }
56 typedef True NodeNumTag;
57 typedef True EdgeNumTag;
59 Node operator()(int ix) const { return Node(ix); }
60 int index(const Node& node) const { return node.id; }
62 Edge edge(const Node& u, const Node& v) const {
63 return Edge(*this, u.id, v.id);
66 int nodeNum() const { return _nodeNum; }
67 int edgeNum() const { return _edgeNum; }
69 int maxNodeId() const { return _nodeNum-1; }
70 int maxEdgeId() const { return _edgeNum-1; }
72 Node source(Edge e) const { return e.id % _nodeNum; }
73 Node target(Edge e) const { return e.id / _nodeNum; }
76 static int id(Node v) { return v.id; }
77 static int id(Edge e) { return e.id; }
79 static Node nodeFromId(int id) { return Node(id);}
81 static Edge edgeFromId(int id) { return Edge(id);}
83 typedef True FindEdgeTag;
85 Edge findEdge(Node u,Node v, Edge prev = INVALID) const {
86 return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
91 friend class FullGraphBase;
95 Node(int _id) : id(_id) {}
98 Node (Invalid) : id(-1) {}
99 bool operator==(const Node node) const {return id == node.id;}
100 bool operator!=(const Node node) const {return id != node.id;}
101 bool operator<(const Node node) const {return id < node.id;}
107 friend class FullGraphBase;
110 int id; // _nodeNum * target + source;
112 Edge(int _id) : id(_id) {}
114 Edge(const FullGraphBase& _graph, int source, int target)
115 : id(_graph._nodeNum * target+source) {}
118 Edge (Invalid) { id = -1; }
119 bool operator==(const Edge edge) const {return id == edge.id;}
120 bool operator!=(const Edge edge) const {return id != edge.id;}
121 bool operator<(const Edge edge) const {return id < edge.id;}
124 void first(Node& node) const {
125 node.id = _nodeNum-1;
128 static void next(Node& node) {
132 void first(Edge& e) const {
136 static void next(Edge& e) {
140 void firstOut(Edge& e, const Node& n) const {
141 e.id = _edgeNum + n.id - _nodeNum;
144 void nextOut(Edge& e) const {
146 if (e.id < 0) e.id = -1;
149 void firstIn(Edge& e, const Node& n) const {
150 e.id = n.id * _nodeNum;
153 void nextIn(Edge& e) const {
155 if (e.id % _nodeNum == 0) e.id = -1;
160 typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
164 /// \brief A full graph class.
166 /// This is a simple and fast directed full graph implementation.
167 /// It is completely static, so you can neither add nor delete either
169 /// Thus it conforms to
170 /// the \ref concepts::Graph "Graph" concept and
172 ///important extra feature that
173 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
174 /// \sa concepts::Graph.
178 /// \author Alpar Juttner
179 class FullGraph : public ExtendedFullGraphBase {
182 typedef ExtendedFullGraphBase Parent;
184 /// \brief Constructor
185 FullGraph() { construct(0); }
187 /// \brief Constructor
189 FullGraph(int n) { construct(n); }
191 /// \brief Resize the graph
193 /// Resize the graph. The function will fully destroy and build the graph.
194 /// This cause that the maps of the graph will reallocated
195 /// automatically and the previous values will be lost.
197 Parent::notifier(Edge()).clear();
198 Parent::notifier(Node()).clear();
200 Parent::notifier(Node()).build();
201 Parent::notifier(Edge()).build();
204 /// \brief Returns the node with the given index.
206 /// Returns the node with the given index. Because it is a
207 /// static size graph the node's of the graph can be indiced
208 /// by the range from 0 to \e nodeNum()-1 and the index of
209 /// the node can accessed by the \e index() member.
210 Node operator()(int ix) const { return Parent::operator()(ix); }
212 /// \brief Returns the index of the node.
214 /// Returns the index of the node. Because it is a
215 /// static size graph the node's of the graph can be indiced
216 /// by the range from 0 to \e nodeNum()-1 and the index of
217 /// the node can accessed by the \e index() member.
218 int index(const Node& node) const { return Parent::index(node); }
220 /// \brief Returns the edge connects the given nodes.
222 /// Returns the edge connects the given nodes.
223 Edge edge(const Node& u, const Node& v) const {
224 return Parent::edge(u, v);
227 /// \brief Number of nodes.
228 int nodeNum() const { return Parent::nodeNum(); }
229 /// \brief Number of edges.
230 int edgeNum() const { return Parent::edgeNum(); }
234 class FullUGraphBase {
239 typedef FullUGraphBase Graph;
248 void construct(int n) { _nodeNum = n; _edgeNum = n * (n - 1) / 2; }
253 Node operator()(int ix) const { return Node(ix); }
254 int index(const Node& node) const { return node.id; }
256 Edge edge(const Node& u, const Node& v) const {
257 return Edge(u.id * (u.id - 1) / 2 + v.id);
260 typedef True NodeNumTag;
261 typedef True EdgeNumTag;
263 int nodeNum() const { return _nodeNum; }
264 int edgeNum() const { return _edgeNum; }
266 int maxNodeId() const { return _nodeNum-1; }
267 int maxEdgeId() const { return _edgeNum-1; }
269 static Node nodeFromId(int id) { return Node(id);}
270 static Edge edgeFromId(int id) { return Edge(id);}
272 Node source(Edge e) const {
273 /// \todo we may do it faster
274 return Node((int(sqrt(double(1 + 8 * e.id)) + 1)) / 2);
277 Node target(Edge e) const {
278 int s = (int(sqrt(double(1 + 8 * e.id)) + 1)) / 2;
279 return Node(e.id - s * (s - 1) / 2);
282 static int id(Node v) { return v.id; }
283 static int id(Edge e) { return e.id; }
285 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
286 if (prev.id != -1 || u.id <= v.id) return Edge(-1);
287 return Edge(u.id * (u.id - 1) / 2 + v.id);
290 typedef True FindEdgeTag;
294 friend class FullUGraphBase;
298 Node(int _id) { id = _id;}
301 Node (Invalid) { id = -1; }
302 bool operator==(const Node node) const {return id == node.id;}
303 bool operator!=(const Node node) const {return id != node.id;}
304 bool operator<(const Node node) const {return id < node.id;}
310 friend class FullUGraphBase;
313 int id; // _nodeNum * target + source;
315 Edge(int _id) : id(_id) {}
319 Edge (Invalid) { id = -1; }
320 bool operator==(const Edge edge) const {return id == edge.id;}
321 bool operator!=(const Edge edge) const {return id != edge.id;}
322 bool operator<(const Edge edge) const {return id < edge.id;}
325 void first(Node& n) const {
329 static void next(Node& n) {
333 void first(Edge& e) const {
337 static void next(Edge& e) {
341 void firstOut(Edge& e, const Node& n) const {
344 e.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
347 /// \todo with specialized iterators we can make faster iterating
348 void nextOut(Edge& e) const {
349 int src = source(e).id;
350 int trg = target(e).id;
352 e.id = (trg < src ? src * (src - 1) / 2 + trg : -1);
355 void firstIn(Edge& e, const Node& n) const {
358 e.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
361 void nextIn(Edge& e) const {
362 int src = source(e).id;
363 int trg = target(e).id;
365 e.id = (src < _nodeNum ? src * (src - 1) / 2 + trg : -1);
370 typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
371 ExtendedFullUGraphBase;
375 /// \brief An undirected full graph class.
377 /// This is a simple and fast undirected full graph implementation.
378 /// It is completely static, so you can neither add nor delete either
381 /// The main difference beetween the \e FullGraph and \e FullUGraph class
382 /// is that this class conforms to the undirected graph concept and
383 /// it does not contain the loop edges.
386 ///important extra feature that
387 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
391 /// \author Balazs Dezso
392 class FullUGraph : public ExtendedFullUGraphBase {
395 typedef ExtendedFullUGraphBase Parent;
397 /// \brief Constructor
398 FullUGraph() { construct(0); }
400 /// \brief Constructor
401 FullUGraph(int n) { construct(n); }
403 /// \brief Resize the graph
405 /// Resize the graph. The function will fully destroy and build the graph.
406 /// This cause that the maps of the graph will reallocated
407 /// automatically and the previous values will be lost.
409 Parent::notifier(Edge()).clear();
410 Parent::notifier(UEdge()).clear();
411 Parent::notifier(Node()).clear();
413 Parent::notifier(Node()).build();
414 Parent::notifier(UEdge()).build();
415 Parent::notifier(Edge()).build();
418 /// \brief Returns the node with the given index.
420 /// Returns the node with the given index. Because it is a
421 /// static size graph the node's of the graph can be indiced
422 /// by the range from 0 to \e nodeNum()-1 and the index of
423 /// the node can accessed by the \e index() member.
424 Node operator()(int ix) const { return Parent::operator()(ix); }
426 /// \brief Returns the index of the node.
428 /// Returns the index of the node. Because it is a
429 /// static size graph the node's of the graph can be indiced
430 /// by the range from 0 to \e nodeNum()-1 and the index of
431 /// the node can accessed by the \e index() member.
432 int index(const Node& node) const { return Parent::index(node); }
434 /// \brief Number of nodes.
435 int nodeNum() const { return Parent::nodeNum(); }
436 /// \brief Number of edges.
437 int edgeNum() const { return Parent::edgeNum(); }
438 /// \brief Number of undirected edges.
439 int uEdgeNum() const { return Parent::uEdgeNum(); }
441 /// \brief Returns the edge connects the given nodes.
443 /// Returns the edge connects the given nodes.
444 Edge edge(const Node& u, const Node& v) const {
445 if (Parent::index(u) > Parent::index(v)) {
446 return Parent::direct(Parent::edge(u, v), true);
447 } else if (Parent::index(u) == Parent::index(v)) {
450 return Parent::direct(Parent::edge(v, u), false);
454 /// \brief Returns the undirected edge connects the given nodes.
456 /// Returns the undirected edge connects the given nodes.
457 UEdge uEdge(const Node& u, const Node& v) const {
458 if (Parent::index(u) > Parent::index(v)) {
459 return Parent::edge(u, v);
460 } else if (Parent::index(u) == Parent::index(v)) {
463 return Parent::edge(v, u);
469 class FullBpUGraphBase {
479 FullBpUGraphBase() {}
481 void construct(int ann, int bnn) {
484 _edgeNum = ann * bnn;
489 class NodeSetError : public LogicError {
491 virtual const char* what() const throw() {
492 return "lemon::FullBpUGraph::NodeSetError";
497 friend class FullBpUGraphBase;
501 Node(int _id) : id(_id) {}
504 Node(Invalid) { id = -1; }
505 bool operator==(const Node i) const {return id==i.id;}
506 bool operator!=(const Node i) const {return id!=i.id;}
507 bool operator<(const Node i) const {return id<i.id;}
511 friend class FullBpUGraphBase;
515 UEdge(int _id) { id = _id;}
518 UEdge (Invalid) { id = -1; }
519 bool operator==(const UEdge i) const {return id==i.id;}
520 bool operator!=(const UEdge i) const {return id!=i.id;}
521 bool operator<(const UEdge i) const {return id<i.id;}
524 Node aNode(int ix) const { return Node(ix << 1); }
525 Node bNode(int ix) const { return Node((ix << 1) + 1); }
527 int aNodeIndex(const Node& node) const { return node.id >> 1; }
528 int bNodeIndex(const Node& node) const { return node.id >> 1; }
530 UEdge uEdge(const Node& u, const Node& v) const {
531 if (((u.id ^ v.id) & 1) != 1) {
533 } else if ((u.id & 1) == 0) {
534 return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
536 return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
540 void firstANode(Node& node) const {
541 node.id = 2 * _aNodeNum - 2;
542 if (node.id < 0) node.id = -1;
544 void nextANode(Node& node) const {
546 if (node.id < 0) node.id = -1;
549 void firstBNode(Node& node) const {
550 node.id = 2 * _bNodeNum - 1;
552 void nextBNode(Node& node) const {
556 void first(Node& node) const {
558 node.id = 2 * _aNodeNum - 2;
560 node.id = 2 * _bNodeNum - 1;
563 void next(Node& node) const {
566 node.id = 2 * _bNodeNum - 1;
570 void first(UEdge& edge) const {
571 edge.id = _edgeNum - 1;
573 void next(UEdge& edge) const {
577 void firstFromANode(UEdge& edge, const Node& node) const {
578 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
579 edge.id = (node.id >> 1) * _bNodeNum;
581 void nextFromANode(UEdge& edge) const {
583 if (edge.id % _bNodeNum == 0) edge.id = -1;
586 void firstFromBNode(UEdge& edge, const Node& node) const {
587 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
588 edge.id = (node.id >> 1);
590 void nextFromBNode(UEdge& edge) const {
591 edge.id += _bNodeNum;
592 if (edge.id >= _edgeNum) edge.id = -1;
595 static int id(const Node& node) {
598 static Node nodeFromId(int id) {
601 int maxNodeId() const {
602 return _aNodeNum > _bNodeNum ?
603 _aNodeNum * 2 - 2 : _bNodeNum * 2 - 1;
606 static int id(const UEdge& edge) {
609 static UEdge uEdgeFromId(int id) {
612 int maxUEdgeId() const {
616 static int aNodeId(const Node& node) {
619 static Node nodeFromANodeId(int id) {
620 return Node(id << 1);
622 int maxANodeId() const {
626 static int bNodeId(const Node& node) {
629 static Node nodeFromBNodeId(int id) {
630 return Node((id << 1) + 1);
632 int maxBNodeId() const {
636 Node aNode(const UEdge& edge) const {
637 return Node((edge.id / _bNodeNum) << 1);
639 Node bNode(const UEdge& edge) const {
640 return Node(((edge.id % _bNodeNum) << 1) + 1);
643 static bool aNode(const Node& node) {
644 return (node.id & 1) == 0;
647 static bool bNode(const Node& node) {
648 return (node.id & 1) == 1;
652 typedef True NodeNumTag;
653 int nodeNum() const { return _aNodeNum + _bNodeNum; }
654 int aNodeNum() const { return _aNodeNum; }
655 int bNodeNum() const { return _bNodeNum; }
657 typedef True EdgeNumTag;
658 int uEdgeNum() const { return _edgeNum; }
661 typedef True FindEdgeTag;
662 UEdge findUEdge(Node u, Node v, UEdge prev = INVALID) const {
663 if (prev.id != -1 || ((u.id ^ v.id) & 1) != 1) {
665 } else if ((u.id & 1) == 0) {
666 return UEdge((u.id >> 1) * _bNodeNum + (v.id >> 1));
668 return UEdge((v.id >> 1) * _bNodeNum + (u.id >> 1));
675 typedef BpUGraphExtender<BidirBpUGraphExtender<FullBpUGraphBase> >
676 ExtendedFullBpUGraphBase;
681 /// \brief An undirected full bipartite graph class.
683 /// This is a simple and fast bipartite undirected full graph implementation.
684 /// It is completely static, so you can neither add nor delete either
687 /// \author Balazs Dezso
689 public ExtendedFullBpUGraphBase {
692 typedef ExtendedFullBpUGraphBase Parent;
695 Parent::construct(0, 0);
698 FullBpUGraph(int ann, int bnn) {
699 Parent::construct(ann, bnn);
702 /// \brief Resize the graph
705 void resize(int n, int m) {
706 Parent::notifier(Edge()).clear();
707 Parent::notifier(UEdge()).clear();
708 Parent::notifier(Node()).clear();
709 Parent::notifier(ANode()).clear();
710 Parent::notifier(BNode()).clear();
712 Parent::notifier(ANode()).build();
713 Parent::notifier(BNode()).build();
714 Parent::notifier(Node()).build();
715 Parent::notifier(UEdge()).build();
716 Parent::notifier(Edge()).build();
719 /// \brief Number of nodes.
720 int nodeNum() const { return Parent::nodeNum(); }
721 /// \brief Number of A-nodes.
722 int aNodeNum() const { return Parent::aNodeNum(); }
723 /// \brief Number of B-nodes.
724 int bNodeNum() const { return Parent::bNodeNum(); }
725 /// \brief Number of edges.
726 int edgeNum() const { return Parent::edgeNum(); }
727 /// \brief Number of undirected edges.
728 int uEdgeNum() const { return Parent::uEdgeNum(); }
734 /// \brief Returns the A-node with the given index.
736 /// Returns the A-node with the given index. Because it is a
737 /// static size graph the node's of the graph can be indiced
738 /// by the range from 0 to \e aNodeNum()-1 and the index of
739 /// the node can accessed by the \e aNodeIndex() member.
740 Node aNode(int ix) const { return Parent::aNode(ix); }
742 /// \brief Returns the B-node with the given index.
744 /// Returns the B-node with the given index. Because it is a
745 /// static size graph the node's of the graph can be indiced
746 /// by the range from 0 to \e bNodeNum()-1 and the index of
747 /// the node can accessed by the \e bNodeIndex() member.
748 Node bNode(int ix) const { return Parent::bNode(ix); }
750 /// \brief Returns the index of the A-node.
752 /// Returns the index of the A-node. Because it is a
753 /// static size graph the node's of the graph can be indiced
754 /// by the range from 0 to \e aNodeNum()-1 and the index of
755 /// the node can accessed by the \e aNodeIndex() member.
756 int aNodeIndex(const Node& node) const { return Parent::aNodeIndex(node); }
758 /// \brief Returns the index of the B-node.
760 /// Returns the index of the B-node. Because it is a
761 /// static size graph the node's of the graph can be indiced
762 /// by the range from 0 to \e bNodeNum()-1 and the index of
763 /// the node can accessed by the \e bNodeIndex() member.
764 int bNodeIndex(const Node& node) const { return Parent::bNodeIndex(node); }
766 /// \brief Returns the edge connects the given nodes.
768 /// Returns the edge connects the given nodes.
769 Edge edge(const Node& u, const Node& v) const {
770 UEdge uedge = Parent::uEdge(u, v);
771 if (uedge != INVALID) {
772 return Parent::direct(uedge, Parent::aNode(u));
778 /// \brief Returns the undirected edge connects the given nodes.
780 /// Returns the undirected edge connects the given nodes.
781 UEdge uEdge(const Node& u, const Node& v) const {
782 return Parent::uEdge(u, v);
789 #endif //LEMON_FULL_GRAPH_H