Revert to long long int since currently I don't know a better solution.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
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 /// Using this it is possible to avoid the superfluous memory
393 /// allocation: if you know that the graph you want to build will
394 /// be very large (e.g. it will contain millions of nodes and/or edges)
395 /// then it is worth reserving space for this amount before starting
396 /// to build the graph.
398 void reserveNode(int n) { nodes.reserve(n); };
400 /// \brief Using this it is possible to avoid the superfluous memory
403 /// Using this it is possible to avoid the superfluous memory
404 /// allocation: if you know that the graph you want to build will
405 /// be very large (e.g. it will contain millions of nodes and/or edges)
406 /// then it is worth reserving space for this amount before starting
407 /// to build the graph.
409 void reserveEdge(int m) { edges.reserve(m); };
411 ///Contract two nodes.
413 ///This function contracts two nodes.
415 ///Node \p b will be removed but instead of deleting
416 ///incident edges, they will be joined to \p a.
417 ///The last parameter \p r controls whether to remove loops. \c true
418 ///means that loops will be removed.
420 ///\note The <tt>EdgeIt</tt>s
421 ///referencing a moved edge remain
422 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
423 ///may be invalidated.
424 ///\warning This functionality cannot be used together with the Snapshot
426 void contract(Node a, Node b, bool r = true)
428 for(OutEdgeIt e(*this,b);e!=INVALID;) {
431 if(r && target(e)==a) erase(e);
432 else changeSource(e,a);
435 for(InEdgeIt e(*this,b);e!=INVALID;) {
438 if(r && source(e)==a) erase(e);
439 else changeTarget(e,a);
447 ///This function splits a node. First a new node is added to the graph,
448 ///then the source of each outgoing edge of \c n is moved to this new node.
449 ///If \c connect is \c true (this is the default value), then a new edge
450 ///from \c n to the newly created node is also added.
451 ///\return The newly created node.
453 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
454 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
457 ///\warning This functionality cannot be used together with the
458 ///Snapshot feature. \todo It could be implemented in a bit
460 Node split(Node n, bool connect = true) {
462 for(OutEdgeIt e(*this,n);e!=INVALID;) {
468 if (connect) addEdge(n,b);
474 ///This function splits an edge. First a new node \c b is added to
475 ///the graph, then the original edge is re-targeted to \c
476 ///b. Finally an edge from \c b to the original target is added.
477 ///\return The newly created node.
478 ///\warning This functionality
479 ///cannot be used together with the Snapshot feature.
482 addEdge(b,target(e));
487 /// \brief Class to make a snapshot of the graph and restore
490 /// Class to make a snapshot of the graph and to restore it
493 /// The newly added nodes and edges can be removed using the
494 /// restore() function.
496 /// \warning Edge and node deletions cannot be restored. This
497 /// events invalidate the snapshot.
501 typedef Parent::NodeNotifier NodeNotifier;
503 class NodeObserverProxy : public NodeNotifier::ObserverBase {
506 NodeObserverProxy(Snapshot& _snapshot)
507 : snapshot(_snapshot) {}
509 using NodeNotifier::ObserverBase::attach;
510 using NodeNotifier::ObserverBase::detach;
511 using NodeNotifier::ObserverBase::attached;
515 virtual void add(const Node& node) {
516 snapshot.addNode(node);
518 virtual void add(const std::vector<Node>& nodes) {
519 for (int i = nodes.size() - 1; i >= 0; ++i) {
520 snapshot.addNode(nodes[i]);
523 virtual void erase(const Node& node) {
524 snapshot.eraseNode(node);
526 virtual void erase(const std::vector<Node>& nodes) {
527 for (int i = 0; i < int(nodes.size()); ++i) {
528 snapshot.eraseNode(nodes[i]);
531 virtual void build() {
533 std::vector<Node> nodes;
534 for (notifier()->first(node); node != INVALID;
535 notifier()->next(node)) {
536 nodes.push_back(node);
538 for (int i = nodes.size() - 1; i >= 0; --i) {
539 snapshot.addNode(nodes[i]);
542 virtual void clear() {
544 for (notifier()->first(node); node != INVALID;
545 notifier()->next(node)) {
546 snapshot.eraseNode(node);
553 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
556 EdgeObserverProxy(Snapshot& _snapshot)
557 : snapshot(_snapshot) {}
559 using EdgeNotifier::ObserverBase::attach;
560 using EdgeNotifier::ObserverBase::detach;
561 using EdgeNotifier::ObserverBase::attached;
565 virtual void add(const Edge& edge) {
566 snapshot.addEdge(edge);
568 virtual void add(const std::vector<Edge>& edges) {
569 for (int i = edges.size() - 1; i >= 0; ++i) {
570 snapshot.addEdge(edges[i]);
573 virtual void erase(const Edge& edge) {
574 snapshot.eraseEdge(edge);
576 virtual void erase(const std::vector<Edge>& edges) {
577 for (int i = 0; i < int(edges.size()); ++i) {
578 snapshot.eraseEdge(edges[i]);
581 virtual void build() {
583 std::vector<Edge> edges;
584 for (notifier()->first(edge); edge != INVALID;
585 notifier()->next(edge)) {
586 edges.push_back(edge);
588 for (int i = edges.size() - 1; i >= 0; --i) {
589 snapshot.addEdge(edges[i]);
592 virtual void clear() {
594 for (notifier()->first(edge); edge != INVALID;
595 notifier()->next(edge)) {
596 snapshot.eraseEdge(edge);
605 NodeObserverProxy node_observer_proxy;
606 EdgeObserverProxy edge_observer_proxy;
608 std::list<Node> added_nodes;
609 std::list<Edge> added_edges;
612 void addNode(const Node& node) {
613 added_nodes.push_front(node);
615 void eraseNode(const Node& node) {
616 std::list<Node>::iterator it =
617 std::find(added_nodes.begin(), added_nodes.end(), node);
618 if (it == added_nodes.end()) {
620 edge_observer_proxy.detach();
621 throw NodeNotifier::ImmediateDetach();
623 added_nodes.erase(it);
627 void addEdge(const Edge& edge) {
628 added_edges.push_front(edge);
630 void eraseEdge(const Edge& edge) {
631 std::list<Edge>::iterator it =
632 std::find(added_edges.begin(), added_edges.end(), edge);
633 if (it == added_edges.end()) {
635 node_observer_proxy.detach();
636 throw EdgeNotifier::ImmediateDetach();
638 added_edges.erase(it);
642 void attach(ListGraph &_graph) {
644 node_observer_proxy.attach(graph->notifier(Node()));
645 edge_observer_proxy.attach(graph->notifier(Edge()));
649 node_observer_proxy.detach();
650 edge_observer_proxy.detach();
653 bool attached() const {
654 return node_observer_proxy.attached();
664 /// \brief Default constructor.
666 /// Default constructor.
667 /// To actually make a snapshot you must call save().
669 : graph(0), node_observer_proxy(*this),
670 edge_observer_proxy(*this) {}
672 /// \brief Constructor that immediately makes a snapshot.
674 /// This constructor immediately makes a snapshot of the graph.
675 /// \param _graph The graph we make a snapshot of.
676 Snapshot(ListGraph &_graph)
677 : node_observer_proxy(*this),
678 edge_observer_proxy(*this) {
682 /// \brief Make a snapshot.
684 /// Make a snapshot of the graph.
686 /// This function can be called more than once. In case of a repeated
687 /// call, the previous snapshot gets lost.
688 /// \param _graph The graph we make the snapshot of.
689 void save(ListGraph &_graph) {
697 /// \brief Undo the changes until the last snapshot.
699 /// Undo the changes until the last snapshot created by save().
702 for(std::list<Edge>::iterator it = added_edges.begin();
703 it != added_edges.end(); ++it) {
706 for(std::list<Node>::iterator it = added_nodes.begin();
707 it != added_nodes.end(); ++it) {
713 /// \brief Gives back true when the snapshot is valid.
715 /// Gives back true when the snapshot is valid.
725 class ListUGraphBase {
736 int prev_out, next_out;
739 std::vector<NodeT> nodes;
745 std::vector<EdgeT> edges;
751 typedef ListUGraphBase Graph;
758 friend class ListUGraphBase;
762 explicit Node(int pid) { id = pid;}
766 Node (Invalid) { id = -1; }
767 bool operator==(const Node& node) const {return id == node.id;}
768 bool operator!=(const Node& node) const {return id != node.id;}
769 bool operator<(const Node& node) const {return id < node.id;}
773 friend class ListUGraphBase;
777 explicit UEdge(int pid) { id = pid;}
781 UEdge (Invalid) { id = -1; }
782 bool operator==(const UEdge& edge) const {return id == edge.id;}
783 bool operator!=(const UEdge& edge) const {return id != edge.id;}
784 bool operator<(const UEdge& edge) const {return id < edge.id;}
788 friend class ListUGraphBase;
792 explicit Edge(int pid) { id = pid;}
795 operator UEdge() const { return uEdgeFromId(id / 2); }
798 Edge (Invalid) { id = -1; }
799 bool operator==(const Edge& edge) const {return id == edge.id;}
800 bool operator!=(const Edge& edge) const {return id != edge.id;}
801 bool operator<(const Edge& edge) const {return id < edge.id;}
807 : nodes(), first_node(-1),
808 first_free_node(-1), edges(), first_free_edge(-1) {}
811 int maxNodeId() const { return nodes.size()-1; }
812 int maxUEdgeId() const { return edges.size() / 2 - 1; }
813 int maxEdgeId() const { return edges.size()-1; }
815 Node source(Edge e) const { return Node(edges[e.id ^ 1].target); }
816 Node target(Edge e) const { return Node(edges[e.id].target); }
818 Node source(UEdge e) const { return Node(edges[2 * e.id].target); }
819 Node target(UEdge e) const { return Node(edges[2 * e.id + 1].target); }
821 static bool direction(Edge e) {
822 return (e.id & 1) == 1;
825 static Edge direct(UEdge e, bool d) {
826 return Edge(e.id * 2 + (d ? 1 : 0));
829 void first(Node& node) const {
830 node.id = first_node;
833 void next(Node& node) const {
834 node.id = nodes[node.id].next;
837 void first(Edge& e) const {
839 while (n != -1 && nodes[n].first_out == -1) {
842 e.id = (n == -1) ? -1 : nodes[n].first_out;
845 void next(Edge& e) const {
846 if (edges[e.id].next_out != -1) {
847 e.id = edges[e.id].next_out;
849 int n = nodes[edges[e.id ^ 1].target].next;
850 while(n != -1 && nodes[n].first_out == -1) {
853 e.id = (n == -1) ? -1 : nodes[n].first_out;
857 void first(UEdge& e) const {
860 e.id = nodes[n].first_out;
861 while ((e.id & 1) != 1) {
862 e.id = edges[e.id].next_out;
873 void next(UEdge& e) const {
874 int n = edges[e.id * 2].target;
875 e.id = edges[(e.id * 2) | 1].next_out;
876 while ((e.id & 1) != 1) {
877 e.id = edges[e.id].next_out;
885 e.id = nodes[n].first_out;
886 while ((e.id & 1) != 1) {
887 e.id = edges[e.id].next_out;
898 void firstOut(Edge &e, const Node& v) const {
899 e.id = nodes[v.id].first_out;
901 void nextOut(Edge &e) const {
902 e.id = edges[e.id].next_out;
905 void firstIn(Edge &e, const Node& v) const {
906 e.id = ((nodes[v.id].first_out) ^ 1);
907 if (e.id == -2) e.id = -1;
909 void nextIn(Edge &e) const {
910 e.id = ((edges[e.id ^ 1].next_out) ^ 1);
911 if (e.id == -2) e.id = -1;
914 void firstInc(UEdge &e, bool& d, const Node& v) const {
915 int de = nodes[v.id].first_out;
924 void nextInc(UEdge &e, bool& d) const {
925 int de = (edges[(e.id * 2) | (d ? 1 : 0)].next_out);
935 static int id(Node v) { return v.id; }
936 static int id(Edge e) { return e.id; }
937 static int id(UEdge e) { return e.id; }
939 static Node nodeFromId(int id) { return Node(id);}
940 static Edge edgeFromId(int id) { return Edge(id);}
941 static UEdge uEdgeFromId(int id) { return UEdge(id);}
946 if(first_free_node==-1) {
948 nodes.push_back(NodeT());
951 first_free_node = nodes[n].next;
954 nodes[n].next = first_node;
955 if (first_node != -1) nodes[first_node].prev = n;
959 nodes[n].first_out = -1;
964 UEdge addEdge(Node u, Node v) {
967 if (first_free_edge == -1) {
969 edges.push_back(EdgeT());
970 edges.push_back(EdgeT());
973 first_free_edge = edges[n].next_out;
976 edges[n].target = u.id;
977 edges[n | 1].target = v.id;
979 edges[n].next_out = nodes[v.id].first_out;
980 if (nodes[v.id].first_out != -1) {
981 edges[nodes[v.id].first_out].prev_out = n;
983 edges[n].prev_out = -1;
984 nodes[v.id].first_out = n;
986 edges[n | 1].next_out = nodes[u.id].first_out;
987 if (nodes[u.id].first_out != -1) {
988 edges[nodes[u.id].first_out].prev_out = (n | 1);
990 edges[n | 1].prev_out = -1;
991 nodes[u.id].first_out = (n | 1);
996 void erase(const Node& node) {
999 if(nodes[n].next != -1) {
1000 nodes[nodes[n].next].prev = nodes[n].prev;
1003 if(nodes[n].prev != -1) {
1004 nodes[nodes[n].prev].next = nodes[n].next;
1006 first_node = nodes[n].next;
1009 nodes[n].next = first_free_node;
1010 first_free_node = n;
1014 void erase(const UEdge& edge) {
1015 int n = edge.id * 2;
1017 if (edges[n].next_out != -1) {
1018 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1021 if (edges[n].prev_out != -1) {
1022 edges[edges[n].prev_out].next_out = edges[n].next_out;
1024 nodes[edges[n | 1].target].first_out = edges[n].next_out;
1027 if (edges[n | 1].next_out != -1) {
1028 edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
1031 if (edges[n | 1].prev_out != -1) {
1032 edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
1034 nodes[edges[n].target].first_out = edges[n | 1].next_out;
1037 edges[n].next_out = first_free_edge;
1038 first_free_edge = n;
1045 first_node = first_free_node = first_free_edge = -1;
1050 void changeTarget(UEdge e, Node n) {
1051 if(edges[2 * e.id].next_out != -1) {
1052 edges[edges[2 * e.id].next_out].prev_out = edges[2 * e.id].prev_out;
1054 if(edges[2 * e.id].prev_out != -1) {
1055 edges[edges[2 * e.id].prev_out].next_out =
1056 edges[2 * e.id].next_out;
1058 nodes[edges[(2 * e.id) | 1].target].first_out =
1059 edges[2 * e.id].next_out;
1062 if (nodes[n.id].first_out != -1) {
1063 edges[nodes[n.id].first_out].prev_out = 2 * e.id;
1065 edges[(2 * e.id) | 1].target = n.id;
1066 edges[2 * e.id].prev_out = -1;
1067 edges[2 * e.id].next_out = nodes[n.id].first_out;
1068 nodes[n.id].first_out = 2 * e.id;
1071 void changeSource(UEdge e, Node n) {
1072 if(edges[(2 * e.id) | 1].next_out != -1) {
1073 edges[edges[(2 * e.id) | 1].next_out].prev_out =
1074 edges[(2 * e.id) | 1].prev_out;
1076 if(edges[(2 * e.id) | 1].prev_out != -1) {
1077 edges[edges[(2 * e.id) | 1].prev_out].next_out =
1078 edges[(2 * e.id) | 1].next_out;
1080 nodes[edges[2 * e.id].target].first_out =
1081 edges[(2 * e.id) | 1].next_out;
1084 if (nodes[n.id].first_out != -1) {
1085 edges[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1087 edges[2 * e.id].target = n.id;
1088 edges[(2 * e.id) | 1].prev_out = -1;
1089 edges[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1090 nodes[n.id].first_out = ((2 * e.id) | 1);
1095 // typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
1096 // ExtendedListUGraphBase;
1098 typedef UGraphExtender<ListUGraphBase> ExtendedListUGraphBase;
1102 /// \addtogroup graphs
1105 ///An undirected list graph class.
1107 ///This is a simple and fast undirected graph implementation.
1109 ///An important extra feature of this graph implementation is that
1110 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1112 ///It conforms to the
1113 ///\ref concepts::UGraph "UGraph concept".
1115 ///\sa concepts::UGraph.
1117 class ListUGraph : public ExtendedListUGraphBase {
1119 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1121 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
1123 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
1124 ///\brief Assignment of ListUGraph to another one is \e not allowed.
1125 ///Use UGraphCopy() instead.
1127 ///Assignment of ListUGraph to another one is \e not allowed.
1128 ///Use UGraphCopy() instead.
1129 void operator=(const ListUGraph &) {}
1137 typedef ExtendedListUGraphBase Parent;
1139 typedef Parent::OutEdgeIt IncEdgeIt;
1141 /// \brief Add a new node to the graph.
1143 /// \return the new node.
1145 Node addNode() { return Parent::addNode(); }
1147 /// \brief Add a new edge to the graph.
1149 /// Add a new edge to the graph with source node \c s
1150 /// and target node \c t.
1151 /// \return the new undirected edge.
1152 UEdge addEdge(const Node& s, const Node& t) {
1153 return Parent::addEdge(s, t);
1155 /// \brief Changes the source of \c e to \c n
1157 /// Changes the source of \c e to \c n
1159 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1160 ///referencing the changed edge remain
1161 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1162 void changeSource(UEdge e, Node n) {
1163 Parent::changeSource(e,n);
1165 /// \brief Changes the target of \c e to \c n
1167 /// Changes the target of \c e to \c n
1169 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
1170 /// valid. However the other iterators may be invalidated.
1171 void changeTarget(UEdge e, Node n) {
1172 Parent::changeTarget(e,n);
1174 /// \brief Changes the source of \c e to \c n
1176 /// Changes the source 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>InEdgeIt</tt>s
1180 ///referencing the changed edge remain
1181 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1182 void changeSource(Edge e, Node n) {
1183 if (Parent::direction(e)) {
1184 Parent::changeSource(e,n);
1186 Parent::changeTarget(e,n);
1189 /// \brief Changes the target of \c e to \c n
1191 /// Changes the target of \c e to \c n. It changes the proper
1192 /// node of the represented undirected edge.
1194 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1195 ///referencing the changed edge remain
1196 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1197 void changeTarget(Edge e, Node n) {
1198 if (Parent::direction(e)) {
1199 Parent::changeTarget(e,n);
1201 Parent::changeSource(e,n);
1204 /// \brief Contract two nodes.
1206 /// This function contracts two nodes.
1208 /// Node \p b will be removed but instead of deleting
1209 /// its neighboring edges, they will be joined to \p a.
1210 /// The last parameter \p r controls whether to remove loops. \c true
1211 /// means that loops will be removed.
1213 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1215 void contract(Node a, Node b, bool r = true) {
1216 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1217 IncEdgeIt f = e; ++f;
1218 if (r && runningNode(e) == a) {
1220 } else if (source(e) == b) {
1231 /// \brief Class to make a snapshot of the graph and restore
1234 /// Class to make a snapshot of the graph and to restore it
1237 /// The newly added nodes and undirected edges can be removed
1238 /// using the restore() function.
1240 /// \warning Edge and node deletions cannot be restored. This
1241 /// events invalidate the snapshot.
1245 typedef Parent::NodeNotifier NodeNotifier;
1247 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1250 NodeObserverProxy(Snapshot& _snapshot)
1251 : snapshot(_snapshot) {}
1253 using NodeNotifier::ObserverBase::attach;
1254 using NodeNotifier::ObserverBase::detach;
1255 using NodeNotifier::ObserverBase::attached;
1259 virtual void add(const Node& node) {
1260 snapshot.addNode(node);
1262 virtual void add(const std::vector<Node>& nodes) {
1263 for (int i = nodes.size() - 1; i >= 0; ++i) {
1264 snapshot.addNode(nodes[i]);
1267 virtual void erase(const Node& node) {
1268 snapshot.eraseNode(node);
1270 virtual void erase(const std::vector<Node>& nodes) {
1271 for (int i = 0; i < int(nodes.size()); ++i) {
1272 snapshot.eraseNode(nodes[i]);
1275 virtual void build() {
1277 std::vector<Node> nodes;
1278 for (notifier()->first(node); node != INVALID;
1279 notifier()->next(node)) {
1280 nodes.push_back(node);
1282 for (int i = nodes.size() - 1; i >= 0; --i) {
1283 snapshot.addNode(nodes[i]);
1286 virtual void clear() {
1288 for (notifier()->first(node); node != INVALID;
1289 notifier()->next(node)) {
1290 snapshot.eraseNode(node);
1297 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
1300 UEdgeObserverProxy(Snapshot& _snapshot)
1301 : snapshot(_snapshot) {}
1303 using UEdgeNotifier::ObserverBase::attach;
1304 using UEdgeNotifier::ObserverBase::detach;
1305 using UEdgeNotifier::ObserverBase::attached;
1309 virtual void add(const UEdge& edge) {
1310 snapshot.addUEdge(edge);
1312 virtual void add(const std::vector<UEdge>& edges) {
1313 for (int i = edges.size() - 1; i >= 0; ++i) {
1314 snapshot.addUEdge(edges[i]);
1317 virtual void erase(const UEdge& edge) {
1318 snapshot.eraseUEdge(edge);
1320 virtual void erase(const std::vector<UEdge>& edges) {
1321 for (int i = 0; i < int(edges.size()); ++i) {
1322 snapshot.eraseUEdge(edges[i]);
1325 virtual void build() {
1327 std::vector<UEdge> edges;
1328 for (notifier()->first(edge); edge != INVALID;
1329 notifier()->next(edge)) {
1330 edges.push_back(edge);
1332 for (int i = edges.size() - 1; i >= 0; --i) {
1333 snapshot.addUEdge(edges[i]);
1336 virtual void clear() {
1338 for (notifier()->first(edge); edge != INVALID;
1339 notifier()->next(edge)) {
1340 snapshot.eraseUEdge(edge);
1349 NodeObserverProxy node_observer_proxy;
1350 UEdgeObserverProxy edge_observer_proxy;
1352 std::list<Node> added_nodes;
1353 std::list<UEdge> added_edges;
1356 void addNode(const Node& node) {
1357 added_nodes.push_front(node);
1359 void eraseNode(const Node& node) {
1360 std::list<Node>::iterator it =
1361 std::find(added_nodes.begin(), added_nodes.end(), node);
1362 if (it == added_nodes.end()) {
1364 edge_observer_proxy.detach();
1365 throw NodeNotifier::ImmediateDetach();
1367 added_nodes.erase(it);
1371 void addUEdge(const UEdge& edge) {
1372 added_edges.push_front(edge);
1374 void eraseUEdge(const UEdge& edge) {
1375 std::list<UEdge>::iterator it =
1376 std::find(added_edges.begin(), added_edges.end(), edge);
1377 if (it == added_edges.end()) {
1379 node_observer_proxy.detach();
1380 throw UEdgeNotifier::ImmediateDetach();
1382 added_edges.erase(it);
1386 void attach(ListUGraph &_graph) {
1388 node_observer_proxy.attach(graph->notifier(Node()));
1389 edge_observer_proxy.attach(graph->notifier(UEdge()));
1393 node_observer_proxy.detach();
1394 edge_observer_proxy.detach();
1397 bool attached() const {
1398 return node_observer_proxy.attached();
1402 added_nodes.clear();
1403 added_edges.clear();
1408 /// \brief Default constructor.
1410 /// Default constructor.
1411 /// To actually make a snapshot you must call save().
1413 : graph(0), node_observer_proxy(*this),
1414 edge_observer_proxy(*this) {}
1416 /// \brief Constructor that immediately makes a snapshot.
1418 /// This constructor immediately makes a snapshot of the graph.
1419 /// \param _graph The graph we make a snapshot of.
1420 Snapshot(ListUGraph &_graph)
1421 : node_observer_proxy(*this),
1422 edge_observer_proxy(*this) {
1426 /// \brief Make a snapshot.
1428 /// Make a snapshot of the graph.
1430 /// This function can be called more than once. In case of a repeated
1431 /// call, the previous snapshot gets lost.
1432 /// \param _graph The graph we make the snapshot of.
1433 void save(ListUGraph &_graph) {
1441 /// \brief Undo the changes until the last snapshot.
1443 /// Undo the changes until the last snapshot created by save().
1446 for(std::list<UEdge>::iterator it = added_edges.begin();
1447 it != added_edges.end(); ++it) {
1450 for(std::list<Node>::iterator it = added_nodes.begin();
1451 it != added_nodes.end(); ++it) {
1457 /// \brief Gives back true when the snapshot is valid.
1459 /// Gives back true when the snapshot is valid.
1460 bool valid() const {
1467 class ListBpUGraphBase {
1470 class NodeSetError : public LogicError {
1472 virtual const char* what() const throw() {
1473 return "lemon::ListBpUGraph::NodeSetError";
1480 int first_edge, prev, next;
1484 int aNode, prev_out, next_out;
1485 int bNode, prev_in, next_in;
1488 std::vector<NodeT> aNodes;
1489 std::vector<NodeT> bNodes;
1491 std::vector<UEdgeT> edges;
1494 int first_free_anode;
1497 int first_free_bnode;
1499 int first_free_edge;
1504 friend class ListBpUGraphBase;
1508 explicit Node(int _id) : id(_id) {}
1511 Node(Invalid) { id = -1; }
1512 bool operator==(const Node i) const {return id==i.id;}
1513 bool operator!=(const Node i) const {return id!=i.id;}
1514 bool operator<(const Node i) const {return id<i.id;}
1518 friend class ListBpUGraphBase;
1522 explicit UEdge(int _id) { id = _id;}
1525 UEdge (Invalid) { id = -1; }
1526 bool operator==(const UEdge i) const {return id==i.id;}
1527 bool operator!=(const UEdge i) const {return id!=i.id;}
1528 bool operator<(const UEdge i) const {return id<i.id;}
1532 : first_anode(-1), first_free_anode(-1),
1533 first_bnode(-1), first_free_bnode(-1),
1534 first_free_edge(-1) {}
1536 void firstANode(Node& node) const {
1537 node.id = first_anode != -1 ? (first_anode << 1) : -1;
1539 void nextANode(Node& node) const {
1540 node.id = aNodes[node.id >> 1].next;
1543 void firstBNode(Node& node) const {
1544 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
1546 void nextBNode(Node& node) const {
1547 node.id = bNodes[node.id >> 1].next;
1550 void first(Node& node) const {
1551 if (first_anode != -1) {
1552 node.id = (first_anode << 1);
1553 } else if (first_bnode != -1) {
1554 node.id = (first_bnode << 1) + 1;
1559 void next(Node& node) const {
1561 node.id = aNodes[node.id >> 1].next;
1562 if (node.id == -1) {
1563 if (first_bnode != -1) {
1564 node.id = (first_bnode << 1) + 1;
1568 node.id = bNodes[node.id >> 1].next;
1572 void first(UEdge& edge) const {
1573 int aid = first_anode;
1574 while (aid != -1 && aNodes[aid].first_edge == -1) {
1575 aid = aNodes[aid].next != -1 ?
1576 aNodes[aid].next >> 1 : -1;
1579 edge.id = aNodes[aid].first_edge;
1584 void next(UEdge& edge) const {
1585 int aid = edges[edge.id].aNode >> 1;
1586 edge.id = edges[edge.id].next_out;
1587 if (edge.id == -1) {
1588 aid = aNodes[aid].next != -1 ?
1589 aNodes[aid].next >> 1 : -1;
1590 while (aid != -1 && aNodes[aid].first_edge == -1) {
1591 aid = aNodes[aid].next != -1 ?
1592 aNodes[aid].next >> 1 : -1;
1595 edge.id = aNodes[aid].first_edge;
1602 void firstFromANode(UEdge& edge, const Node& node) const {
1603 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1604 edge.id = aNodes[node.id >> 1].first_edge;
1606 void nextFromANode(UEdge& edge) const {
1607 edge.id = edges[edge.id].next_out;
1610 void firstFromBNode(UEdge& edge, const Node& node) const {
1611 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1612 edge.id = bNodes[node.id >> 1].first_edge;
1614 void nextFromBNode(UEdge& edge) const {
1615 edge.id = edges[edge.id].next_in;
1618 static int id(const Node& node) {
1621 static Node nodeFromId(int id) {
1624 int maxNodeId() const {
1625 return aNodes.size() > bNodes.size() ?
1626 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1629 static int id(const UEdge& edge) {
1632 static UEdge uEdgeFromId(int id) {
1635 int maxUEdgeId() const {
1636 return edges.size();
1639 static int aNodeId(const Node& node) {
1640 return node.id >> 1;
1642 static Node nodeFromANodeId(int id) {
1643 return Node(id << 1);
1645 int maxANodeId() const {
1646 return aNodes.size();
1649 static int bNodeId(const Node& node) {
1650 return node.id >> 1;
1652 static Node nodeFromBNodeId(int id) {
1653 return Node((id << 1) + 1);
1655 int maxBNodeId() const {
1656 return bNodes.size();
1659 Node aNode(const UEdge& edge) const {
1660 return Node(edges[edge.id].aNode);
1662 Node bNode(const UEdge& edge) const {
1663 return Node(edges[edge.id].bNode);
1666 static bool aNode(const Node& node) {
1667 return (node.id & 1) == 0;
1670 static bool bNode(const Node& node) {
1671 return (node.id & 1) == 1;
1676 if (first_free_anode == -1) {
1677 aid = aNodes.size();
1678 aNodes.push_back(NodeT());
1680 aid = first_free_anode;
1681 first_free_anode = aNodes[first_free_anode].next;
1683 if (first_anode != -1) {
1684 aNodes[aid].next = first_anode << 1;
1685 aNodes[first_anode].prev = aid << 1;
1687 aNodes[aid].next = -1;
1689 aNodes[aid].prev = -1;
1691 aNodes[aid].first_edge = -1;
1692 return Node(aid << 1);
1697 if (first_free_bnode == -1) {
1698 bid = bNodes.size();
1699 bNodes.push_back(NodeT());
1701 bid = first_free_bnode;
1702 first_free_bnode = bNodes[first_free_bnode].next;
1704 if (first_bnode != -1) {
1705 bNodes[bid].next = (first_bnode << 1) + 1;
1706 bNodes[first_bnode].prev = (bid << 1) + 1;
1708 bNodes[bid].next = -1;
1710 bNodes[bid].prev = -1;
1712 bNodes[bid].first_edge = -1;
1713 return Node((bid << 1) + 1);
1716 UEdge addEdge(const Node& source, const Node& target) {
1717 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1719 if (first_free_edge != -1) {
1720 edgeId = first_free_edge;
1721 first_free_edge = edges[edgeId].next_out;
1723 edgeId = edges.size();
1724 edges.push_back(UEdgeT());
1726 if ((source.id & 1) == 0) {
1727 edges[edgeId].aNode = source.id;
1728 edges[edgeId].bNode = target.id;
1730 edges[edgeId].aNode = target.id;
1731 edges[edgeId].bNode = source.id;
1733 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1734 edges[edgeId].prev_out = -1;
1735 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1736 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1738 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1739 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1740 edges[edgeId].prev_in = -1;
1741 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1742 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1744 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1745 return UEdge(edgeId);
1748 void erase(const Node& node) {
1750 int aid = node.id >> 1;
1751 if (aNodes[aid].prev != -1) {
1752 aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next;
1755 aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1;
1757 if (aNodes[aid].next != -1) {
1758 aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev;
1760 aNodes[aid].next = first_free_anode;
1761 first_free_anode = aid;
1763 int bid = node.id >> 1;
1764 if (bNodes[bid].prev != -1) {
1765 bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next;
1768 bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1;
1770 if (bNodes[bid].next != -1) {
1771 bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev;
1773 bNodes[bid].next = first_free_bnode;
1774 first_free_bnode = bid;
1778 void erase(const UEdge& edge) {
1780 if (edges[edge.id].prev_out != -1) {
1781 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1783 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1785 if (edges[edge.id].next_out != -1) {
1786 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1789 if (edges[edge.id].prev_in != -1) {
1790 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1792 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1794 if (edges[edge.id].next_in != -1) {
1795 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1798 edges[edge.id].next_out = first_free_edge;
1799 first_free_edge = edge.id;
1807 first_free_anode = -1;
1809 first_free_bnode = -1;
1810 first_free_edge = -1;
1813 void changeANode(const UEdge& edge, const Node& node) {
1814 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1815 if (edges[edge.id].prev_out != -1) {
1816 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1818 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1820 if (edges[edge.id].next_out != -1) {
1821 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1823 if (aNodes[node.id >> 1].first_edge != -1) {
1824 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1826 edges[edge.id].prev_out = -1;
1827 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1828 aNodes[node.id >> 1].first_edge = edge.id;
1829 edges[edge.id].aNode = node.id;
1832 void changeBNode(const UEdge& edge, const Node& node) {
1833 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1834 if (edges[edge.id].prev_in != -1) {
1835 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1837 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1839 if (edges[edge.id].next_in != -1) {
1840 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1842 if (bNodes[node.id >> 1].first_edge != -1) {
1843 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1845 edges[edge.id].prev_in = -1;
1846 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1847 bNodes[node.id >> 1].first_edge = edge.id;
1848 edges[edge.id].bNode = node.id;
1854 typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> >
1855 ExtendedListBpUGraphBase;
1859 /// \brief A smart bipartite undirected graph class.
1861 /// This is a bipartite undirected graph implementation.
1862 /// It is conforms to the \ref concepts::BpUGraph "BpUGraph concept".
1864 ///An important extra feature of this graph implementation is that
1865 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1867 /// \sa concepts::BpUGraph.
1869 class ListBpUGraph : public ExtendedListBpUGraphBase {
1870 /// \brief ListBpUGraph is \e not copy constructible.
1872 ///ListBpUGraph is \e not copy constructible.
1873 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1874 /// \brief Assignment of ListBpUGraph to another one is \e not
1877 /// Assignment of ListBpUGraph to another one is \e not allowed.
1878 void operator=(const ListBpUGraph &) {}
1880 /// \brief Constructor
1886 typedef ExtendedListBpUGraphBase Parent;
1887 /// \brief Add a new ANode to the graph.
1889 /// \return the new node.
1891 Node addANode() { return Parent::addANode(); }
1893 /// \brief Add a new BNode to the graph.
1895 /// \return the new node.
1897 Node addBNode() { return Parent::addBNode(); }
1899 /// \brief Add a new edge to the graph.
1901 /// Add a new edge to the graph with an ANode and a BNode.
1902 /// \return the new undirected edge.
1903 UEdge addEdge(const Node& s, const Node& t) {
1904 return Parent::addEdge(s, t);
1907 /// \brief Changes the ANode of \c e to \c n
1909 /// Changes the ANode of \c e to \c n
1911 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1912 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1914 void changeANode(UEdge e, Node n) {
1915 Parent::changeANode(e,n);
1918 /// \brief Changes the BNode of \c e to \c n
1920 /// Changes the BNode of \c e to \c n
1922 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1923 /// referencing the changed edge remain
1924 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1925 void changeBNode(UEdge e, Node n) {
1926 Parent::changeBNode(e,n);
1929 /// \brief Changes the source(ANode) of \c e to \c n
1931 /// Changes the source(ANode) of \c e to \c n
1933 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1934 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1936 void changeSource(UEdge e, Node n) {
1937 Parent::changeANode(e,n);
1940 /// \brief Changes the target(BNode) of \c e to \c n
1942 /// Changes the target(BNode) of \c e to \c n
1944 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1945 /// referencing the changed edge remain
1946 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1947 void changeTarget(UEdge e, Node n) {
1948 Parent::changeBNode(e,n);
1951 /// \brief Changes the source of \c e to \c n
1953 /// Changes the source 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>InEdgeIt</tt>s
1957 ///referencing the changed edge remain
1958 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1959 void changeSource(Edge e, Node n) {
1960 if (Parent::direction(e)) {
1961 Parent::changeANode(e,n);
1963 Parent::changeBNode(e,n);
1966 /// \brief Changes the target of \c e to \c n
1968 /// Changes the target of \c e to \c n. It changes the proper
1969 /// node of the represented undirected edge.
1971 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1972 ///referencing the changed edge remain
1973 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1974 void changeTarget(Edge e, Node n) {
1975 if (Parent::direction(e)) {
1976 Parent::changeBNode(e,n);
1978 Parent::changeANode(e,n);
1981 /// \brief Contract two nodes.
1983 /// This function contracts two nodes.
1985 /// Node \p b will be removed but instead of deleting its
1986 /// neighboring edges, they will be joined to \p a. The two nodes
1987 /// should be from the same nodeset, of course.
1989 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1991 void contract(const Node& a, const Node& b) {
1992 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1993 if (Parent::aNode(a)) {
1994 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1995 IncEdgeIt f = e; ++f;
2000 for (IncEdgeIt e(*this, b); e!=INVALID;) {
2001 IncEdgeIt f = e; ++f;
2009 /// \brief Class to make a snapshot of the graph and restore
2012 /// Class to make a snapshot of the graph and to restore it
2015 /// The newly added nodes and undirected edges can be removed
2016 /// using the restore() function.
2018 /// \warning Edge and node deletions cannot be restored. This
2019 /// events invalidate the snapshot.
2023 typedef Parent::NodeNotifier NodeNotifier;
2025 class NodeObserverProxy : public NodeNotifier::ObserverBase {
2028 NodeObserverProxy(Snapshot& _snapshot)
2029 : snapshot(_snapshot) {}
2031 using NodeNotifier::ObserverBase::attach;
2032 using NodeNotifier::ObserverBase::detach;
2033 using NodeNotifier::ObserverBase::attached;
2037 virtual void add(const Node& node) {
2038 snapshot.addNode(node);
2040 virtual void add(const std::vector<Node>& nodes) {
2041 for (int i = nodes.size() - 1; i >= 0; ++i) {
2042 snapshot.addNode(nodes[i]);
2045 virtual void erase(const Node& node) {
2046 snapshot.eraseNode(node);
2048 virtual void erase(const std::vector<Node>& nodes) {
2049 for (int i = 0; i < int(nodes.size()); ++i) {
2050 snapshot.eraseNode(nodes[i]);
2053 virtual void build() {
2055 std::vector<Node> nodes;
2056 for (notifier()->first(node); node != INVALID;
2057 notifier()->next(node)) {
2058 nodes.push_back(node);
2060 for (int i = nodes.size() - 1; i >= 0; --i) {
2061 snapshot.addNode(nodes[i]);
2064 virtual void clear() {
2066 for (notifier()->first(node); node != INVALID;
2067 notifier()->next(node)) {
2068 snapshot.eraseNode(node);
2075 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
2078 UEdgeObserverProxy(Snapshot& _snapshot)
2079 : snapshot(_snapshot) {}
2081 using UEdgeNotifier::ObserverBase::attach;
2082 using UEdgeNotifier::ObserverBase::detach;
2083 using UEdgeNotifier::ObserverBase::attached;
2087 virtual void add(const UEdge& edge) {
2088 snapshot.addUEdge(edge);
2090 virtual void add(const std::vector<UEdge>& edges) {
2091 for (int i = edges.size() - 1; i >= 0; ++i) {
2092 snapshot.addUEdge(edges[i]);
2095 virtual void erase(const UEdge& edge) {
2096 snapshot.eraseUEdge(edge);
2098 virtual void erase(const std::vector<UEdge>& edges) {
2099 for (int i = 0; i < int(edges.size()); ++i) {
2100 snapshot.eraseUEdge(edges[i]);
2103 virtual void build() {
2105 std::vector<UEdge> edges;
2106 for (notifier()->first(edge); edge != INVALID;
2107 notifier()->next(edge)) {
2108 edges.push_back(edge);
2110 for (int i = edges.size() - 1; i >= 0; --i) {
2111 snapshot.addUEdge(edges[i]);
2114 virtual void clear() {
2116 for (notifier()->first(edge); edge != INVALID;
2117 notifier()->next(edge)) {
2118 snapshot.eraseUEdge(edge);
2125 ListBpUGraph *graph;
2127 NodeObserverProxy node_observer_proxy;
2128 UEdgeObserverProxy edge_observer_proxy;
2130 std::list<Node> added_nodes;
2131 std::list<UEdge> added_edges;
2134 void addNode(const Node& node) {
2135 added_nodes.push_front(node);
2137 void eraseNode(const Node& node) {
2138 std::list<Node>::iterator it =
2139 std::find(added_nodes.begin(), added_nodes.end(), node);
2140 if (it == added_nodes.end()) {
2142 edge_observer_proxy.detach();
2143 throw NodeNotifier::ImmediateDetach();
2145 added_nodes.erase(it);
2149 void addUEdge(const UEdge& edge) {
2150 added_edges.push_front(edge);
2152 void eraseUEdge(const UEdge& edge) {
2153 std::list<UEdge>::iterator it =
2154 std::find(added_edges.begin(), added_edges.end(), edge);
2155 if (it == added_edges.end()) {
2157 node_observer_proxy.detach();
2158 throw UEdgeNotifier::ImmediateDetach();
2160 added_edges.erase(it);
2164 void attach(ListBpUGraph &_graph) {
2166 node_observer_proxy.attach(graph->notifier(Node()));
2167 edge_observer_proxy.attach(graph->notifier(UEdge()));
2171 node_observer_proxy.detach();
2172 edge_observer_proxy.detach();
2175 bool attached() const {
2176 return node_observer_proxy.attached();
2180 added_nodes.clear();
2181 added_edges.clear();
2186 /// \brief Default constructor.
2188 /// Default constructor.
2189 /// To actually make a snapshot you must call save().
2191 : graph(0), node_observer_proxy(*this),
2192 edge_observer_proxy(*this) {}
2194 /// \brief Constructor that immediately makes a snapshot.
2196 /// This constructor immediately makes a snapshot of the graph.
2197 /// \param _graph The graph we make a snapshot of.
2198 Snapshot(ListBpUGraph &_graph)
2199 : node_observer_proxy(*this),
2200 edge_observer_proxy(*this) {
2204 /// \brief Make a snapshot.
2206 /// Make a snapshot of the graph.
2208 /// This function can be called more than once. In case of a repeated
2209 /// call, the previous snapshot gets lost.
2210 /// \param _graph The graph we make the snapshot of.
2211 void save(ListBpUGraph &_graph) {
2219 /// \brief Undo the changes until the last snapshot.
2221 /// Undo the changes until the last snapshot created by save().
2224 for(std::list<UEdge>::iterator it = added_edges.begin();
2225 it != added_edges.end(); ++it) {
2228 for(std::list<Node>::iterator it = added_nodes.begin();
2229 it != added_nodes.end(); ++it) {
2235 /// \brief Gives back true when the snapshot is valid.
2237 /// Gives back true when the snapshot is valid.
2238 bool valid() const {