1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
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 ListDigraph, ListGraph classes.
26 #include <lemon/core.h>
27 #include <lemon/error.h>
28 #include <lemon/bits/graph_extender.h>
35 class ListDigraphBase {
39 int first_in, first_out;
45 int prev_in, prev_out;
46 int next_in, next_out;
49 std::vector<NodeT> nodes;
55 std::vector<ArcT> arcs;
61 typedef ListDigraphBase Digraph;
64 friend class ListDigraphBase;
68 explicit Node(int pid) { id = pid;}
72 Node (Invalid) { id = -1; }
73 bool operator==(const Node& node) const {return id == node.id;}
74 bool operator!=(const Node& node) const {return id != node.id;}
75 bool operator<(const Node& node) const {return id < node.id;}
79 friend class ListDigraphBase;
83 explicit Arc(int pid) { id = pid;}
87 Arc (Invalid) { id = -1; }
88 bool operator==(const Arc& arc) const {return id == arc.id;}
89 bool operator!=(const Arc& arc) const {return id != arc.id;}
90 bool operator<(const Arc& arc) const {return id < arc.id;}
96 : nodes(), first_node(-1),
97 first_free_node(-1), arcs(), first_free_arc(-1) {}
100 int maxNodeId() const { return nodes.size()-1; }
101 int maxArcId() const { return arcs.size()-1; }
103 Node source(Arc e) const { return Node(arcs[e.id].source); }
104 Node target(Arc e) const { return Node(arcs[e.id].target); }
107 void first(Node& node) const {
108 node.id = first_node;
111 void next(Node& node) const {
112 node.id = nodes[node.id].next;
116 void first(Arc& arc) const {
119 n!=-1 && nodes[n].first_in == -1;
120 n = nodes[n].next) {}
121 arc.id = (n == -1) ? -1 : nodes[n].first_in;
124 void next(Arc& arc) const {
125 if (arcs[arc.id].next_in != -1) {
126 arc.id = arcs[arc.id].next_in;
129 for(n = nodes[arcs[arc.id].target].next;
130 n!=-1 && nodes[n].first_in == -1;
131 n = nodes[n].next) {}
132 arc.id = (n == -1) ? -1 : nodes[n].first_in;
136 void firstOut(Arc &e, const Node& v) const {
137 e.id = nodes[v.id].first_out;
139 void nextOut(Arc &e) const {
140 e.id=arcs[e.id].next_out;
143 void firstIn(Arc &e, const Node& v) const {
144 e.id = nodes[v.id].first_in;
146 void nextIn(Arc &e) const {
147 e.id=arcs[e.id].next_in;
151 static int id(Node v) { return v.id; }
152 static int id(Arc e) { return e.id; }
154 static Node nodeFromId(int id) { return Node(id);}
155 static Arc arcFromId(int id) { return Arc(id);}
157 bool valid(Node n) const {
158 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
159 nodes[n.id].prev != -2;
162 bool valid(Arc a) const {
163 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
164 arcs[a.id].prev_in != -2;
170 if(first_free_node==-1) {
172 nodes.push_back(NodeT());
175 first_free_node = nodes[n].next;
178 nodes[n].next = first_node;
179 if(first_node != -1) nodes[first_node].prev = n;
183 nodes[n].first_in = nodes[n].first_out = -1;
188 Arc addArc(Node u, Node v) {
191 if (first_free_arc == -1) {
193 arcs.push_back(ArcT());
196 first_free_arc = arcs[n].next_in;
199 arcs[n].source = u.id;
200 arcs[n].target = v.id;
202 arcs[n].next_out = nodes[u.id].first_out;
203 if(nodes[u.id].first_out != -1) {
204 arcs[nodes[u.id].first_out].prev_out = n;
207 arcs[n].next_in = nodes[v.id].first_in;
208 if(nodes[v.id].first_in != -1) {
209 arcs[nodes[v.id].first_in].prev_in = n;
212 arcs[n].prev_in = arcs[n].prev_out = -1;
214 nodes[u.id].first_out = nodes[v.id].first_in = n;
219 void erase(const Node& node) {
222 if(nodes[n].next != -1) {
223 nodes[nodes[n].next].prev = nodes[n].prev;
226 if(nodes[n].prev != -1) {
227 nodes[nodes[n].prev].next = nodes[n].next;
229 first_node = nodes[n].next;
232 nodes[n].next = first_free_node;
238 void erase(const Arc& arc) {
241 if(arcs[n].next_in!=-1) {
242 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
245 if(arcs[n].prev_in!=-1) {
246 arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
248 nodes[arcs[n].target].first_in = arcs[n].next_in;
252 if(arcs[n].next_out!=-1) {
253 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
256 if(arcs[n].prev_out!=-1) {
257 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
259 nodes[arcs[n].source].first_out = arcs[n].next_out;
262 arcs[n].next_in = first_free_arc;
264 arcs[n].prev_in = -2;
270 first_node = first_free_node = first_free_arc = -1;
274 void changeTarget(Arc e, Node n)
276 if(arcs[e.id].next_in != -1)
277 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
278 if(arcs[e.id].prev_in != -1)
279 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
280 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
281 if (nodes[n.id].first_in != -1) {
282 arcs[nodes[n.id].first_in].prev_in = e.id;
284 arcs[e.id].target = n.id;
285 arcs[e.id].prev_in = -1;
286 arcs[e.id].next_in = nodes[n.id].first_in;
287 nodes[n.id].first_in = e.id;
289 void changeSource(Arc e, Node n)
291 if(arcs[e.id].next_out != -1)
292 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
293 if(arcs[e.id].prev_out != -1)
294 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
295 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
296 if (nodes[n.id].first_out != -1) {
297 arcs[nodes[n.id].first_out].prev_out = e.id;
299 arcs[e.id].source = n.id;
300 arcs[e.id].prev_out = -1;
301 arcs[e.id].next_out = nodes[n.id].first_out;
302 nodes[n.id].first_out = e.id;
307 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
309 /// \addtogroup graphs
312 ///A general directed graph structure.
314 ///\ref ListDigraph is a simple and fast <em>directed graph</em>
315 ///implementation based on static linked lists that are stored in
316 ///\c std::vector structures.
318 ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
319 ///also provides several useful additional functionalities.
320 ///Most of the member functions and nested classes are documented
321 ///only in the concept class.
323 ///An important extra feature of this digraph implementation is that
324 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
326 ///\sa concepts::Digraph
328 class ListDigraph : public ExtendedListDigraphBase {
330 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
332 ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
334 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
335 ///\brief Assignment of ListDigraph to another one is \e not allowed.
336 ///Use copyDigraph() instead.
338 ///Assignment of ListDigraph to another one is \e not allowed.
339 ///Use copyDigraph() instead.
340 void operator=(const ListDigraph &) {}
343 typedef ExtendedListDigraphBase Parent;
351 ///Add a new node to the digraph.
353 ///Add a new node to the digraph.
354 ///\return the new node.
355 Node addNode() { return Parent::addNode(); }
357 ///Add a new arc to the digraph.
359 ///Add a new arc to the digraph with source node \c s
360 ///and target node \c t.
361 ///\return the new arc.
362 Arc addArc(const Node& s, const Node& t) {
363 return Parent::addArc(s, t);
366 ///\brief Erase a node from the digraph.
368 ///Erase a node from the digraph.
370 void erase(const Node& n) { Parent::erase(n); }
372 ///\brief Erase an arc from the digraph.
374 ///Erase an arc from the digraph.
376 void erase(const Arc& a) { Parent::erase(a); }
378 /// Node validity check
380 /// This function gives back true if the given node is valid,
381 /// ie. it is a real node of the graph.
383 /// \warning A Node pointing to a removed item
384 /// could become valid again later if new nodes are
385 /// added to the graph.
386 bool valid(Node n) const { return Parent::valid(n); }
388 /// Arc validity check
390 /// This function gives back true if the given arc is valid,
391 /// ie. it is a real arc of the graph.
393 /// \warning An Arc pointing to a removed item
394 /// could become valid again later if new nodes are
395 /// added to the graph.
396 bool valid(Arc a) const { return Parent::valid(a); }
398 /// Change the target of \c e to \c n
400 /// Change the target of \c e to \c n
402 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
403 ///the changed arc remain valid. However <tt>InArcIt</tt>s are
406 ///\warning This functionality cannot be used together with the Snapshot
408 void changeTarget(Arc e, Node n) {
409 Parent::changeTarget(e,n);
411 /// Change the source of \c e to \c n
413 /// Change the source of \c e to \c n
415 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
416 ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
419 ///\warning This functionality cannot be used together with the Snapshot
421 void changeSource(Arc e, Node n) {
422 Parent::changeSource(e,n);
425 /// Invert the direction of an arc.
427 ///\note The <tt>ArcIt</tt>s referencing the changed arc remain
428 ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
431 ///\warning This functionality cannot be used together with the Snapshot
433 void reverseArc(Arc e) {
435 changeTarget(e,source(e));
439 /// Reserve memory for nodes.
441 /// Using this function it is possible to avoid the superfluous memory
442 /// allocation: if you know that the digraph you want to build will
443 /// be very large (e.g. it will contain millions of nodes and/or arcs)
444 /// then it is worth reserving space for this amount before starting
445 /// to build the digraph.
447 void reserveNode(int n) { nodes.reserve(n); };
449 /// Reserve memory for arcs.
451 /// Using this function it is possible to avoid the superfluous memory
452 /// allocation: if you know that the digraph you want to build will
453 /// be very large (e.g. it will contain millions of nodes and/or arcs)
454 /// then it is worth reserving space for this amount before starting
455 /// to build the digraph.
457 void reserveArc(int m) { arcs.reserve(m); };
459 ///Contract two nodes.
461 ///This function contracts two nodes.
462 ///Node \p b will be removed but instead of deleting
463 ///incident arcs, they will be joined to \p a.
464 ///The last parameter \p r controls whether to remove loops. \c true
465 ///means that loops will be removed.
467 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
468 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
469 ///may be invalidated.
471 ///\warning This functionality cannot be used together with the Snapshot
473 void contract(Node a, Node b, bool r = true)
475 for(OutArcIt e(*this,b);e!=INVALID;) {
478 if(r && target(e)==a) erase(e);
479 else changeSource(e,a);
482 for(InArcIt e(*this,b);e!=INVALID;) {
485 if(r && source(e)==a) erase(e);
486 else changeTarget(e,a);
494 ///This function splits a node. First a new node is added to the digraph,
495 ///then the source of each outgoing arc of \c n is moved to this new node.
496 ///If \c connect is \c true (this is the default value), then a new arc
497 ///from \c n to the newly created node is also added.
498 ///\return The newly created node.
500 ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
501 ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may
504 ///\warning This functionality cannot be used together with the
507 ///\todo It could be implemented in a bit faster way.
508 Node split(Node n, bool connect = true) {
510 for(OutArcIt e(*this,n);e!=INVALID;) {
516 if (connect) addArc(n,b);
522 ///This function splits an arc. First a new node \c b is added to
523 ///the digraph, then the original arc is re-targeted to \c
524 ///b. Finally an arc from \c b to the original target is added.
526 ///\return The newly created node.
528 ///\warning This functionality cannot be used together with the
537 /// \brief Class to make a snapshot of the digraph and restore
540 /// Class to make a snapshot of the digraph and restore it later.
542 /// The newly added nodes and arcs can be removed using the
543 /// restore() function.
545 /// \warning Arc and node deletions and other modifications (e.g.
546 /// contracting, splitting, reversing arcs or nodes) cannot be
547 /// restored. These events invalidate the snapshot.
551 typedef Parent::NodeNotifier NodeNotifier;
553 class NodeObserverProxy : public NodeNotifier::ObserverBase {
556 NodeObserverProxy(Snapshot& _snapshot)
557 : snapshot(_snapshot) {}
559 using NodeNotifier::ObserverBase::attach;
560 using NodeNotifier::ObserverBase::detach;
561 using NodeNotifier::ObserverBase::attached;
565 virtual void add(const Node& node) {
566 snapshot.addNode(node);
568 virtual void add(const std::vector<Node>& nodes) {
569 for (int i = nodes.size() - 1; i >= 0; ++i) {
570 snapshot.addNode(nodes[i]);
573 virtual void erase(const Node& node) {
574 snapshot.eraseNode(node);
576 virtual void erase(const std::vector<Node>& nodes) {
577 for (int i = 0; i < int(nodes.size()); ++i) {
578 snapshot.eraseNode(nodes[i]);
581 virtual void build() {
583 std::vector<Node> nodes;
584 for (notifier()->first(node); node != INVALID;
585 notifier()->next(node)) {
586 nodes.push_back(node);
588 for (int i = nodes.size() - 1; i >= 0; --i) {
589 snapshot.addNode(nodes[i]);
592 virtual void clear() {
594 for (notifier()->first(node); node != INVALID;
595 notifier()->next(node)) {
596 snapshot.eraseNode(node);
603 class ArcObserverProxy : public ArcNotifier::ObserverBase {
606 ArcObserverProxy(Snapshot& _snapshot)
607 : snapshot(_snapshot) {}
609 using ArcNotifier::ObserverBase::attach;
610 using ArcNotifier::ObserverBase::detach;
611 using ArcNotifier::ObserverBase::attached;
615 virtual void add(const Arc& arc) {
616 snapshot.addArc(arc);
618 virtual void add(const std::vector<Arc>& arcs) {
619 for (int i = arcs.size() - 1; i >= 0; ++i) {
620 snapshot.addArc(arcs[i]);
623 virtual void erase(const Arc& arc) {
624 snapshot.eraseArc(arc);
626 virtual void erase(const std::vector<Arc>& arcs) {
627 for (int i = 0; i < int(arcs.size()); ++i) {
628 snapshot.eraseArc(arcs[i]);
631 virtual void build() {
633 std::vector<Arc> arcs;
634 for (notifier()->first(arc); arc != INVALID;
635 notifier()->next(arc)) {
638 for (int i = arcs.size() - 1; i >= 0; --i) {
639 snapshot.addArc(arcs[i]);
642 virtual void clear() {
644 for (notifier()->first(arc); arc != INVALID;
645 notifier()->next(arc)) {
646 snapshot.eraseArc(arc);
653 ListDigraph *digraph;
655 NodeObserverProxy node_observer_proxy;
656 ArcObserverProxy arc_observer_proxy;
658 std::list<Node> added_nodes;
659 std::list<Arc> added_arcs;
662 void addNode(const Node& node) {
663 added_nodes.push_front(node);
665 void eraseNode(const Node& node) {
666 std::list<Node>::iterator it =
667 std::find(added_nodes.begin(), added_nodes.end(), node);
668 if (it == added_nodes.end()) {
670 arc_observer_proxy.detach();
671 throw NodeNotifier::ImmediateDetach();
673 added_nodes.erase(it);
677 void addArc(const Arc& arc) {
678 added_arcs.push_front(arc);
680 void eraseArc(const Arc& arc) {
681 std::list<Arc>::iterator it =
682 std::find(added_arcs.begin(), added_arcs.end(), arc);
683 if (it == added_arcs.end()) {
685 node_observer_proxy.detach();
686 throw ArcNotifier::ImmediateDetach();
688 added_arcs.erase(it);
692 void attach(ListDigraph &_digraph) {
694 node_observer_proxy.attach(digraph->notifier(Node()));
695 arc_observer_proxy.attach(digraph->notifier(Arc()));
699 node_observer_proxy.detach();
700 arc_observer_proxy.detach();
703 bool attached() const {
704 return node_observer_proxy.attached();
714 /// \brief Default constructor.
716 /// Default constructor.
717 /// To actually make a snapshot you must call save().
719 : digraph(0), node_observer_proxy(*this),
720 arc_observer_proxy(*this) {}
722 /// \brief Constructor that immediately makes a snapshot.
724 /// This constructor immediately makes a snapshot of the digraph.
725 /// \param _digraph The digraph we make a snapshot of.
726 Snapshot(ListDigraph &_digraph)
727 : node_observer_proxy(*this),
728 arc_observer_proxy(*this) {
732 /// \brief Make a snapshot.
734 /// Make a snapshot of the digraph.
736 /// This function can be called more than once. In case of a repeated
737 /// call, the previous snapshot gets lost.
738 /// \param _digraph The digraph we make the snapshot of.
739 void save(ListDigraph &_digraph) {
747 /// \brief Undo the changes until the last snapshot.
749 /// Undo the changes until the last snapshot created by save().
752 for(std::list<Arc>::iterator it = added_arcs.begin();
753 it != added_arcs.end(); ++it) {
756 for(std::list<Node>::iterator it = added_nodes.begin();
757 it != added_nodes.end(); ++it) {
763 /// \brief Gives back true when the snapshot is valid.
765 /// Gives back true when the snapshot is valid.
775 class ListGraphBase {
786 int prev_out, next_out;
789 std::vector<NodeT> nodes;
795 std::vector<ArcT> arcs;
801 typedef ListGraphBase Digraph;
808 friend class ListGraphBase;
812 explicit Node(int pid) { id = pid;}
816 Node (Invalid) { id = -1; }
817 bool operator==(const Node& node) const {return id == node.id;}
818 bool operator!=(const Node& node) const {return id != node.id;}
819 bool operator<(const Node& node) const {return id < node.id;}
823 friend class ListGraphBase;
827 explicit Edge(int pid) { id = pid;}
831 Edge (Invalid) { id = -1; }
832 bool operator==(const Edge& edge) const {return id == edge.id;}
833 bool operator!=(const Edge& edge) const {return id != edge.id;}
834 bool operator<(const Edge& edge) const {return id < edge.id;}
838 friend class ListGraphBase;
842 explicit Arc(int pid) { id = pid;}
845 operator Edge() const {
846 return id != -1 ? edgeFromId(id / 2) : INVALID;
850 Arc (Invalid) { id = -1; }
851 bool operator==(const Arc& arc) const {return id == arc.id;}
852 bool operator!=(const Arc& arc) const {return id != arc.id;}
853 bool operator<(const Arc& arc) const {return id < arc.id;}
859 : nodes(), first_node(-1),
860 first_free_node(-1), arcs(), first_free_arc(-1) {}
863 int maxNodeId() const { return nodes.size()-1; }
864 int maxEdgeId() const { return arcs.size() / 2 - 1; }
865 int maxArcId() const { return arcs.size()-1; }
867 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
868 Node target(Arc e) const { return Node(arcs[e.id].target); }
870 Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
871 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
873 static bool direction(Arc e) {
874 return (e.id & 1) == 1;
877 static Arc direct(Edge e, bool d) {
878 return Arc(e.id * 2 + (d ? 1 : 0));
881 void first(Node& node) const {
882 node.id = first_node;
885 void next(Node& node) const {
886 node.id = nodes[node.id].next;
889 void first(Arc& e) const {
891 while (n != -1 && nodes[n].first_out == -1) {
894 e.id = (n == -1) ? -1 : nodes[n].first_out;
897 void next(Arc& e) const {
898 if (arcs[e.id].next_out != -1) {
899 e.id = arcs[e.id].next_out;
901 int n = nodes[arcs[e.id ^ 1].target].next;
902 while(n != -1 && nodes[n].first_out == -1) {
905 e.id = (n == -1) ? -1 : nodes[n].first_out;
909 void first(Edge& e) const {
912 e.id = nodes[n].first_out;
913 while ((e.id & 1) != 1) {
914 e.id = arcs[e.id].next_out;
925 void next(Edge& e) const {
926 int n = arcs[e.id * 2].target;
927 e.id = arcs[(e.id * 2) | 1].next_out;
928 while ((e.id & 1) != 1) {
929 e.id = arcs[e.id].next_out;
937 e.id = nodes[n].first_out;
938 while ((e.id & 1) != 1) {
939 e.id = arcs[e.id].next_out;
950 void firstOut(Arc &e, const Node& v) const {
951 e.id = nodes[v.id].first_out;
953 void nextOut(Arc &e) const {
954 e.id = arcs[e.id].next_out;
957 void firstIn(Arc &e, const Node& v) const {
958 e.id = ((nodes[v.id].first_out) ^ 1);
959 if (e.id == -2) e.id = -1;
961 void nextIn(Arc &e) const {
962 e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
963 if (e.id == -2) e.id = -1;
966 void firstInc(Edge &e, bool& d, const Node& v) const {
967 int a = nodes[v.id].first_out;
976 void nextInc(Edge &e, bool& d) const {
977 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
987 static int id(Node v) { return v.id; }
988 static int id(Arc e) { return e.id; }
989 static int id(Edge e) { return e.id; }
991 static Node nodeFromId(int id) { return Node(id);}
992 static Arc arcFromId(int id) { return Arc(id);}
993 static Edge edgeFromId(int id) { return Edge(id);}
995 bool valid(Node n) const {
996 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
997 nodes[n.id].prev != -2;
1000 bool valid(Arc a) const {
1001 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1002 arcs[a.id].prev_out != -2;
1005 bool valid(Edge e) const {
1006 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1007 arcs[2 * e.id].prev_out != -2;
1013 if(first_free_node==-1) {
1015 nodes.push_back(NodeT());
1017 n = first_free_node;
1018 first_free_node = nodes[n].next;
1021 nodes[n].next = first_node;
1022 if (first_node != -1) nodes[first_node].prev = n;
1026 nodes[n].first_out = -1;
1031 Edge addEdge(Node u, Node v) {
1034 if (first_free_arc == -1) {
1036 arcs.push_back(ArcT());
1037 arcs.push_back(ArcT());
1040 first_free_arc = arcs[n].next_out;
1043 arcs[n].target = u.id;
1044 arcs[n | 1].target = v.id;
1046 arcs[n].next_out = nodes[v.id].first_out;
1047 if (nodes[v.id].first_out != -1) {
1048 arcs[nodes[v.id].first_out].prev_out = n;
1050 arcs[n].prev_out = -1;
1051 nodes[v.id].first_out = n;
1053 arcs[n | 1].next_out = nodes[u.id].first_out;
1054 if (nodes[u.id].first_out != -1) {
1055 arcs[nodes[u.id].first_out].prev_out = (n | 1);
1057 arcs[n | 1].prev_out = -1;
1058 nodes[u.id].first_out = (n | 1);
1063 void erase(const Node& node) {
1066 if(nodes[n].next != -1) {
1067 nodes[nodes[n].next].prev = nodes[n].prev;
1070 if(nodes[n].prev != -1) {
1071 nodes[nodes[n].prev].next = nodes[n].next;
1073 first_node = nodes[n].next;
1076 nodes[n].next = first_free_node;
1077 first_free_node = n;
1081 void erase(const Edge& edge) {
1082 int n = edge.id * 2;
1084 if (arcs[n].next_out != -1) {
1085 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1088 if (arcs[n].prev_out != -1) {
1089 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1091 nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1094 if (arcs[n | 1].next_out != -1) {
1095 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1098 if (arcs[n | 1].prev_out != -1) {
1099 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1101 nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1104 arcs[n].next_out = first_free_arc;
1106 arcs[n].prev_out = -2;
1107 arcs[n | 1].prev_out = -2;
1114 first_node = first_free_node = first_free_arc = -1;
1119 void changeTarget(Edge e, Node n) {
1120 if(arcs[2 * e.id].next_out != -1) {
1121 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1123 if(arcs[2 * e.id].prev_out != -1) {
1124 arcs[arcs[2 * e.id].prev_out].next_out =
1125 arcs[2 * e.id].next_out;
1127 nodes[arcs[(2 * e.id) | 1].target].first_out =
1128 arcs[2 * e.id].next_out;
1131 if (nodes[n.id].first_out != -1) {
1132 arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1134 arcs[(2 * e.id) | 1].target = n.id;
1135 arcs[2 * e.id].prev_out = -1;
1136 arcs[2 * e.id].next_out = nodes[n.id].first_out;
1137 nodes[n.id].first_out = 2 * e.id;
1140 void changeSource(Edge e, Node n) {
1141 if(arcs[(2 * e.id) | 1].next_out != -1) {
1142 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1143 arcs[(2 * e.id) | 1].prev_out;
1145 if(arcs[(2 * e.id) | 1].prev_out != -1) {
1146 arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1147 arcs[(2 * e.id) | 1].next_out;
1149 nodes[arcs[2 * e.id].target].first_out =
1150 arcs[(2 * e.id) | 1].next_out;
1153 if (nodes[n.id].first_out != -1) {
1154 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1156 arcs[2 * e.id].target = n.id;
1157 arcs[(2 * e.id) | 1].prev_out = -1;
1158 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1159 nodes[n.id].first_out = ((2 * e.id) | 1);
1164 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1167 /// \addtogroup graphs
1170 ///A general undirected graph structure.
1172 ///\ref ListGraph is a simple and fast <em>undirected graph</em>
1173 ///implementation based on static linked lists that are stored in
1174 ///\c std::vector structures.
1176 ///It conforms to the \ref concepts::Graph "Graph concept" and it
1177 ///also provides several useful additional functionalities.
1178 ///Most of the member functions and nested classes are documented
1179 ///only in the concept class.
1181 ///An important extra feature of this graph implementation is that
1182 ///its maps are real \ref concepts::ReferenceMap "reference map"s.
1184 ///\sa concepts::Graph
1186 class ListGraph : public ExtendedListGraphBase {
1188 ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1190 ///ListGraph is \e not copy constructible. Use copyGraph() instead.
1192 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1193 ///\brief Assignment of ListGraph to another one is \e not allowed.
1194 ///Use copyGraph() instead.
1196 ///Assignment of ListGraph to another one is \e not allowed.
1197 ///Use copyGraph() instead.
1198 void operator=(const ListGraph &) {}
1206 typedef ExtendedListGraphBase Parent;
1208 typedef Parent::OutArcIt IncEdgeIt;
1210 /// \brief Add a new node to the graph.
1212 /// Add a new node to the graph.
1213 /// \return the new node.
1214 Node addNode() { return Parent::addNode(); }
1216 /// \brief Add a new edge to the graph.
1218 /// Add a new edge to the graph with source node \c s
1219 /// and target node \c t.
1220 /// \return the new edge.
1221 Edge addEdge(const Node& s, const Node& t) {
1222 return Parent::addEdge(s, t);
1225 /// \brief Erase a node from the graph.
1227 /// Erase a node from the graph.
1229 void erase(const Node& n) { Parent::erase(n); }
1231 /// \brief Erase an edge from the graph.
1233 /// Erase an edge from the graph.
1235 void erase(const Edge& e) { Parent::erase(e); }
1236 /// Node validity check
1238 /// This function gives back true if the given node is valid,
1239 /// ie. it is a real node of the graph.
1241 /// \warning A Node pointing to a removed item
1242 /// could become valid again later if new nodes are
1243 /// added to the graph.
1244 bool valid(Node n) const { return Parent::valid(n); }
1245 /// Arc validity check
1247 /// This function gives back true if the given arc is valid,
1248 /// ie. it is a real arc of the graph.
1250 /// \warning An Arc pointing to a removed item
1251 /// could become valid again later if new edges are
1252 /// added to the graph.
1253 bool valid(Arc a) const { return Parent::valid(a); }
1254 /// Edge validity check
1256 /// This function gives back true if the given edge is valid,
1257 /// ie. it is a real arc of the graph.
1259 /// \warning A Edge pointing to a removed item
1260 /// could become valid again later if new edges are
1261 /// added to the graph.
1262 bool valid(Edge e) const { return Parent::valid(e); }
1263 /// \brief Change the source of \c e to \c n
1265 /// This function changes the source of \c e to \c n.
1267 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1268 ///referencing the changed arc remain
1269 ///valid. However <tt>OutArcIt</tt>s are invalidated.
1271 ///\warning This functionality cannot be used together with the
1272 ///Snapshot feature.
1273 void changeSource(Edge e, Node n) {
1274 Parent::changeSource(e,n);
1276 /// \brief Change the target of \c e to \c n
1278 /// This function changes the target of \c e to \c n.
1280 /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
1281 /// valid. However the other iterators may be invalidated.
1283 ///\warning This functionality cannot be used together with the
1284 ///Snapshot feature.
1285 void changeTarget(Edge e, Node n) {
1286 Parent::changeTarget(e,n);
1288 /// \brief Change the source of \c e to \c n
1290 /// This function changes the source of \c e to \c n.
1291 /// It also changes the proper node of the represented edge.
1293 ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
1294 ///referencing the changed arc remain
1295 ///valid. However <tt>OutArcIt</tt>s are invalidated.
1297 ///\warning This functionality cannot be used together with the
1298 ///Snapshot feature.
1299 void changeSource(Arc e, Node n) {
1300 if (Parent::direction(e)) {
1301 Parent::changeSource(e,n);
1303 Parent::changeTarget(e,n);
1306 /// \brief Change the target of \c e to \c n
1308 /// This function changes the target of \c e to \c n.
1309 /// It also changes the proper node of the represented edge.
1311 ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
1312 ///referencing the changed arc remain
1313 ///valid. However <tt>InArcIt</tt>s are invalidated.
1315 ///\warning This functionality cannot be used together with the
1316 ///Snapshot feature.
1317 void changeTarget(Arc e, Node n) {
1318 if (Parent::direction(e)) {
1319 Parent::changeTarget(e,n);
1321 Parent::changeSource(e,n);
1324 /// \brief Contract two nodes.
1326 /// This function contracts two nodes.
1327 /// Node \p b will be removed but instead of deleting
1328 /// its neighboring arcs, they will be joined to \p a.
1329 /// The last parameter \p r controls whether to remove loops. \c true
1330 /// means that loops will be removed.
1332 /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
1335 ///\warning This functionality cannot be used together with the
1336 ///Snapshot feature.
1337 void contract(Node a, Node b, bool r = true) {
1338 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1339 IncEdgeIt f = e; ++f;
1340 if (r && runningNode(e) == a) {
1342 } else if (source(e) == b) {
1353 /// \brief Class to make a snapshot of the graph and restore
1356 /// Class to make a snapshot of the graph and restore it later.
1358 /// The newly added nodes and edges can be removed
1359 /// using the restore() function.
1361 /// \warning Edge and node deletions and other modifications
1362 /// (e.g. changing nodes of edges, contracting nodes) cannot be
1363 /// restored. These events invalidate the snapshot.
1367 typedef Parent::NodeNotifier NodeNotifier;
1369 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1372 NodeObserverProxy(Snapshot& _snapshot)
1373 : snapshot(_snapshot) {}
1375 using NodeNotifier::ObserverBase::attach;
1376 using NodeNotifier::ObserverBase::detach;
1377 using NodeNotifier::ObserverBase::attached;
1381 virtual void add(const Node& node) {
1382 snapshot.addNode(node);
1384 virtual void add(const std::vector<Node>& nodes) {
1385 for (int i = nodes.size() - 1; i >= 0; ++i) {
1386 snapshot.addNode(nodes[i]);
1389 virtual void erase(const Node& node) {
1390 snapshot.eraseNode(node);
1392 virtual void erase(const std::vector<Node>& nodes) {
1393 for (int i = 0; i < int(nodes.size()); ++i) {
1394 snapshot.eraseNode(nodes[i]);
1397 virtual void build() {
1399 std::vector<Node> nodes;
1400 for (notifier()->first(node); node != INVALID;
1401 notifier()->next(node)) {
1402 nodes.push_back(node);
1404 for (int i = nodes.size() - 1; i >= 0; --i) {
1405 snapshot.addNode(nodes[i]);
1408 virtual void clear() {
1410 for (notifier()->first(node); node != INVALID;
1411 notifier()->next(node)) {
1412 snapshot.eraseNode(node);
1419 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1422 EdgeObserverProxy(Snapshot& _snapshot)
1423 : snapshot(_snapshot) {}
1425 using EdgeNotifier::ObserverBase::attach;
1426 using EdgeNotifier::ObserverBase::detach;
1427 using EdgeNotifier::ObserverBase::attached;
1431 virtual void add(const Edge& edge) {
1432 snapshot.addEdge(edge);
1434 virtual void add(const std::vector<Edge>& edges) {
1435 for (int i = edges.size() - 1; i >= 0; ++i) {
1436 snapshot.addEdge(edges[i]);
1439 virtual void erase(const Edge& edge) {
1440 snapshot.eraseEdge(edge);
1442 virtual void erase(const std::vector<Edge>& edges) {
1443 for (int i = 0; i < int(edges.size()); ++i) {
1444 snapshot.eraseEdge(edges[i]);
1447 virtual void build() {
1449 std::vector<Edge> edges;
1450 for (notifier()->first(edge); edge != INVALID;
1451 notifier()->next(edge)) {
1452 edges.push_back(edge);
1454 for (int i = edges.size() - 1; i >= 0; --i) {
1455 snapshot.addEdge(edges[i]);
1458 virtual void clear() {
1460 for (notifier()->first(edge); edge != INVALID;
1461 notifier()->next(edge)) {
1462 snapshot.eraseEdge(edge);
1471 NodeObserverProxy node_observer_proxy;
1472 EdgeObserverProxy edge_observer_proxy;
1474 std::list<Node> added_nodes;
1475 std::list<Edge> added_edges;
1478 void addNode(const Node& node) {
1479 added_nodes.push_front(node);
1481 void eraseNode(const Node& node) {
1482 std::list<Node>::iterator it =
1483 std::find(added_nodes.begin(), added_nodes.end(), node);
1484 if (it == added_nodes.end()) {
1486 edge_observer_proxy.detach();
1487 throw NodeNotifier::ImmediateDetach();
1489 added_nodes.erase(it);
1493 void addEdge(const Edge& edge) {
1494 added_edges.push_front(edge);
1496 void eraseEdge(const Edge& edge) {
1497 std::list<Edge>::iterator it =
1498 std::find(added_edges.begin(), added_edges.end(), edge);
1499 if (it == added_edges.end()) {
1501 node_observer_proxy.detach();
1502 throw EdgeNotifier::ImmediateDetach();
1504 added_edges.erase(it);
1508 void attach(ListGraph &_graph) {
1510 node_observer_proxy.attach(graph->notifier(Node()));
1511 edge_observer_proxy.attach(graph->notifier(Edge()));
1515 node_observer_proxy.detach();
1516 edge_observer_proxy.detach();
1519 bool attached() const {
1520 return node_observer_proxy.attached();
1524 added_nodes.clear();
1525 added_edges.clear();
1530 /// \brief Default constructor.
1532 /// Default constructor.
1533 /// To actually make a snapshot you must call save().
1535 : graph(0), node_observer_proxy(*this),
1536 edge_observer_proxy(*this) {}
1538 /// \brief Constructor that immediately makes a snapshot.
1540 /// This constructor immediately makes a snapshot of the graph.
1541 /// \param _graph The graph we make a snapshot of.
1542 Snapshot(ListGraph &_graph)
1543 : node_observer_proxy(*this),
1544 edge_observer_proxy(*this) {
1548 /// \brief Make a snapshot.
1550 /// Make a snapshot of the graph.
1552 /// This function can be called more than once. In case of a repeated
1553 /// call, the previous snapshot gets lost.
1554 /// \param _graph The graph we make the snapshot of.
1555 void save(ListGraph &_graph) {
1563 /// \brief Undo the changes until the last snapshot.
1565 /// Undo the changes until the last snapshot created by save().
1568 for(std::list<Edge>::iterator it = added_edges.begin();
1569 it != added_edges.end(); ++it) {
1572 for(std::list<Node>::iterator it = added_nodes.begin();
1573 it != added_nodes.end(); ++it) {
1579 /// \brief Gives back true when the snapshot is valid.
1581 /// Gives back true when the snapshot is valid.
1582 bool valid() const {