Graph imlementations actually provide ReferenceMaps.
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>
40 int first_in, first_out;
46 int prev_in, prev_out;
47 int next_in, next_out;
50 std::vector<NodeT> nodes;
56 std::vector<EdgeT> edges;
62 typedef ListGraphBase Graph;
65 friend class ListGraphBase;
69 explicit Node(int pid) { id = pid;}
73 Node (Invalid) { id = -1; }
74 bool operator==(const Node& node) const {return id == node.id;}
75 bool operator!=(const Node& node) const {return id != node.id;}
76 bool operator<(const Node& node) const {return id < node.id;}
80 friend class ListGraphBase;
84 explicit Edge(int pid) { id = pid;}
88 Edge (Invalid) { id = -1; }
89 bool operator==(const Edge& edge) const {return id == edge.id;}
90 bool operator!=(const Edge& edge) const {return id != edge.id;}
91 bool operator<(const Edge& edge) const {return id < edge.id;}
97 : nodes(), first_node(-1),
98 first_free_node(-1), edges(), first_free_edge(-1) {}
105 int maxNodeId() const { return nodes.size()-1; }
111 int maxEdgeId() const { return edges.size()-1; }
113 Node source(Edge e) const { return Node(edges[e.id].source); }
114 Node target(Edge e) const { return Node(edges[e.id].target); }
117 void first(Node& node) const {
118 node.id = first_node;
121 void next(Node& node) const {
122 node.id = nodes[node.id].next;
126 void first(Edge& e) const {
129 n!=-1 && nodes[n].first_in == -1;
131 e.id = (n == -1) ? -1 : nodes[n].first_in;
134 void next(Edge& edge) const {
135 if (edges[edge.id].next_in != -1) {
136 edge.id = edges[edge.id].next_in;
139 for(n = nodes[edges[edge.id].target].next;
140 n!=-1 && nodes[n].first_in == -1;
142 edge.id = (n == -1) ? -1 : nodes[n].first_in;
146 void firstOut(Edge &e, const Node& v) const {
147 e.id = nodes[v.id].first_out;
149 void nextOut(Edge &e) const {
150 e.id=edges[e.id].next_out;
153 void firstIn(Edge &e, const Node& v) const {
154 e.id = nodes[v.id].first_in;
156 void nextIn(Edge &e) const {
157 e.id=edges[e.id].next_in;
161 static int id(Node v) { return v.id; }
162 static int id(Edge e) { return e.id; }
164 static Node nodeFromId(int id) { return Node(id);}
165 static Edge edgeFromId(int id) { return Edge(id);}
167 /// Adds a new node to the graph.
169 /// Adds a new node to the graph.
171 /// \warning It adds the new node to the front of the list.
172 /// (i.e. the lastly added node becomes the first.)
176 if(first_free_node==-1) {
178 nodes.push_back(NodeT());
181 first_free_node = nodes[n].next;
184 nodes[n].next = first_node;
185 if(first_node != -1) nodes[first_node].prev = n;
189 nodes[n].first_in = nodes[n].first_out = -1;
194 Edge addEdge(Node u, Node v) {
197 if (first_free_edge == -1) {
199 edges.push_back(EdgeT());
202 first_free_edge = edges[n].next_in;
205 edges[n].source = u.id;
206 edges[n].target = v.id;
208 edges[n].next_out = nodes[u.id].first_out;
209 if(nodes[u.id].first_out != -1) {
210 edges[nodes[u.id].first_out].prev_out = n;
213 edges[n].next_in = nodes[v.id].first_in;
214 if(nodes[v.id].first_in != -1) {
215 edges[nodes[v.id].first_in].prev_in = n;
218 edges[n].prev_in = edges[n].prev_out = -1;
220 nodes[u.id].first_out = nodes[v.id].first_in = n;
225 void erase(const Node& node) {
228 if(nodes[n].next != -1) {
229 nodes[nodes[n].next].prev = nodes[n].prev;
232 if(nodes[n].prev != -1) {
233 nodes[nodes[n].prev].next = nodes[n].next;
235 first_node = nodes[n].next;
238 nodes[n].next = first_free_node;
243 void erase(const Edge& edge) {
246 if(edges[n].next_in!=-1) {
247 edges[edges[n].next_in].prev_in = edges[n].prev_in;
250 if(edges[n].prev_in!=-1) {
251 edges[edges[n].prev_in].next_in = edges[n].next_in;
253 nodes[edges[n].target].first_in = edges[n].next_in;
257 if(edges[n].next_out!=-1) {
258 edges[edges[n].next_out].prev_out = edges[n].prev_out;
261 if(edges[n].prev_out!=-1) {
262 edges[edges[n].prev_out].next_out = edges[n].next_out;
264 nodes[edges[n].source].first_out = edges[n].next_out;
267 edges[n].next_in = first_free_edge;
275 first_node = first_free_node = first_free_edge = -1;
279 void changeTarget(Edge e, Node n)
281 if(edges[e.id].next_in != -1)
282 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
283 if(edges[e.id].prev_in != -1)
284 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
285 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
286 if (nodes[n.id].first_in != -1) {
287 edges[nodes[n.id].first_in].prev_in = e.id;
289 edges[e.id].target = n.id;
290 edges[e.id].prev_in = -1;
291 edges[e.id].next_in = nodes[n.id].first_in;
292 nodes[n.id].first_in = e.id;
294 void changeSource(Edge e, Node n)
296 if(edges[e.id].next_out != -1)
297 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
298 if(edges[e.id].prev_out != -1)
299 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
300 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
301 if (nodes[n.id].first_out != -1) {
302 edges[nodes[n.id].first_out].prev_out = e.id;
304 edges[e.id].source = n.id;
305 edges[e.id].prev_out = -1;
306 edges[e.id].next_out = nodes[n.id].first_out;
307 nodes[n.id].first_out = e.id;
312 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
314 /// \addtogroup graphs
317 ///A list graph class.
319 ///This is a simple and fast graph implementation.
321 ///It conforms to the \ref concept::Graph "Graph concept" and it
322 ///also provides several additional useful extra functionalities.
323 ///The most of the member functions and nested classes are
324 ///documented only in the concept class.
326 ///An important extra feature of this graph implementation is that
327 ///its maps are real \ref concept::ReferenceMap "reference map"s.
329 ///\sa concept::Graph.
331 class ListGraph : public ExtendedListGraphBase {
333 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
335 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
337 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
338 ///\brief Assignment of ListGraph to another one is \e not allowed.
339 ///Use GraphCopy() instead.
341 ///Assignment of ListGraph to another one is \e not allowed.
342 ///Use GraphCopy() instead.
343 void operator=(const ListGraph &) {}
346 typedef ExtendedListGraphBase Parent;
354 ///Add a new node to the graph.
356 /// \return the new node.
358 Node addNode() { return Parent::addNode(); }
360 ///Add a new edge to the graph.
362 ///Add a new edge to the graph with source node \c s
363 ///and target node \c t.
364 ///\return the new edge.
365 Edge addEdge(const Node& s, const Node& t) {
366 return Parent::addEdge(s, t);
369 /// Changes the target of \c e to \c n
371 /// Changes the target of \c e to \c n
373 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
374 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
376 ///\warning This functionality cannot be used together with the Snapshot
378 void changeTarget(Edge e, Node n) {
379 Parent::changeTarget(e,n);
381 /// Changes the source of \c e to \c n
383 /// Changes the source of \c e to \c n
385 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
386 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
388 ///\warning This functionality cannot be used together with the Snapshot
390 void changeSource(Edge e, Node n) {
391 Parent::changeSource(e,n);
394 /// Invert the direction of an edge.
396 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
397 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
399 ///\warning This functionality cannot be used together with the Snapshot
401 void reverseEdge(Edge e) {
403 changeTarget(e,source(e));
407 /// \brief Using this it is possible to avoid the superfluous memory
410 ///Using this it is possible to avoid the superfluous memory
411 ///allocation: if you know that the graph you want to build will
412 ///contain at least 10 million nodes then it is worth reserving
413 ///space for this amount before starting to build the graph.
414 void reserveNode(int n) { nodes.reserve(n); };
416 /// \brief Using this it is possible to avoid the superfluous memory
419 ///Using this it is possible to avoid the superfluous memory
420 ///allocation: see the \ref reserveNode function.
421 void reserveEdge(int n) { edges.reserve(n); };
424 ///Contract two nodes.
426 ///This function contracts two nodes.
428 ///Node \p b will be removed but instead of deleting
429 ///incident edges, they will be joined to \p a.
430 ///The last parameter \p r controls whether to remove loops. \c true
431 ///means that loops will be removed.
433 ///\note The <tt>EdgeIt</tt>s
434 ///referencing a moved edge remain
435 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
436 ///may be invalidated.
437 ///\warning This functionality cannot be used together with the Snapshot
439 void contract(Node a, Node b, bool r = true)
441 for(OutEdgeIt e(*this,b);e!=INVALID;) {
444 if(r && target(e)==a) erase(e);
445 else changeSource(e,a);
448 for(InEdgeIt e(*this,b);e!=INVALID;) {
451 if(r && source(e)==a) erase(e);
452 else changeTarget(e,a);
460 ///This function splits a node. First a new node is added to the graph,
461 ///then the source of each outgoing edge of \c n is moved to this new node.
462 ///If \c connect is \c true (this is the default value), then a new edge
463 ///from \c n to the newly created node is also added.
464 ///\return The newly created node.
466 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
467 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
470 ///\warning This functionality cannot be used together with the
471 ///Snapshot feature. \todo It could be implemented in a bit
473 Node split(Node n, bool connect = true) {
475 for(OutEdgeIt e(*this,n);e!=INVALID;) {
481 if (connect) addEdge(n,b);
487 ///This function splits an edge. First a new node \c b is added to
488 ///the graph, then the original edge is re-targeted to \c
489 ///b. Finally an edge from \c b to the original target is added.
490 ///\return The newly created node.
491 ///\warning This functionality
492 ///cannot be used together with the Snapshot feature.
495 addEdge(b,target(e));
500 /// \brief Class to make a snapshot of the graph and restore
503 /// Class to make a snapshot of the graph and to restore it
506 /// The newly added nodes and edges can be removed using the
507 /// restore() function.
509 /// \warning Edge and node deletions cannot be restored. This
510 /// events invalidate the snapshot.
514 typedef Parent::NodeNotifier NodeNotifier;
516 class NodeObserverProxy : public NodeNotifier::ObserverBase {
519 NodeObserverProxy(Snapshot& _snapshot)
520 : snapshot(_snapshot) {}
522 using NodeNotifier::ObserverBase::attach;
523 using NodeNotifier::ObserverBase::detach;
524 using NodeNotifier::ObserverBase::attached;
528 virtual void add(const Node& node) {
529 snapshot.addNode(node);
531 virtual void add(const std::vector<Node>& nodes) {
532 for (int i = nodes.size() - 1; i >= 0; ++i) {
533 snapshot.addNode(nodes[i]);
536 virtual void erase(const Node& node) {
537 snapshot.eraseNode(node);
539 virtual void erase(const std::vector<Node>& nodes) {
540 for (int i = 0; i < (int)nodes.size(); ++i) {
541 snapshot.eraseNode(nodes[i]);
544 virtual void build() {
545 NodeNotifier* notifier = getNotifier();
547 std::vector<Node> nodes;
548 for (notifier->first(node); node != INVALID; notifier->next(node)) {
549 nodes.push_back(node);
551 for (int i = nodes.size() - 1; i >= 0; --i) {
552 snapshot.addNode(nodes[i]);
555 virtual void clear() {
556 NodeNotifier* notifier = getNotifier();
558 for (notifier->first(node); node != INVALID; notifier->next(node)) {
559 snapshot.eraseNode(node);
566 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
569 EdgeObserverProxy(Snapshot& _snapshot)
570 : snapshot(_snapshot) {}
572 using EdgeNotifier::ObserverBase::attach;
573 using EdgeNotifier::ObserverBase::detach;
574 using EdgeNotifier::ObserverBase::attached;
578 virtual void add(const Edge& edge) {
579 snapshot.addEdge(edge);
581 virtual void add(const std::vector<Edge>& edges) {
582 for (int i = edges.size() - 1; i >= 0; ++i) {
583 snapshot.addEdge(edges[i]);
586 virtual void erase(const Edge& edge) {
587 snapshot.eraseEdge(edge);
589 virtual void erase(const std::vector<Edge>& edges) {
590 for (int i = 0; i < (int)edges.size(); ++i) {
591 snapshot.eraseEdge(edges[i]);
594 virtual void build() {
595 EdgeNotifier* notifier = getNotifier();
597 std::vector<Edge> edges;
598 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
599 edges.push_back(edge);
601 for (int i = edges.size() - 1; i >= 0; --i) {
602 snapshot.addEdge(edges[i]);
605 virtual void clear() {
606 EdgeNotifier* notifier = getNotifier();
608 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
609 snapshot.eraseEdge(edge);
618 NodeObserverProxy node_observer_proxy;
619 EdgeObserverProxy edge_observer_proxy;
621 std::list<Node> added_nodes;
622 std::list<Edge> added_edges;
625 void addNode(const Node& node) {
626 added_nodes.push_front(node);
628 void eraseNode(const Node& node) {
629 std::list<Node>::iterator it =
630 std::find(added_nodes.begin(), added_nodes.end(), node);
631 if (it == added_nodes.end()) {
633 edge_observer_proxy.detach();
634 throw NodeNotifier::ImmediateDetach();
636 added_nodes.erase(it);
640 void addEdge(const Edge& edge) {
641 added_edges.push_front(edge);
643 void eraseEdge(const Edge& edge) {
644 std::list<Edge>::iterator it =
645 std::find(added_edges.begin(), added_edges.end(), edge);
646 if (it == added_edges.end()) {
648 node_observer_proxy.detach();
649 throw EdgeNotifier::ImmediateDetach();
651 added_edges.erase(it);
655 void attach(ListGraph &_graph) {
657 node_observer_proxy.attach(graph->getNotifier(Node()));
658 edge_observer_proxy.attach(graph->getNotifier(Edge()));
662 node_observer_proxy.detach();
663 edge_observer_proxy.detach();
666 bool attached() const {
667 return node_observer_proxy.attached();
677 /// \brief Default constructor.
679 /// Default constructor.
680 /// To actually make a snapshot you must call save().
682 : graph(0), node_observer_proxy(*this),
683 edge_observer_proxy(*this) {}
685 /// \brief Constructor that immediately makes a snapshot.
687 /// This constructor immediately makes a snapshot of the graph.
688 /// \param _graph The graph we make a snapshot of.
689 Snapshot(ListGraph &_graph)
690 : node_observer_proxy(*this),
691 edge_observer_proxy(*this) {
695 /// \brief Make a snapshot.
697 /// Make a snapshot of the graph.
699 /// This function can be called more than once. In case of a repeated
700 /// call, the previous snapshot gets lost.
701 /// \param _graph The graph we make the snapshot of.
702 void save(ListGraph &_graph) {
710 /// \brief Undo the changes until the last snapshot.
712 /// Undo the changes until the last snapshot created by save().
715 for(std::list<Edge>::iterator it = added_edges.begin();
716 it != added_edges.end(); ++it) {
719 for(std::list<Node>::iterator it = added_nodes.begin();
720 it != added_nodes.end(); ++it) {
726 /// \brief Gives back true when the snapshot is valid.
728 /// Gives back true when the snapshot is valid.
738 /**************** Undirected List Graph ****************/
740 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
741 ExtendedListUGraphBase;
743 /// \addtogroup graphs
746 ///An undirected list graph class.
748 ///This is a simple and fast undirected graph implementation.
750 ///An important extra feature of this graph implementation is that
751 ///its maps are real \ref concept::ReferenceMap "reference map"s.
753 ///It conforms to the
754 ///\ref concept::UGraph "UGraph concept".
756 ///\sa concept::UGraph.
758 class ListUGraph : public ExtendedListUGraphBase {
760 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
762 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
764 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
765 ///\brief Assignment of ListUGraph to another one is \e not allowed.
766 ///Use UGraphCopy() instead.
768 ///Assignment of ListUGraph to another one is \e not allowed.
769 ///Use UGraphCopy() instead.
770 void operator=(const ListUGraph &) {}
778 typedef ExtendedListUGraphBase Parent;
779 /// \brief Add a new node to the graph.
781 /// \return the new node.
783 Node addNode() { return Parent::addNode(); }
785 /// \brief Add a new edge to the graph.
787 /// Add a new edge to the graph with source node \c s
788 /// and target node \c t.
789 /// \return the new undirected edge.
790 UEdge addEdge(const Node& s, const Node& t) {
791 return Parent::addEdge(s, t);
793 /// \brief Changes the source of \c e to \c n
795 /// Changes the source of \c e to \c n
797 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
798 ///referencing the changed edge remain
799 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
800 void changeSource(UEdge e, Node n) {
801 Parent::changeSource(e,n);
803 /// \brief Changes the target of \c e to \c n
805 /// Changes the target of \c e to \c n
807 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
808 /// valid. However the other iterators may be invalidated.
809 void changeTarget(UEdge e, Node n) {
810 Parent::changeTarget(e,n);
812 /// \brief Changes the source of \c e to \c n
814 /// Changes the source of \c e to \c n. It changes the proper
815 /// node of the represented undirected edge.
817 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
818 ///referencing the changed edge remain
819 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
820 void changeSource(Edge e, Node n) {
821 if (Parent::direction(e)) {
822 Parent::changeSource(e,n);
824 Parent::changeTarget(e,n);
827 /// \brief Changes the target of \c e to \c n
829 /// Changes the target of \c e to \c n. It changes the proper
830 /// node of the represented undirected edge.
832 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
833 ///referencing the changed edge remain
834 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
835 void changeTarget(Edge e, Node n) {
836 if (Parent::direction(e)) {
837 Parent::changeTarget(e,n);
839 Parent::changeSource(e,n);
842 /// \brief Contract two nodes.
844 /// This function contracts two nodes.
846 /// Node \p b will be removed but instead of deleting
847 /// its neighboring edges, they will be joined to \p a.
848 /// The last parameter \p r controls whether to remove loops. \c true
849 /// means that loops will be removed.
851 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
853 void contract(Node a, Node b, bool r = true) {
854 for(IncEdgeIt e(*this, b); e!=INVALID;) {
855 IncEdgeIt f = e; ++f;
856 if (r && runningNode(e) == a) {
858 } else if (source(e) == b) {
869 /// \brief Class to make a snapshot of the graph and restore
872 /// Class to make a snapshot of the graph and to restore it
875 /// The newly added nodes and undirected edges can be removed
876 /// using the restore() function.
878 /// \warning Edge and node deletions cannot be restored. This
879 /// events invalidate the snapshot.
883 typedef Parent::NodeNotifier NodeNotifier;
885 class NodeObserverProxy : public NodeNotifier::ObserverBase {
888 NodeObserverProxy(Snapshot& _snapshot)
889 : snapshot(_snapshot) {}
891 using NodeNotifier::ObserverBase::attach;
892 using NodeNotifier::ObserverBase::detach;
893 using NodeNotifier::ObserverBase::attached;
897 virtual void add(const Node& node) {
898 snapshot.addNode(node);
900 virtual void add(const std::vector<Node>& nodes) {
901 for (int i = nodes.size() - 1; i >= 0; ++i) {
902 snapshot.addNode(nodes[i]);
905 virtual void erase(const Node& node) {
906 snapshot.eraseNode(node);
908 virtual void erase(const std::vector<Node>& nodes) {
909 for (int i = 0; i < (int)nodes.size(); ++i) {
910 snapshot.eraseNode(nodes[i]);
913 virtual void build() {
914 NodeNotifier* notifier = getNotifier();
916 std::vector<Node> nodes;
917 for (notifier->first(node); node != INVALID; notifier->next(node)) {
918 nodes.push_back(node);
920 for (int i = nodes.size() - 1; i >= 0; --i) {
921 snapshot.addNode(nodes[i]);
924 virtual void clear() {
925 NodeNotifier* notifier = getNotifier();
927 for (notifier->first(node); node != INVALID; notifier->next(node)) {
928 snapshot.eraseNode(node);
935 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
938 UEdgeObserverProxy(Snapshot& _snapshot)
939 : snapshot(_snapshot) {}
941 using UEdgeNotifier::ObserverBase::attach;
942 using UEdgeNotifier::ObserverBase::detach;
943 using UEdgeNotifier::ObserverBase::attached;
947 virtual void add(const UEdge& edge) {
948 snapshot.addUEdge(edge);
950 virtual void add(const std::vector<UEdge>& edges) {
951 for (int i = edges.size() - 1; i >= 0; ++i) {
952 snapshot.addUEdge(edges[i]);
955 virtual void erase(const UEdge& edge) {
956 snapshot.eraseUEdge(edge);
958 virtual void erase(const std::vector<UEdge>& edges) {
959 for (int i = 0; i < (int)edges.size(); ++i) {
960 snapshot.eraseUEdge(edges[i]);
963 virtual void build() {
964 UEdgeNotifier* notifier = getNotifier();
966 std::vector<UEdge> edges;
967 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
968 edges.push_back(edge);
970 for (int i = edges.size() - 1; i >= 0; --i) {
971 snapshot.addUEdge(edges[i]);
974 virtual void clear() {
975 UEdgeNotifier* notifier = getNotifier();
977 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
978 snapshot.eraseUEdge(edge);
987 NodeObserverProxy node_observer_proxy;
988 UEdgeObserverProxy edge_observer_proxy;
990 std::list<Node> added_nodes;
991 std::list<UEdge> added_edges;
994 void addNode(const Node& node) {
995 added_nodes.push_front(node);
997 void eraseNode(const Node& node) {
998 std::list<Node>::iterator it =
999 std::find(added_nodes.begin(), added_nodes.end(), node);
1000 if (it == added_nodes.end()) {
1002 edge_observer_proxy.detach();
1003 throw NodeNotifier::ImmediateDetach();
1005 added_nodes.erase(it);
1009 void addUEdge(const UEdge& edge) {
1010 added_edges.push_front(edge);
1012 void eraseUEdge(const UEdge& edge) {
1013 std::list<UEdge>::iterator it =
1014 std::find(added_edges.begin(), added_edges.end(), edge);
1015 if (it == added_edges.end()) {
1017 node_observer_proxy.detach();
1018 throw UEdgeNotifier::ImmediateDetach();
1020 added_edges.erase(it);
1024 void attach(ListUGraph &_graph) {
1026 node_observer_proxy.attach(graph->getNotifier(Node()));
1027 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1031 node_observer_proxy.detach();
1032 edge_observer_proxy.detach();
1035 bool attached() const {
1036 return node_observer_proxy.attached();
1040 added_nodes.clear();
1041 added_edges.clear();
1046 /// \brief Default constructor.
1048 /// Default constructor.
1049 /// To actually make a snapshot you must call save().
1051 : graph(0), node_observer_proxy(*this),
1052 edge_observer_proxy(*this) {}
1054 /// \brief Constructor that immediately makes a snapshot.
1056 /// This constructor immediately makes a snapshot of the graph.
1057 /// \param _graph The graph we make a snapshot of.
1058 Snapshot(ListUGraph &_graph)
1059 : node_observer_proxy(*this),
1060 edge_observer_proxy(*this) {
1064 /// \brief Make a snapshot.
1066 /// Make a snapshot of the graph.
1068 /// This function can be called more than once. In case of a repeated
1069 /// call, the previous snapshot gets lost.
1070 /// \param _graph The graph we make the snapshot of.
1071 void save(ListUGraph &_graph) {
1079 /// \brief Undo the changes until the last snapshot.
1081 /// Undo the changes until the last snapshot created by save().
1084 for(std::list<UEdge>::iterator it = added_edges.begin();
1085 it != added_edges.end(); ++it) {
1088 for(std::list<Node>::iterator it = added_nodes.begin();
1089 it != added_nodes.end(); ++it) {
1095 /// \brief Gives back true when the snapshot is valid.
1097 /// Gives back true when the snapshot is valid.
1098 bool valid() const {
1105 class ListBpUGraphBase {
1108 class NodeSetError : public LogicError {
1110 virtual const char* what() const throw() {
1111 return "lemon::ListBpUGraph::NodeSetError";
1118 int first_edge, prev, next;
1122 int aNode, prev_out, next_out;
1123 int bNode, prev_in, next_in;
1126 std::vector<NodeT> aNodes;
1127 std::vector<NodeT> bNodes;
1129 std::vector<UEdgeT> edges;
1132 int first_free_anode;
1135 int first_free_bnode;
1137 int first_free_edge;
1142 friend class ListBpUGraphBase;
1146 explicit Node(int _id) : id(_id) {}
1149 Node(Invalid) { id = -1; }
1150 bool operator==(const Node i) const {return id==i.id;}
1151 bool operator!=(const Node i) const {return id!=i.id;}
1152 bool operator<(const Node i) const {return id<i.id;}
1156 friend class ListBpUGraphBase;
1160 explicit UEdge(int _id) { id = _id;}
1163 UEdge (Invalid) { id = -1; }
1164 bool operator==(const UEdge i) const {return id==i.id;}
1165 bool operator!=(const UEdge i) const {return id!=i.id;}
1166 bool operator<(const UEdge i) const {return id<i.id;}
1170 : first_anode(-1), first_free_anode(-1),
1171 first_bnode(-1), first_free_bnode(-1),
1172 first_free_edge(-1) {}
1174 void firstANode(Node& node) const {
1175 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1177 void nextANode(Node& node) const {
1178 node.id = aNodes[node.id >> 1].next;
1181 void firstBNode(Node& node) const {
1182 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1184 void nextBNode(Node& node) const {
1185 node.id = bNodes[node.id >> 1].next;
1188 void first(Node& node) const {
1189 if (first_anode != -1) {
1190 node.id = (first_anode << 1);
1191 } else if (first_bnode != -1) {
1192 node.id = (first_bnode << 1) + 1;
1197 void next(Node& node) const {
1199 node.id = aNodes[node.id >> 1].next;
1200 if (node.id == -1) {
1201 if (first_bnode != -1) {
1202 node.id = (first_bnode << 1) + 1;
1206 node.id = bNodes[node.id >> 1].next;
1210 void first(UEdge& edge) const {
1211 int aNodeId = first_anode;
1212 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1213 aNodeId = aNodes[aNodeId].next != -1 ?
1214 aNodes[aNodeId].next >> 1 : -1;
1216 if (aNodeId != -1) {
1217 edge.id = aNodes[aNodeId].first_edge;
1222 void next(UEdge& edge) const {
1223 int aNodeId = edges[edge.id].aNode >> 1;
1224 edge.id = edges[edge.id].next_out;
1225 if (edge.id == -1) {
1226 aNodeId = aNodes[aNodeId].next != -1 ?
1227 aNodes[aNodeId].next >> 1 : -1;
1228 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1229 aNodeId = aNodes[aNodeId].next != -1 ?
1230 aNodes[aNodeId].next >> 1 : -1;
1232 if (aNodeId != -1) {
1233 edge.id = aNodes[aNodeId].first_edge;
1240 void firstFromANode(UEdge& edge, const Node& node) const {
1241 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1242 edge.id = aNodes[node.id >> 1].first_edge;
1244 void nextFromANode(UEdge& edge) const {
1245 edge.id = edges[edge.id].next_out;
1248 void firstFromBNode(UEdge& edge, const Node& node) const {
1249 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1250 edge.id = bNodes[node.id >> 1].first_edge;
1252 void nextFromBNode(UEdge& edge) const {
1253 edge.id = edges[edge.id].next_in;
1256 static int id(const Node& node) {
1259 static Node nodeFromId(int id) {
1262 int maxNodeId() const {
1263 return aNodes.size() > bNodes.size() ?
1264 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1267 static int id(const UEdge& edge) {
1270 static UEdge uEdgeFromId(int id) {
1273 int maxUEdgeId() const {
1274 return edges.size();
1277 static int aNodeId(const Node& node) {
1278 return node.id >> 1;
1280 static Node nodeFromANodeId(int id) {
1281 return Node(id << 1);
1283 int maxANodeId() const {
1284 return aNodes.size();
1287 static int bNodeId(const Node& node) {
1288 return node.id >> 1;
1290 static Node nodeFromBNodeId(int id) {
1291 return Node((id << 1) + 1);
1293 int maxBNodeId() const {
1294 return bNodes.size();
1297 Node aNode(const UEdge& edge) const {
1298 return Node(edges[edge.id].aNode);
1300 Node bNode(const UEdge& edge) const {
1301 return Node(edges[edge.id].bNode);
1304 static bool aNode(const Node& node) {
1305 return (node.id & 1) == 0;
1308 static bool bNode(const Node& node) {
1309 return (node.id & 1) == 1;
1314 if (first_free_anode == -1) {
1315 aNodeId = aNodes.size();
1316 aNodes.push_back(NodeT());
1318 aNodeId = first_free_anode;
1319 first_free_anode = aNodes[first_free_anode].next;
1321 if (first_anode != -1) {
1322 aNodes[aNodeId].next = first_anode << 1;
1323 aNodes[first_anode].prev = aNodeId << 1;
1325 aNodes[aNodeId].next = -1;
1327 aNodes[aNodeId].prev = -1;
1328 first_anode = aNodeId;
1329 aNodes[aNodeId].first_edge = -1;
1330 return Node(aNodeId << 1);
1335 if (first_free_bnode == -1) {
1336 bNodeId = bNodes.size();
1337 bNodes.push_back(NodeT());
1339 bNodeId = first_free_bnode;
1340 first_free_bnode = bNodes[first_free_bnode].next;
1342 if (first_bnode != -1) {
1343 bNodes[bNodeId].next = (first_bnode << 1) + 1;
1344 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1346 bNodes[bNodeId].next = -1;
1348 bNodes[bNodeId].prev = -1;
1349 first_bnode = bNodeId;
1350 bNodes[bNodeId].first_edge = -1;
1351 return Node((bNodeId << 1) + 1);
1354 UEdge addEdge(const Node& source, const Node& target) {
1355 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1357 if (first_free_edge != -1) {
1358 edgeId = first_free_edge;
1359 first_free_edge = edges[edgeId].next_out;
1361 edgeId = edges.size();
1362 edges.push_back(UEdgeT());
1364 if ((source.id & 1) == 0) {
1365 edges[edgeId].aNode = source.id;
1366 edges[edgeId].bNode = target.id;
1368 edges[edgeId].aNode = target.id;
1369 edges[edgeId].bNode = source.id;
1371 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1372 edges[edgeId].prev_out = -1;
1373 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1374 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1376 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1377 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1378 edges[edgeId].prev_in = -1;
1379 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1380 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1382 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1383 return UEdge(edgeId);
1386 void erase(const Node& node) {
1388 int aNodeId = node.id >> 1;
1389 if (aNodes[aNodeId].prev != -1) {
1390 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1393 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
1395 if (aNodes[aNodeId].next != -1) {
1396 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1398 aNodes[aNodeId].next = first_free_anode;
1399 first_free_anode = aNodeId;
1401 int bNodeId = node.id >> 1;
1402 if (bNodes[bNodeId].prev != -1) {
1403 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1406 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
1408 if (bNodes[bNodeId].next != -1) {
1409 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1411 bNodes[bNodeId].next = first_free_bnode;
1412 first_free_bnode = bNodeId;
1416 void erase(const UEdge& edge) {
1418 if (edges[edge.id].prev_out != -1) {
1419 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1421 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1423 if (edges[edge.id].next_out != -1) {
1424 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1427 if (edges[edge.id].prev_in != -1) {
1428 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1430 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1432 if (edges[edge.id].next_in != -1) {
1433 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1436 edges[edge.id].next_out = first_free_edge;
1437 first_free_edge = edge.id;
1445 first_free_anode = -1;
1447 first_free_bnode = -1;
1448 first_free_edge = -1;
1451 void changeANode(const UEdge& edge, const Node& node) {
1452 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1453 if (edges[edge.id].prev_out != -1) {
1454 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1456 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1458 if (edges[edge.id].next_out != -1) {
1459 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1461 if (aNodes[node.id >> 1].first_edge != -1) {
1462 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1464 edges[edge.id].prev_out = -1;
1465 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1466 aNodes[node.id >> 1].first_edge = edge.id;
1467 edges[edge.id].aNode = node.id;
1470 void changeBNode(const UEdge& edge, const Node& node) {
1471 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1472 if (edges[edge.id].prev_in != -1) {
1473 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1475 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1477 if (edges[edge.id].next_in != -1) {
1478 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1480 if (bNodes[node.id >> 1].first_edge != -1) {
1481 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1483 edges[edge.id].prev_in = -1;
1484 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1485 bNodes[node.id >> 1].first_edge = edge.id;
1486 edges[edge.id].bNode = node.id;
1492 typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1493 ExtendedListBpUGraphBase;
1497 /// \brief A smart bipartite undirected graph class.
1499 /// This is a bipartite undirected graph implementation.
1500 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
1502 ///An important extra feature of this graph implementation is that
1503 ///its maps are real \ref concept::ReferenceMap "reference map"s.
1505 /// \sa concept::BpUGraph.
1507 class ListBpUGraph : public ExtendedListBpUGraphBase {
1508 /// \brief ListBpUGraph is \e not copy constructible.
1510 ///ListBpUGraph is \e not copy constructible.
1511 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1512 /// \brief Assignment of ListBpUGraph to another one is \e not
1515 /// Assignment of ListBpUGraph to another one is \e not allowed.
1516 void operator=(const ListBpUGraph &) {}
1518 /// \brief Constructor
1524 typedef ExtendedListBpUGraphBase Parent;
1525 /// \brief Add a new ANode to the graph.
1527 /// \return the new node.
1529 Node addANode() { return Parent::addANode(); }
1531 /// \brief Add a new BNode to the graph.
1533 /// \return the new node.
1535 Node addBNode() { return Parent::addBNode(); }
1537 /// \brief Add a new edge to the graph.
1539 /// Add a new edge to the graph with an ANode and a BNode.
1540 /// \return the new undirected edge.
1541 UEdge addEdge(const Node& s, const Node& t) {
1542 return Parent::addEdge(s, t);
1545 /// \brief Changes the ANode of \c e to \c n
1547 /// Changes the ANode of \c e to \c n
1549 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1550 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1552 void changeANode(UEdge e, Node n) {
1553 Parent::changeANode(e,n);
1556 /// \brief Changes the BNode of \c e to \c n
1558 /// Changes the BNode of \c e to \c n
1560 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1561 /// referencing the changed edge remain
1562 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1563 void changeBNode(UEdge e, Node n) {
1564 Parent::changeBNode(e,n);
1567 /// \brief Changes the source(ANode) of \c e to \c n
1569 /// Changes the source(ANode) of \c e to \c n
1571 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1572 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1574 void changeSource(UEdge e, Node n) {
1575 Parent::changeANode(e,n);
1578 /// \brief Changes the target(BNode) of \c e to \c n
1580 /// Changes the target(BNode) of \c e to \c n
1582 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1583 /// referencing the changed edge remain
1584 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1585 void changeTarget(UEdge e, Node n) {
1586 Parent::changeBNode(e,n);
1589 /// \brief Changes the source of \c e to \c n
1591 /// Changes the source of \c e to \c n. It changes the proper
1592 /// node of the represented undirected edge.
1594 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1595 ///referencing the changed edge remain
1596 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1597 void changeSource(Edge e, Node n) {
1598 if (Parent::direction(e)) {
1599 Parent::changeANode(e,n);
1601 Parent::changeBNode(e,n);
1604 /// \brief Changes the target of \c e to \c n
1606 /// Changes the target of \c e to \c n. It changes the proper
1607 /// node of the represented undirected edge.
1609 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1610 ///referencing the changed edge remain
1611 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1612 void changeTarget(Edge e, Node n) {
1613 if (Parent::direction(e)) {
1614 Parent::changeBNode(e,n);
1616 Parent::changeANode(e,n);
1619 /// \brief Contract two nodes.
1621 /// This function contracts two nodes.
1623 /// Node \p b will be removed but instead of deleting its
1624 /// neighboring edges, they will be joined to \p a. The two nodes
1625 /// should be from the same nodeset, of course.
1627 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1629 void contract(const Node& a, const Node& b) {
1630 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1631 if (Parent::aNode(a)) {
1632 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1633 IncEdgeIt f = e; ++f;
1638 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1639 IncEdgeIt f = e; ++f;
1647 /// \brief Class to make a snapshot of the graph and restore
1650 /// Class to make a snapshot of the graph and to restore it
1653 /// The newly added nodes and undirected edges can be removed
1654 /// using the restore() function.
1656 /// \warning Edge and node deletions cannot be restored. This
1657 /// events invalidate the snapshot.
1661 typedef Parent::NodeNotifier NodeNotifier;
1663 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1666 NodeObserverProxy(Snapshot& _snapshot)
1667 : snapshot(_snapshot) {}
1669 using NodeNotifier::ObserverBase::attach;
1670 using NodeNotifier::ObserverBase::detach;
1671 using NodeNotifier::ObserverBase::attached;
1675 virtual void add(const Node& node) {
1676 snapshot.addNode(node);
1678 virtual void add(const std::vector<Node>& nodes) {
1679 for (int i = nodes.size() - 1; i >= 0; ++i) {
1680 snapshot.addNode(nodes[i]);
1683 virtual void erase(const Node& node) {
1684 snapshot.eraseNode(node);
1686 virtual void erase(const std::vector<Node>& nodes) {
1687 for (int i = 0; i < (int)nodes.size(); ++i) {
1688 snapshot.eraseNode(nodes[i]);
1691 virtual void build() {
1692 NodeNotifier* notifier = getNotifier();
1694 std::vector<Node> nodes;
1695 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1696 nodes.push_back(node);
1698 for (int i = nodes.size() - 1; i >= 0; --i) {
1699 snapshot.addNode(nodes[i]);
1702 virtual void clear() {
1703 NodeNotifier* notifier = getNotifier();
1705 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1706 snapshot.eraseNode(node);
1713 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1716 UEdgeObserverProxy(Snapshot& _snapshot)
1717 : snapshot(_snapshot) {}
1719 using UEdgeNotifier::ObserverBase::attach;
1720 using UEdgeNotifier::ObserverBase::detach;
1721 using UEdgeNotifier::ObserverBase::attached;
1725 virtual void add(const UEdge& edge) {
1726 snapshot.addUEdge(edge);
1728 virtual void add(const std::vector<UEdge>& edges) {
1729 for (int i = edges.size() - 1; i >= 0; ++i) {
1730 snapshot.addUEdge(edges[i]);
1733 virtual void erase(const UEdge& edge) {
1734 snapshot.eraseUEdge(edge);
1736 virtual void erase(const std::vector<UEdge>& edges) {
1737 for (int i = 0; i < (int)edges.size(); ++i) {
1738 snapshot.eraseUEdge(edges[i]);
1741 virtual void build() {
1742 UEdgeNotifier* notifier = getNotifier();
1744 std::vector<UEdge> edges;
1745 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1746 edges.push_back(edge);
1748 for (int i = edges.size() - 1; i >= 0; --i) {
1749 snapshot.addUEdge(edges[i]);
1752 virtual void clear() {
1753 UEdgeNotifier* notifier = getNotifier();
1755 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1756 snapshot.eraseUEdge(edge);
1763 ListBpUGraph *graph;
1765 NodeObserverProxy node_observer_proxy;
1766 UEdgeObserverProxy edge_observer_proxy;
1768 std::list<Node> added_nodes;
1769 std::list<UEdge> added_edges;
1772 void addNode(const Node& node) {
1773 added_nodes.push_front(node);
1775 void eraseNode(const Node& node) {
1776 std::list<Node>::iterator it =
1777 std::find(added_nodes.begin(), added_nodes.end(), node);
1778 if (it == added_nodes.end()) {
1780 edge_observer_proxy.detach();
1781 throw NodeNotifier::ImmediateDetach();
1783 added_nodes.erase(it);
1787 void addUEdge(const UEdge& edge) {
1788 added_edges.push_front(edge);
1790 void eraseUEdge(const UEdge& edge) {
1791 std::list<UEdge>::iterator it =
1792 std::find(added_edges.begin(), added_edges.end(), edge);
1793 if (it == added_edges.end()) {
1795 node_observer_proxy.detach();
1796 throw UEdgeNotifier::ImmediateDetach();
1798 added_edges.erase(it);
1802 void attach(ListBpUGraph &_graph) {
1804 node_observer_proxy.attach(graph->getNotifier(Node()));
1805 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1809 node_observer_proxy.detach();
1810 edge_observer_proxy.detach();
1813 bool attached() const {
1814 return node_observer_proxy.attached();
1818 added_nodes.clear();
1819 added_edges.clear();
1824 /// \brief Default constructor.
1826 /// Default constructor.
1827 /// To actually make a snapshot you must call save().
1829 : graph(0), node_observer_proxy(*this),
1830 edge_observer_proxy(*this) {}
1832 /// \brief Constructor that immediately makes a snapshot.
1834 /// This constructor immediately makes a snapshot of the graph.
1835 /// \param _graph The graph we make a snapshot of.
1836 Snapshot(ListBpUGraph &_graph)
1837 : node_observer_proxy(*this),
1838 edge_observer_proxy(*this) {
1842 /// \brief Make a snapshot.
1844 /// Make a snapshot of the graph.
1846 /// This function can be called more than once. In case of a repeated
1847 /// call, the previous snapshot gets lost.
1848 /// \param _graph The graph we make the snapshot of.
1849 void save(ListBpUGraph &_graph) {
1857 /// \brief Undo the changes until the last snapshot.
1859 /// Undo the changes until the last snapshot created by save().
1862 for(std::list<UEdge>::iterator it = added_edges.begin();
1863 it != added_edges.end(); ++it) {
1866 for(std::list<Node>::iterator it = added_nodes.begin();
1867 it != added_nodes.end(); ++it) {
1873 /// \brief Gives back true when the snapshot is valid.
1875 /// Gives back true when the snapshot is valid.
1876 bool valid() const {