Interface to the cplex MIP solver: it is little, a bit sour but it is ours.
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.
325 ///\sa concept::Graph.
327 class ListGraph : public ExtendedListGraphBase {
329 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
331 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
333 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
334 ///\brief Assignment of ListGraph to another one is \e not allowed.
335 ///Use GraphCopy() instead.
337 ///Assignment of ListGraph to another one is \e not allowed.
338 ///Use GraphCopy() instead.
339 void operator=(const ListGraph &) {}
342 typedef ExtendedListGraphBase Parent;
350 ///Add a new node to the graph.
352 /// \return the new node.
354 Node addNode() { return Parent::addNode(); }
356 ///Add a new edge to the graph.
358 ///Add a new edge to the graph with source node \c s
359 ///and target node \c t.
360 ///\return the new edge.
361 Edge addEdge(const Node& s, const Node& t) {
362 return Parent::addEdge(s, t);
365 /// Changes the target of \c e to \c n
367 /// Changes the target of \c e to \c n
369 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
370 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
372 ///\warning This functionality cannot be used together with the Snapshot
374 void changeTarget(Edge e, Node n) {
375 Parent::changeTarget(e,n);
377 /// Changes the source of \c e to \c n
379 /// Changes the source of \c e to \c n
381 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
382 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
384 ///\warning This functionality cannot be used together with the Snapshot
386 void changeSource(Edge e, Node n) {
387 Parent::changeSource(e,n);
390 /// Invert the direction of an edge.
392 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
393 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
395 ///\warning This functionality cannot be used together with the Snapshot
397 void reverseEdge(Edge e) {
399 changeTarget(e,source(e));
403 /// \brief Using this it is possible to avoid the superfluous memory
406 ///Using this it is possible to avoid the superfluous memory
407 ///allocation: if you know that the graph you want to build will
408 ///contain at least 10 million nodes then it is worth reserving
409 ///space for this amount before starting to build the graph.
410 void reserveNode(int n) { nodes.reserve(n); };
412 /// \brief Using this it is possible to avoid the superfluous memory
415 ///Using this it is possible to avoid the superfluous memory
416 ///allocation: see the \ref reserveNode function.
417 void reserveEdge(int n) { edges.reserve(n); };
420 ///Contract two nodes.
422 ///This function contracts two nodes.
424 ///Node \p b will be removed but instead of deleting
425 ///incident edges, they will be joined to \p a.
426 ///The last parameter \p r controls whether to remove loops. \c true
427 ///means that loops will be removed.
429 ///\note The <tt>EdgeIt</tt>s
430 ///referencing a moved edge remain
431 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
432 ///may be invalidated.
433 ///\warning This functionality cannot be used together with the Snapshot
435 void contract(Node a, Node b, bool r = true)
437 for(OutEdgeIt e(*this,b);e!=INVALID;) {
440 if(r && target(e)==a) erase(e);
441 else changeSource(e,a);
444 for(InEdgeIt e(*this,b);e!=INVALID;) {
447 if(r && source(e)==a) erase(e);
448 else changeTarget(e,a);
456 ///This function splits a node. First a new node is added to the graph,
457 ///then the source of each outgoing edge of \c n is moved to this new node.
458 ///If \c connect is \c true (this is the default value), then a new edge
459 ///from \c n to the newly created node is also added.
460 ///\return The newly created node.
462 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
463 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
466 ///\warning This functionality cannot be used together with the
467 ///Snapshot feature. \todo It could be implemented in a bit
469 Node split(Node n, bool connect = true) {
471 for(OutEdgeIt e(*this,n);e!=INVALID;) {
477 if (connect) addEdge(n,b);
483 ///This function splits an edge. First a new node \c b is added to
484 ///the graph, then the original edge is re-targeted to \c
485 ///b. Finally an edge from \c b to the original target is added.
486 ///\return The newly created node.
487 ///\warning This functionality
488 ///cannot be used together with the Snapshot feature.
491 addEdge(b,target(e));
496 /// \brief Class to make a snapshot of the graph and restore
499 /// Class to make a snapshot of the graph and to restore it
502 /// The newly added nodes and edges can be removed using the
503 /// restore() function.
505 /// \warning Edge and node deletions cannot be restored. This
506 /// events invalidate the snapshot.
510 typedef Parent::NodeNotifier NodeNotifier;
512 class NodeObserverProxy : public NodeNotifier::ObserverBase {
515 NodeObserverProxy(Snapshot& _snapshot)
516 : snapshot(_snapshot) {}
518 using NodeNotifier::ObserverBase::attach;
519 using NodeNotifier::ObserverBase::detach;
520 using NodeNotifier::ObserverBase::attached;
524 virtual void add(const Node& node) {
525 snapshot.addNode(node);
527 virtual void add(const std::vector<Node>& nodes) {
528 for (int i = nodes.size() - 1; i >= 0; ++i) {
529 snapshot.addNode(nodes[i]);
532 virtual void erase(const Node& node) {
533 snapshot.eraseNode(node);
535 virtual void erase(const std::vector<Node>& nodes) {
536 for (int i = 0; i < (int)nodes.size(); ++i) {
537 snapshot.eraseNode(nodes[i]);
540 virtual void build() {
541 NodeNotifier* notifier = getNotifier();
543 std::vector<Node> nodes;
544 for (notifier->first(node); node != INVALID; notifier->next(node)) {
545 nodes.push_back(node);
547 for (int i = nodes.size() - 1; i >= 0; --i) {
548 snapshot.addNode(nodes[i]);
551 virtual void clear() {
552 NodeNotifier* notifier = getNotifier();
554 for (notifier->first(node); node != INVALID; notifier->next(node)) {
555 snapshot.eraseNode(node);
562 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
565 EdgeObserverProxy(Snapshot& _snapshot)
566 : snapshot(_snapshot) {}
568 using EdgeNotifier::ObserverBase::attach;
569 using EdgeNotifier::ObserverBase::detach;
570 using EdgeNotifier::ObserverBase::attached;
574 virtual void add(const Edge& edge) {
575 snapshot.addEdge(edge);
577 virtual void add(const std::vector<Edge>& edges) {
578 for (int i = edges.size() - 1; i >= 0; ++i) {
579 snapshot.addEdge(edges[i]);
582 virtual void erase(const Edge& edge) {
583 snapshot.eraseEdge(edge);
585 virtual void erase(const std::vector<Edge>& edges) {
586 for (int i = 0; i < (int)edges.size(); ++i) {
587 snapshot.eraseEdge(edges[i]);
590 virtual void build() {
591 EdgeNotifier* notifier = getNotifier();
593 std::vector<Edge> edges;
594 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
595 edges.push_back(edge);
597 for (int i = edges.size() - 1; i >= 0; --i) {
598 snapshot.addEdge(edges[i]);
601 virtual void clear() {
602 EdgeNotifier* notifier = getNotifier();
604 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
605 snapshot.eraseEdge(edge);
614 NodeObserverProxy node_observer_proxy;
615 EdgeObserverProxy edge_observer_proxy;
617 std::list<Node> added_nodes;
618 std::list<Edge> added_edges;
621 void addNode(const Node& node) {
622 added_nodes.push_front(node);
624 void eraseNode(const Node& node) {
625 std::list<Node>::iterator it =
626 std::find(added_nodes.begin(), added_nodes.end(), node);
627 if (it == added_nodes.end()) {
629 edge_observer_proxy.detach();
630 throw NodeNotifier::ImmediateDetach();
632 added_nodes.erase(it);
636 void addEdge(const Edge& edge) {
637 added_edges.push_front(edge);
639 void eraseEdge(const Edge& edge) {
640 std::list<Edge>::iterator it =
641 std::find(added_edges.begin(), added_edges.end(), edge);
642 if (it == added_edges.end()) {
644 node_observer_proxy.detach();
645 throw EdgeNotifier::ImmediateDetach();
647 added_edges.erase(it);
651 void attach(ListGraph &_graph) {
653 node_observer_proxy.attach(graph->getNotifier(Node()));
654 edge_observer_proxy.attach(graph->getNotifier(Edge()));
658 node_observer_proxy.detach();
659 edge_observer_proxy.detach();
662 bool attached() const {
663 return node_observer_proxy.attached();
673 /// \brief Default constructor.
675 /// Default constructor.
676 /// To actually make a snapshot you must call save().
678 : graph(0), node_observer_proxy(*this),
679 edge_observer_proxy(*this) {}
681 /// \brief Constructor that immediately makes a snapshot.
683 /// This constructor immediately makes a snapshot of the graph.
684 /// \param _graph The graph we make a snapshot of.
685 Snapshot(ListGraph &_graph)
686 : node_observer_proxy(*this),
687 edge_observer_proxy(*this) {
691 /// \brief Make a snapshot.
693 /// Make a snapshot of the graph.
695 /// This function can be called more than once. In case of a repeated
696 /// call, the previous snapshot gets lost.
697 /// \param _graph The graph we make the snapshot of.
698 void save(ListGraph &_graph) {
706 /// \brief Undo the changes until the last snapshot.
708 /// Undo the changes until the last snapshot created by save().
711 for(std::list<Edge>::iterator it = added_edges.begin();
712 it != added_edges.end(); ++it) {
715 for(std::list<Node>::iterator it = added_nodes.begin();
716 it != added_nodes.end(); ++it) {
722 /// \brief Gives back true when the snapshot is valid.
724 /// Gives back true when the snapshot is valid.
734 /**************** Undirected List Graph ****************/
736 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
737 ExtendedListUGraphBase;
739 /// \addtogroup graphs
742 ///An undirected list graph class.
744 ///This is a simple and fast undirected graph implementation.
746 ///It conforms to the
747 ///\ref concept::UGraph "UGraph concept".
749 ///\sa concept::UGraph.
751 class ListUGraph : public ExtendedListUGraphBase {
753 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
755 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
757 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
758 ///\brief Assignment of ListUGraph to another one is \e not allowed.
759 ///Use UGraphCopy() instead.
761 ///Assignment of ListUGraph to another one is \e not allowed.
762 ///Use UGraphCopy() instead.
763 void operator=(const ListUGraph &) {}
771 typedef ExtendedListUGraphBase Parent;
772 /// \brief Add a new node to the graph.
774 /// \return the new node.
776 Node addNode() { return Parent::addNode(); }
778 /// \brief Add a new edge to the graph.
780 /// Add a new edge to the graph with source node \c s
781 /// and target node \c t.
782 /// \return the new undirected edge.
783 UEdge addEdge(const Node& s, const Node& t) {
784 return Parent::addEdge(s, t);
786 /// \brief Changes the source of \c e to \c n
788 /// Changes the source of \c e to \c n
790 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
791 ///referencing the changed edge remain
792 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
793 void changeSource(UEdge e, Node n) {
794 Parent::changeSource(e,n);
796 /// \brief Changes the target of \c e to \c n
798 /// Changes the target of \c e to \c n
800 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
801 /// valid. However the other iterators may be invalidated.
802 void changeTarget(UEdge e, Node n) {
803 Parent::changeTarget(e,n);
805 /// \brief Changes the source of \c e to \c n
807 /// Changes the source of \c e to \c n. It changes the proper
808 /// node of the represented undirected edge.
810 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
811 ///referencing the changed edge remain
812 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
813 void changeSource(Edge e, Node n) {
814 if (Parent::direction(e)) {
815 Parent::changeSource(e,n);
817 Parent::changeTarget(e,n);
820 /// \brief Changes the target of \c e to \c n
822 /// Changes the target of \c e to \c n. It changes the proper
823 /// node of the represented undirected edge.
825 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
826 ///referencing the changed edge remain
827 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
828 void changeTarget(Edge e, Node n) {
829 if (Parent::direction(e)) {
830 Parent::changeTarget(e,n);
832 Parent::changeSource(e,n);
835 /// \brief Contract two nodes.
837 /// This function contracts two nodes.
839 /// Node \p b will be removed but instead of deleting
840 /// its neighboring edges, they will be joined to \p a.
841 /// The last parameter \p r controls whether to remove loops. \c true
842 /// means that loops will be removed.
844 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
846 void contract(Node a, Node b, bool r = true) {
847 for(IncEdgeIt e(*this, b); e!=INVALID;) {
848 IncEdgeIt f = e; ++f;
849 if (r && runningNode(e) == a) {
851 } else if (source(e) == b) {
862 /// \brief Class to make a snapshot of the graph and restore
865 /// Class to make a snapshot of the graph and to restore it
868 /// The newly added nodes and undirected edges can be removed
869 /// using the restore() function.
871 /// \warning Edge and node deletions cannot be restored. This
872 /// events invalidate the snapshot.
876 typedef Parent::NodeNotifier NodeNotifier;
878 class NodeObserverProxy : public NodeNotifier::ObserverBase {
881 NodeObserverProxy(Snapshot& _snapshot)
882 : snapshot(_snapshot) {}
884 using NodeNotifier::ObserverBase::attach;
885 using NodeNotifier::ObserverBase::detach;
886 using NodeNotifier::ObserverBase::attached;
890 virtual void add(const Node& node) {
891 snapshot.addNode(node);
893 virtual void add(const std::vector<Node>& nodes) {
894 for (int i = nodes.size() - 1; i >= 0; ++i) {
895 snapshot.addNode(nodes[i]);
898 virtual void erase(const Node& node) {
899 snapshot.eraseNode(node);
901 virtual void erase(const std::vector<Node>& nodes) {
902 for (int i = 0; i < (int)nodes.size(); ++i) {
903 snapshot.eraseNode(nodes[i]);
906 virtual void build() {
907 NodeNotifier* notifier = getNotifier();
909 std::vector<Node> nodes;
910 for (notifier->first(node); node != INVALID; notifier->next(node)) {
911 nodes.push_back(node);
913 for (int i = nodes.size() - 1; i >= 0; --i) {
914 snapshot.addNode(nodes[i]);
917 virtual void clear() {
918 NodeNotifier* notifier = getNotifier();
920 for (notifier->first(node); node != INVALID; notifier->next(node)) {
921 snapshot.eraseNode(node);
928 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
931 UEdgeObserverProxy(Snapshot& _snapshot)
932 : snapshot(_snapshot) {}
934 using UEdgeNotifier::ObserverBase::attach;
935 using UEdgeNotifier::ObserverBase::detach;
936 using UEdgeNotifier::ObserverBase::attached;
940 virtual void add(const UEdge& edge) {
941 snapshot.addUEdge(edge);
943 virtual void add(const std::vector<UEdge>& edges) {
944 for (int i = edges.size() - 1; i >= 0; ++i) {
945 snapshot.addUEdge(edges[i]);
948 virtual void erase(const UEdge& edge) {
949 snapshot.eraseUEdge(edge);
951 virtual void erase(const std::vector<UEdge>& edges) {
952 for (int i = 0; i < (int)edges.size(); ++i) {
953 snapshot.eraseUEdge(edges[i]);
956 virtual void build() {
957 UEdgeNotifier* notifier = getNotifier();
959 std::vector<UEdge> edges;
960 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
961 edges.push_back(edge);
963 for (int i = edges.size() - 1; i >= 0; --i) {
964 snapshot.addUEdge(edges[i]);
967 virtual void clear() {
968 UEdgeNotifier* notifier = getNotifier();
970 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
971 snapshot.eraseUEdge(edge);
980 NodeObserverProxy node_observer_proxy;
981 UEdgeObserverProxy edge_observer_proxy;
983 std::list<Node> added_nodes;
984 std::list<UEdge> added_edges;
987 void addNode(const Node& node) {
988 added_nodes.push_front(node);
990 void eraseNode(const Node& node) {
991 std::list<Node>::iterator it =
992 std::find(added_nodes.begin(), added_nodes.end(), node);
993 if (it == added_nodes.end()) {
995 edge_observer_proxy.detach();
996 throw NodeNotifier::ImmediateDetach();
998 added_nodes.erase(it);
1002 void addUEdge(const UEdge& edge) {
1003 added_edges.push_front(edge);
1005 void eraseUEdge(const UEdge& edge) {
1006 std::list<UEdge>::iterator it =
1007 std::find(added_edges.begin(), added_edges.end(), edge);
1008 if (it == added_edges.end()) {
1010 node_observer_proxy.detach();
1011 throw UEdgeNotifier::ImmediateDetach();
1013 added_edges.erase(it);
1017 void attach(ListUGraph &_graph) {
1019 node_observer_proxy.attach(graph->getNotifier(Node()));
1020 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1024 node_observer_proxy.detach();
1025 edge_observer_proxy.detach();
1028 bool attached() const {
1029 return node_observer_proxy.attached();
1033 added_nodes.clear();
1034 added_edges.clear();
1039 /// \brief Default constructor.
1041 /// Default constructor.
1042 /// To actually make a snapshot you must call save().
1044 : graph(0), node_observer_proxy(*this),
1045 edge_observer_proxy(*this) {}
1047 /// \brief Constructor that immediately makes a snapshot.
1049 /// This constructor immediately makes a snapshot of the graph.
1050 /// \param _graph The graph we make a snapshot of.
1051 Snapshot(ListUGraph &_graph)
1052 : node_observer_proxy(*this),
1053 edge_observer_proxy(*this) {
1057 /// \brief Make a snapshot.
1059 /// Make a snapshot of the graph.
1061 /// This function can be called more than once. In case of a repeated
1062 /// call, the previous snapshot gets lost.
1063 /// \param _graph The graph we make the snapshot of.
1064 void save(ListUGraph &_graph) {
1072 /// \brief Undo the changes until the last snapshot.
1074 /// Undo the changes until the last snapshot created by save().
1077 for(std::list<UEdge>::iterator it = added_edges.begin();
1078 it != added_edges.end(); ++it) {
1081 for(std::list<Node>::iterator it = added_nodes.begin();
1082 it != added_nodes.end(); ++it) {
1088 /// \brief Gives back true when the snapshot is valid.
1090 /// Gives back true when the snapshot is valid.
1091 bool valid() const {
1098 class ListBpUGraphBase {
1101 class NodeSetError : public LogicError {
1103 virtual const char* what() const throw() {
1104 return "lemon::ListBpUGraph::NodeSetError";
1111 int first_edge, prev, next;
1115 int aNode, prev_out, next_out;
1116 int bNode, prev_in, next_in;
1119 std::vector<NodeT> aNodes;
1120 std::vector<NodeT> bNodes;
1122 std::vector<UEdgeT> edges;
1125 int first_free_anode;
1128 int first_free_bnode;
1130 int first_free_edge;
1135 friend class ListBpUGraphBase;
1139 explicit Node(int _id) : id(_id) {}
1142 Node(Invalid) { id = -1; }
1143 bool operator==(const Node i) const {return id==i.id;}
1144 bool operator!=(const Node i) const {return id!=i.id;}
1145 bool operator<(const Node i) const {return id<i.id;}
1149 friend class ListBpUGraphBase;
1153 explicit UEdge(int _id) { id = _id;}
1156 UEdge (Invalid) { id = -1; }
1157 bool operator==(const UEdge i) const {return id==i.id;}
1158 bool operator!=(const UEdge i) const {return id!=i.id;}
1159 bool operator<(const UEdge i) const {return id<i.id;}
1163 : first_anode(-1), first_free_anode(-1),
1164 first_bnode(-1), first_free_bnode(-1),
1165 first_free_edge(-1) {}
1167 void firstANode(Node& node) const {
1168 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1170 void nextANode(Node& node) const {
1171 node.id = aNodes[node.id >> 1].next;
1174 void firstBNode(Node& node) const {
1175 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1177 void nextBNode(Node& node) const {
1178 node.id = bNodes[node.id >> 1].next;
1181 void first(Node& node) const {
1182 if (first_anode != -1) {
1183 node.id = (first_anode << 1);
1184 } else if (first_bnode != -1) {
1185 node.id = (first_bnode << 1) + 1;
1190 void next(Node& node) const {
1192 node.id = aNodes[node.id >> 1].next;
1193 if (node.id == -1) {
1194 if (first_bnode != -1) {
1195 node.id = (first_bnode << 1) + 1;
1199 node.id = bNodes[node.id >> 1].next;
1203 void first(UEdge& edge) const {
1204 int aNodeId = first_anode;
1205 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1206 aNodeId = aNodes[aNodeId].next != -1 ?
1207 aNodes[aNodeId].next >> 1 : -1;
1209 if (aNodeId != -1) {
1210 edge.id = aNodes[aNodeId].first_edge;
1215 void next(UEdge& edge) const {
1216 int aNodeId = edges[edge.id].aNode >> 1;
1217 edge.id = edges[edge.id].next_out;
1218 if (edge.id == -1) {
1219 aNodeId = aNodes[aNodeId].next != -1 ?
1220 aNodes[aNodeId].next >> 1 : -1;
1221 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1222 aNodeId = aNodes[aNodeId].next != -1 ?
1223 aNodes[aNodeId].next >> 1 : -1;
1225 if (aNodeId != -1) {
1226 edge.id = aNodes[aNodeId].first_edge;
1233 void firstFromANode(UEdge& edge, const Node& node) const {
1234 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1235 edge.id = aNodes[node.id >> 1].first_edge;
1237 void nextFromANode(UEdge& edge) const {
1238 edge.id = edges[edge.id].next_out;
1241 void firstFromBNode(UEdge& edge, const Node& node) const {
1242 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1243 edge.id = bNodes[node.id >> 1].first_edge;
1245 void nextFromBNode(UEdge& edge) const {
1246 edge.id = edges[edge.id].next_in;
1249 static int id(const Node& node) {
1252 static Node nodeFromId(int id) {
1255 int maxNodeId() const {
1256 return aNodes.size() > bNodes.size() ?
1257 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1260 static int id(const UEdge& edge) {
1263 static UEdge uEdgeFromId(int id) {
1266 int maxUEdgeId() const {
1267 return edges.size();
1270 static int aNodeId(const Node& node) {
1271 return node.id >> 1;
1273 static Node fromANodeId(int id) {
1274 return Node(id << 1);
1276 int maxANodeId() const {
1277 return aNodes.size();
1280 static int bNodeId(const Node& node) {
1281 return node.id >> 1;
1283 static Node fromBNodeId(int id) {
1284 return Node((id << 1) + 1);
1286 int maxBNodeId() const {
1287 return bNodes.size();
1290 Node aNode(const UEdge& edge) const {
1291 return Node(edges[edge.id].aNode);
1293 Node bNode(const UEdge& edge) const {
1294 return Node(edges[edge.id].bNode);
1297 static bool aNode(const Node& node) {
1298 return (node.id & 1) == 0;
1301 static bool bNode(const Node& node) {
1302 return (node.id & 1) == 1;
1307 if (first_free_anode == -1) {
1308 aNodeId = aNodes.size();
1309 aNodes.push_back(NodeT());
1311 aNodeId = first_free_anode;
1312 first_free_anode = aNodes[first_free_anode].next;
1314 if (first_anode != -1) {
1315 aNodes[aNodeId].next = first_anode << 1;
1316 aNodes[first_anode].prev = aNodeId << 1;
1318 aNodes[aNodeId].next = -1;
1320 aNodes[aNodeId].prev = -1;
1321 first_anode = aNodeId;
1322 aNodes[aNodeId].first_edge = -1;
1323 return Node(aNodeId << 1);
1328 if (first_free_bnode == -1) {
1329 bNodeId = bNodes.size();
1330 bNodes.push_back(NodeT());
1332 bNodeId = first_free_bnode;
1333 first_free_bnode = bNodes[first_free_bnode].next;
1335 if (first_bnode != -1) {
1336 bNodes[bNodeId].next = (first_bnode << 1) + 1;
1337 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1339 bNodes[bNodeId].next = -1;
1341 bNodes[bNodeId].prev = -1;
1342 first_bnode = bNodeId;
1343 bNodes[bNodeId].first_edge = -1;
1344 return Node((bNodeId << 1) + 1);
1347 UEdge addEdge(const Node& source, const Node& target) {
1348 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1350 if (first_free_edge != -1) {
1351 edgeId = first_free_edge;
1352 first_free_edge = edges[edgeId].next_out;
1354 edgeId = edges.size();
1355 edges.push_back(UEdgeT());
1357 if ((source.id & 1) == 0) {
1358 edges[edgeId].aNode = source.id;
1359 edges[edgeId].bNode = target.id;
1361 edges[edgeId].aNode = target.id;
1362 edges[edgeId].bNode = source.id;
1364 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1365 edges[edgeId].prev_out = -1;
1366 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1367 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1369 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1370 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1371 edges[edgeId].prev_in = -1;
1372 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1373 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1375 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1376 return UEdge(edgeId);
1379 void erase(const Node& node) {
1381 int aNodeId = node.id >> 1;
1382 if (aNodes[aNodeId].prev != -1) {
1383 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1386 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
1388 if (aNodes[aNodeId].next != -1) {
1389 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1391 aNodes[aNodeId].next = first_free_anode;
1392 first_free_anode = aNodeId;
1394 int bNodeId = node.id >> 1;
1395 if (bNodes[bNodeId].prev != -1) {
1396 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1399 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
1401 if (bNodes[bNodeId].next != -1) {
1402 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1404 bNodes[bNodeId].next = first_free_bnode;
1405 first_free_bnode = bNodeId;
1409 void erase(const UEdge& edge) {
1411 if (edges[edge.id].prev_out != -1) {
1412 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1414 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1416 if (edges[edge.id].next_out != -1) {
1417 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1420 if (edges[edge.id].prev_in != -1) {
1421 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1423 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1425 if (edges[edge.id].next_in != -1) {
1426 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1429 edges[edge.id].next_out = first_free_edge;
1430 first_free_edge = edge.id;
1438 first_free_anode = -1;
1440 first_free_bnode = -1;
1441 first_free_edge = -1;
1444 void changeANode(const UEdge& edge, const Node& node) {
1445 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1446 if (edges[edge.id].prev_out != -1) {
1447 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1449 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1451 if (edges[edge.id].next_out != -1) {
1452 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1454 if (aNodes[node.id >> 1].first_edge != -1) {
1455 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1457 edges[edge.id].prev_out = -1;
1458 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1459 aNodes[node.id >> 1].first_edge = edge.id;
1460 edges[edge.id].aNode = node.id;
1463 void changeBNode(const UEdge& edge, const Node& node) {
1464 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1465 if (edges[edge.id].prev_in != -1) {
1466 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1468 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1470 if (edges[edge.id].next_in != -1) {
1471 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1473 if (bNodes[node.id >> 1].first_edge != -1) {
1474 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1476 edges[edge.id].prev_in = -1;
1477 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1478 bNodes[node.id >> 1].first_edge = edge.id;
1479 edges[edge.id].bNode = node.id;
1485 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
1489 /// \brief A smart bipartite undirected graph class.
1491 /// This is a bipartite undirected graph implementation.
1492 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
1493 /// \sa concept::BpUGraph.
1495 class ListBpUGraph : public ExtendedListBpUGraphBase {
1496 /// \brief ListBpUGraph is \e not copy constructible.
1498 ///ListBpUGraph is \e not copy constructible.
1499 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1500 /// \brief Assignment of ListBpUGraph to another one is \e not
1503 /// Assignment of ListBpUGraph to another one is \e not allowed.
1504 void operator=(const ListBpUGraph &) {}
1506 /// \brief Constructor
1512 typedef ExtendedListBpUGraphBase Parent;
1513 /// \brief Add a new ANode to the graph.
1515 /// \return the new node.
1517 Node addANode() { return Parent::addANode(); }
1519 /// \brief Add a new BNode to the graph.
1521 /// \return the new node.
1523 Node addBNode() { return Parent::addBNode(); }
1525 /// \brief Add a new edge to the graph.
1527 /// Add a new edge to the graph with an ANode and a BNode.
1528 /// \return the new undirected edge.
1529 UEdge addEdge(const Node& s, const Node& t) {
1530 return Parent::addEdge(s, t);
1533 /// \brief Changes the ANode of \c e to \c n
1535 /// Changes the ANode of \c e to \c n
1537 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1538 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1540 void changeANode(UEdge e, Node n) {
1541 Parent::changeANode(e,n);
1544 /// \brief Changes the BNode of \c e to \c n
1546 /// Changes the BNode of \c e to \c n
1548 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1549 /// referencing the changed edge remain
1550 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1551 void changeBNode(UEdge e, Node n) {
1552 Parent::changeBNode(e,n);
1555 /// \brief Changes the source(ANode) of \c e to \c n
1557 /// Changes the source(ANode) of \c e to \c n
1559 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1560 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1562 void changeSource(UEdge e, Node n) {
1563 Parent::changeANode(e,n);
1566 /// \brief Changes the target(BNode) of \c e to \c n
1568 /// Changes the target(BNode) of \c e to \c n
1570 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1571 /// referencing the changed edge remain
1572 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1573 void changeTarget(UEdge e, Node n) {
1574 Parent::changeBNode(e,n);
1577 /// \brief Changes the source of \c e to \c n
1579 /// Changes the source of \c e to \c n. It changes the proper
1580 /// node of the represented undirected edge.
1582 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1583 ///referencing the changed edge remain
1584 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1585 void changeSource(Edge e, Node n) {
1586 if (Parent::direction(e)) {
1587 Parent::changeANode(e,n);
1589 Parent::changeBNode(e,n);
1592 /// \brief Changes the target of \c e to \c n
1594 /// Changes the target of \c e to \c n. It changes the proper
1595 /// node of the represented undirected edge.
1597 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1598 ///referencing the changed edge remain
1599 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1600 void changeTarget(Edge e, Node n) {
1601 if (Parent::direction(e)) {
1602 Parent::changeBNode(e,n);
1604 Parent::changeANode(e,n);
1607 /// \brief Contract two nodes.
1609 /// This function contracts two nodes.
1611 /// Node \p b will be removed but instead of deleting its
1612 /// neighboring edges, they will be joined to \p a. The two nodes
1613 /// should be from the same nodeset, of course.
1615 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1617 void contract(const Node& a, const Node& b) {
1618 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1619 if (Parent::aNode(a)) {
1620 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1621 IncEdgeIt f = e; ++f;
1626 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1627 IncEdgeIt f = e; ++f;
1635 /// \brief Class to make a snapshot of the graph and restore
1638 /// Class to make a snapshot of the graph and to restore it
1641 /// The newly added nodes and undirected edges can be removed
1642 /// using the restore() function.
1644 /// \warning Edge and node deletions cannot be restored. This
1645 /// events invalidate the snapshot.
1649 typedef Parent::NodeNotifier NodeNotifier;
1651 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1654 NodeObserverProxy(Snapshot& _snapshot)
1655 : snapshot(_snapshot) {}
1657 using NodeNotifier::ObserverBase::attach;
1658 using NodeNotifier::ObserverBase::detach;
1659 using NodeNotifier::ObserverBase::attached;
1663 virtual void add(const Node& node) {
1664 snapshot.addNode(node);
1666 virtual void add(const std::vector<Node>& nodes) {
1667 for (int i = nodes.size() - 1; i >= 0; ++i) {
1668 snapshot.addNode(nodes[i]);
1671 virtual void erase(const Node& node) {
1672 snapshot.eraseNode(node);
1674 virtual void erase(const std::vector<Node>& nodes) {
1675 for (int i = 0; i < (int)nodes.size(); ++i) {
1676 snapshot.eraseNode(nodes[i]);
1679 virtual void build() {
1680 NodeNotifier* notifier = getNotifier();
1682 std::vector<Node> nodes;
1683 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1684 nodes.push_back(node);
1686 for (int i = nodes.size() - 1; i >= 0; --i) {
1687 snapshot.addNode(nodes[i]);
1690 virtual void clear() {
1691 NodeNotifier* notifier = getNotifier();
1693 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1694 snapshot.eraseNode(node);
1701 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1704 UEdgeObserverProxy(Snapshot& _snapshot)
1705 : snapshot(_snapshot) {}
1707 using UEdgeNotifier::ObserverBase::attach;
1708 using UEdgeNotifier::ObserverBase::detach;
1709 using UEdgeNotifier::ObserverBase::attached;
1713 virtual void add(const UEdge& edge) {
1714 snapshot.addUEdge(edge);
1716 virtual void add(const std::vector<UEdge>& edges) {
1717 for (int i = edges.size() - 1; i >= 0; ++i) {
1718 snapshot.addUEdge(edges[i]);
1721 virtual void erase(const UEdge& edge) {
1722 snapshot.eraseUEdge(edge);
1724 virtual void erase(const std::vector<UEdge>& edges) {
1725 for (int i = 0; i < (int)edges.size(); ++i) {
1726 snapshot.eraseUEdge(edges[i]);
1729 virtual void build() {
1730 UEdgeNotifier* notifier = getNotifier();
1732 std::vector<UEdge> edges;
1733 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1734 edges.push_back(edge);
1736 for (int i = edges.size() - 1; i >= 0; --i) {
1737 snapshot.addUEdge(edges[i]);
1740 virtual void clear() {
1741 UEdgeNotifier* notifier = getNotifier();
1743 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1744 snapshot.eraseUEdge(edge);
1751 ListBpUGraph *graph;
1753 NodeObserverProxy node_observer_proxy;
1754 UEdgeObserverProxy edge_observer_proxy;
1756 std::list<Node> added_nodes;
1757 std::list<UEdge> added_edges;
1760 void addNode(const Node& node) {
1761 added_nodes.push_front(node);
1763 void eraseNode(const Node& node) {
1764 std::list<Node>::iterator it =
1765 std::find(added_nodes.begin(), added_nodes.end(), node);
1766 if (it == added_nodes.end()) {
1768 edge_observer_proxy.detach();
1769 throw NodeNotifier::ImmediateDetach();
1771 added_nodes.erase(it);
1775 void addUEdge(const UEdge& edge) {
1776 added_edges.push_front(edge);
1778 void eraseUEdge(const UEdge& edge) {
1779 std::list<UEdge>::iterator it =
1780 std::find(added_edges.begin(), added_edges.end(), edge);
1781 if (it == added_edges.end()) {
1783 node_observer_proxy.detach();
1784 throw UEdgeNotifier::ImmediateDetach();
1786 added_edges.erase(it);
1790 void attach(ListBpUGraph &_graph) {
1792 node_observer_proxy.attach(graph->getNotifier(Node()));
1793 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1797 node_observer_proxy.detach();
1798 edge_observer_proxy.detach();
1801 bool attached() const {
1802 return node_observer_proxy.attached();
1806 added_nodes.clear();
1807 added_edges.clear();
1812 /// \brief Default constructor.
1814 /// Default constructor.
1815 /// To actually make a snapshot you must call save().
1817 : graph(0), node_observer_proxy(*this),
1818 edge_observer_proxy(*this) {}
1820 /// \brief Constructor that immediately makes a snapshot.
1822 /// This constructor immediately makes a snapshot of the graph.
1823 /// \param _graph The graph we make a snapshot of.
1824 Snapshot(ListBpUGraph &_graph)
1825 : node_observer_proxy(*this),
1826 edge_observer_proxy(*this) {
1830 /// \brief Make a snapshot.
1832 /// Make a snapshot of the graph.
1834 /// This function can be called more than once. In case of a repeated
1835 /// call, the previous snapshot gets lost.
1836 /// \param _graph The graph we make the snapshot of.
1837 void save(ListBpUGraph &_graph) {
1845 /// \brief Undo the changes until the last snapshot.
1847 /// Undo the changes until the last snapshot created by save().
1850 for(std::list<UEdge>::iterator it = added_edges.begin();
1851 it != added_edges.end(); ++it) {
1854 for(std::list<Node>::iterator it = added_nodes.begin();
1855 it != added_nodes.end(); ++it) {
1861 /// \brief Gives back true when the snapshot is valid.
1863 /// Gives back true when the snapshot is valid.
1864 bool valid() const {