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_LIST_GRAPH_H
20 #define LEMON_LIST_GRAPH_H
24 ///\brief ListGraph, ListUGraph classes.
26 #include <lemon/bits/base_extender.h>
27 #include <lemon/bits/graph_extender.h>
29 #include <lemon/error.h>
42 int first_in, first_out;
48 int prev_in, prev_out;
49 int next_in, next_out;
52 std::vector<NodeT> nodes;
58 std::vector<EdgeT> edges;
64 typedef ListGraphBase Graph;
67 friend class ListGraphBase;
71 explicit Node(int pid) { id = pid;}
75 Node (Invalid) { id = -1; }
76 bool operator==(const Node& node) const {return id == node.id;}
77 bool operator!=(const Node& node) const {return id != node.id;}
78 bool operator<(const Node& node) const {return id < node.id;}
82 friend class ListGraphBase;
86 explicit Edge(int pid) { id = pid;}
90 Edge (Invalid) { id = -1; }
91 bool operator==(const Edge& edge) const {return id == edge.id;}
92 bool operator!=(const Edge& edge) const {return id != edge.id;}
93 bool operator<(const Edge& edge) const {return id < edge.id;}
99 : nodes(), first_node(-1),
100 first_free_node(-1), edges(), first_free_edge(-1) {}
107 int maxNodeId() const { return nodes.size()-1; }
113 int maxEdgeId() const { return edges.size()-1; }
115 Node source(Edge e) const { return Node(edges[e.id].source); }
116 Node target(Edge e) const { return Node(edges[e.id].target); }
119 void first(Node& node) const {
120 node.id = first_node;
123 void next(Node& node) const {
124 node.id = nodes[node.id].next;
128 void first(Edge& e) const {
131 n!=-1 && nodes[n].first_in == -1;
133 e.id = (n == -1) ? -1 : nodes[n].first_in;
136 void next(Edge& edge) const {
137 if (edges[edge.id].next_in != -1) {
138 edge.id = edges[edge.id].next_in;
141 for(n = nodes[edges[edge.id].target].next;
142 n!=-1 && nodes[n].first_in == -1;
144 edge.id = (n == -1) ? -1 : nodes[n].first_in;
148 void firstOut(Edge &e, const Node& v) const {
149 e.id = nodes[v.id].first_out;
151 void nextOut(Edge &e) const {
152 e.id=edges[e.id].next_out;
155 void firstIn(Edge &e, const Node& v) const {
156 e.id = nodes[v.id].first_in;
158 void nextIn(Edge &e) const {
159 e.id=edges[e.id].next_in;
163 static int id(Node v) { return v.id; }
164 static int id(Edge e) { return e.id; }
166 static Node nodeFromId(int id) { return Node(id);}
167 static Edge edgeFromId(int id) { return Edge(id);}
169 /// Adds a new node to the graph.
171 /// Adds a new node to the graph.
173 /// \warning It adds the new node to the front of the list.
174 /// (i.e. the lastly added node becomes the first.)
178 if(first_free_node==-1) {
180 nodes.push_back(NodeT());
183 first_free_node = nodes[n].next;
186 nodes[n].next = first_node;
187 if(first_node != -1) nodes[first_node].prev = n;
191 nodes[n].first_in = nodes[n].first_out = -1;
196 Edge addEdge(Node u, Node v) {
199 if (first_free_edge == -1) {
201 edges.push_back(EdgeT());
204 first_free_edge = edges[n].next_in;
207 edges[n].source = u.id;
208 edges[n].target = v.id;
210 edges[n].next_out = nodes[u.id].first_out;
211 if(nodes[u.id].first_out != -1) {
212 edges[nodes[u.id].first_out].prev_out = n;
215 edges[n].next_in = nodes[v.id].first_in;
216 if(nodes[v.id].first_in != -1) {
217 edges[nodes[v.id].first_in].prev_in = n;
220 edges[n].prev_in = edges[n].prev_out = -1;
222 nodes[u.id].first_out = nodes[v.id].first_in = n;
227 void erase(const Node& node) {
230 if(nodes[n].next != -1) {
231 nodes[nodes[n].next].prev = nodes[n].prev;
234 if(nodes[n].prev != -1) {
235 nodes[nodes[n].prev].next = nodes[n].next;
237 first_node = nodes[n].next;
240 nodes[n].next = first_free_node;
245 void erase(const Edge& edge) {
248 if(edges[n].next_in!=-1) {
249 edges[edges[n].next_in].prev_in = edges[n].prev_in;
252 if(edges[n].prev_in!=-1) {
253 edges[edges[n].prev_in].next_in = edges[n].next_in;
255 nodes[edges[n].target].first_in = edges[n].next_in;
259 if(edges[n].next_out!=-1) {
260 edges[edges[n].next_out].prev_out = edges[n].prev_out;
263 if(edges[n].prev_out!=-1) {
264 edges[edges[n].prev_out].next_out = edges[n].next_out;
266 nodes[edges[n].source].first_out = edges[n].next_out;
269 edges[n].next_in = first_free_edge;
277 first_node = first_free_node = first_free_edge = -1;
281 void changeTarget(Edge e, Node n)
283 if(edges[e.id].next_in != -1)
284 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
285 if(edges[e.id].prev_in != -1)
286 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
287 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
288 if (nodes[n.id].first_in != -1) {
289 edges[nodes[n.id].first_in].prev_in = e.id;
291 edges[e.id].target = n.id;
292 edges[e.id].prev_in = -1;
293 edges[e.id].next_in = nodes[n.id].first_in;
294 nodes[n.id].first_in = e.id;
296 void changeSource(Edge e, Node n)
298 if(edges[e.id].next_out != -1)
299 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
300 if(edges[e.id].prev_out != -1)
301 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
302 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
303 if (nodes[n.id].first_out != -1) {
304 edges[nodes[n.id].first_out].prev_out = e.id;
306 edges[e.id].source = n.id;
307 edges[e.id].prev_out = -1;
308 edges[e.id].next_out = nodes[n.id].first_out;
309 nodes[n.id].first_out = e.id;
314 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
316 /// \addtogroup graphs
319 ///A list graph class.
321 ///This is a simple and fast graph implementation.
323 ///It conforms to the \ref concepts::Graph "Graph concept" and it
324 ///also provides several additional useful extra functionalities.
325 ///The most of the member functions and nested classes are
326 ///documented only in the concept class.
328 ///An important extra feature of this graph implementation is that
329 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
331 ///\sa concepts::Graph.
333 class ListGraph : public ExtendedListGraphBase {
335 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
337 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
339 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
340 ///\brief Assignment of ListGraph to another one is \e not allowed.
341 ///Use GraphCopy() instead.
343 ///Assignment of ListGraph to another one is \e not allowed.
344 ///Use GraphCopy() instead.
345 void operator=(const ListGraph &) {}
348 typedef ExtendedListGraphBase Parent;
356 ///Add a new node to the graph.
358 /// \return the new node.
360 Node addNode() { return Parent::addNode(); }
362 ///Add a new edge to the graph.
364 ///Add a new edge to the graph with source node \c s
365 ///and target node \c t.
366 ///\return the new edge.
367 Edge addEdge(const Node& s, const Node& t) {
368 return Parent::addEdge(s, t);
371 /// Changes the target of \c e to \c n
373 /// Changes the target of \c e to \c n
375 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
376 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
378 ///\warning This functionality cannot be used together with the Snapshot
380 void changeTarget(Edge e, Node n) {
381 Parent::changeTarget(e,n);
383 /// Changes the source of \c e to \c n
385 /// Changes the source of \c e to \c n
387 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
388 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
390 ///\warning This functionality cannot be used together with the Snapshot
392 void changeSource(Edge e, Node n) {
393 Parent::changeSource(e,n);
396 /// Invert the direction of an edge.
398 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
399 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
401 ///\warning This functionality cannot be used together with the Snapshot
403 void reverseEdge(Edge e) {
405 changeTarget(e,source(e));
409 /// \brief Using this it is possible to avoid the superfluous memory
412 ///Using this it is possible to avoid the superfluous memory
413 ///allocation: if you know that the graph you want to build will
414 ///contain at least 10 million nodes then it is worth reserving
415 ///space for this amount before starting to build the graph.
416 void reserveNode(int n) { nodes.reserve(n); };
418 /// \brief Using this it is possible to avoid the superfluous memory
421 ///Using this it is possible to avoid the superfluous memory
422 ///allocation: see the \ref reserveNode function.
423 void reserveEdge(int n) { edges.reserve(n); };
426 ///Contract two nodes.
428 ///This function contracts two nodes.
430 ///Node \p b will be removed but instead of deleting
431 ///incident edges, they will be joined to \p a.
432 ///The last parameter \p r controls whether to remove loops. \c true
433 ///means that loops will be removed.
435 ///\note The <tt>EdgeIt</tt>s
436 ///referencing a moved edge remain
437 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
438 ///may be invalidated.
439 ///\warning This functionality cannot be used together with the Snapshot
441 void contract(Node a, Node b, bool r = true)
443 for(OutEdgeIt e(*this,b);e!=INVALID;) {
446 if(r && target(e)==a) erase(e);
447 else changeSource(e,a);
450 for(InEdgeIt e(*this,b);e!=INVALID;) {
453 if(r && source(e)==a) erase(e);
454 else changeTarget(e,a);
462 ///This function splits a node. First a new node is added to the graph,
463 ///then the source of each outgoing edge of \c n is moved to this new node.
464 ///If \c connect is \c true (this is the default value), then a new edge
465 ///from \c n to the newly created node is also added.
466 ///\return The newly created node.
468 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
469 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
472 ///\warning This functionality cannot be used together with the
473 ///Snapshot feature. \todo It could be implemented in a bit
475 Node split(Node n, bool connect = true) {
477 for(OutEdgeIt e(*this,n);e!=INVALID;) {
483 if (connect) addEdge(n,b);
489 ///This function splits an edge. First a new node \c b is added to
490 ///the graph, then the original edge is re-targeted to \c
491 ///b. Finally an edge from \c b to the original target is added.
492 ///\return The newly created node.
493 ///\warning This functionality
494 ///cannot be used together with the Snapshot feature.
497 addEdge(b,target(e));
502 /// \brief Class to make a snapshot of the graph and restore
505 /// Class to make a snapshot of the graph and to restore it
508 /// The newly added nodes and edges can be removed using the
509 /// restore() function.
511 /// \warning Edge and node deletions cannot be restored. This
512 /// events invalidate the snapshot.
516 typedef Parent::NodeNotifier NodeNotifier;
518 class NodeObserverProxy : public NodeNotifier::ObserverBase {
521 NodeObserverProxy(Snapshot& _snapshot)
522 : snapshot(_snapshot) {}
524 using NodeNotifier::ObserverBase::attach;
525 using NodeNotifier::ObserverBase::detach;
526 using NodeNotifier::ObserverBase::attached;
530 virtual void add(const Node& node) {
531 snapshot.addNode(node);
533 virtual void add(const std::vector<Node>& nodes) {
534 for (int i = nodes.size() - 1; i >= 0; ++i) {
535 snapshot.addNode(nodes[i]);
538 virtual void erase(const Node& node) {
539 snapshot.eraseNode(node);
541 virtual void erase(const std::vector<Node>& nodes) {
542 for (int i = 0; i < (int)nodes.size(); ++i) {
543 snapshot.eraseNode(nodes[i]);
546 virtual void build() {
547 NodeNotifier* notifier = getNotifier();
549 std::vector<Node> nodes;
550 for (notifier->first(node); node != INVALID; notifier->next(node)) {
551 nodes.push_back(node);
553 for (int i = nodes.size() - 1; i >= 0; --i) {
554 snapshot.addNode(nodes[i]);
557 virtual void clear() {
558 NodeNotifier* notifier = getNotifier();
560 for (notifier->first(node); node != INVALID; notifier->next(node)) {
561 snapshot.eraseNode(node);
568 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
571 EdgeObserverProxy(Snapshot& _snapshot)
572 : snapshot(_snapshot) {}
574 using EdgeNotifier::ObserverBase::attach;
575 using EdgeNotifier::ObserverBase::detach;
576 using EdgeNotifier::ObserverBase::attached;
580 virtual void add(const Edge& edge) {
581 snapshot.addEdge(edge);
583 virtual void add(const std::vector<Edge>& edges) {
584 for (int i = edges.size() - 1; i >= 0; ++i) {
585 snapshot.addEdge(edges[i]);
588 virtual void erase(const Edge& edge) {
589 snapshot.eraseEdge(edge);
591 virtual void erase(const std::vector<Edge>& edges) {
592 for (int i = 0; i < (int)edges.size(); ++i) {
593 snapshot.eraseEdge(edges[i]);
596 virtual void build() {
597 EdgeNotifier* notifier = getNotifier();
599 std::vector<Edge> edges;
600 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
601 edges.push_back(edge);
603 for (int i = edges.size() - 1; i >= 0; --i) {
604 snapshot.addEdge(edges[i]);
607 virtual void clear() {
608 EdgeNotifier* notifier = getNotifier();
610 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
611 snapshot.eraseEdge(edge);
620 NodeObserverProxy node_observer_proxy;
621 EdgeObserverProxy edge_observer_proxy;
623 std::list<Node> added_nodes;
624 std::list<Edge> added_edges;
627 void addNode(const Node& node) {
628 added_nodes.push_front(node);
630 void eraseNode(const Node& node) {
631 std::list<Node>::iterator it =
632 std::find(added_nodes.begin(), added_nodes.end(), node);
633 if (it == added_nodes.end()) {
635 edge_observer_proxy.detach();
636 throw NodeNotifier::ImmediateDetach();
638 added_nodes.erase(it);
642 void addEdge(const Edge& edge) {
643 added_edges.push_front(edge);
645 void eraseEdge(const Edge& edge) {
646 std::list<Edge>::iterator it =
647 std::find(added_edges.begin(), added_edges.end(), edge);
648 if (it == added_edges.end()) {
650 node_observer_proxy.detach();
651 throw EdgeNotifier::ImmediateDetach();
653 added_edges.erase(it);
657 void attach(ListGraph &_graph) {
659 node_observer_proxy.attach(graph->getNotifier(Node()));
660 edge_observer_proxy.attach(graph->getNotifier(Edge()));
664 node_observer_proxy.detach();
665 edge_observer_proxy.detach();
668 bool attached() const {
669 return node_observer_proxy.attached();
679 /// \brief Default constructor.
681 /// Default constructor.
682 /// To actually make a snapshot you must call save().
684 : graph(0), node_observer_proxy(*this),
685 edge_observer_proxy(*this) {}
687 /// \brief Constructor that immediately makes a snapshot.
689 /// This constructor immediately makes a snapshot of the graph.
690 /// \param _graph The graph we make a snapshot of.
691 Snapshot(ListGraph &_graph)
692 : node_observer_proxy(*this),
693 edge_observer_proxy(*this) {
697 /// \brief Make a snapshot.
699 /// Make a snapshot of the graph.
701 /// This function can be called more than once. In case of a repeated
702 /// call, the previous snapshot gets lost.
703 /// \param _graph The graph we make the snapshot of.
704 void save(ListGraph &_graph) {
712 /// \brief Undo the changes until the last snapshot.
714 /// Undo the changes until the last snapshot created by save().
717 for(std::list<Edge>::iterator it = added_edges.begin();
718 it != added_edges.end(); ++it) {
721 for(std::list<Node>::iterator it = added_nodes.begin();
722 it != added_nodes.end(); ++it) {
728 /// \brief Gives back true when the snapshot is valid.
730 /// Gives back true when the snapshot is valid.
740 /**************** Undirected List Graph ****************/
742 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
743 ExtendedListUGraphBase;
745 /// \addtogroup graphs
748 ///An undirected list graph class.
750 ///This is a simple and fast undirected graph implementation.
752 ///An important extra feature of this graph implementation is that
753 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
755 ///It conforms to the
756 ///\ref concepts::UGraph "UGraph concept".
758 ///\sa concepts::UGraph.
760 class ListUGraph : public ExtendedListUGraphBase {
762 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
764 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
766 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
767 ///\brief Assignment of ListUGraph to another one is \e not allowed.
768 ///Use UGraphCopy() instead.
770 ///Assignment of ListUGraph to another one is \e not allowed.
771 ///Use UGraphCopy() instead.
772 void operator=(const ListUGraph &) {}
780 typedef ExtendedListUGraphBase Parent;
781 /// \brief Add a new node to the graph.
783 /// \return the new node.
785 Node addNode() { return Parent::addNode(); }
787 /// \brief Add a new edge to the graph.
789 /// Add a new edge to the graph with source node \c s
790 /// and target node \c t.
791 /// \return the new undirected edge.
792 UEdge addEdge(const Node& s, const Node& t) {
793 return Parent::addEdge(s, t);
795 /// \brief Changes the source of \c e to \c n
797 /// Changes the source of \c e to \c n
799 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
800 ///referencing the changed edge remain
801 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
802 void changeSource(UEdge e, Node n) {
803 Parent::changeSource(e,n);
805 /// \brief Changes the target of \c e to \c n
807 /// Changes the target of \c e to \c n
809 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
810 /// valid. However the other iterators may be invalidated.
811 void changeTarget(UEdge e, Node n) {
812 Parent::changeTarget(e,n);
814 /// \brief Changes the source of \c e to \c n
816 /// Changes the source of \c e to \c n. It changes the proper
817 /// node of the represented undirected edge.
819 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
820 ///referencing the changed edge remain
821 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
822 void changeSource(Edge e, Node n) {
823 if (Parent::direction(e)) {
824 Parent::changeSource(e,n);
826 Parent::changeTarget(e,n);
829 /// \brief Changes the target of \c e to \c n
831 /// Changes the target of \c e to \c n. It changes the proper
832 /// node of the represented undirected edge.
834 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
835 ///referencing the changed edge remain
836 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
837 void changeTarget(Edge e, Node n) {
838 if (Parent::direction(e)) {
839 Parent::changeTarget(e,n);
841 Parent::changeSource(e,n);
844 /// \brief Contract two nodes.
846 /// This function contracts two nodes.
848 /// Node \p b will be removed but instead of deleting
849 /// its neighboring edges, they will be joined to \p a.
850 /// The last parameter \p r controls whether to remove loops. \c true
851 /// means that loops will be removed.
853 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
855 void contract(Node a, Node b, bool r = true) {
856 for(IncEdgeIt e(*this, b); e!=INVALID;) {
857 IncEdgeIt f = e; ++f;
858 if (r && runningNode(e) == a) {
860 } else if (source(e) == b) {
871 /// \brief Class to make a snapshot of the graph and restore
874 /// Class to make a snapshot of the graph and to restore it
877 /// The newly added nodes and undirected edges can be removed
878 /// using the restore() function.
880 /// \warning Edge and node deletions cannot be restored. This
881 /// events invalidate the snapshot.
885 typedef Parent::NodeNotifier NodeNotifier;
887 class NodeObserverProxy : public NodeNotifier::ObserverBase {
890 NodeObserverProxy(Snapshot& _snapshot)
891 : snapshot(_snapshot) {}
893 using NodeNotifier::ObserverBase::attach;
894 using NodeNotifier::ObserverBase::detach;
895 using NodeNotifier::ObserverBase::attached;
899 virtual void add(const Node& node) {
900 snapshot.addNode(node);
902 virtual void add(const std::vector<Node>& nodes) {
903 for (int i = nodes.size() - 1; i >= 0; ++i) {
904 snapshot.addNode(nodes[i]);
907 virtual void erase(const Node& node) {
908 snapshot.eraseNode(node);
910 virtual void erase(const std::vector<Node>& nodes) {
911 for (int i = 0; i < (int)nodes.size(); ++i) {
912 snapshot.eraseNode(nodes[i]);
915 virtual void build() {
916 NodeNotifier* notifier = getNotifier();
918 std::vector<Node> nodes;
919 for (notifier->first(node); node != INVALID; notifier->next(node)) {
920 nodes.push_back(node);
922 for (int i = nodes.size() - 1; i >= 0; --i) {
923 snapshot.addNode(nodes[i]);
926 virtual void clear() {
927 NodeNotifier* notifier = getNotifier();
929 for (notifier->first(node); node != INVALID; notifier->next(node)) {
930 snapshot.eraseNode(node);
937 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
940 UEdgeObserverProxy(Snapshot& _snapshot)
941 : snapshot(_snapshot) {}
943 using UEdgeNotifier::ObserverBase::attach;
944 using UEdgeNotifier::ObserverBase::detach;
945 using UEdgeNotifier::ObserverBase::attached;
949 virtual void add(const UEdge& edge) {
950 snapshot.addUEdge(edge);
952 virtual void add(const std::vector<UEdge>& edges) {
953 for (int i = edges.size() - 1; i >= 0; ++i) {
954 snapshot.addUEdge(edges[i]);
957 virtual void erase(const UEdge& edge) {
958 snapshot.eraseUEdge(edge);
960 virtual void erase(const std::vector<UEdge>& edges) {
961 for (int i = 0; i < (int)edges.size(); ++i) {
962 snapshot.eraseUEdge(edges[i]);
965 virtual void build() {
966 UEdgeNotifier* notifier = getNotifier();
968 std::vector<UEdge> edges;
969 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
970 edges.push_back(edge);
972 for (int i = edges.size() - 1; i >= 0; --i) {
973 snapshot.addUEdge(edges[i]);
976 virtual void clear() {
977 UEdgeNotifier* notifier = getNotifier();
979 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
980 snapshot.eraseUEdge(edge);
989 NodeObserverProxy node_observer_proxy;
990 UEdgeObserverProxy edge_observer_proxy;
992 std::list<Node> added_nodes;
993 std::list<UEdge> added_edges;
996 void addNode(const Node& node) {
997 added_nodes.push_front(node);
999 void eraseNode(const Node& node) {
1000 std::list<Node>::iterator it =
1001 std::find(added_nodes.begin(), added_nodes.end(), node);
1002 if (it == added_nodes.end()) {
1004 edge_observer_proxy.detach();
1005 throw NodeNotifier::ImmediateDetach();
1007 added_nodes.erase(it);
1011 void addUEdge(const UEdge& edge) {
1012 added_edges.push_front(edge);
1014 void eraseUEdge(const UEdge& edge) {
1015 std::list<UEdge>::iterator it =
1016 std::find(added_edges.begin(), added_edges.end(), edge);
1017 if (it == added_edges.end()) {
1019 node_observer_proxy.detach();
1020 throw UEdgeNotifier::ImmediateDetach();
1022 added_edges.erase(it);
1026 void attach(ListUGraph &_graph) {
1028 node_observer_proxy.attach(graph->getNotifier(Node()));
1029 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1033 node_observer_proxy.detach();
1034 edge_observer_proxy.detach();
1037 bool attached() const {
1038 return node_observer_proxy.attached();
1042 added_nodes.clear();
1043 added_edges.clear();
1048 /// \brief Default constructor.
1050 /// Default constructor.
1051 /// To actually make a snapshot you must call save().
1053 : graph(0), node_observer_proxy(*this),
1054 edge_observer_proxy(*this) {}
1056 /// \brief Constructor that immediately makes a snapshot.
1058 /// This constructor immediately makes a snapshot of the graph.
1059 /// \param _graph The graph we make a snapshot of.
1060 Snapshot(ListUGraph &_graph)
1061 : node_observer_proxy(*this),
1062 edge_observer_proxy(*this) {
1066 /// \brief Make a snapshot.
1068 /// Make a snapshot of the graph.
1070 /// This function can be called more than once. In case of a repeated
1071 /// call, the previous snapshot gets lost.
1072 /// \param _graph The graph we make the snapshot of.
1073 void save(ListUGraph &_graph) {
1081 /// \brief Undo the changes until the last snapshot.
1083 /// Undo the changes until the last snapshot created by save().
1086 for(std::list<UEdge>::iterator it = added_edges.begin();
1087 it != added_edges.end(); ++it) {
1090 for(std::list<Node>::iterator it = added_nodes.begin();
1091 it != added_nodes.end(); ++it) {
1097 /// \brief Gives back true when the snapshot is valid.
1099 /// Gives back true when the snapshot is valid.
1100 bool valid() const {
1107 class ListBpUGraphBase {
1110 class NodeSetError : public LogicError {
1112 virtual const char* what() const throw() {
1113 return "lemon::ListBpUGraph::NodeSetError";
1120 int first_edge, prev, next;
1124 int aNode, prev_out, next_out;
1125 int bNode, prev_in, next_in;
1128 std::vector<NodeT> aNodes;
1129 std::vector<NodeT> bNodes;
1131 std::vector<UEdgeT> edges;
1134 int first_free_anode;
1137 int first_free_bnode;
1139 int first_free_edge;
1144 friend class ListBpUGraphBase;
1148 explicit Node(int _id) : id(_id) {}
1151 Node(Invalid) { id = -1; }
1152 bool operator==(const Node i) const {return id==i.id;}
1153 bool operator!=(const Node i) const {return id!=i.id;}
1154 bool operator<(const Node i) const {return id<i.id;}
1158 friend class ListBpUGraphBase;
1162 explicit UEdge(int _id) { id = _id;}
1165 UEdge (Invalid) { id = -1; }
1166 bool operator==(const UEdge i) const {return id==i.id;}
1167 bool operator!=(const UEdge i) const {return id!=i.id;}
1168 bool operator<(const UEdge i) const {return id<i.id;}
1172 : first_anode(-1), first_free_anode(-1),
1173 first_bnode(-1), first_free_bnode(-1),
1174 first_free_edge(-1) {}
1176 void firstANode(Node& node) const {
1177 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1179 void nextANode(Node& node) const {
1180 node.id = aNodes[node.id >> 1].next;
1183 void firstBNode(Node& node) const {
1184 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1186 void nextBNode(Node& node) const {
1187 node.id = bNodes[node.id >> 1].next;
1190 void first(Node& node) const {
1191 if (first_anode != -1) {
1192 node.id = (first_anode << 1);
1193 } else if (first_bnode != -1) {
1194 node.id = (first_bnode << 1) + 1;
1199 void next(Node& node) const {
1201 node.id = aNodes[node.id >> 1].next;
1202 if (node.id == -1) {
1203 if (first_bnode != -1) {
1204 node.id = (first_bnode << 1) + 1;
1208 node.id = bNodes[node.id >> 1].next;
1212 void first(UEdge& edge) const {
1213 int aNodeId = first_anode;
1214 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1215 aNodeId = aNodes[aNodeId].next != -1 ?
1216 aNodes[aNodeId].next >> 1 : -1;
1218 if (aNodeId != -1) {
1219 edge.id = aNodes[aNodeId].first_edge;
1224 void next(UEdge& edge) const {
1225 int aNodeId = edges[edge.id].aNode >> 1;
1226 edge.id = edges[edge.id].next_out;
1227 if (edge.id == -1) {
1228 aNodeId = aNodes[aNodeId].next != -1 ?
1229 aNodes[aNodeId].next >> 1 : -1;
1230 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1231 aNodeId = aNodes[aNodeId].next != -1 ?
1232 aNodes[aNodeId].next >> 1 : -1;
1234 if (aNodeId != -1) {
1235 edge.id = aNodes[aNodeId].first_edge;
1242 void firstFromANode(UEdge& edge, const Node& node) const {
1243 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1244 edge.id = aNodes[node.id >> 1].first_edge;
1246 void nextFromANode(UEdge& edge) const {
1247 edge.id = edges[edge.id].next_out;
1250 void firstFromBNode(UEdge& edge, const Node& node) const {
1251 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1252 edge.id = bNodes[node.id >> 1].first_edge;
1254 void nextFromBNode(UEdge& edge) const {
1255 edge.id = edges[edge.id].next_in;
1258 static int id(const Node& node) {
1261 static Node nodeFromId(int id) {
1264 int maxNodeId() const {
1265 return aNodes.size() > bNodes.size() ?
1266 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1269 static int id(const UEdge& edge) {
1272 static UEdge uEdgeFromId(int id) {
1275 int maxUEdgeId() const {
1276 return edges.size();
1279 static int aNodeId(const Node& node) {
1280 return node.id >> 1;
1282 static Node nodeFromANodeId(int id) {
1283 return Node(id << 1);
1285 int maxANodeId() const {
1286 return aNodes.size();
1289 static int bNodeId(const Node& node) {
1290 return node.id >> 1;
1292 static Node nodeFromBNodeId(int id) {
1293 return Node((id << 1) + 1);
1295 int maxBNodeId() const {
1296 return bNodes.size();
1299 Node aNode(const UEdge& edge) const {
1300 return Node(edges[edge.id].aNode);
1302 Node bNode(const UEdge& edge) const {
1303 return Node(edges[edge.id].bNode);
1306 static bool aNode(const Node& node) {
1307 return (node.id & 1) == 0;
1310 static bool bNode(const Node& node) {
1311 return (node.id & 1) == 1;
1316 if (first_free_anode == -1) {
1317 aNodeId = aNodes.size();
1318 aNodes.push_back(NodeT());
1320 aNodeId = first_free_anode;
1321 first_free_anode = aNodes[first_free_anode].next;
1323 if (first_anode != -1) {
1324 aNodes[aNodeId].next = first_anode << 1;
1325 aNodes[first_anode].prev = aNodeId << 1;
1327 aNodes[aNodeId].next = -1;
1329 aNodes[aNodeId].prev = -1;
1330 first_anode = aNodeId;
1331 aNodes[aNodeId].first_edge = -1;
1332 return Node(aNodeId << 1);
1337 if (first_free_bnode == -1) {
1338 bNodeId = bNodes.size();
1339 bNodes.push_back(NodeT());
1341 bNodeId = first_free_bnode;
1342 first_free_bnode = bNodes[first_free_bnode].next;
1344 if (first_bnode != -1) {
1345 bNodes[bNodeId].next = (first_bnode << 1) + 1;
1346 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1348 bNodes[bNodeId].next = -1;
1350 bNodes[bNodeId].prev = -1;
1351 first_bnode = bNodeId;
1352 bNodes[bNodeId].first_edge = -1;
1353 return Node((bNodeId << 1) + 1);
1356 UEdge addEdge(const Node& source, const Node& target) {
1357 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1359 if (first_free_edge != -1) {
1360 edgeId = first_free_edge;
1361 first_free_edge = edges[edgeId].next_out;
1363 edgeId = edges.size();
1364 edges.push_back(UEdgeT());
1366 if ((source.id & 1) == 0) {
1367 edges[edgeId].aNode = source.id;
1368 edges[edgeId].bNode = target.id;
1370 edges[edgeId].aNode = target.id;
1371 edges[edgeId].bNode = source.id;
1373 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1374 edges[edgeId].prev_out = -1;
1375 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1376 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1378 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1379 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1380 edges[edgeId].prev_in = -1;
1381 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1382 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1384 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1385 return UEdge(edgeId);
1388 void erase(const Node& node) {
1390 int aNodeId = node.id >> 1;
1391 if (aNodes[aNodeId].prev != -1) {
1392 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1395 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
1397 if (aNodes[aNodeId].next != -1) {
1398 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1400 aNodes[aNodeId].next = first_free_anode;
1401 first_free_anode = aNodeId;
1403 int bNodeId = node.id >> 1;
1404 if (bNodes[bNodeId].prev != -1) {
1405 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1408 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
1410 if (bNodes[bNodeId].next != -1) {
1411 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1413 bNodes[bNodeId].next = first_free_bnode;
1414 first_free_bnode = bNodeId;
1418 void erase(const UEdge& edge) {
1420 if (edges[edge.id].prev_out != -1) {
1421 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1423 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1425 if (edges[edge.id].next_out != -1) {
1426 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1429 if (edges[edge.id].prev_in != -1) {
1430 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1432 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1434 if (edges[edge.id].next_in != -1) {
1435 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1438 edges[edge.id].next_out = first_free_edge;
1439 first_free_edge = edge.id;
1447 first_free_anode = -1;
1449 first_free_bnode = -1;
1450 first_free_edge = -1;
1453 void changeANode(const UEdge& edge, const Node& node) {
1454 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1455 if (edges[edge.id].prev_out != -1) {
1456 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1458 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1460 if (edges[edge.id].next_out != -1) {
1461 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1463 if (aNodes[node.id >> 1].first_edge != -1) {
1464 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1466 edges[edge.id].prev_out = -1;
1467 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1468 aNodes[node.id >> 1].first_edge = edge.id;
1469 edges[edge.id].aNode = node.id;
1472 void changeBNode(const UEdge& edge, const Node& node) {
1473 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1474 if (edges[edge.id].prev_in != -1) {
1475 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1477 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1479 if (edges[edge.id].next_in != -1) {
1480 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1482 if (bNodes[node.id >> 1].first_edge != -1) {
1483 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1485 edges[edge.id].prev_in = -1;
1486 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1487 bNodes[node.id >> 1].first_edge = edge.id;
1488 edges[edge.id].bNode = node.id;
1494 typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1495 ExtendedListBpUGraphBase;
1499 /// \brief A smart bipartite undirected graph class.
1501 /// This is a bipartite undirected graph implementation.
1502 /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
1504 ///An important extra feature of this graph implementation is that
1505 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1507 /// \sa concepts::BpUGraph.
1509 class ListBpUGraph : public ExtendedListBpUGraphBase {
1510 /// \brief ListBpUGraph is \e not copy constructible.
1512 ///ListBpUGraph is \e not copy constructible.
1513 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1514 /// \brief Assignment of ListBpUGraph to another one is \e not
1517 /// Assignment of ListBpUGraph to another one is \e not allowed.
1518 void operator=(const ListBpUGraph &) {}
1520 /// \brief Constructor
1526 typedef ExtendedListBpUGraphBase Parent;
1527 /// \brief Add a new ANode to the graph.
1529 /// \return the new node.
1531 Node addANode() { return Parent::addANode(); }
1533 /// \brief Add a new BNode to the graph.
1535 /// \return the new node.
1537 Node addBNode() { return Parent::addBNode(); }
1539 /// \brief Add a new edge to the graph.
1541 /// Add a new edge to the graph with an ANode and a BNode.
1542 /// \return the new undirected edge.
1543 UEdge addEdge(const Node& s, const Node& t) {
1544 return Parent::addEdge(s, t);
1547 /// \brief Changes the ANode of \c e to \c n
1549 /// Changes the ANode of \c e to \c n
1551 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1552 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1554 void changeANode(UEdge e, Node n) {
1555 Parent::changeANode(e,n);
1558 /// \brief Changes the BNode of \c e to \c n
1560 /// Changes the BNode of \c e to \c n
1562 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1563 /// referencing the changed edge remain
1564 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1565 void changeBNode(UEdge e, Node n) {
1566 Parent::changeBNode(e,n);
1569 /// \brief Changes the source(ANode) of \c e to \c n
1571 /// Changes the source(ANode) of \c e to \c n
1573 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1574 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1576 void changeSource(UEdge e, Node n) {
1577 Parent::changeANode(e,n);
1580 /// \brief Changes the target(BNode) of \c e to \c n
1582 /// Changes the target(BNode) of \c e to \c n
1584 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1585 /// referencing the changed edge remain
1586 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1587 void changeTarget(UEdge e, Node n) {
1588 Parent::changeBNode(e,n);
1591 /// \brief Changes the source of \c e to \c n
1593 /// Changes the source of \c e to \c n. It changes the proper
1594 /// node of the represented undirected edge.
1596 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1597 ///referencing the changed edge remain
1598 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1599 void changeSource(Edge e, Node n) {
1600 if (Parent::direction(e)) {
1601 Parent::changeANode(e,n);
1603 Parent::changeBNode(e,n);
1606 /// \brief Changes the target of \c e to \c n
1608 /// Changes the target of \c e to \c n. It changes the proper
1609 /// node of the represented undirected edge.
1611 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1612 ///referencing the changed edge remain
1613 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1614 void changeTarget(Edge e, Node n) {
1615 if (Parent::direction(e)) {
1616 Parent::changeBNode(e,n);
1618 Parent::changeANode(e,n);
1621 /// \brief Contract two nodes.
1623 /// This function contracts two nodes.
1625 /// Node \p b will be removed but instead of deleting its
1626 /// neighboring edges, they will be joined to \p a. The two nodes
1627 /// should be from the same nodeset, of course.
1629 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1631 void contract(const Node& a, const Node& b) {
1632 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1633 if (Parent::aNode(a)) {
1634 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1635 IncEdgeIt f = e; ++f;
1640 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1641 IncEdgeIt f = e; ++f;
1649 /// \brief Class to make a snapshot of the graph and restore
1652 /// Class to make a snapshot of the graph and to restore it
1655 /// The newly added nodes and undirected edges can be removed
1656 /// using the restore() function.
1658 /// \warning Edge and node deletions cannot be restored. This
1659 /// events invalidate the snapshot.
1663 typedef Parent::NodeNotifier NodeNotifier;
1665 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1668 NodeObserverProxy(Snapshot& _snapshot)
1669 : snapshot(_snapshot) {}
1671 using NodeNotifier::ObserverBase::attach;
1672 using NodeNotifier::ObserverBase::detach;
1673 using NodeNotifier::ObserverBase::attached;
1677 virtual void add(const Node& node) {
1678 snapshot.addNode(node);
1680 virtual void add(const std::vector<Node>& nodes) {
1681 for (int i = nodes.size() - 1; i >= 0; ++i) {
1682 snapshot.addNode(nodes[i]);
1685 virtual void erase(const Node& node) {
1686 snapshot.eraseNode(node);
1688 virtual void erase(const std::vector<Node>& nodes) {
1689 for (int i = 0; i < (int)nodes.size(); ++i) {
1690 snapshot.eraseNode(nodes[i]);
1693 virtual void build() {
1694 NodeNotifier* notifier = getNotifier();
1696 std::vector<Node> nodes;
1697 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1698 nodes.push_back(node);
1700 for (int i = nodes.size() - 1; i >= 0; --i) {
1701 snapshot.addNode(nodes[i]);
1704 virtual void clear() {
1705 NodeNotifier* notifier = getNotifier();
1707 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1708 snapshot.eraseNode(node);
1715 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1718 UEdgeObserverProxy(Snapshot& _snapshot)
1719 : snapshot(_snapshot) {}
1721 using UEdgeNotifier::ObserverBase::attach;
1722 using UEdgeNotifier::ObserverBase::detach;
1723 using UEdgeNotifier::ObserverBase::attached;
1727 virtual void add(const UEdge& edge) {
1728 snapshot.addUEdge(edge);
1730 virtual void add(const std::vector<UEdge>& edges) {
1731 for (int i = edges.size() - 1; i >= 0; ++i) {
1732 snapshot.addUEdge(edges[i]);
1735 virtual void erase(const UEdge& edge) {
1736 snapshot.eraseUEdge(edge);
1738 virtual void erase(const std::vector<UEdge>& edges) {
1739 for (int i = 0; i < (int)edges.size(); ++i) {
1740 snapshot.eraseUEdge(edges[i]);
1743 virtual void build() {
1744 UEdgeNotifier* notifier = getNotifier();
1746 std::vector<UEdge> edges;
1747 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1748 edges.push_back(edge);
1750 for (int i = edges.size() - 1; i >= 0; --i) {
1751 snapshot.addUEdge(edges[i]);
1754 virtual void clear() {
1755 UEdgeNotifier* notifier = getNotifier();
1757 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1758 snapshot.eraseUEdge(edge);
1765 ListBpUGraph *graph;
1767 NodeObserverProxy node_observer_proxy;
1768 UEdgeObserverProxy edge_observer_proxy;
1770 std::list<Node> added_nodes;
1771 std::list<UEdge> added_edges;
1774 void addNode(const Node& node) {
1775 added_nodes.push_front(node);
1777 void eraseNode(const Node& node) {
1778 std::list<Node>::iterator it =
1779 std::find(added_nodes.begin(), added_nodes.end(), node);
1780 if (it == added_nodes.end()) {
1782 edge_observer_proxy.detach();
1783 throw NodeNotifier::ImmediateDetach();
1785 added_nodes.erase(it);
1789 void addUEdge(const UEdge& edge) {
1790 added_edges.push_front(edge);
1792 void eraseUEdge(const UEdge& edge) {
1793 std::list<UEdge>::iterator it =
1794 std::find(added_edges.begin(), added_edges.end(), edge);
1795 if (it == added_edges.end()) {
1797 node_observer_proxy.detach();
1798 throw UEdgeNotifier::ImmediateDetach();
1800 added_edges.erase(it);
1804 void attach(ListBpUGraph &_graph) {
1806 node_observer_proxy.attach(graph->getNotifier(Node()));
1807 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1811 node_observer_proxy.detach();
1812 edge_observer_proxy.detach();
1815 bool attached() const {
1816 return node_observer_proxy.attached();
1820 added_nodes.clear();
1821 added_edges.clear();
1826 /// \brief Default constructor.
1828 /// Default constructor.
1829 /// To actually make a snapshot you must call save().
1831 : graph(0), node_observer_proxy(*this),
1832 edge_observer_proxy(*this) {}
1834 /// \brief Constructor that immediately makes a snapshot.
1836 /// This constructor immediately makes a snapshot of the graph.
1837 /// \param _graph The graph we make a snapshot of.
1838 Snapshot(ListBpUGraph &_graph)
1839 : node_observer_proxy(*this),
1840 edge_observer_proxy(*this) {
1844 /// \brief Make a snapshot.
1846 /// Make a snapshot of the graph.
1848 /// This function can be called more than once. In case of a repeated
1849 /// call, the previous snapshot gets lost.
1850 /// \param _graph The graph we make the snapshot of.
1851 void save(ListBpUGraph &_graph) {
1859 /// \brief Undo the changes until the last snapshot.
1861 /// Undo the changes until the last snapshot created by save().
1864 for(std::list<UEdge>::iterator it = added_edges.begin();
1865 it != added_edges.end(); ++it) {
1868 for(std::list<Node>::iterator it = added_nodes.begin();
1869 it != added_nodes.end(); ++it) {
1875 /// \brief Gives back true when the snapshot is valid.
1877 /// Gives back true when the snapshot is valid.
1878 bool valid() const {