Better handling of inexact computation.
We do not use tolerance for excess, just for edges
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_SMART_GRAPH_H
20 #define LEMON_SMART_GRAPH_H
24 ///\brief SmartGraph and SmartUGraph classes.
28 #include <lemon/bits/invalid.h>
30 #include <lemon/bits/base_extender.h>
31 #include <lemon/bits/graph_extender.h>
33 #include <lemon/bits/utility.h>
34 #include <lemon/error.h>
36 #include <lemon/bits/graph_extender.h>
45 class SmartGraphBase {
50 int first_in, first_out;
55 int target, source, next_in, next_out;
59 std::vector<NodeT> nodes;
61 std::vector<EdgeT> edges;
66 typedef SmartGraphBase Graph;
74 SmartGraphBase() : nodes(), edges() { }
75 SmartGraphBase(const SmartGraphBase &_g)
76 : nodes(_g.nodes), edges(_g.edges) { }
78 typedef True NodeNumTag;
79 typedef True EdgeNumTag;
81 int nodeNum() const { return nodes.size(); }
82 int edgeNum() const { return edges.size(); }
84 int maxNodeId() const { return nodes.size()-1; }
85 int maxEdgeId() const { return edges.size()-1; }
89 nodes.push_back(NodeT());
90 nodes[n].first_in = -1;
91 nodes[n].first_out = -1;
95 Edge addEdge(Node u, Node v) {
97 edges.push_back(EdgeT());
98 edges[n].source = u.id;
99 edges[n].target = v.id;
100 edges[n].next_out = nodes[u.id].first_out;
101 edges[n].next_in = nodes[v.id].first_in;
102 nodes[u.id].first_out = nodes[v.id].first_in = n;
112 Node source(Edge e) const { return Node(edges[e.id].source); }
113 Node target(Edge e) const { return Node(edges[e.id].target); }
115 static int id(Node v) { return v.id; }
116 static int id(Edge e) { return e.id; }
118 static Node nodeFromId(int id) { return Node(id);}
119 static Edge edgeFromId(int id) { return Edge(id);}
122 friend class SmartGraphBase;
123 friend class SmartGraph;
127 explicit Node(int _id) : id(_id) {}
130 Node (Invalid) : id(-1) {}
131 bool operator==(const Node i) const {return id == i.id;}
132 bool operator!=(const Node i) const {return id != i.id;}
133 bool operator<(const Node i) const {return id < i.id;}
138 friend class SmartGraphBase;
139 friend class SmartGraph;
143 explicit Edge(int _id) : id(_id) {}
146 Edge (Invalid) : id(-1) {}
147 bool operator==(const Edge i) const {return id == i.id;}
148 bool operator!=(const Edge i) const {return id != i.id;}
149 bool operator<(const Edge i) const {return id < i.id;}
152 void first(Node& node) const {
153 node.id = nodes.size() - 1;
156 static void next(Node& node) {
160 void first(Edge& edge) const {
161 edge.id = edges.size() - 1;
164 static void next(Edge& edge) {
168 void firstOut(Edge& edge, const Node& node) const {
169 edge.id = nodes[node.id].first_out;
172 void nextOut(Edge& edge) const {
173 edge.id = edges[edge.id].next_out;
176 void firstIn(Edge& edge, const Node& node) const {
177 edge.id = nodes[node.id].first_in;
180 void nextIn(Edge& edge) const {
181 edge.id = edges[edge.id].next_in;
186 typedef GraphExtender<SmartGraphBase> ExtendedSmartGraphBase;
190 ///A smart graph class.
192 ///This is a simple and fast graph implementation.
193 ///It is also quite memory efficient, but at the price
194 ///that <b> it does support only limited (only stack-like)
195 ///node and edge deletions</b>.
197 ///the \ref concepts::Graph "Graph concept" with an
198 ///important extra feature that
199 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
201 ///\sa concepts::Graph.
203 ///\author Alpar Juttner
204 class SmartGraph : public ExtendedSmartGraphBase {
207 typedef ExtendedSmartGraphBase Parent;
211 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
213 ///SmartGraph is \e not copy constructible. Use GraphCopy() instead.
215 SmartGraph(const SmartGraph &) : ExtendedSmartGraphBase() {};
216 ///\brief Assignment of SmartGraph to another one is \e not allowed.
217 ///Use GraphCopy() instead.
219 ///Assignment of SmartGraph to another one is \e not allowed.
220 ///Use GraphCopy() instead.
221 void operator=(const SmartGraph &) {}
231 ///Add a new node to the graph.
233 /// \return the new node.
235 Node addNode() { return Parent::addNode(); }
237 ///Add a new edge to the graph.
239 ///Add a new edge to the graph with source node \c s
240 ///and target node \c t.
241 ///\return the new edge.
242 Edge addEdge(const Node& s, const Node& t) {
243 return Parent::addEdge(s, t);
248 ///Erase all the nodes and edges from the graph.
256 ///This function splits a node. First a new node is added to the graph,
257 ///then the source of each outgoing edge of \c n is moved to this new node.
258 ///If \c connect is \c true (this is the default value), then a new edge
259 ///from \c n to the newly created node is also added.
260 ///\return The newly created node.
262 ///\note The <tt>Edge</tt>s
263 ///referencing a moved edge remain
264 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
265 ///may be invalidated.
266 ///\warning This functionality cannot be used together with the Snapshot
268 ///\todo It could be implemented in a bit faster way.
269 Node split(Node n, bool connect = true)
272 nodes[b.id].first_out=nodes[n.id].first_out;
273 nodes[n.id].first_out=-1;
274 for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
275 if(connect) addEdge(n,b);
285 void restoreSnapshot(const Snapshot &s)
287 while(s.edge_num<edges.size()) {
288 Edge edge = edgeFromId(edges.size()-1);
289 Parent::getNotifier(Edge()).erase(edge);
290 nodes[edges.back().source].first_out=edges.back().next_out;
291 nodes[edges.back().target].first_in=edges.back().next_in;
294 while(s.node_num<nodes.size()) {
295 Node node = nodeFromId(nodes.size()-1);
296 Parent::getNotifier(Node()).erase(node);
303 ///Class to make a snapshot of the graph and to restrore to it later.
305 ///Class to make a snapshot of the graph and to restrore to it later.
307 ///The newly added nodes and edges can be removed using the
308 ///restore() function.
309 ///\note After you restore a state, you cannot restore
310 ///a later state, in other word you cannot add again the edges deleted
311 ///by restore() using another one Snapshot instance.
313 ///\warning If you do not use correctly the snapshot that can cause
314 ///either broken program, invalid state of the graph, valid but
315 ///not the restored graph or no change. Because the runtime performance
316 ///the validity of the snapshot is not stored.
321 friend class SmartGraph;
322 unsigned int node_num;
323 unsigned int edge_num;
325 ///Default constructor.
327 ///Default constructor.
328 ///To actually make a snapshot you must call save().
331 ///Constructor that immediately makes a snapshot
333 ///This constructor immediately makes a snapshot of the graph.
334 ///\param _g The graph we make a snapshot of.
335 Snapshot(SmartGraph &_g) :g(&_g) {
336 node_num=g->nodes.size();
337 edge_num=g->edges.size();
342 ///Make a snapshot of the graph.
344 ///This function can be called more than once. In case of a repeated
345 ///call, the previous snapshot gets lost.
346 ///\param _g The graph we make the snapshot of.
347 void save(SmartGraph &_g)
350 node_num=g->nodes.size();
351 edge_num=g->edges.size();
354 ///Undo the changes until a snapshot.
356 ///Undo the changes until a snapshot created by save().
358 ///\note After you restored a state, you cannot restore
359 ///a later state, in other word you cannot add again the edges deleted
363 g->restoreSnapshot(*this);
369 /**************** Undirected List Graph ****************/
371 typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
372 ExtendedSmartUGraphBase;
376 /// \brief A smart undirected graph class.
378 /// This is a simple and fast undirected graph implementation.
379 /// It is also quite memory efficient, but at the price
380 /// that <b> it does support only limited (only stack-like)
381 /// node and edge deletions</b>.
382 /// Except from this it conforms to
383 /// the \ref concepts::UGraph "UGraph concept".
386 ///important extra feature that
387 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
389 /// \sa concepts::UGraph.
391 class SmartUGraph : public ExtendedSmartUGraphBase {
394 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
396 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
398 SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
400 ///\brief Assignment of SmartUGraph to another one is \e not allowed.
401 ///Use UGraphCopy() instead.
403 ///Assignment of SmartUGraph to another one is \e not allowed.
404 ///Use UGraphCopy() instead.
405 void operator=(const SmartUGraph &) {}
409 typedef ExtendedSmartUGraphBase Parent;
417 ///Add a new node to the graph.
419 /// \return the new node.
421 Node addNode() { return Parent::addNode(); }
423 ///Add a new undirected edge to the graph.
425 ///Add a new undirected edge to the graph with node \c s
427 ///\return the new undirected edge.
428 UEdge addEdge(const Node& s, const Node& t) {
429 return Parent::addEdge(s, t);
434 ///Erase all the nodes and edges from the graph.
447 void restoreSnapshot(const Snapshot &s)
449 while(s.edge_num<edges.size()) {
450 UEdge edge = uEdgeFromId(edges.size()-1);
451 Parent::getNotifier(UEdge()).erase(edge);
452 std::vector<Edge> dir;
453 dir.push_back(Parent::direct(edge, true));
454 dir.push_back(Parent::direct(edge, false));
455 Parent::getNotifier(Edge()).erase(dir);
456 nodes[edges.back().source].first_out=edges.back().next_out;
457 nodes[edges.back().target].first_in=edges.back().next_in;
460 while(s.node_num<nodes.size()) {
461 Node node = nodeFromId(nodes.size()-1);
462 Parent::getNotifier(Node()).erase(node);
469 ///Class to make a snapshot of the graph and to restrore to it later.
471 ///Class to make a snapshot of the graph and to restrore to it later.
473 ///The newly added nodes and edges can be removed using the
474 ///restore() function.
476 ///\note After you restore a state, you cannot restore
477 ///a later state, in other word you cannot add again the edges deleted
478 ///by restore() using another one Snapshot instance.
480 ///\warning If you do not use correctly the snapshot that can cause
481 ///either broken program, invalid state of the graph, valid but
482 ///not the restored graph or no change. Because the runtime performance
483 ///the validity of the snapshot is not stored.
488 friend class SmartUGraph;
489 unsigned int node_num;
490 unsigned int edge_num;
492 ///Default constructor.
494 ///Default constructor.
495 ///To actually make a snapshot you must call save().
498 ///Constructor that immediately makes a snapshot
500 ///This constructor immediately makes a snapshot of the graph.
501 ///\param _g The graph we make a snapshot of.
502 Snapshot(SmartUGraph &_g) :g(&_g) {
503 node_num=g->nodes.size();
504 edge_num=g->edges.size();
509 ///Make a snapshot of the graph.
511 ///This function can be called more than once. In case of a repeated
512 ///call, the previous snapshot gets lost.
513 ///\param _g The graph we make the snapshot of.
514 void save(SmartUGraph &_g)
517 node_num=g->nodes.size();
518 edge_num=g->edges.size();
521 ///Undo the changes until a snapshot.
523 ///Undo the changes until a snapshot created by save().
525 ///\note After you restored a state, you cannot restore
526 ///a later state, in other word you cannot add again the edges deleted
530 g->restoreSnapshot(*this);
536 class SmartBpUGraphBase {
539 class NodeSetError : public LogicError {
541 virtual const char* what() const throw() {
542 return "lemon::SmartBpUGraph::NodeSetError";
551 NodeT(int _first) : first(_first) {}
559 std::vector<NodeT> aNodes;
560 std::vector<NodeT> bNodes;
562 std::vector<UEdgeT> edges;
567 friend class SmartBpUGraphBase;
571 explicit Node(int _id) : id(_id) {}
574 Node(Invalid) : id(-1) {}
575 bool operator==(const Node i) const {return id==i.id;}
576 bool operator!=(const Node i) const {return id!=i.id;}
577 bool operator<(const Node i) const {return id<i.id;}
581 friend class SmartBpUGraphBase;
585 UEdge(int _id) : id(_id) {}
588 UEdge(Invalid) : id(-1) {}
589 bool operator==(const UEdge i) const {return id==i.id;}
590 bool operator!=(const UEdge i) const {return id!=i.id;}
591 bool operator<(const UEdge i) const {return id<i.id;}
594 void firstANode(Node& node) const {
595 node.id = 2 * aNodes.size() - 2;
596 if (node.id < 0) node.id = -1;
598 void nextANode(Node& node) const {
600 if (node.id < 0) node.id = -1;
603 void firstBNode(Node& node) const {
604 node.id = 2 * bNodes.size() - 1;
606 void nextBNode(Node& node) const {
610 void first(Node& node) const {
611 if (aNodes.size() > 0) {
612 node.id = 2 * aNodes.size() - 2;
614 node.id = 2 * bNodes.size() - 1;
617 void next(Node& node) const {
620 node.id = 2 * bNodes.size() - 1;
624 void first(UEdge& edge) const {
625 edge.id = edges.size() - 1;
627 void next(UEdge& edge) const {
631 void firstFromANode(UEdge& edge, const Node& node) const {
632 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
633 edge.id = aNodes[node.id >> 1].first;
635 void nextFromANode(UEdge& edge) const {
636 edge.id = edges[edge.id].next_out;
639 void firstFromBNode(UEdge& edge, const Node& node) const {
640 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
641 edge.id = bNodes[node.id >> 1].first;
643 void nextFromBNode(UEdge& edge) const {
644 edge.id = edges[edge.id].next_in;
647 static int id(const Node& node) {
650 static Node nodeFromId(int id) {
653 int maxNodeId() const {
654 return aNodes.size() > bNodes.size() ?
655 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
658 static int id(const UEdge& edge) {
661 static UEdge uEdgeFromId(int id) {
664 int maxUEdgeId() const {
668 static int aNodeId(const Node& node) {
671 static Node nodeFromANodeId(int id) {
672 return Node(id << 1);
674 int maxANodeId() const {
675 return aNodes.size();
678 static int bNodeId(const Node& node) {
681 static Node nodeFromBNodeId(int id) {
682 return Node((id << 1) + 1);
684 int maxBNodeId() const {
685 return bNodes.size();
688 Node aNode(const UEdge& edge) const {
689 return Node(edges[edge.id].aNode);
691 Node bNode(const UEdge& edge) const {
692 return Node(edges[edge.id].bNode);
695 static bool aNode(const Node& node) {
696 return (node.id & 1) == 0;
699 static bool bNode(const Node& node) {
700 return (node.id & 1) == 1;
706 aNodes.push_back(nodeT);
707 return Node(aNodes.size() * 2 - 2);
713 bNodes.push_back(nodeT);
714 return Node(bNodes.size() * 2 - 1);
717 UEdge addEdge(const Node& source, const Node& target) {
718 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
720 if ((source.id & 1) == 0) {
721 edgeT.aNode = source.id;
722 edgeT.bNode = target.id;
724 edgeT.aNode = target.id;
725 edgeT.bNode = source.id;
727 edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
728 aNodes[edgeT.aNode >> 1].first = edges.size();
729 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
730 bNodes[edgeT.bNode >> 1].first = edges.size();
731 edges.push_back(edgeT);
732 return UEdge(edges.size() - 1);
741 typedef True NodeNumTag;
742 int nodeNum() const { return aNodes.size() + bNodes.size(); }
743 int aNodeNum() const { return aNodes.size(); }
744 int bNodeNum() const { return bNodes.size(); }
746 typedef True EdgeNumTag;
747 int uEdgeNum() const { return edges.size(); }
752 typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
753 ExtendedSmartBpUGraphBase;
757 /// \brief A smart bipartite undirected graph class.
759 /// This is a simple and fast bipartite undirected graph implementation.
760 /// It is also quite memory efficient, but at the price
761 /// that <b> it does not support node and edge deletions</b>.
762 /// Except from this it conforms to
763 /// the \ref concepts::BpUGraph "BpUGraph concept".
766 ///important extra feature that
767 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
769 /// \sa concepts::BpUGraph.
771 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
774 /// \brief SmartBpUGraph is \e not copy constructible.
776 ///SmartBpUGraph is \e not copy constructible.
777 SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
779 /// \brief Assignment of SmartBpUGraph to another one is \e not
782 /// Assignment of SmartBpUGraph to another one is \e not allowed.
783 void operator=(const SmartBpUGraph &) {}
787 typedef ExtendedSmartBpUGraphBase Parent;
793 SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
795 ///Add a new ANode to the graph.
797 /// \return the new node.
799 Node addANode() { return Parent::addANode(); }
801 ///Add a new BNode to the graph.
803 /// \return the new node.
805 Node addBNode() { return Parent::addBNode(); }
807 ///Add a new undirected edge to the graph.
809 ///Add a new undirected edge to the graph with node \c s
811 ///\return the new undirected edge.
812 UEdge addEdge(const Node& s, const Node& t) {
813 return Parent::addEdge(s, t);
818 ///Erase all the nodes and edges from the graph.
830 void restoreSnapshot(const Snapshot &s)
832 while(s.edge_num<edges.size()) {
833 UEdge edge = uEdgeFromId(edges.size()-1);
834 Parent::getNotifier(UEdge()).erase(edge);
835 std::vector<Edge> dir;
836 dir.push_back(Parent::direct(edge, true));
837 dir.push_back(Parent::direct(edge, false));
838 Parent::getNotifier(Edge()).erase(dir);
839 aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
840 bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
843 while(s.anode_num<aNodes.size()) {
844 Node node = nodeFromANodeId(aNodes.size() - 1);
845 Parent::getNotifier(ANode()).erase(node);
846 Parent::getNotifier(Node()).erase(node);
849 while(s.bnode_num<bNodes.size()) {
850 Node node = nodeFromBNodeId(bNodes.size() - 1);
851 Parent::getNotifier(BNode()).erase(node);
852 Parent::getNotifier(Node()).erase(node);
859 ///Class to make a snapshot of the graph and to restrore to it later.
861 ///Class to make a snapshot of the graph and to restrore to it later.
863 ///The newly added nodes and edges can be removed using the
864 ///restore() function.
866 ///\note After you restore a state, you cannot restore
867 ///a later state, in other word you cannot add again the edges deleted
868 ///by restore() using another one Snapshot instance.
870 ///\warning If you do not use correctly the snapshot that can cause
871 ///either broken program, invalid state of the graph, valid but
872 ///not the restored graph or no change. Because the runtime performance
873 ///the validity of the snapshot is not stored.
878 friend class SmartBpUGraph;
879 unsigned int anode_num;
880 unsigned int bnode_num;
881 unsigned int edge_num;
883 ///Default constructor.
885 ///Default constructor.
886 ///To actually make a snapshot you must call save().
890 ///Constructor that immediately makes a snapshot
892 ///This constructor immediately makes a snapshot of the graph.
893 ///\param _g The graph we make a snapshot of.
894 Snapshot(SmartBpUGraph &_g) : g(&_g) {
895 anode_num=g->aNodes.size();
896 bnode_num=g->bNodes.size();
897 edge_num=g->edges.size();
902 ///Make a snapshot of the graph.
904 ///This function can be called more than once. In case of a repeated
905 ///call, the previous snapshot gets lost.
906 ///\param _g The graph we make the snapshot of.
907 void save(SmartBpUGraph &_g)
910 anode_num=g->aNodes.size();
911 bnode_num=g->bNodes.size();
912 edge_num=g->edges.size();
915 ///Undo the changes until a snapshot.
917 ///Undo the changes until a snapshot created by save().
919 ///\note After you restored a state, you cannot restore
920 ///a later state, in other word you cannot add again the edges deleted
924 g->restoreSnapshot(*this);
934 #endif //LEMON_SMART_GRAPH_H