Revert to long long int since currently I don't know a better solution.
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_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 ///\brief 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);
246 /// \brief Using this it is possible to avoid the superfluous memory
249 /// Using this it is possible to avoid the superfluous memory
250 /// allocation: if you know that the graph you want to build will
251 /// be very large (e.g. it will contain millions of nodes and/or edges)
252 /// then it is worth reserving space for this amount before starting
253 /// to build the graph.
255 void reserveNode(int n) { nodes.reserve(n); };
257 /// \brief Using this it is possible to avoid the superfluous memory
260 /// Using this it is possible to avoid the superfluous memory
261 /// allocation: if you know that the graph you want to build will
262 /// be very large (e.g. it will contain millions of nodes and/or edges)
263 /// then it is worth reserving space for this amount before starting
264 /// to build the graph.
266 void reserveEdge(int m) { edges.reserve(m); };
270 ///Erase all the nodes and edges from the graph.
278 ///This function splits a node. First a new node is added to the graph,
279 ///then the source of each outgoing edge of \c n is moved to this new node.
280 ///If \c connect is \c true (this is the default value), then a new edge
281 ///from \c n to the newly created node is also added.
282 ///\return The newly created node.
284 ///\note The <tt>Edge</tt>s
285 ///referencing a moved edge remain
286 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
287 ///may be invalidated.
288 ///\warning This functionality cannot be used together with the Snapshot
290 ///\todo It could be implemented in a bit faster way.
291 Node split(Node n, bool connect = true)
294 nodes[b.id].first_out=nodes[n.id].first_out;
295 nodes[n.id].first_out=-1;
296 for(int i=nodes[b.id].first_out;i!=-1;i++) edges[i].source=b.id;
297 if(connect) addEdge(n,b);
307 void restoreSnapshot(const Snapshot &s)
309 while(s.edge_num<edges.size()) {
310 Edge edge = edgeFromId(edges.size()-1);
311 Parent::notifier(Edge()).erase(edge);
312 nodes[edges.back().source].first_out=edges.back().next_out;
313 nodes[edges.back().target].first_in=edges.back().next_in;
316 while(s.node_num<nodes.size()) {
317 Node node = nodeFromId(nodes.size()-1);
318 Parent::notifier(Node()).erase(node);
325 ///Class to make a snapshot of the graph and to restrore to it later.
327 ///Class to make a snapshot of the graph and to restrore to it later.
329 ///The newly added nodes and edges can be removed using the
330 ///restore() function.
331 ///\note After you restore a state, you cannot restore
332 ///a later state, in other word you cannot add again the edges deleted
333 ///by restore() using another one Snapshot instance.
335 ///\warning If you do not use correctly the snapshot that can cause
336 ///either broken program, invalid state of the graph, valid but
337 ///not the restored graph or no change. Because the runtime performance
338 ///the validity of the snapshot is not stored.
343 friend class SmartGraph;
344 unsigned int node_num;
345 unsigned int edge_num;
347 ///Default constructor.
349 ///Default constructor.
350 ///To actually make a snapshot you must call save().
353 ///Constructor that immediately makes a snapshot
355 ///This constructor immediately makes a snapshot of the graph.
356 ///\param _g The graph we make a snapshot of.
357 Snapshot(SmartGraph &_g) :g(&_g) {
358 node_num=g->nodes.size();
359 edge_num=g->edges.size();
364 ///Make a snapshot of the graph.
366 ///This function can be called more than once. In case of a repeated
367 ///call, the previous snapshot gets lost.
368 ///\param _g The graph we make the snapshot of.
369 void save(SmartGraph &_g)
372 node_num=g->nodes.size();
373 edge_num=g->edges.size();
376 ///Undo the changes until a snapshot.
378 ///Undo the changes until a snapshot created by save().
380 ///\note After you restored a state, you cannot restore
381 ///a later state, in other word you cannot add again the edges deleted
385 g->restoreSnapshot(*this);
391 class SmartUGraphBase {
404 std::vector<NodeT> nodes;
405 std::vector<EdgeT> edges;
411 typedef SmartUGraphBase Graph;
418 friend class SmartUGraphBase;
422 explicit Node(int pid) { id = pid;}
426 Node (Invalid) { id = -1; }
427 bool operator==(const Node& node) const {return id == node.id;}
428 bool operator!=(const Node& node) const {return id != node.id;}
429 bool operator<(const Node& node) const {return id < node.id;}
433 friend class SmartUGraphBase;
437 explicit UEdge(int pid) { id = pid;}
441 UEdge (Invalid) { id = -1; }
442 bool operator==(const UEdge& edge) const {return id == edge.id;}
443 bool operator!=(const UEdge& edge) const {return id != edge.id;}
444 bool operator<(const UEdge& edge) const {return id < edge.id;}
448 friend class SmartUGraphBase;
452 explicit Edge(int pid) { id = pid;}
455 operator UEdge() const { return uEdgeFromId(id / 2); }
458 Edge (Invalid) { id = -1; }
459 bool operator==(const Edge& edge) const {return id == edge.id;}
460 bool operator!=(const Edge& edge) const {return id != edge.id;}
461 bool operator<(const Edge& edge) const {return id < edge.id;}
467 : nodes(), edges() {}
470 int maxNodeId() const { return nodes.size()-1; }
471 int maxUEdgeId() const { return edges.size() / 2 - 1; }
472 int maxEdgeId() const { return edges.size()-1; }
474 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
475 Node target(Edge e) const { return Node(edges[e.id].target); }
477 Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
478 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
480 static bool direction(Edge e) {
481 return (e.id & 1) == 1;
484 static Edge direct(UEdge e, bool d) {
485 return Edge(e.id * 2 + (d ? 1 : 0));
488 void first(Node& node) const {
489 node.id = nodes.size() - 1;
492 void next(Node& node) const {
496 void first(Edge& edge) const {
497 edge.id = edges.size() - 1;
500 void next(Edge& edge) const {
504 void first(UEdge& edge) const {
505 edge.id = edges.size() / 2 - 1;
508 void next(UEdge& edge) const {
512 void firstOut(Edge &edge, const Node& v) const {
513 edge.id = nodes[v.id].first_out;
515 void nextOut(Edge &edge) const {
516 edge.id = edges[edge.id].next_out;
519 void firstIn(Edge &edge, const Node& v) const {
520 edge.id = ((nodes[v.id].first_out) ^ 1);
521 if (edge.id == -2) edge.id = -1;
523 void nextIn(Edge &edge) const {
524 edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
525 if (edge.id == -2) edge.id = -1;
528 void firstInc(UEdge &edge, bool& d, const Node& v) const {
529 int de = nodes[v.id].first_out;
538 void nextInc(UEdge &edge, bool& d) const {
539 int de = (edges[(edge.id * 2) | (d ? 1 : 0)].next_out);
549 static int id(Node v) { return v.id; }
550 static int id(Edge e) { return e.id; }
551 static int id(UEdge e) { return e.id; }
553 static Node nodeFromId(int id) { return Node(id);}
554 static Edge edgeFromId(int id) { return Edge(id);}
555 static UEdge uEdgeFromId(int id) { return UEdge(id);}
558 int n = nodes.size();
559 nodes.push_back(NodeT());
560 nodes[n].first_out = -1;
565 UEdge addEdge(Node u, Node v) {
566 int n = edges.size();
567 edges.push_back(EdgeT());
568 edges.push_back(EdgeT());
570 edges[n].target = u.id;
571 edges[n | 1].target = v.id;
573 edges[n].next_out = nodes[v.id].first_out;
574 nodes[v.id].first_out = n;
576 edges[n | 1].next_out = nodes[u.id].first_out;
577 nodes[u.id].first_out = (n | 1);
589 typedef UGraphExtender<SmartUGraphBase> ExtendedSmartUGraphBase;
593 /// \brief A smart undirected graph class.
595 /// This is a simple and fast undirected graph implementation.
596 /// It is also quite memory efficient, but at the price
597 /// that <b> it does support only limited (only stack-like)
598 /// node and edge deletions</b>.
599 /// Except from this it conforms to
600 /// the \ref concepts::UGraph "UGraph concept".
603 ///important extra feature that
604 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
606 /// \sa concepts::UGraph.
608 class SmartUGraph : public ExtendedSmartUGraphBase {
611 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
613 ///SmartUGraph is \e not copy constructible. Use UGraphCopy() instead.
615 SmartUGraph(const SmartUGraph &) : ExtendedSmartUGraphBase() {};
617 ///\brief Assignment of SmartUGraph to another one is \e not allowed.
618 ///Use UGraphCopy() instead.
620 ///Assignment of SmartUGraph to another one is \e not allowed.
621 ///Use UGraphCopy() instead.
622 void operator=(const SmartUGraph &) {}
626 typedef ExtendedSmartUGraphBase Parent;
627 typedef Parent::OutEdgeIt IncEdgeIt;
635 ///Add a new node to the graph.
637 /// \return the new node.
639 Node addNode() { return Parent::addNode(); }
641 ///Add a new undirected edge to the graph.
643 ///Add a new undirected edge to the graph with node \c s
645 ///\return the new undirected edge.
646 UEdge addEdge(const Node& s, const Node& t) {
647 return Parent::addEdge(s, t);
652 ///Erase all the nodes and edges from the graph.
664 void saveSnapshot(Snapshot &s)
667 s.node_num = nodes.size();
668 s.edge_num = edges.size();
671 void restoreSnapshot(const Snapshot &s)
673 while(s.edge_num<edges.size()) {
674 int n=edges.size()-1;
675 UEdge edge=uEdgeFromId(n/2);
676 Parent::notifier(UEdge()).erase(edge);
677 std::vector<Edge> dir;
678 dir.push_back(edgeFromId(n));
679 dir.push_back(edgeFromId(n-1));
680 Parent::notifier(Edge()).erase(dir);
681 nodes[edges[n].target].first_out=edges[n].next_out;
682 nodes[edges[n-1].target].first_out=edges[n-1].next_out;
686 while(s.node_num<nodes.size()) {
687 int n=nodes.size()-1;
688 Node node = nodeFromId(n);
689 Parent::notifier(Node()).erase(node);
696 ///Class to make a snapshot of the graph and to restrore to it later.
698 ///Class to make a snapshot of the graph and to restrore to it later.
700 ///The newly added nodes and edges can be removed using the
701 ///restore() function.
703 ///\note After you restore a state, you cannot restore
704 ///a later state, in other word you cannot add again the edges deleted
705 ///by restore() using another one Snapshot instance.
707 ///\warning If you do not use correctly the snapshot that can cause
708 ///either broken program, invalid state of the graph, valid but
709 ///not the restored graph or no change. Because the runtime performance
710 ///the validity of the snapshot is not stored.
715 friend class SmartUGraph;
716 unsigned int node_num;
717 unsigned int edge_num;
719 ///Default constructor.
721 ///Default constructor.
722 ///To actually make a snapshot you must call save().
724 Snapshot() : graph(0) {}
725 ///Constructor that immediately makes a snapshot
727 ///This constructor immediately makes a snapshot of the graph.
728 ///\param g The graph we make a snapshot of.
729 Snapshot(SmartUGraph &g) {
730 g.saveSnapshot(*this);
735 ///Make a snapshot of the graph.
737 ///This function can be called more than once. In case of a repeated
738 ///call, the previous snapshot gets lost.
739 ///\param g The graph we make the snapshot of.
740 void save(SmartUGraph &g)
742 g.saveSnapshot(*this);
745 ///Undo the changes until a snapshot.
747 ///Undo the changes until a snapshot created by save().
749 ///\note After you restored a state, you cannot restore
750 ///a later state, in other word you cannot add again the edges deleted
754 graph->restoreSnapshot(*this);
760 class SmartBpUGraphBase {
763 class NodeSetError : public LogicError {
765 virtual const char* what() const throw() {
766 return "lemon::SmartBpUGraph::NodeSetError";
775 NodeT(int _first) : first(_first) {}
783 std::vector<NodeT> aNodes;
784 std::vector<NodeT> bNodes;
786 std::vector<UEdgeT> edges;
791 friend class SmartBpUGraphBase;
795 explicit Node(int _id) : id(_id) {}
798 Node(Invalid) : id(-1) {}
799 bool operator==(const Node i) const {return id==i.id;}
800 bool operator!=(const Node i) const {return id!=i.id;}
801 bool operator<(const Node i) const {return id<i.id;}
805 friend class SmartBpUGraphBase;
809 UEdge(int _id) : id(_id) {}
812 UEdge(Invalid) : id(-1) {}
813 bool operator==(const UEdge i) const {return id==i.id;}
814 bool operator!=(const UEdge i) const {return id!=i.id;}
815 bool operator<(const UEdge i) const {return id<i.id;}
818 void firstANode(Node& node) const {
819 node.id = 2 * aNodes.size() - 2;
820 if (node.id < 0) node.id = -1;
822 void nextANode(Node& node) const {
824 if (node.id < 0) node.id = -1;
827 void firstBNode(Node& node) const {
828 node.id = 2 * bNodes.size() - 1;
830 void nextBNode(Node& node) const {
834 void first(Node& node) const {
835 if (aNodes.size() > 0) {
836 node.id = 2 * aNodes.size() - 2;
838 node.id = 2 * bNodes.size() - 1;
841 void next(Node& node) const {
844 node.id = 2 * bNodes.size() - 1;
848 void first(UEdge& edge) const {
849 edge.id = edges.size() - 1;
851 void next(UEdge& edge) const {
855 void firstFromANode(UEdge& edge, const Node& node) const {
856 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
857 edge.id = aNodes[node.id >> 1].first;
859 void nextFromANode(UEdge& edge) const {
860 edge.id = edges[edge.id].next_out;
863 void firstFromBNode(UEdge& edge, const Node& node) const {
864 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
865 edge.id = bNodes[node.id >> 1].first;
867 void nextFromBNode(UEdge& edge) const {
868 edge.id = edges[edge.id].next_in;
871 static int id(const Node& node) {
874 static Node nodeFromId(int id) {
877 int maxNodeId() const {
878 return aNodes.size() > bNodes.size() ?
879 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
882 static int id(const UEdge& edge) {
885 static UEdge uEdgeFromId(int id) {
888 int maxUEdgeId() const {
892 static int aNodeId(const Node& node) {
895 static Node nodeFromANodeId(int id) {
896 return Node(id << 1);
898 int maxANodeId() const {
899 return aNodes.size();
902 static int bNodeId(const Node& node) {
905 static Node nodeFromBNodeId(int id) {
906 return Node((id << 1) + 1);
908 int maxBNodeId() const {
909 return bNodes.size();
912 Node aNode(const UEdge& edge) const {
913 return Node(edges[edge.id].aNode);
915 Node bNode(const UEdge& edge) const {
916 return Node(edges[edge.id].bNode);
919 static bool aNode(const Node& node) {
920 return (node.id & 1) == 0;
923 static bool bNode(const Node& node) {
924 return (node.id & 1) == 1;
930 aNodes.push_back(nodeT);
931 return Node(aNodes.size() * 2 - 2);
937 bNodes.push_back(nodeT);
938 return Node(bNodes.size() * 2 - 1);
941 UEdge addEdge(const Node& source, const Node& target) {
942 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
944 if ((source.id & 1) == 0) {
945 edgeT.aNode = source.id;
946 edgeT.bNode = target.id;
948 edgeT.aNode = target.id;
949 edgeT.bNode = source.id;
951 edgeT.next_out = aNodes[edgeT.aNode >> 1].first;
952 aNodes[edgeT.aNode >> 1].first = edges.size();
953 edgeT.next_in = bNodes[edgeT.bNode >> 1].first;
954 bNodes[edgeT.bNode >> 1].first = edges.size();
955 edges.push_back(edgeT);
956 return UEdge(edges.size() - 1);
965 typedef True NodeNumTag;
966 int nodeNum() const { return aNodes.size() + bNodes.size(); }
967 int aNodeNum() const { return aNodes.size(); }
968 int bNodeNum() const { return bNodes.size(); }
970 typedef True EdgeNumTag;
971 int uEdgeNum() const { return edges.size(); }
976 typedef BpUGraphExtender<BidirBpUGraphExtender<SmartBpUGraphBase> >
977 ExtendedSmartBpUGraphBase;
981 /// \brief A smart bipartite undirected graph class.
983 /// This is a simple and fast bipartite undirected graph implementation.
984 /// It is also quite memory efficient, but at the price
985 /// that <b> it does not support node and edge deletions</b>.
986 /// Except from this it conforms to
987 /// the \ref concepts::BpUGraph "BpUGraph concept".
990 ///important extra feature that
991 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
993 /// \sa concepts::BpUGraph.
995 class SmartBpUGraph : public ExtendedSmartBpUGraphBase {
998 /// \brief SmartBpUGraph is \e not copy constructible.
1000 ///SmartBpUGraph is \e not copy constructible.
1001 SmartBpUGraph(const SmartBpUGraph &) : ExtendedSmartBpUGraphBase() {};
1003 /// \brief Assignment of SmartBpUGraph to another one is \e not
1006 /// Assignment of SmartBpUGraph to another one is \e not allowed.
1007 void operator=(const SmartBpUGraph &) {}
1011 typedef ExtendedSmartBpUGraphBase Parent;
1017 SmartBpUGraph() : ExtendedSmartBpUGraphBase() {}
1019 ///Add a new ANode to the graph.
1021 /// \return the new node.
1023 Node addANode() { return Parent::addANode(); }
1025 ///Add a new BNode to the graph.
1027 /// \return the new node.
1029 Node addBNode() { return Parent::addBNode(); }
1031 ///Add a new undirected edge to the graph.
1033 ///Add a new undirected edge to the graph with node \c s
1035 ///\return the new undirected edge.
1036 UEdge addEdge(const Node& s, const Node& t) {
1037 return Parent::addEdge(s, t);
1042 ///Erase all the nodes and edges from the graph.
1054 void restoreSnapshot(const Snapshot &s)
1056 while(s.edge_num<edges.size()) {
1057 UEdge edge = uEdgeFromId(edges.size()-1);
1058 Parent::notifier(UEdge()).erase(edge);
1059 std::vector<Edge> dir;
1060 dir.push_back(Parent::direct(edge, true));
1061 dir.push_back(Parent::direct(edge, false));
1062 Parent::notifier(Edge()).erase(dir);
1063 aNodes[edges.back().aNode >> 1].first=edges.back().next_out;
1064 bNodes[edges.back().bNode >> 1].first=edges.back().next_in;
1067 while(s.anode_num<aNodes.size()) {
1068 Node node = nodeFromANodeId(aNodes.size() - 1);
1069 Parent::notifier(ANode()).erase(node);
1070 Parent::notifier(Node()).erase(node);
1073 while(s.bnode_num<bNodes.size()) {
1074 Node node = nodeFromBNodeId(bNodes.size() - 1);
1075 Parent::notifier(BNode()).erase(node);
1076 Parent::notifier(Node()).erase(node);
1083 ///Class to make a snapshot of the graph and to restrore to it later.
1085 ///Class to make a snapshot of the graph and to restrore to it later.
1087 ///The newly added nodes and edges can be removed using the
1088 ///restore() function.
1090 ///\note After you restore a state, you cannot restore
1091 ///a later state, in other word you cannot add again the edges deleted
1092 ///by restore() using another one Snapshot instance.
1094 ///\warning If you do not use correctly the snapshot that can cause
1095 ///either broken program, invalid state of the graph, valid but
1096 ///not the restored graph or no change. Because the runtime performance
1097 ///the validity of the snapshot is not stored.
1102 friend class SmartBpUGraph;
1103 unsigned int anode_num;
1104 unsigned int bnode_num;
1105 unsigned int edge_num;
1107 ///Default constructor.
1109 ///Default constructor.
1110 ///To actually make a snapshot you must call save().
1112 Snapshot() : g(0) {}
1114 ///Constructor that immediately makes a snapshot
1116 ///This constructor immediately makes a snapshot of the graph.
1117 ///\param _g The graph we make a snapshot of.
1118 Snapshot(SmartBpUGraph &_g) : g(&_g) {
1119 anode_num=g->aNodes.size();
1120 bnode_num=g->bNodes.size();
1121 edge_num=g->edges.size();
1126 ///Make a snapshot of the graph.
1128 ///This function can be called more than once. In case of a repeated
1129 ///call, the previous snapshot gets lost.
1130 ///\param _g The graph we make the snapshot of.
1131 void save(SmartBpUGraph &_g)
1134 anode_num=g->aNodes.size();
1135 bnode_num=g->bNodes.size();
1136 edge_num=g->edges.size();
1139 ///Undo the changes until a snapshot.
1141 ///Undo the changes until a snapshot created by save().
1143 ///\note After you restored a state, you cannot restore
1144 ///a later state, in other word you cannot add again the edges deleted
1148 g->restoreSnapshot(*this);
1158 #endif //LEMON_SMART_GRAPH_H