3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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) {}
101 int maxNodeId() const { return nodes.size()-1; }
102 int maxEdgeId() const { return edges.size()-1; }
104 Node source(Edge e) const { return Node(edges[e.id].source); }
105 Node target(Edge e) const { return Node(edges[e.id].target); }
108 void first(Node& node) const {
109 node.id = first_node;
112 void next(Node& node) const {
113 node.id = nodes[node.id].next;
117 void first(Edge& e) const {
120 n!=-1 && nodes[n].first_in == -1;
122 e.id = (n == -1) ? -1 : nodes[n].first_in;
125 void next(Edge& edge) const {
126 if (edges[edge.id].next_in != -1) {
127 edge.id = edges[edge.id].next_in;
130 for(n = nodes[edges[edge.id].target].next;
131 n!=-1 && nodes[n].first_in == -1;
133 edge.id = (n == -1) ? -1 : nodes[n].first_in;
137 void firstOut(Edge &e, const Node& v) const {
138 e.id = nodes[v.id].first_out;
140 void nextOut(Edge &e) const {
141 e.id=edges[e.id].next_out;
144 void firstIn(Edge &e, const Node& v) const {
145 e.id = nodes[v.id].first_in;
147 void nextIn(Edge &e) const {
148 e.id=edges[e.id].next_in;
152 static int id(Node v) { return v.id; }
153 static int id(Edge e) { return e.id; }
155 static Node nodeFromId(int id) { return Node(id);}
156 static Edge edgeFromId(int id) { return Edge(id);}
161 if(first_free_node==-1) {
163 nodes.push_back(NodeT());
166 first_free_node = nodes[n].next;
169 nodes[n].next = first_node;
170 if(first_node != -1) nodes[first_node].prev = n;
174 nodes[n].first_in = nodes[n].first_out = -1;
179 Edge addEdge(Node u, Node v) {
182 if (first_free_edge == -1) {
184 edges.push_back(EdgeT());
187 first_free_edge = edges[n].next_in;
190 edges[n].source = u.id;
191 edges[n].target = v.id;
193 edges[n].next_out = nodes[u.id].first_out;
194 if(nodes[u.id].first_out != -1) {
195 edges[nodes[u.id].first_out].prev_out = n;
198 edges[n].next_in = nodes[v.id].first_in;
199 if(nodes[v.id].first_in != -1) {
200 edges[nodes[v.id].first_in].prev_in = n;
203 edges[n].prev_in = edges[n].prev_out = -1;
205 nodes[u.id].first_out = nodes[v.id].first_in = n;
210 void erase(const Node& node) {
213 if(nodes[n].next != -1) {
214 nodes[nodes[n].next].prev = nodes[n].prev;
217 if(nodes[n].prev != -1) {
218 nodes[nodes[n].prev].next = nodes[n].next;
220 first_node = nodes[n].next;
223 nodes[n].next = first_free_node;
228 void erase(const Edge& edge) {
231 if(edges[n].next_in!=-1) {
232 edges[edges[n].next_in].prev_in = edges[n].prev_in;
235 if(edges[n].prev_in!=-1) {
236 edges[edges[n].prev_in].next_in = edges[n].next_in;
238 nodes[edges[n].target].first_in = edges[n].next_in;
242 if(edges[n].next_out!=-1) {
243 edges[edges[n].next_out].prev_out = edges[n].prev_out;
246 if(edges[n].prev_out!=-1) {
247 edges[edges[n].prev_out].next_out = edges[n].next_out;
249 nodes[edges[n].source].first_out = edges[n].next_out;
252 edges[n].next_in = first_free_edge;
260 first_node = first_free_node = first_free_edge = -1;
264 void changeTarget(Edge e, Node n)
266 if(edges[e.id].next_in != -1)
267 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
268 if(edges[e.id].prev_in != -1)
269 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
270 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
271 if (nodes[n.id].first_in != -1) {
272 edges[nodes[n.id].first_in].prev_in = e.id;
274 edges[e.id].target = n.id;
275 edges[e.id].prev_in = -1;
276 edges[e.id].next_in = nodes[n.id].first_in;
277 nodes[n.id].first_in = e.id;
279 void changeSource(Edge e, Node n)
281 if(edges[e.id].next_out != -1)
282 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
283 if(edges[e.id].prev_out != -1)
284 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
285 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
286 if (nodes[n.id].first_out != -1) {
287 edges[nodes[n.id].first_out].prev_out = e.id;
289 edges[e.id].source = n.id;
290 edges[e.id].prev_out = -1;
291 edges[e.id].next_out = nodes[n.id].first_out;
292 nodes[n.id].first_out = e.id;
297 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
299 /// \addtogroup graphs
302 ///A list graph class.
304 ///This is a simple and fast graph implementation.
306 ///It conforms to the \ref concepts::Graph "Graph concept" and it
307 ///also provides several additional useful extra functionalities.
308 ///The most of the member functions and nested classes are
309 ///documented only in the concept class.
311 ///An important extra feature of this graph implementation is that
312 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
314 ///\sa concepts::Graph.
316 class ListGraph : public ExtendedListGraphBase {
318 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
320 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
322 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
323 ///\brief Assignment of ListGraph to another one is \e not allowed.
324 ///Use GraphCopy() instead.
326 ///Assignment of ListGraph to another one is \e not allowed.
327 ///Use GraphCopy() instead.
328 void operator=(const ListGraph &) {}
331 typedef ExtendedListGraphBase Parent;
339 ///Add a new node to the graph.
341 /// \return the new node.
343 Node addNode() { return Parent::addNode(); }
345 ///Add a new edge to the graph.
347 ///Add a new edge to the graph with source node \c s
348 ///and target node \c t.
349 ///\return the new edge.
350 Edge addEdge(const Node& s, const Node& t) {
351 return Parent::addEdge(s, t);
354 /// Changes the target of \c e to \c n
356 /// Changes the target of \c e to \c n
358 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
359 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
361 ///\warning This functionality cannot be used together with the Snapshot
363 void changeTarget(Edge e, Node n) {
364 Parent::changeTarget(e,n);
366 /// Changes the source of \c e to \c n
368 /// Changes the source of \c e to \c n
370 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
371 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
373 ///\warning This functionality cannot be used together with the Snapshot
375 void changeSource(Edge e, Node n) {
376 Parent::changeSource(e,n);
379 /// Invert the direction of an edge.
381 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
382 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
384 ///\warning This functionality cannot be used together with the Snapshot
386 void reverseEdge(Edge e) {
388 changeTarget(e,source(e));
392 /// \brief Using this it is possible to avoid the superfluous memory
395 ///Using this it is possible to avoid the superfluous memory
396 ///allocation: if you know that the graph you want to build will
397 ///contain at least 10 million nodes then it is worth reserving
398 ///space for this amount before starting to build the graph.
399 void reserveNode(int n) { nodes.reserve(n); };
401 /// \brief Using this it is possible to avoid the superfluous memory
404 ///Using this it is possible to avoid the superfluous memory
405 ///allocation: see the \ref reserveNode function.
406 void reserveEdge(int n) { edges.reserve(n); };
409 ///Contract two nodes.
411 ///This function contracts two nodes.
413 ///Node \p b will be removed but instead of deleting
414 ///incident edges, they will be joined to \p a.
415 ///The last parameter \p r controls whether to remove loops. \c true
416 ///means that loops will be removed.
418 ///\note The <tt>EdgeIt</tt>s
419 ///referencing a moved edge remain
420 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
421 ///may be invalidated.
422 ///\warning This functionality cannot be used together with the Snapshot
424 void contract(Node a, Node b, bool r = true)
426 for(OutEdgeIt e(*this,b);e!=INVALID;) {
429 if(r && target(e)==a) erase(e);
430 else changeSource(e,a);
433 for(InEdgeIt e(*this,b);e!=INVALID;) {
436 if(r && source(e)==a) erase(e);
437 else changeTarget(e,a);
445 ///This function splits a node. First a new node is added to the graph,
446 ///then the source of each outgoing edge of \c n is moved to this new node.
447 ///If \c connect is \c true (this is the default value), then a new edge
448 ///from \c n to the newly created node is also added.
449 ///\return The newly created node.
451 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
452 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
455 ///\warning This functionality cannot be used together with the
456 ///Snapshot feature. \todo It could be implemented in a bit
458 Node split(Node n, bool connect = true) {
460 for(OutEdgeIt e(*this,n);e!=INVALID;) {
466 if (connect) addEdge(n,b);
472 ///This function splits an edge. First a new node \c b is added to
473 ///the graph, then the original edge is re-targeted to \c
474 ///b. Finally an edge from \c b to the original target is added.
475 ///\return The newly created node.
476 ///\warning This functionality
477 ///cannot be used together with the Snapshot feature.
480 addEdge(b,target(e));
485 /// \brief Class to make a snapshot of the graph and restore
488 /// Class to make a snapshot of the graph and to restore it
491 /// The newly added nodes and edges can be removed using the
492 /// restore() function.
494 /// \warning Edge and node deletions cannot be restored. This
495 /// events invalidate the snapshot.
499 typedef Parent::NodeNotifier NodeNotifier;
501 class NodeObserverProxy : public NodeNotifier::ObserverBase {
504 NodeObserverProxy(Snapshot& _snapshot)
505 : snapshot(_snapshot) {}
507 using NodeNotifier::ObserverBase::attach;
508 using NodeNotifier::ObserverBase::detach;
509 using NodeNotifier::ObserverBase::attached;
513 virtual void add(const Node& node) {
514 snapshot.addNode(node);
516 virtual void add(const std::vector<Node>& nodes) {
517 for (int i = nodes.size() - 1; i >= 0; ++i) {
518 snapshot.addNode(nodes[i]);
521 virtual void erase(const Node& node) {
522 snapshot.eraseNode(node);
524 virtual void erase(const std::vector<Node>& nodes) {
525 for (int i = 0; i < int(nodes.size()); ++i) {
526 snapshot.eraseNode(nodes[i]);
529 virtual void build() {
531 std::vector<Node> nodes;
532 for (notifier()->first(node); node != INVALID;
533 notifier()->next(node)) {
534 nodes.push_back(node);
536 for (int i = nodes.size() - 1; i >= 0; --i) {
537 snapshot.addNode(nodes[i]);
540 virtual void clear() {
542 for (notifier()->first(node); node != INVALID;
543 notifier()->next(node)) {
544 snapshot.eraseNode(node);
551 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
554 EdgeObserverProxy(Snapshot& _snapshot)
555 : snapshot(_snapshot) {}
557 using EdgeNotifier::ObserverBase::attach;
558 using EdgeNotifier::ObserverBase::detach;
559 using EdgeNotifier::ObserverBase::attached;
563 virtual void add(const Edge& edge) {
564 snapshot.addEdge(edge);
566 virtual void add(const std::vector<Edge>& edges) {
567 for (int i = edges.size() - 1; i >= 0; ++i) {
568 snapshot.addEdge(edges[i]);
571 virtual void erase(const Edge& edge) {
572 snapshot.eraseEdge(edge);
574 virtual void erase(const std::vector<Edge>& edges) {
575 for (int i = 0; i < int(edges.size()); ++i) {
576 snapshot.eraseEdge(edges[i]);
579 virtual void build() {
581 std::vector<Edge> edges;
582 for (notifier()->first(edge); edge != INVALID;
583 notifier()->next(edge)) {
584 edges.push_back(edge);
586 for (int i = edges.size() - 1; i >= 0; --i) {
587 snapshot.addEdge(edges[i]);
590 virtual void clear() {
592 for (notifier()->first(edge); edge != INVALID;
593 notifier()->next(edge)) {
594 snapshot.eraseEdge(edge);
603 NodeObserverProxy node_observer_proxy;
604 EdgeObserverProxy edge_observer_proxy;
606 std::list<Node> added_nodes;
607 std::list<Edge> added_edges;
610 void addNode(const Node& node) {
611 added_nodes.push_front(node);
613 void eraseNode(const Node& node) {
614 std::list<Node>::iterator it =
615 std::find(added_nodes.begin(), added_nodes.end(), node);
616 if (it == added_nodes.end()) {
618 edge_observer_proxy.detach();
619 throw NodeNotifier::ImmediateDetach();
621 added_nodes.erase(it);
625 void addEdge(const Edge& edge) {
626 added_edges.push_front(edge);
628 void eraseEdge(const Edge& edge) {
629 std::list<Edge>::iterator it =
630 std::find(added_edges.begin(), added_edges.end(), edge);
631 if (it == added_edges.end()) {
633 node_observer_proxy.detach();
634 throw EdgeNotifier::ImmediateDetach();
636 added_edges.erase(it);
640 void attach(ListGraph &_graph) {
642 node_observer_proxy.attach(graph->notifier(Node()));
643 edge_observer_proxy.attach(graph->notifier(Edge()));
647 node_observer_proxy.detach();
648 edge_observer_proxy.detach();
651 bool attached() const {
652 return node_observer_proxy.attached();
662 /// \brief Default constructor.
664 /// Default constructor.
665 /// To actually make a snapshot you must call save().
667 : graph(0), node_observer_proxy(*this),
668 edge_observer_proxy(*this) {}
670 /// \brief Constructor that immediately makes a snapshot.
672 /// This constructor immediately makes a snapshot of the graph.
673 /// \param _graph The graph we make a snapshot of.
674 Snapshot(ListGraph &_graph)
675 : node_observer_proxy(*this),
676 edge_observer_proxy(*this) {
680 /// \brief Make a snapshot.
682 /// Make a snapshot of the graph.
684 /// This function can be called more than once. In case of a repeated
685 /// call, the previous snapshot gets lost.
686 /// \param _graph The graph we make the snapshot of.
687 void save(ListGraph &_graph) {
695 /// \brief Undo the changes until the last snapshot.
697 /// Undo the changes until the last snapshot created by save().
700 for(std::list<Edge>::iterator it = added_edges.begin();
701 it != added_edges.end(); ++it) {
704 for(std::list<Node>::iterator it = added_nodes.begin();
705 it != added_nodes.end(); ++it) {
711 /// \brief Gives back true when the snapshot is valid.
713 /// Gives back true when the snapshot is valid.
723 class ListUGraphBase {
734 int prev_out, next_out;
737 std::vector<NodeT> nodes;
743 std::vector<EdgeT> edges;
749 typedef ListUGraphBase Graph;
756 friend class ListUGraphBase;
760 explicit Node(int pid) { id = pid;}
764 Node (Invalid) { id = -1; }
765 bool operator==(const Node& node) const {return id == node.id;}
766 bool operator!=(const Node& node) const {return id != node.id;}
767 bool operator<(const Node& node) const {return id < node.id;}
771 friend class ListUGraphBase;
775 explicit UEdge(int pid) { id = pid;}
779 UEdge (Invalid) { id = -1; }
780 bool operator==(const UEdge& edge) const {return id == edge.id;}
781 bool operator!=(const UEdge& edge) const {return id != edge.id;}
782 bool operator<(const UEdge& edge) const {return id < edge.id;}
786 friend class ListUGraphBase;
790 explicit Edge(int pid) { id = pid;}
793 operator UEdge() const { return uEdgeFromId(id / 2); }
796 Edge (Invalid) { id = -1; }
797 bool operator==(const Edge& edge) const {return id == edge.id;}
798 bool operator!=(const Edge& edge) const {return id != edge.id;}
799 bool operator<(const Edge& edge) const {return id < edge.id;}
805 : nodes(), first_node(-1),
806 first_free_node(-1), edges(), first_free_edge(-1) {}
809 int maxNodeId() const { return nodes.size()-1; }
810 int maxUEdgeId() const { return edges.size() / 2 - 1; }
811 int maxEdgeId() const { return edges.size()-1; }
813 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
814 Node target(Edge e) const { return Node(edges[e.id].target); }
816 Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
817 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
819 static bool direction(Edge e) {
820 return (e.id & 1) == 1;
823 static Edge direct(UEdge e, bool d) {
824 return Edge(e.id * 2 + (d ? 1 : 0));
827 void first(Node& node) const {
828 node.id = first_node;
831 void next(Node& node) const {
832 node.id = nodes[node.id].next;
835 void first(Edge& e) const {
837 while (n != -1 && nodes[n].first_out == -1) {
840 e.id = (n == -1) ? -1 : nodes[n].first_out;
843 void next(Edge& e) const {
844 if (edges[e.id].next_out != -1) {
845 e.id = edges[e.id].next_out;
847 int n = nodes[edges[e.id ^ 1].target].next;
848 while(n != -1 && nodes[n].first_out == -1) {
851 e.id = (n == -1) ? -1 : nodes[n].first_out;
855 void first(UEdge& e) const {
858 e.id = nodes[n].first_out;
859 while ((e.id & 1) != 1) {
860 e.id = edges[e.id].next_out;
871 void next(UEdge& e) const {
872 int n = edges[e.id * 2].target;
873 e.id = edges[(e.id * 2) | 1].next_out;
874 while ((e.id & 1) != 1) {
875 e.id = edges[e.id].next_out;
883 e.id = nodes[n].first_out;
884 while ((e.id & 1) != 1) {
885 e.id = edges[e.id].next_out;
896 void firstOut(Edge &e, const Node& v) const {
897 e.id = nodes[v.id].first_out;
899 void nextOut(Edge &e) const {
900 e.id = edges[e.id].next_out;
903 void firstIn(Edge &e, const Node& v) const {
904 e.id = ((nodes[v.id].first_out) ^ 1);
905 if (e.id == -2) e.id = -1;
907 void nextIn(Edge &e) const {
908 e.id = ((edges[e.id ^ 1].next_out) ^ 1);
909 if (e.id == -2) e.id = -1;
912 void firstInc(UEdge &e, bool& d, const Node& v) const {
913 int de = nodes[v.id].first_out;
922 void nextInc(UEdge &e, bool& d) const {
923 int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
933 static int id(Node v) { return v.id; }
934 static int id(Edge e) { return e.id; }
935 static int id(UEdge e) { return e.id; }
937 static Node nodeFromId(int id) { return Node(id);}
938 static Edge edgeFromId(int id) { return Edge(id);}
939 static UEdge uEdgeFromId(int id) { return UEdge(id);}
944 if(first_free_node==-1) {
946 nodes.push_back(NodeT());
949 first_free_node = nodes[n].next;
952 nodes[n].next = first_node;
953 if (first_node != -1) nodes[first_node].prev = n;
957 nodes[n].first_out = -1;
962 UEdge addEdge(Node u, Node v) {
965 if (first_free_edge == -1) {
967 edges.push_back(EdgeT());
968 edges.push_back(EdgeT());
971 first_free_edge = edges[n].next_out;
974 edges[n].target = u.id;
975 edges[n | 1].target = v.id;
977 edges[n].next_out = nodes[v.id].first_out;
978 edges[n | 1].next_out = nodes[u.id].first_out;
979 if (nodes[v.id].first_out != -1) {
980 edges[nodes[v.id].first_out].prev_out = n;
982 if (nodes[u.id].first_out != -1) {
983 edges[nodes[u.id].first_out].prev_out = (n | 1);
986 edges[n].prev_out = edges[n | 1].prev_out = -1;
988 nodes[v.id].first_out = n;
989 nodes[u.id].first_out = (n | 1);
994 void erase(const Node& node) {
997 if(nodes[n].next != -1) {
998 nodes[nodes[n].next].prev = nodes[n].prev;
1001 if(nodes[n].prev != -1) {
1002 nodes[nodes[n].prev].next = nodes[n].next;
1004 first_node = nodes[n].next;
1007 nodes[n].next = first_free_node;
1008 first_free_node = n;
1012 void erase(const UEdge& edge) {
1013 int n = edge.id * 2;
1015 if (edges[n].next_out != -1) {
1016 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1019 if (edges[n].prev_out != -1) {
1020 edges[edges[n].prev_out].next_out = edges[n].next_out;
1022 nodes[edges[n | 1].target].first_out = edges[n].next_out;
1025 if (edges[n | 1].next_out != -1) {
1026 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1029 if (edges[n | 1].prev_out != -1) {
1030 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1032 nodes[edges[n].target].first_out = edges[n | 1].next_out;
1035 edges[n].next_out = first_free_edge;
1036 first_free_edge = n;
1043 first_node = first_free_node = first_free_edge = -1;
1048 void changeTarget(UEdge e, Node n) {
1049 if(edges[2 * e.id].next_out != -1) {
1050 edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1052 if(edges[2 * e.id].prev_out != -1) {
1053 edges[edges[2 * e.id].prev_out].next_out =
1054 edges[2 * e.id].next_out;
1056 nodes[edges[(2 * e.id) | 1].target].first_out =
1057 edges[2 * e.id].next_out;
1060 if (nodes[n.id].first_out != -1) {
1061 edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1063 edges[(2 * e.id) | 1].target = n.id;
1064 edges[2 * e.id].prev_out = -1;
1065 edges[2 * e.id].next_out = nodes[n.id].first_out;
1066 nodes[n.id].first_out = 2 * e.id;
1069 void changeSource(UEdge e, Node n) {
1070 if(edges[(2 * e.id) | 1].next_out != -1) {
1071 edges[edges[(2 * e.id) | 1].next_out].prev_out =
1072 edges[(2 * e.id) | 1].prev_out;
1074 if(edges[(2 * e.id) | 1].prev_out != -1) {
1075 edges[edges[(2 * e.id) | 1].prev_out].next_out =
1076 edges[(2 * e.id) | 1].next_out;
1078 nodes[edges[2 * e.id].target].first_out =
1079 edges[(2 * e.id) | 1].next_out;
1082 if (nodes[n.id].first_out != -1) {
1083 edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1085 edges[2 * e.id].target = n.id;
1086 edges[(2 * e.id) | 1].prev_out = -1;
1087 edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1088 nodes[n.id].first_out = ((2 * e.id) | 1);
1093 // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1094 // ExtendedListUGraphBase;
1096 typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1100 /// \addtogroup graphs
1103 ///An undirected list graph class.
1105 ///This is a simple and fast undirected graph implementation.
1107 ///An important extra feature of this graph implementation is that
1108 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1110 ///It conforms to the
1111 ///\ref concepts::UGraph "UGraph concept".
1113 ///\sa concepts::UGraph.
1115 class ListUGraph : public ExtendedListUGraphBase {
1117 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1119 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1121 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
1122 ///\brief Assignment of ListUGraph to another one is \e not allowed.
1123 ///Use UGraphCopy() instead.
1125 ///Assignment of ListUGraph to another one is \e not allowed.
1126 ///Use UGraphCopy() instead.
1127 void operator=(const ListUGraph &) {}
1135 typedef ExtendedListUGraphBase Parent;
1137 typedef Parent::OutEdgeIt IncEdgeIt;
1139 /// \brief Add a new node to the graph.
1141 /// \return the new node.
1143 Node addNode() { return Parent::addNode(); }
1145 /// \brief Add a new edge to the graph.
1147 /// Add a new edge to the graph with source node \c s
1148 /// and target node \c t.
1149 /// \return the new undirected edge.
1150 UEdge addEdge(const Node& s, const Node& t) {
1151 return Parent::addEdge(s, t);
1153 /// \brief Changes the source of \c e to \c n
1155 /// Changes the source of \c e to \c n
1157 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1158 ///referencing the changed edge remain
1159 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1160 void changeSource(UEdge e, Node n) {
1161 Parent::changeSource(e,n);
1163 /// \brief Changes the target of \c e to \c n
1165 /// Changes the target of \c e to \c n
1167 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
1168 /// valid. However the other iterators may be invalidated.
1169 void changeTarget(UEdge e, Node n) {
1170 Parent::changeTarget(e,n);
1172 /// \brief Changes the source of \c e to \c n
1174 /// Changes the source of \c e to \c n. It changes the proper
1175 /// node of the represented undirected edge.
1177 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1178 ///referencing the changed edge remain
1179 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1180 void changeSource(Edge e, Node n) {
1181 if (Parent::direction(e)) {
1182 Parent::changeSource(e,n);
1184 Parent::changeTarget(e,n);
1187 /// \brief Changes the target of \c e to \c n
1189 /// Changes the target of \c e to \c n. It changes the proper
1190 /// node of the represented undirected edge.
1192 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1193 ///referencing the changed edge remain
1194 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1195 void changeTarget(Edge e, Node n) {
1196 if (Parent::direction(e)) {
1197 Parent::changeTarget(e,n);
1199 Parent::changeSource(e,n);
1202 /// \brief Contract two nodes.
1204 /// This function contracts two nodes.
1206 /// Node \p b will be removed but instead of deleting
1207 /// its neighboring edges, they will be joined to \p a.
1208 /// The last parameter \p r controls whether to remove loops. \c true
1209 /// means that loops will be removed.
1211 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1213 void contract(Node a, Node b, bool r = true) {
1214 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1215 IncEdgeIt f = e; ++f;
1216 if (r && runningNode(e) == a) {
1218 } else if (source(e) == b) {
1229 /// \brief Class to make a snapshot of the graph and restore
1232 /// Class to make a snapshot of the graph and to restore it
1235 /// The newly added nodes and undirected edges can be removed
1236 /// using the restore() function.
1238 /// \warning Edge and node deletions cannot be restored. This
1239 /// events invalidate the snapshot.
1243 typedef Parent::NodeNotifier NodeNotifier;
1245 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1248 NodeObserverProxy(Snapshot& _snapshot)
1249 : snapshot(_snapshot) {}
1251 using NodeNotifier::ObserverBase::attach;
1252 using NodeNotifier::ObserverBase::detach;
1253 using NodeNotifier::ObserverBase::attached;
1257 virtual void add(const Node& node) {
1258 snapshot.addNode(node);
1260 virtual void add(const std::vector<Node>& nodes) {
1261 for (int i = nodes.size() - 1; i >= 0; ++i) {
1262 snapshot.addNode(nodes[i]);
1265 virtual void erase(const Node& node) {
1266 snapshot.eraseNode(node);
1268 virtual void erase(const std::vector<Node>& nodes) {
1269 for (int i = 0; i < int(nodes.size()); ++i) {
1270 snapshot.eraseNode(nodes[i]);
1273 virtual void build() {
1275 std::vector<Node> nodes;
1276 for (notifier()->first(node); node != INVALID;
1277 notifier()->next(node)) {
1278 nodes.push_back(node);
1280 for (int i = nodes.size() - 1; i >= 0; --i) {
1281 snapshot.addNode(nodes[i]);
1284 virtual void clear() {
1286 for (notifier()->first(node); node != INVALID;
1287 notifier()->next(node)) {
1288 snapshot.eraseNode(node);
1295 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1298 UEdgeObserverProxy(Snapshot& _snapshot)
1299 : snapshot(_snapshot) {}
1301 using UEdgeNotifier::ObserverBase::attach;
1302 using UEdgeNotifier::ObserverBase::detach;
1303 using UEdgeNotifier::ObserverBase::attached;
1307 virtual void add(const UEdge& edge) {
1308 snapshot.addUEdge(edge);
1310 virtual void add(const std::vector<UEdge>& edges) {
1311 for (int i = edges.size() - 1; i >= 0; ++i) {
1312 snapshot.addUEdge(edges[i]);
1315 virtual void erase(const UEdge& edge) {
1316 snapshot.eraseUEdge(edge);
1318 virtual void erase(const std::vector<UEdge>& edges) {
1319 for (int i = 0; i < int(edges.size()); ++i) {
1320 snapshot.eraseUEdge(edges[i]);
1323 virtual void build() {
1325 std::vector<UEdge> edges;
1326 for (notifier()->first(edge); edge != INVALID;
1327 notifier()->next(edge)) {
1328 edges.push_back(edge);
1330 for (int i = edges.size() - 1; i >= 0; --i) {
1331 snapshot.addUEdge(edges[i]);
1334 virtual void clear() {
1336 for (notifier()->first(edge); edge != INVALID;
1337 notifier()->next(edge)) {
1338 snapshot.eraseUEdge(edge);
1347 NodeObserverProxy node_observer_proxy;
1348 UEdgeObserverProxy edge_observer_proxy;
1350 std::list<Node> added_nodes;
1351 std::list<UEdge> added_edges;
1354 void addNode(const Node& node) {
1355 added_nodes.push_front(node);
1357 void eraseNode(const Node& node) {
1358 std::list<Node>::iterator it =
1359 std::find(added_nodes.begin(), added_nodes.end(), node);
1360 if (it == added_nodes.end()) {
1362 edge_observer_proxy.detach();
1363 throw NodeNotifier::ImmediateDetach();
1365 added_nodes.erase(it);
1369 void addUEdge(const UEdge& edge) {
1370 added_edges.push_front(edge);
1372 void eraseUEdge(const UEdge& edge) {
1373 std::list<UEdge>::iterator it =
1374 std::find(added_edges.begin(), added_edges.end(), edge);
1375 if (it == added_edges.end()) {
1377 node_observer_proxy.detach();
1378 throw UEdgeNotifier::ImmediateDetach();
1380 added_edges.erase(it);
1384 void attach(ListUGraph &_graph) {
1386 node_observer_proxy.attach(graph->notifier(Node()));
1387 edge_observer_proxy.attach(graph->notifier(UEdge()));
1391 node_observer_proxy.detach();
1392 edge_observer_proxy.detach();
1395 bool attached() const {
1396 return node_observer_proxy.attached();
1400 added_nodes.clear();
1401 added_edges.clear();
1406 /// \brief Default constructor.
1408 /// Default constructor.
1409 /// To actually make a snapshot you must call save().
1411 : graph(0), node_observer_proxy(*this),
1412 edge_observer_proxy(*this) {}
1414 /// \brief Constructor that immediately makes a snapshot.
1416 /// This constructor immediately makes a snapshot of the graph.
1417 /// \param _graph The graph we make a snapshot of.
1418 Snapshot(ListUGraph &_graph)
1419 : node_observer_proxy(*this),
1420 edge_observer_proxy(*this) {
1424 /// \brief Make a snapshot.
1426 /// Make a snapshot of the graph.
1428 /// This function can be called more than once. In case of a repeated
1429 /// call, the previous snapshot gets lost.
1430 /// \param _graph The graph we make the snapshot of.
1431 void save(ListUGraph &_graph) {
1439 /// \brief Undo the changes until the last snapshot.
1441 /// Undo the changes until the last snapshot created by save().
1444 for(std::list<UEdge>::iterator it = added_edges.begin();
1445 it != added_edges.end(); ++it) {
1448 for(std::list<Node>::iterator it = added_nodes.begin();
1449 it != added_nodes.end(); ++it) {
1455 /// \brief Gives back true when the snapshot is valid.
1457 /// Gives back true when the snapshot is valid.
1458 bool valid() const {
1465 class ListBpUGraphBase {
1468 class NodeSetError : public LogicError {
1470 virtual const char* what() const throw() {
1471 return "lemon::ListBpUGraph::NodeSetError";
1478 int first_edge, prev, next;
1482 int aNode, prev_out, next_out;
1483 int bNode, prev_in, next_in;
1486 std::vector<NodeT> aNodes;
1487 std::vector<NodeT> bNodes;
1489 std::vector<UEdgeT> edges;
1492 int first_free_anode;
1495 int first_free_bnode;
1497 int first_free_edge;
1502 friend class ListBpUGraphBase;
1506 explicit Node(int _id) : id(_id) {}
1509 Node(Invalid) { id = -1; }
1510 bool operator==(const Node i) const {return id==i.id;}
1511 bool operator!=(const Node i) const {return id!=i.id;}
1512 bool operator<(const Node i) const {return id<i.id;}
1516 friend class ListBpUGraphBase;
1520 explicit UEdge(int _id) { id = _id;}
1523 UEdge (Invalid) { id = -1; }
1524 bool operator==(const UEdge i) const {return id==i.id;}
1525 bool operator!=(const UEdge i) const {return id!=i.id;}
1526 bool operator<(const UEdge i) const {return id<i.id;}
1530 : first_anode(-1), first_free_anode(-1),
1531 first_bnode(-1), first_free_bnode(-1),
1532 first_free_edge(-1) {}
1534 void firstANode(Node& node) const {
1535 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1537 void nextANode(Node& node) const {
1538 node.id = aNodes[node.id >> 1].next;
1541 void firstBNode(Node& node) const {
1542 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1544 void nextBNode(Node& node) const {
1545 node.id = bNodes[node.id >> 1].next;
1548 void first(Node& node) const {
1549 if (first_anode != -1) {
1550 node.id = (first_anode << 1);
1551 } else if (first_bnode != -1) {
1552 node.id = (first_bnode << 1) + 1;
1557 void next(Node& node) const {
1559 node.id = aNodes[node.id >> 1].next;
1560 if (node.id == -1) {
1561 if (first_bnode != -1) {
1562 node.id = (first_bnode << 1) + 1;
1566 node.id = bNodes[node.id >> 1].next;
1570 void first(UEdge& edge) const {
1571 int aid = first_anode;
1572 while (aid != -1 && aNodes[aid].first_edge == -1) {
1573 aid = aNodes[aid].next != -1 ?
1574 aNodes[aid].next >> 1 : -1;
1577 edge.id = aNodes[aid].first_edge;
1582 void next(UEdge& edge) const {
1583 int aid = edges[edge.id].aNode >> 1;
1584 edge.id = edges[edge.id].next_out;
1585 if (edge.id == -1) {
1586 aid = aNodes[aid].next != -1 ?
1587 aNodes[aid].next >> 1 : -1;
1588 while (aid != -1 && aNodes[aid].first_edge == -1) {
1589 aid = aNodes[aid].next != -1 ?
1590 aNodes[aid].next >> 1 : -1;
1593 edge.id = aNodes[aid].first_edge;
1600 void firstFromANode(UEdge& edge, const Node& node) const {
1601 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1602 edge.id = aNodes[node.id >> 1].first_edge;
1604 void nextFromANode(UEdge& edge) const {
1605 edge.id = edges[edge.id].next_out;
1608 void firstFromBNode(UEdge& edge, const Node& node) const {
1609 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1610 edge.id = bNodes[node.id >> 1].first_edge;
1612 void nextFromBNode(UEdge& edge) const {
1613 edge.id = edges[edge.id].next_in;
1616 static int id(const Node& node) {
1619 static Node nodeFromId(int id) {
1622 int maxNodeId() const {
1623 return aNodes.size() > bNodes.size() ?
1624 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1627 static int id(const UEdge& edge) {
1630 static UEdge uEdgeFromId(int id) {
1633 int maxUEdgeId() const {
1634 return edges.size();
1637 static int aNodeId(const Node& node) {
1638 return node.id >> 1;
1640 static Node nodeFromANodeId(int id) {
1641 return Node(id << 1);
1643 int maxANodeId() const {
1644 return aNodes.size();
1647 static int bNodeId(const Node& node) {
1648 return node.id >> 1;
1650 static Node nodeFromBNodeId(int id) {
1651 return Node((id << 1) + 1);
1653 int maxBNodeId() const {
1654 return bNodes.size();
1657 Node aNode(const UEdge& edge) const {
1658 return Node(edges[edge.id].aNode);
1660 Node bNode(const UEdge& edge) const {
1661 return Node(edges[edge.id].bNode);
1664 static bool aNode(const Node& node) {
1665 return (node.id & 1) == 0;
1668 static bool bNode(const Node& node) {
1669 return (node.id & 1) == 1;
1674 if (first_free_anode == -1) {
1675 aid = aNodes.size();
1676 aNodes.push_back(NodeT());
1678 aid = first_free_anode;
1679 first_free_anode = aNodes[first_free_anode].next;
1681 if (first_anode != -1) {
1682 aNodes[aid].next = first_anode << 1;
1683 aNodes[first_anode].prev = aid << 1;
1685 aNodes[aid].next = -1;
1687 aNodes[aid].prev = -1;
1689 aNodes[aid].first_edge = -1;
1690 return Node(aid << 1);
1695 if (first_free_bnode == -1) {
1696 bid = bNodes.size();
1697 bNodes.push_back(NodeT());
1699 bid = first_free_bnode;
1700 first_free_bnode = bNodes[first_free_bnode].next;
1702 if (first_bnode != -1) {
1703 bNodes[bid].next = (first_bnode << 1) + 1;
1704 bNodes[first_bnode].prev = (bid << 1) + 1;
1706 bNodes[bid].next = -1;
1708 bNodes[bid].prev = -1;
1710 bNodes[bid].first_edge = -1;
1711 return Node((bid << 1) + 1);
1714 UEdge addEdge(const Node& source, const Node& target) {
1715 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1717 if (first_free_edge != -1) {
1718 edgeId = first_free_edge;
1719 first_free_edge = edges[edgeId].next_out;
1721 edgeId = edges.size();
1722 edges.push_back(UEdgeT());
1724 if ((source.id & 1) == 0) {
1725 edges[edgeId].aNode = source.id;
1726 edges[edgeId].bNode = target.id;
1728 edges[edgeId].aNode = target.id;
1729 edges[edgeId].bNode = source.id;
1731 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1732 edges[edgeId].prev_out = -1;
1733 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1734 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1736 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1737 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1738 edges[edgeId].prev_in = -1;
1739 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1740 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1742 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1743 return UEdge(edgeId);
1746 void erase(const Node& node) {
1748 int aid = node.id >> 1;
1749 if (aNodes[aid].prev != -1) {
1750 aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next;
1753 aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1;
1755 if (aNodes[aid].next != -1) {
1756 aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev;
1758 aNodes[aid].next = first_free_anode;
1759 first_free_anode = aid;
1761 int bid = node.id >> 1;
1762 if (bNodes[bid].prev != -1) {
1763 bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next;
1766 bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1;
1768 if (bNodes[bid].next != -1) {
1769 bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev;
1771 bNodes[bid].next = first_free_bnode;
1772 first_free_bnode = bid;
1776 void erase(const UEdge& edge) {
1778 if (edges[edge.id].prev_out != -1) {
1779 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1781 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1783 if (edges[edge.id].next_out != -1) {
1784 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1787 if (edges[edge.id].prev_in != -1) {
1788 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1790 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1792 if (edges[edge.id].next_in != -1) {
1793 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1796 edges[edge.id].next_out = first_free_edge;
1797 first_free_edge = edge.id;
1805 first_free_anode = -1;
1807 first_free_bnode = -1;
1808 first_free_edge = -1;
1811 void changeANode(const UEdge& edge, const Node& node) {
1812 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1813 if (edges[edge.id].prev_out != -1) {
1814 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1816 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1818 if (edges[edge.id].next_out != -1) {
1819 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1821 if (aNodes[node.id >> 1].first_edge != -1) {
1822 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1824 edges[edge.id].prev_out = -1;
1825 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1826 aNodes[node.id >> 1].first_edge = edge.id;
1827 edges[edge.id].aNode = node.id;
1830 void changeBNode(const UEdge& edge, const Node& node) {
1831 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1832 if (edges[edge.id].prev_in != -1) {
1833 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1835 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1837 if (edges[edge.id].next_in != -1) {
1838 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1840 if (bNodes[node.id >> 1].first_edge != -1) {
1841 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1843 edges[edge.id].prev_in = -1;
1844 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1845 bNodes[node.id >> 1].first_edge = edge.id;
1846 edges[edge.id].bNode = node.id;
1852 typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1853 ExtendedListBpUGraphBase;
1857 /// \brief A smart bipartite undirected graph class.
1859 /// This is a bipartite undirected graph implementation.
1860 /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
1862 ///An important extra feature of this graph implementation is that
1863 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1865 /// \sa concepts::BpUGraph.
1867 class ListBpUGraph : public ExtendedListBpUGraphBase {
1868 /// \brief ListBpUGraph is \e not copy constructible.
1870 ///ListBpUGraph is \e not copy constructible.
1871 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1872 /// \brief Assignment of ListBpUGraph to another one is \e not
1875 /// Assignment of ListBpUGraph to another one is \e not allowed.
1876 void operator=(const ListBpUGraph &) {}
1878 /// \brief Constructor
1884 typedef ExtendedListBpUGraphBase Parent;
1885 /// \brief Add a new ANode to the graph.
1887 /// \return the new node.
1889 Node addANode() { return Parent::addANode(); }
1891 /// \brief Add a new BNode to the graph.
1893 /// \return the new node.
1895 Node addBNode() { return Parent::addBNode(); }
1897 /// \brief Add a new edge to the graph.
1899 /// Add a new edge to the graph with an ANode and a BNode.
1900 /// \return the new undirected edge.
1901 UEdge addEdge(const Node& s, const Node& t) {
1902 return Parent::addEdge(s, t);
1905 /// \brief Changes the ANode of \c e to \c n
1907 /// Changes the ANode of \c e to \c n
1909 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1910 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1912 void changeANode(UEdge e, Node n) {
1913 Parent::changeANode(e,n);
1916 /// \brief Changes the BNode of \c e to \c n
1918 /// Changes the BNode of \c e to \c n
1920 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1921 /// referencing the changed edge remain
1922 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1923 void changeBNode(UEdge e, Node n) {
1924 Parent::changeBNode(e,n);
1927 /// \brief Changes the source(ANode) of \c e to \c n
1929 /// Changes the source(ANode) of \c e to \c n
1931 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1932 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1934 void changeSource(UEdge e, Node n) {
1935 Parent::changeANode(e,n);
1938 /// \brief Changes the target(BNode) of \c e to \c n
1940 /// Changes the target(BNode) of \c e to \c n
1942 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1943 /// referencing the changed edge remain
1944 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1945 void changeTarget(UEdge e, Node n) {
1946 Parent::changeBNode(e,n);
1949 /// \brief Changes the source of \c e to \c n
1951 /// Changes the source of \c e to \c n. It changes the proper
1952 /// node of the represented undirected edge.
1954 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1955 ///referencing the changed edge remain
1956 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1957 void changeSource(Edge e, Node n) {
1958 if (Parent::direction(e)) {
1959 Parent::changeANode(e,n);
1961 Parent::changeBNode(e,n);
1964 /// \brief Changes the target of \c e to \c n
1966 /// Changes the target of \c e to \c n. It changes the proper
1967 /// node of the represented undirected edge.
1969 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1970 ///referencing the changed edge remain
1971 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1972 void changeTarget(Edge e, Node n) {
1973 if (Parent::direction(e)) {
1974 Parent::changeBNode(e,n);
1976 Parent::changeANode(e,n);
1979 /// \brief Contract two nodes.
1981 /// This function contracts two nodes.
1983 /// Node \p b will be removed but instead of deleting its
1984 /// neighboring edges, they will be joined to \p a. The two nodes
1985 /// should be from the same nodeset, of course.
1987 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1989 void contract(const Node& a, const Node& b) {
1990 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1991 if (Parent::aNode(a)) {
1992 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1993 IncEdgeIt f = e; ++f;
1998 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1999 IncEdgeIt f = e; ++f;
2007 /// \brief Class to make a snapshot of the graph and restore
2010 /// Class to make a snapshot of the graph and to restore it
2013 /// The newly added nodes and undirected edges can be removed
2014 /// using the restore() function.
2016 /// \warning Edge and node deletions cannot be restored. This
2017 /// events invalidate the snapshot.
2021 typedef Parent::NodeNotifier NodeNotifier;
2023 class NodeObserverProxy : public NodeNotifier::ObserverBase {
2026 NodeObserverProxy(Snapshot& _snapshot)
2027 : snapshot(_snapshot) {}
2029 using NodeNotifier::ObserverBase::attach;
2030 using NodeNotifier::ObserverBase::detach;
2031 using NodeNotifier::ObserverBase::attached;
2035 virtual void add(const Node& node) {
2036 snapshot.addNode(node);
2038 virtual void add(const std::vector<Node>& nodes) {
2039 for (int i = nodes.size() - 1; i >= 0; ++i) {
2040 snapshot.addNode(nodes[i]);
2043 virtual void erase(const Node& node) {
2044 snapshot.eraseNode(node);
2046 virtual void erase(const std::vector<Node>& nodes) {
2047 for (int i = 0; i < int(nodes.size()); ++i) {
2048 snapshot.eraseNode(nodes[i]);
2051 virtual void build() {
2053 std::vector<Node> nodes;
2054 for (notifier()->first(node); node != INVALID;
2055 notifier()->next(node)) {
2056 nodes.push_back(node);
2058 for (int i = nodes.size() - 1; i >= 0; --i) {
2059 snapshot.addNode(nodes[i]);
2062 virtual void clear() {
2064 for (notifier()->first(node); node != INVALID;
2065 notifier()->next(node)) {
2066 snapshot.eraseNode(node);
2073 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
2076 UEdgeObserverProxy(Snapshot& _snapshot)
2077 : snapshot(_snapshot) {}
2079 using UEdgeNotifier::ObserverBase::attach;
2080 using UEdgeNotifier::ObserverBase::detach;
2081 using UEdgeNotifier::ObserverBase::attached;
2085 virtual void add(const UEdge& edge) {
2086 snapshot.addUEdge(edge);
2088 virtual void add(const std::vector<UEdge>& edges) {
2089 for (int i = edges.size() - 1; i >= 0; ++i) {
2090 snapshot.addUEdge(edges[i]);
2093 virtual void erase(const UEdge& edge) {
2094 snapshot.eraseUEdge(edge);
2096 virtual void erase(const std::vector<UEdge>& edges) {
2097 for (int i = 0; i < int(edges.size()); ++i) {
2098 snapshot.eraseUEdge(edges[i]);
2101 virtual void build() {
2103 std::vector<UEdge> edges;
2104 for (notifier()->first(edge); edge != INVALID;
2105 notifier()->next(edge)) {
2106 edges.push_back(edge);
2108 for (int i = edges.size() - 1; i >= 0; --i) {
2109 snapshot.addUEdge(edges[i]);
2112 virtual void clear() {
2114 for (notifier()->first(edge); edge != INVALID;
2115 notifier()->next(edge)) {
2116 snapshot.eraseUEdge(edge);
2123 ListBpUGraph *graph;
2125 NodeObserverProxy node_observer_proxy;
2126 UEdgeObserverProxy edge_observer_proxy;
2128 std::list<Node> added_nodes;
2129 std::list<UEdge> added_edges;
2132 void addNode(const Node& node) {
2133 added_nodes.push_front(node);
2135 void eraseNode(const Node& node) {
2136 std::list<Node>::iterator it =
2137 std::find(added_nodes.begin(), added_nodes.end(), node);
2138 if (it == added_nodes.end()) {
2140 edge_observer_proxy.detach();
2141 throw NodeNotifier::ImmediateDetach();
2143 added_nodes.erase(it);
2147 void addUEdge(const UEdge& edge) {
2148 added_edges.push_front(edge);
2150 void eraseUEdge(const UEdge& edge) {
2151 std::list<UEdge>::iterator it =
2152 std::find(added_edges.begin(), added_edges.end(), edge);
2153 if (it == added_edges.end()) {
2155 node_observer_proxy.detach();
2156 throw UEdgeNotifier::ImmediateDetach();
2158 added_edges.erase(it);
2162 void attach(ListBpUGraph &_graph) {
2164 node_observer_proxy.attach(graph->notifier(Node()));
2165 edge_observer_proxy.attach(graph->notifier(UEdge()));
2169 node_observer_proxy.detach();
2170 edge_observer_proxy.detach();
2173 bool attached() const {
2174 return node_observer_proxy.attached();
2178 added_nodes.clear();
2179 added_edges.clear();
2184 /// \brief Default constructor.
2186 /// Default constructor.
2187 /// To actually make a snapshot you must call save().
2189 : graph(0), node_observer_proxy(*this),
2190 edge_observer_proxy(*this) {}
2192 /// \brief Constructor that immediately makes a snapshot.
2194 /// This constructor immediately makes a snapshot of the graph.
2195 /// \param _graph The graph we make a snapshot of.
2196 Snapshot(ListBpUGraph &_graph)
2197 : node_observer_proxy(*this),
2198 edge_observer_proxy(*this) {
2202 /// \brief Make a snapshot.
2204 /// Make a snapshot of the graph.
2206 /// This function can be called more than once. In case of a repeated
2207 /// call, the previous snapshot gets lost.
2208 /// \param _graph The graph we make the snapshot of.
2209 void save(ListBpUGraph &_graph) {
2217 /// \brief Undo the changes until the last snapshot.
2219 /// Undo the changes until the last snapshot created by save().
2222 for(std::list<UEdge>::iterator it = added_edges.begin();
2223 it != added_edges.end(); ++it) {
2226 for(std::list<Node>::iterator it = added_nodes.begin();
2227 it != added_nodes.end(); ++it) {
2233 /// \brief Gives back true when the snapshot is valid.
2235 /// Gives back true when the snapshot is valid.
2236 bool valid() const {