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) {}
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() {
530 NodeNotifier* notifier = getNotifier();
532 std::vector<Node> nodes;
533 for (notifier->first(node); node != INVALID; 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() {
541 NodeNotifier* notifier = getNotifier();
543 for (notifier->first(node); node != INVALID; 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() {
580 EdgeNotifier* notifier = getNotifier();
582 std::vector<Edge> edges;
583 for (notifier->first(edge); edge != INVALID; 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() {
591 EdgeNotifier* notifier = getNotifier();
593 for (notifier->first(edge); edge != INVALID; 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->getNotifier(Node()));
643 edge_observer_proxy.attach(graph->getNotifier(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;
752 friend class ListUGraphBase;
756 explicit Node(int pid) { id = pid;}
760 Node (Invalid) { id = -1; }
761 bool operator==(const Node& node) const {return id == node.id;}
762 bool operator!=(const Node& node) const {return id != node.id;}
763 bool operator<(const Node& node) const {return id < node.id;}
767 friend class ListUGraphBase;
768 friend class ListUGraphBase::Edge;
772 explicit UEdge(int pid) { id = pid;}
776 UEdge (Invalid) { id = -1; }
777 bool operator==(const UEdge& edge) const {return id == edge.id;}
778 bool operator!=(const UEdge& edge) const {return id != edge.id;}
779 bool operator<(const UEdge& edge) const {return id < edge.id;}
783 friend class ListUGraphBase;
787 explicit Edge(int pid) { id = pid;}
790 operator UEdge() const { return UEdge(id / 2); }
793 Edge (Invalid) { id = -1; }
794 bool operator==(const Edge& edge) const {return id == edge.id;}
795 bool operator!=(const Edge& edge) const {return id != edge.id;}
796 bool operator<(const Edge& edge) const {return id < edge.id;}
802 : nodes(), first_node(-1),
803 first_free_node(-1), edges(), first_free_edge(-1) {}
806 int maxNodeId() const { return nodes.size()-1; }
807 int maxUEdgeId() const { return edges.size() / 2 - 1; }
808 int maxEdgeId() const { return edges.size()-1; }
810 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
811 Node target(Edge e) const { return Node(edges[e.id].target); }
813 Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
814 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
816 static bool direction(Edge e) {
817 return (e.id & 1) == 1;
820 static Edge direct(UEdge e, bool d) {
821 return Edge(e.id * 2 + (d ? 1 : 0));
824 void first(Node& node) const {
825 node.id = first_node;
828 void next(Node& node) const {
829 node.id = nodes[node.id].next;
832 void first(Edge& e) const {
834 while (n != -1 && nodes[n].first_out == -1) {
837 e.id = (n == -1) ? -1 : nodes[n].first_out;
840 void next(Edge& e) const {
841 if (edges[e.id].next_out != -1) {
842 e.id = edges[e.id].next_out;
844 int n = nodes[edges[e.id ^ 1].target].next;
845 while(n != -1 && nodes[n].first_out == -1) {
848 e.id = (n == -1) ? -1 : nodes[n].first_out;
852 void first(UEdge& e) const {
855 e.id = nodes[n].first_out;
856 while ((e.id & 1) != 1) {
857 e.id = edges[e.id].next_out;
868 void next(UEdge& e) const {
869 int n = edges[e.id * 2].target;
870 e.id = edges[(e.id * 2) | 1].next_out;
871 while ((e.id & 1) != 1) {
872 e.id = edges[e.id].next_out;
880 e.id = nodes[n].first_out;
881 while ((e.id & 1) != 1) {
882 e.id = edges[e.id].next_out;
893 void firstOut(Edge &e, const Node& v) const {
894 e.id = nodes[v.id].first_out;
896 void nextOut(Edge &e) const {
897 e.id = edges[e.id].next_out;
900 void firstIn(Edge &e, const Node& v) const {
901 e.id = ((nodes[v.id].first_out) ^ 1);
902 if (e.id == -2) e.id = -1;
904 void nextIn(Edge &e) const {
905 e.id = ((edges[e.id ^ 1].next_out) ^ 1);
906 if (e.id == -2) e.id = -1;
909 void firstInc(UEdge &e, bool& d, const Node& v) const {
910 int de = nodes[v.id].first_out;
914 void nextInc(UEdge &e, bool& d) const {
915 int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
920 static int id(Node v) { return v.id; }
921 static int id(Edge e) { return e.id; }
922 static int id(UEdge e) { return e.id; }
924 static Node nodeFromId(int id) { return Node(id);}
925 static Edge edgeFromId(int id) { return Edge(id);}
926 static UEdge uEdgeFromId(int id) { return UEdge(id);}
931 if(first_free_node==-1) {
933 nodes.push_back(NodeT());
936 first_free_node = nodes[n].next;
939 nodes[n].next = first_node;
940 if (first_node != -1) nodes[first_node].prev = n;
944 nodes[n].first_out = -1;
949 UEdge addEdge(Node u, Node v) {
952 if (first_free_edge == -1) {
954 edges.push_back(EdgeT());
955 edges.push_back(EdgeT());
958 first_free_edge = edges[n].next_out;
961 edges[n].target = u.id;
962 edges[n | 1].target = v.id;
964 edges[n].next_out = nodes[v.id].first_out;
965 edges[n | 1].next_out = nodes[u.id].first_out;
966 if (nodes[v.id].first_out != -1) {
967 edges[nodes[v.id].first_out].prev_out = n;
969 if (nodes[u.id].first_out != -1) {
970 edges[nodes[u.id].first_out].prev_out = (n | 1);
973 edges[n].prev_out = edges[n | 1].prev_out = -1;
975 nodes[v.id].first_out = n;
976 nodes[u.id].first_out = (n | 1);
981 void erase(const Node& node) {
984 if(nodes[n].next != -1) {
985 nodes[nodes[n].next].prev = nodes[n].prev;
988 if(nodes[n].prev != -1) {
989 nodes[nodes[n].prev].next = nodes[n].next;
991 first_node = nodes[n].next;
994 nodes[n].next = first_free_node;
999 void erase(const UEdge& edge) {
1000 int n = edge.id * 2;
1002 if (edges[n].next_out != -1) {
1003 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1006 if (edges[n].prev_out != -1) {
1007 edges[edges[n].prev_out].next_out = edges[n].next_out;
1009 nodes[edges[n | 1].target].first_out = edges[n].next_out;
1012 if (edges[n | 1].next_out != -1) {
1013 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1016 if (edges[n | 1].prev_out != -1) {
1017 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1019 nodes[edges[n].target].first_out = edges[n | 1].next_out;
1022 edges[n].next_out = first_free_edge;
1023 first_free_edge = n;
1030 first_node = first_free_node = first_free_edge = -1;
1035 void changeTarget(UEdge e, Node n) {
1036 if(edges[2 * e.id].next_out != -1) {
1037 edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1039 if(edges[2 * e.id].prev_out != -1) {
1040 edges[edges[2 * e.id].prev_out].next_out =
1041 edges[2 * e.id].next_out;
1043 nodes[edges[(2 * e.id) | 1].target].first_out =
1044 edges[2 * e.id].next_out;
1047 if (nodes[n.id].first_out != -1) {
1048 edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1050 edges[(2 * e.id) | 1].target = n.id;
1051 edges[2 * e.id].prev_out = -1;
1052 edges[2 * e.id].next_out = nodes[n.id].first_out;
1053 nodes[n.id].first_out = 2 * e.id;
1056 void changeSource(UEdge e, Node n) {
1057 if(edges[(2 * e.id) | 1].next_out != -1) {
1058 edges[edges[(2 * e.id) | 1].next_out].prev_out =
1059 edges[(2 * e.id) | 1].prev_out;
1061 if(edges[(2 * e.id) | 1].prev_out != -1) {
1062 edges[edges[(2 * e.id) | 1].prev_out].next_out =
1063 edges[(2 * e.id) | 1].next_out;
1065 nodes[edges[2 * e.id].target].first_out =
1066 edges[(2 * e.id) | 1].next_out;
1069 if (nodes[n.id].first_out != -1) {
1070 edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1072 edges[2 * e.id].target = n.id;
1073 edges[(2 * e.id) | 1].prev_out = -1;
1074 edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1075 nodes[n.id].first_out = ((2 * e.id) | 1);
1080 // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1081 // ExtendedListUGraphBase;
1083 typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1087 /// \addtogroup graphs
1090 ///An undirected list graph class.
1092 ///This is a simple and fast undirected graph implementation.
1094 ///An important extra feature of this graph implementation is that
1095 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1097 ///It conforms to the
1098 ///\ref concepts::UGraph "UGraph concept".
1100 ///\sa concepts::UGraph.
1102 class ListUGraph : public ExtendedListUGraphBase {
1104 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1106 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1108 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
1109 ///\brief Assignment of ListUGraph to another one is \e not allowed.
1110 ///Use UGraphCopy() instead.
1112 ///Assignment of ListUGraph to another one is \e not allowed.
1113 ///Use UGraphCopy() instead.
1114 void operator=(const ListUGraph &) {}
1122 typedef ExtendedListUGraphBase Parent;
1124 typedef Parent::OutEdgeIt IncEdgeIt;
1126 /// \brief Add a new node to the graph.
1128 /// \return the new node.
1130 Node addNode() { return Parent::addNode(); }
1132 /// \brief Add a new edge to the graph.
1134 /// Add a new edge to the graph with source node \c s
1135 /// and target node \c t.
1136 /// \return the new undirected edge.
1137 UEdge addEdge(const Node& s, const Node& t) {
1138 return Parent::addEdge(s, t);
1140 /// \brief Changes the source of \c e to \c n
1142 /// Changes the source of \c e to \c n
1144 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1145 ///referencing the changed edge remain
1146 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1147 void changeSource(UEdge e, Node n) {
1148 Parent::changeSource(e,n);
1150 /// \brief Changes the target of \c e to \c n
1152 /// Changes the target of \c e to \c n
1154 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
1155 /// valid. However the other iterators may be invalidated.
1156 void changeTarget(UEdge e, Node n) {
1157 Parent::changeTarget(e,n);
1159 /// \brief Changes the source of \c e to \c n
1161 /// Changes the source of \c e to \c n. It changes the proper
1162 /// node of the represented undirected edge.
1164 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1165 ///referencing the changed edge remain
1166 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1167 void changeSource(Edge e, Node n) {
1168 if (Parent::direction(e)) {
1169 Parent::changeSource(e,n);
1171 Parent::changeTarget(e,n);
1174 /// \brief Changes the target of \c e to \c n
1176 /// Changes the target of \c e to \c n. It changes the proper
1177 /// node of the represented undirected edge.
1179 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1180 ///referencing the changed edge remain
1181 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1182 void changeTarget(Edge e, Node n) {
1183 if (Parent::direction(e)) {
1184 Parent::changeTarget(e,n);
1186 Parent::changeSource(e,n);
1189 /// \brief Contract two nodes.
1191 /// This function contracts two nodes.
1193 /// Node \p b will be removed but instead of deleting
1194 /// its neighboring edges, they will be joined to \p a.
1195 /// The last parameter \p r controls whether to remove loops. \c true
1196 /// means that loops will be removed.
1198 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1200 void contract(Node a, Node b, bool r = true) {
1201 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1202 IncEdgeIt f = e; ++f;
1203 if (r && runningNode(e) == a) {
1205 } else if (source(e) == b) {
1216 /// \brief Class to make a snapshot of the graph and restore
1219 /// Class to make a snapshot of the graph and to restore it
1222 /// The newly added nodes and undirected edges can be removed
1223 /// using the restore() function.
1225 /// \warning Edge and node deletions cannot be restored. This
1226 /// events invalidate the snapshot.
1230 typedef Parent::NodeNotifier NodeNotifier;
1232 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1235 NodeObserverProxy(Snapshot& _snapshot)
1236 : snapshot(_snapshot) {}
1238 using NodeNotifier::ObserverBase::attach;
1239 using NodeNotifier::ObserverBase::detach;
1240 using NodeNotifier::ObserverBase::attached;
1244 virtual void add(const Node& node) {
1245 snapshot.addNode(node);
1247 virtual void add(const std::vector<Node>& nodes) {
1248 for (int i = nodes.size() - 1; i >= 0; ++i) {
1249 snapshot.addNode(nodes[i]);
1252 virtual void erase(const Node& node) {
1253 snapshot.eraseNode(node);
1255 virtual void erase(const std::vector<Node>& nodes) {
1256 for (int i = 0; i < (int)nodes.size(); ++i) {
1257 snapshot.eraseNode(nodes[i]);
1260 virtual void build() {
1261 NodeNotifier* notifier = getNotifier();
1263 std::vector<Node> nodes;
1264 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1265 nodes.push_back(node);
1267 for (int i = nodes.size() - 1; i >= 0; --i) {
1268 snapshot.addNode(nodes[i]);
1271 virtual void clear() {
1272 NodeNotifier* notifier = getNotifier();
1274 for (notifier->first(node); node != INVALID; notifier->next(node)) {
1275 snapshot.eraseNode(node);
1282 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1285 UEdgeObserverProxy(Snapshot& _snapshot)
1286 : snapshot(_snapshot) {}
1288 using UEdgeNotifier::ObserverBase::attach;
1289 using UEdgeNotifier::ObserverBase::detach;
1290 using UEdgeNotifier::ObserverBase::attached;
1294 virtual void add(const UEdge& edge) {
1295 snapshot.addUEdge(edge);
1297 virtual void add(const std::vector<UEdge>& edges) {
1298 for (int i = edges.size() - 1; i >= 0; ++i) {
1299 snapshot.addUEdge(edges[i]);
1302 virtual void erase(const UEdge& edge) {
1303 snapshot.eraseUEdge(edge);
1305 virtual void erase(const std::vector<UEdge>& edges) {
1306 for (int i = 0; i < (int)edges.size(); ++i) {
1307 snapshot.eraseUEdge(edges[i]);
1310 virtual void build() {
1311 UEdgeNotifier* notifier = getNotifier();
1313 std::vector<UEdge> edges;
1314 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1315 edges.push_back(edge);
1317 for (int i = edges.size() - 1; i >= 0; --i) {
1318 snapshot.addUEdge(edges[i]);
1321 virtual void clear() {
1322 UEdgeNotifier* notifier = getNotifier();
1324 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1325 snapshot.eraseUEdge(edge);
1334 NodeObserverProxy node_observer_proxy;
1335 UEdgeObserverProxy edge_observer_proxy;
1337 std::list<Node> added_nodes;
1338 std::list<UEdge> added_edges;
1341 void addNode(const Node& node) {
1342 added_nodes.push_front(node);
1344 void eraseNode(const Node& node) {
1345 std::list<Node>::iterator it =
1346 std::find(added_nodes.begin(), added_nodes.end(), node);
1347 if (it == added_nodes.end()) {
1349 edge_observer_proxy.detach();
1350 throw NodeNotifier::ImmediateDetach();
1352 added_nodes.erase(it);
1356 void addUEdge(const UEdge& edge) {
1357 added_edges.push_front(edge);
1359 void eraseUEdge(const UEdge& edge) {
1360 std::list<UEdge>::iterator it =
1361 std::find(added_edges.begin(), added_edges.end(), edge);
1362 if (it == added_edges.end()) {
1364 node_observer_proxy.detach();
1365 throw UEdgeNotifier::ImmediateDetach();
1367 added_edges.erase(it);
1371 void attach(ListUGraph &_graph) {
1373 node_observer_proxy.attach(graph->getNotifier(Node()));
1374 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
1378 node_observer_proxy.detach();
1379 edge_observer_proxy.detach();
1382 bool attached() const {
1383 return node_observer_proxy.attached();
1387 added_nodes.clear();
1388 added_edges.clear();
1393 /// \brief Default constructor.
1395 /// Default constructor.
1396 /// To actually make a snapshot you must call save().
1398 : graph(0), node_observer_proxy(*this),
1399 edge_observer_proxy(*this) {}
1401 /// \brief Constructor that immediately makes a snapshot.
1403 /// This constructor immediately makes a snapshot of the graph.
1404 /// \param _graph The graph we make a snapshot of.
1405 Snapshot(ListUGraph &_graph)
1406 : node_observer_proxy(*this),
1407 edge_observer_proxy(*this) {
1411 /// \brief Make a snapshot.
1413 /// Make a snapshot of the graph.
1415 /// This function can be called more than once. In case of a repeated
1416 /// call, the previous snapshot gets lost.
1417 /// \param _graph The graph we make the snapshot of.
1418 void save(ListUGraph &_graph) {
1426 /// \brief Undo the changes until the last snapshot.
1428 /// Undo the changes until the last snapshot created by save().
1431 for(std::list<UEdge>::iterator it = added_edges.begin();
1432 it != added_edges.end(); ++it) {
1435 for(std::list<Node>::iterator it = added_nodes.begin();
1436 it != added_nodes.end(); ++it) {
1442 /// \brief Gives back true when the snapshot is valid.
1444 /// Gives back true when the snapshot is valid.
1445 bool valid() const {
1452 class ListBpUGraphBase {
1455 class NodeSetError : public LogicError {
1457 virtual const char* what() const throw() {
1458 return "lemon::ListBpUGraph::NodeSetError";
1465 int first_edge, prev, next;
1469 int aNode, prev_out, next_out;
1470 int bNode, prev_in, next_in;
1473 std::vector<NodeT> aNodes;
1474 std::vector<NodeT> bNodes;
1476 std::vector<UEdgeT> edges;
1479 int first_free_anode;
1482 int first_free_bnode;
1484 int first_free_edge;
1489 friend class ListBpUGraphBase;
1493 explicit Node(int _id) : id(_id) {}
1496 Node(Invalid) { id = -1; }
1497 bool operator==(const Node i) const {return id==i.id;}
1498 bool operator!=(const Node i) const {return id!=i.id;}
1499 bool operator<(const Node i) const {return id<i.id;}
1503 friend class ListBpUGraphBase;
1507 explicit UEdge(int _id) { id = _id;}
1510 UEdge (Invalid) { id = -1; }
1511 bool operator==(const UEdge i) const {return id==i.id;}
1512 bool operator!=(const UEdge i) const {return id!=i.id;}
1513 bool operator<(const UEdge i) const {return id<i.id;}
1517 : first_anode(-1), first_free_anode(-1),
1518 first_bnode(-1), first_free_bnode(-1),
1519 first_free_edge(-1) {}
1521 void firstANode(Node& node) const {
1522 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1524 void nextANode(Node& node) const {
1525 node.id = aNodes[node.id >> 1].next;
1528 void firstBNode(Node& node) const {
1529 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1531 void nextBNode(Node& node) const {
1532 node.id = bNodes[node.id >> 1].next;
1535 void first(Node& node) const {
1536 if (first_anode != -1) {
1537 node.id = (first_anode << 1);
1538 } else if (first_bnode != -1) {
1539 node.id = (first_bnode << 1) + 1;
1544 void next(Node& node) const {
1546 node.id = aNodes[node.id >> 1].next;
1547 if (node.id == -1) {
1548 if (first_bnode != -1) {
1549 node.id = (first_bnode << 1) + 1;
1553 node.id = bNodes[node.id >> 1].next;
1557 void first(UEdge& edge) const {
1558 int aNodeId = first_anode;
1559 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1560 aNodeId = aNodes[aNodeId].next != -1 ?
1561 aNodes[aNodeId].next >> 1 : -1;
1563 if (aNodeId != -1) {
1564 edge.id = aNodes[aNodeId].first_edge;
1569 void next(UEdge& edge) const {
1570 int aNodeId = edges[edge.id].aNode >> 1;
1571 edge.id = edges[edge.id].next_out;
1572 if (edge.id == -1) {
1573 aNodeId = aNodes[aNodeId].next != -1 ?
1574 aNodes[aNodeId].next >> 1 : -1;
1575 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
1576 aNodeId = aNodes[aNodeId].next != -1 ?
1577 aNodes[aNodeId].next >> 1 : -1;
1579 if (aNodeId != -1) {
1580 edge.id = aNodes[aNodeId].first_edge;
1587 void firstFromANode(UEdge& edge, const Node& node) const {
1588 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1589 edge.id = aNodes[node.id >> 1].first_edge;
1591 void nextFromANode(UEdge& edge) const {
1592 edge.id = edges[edge.id].next_out;
1595 void firstFromBNode(UEdge& edge, const Node& node) const {
1596 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1597 edge.id = bNodes[node.id >> 1].first_edge;
1599 void nextFromBNode(UEdge& edge) const {
1600 edge.id = edges[edge.id].next_in;
1603 static int id(const Node& node) {
1606 static Node nodeFromId(int id) {
1609 int maxNodeId() const {
1610 return aNodes.size() > bNodes.size() ?
1611 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1614 static int id(const UEdge& edge) {
1617 static UEdge uEdgeFromId(int id) {
1620 int maxUEdgeId() const {
1621 return edges.size();
1624 static int aNodeId(const Node& node) {
1625 return node.id >> 1;
1627 static Node nodeFromANodeId(int id) {
1628 return Node(id << 1);
1630 int maxANodeId() const {
1631 return aNodes.size();
1634 static int bNodeId(const Node& node) {
1635 return node.id >> 1;
1637 static Node nodeFromBNodeId(int id) {
1638 return Node((id << 1) + 1);
1640 int maxBNodeId() const {
1641 return bNodes.size();
1644 Node aNode(const UEdge& edge) const {
1645 return Node(edges[edge.id].aNode);
1647 Node bNode(const UEdge& edge) const {
1648 return Node(edges[edge.id].bNode);
1651 static bool aNode(const Node& node) {
1652 return (node.id & 1) == 0;
1655 static bool bNode(const Node& node) {
1656 return (node.id & 1) == 1;
1661 if (first_free_anode == -1) {
1662 aNodeId = aNodes.size();
1663 aNodes.push_back(NodeT());
1665 aNodeId = first_free_anode;
1666 first_free_anode = aNodes[first_free_anode].next;
1668 if (first_anode != -1) {
1669 aNodes[aNodeId].next = first_anode << 1;
1670 aNodes[first_anode].prev = aNodeId << 1;
1672 aNodes[aNodeId].next = -1;
1674 aNodes[aNodeId].prev = -1;
1675 first_anode = aNodeId;
1676 aNodes[aNodeId].first_edge = -1;
1677 return Node(aNodeId << 1);
1682 if (first_free_bnode == -1) {
1683 bNodeId = bNodes.size();
1684 bNodes.push_back(NodeT());
1686 bNodeId = first_free_bnode;
1687 first_free_bnode = bNodes[first_free_bnode].next;
1689 if (first_bnode != -1) {
1690 bNodes[bNodeId].next = (first_bnode << 1) + 1;
1691 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1693 bNodes[bNodeId].next = -1;
1695 bNodes[bNodeId].prev = -1;
1696 first_bnode = bNodeId;
1697 bNodes[bNodeId].first_edge = -1;
1698 return Node((bNodeId << 1) + 1);
1701 UEdge addEdge(const Node& source, const Node& target) {
1702 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1704 if (first_free_edge != -1) {
1705 edgeId = first_free_edge;
1706 first_free_edge = edges[edgeId].next_out;
1708 edgeId = edges.size();
1709 edges.push_back(UEdgeT());
1711 if ((source.id & 1) == 0) {
1712 edges[edgeId].aNode = source.id;
1713 edges[edgeId].bNode = target.id;
1715 edges[edgeId].aNode = target.id;
1716 edges[edgeId].bNode = source.id;
1718 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1719 edges[edgeId].prev_out = -1;
1720 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1721 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1723 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1724 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1725 edges[edgeId].prev_in = -1;
1726 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1727 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1729 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1730 return UEdge(edgeId);
1733 void erase(const Node& node) {
1735 int aNodeId = node.id >> 1;
1736 if (aNodes[aNodeId].prev != -1) {
1737 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1740 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
1742 if (aNodes[aNodeId].next != -1) {
1743 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1745 aNodes[aNodeId].next = first_free_anode;
1746 first_free_anode = aNodeId;
1748 int bNodeId = node.id >> 1;
1749 if (bNodes[bNodeId].prev != -1) {
1750 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1753 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
1755 if (bNodes[bNodeId].next != -1) {
1756 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1758 bNodes[bNodeId].next = first_free_bnode;
1759 first_free_bnode = bNodeId;
1763 void erase(const UEdge& edge) {
1765 if (edges[edge.id].prev_out != -1) {
1766 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1768 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1770 if (edges[edge.id].next_out != -1) {
1771 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1774 if (edges[edge.id].prev_in != -1) {
1775 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1777 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1779 if (edges[edge.id].next_in != -1) {
1780 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1783 edges[edge.id].next_out = first_free_edge;
1784 first_free_edge = edge.id;
1792 first_free_anode = -1;
1794 first_free_bnode = -1;
1795 first_free_edge = -1;
1798 void changeANode(const UEdge& edge, const Node& node) {
1799 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1800 if (edges[edge.id].prev_out != -1) {
1801 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1803 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1805 if (edges[edge.id].next_out != -1) {
1806 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1808 if (aNodes[node.id >> 1].first_edge != -1) {
1809 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1811 edges[edge.id].prev_out = -1;
1812 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1813 aNodes[node.id >> 1].first_edge = edge.id;
1814 edges[edge.id].aNode = node.id;
1817 void changeBNode(const UEdge& edge, const Node& node) {
1818 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1819 if (edges[edge.id].prev_in != -1) {
1820 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1822 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1824 if (edges[edge.id].next_in != -1) {
1825 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1827 if (bNodes[node.id >> 1].first_edge != -1) {
1828 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1830 edges[edge.id].prev_in = -1;
1831 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1832 bNodes[node.id >> 1].first_edge = edge.id;
1833 edges[edge.id].bNode = node.id;
1839 typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1840 ExtendedListBpUGraphBase;
1844 /// \brief A smart bipartite undirected graph class.
1846 /// This is a bipartite undirected graph implementation.
1847 /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
1849 ///An important extra feature of this graph implementation is that
1850 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1852 /// \sa concepts::BpUGraph.
1854 class ListBpUGraph : public ExtendedListBpUGraphBase {
1855 /// \brief ListBpUGraph is \e not copy constructible.
1857 ///ListBpUGraph is \e not copy constructible.
1858 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1859 /// \brief Assignment of ListBpUGraph to another one is \e not
1862 /// Assignment of ListBpUGraph to another one is \e not allowed.
1863 void operator=(const ListBpUGraph &) {}
1865 /// \brief Constructor
1871 typedef ExtendedListBpUGraphBase Parent;
1872 /// \brief Add a new ANode to the graph.
1874 /// \return the new node.
1876 Node addANode() { return Parent::addANode(); }
1878 /// \brief Add a new BNode to the graph.
1880 /// \return the new node.
1882 Node addBNode() { return Parent::addBNode(); }
1884 /// \brief Add a new edge to the graph.
1886 /// Add a new edge to the graph with an ANode and a BNode.
1887 /// \return the new undirected edge.
1888 UEdge addEdge(const Node& s, const Node& t) {
1889 return Parent::addEdge(s, t);
1892 /// \brief Changes the ANode of \c e to \c n
1894 /// Changes the ANode of \c e to \c n
1896 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1897 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1899 void changeANode(UEdge e, Node n) {
1900 Parent::changeANode(e,n);
1903 /// \brief Changes the BNode of \c e to \c n
1905 /// Changes the BNode of \c e to \c n
1907 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1908 /// referencing the changed edge remain
1909 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1910 void changeBNode(UEdge e, Node n) {
1911 Parent::changeBNode(e,n);
1914 /// \brief Changes the source(ANode) of \c e to \c n
1916 /// Changes the source(ANode) of \c e to \c n
1918 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1919 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1921 void changeSource(UEdge e, Node n) {
1922 Parent::changeANode(e,n);
1925 /// \brief Changes the target(BNode) of \c e to \c n
1927 /// Changes the target(BNode) of \c e to \c n
1929 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1930 /// referencing the changed edge remain
1931 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1932 void changeTarget(UEdge e, Node n) {
1933 Parent::changeBNode(e,n);
1936 /// \brief Changes the source of \c e to \c n
1938 /// Changes the source of \c e to \c n. It changes the proper
1939 /// node of the represented undirected edge.
1941 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1942 ///referencing the changed edge remain
1943 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1944 void changeSource(Edge e, Node n) {
1945 if (Parent::direction(e)) {
1946 Parent::changeANode(e,n);
1948 Parent::changeBNode(e,n);
1951 /// \brief Changes the target of \c e to \c n
1953 /// Changes the target of \c e to \c n. It changes the proper
1954 /// node of the represented undirected edge.
1956 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1957 ///referencing the changed edge remain
1958 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1959 void changeTarget(Edge e, Node n) {
1960 if (Parent::direction(e)) {
1961 Parent::changeBNode(e,n);
1963 Parent::changeANode(e,n);
1966 /// \brief Contract two nodes.
1968 /// This function contracts two nodes.
1970 /// Node \p b will be removed but instead of deleting its
1971 /// neighboring edges, they will be joined to \p a. The two nodes
1972 /// should be from the same nodeset, of course.
1974 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1976 void contract(const Node& a, const Node& b) {
1977 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1978 if (Parent::aNode(a)) {
1979 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1980 IncEdgeIt f = e; ++f;
1985 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1986 IncEdgeIt f = e; ++f;
1994 /// \brief Class to make a snapshot of the graph and restore
1997 /// Class to make a snapshot of the graph and to restore it
2000 /// The newly added nodes and undirected edges can be removed
2001 /// using the restore() function.
2003 /// \warning Edge and node deletions cannot be restored. This
2004 /// events invalidate the snapshot.
2008 typedef Parent::NodeNotifier NodeNotifier;
2010 class NodeObserverProxy : public NodeNotifier::ObserverBase {
2013 NodeObserverProxy(Snapshot& _snapshot)
2014 : snapshot(_snapshot) {}
2016 using NodeNotifier::ObserverBase::attach;
2017 using NodeNotifier::ObserverBase::detach;
2018 using NodeNotifier::ObserverBase::attached;
2022 virtual void add(const Node& node) {
2023 snapshot.addNode(node);
2025 virtual void add(const std::vector<Node>& nodes) {
2026 for (int i = nodes.size() - 1; i >= 0; ++i) {
2027 snapshot.addNode(nodes[i]);
2030 virtual void erase(const Node& node) {
2031 snapshot.eraseNode(node);
2033 virtual void erase(const std::vector<Node>& nodes) {
2034 for (int i = 0; i < (int)nodes.size(); ++i) {
2035 snapshot.eraseNode(nodes[i]);
2038 virtual void build() {
2039 NodeNotifier* notifier = getNotifier();
2041 std::vector<Node> nodes;
2042 for (notifier->first(node); node != INVALID; notifier->next(node)) {
2043 nodes.push_back(node);
2045 for (int i = nodes.size() - 1; i >= 0; --i) {
2046 snapshot.addNode(nodes[i]);
2049 virtual void clear() {
2050 NodeNotifier* notifier = getNotifier();
2052 for (notifier->first(node); node != INVALID; notifier->next(node)) {
2053 snapshot.eraseNode(node);
2060 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
2063 UEdgeObserverProxy(Snapshot& _snapshot)
2064 : snapshot(_snapshot) {}
2066 using UEdgeNotifier::ObserverBase::attach;
2067 using UEdgeNotifier::ObserverBase::detach;
2068 using UEdgeNotifier::ObserverBase::attached;
2072 virtual void add(const UEdge& edge) {
2073 snapshot.addUEdge(edge);
2075 virtual void add(const std::vector<UEdge>& edges) {
2076 for (int i = edges.size() - 1; i >= 0; ++i) {
2077 snapshot.addUEdge(edges[i]);
2080 virtual void erase(const UEdge& edge) {
2081 snapshot.eraseUEdge(edge);
2083 virtual void erase(const std::vector<UEdge>& edges) {
2084 for (int i = 0; i < (int)edges.size(); ++i) {
2085 snapshot.eraseUEdge(edges[i]);
2088 virtual void build() {
2089 UEdgeNotifier* notifier = getNotifier();
2091 std::vector<UEdge> edges;
2092 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
2093 edges.push_back(edge);
2095 for (int i = edges.size() - 1; i >= 0; --i) {
2096 snapshot.addUEdge(edges[i]);
2099 virtual void clear() {
2100 UEdgeNotifier* notifier = getNotifier();
2102 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
2103 snapshot.eraseUEdge(edge);
2110 ListBpUGraph *graph;
2112 NodeObserverProxy node_observer_proxy;
2113 UEdgeObserverProxy edge_observer_proxy;
2115 std::list<Node> added_nodes;
2116 std::list<UEdge> added_edges;
2119 void addNode(const Node& node) {
2120 added_nodes.push_front(node);
2122 void eraseNode(const Node& node) {
2123 std::list<Node>::iterator it =
2124 std::find(added_nodes.begin(), added_nodes.end(), node);
2125 if (it == added_nodes.end()) {
2127 edge_observer_proxy.detach();
2128 throw NodeNotifier::ImmediateDetach();
2130 added_nodes.erase(it);
2134 void addUEdge(const UEdge& edge) {
2135 added_edges.push_front(edge);
2137 void eraseUEdge(const UEdge& edge) {
2138 std::list<UEdge>::iterator it =
2139 std::find(added_edges.begin(), added_edges.end(), edge);
2140 if (it == added_edges.end()) {
2142 node_observer_proxy.detach();
2143 throw UEdgeNotifier::ImmediateDetach();
2145 added_edges.erase(it);
2149 void attach(ListBpUGraph &_graph) {
2151 node_observer_proxy.attach(graph->getNotifier(Node()));
2152 edge_observer_proxy.attach(graph->getNotifier(UEdge()));
2156 node_observer_proxy.detach();
2157 edge_observer_proxy.detach();
2160 bool attached() const {
2161 return node_observer_proxy.attached();
2165 added_nodes.clear();
2166 added_edges.clear();
2171 /// \brief Default constructor.
2173 /// Default constructor.
2174 /// To actually make a snapshot you must call save().
2176 : graph(0), node_observer_proxy(*this),
2177 edge_observer_proxy(*this) {}
2179 /// \brief Constructor that immediately makes a snapshot.
2181 /// This constructor immediately makes a snapshot of the graph.
2182 /// \param _graph The graph we make a snapshot of.
2183 Snapshot(ListBpUGraph &_graph)
2184 : node_observer_proxy(*this),
2185 edge_observer_proxy(*this) {
2189 /// \brief Make a snapshot.
2191 /// Make a snapshot of the graph.
2193 /// This function can be called more than once. In case of a repeated
2194 /// call, the previous snapshot gets lost.
2195 /// \param _graph The graph we make the snapshot of.
2196 void save(ListBpUGraph &_graph) {
2204 /// \brief Undo the changes until the last snapshot.
2206 /// Undo the changes until the last snapshot created by save().
2209 for(std::list<UEdge>::iterator it = added_edges.begin();
2210 it != added_edges.end(); ++it) {
2213 for(std::list<Node>::iterator it = added_nodes.begin();
2214 it != added_nodes.end(); ++it) {
2220 /// \brief Gives back true when the snapshot is valid.
2222 /// Gives back true when the snapshot is valid.
2223 bool valid() const {