1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
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 and ListGraph classes.
26 #include <lemon/core.h>
27 #include <lemon/error.h>
28 #include <lemon/bits/graph_extender.h>
37 class ListDigraphBase {
41 int first_in, first_out;
47 int prev_in, prev_out;
48 int next_in, next_out;
51 std::vector<NodeT> nodes;
57 std::vector<ArcT> arcs;
63 typedef ListDigraphBase Digraph;
66 friend class ListDigraphBase;
67 friend class ListDigraph;
71 explicit Node(int pid) { id = pid;}
75 Node (Invalid) { id = -1; }
76 bool operator==(const Node& node) const {return id == node.id;}
77 bool operator!=(const Node& node) const {return id != node.id;}
78 bool operator<(const Node& node) const {return id < node.id;}
82 friend class ListDigraphBase;
83 friend class ListDigraph;
87 explicit Arc(int pid) { id = pid;}
91 Arc (Invalid) { id = -1; }
92 bool operator==(const Arc& arc) const {return id == arc.id;}
93 bool operator!=(const Arc& arc) const {return id != arc.id;}
94 bool operator<(const Arc& arc) const {return id < arc.id;}
100 : nodes(), first_node(-1),
101 first_free_node(-1), arcs(), first_free_arc(-1) {}
104 int maxNodeId() const { return nodes.size()-1; }
105 int maxArcId() const { return arcs.size()-1; }
107 Node source(Arc e) const { return Node(arcs[e.id].source); }
108 Node target(Arc e) const { return Node(arcs[e.id].target); }
111 void first(Node& node) const {
112 node.id = first_node;
115 void next(Node& node) const {
116 node.id = nodes[node.id].next;
120 void first(Arc& arc) const {
123 n!=-1 && nodes[n].first_in == -1;
124 n = nodes[n].next) {}
125 arc.id = (n == -1) ? -1 : nodes[n].first_in;
128 void next(Arc& arc) const {
129 if (arcs[arc.id].next_in != -1) {
130 arc.id = arcs[arc.id].next_in;
133 for(n = nodes[arcs[arc.id].target].next;
134 n!=-1 && nodes[n].first_in == -1;
135 n = nodes[n].next) {}
136 arc.id = (n == -1) ? -1 : nodes[n].first_in;
140 void firstOut(Arc &e, const Node& v) const {
141 e.id = nodes[v.id].first_out;
143 void nextOut(Arc &e) const {
144 e.id=arcs[e.id].next_out;
147 void firstIn(Arc &e, const Node& v) const {
148 e.id = nodes[v.id].first_in;
150 void nextIn(Arc &e) const {
151 e.id=arcs[e.id].next_in;
155 static int id(Node v) { return v.id; }
156 static int id(Arc e) { return e.id; }
158 static Node nodeFromId(int id) { return Node(id);}
159 static Arc arcFromId(int id) { return Arc(id);}
161 bool valid(Node n) const {
162 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
163 nodes[n.id].prev != -2;
166 bool valid(Arc a) const {
167 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
168 arcs[a.id].prev_in != -2;
174 if(first_free_node==-1) {
176 nodes.push_back(NodeT());
179 first_free_node = nodes[n].next;
182 nodes[n].next = first_node;
183 if(first_node != -1) nodes[first_node].prev = n;
187 nodes[n].first_in = nodes[n].first_out = -1;
192 Arc addArc(Node u, Node v) {
195 if (first_free_arc == -1) {
197 arcs.push_back(ArcT());
200 first_free_arc = arcs[n].next_in;
203 arcs[n].source = u.id;
204 arcs[n].target = v.id;
206 arcs[n].next_out = nodes[u.id].first_out;
207 if(nodes[u.id].first_out != -1) {
208 arcs[nodes[u.id].first_out].prev_out = n;
211 arcs[n].next_in = nodes[v.id].first_in;
212 if(nodes[v.id].first_in != -1) {
213 arcs[nodes[v.id].first_in].prev_in = n;
216 arcs[n].prev_in = arcs[n].prev_out = -1;
218 nodes[u.id].first_out = nodes[v.id].first_in = n;
223 void erase(const Node& node) {
226 if(nodes[n].next != -1) {
227 nodes[nodes[n].next].prev = nodes[n].prev;
230 if(nodes[n].prev != -1) {
231 nodes[nodes[n].prev].next = nodes[n].next;
233 first_node = nodes[n].next;
236 nodes[n].next = first_free_node;
242 void erase(const Arc& arc) {
245 if(arcs[n].next_in!=-1) {
246 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
249 if(arcs[n].prev_in!=-1) {
250 arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
252 nodes[arcs[n].target].first_in = arcs[n].next_in;
256 if(arcs[n].next_out!=-1) {
257 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
260 if(arcs[n].prev_out!=-1) {
261 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
263 nodes[arcs[n].source].first_out = arcs[n].next_out;
266 arcs[n].next_in = first_free_arc;
268 arcs[n].prev_in = -2;
274 first_node = first_free_node = first_free_arc = -1;
278 void changeTarget(Arc e, Node n)
280 if(arcs[e.id].next_in != -1)
281 arcs[arcs[e.id].next_in].prev_in = arcs[e.id].prev_in;
282 if(arcs[e.id].prev_in != -1)
283 arcs[arcs[e.id].prev_in].next_in = arcs[e.id].next_in;
284 else nodes[arcs[e.id].target].first_in = arcs[e.id].next_in;
285 if (nodes[n.id].first_in != -1) {
286 arcs[nodes[n.id].first_in].prev_in = e.id;
288 arcs[e.id].target = n.id;
289 arcs[e.id].prev_in = -1;
290 arcs[e.id].next_in = nodes[n.id].first_in;
291 nodes[n.id].first_in = e.id;
293 void changeSource(Arc e, Node n)
295 if(arcs[e.id].next_out != -1)
296 arcs[arcs[e.id].next_out].prev_out = arcs[e.id].prev_out;
297 if(arcs[e.id].prev_out != -1)
298 arcs[arcs[e.id].prev_out].next_out = arcs[e.id].next_out;
299 else nodes[arcs[e.id].source].first_out = arcs[e.id].next_out;
300 if (nodes[n.id].first_out != -1) {
301 arcs[nodes[n.id].first_out].prev_out = e.id;
303 arcs[e.id].source = n.id;
304 arcs[e.id].prev_out = -1;
305 arcs[e.id].next_out = nodes[n.id].first_out;
306 nodes[n.id].first_out = e.id;
311 typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
313 /// \addtogroup graphs
316 ///A general directed graph structure.
318 ///\ref ListDigraph is a versatile and fast directed graph
319 ///implementation based on linked lists that are stored in
320 ///\c std::vector structures.
322 ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"
323 ///and it also provides several useful additional functionalities.
324 ///Most of its member functions and nested classes are documented
325 ///only in the concept class.
327 ///\sa concepts::Digraph
329 class ListDigraph : public ExtendedListDigraphBase {
330 typedef ExtendedListDigraphBase Parent;
333 /// Digraphs are \e not copy constructible. Use DigraphCopy instead.
334 ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
335 /// \brief Assignment of a digraph to another one is \e not allowed.
336 /// Use DigraphCopy instead.
337 void operator=(const ListDigraph &) {}
346 ///Add a new node to the digraph.
348 ///This function adds a new node to the digraph.
349 ///\return The new node.
350 Node addNode() { return Parent::addNode(); }
352 ///Add a new arc to the digraph.
354 ///This function adds a new arc to the digraph with source node \c s
355 ///and target node \c t.
356 ///\return The new arc.
357 Arc addArc(Node s, Node t) {
358 return Parent::addArc(s, t);
361 ///\brief Erase a node from the digraph.
363 ///This function erases the given node from the digraph.
364 void erase(Node n) { Parent::erase(n); }
366 ///\brief Erase an arc from the digraph.
368 ///This function erases the given arc from the digraph.
369 void erase(Arc a) { Parent::erase(a); }
371 /// Node validity check
373 /// This function gives back \c true if the given node is valid,
374 /// i.e. it is a real node of the digraph.
376 /// \warning A removed node could become valid again if new nodes are
377 /// added to the digraph.
378 bool valid(Node n) const { return Parent::valid(n); }
380 /// Arc validity check
382 /// This function gives back \c true if the given arc is valid,
383 /// i.e. it is a real arc of the digraph.
385 /// \warning A removed arc could become valid again if new arcs are
386 /// added to the digraph.
387 bool valid(Arc a) const { return Parent::valid(a); }
389 /// Change the target node of an arc
391 /// This function changes the target node of the given arc \c a to \c n.
393 ///\note \c ArcIt and \c OutArcIt iterators referencing the changed
394 ///arc remain valid, however \c InArcIt iterators are invalidated.
396 ///\warning This functionality cannot be used together with the Snapshot
398 void changeTarget(Arc a, Node n) {
399 Parent::changeTarget(a,n);
401 /// Change the source node of an arc
403 /// This function changes the source node of the given arc \c a to \c n.
405 ///\note \c InArcIt iterators referencing the changed arc remain
406 ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.
408 ///\warning This functionality cannot be used together with the Snapshot
410 void changeSource(Arc a, Node n) {
411 Parent::changeSource(a,n);
414 /// Reverse the direction of an arc.
416 /// This function reverses the direction of the given arc.
417 ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing
418 ///the changed arc are invalidated.
420 ///\warning This functionality cannot be used together with the Snapshot
422 void reverseArc(Arc a) {
424 changeTarget(a,source(a));
428 ///Contract two nodes.
430 ///This function contracts the given two nodes.
431 ///Node \c v is removed, but instead of deleting its
432 ///incident arcs, they are joined to node \c u.
433 ///If the last parameter \c r is \c true (this is the default value),
434 ///then the newly created loops are removed.
436 ///\note The moved arcs are joined to node \c u using changeSource()
437 ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are
438 ///invalidated for the outgoing arcs of node \c v and \c InArcIt
439 ///iterators are invalidated for the incomming arcs of \c v.
440 ///Moreover all iterators referencing node \c v or the removed
441 ///loops are also invalidated. Other iterators remain valid.
443 ///\warning This functionality cannot be used together with the Snapshot
445 void contract(Node u, Node v, bool r = true)
447 for(OutArcIt e(*this,v);e!=INVALID;) {
450 if(r && target(e)==u) erase(e);
451 else changeSource(e,u);
454 for(InArcIt e(*this,v);e!=INVALID;) {
457 if(r && source(e)==u) erase(e);
458 else changeTarget(e,u);
466 ///This function splits the given node. First, a new node is added
467 ///to the digraph, then the source of each outgoing arc of node \c n
468 ///is moved to this new node.
469 ///If the second parameter \c connect is \c true (this is the default
470 ///value), then a new arc from node \c n to the newly created node
472 ///\return The newly created node.
474 ///\note All iterators remain valid.
476 ///\warning This functionality cannot be used together with the
478 Node split(Node n, bool connect = true) {
480 nodes[b.id].first_out=nodes[n.id].first_out;
481 nodes[n.id].first_out=-1;
482 for(int i=nodes[b.id].first_out; i!=-1; i=arcs[i].next_out) {
485 if (connect) addArc(n,b);
491 ///This function splits the given arc. First, a new node \c v is
492 ///added to the digraph, then the target node of the original arc
493 ///is set to \c v. Finally, an arc from \c v to the original target
495 ///\return The newly created node.
497 ///\note \c InArcIt iterators referencing the original arc are
498 ///invalidated. Other iterators remain valid.
500 ///\warning This functionality cannot be used together with the
509 ///Clear the digraph.
511 ///This function erases all nodes and arcs from the digraph.
517 /// Reserve memory for nodes.
519 /// Using this function, it is possible to avoid superfluous memory
520 /// allocation: if you know that the digraph you want to build will
521 /// be large (e.g. it will contain millions of nodes and/or arcs),
522 /// then it is worth reserving space for this amount before starting
523 /// to build the digraph.
525 void reserveNode(int n) { nodes.reserve(n); };
527 /// Reserve memory for arcs.
529 /// Using this function, it is possible to avoid superfluous memory
530 /// allocation: if you know that the digraph you want to build will
531 /// be large (e.g. it will contain millions of nodes and/or arcs),
532 /// then it is worth reserving space for this amount before starting
533 /// to build the digraph.
534 /// \sa reserveNode()
535 void reserveArc(int m) { arcs.reserve(m); };
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 /// \note After a state is restored, you cannot restore a later state,
546 /// i.e. you cannot add the removed nodes and arcs again using
547 /// another Snapshot instance.
549 /// \warning Node and arc deletions and other modifications (e.g.
550 /// reversing, contracting, splitting arcs or nodes) cannot be
551 /// restored. These events invalidate the snapshot.
552 /// However the arcs and nodes that were added to the digraph after
553 /// making the current snapshot can be removed without invalidating it.
557 typedef Parent::NodeNotifier NodeNotifier;
559 class NodeObserverProxy : public NodeNotifier::ObserverBase {
562 NodeObserverProxy(Snapshot& _snapshot)
563 : snapshot(_snapshot) {}
565 using NodeNotifier::ObserverBase::attach;
566 using NodeNotifier::ObserverBase::detach;
567 using NodeNotifier::ObserverBase::attached;
571 virtual void add(const Node& node) {
572 snapshot.addNode(node);
574 virtual void add(const std::vector<Node>& nodes) {
575 for (int i = nodes.size() - 1; i >= 0; ++i) {
576 snapshot.addNode(nodes[i]);
579 virtual void erase(const Node& node) {
580 snapshot.eraseNode(node);
582 virtual void erase(const std::vector<Node>& nodes) {
583 for (int i = 0; i < int(nodes.size()); ++i) {
584 snapshot.eraseNode(nodes[i]);
587 virtual void build() {
589 std::vector<Node> nodes;
590 for (notifier()->first(node); node != INVALID;
591 notifier()->next(node)) {
592 nodes.push_back(node);
594 for (int i = nodes.size() - 1; i >= 0; --i) {
595 snapshot.addNode(nodes[i]);
598 virtual void clear() {
600 for (notifier()->first(node); node != INVALID;
601 notifier()->next(node)) {
602 snapshot.eraseNode(node);
609 class ArcObserverProxy : public ArcNotifier::ObserverBase {
612 ArcObserverProxy(Snapshot& _snapshot)
613 : snapshot(_snapshot) {}
615 using ArcNotifier::ObserverBase::attach;
616 using ArcNotifier::ObserverBase::detach;
617 using ArcNotifier::ObserverBase::attached;
621 virtual void add(const Arc& arc) {
622 snapshot.addArc(arc);
624 virtual void add(const std::vector<Arc>& arcs) {
625 for (int i = arcs.size() - 1; i >= 0; ++i) {
626 snapshot.addArc(arcs[i]);
629 virtual void erase(const Arc& arc) {
630 snapshot.eraseArc(arc);
632 virtual void erase(const std::vector<Arc>& arcs) {
633 for (int i = 0; i < int(arcs.size()); ++i) {
634 snapshot.eraseArc(arcs[i]);
637 virtual void build() {
639 std::vector<Arc> arcs;
640 for (notifier()->first(arc); arc != INVALID;
641 notifier()->next(arc)) {
644 for (int i = arcs.size() - 1; i >= 0; --i) {
645 snapshot.addArc(arcs[i]);
648 virtual void clear() {
650 for (notifier()->first(arc); arc != INVALID;
651 notifier()->next(arc)) {
652 snapshot.eraseArc(arc);
659 ListDigraph *digraph;
661 NodeObserverProxy node_observer_proxy;
662 ArcObserverProxy arc_observer_proxy;
664 std::list<Node> added_nodes;
665 std::list<Arc> added_arcs;
668 void addNode(const Node& node) {
669 added_nodes.push_front(node);
671 void eraseNode(const Node& node) {
672 std::list<Node>::iterator it =
673 std::find(added_nodes.begin(), added_nodes.end(), node);
674 if (it == added_nodes.end()) {
676 arc_observer_proxy.detach();
677 throw NodeNotifier::ImmediateDetach();
679 added_nodes.erase(it);
683 void addArc(const Arc& arc) {
684 added_arcs.push_front(arc);
686 void eraseArc(const Arc& arc) {
687 std::list<Arc>::iterator it =
688 std::find(added_arcs.begin(), added_arcs.end(), arc);
689 if (it == added_arcs.end()) {
691 node_observer_proxy.detach();
692 throw ArcNotifier::ImmediateDetach();
694 added_arcs.erase(it);
698 void attach(ListDigraph &_digraph) {
700 node_observer_proxy.attach(digraph->notifier(Node()));
701 arc_observer_proxy.attach(digraph->notifier(Arc()));
705 node_observer_proxy.detach();
706 arc_observer_proxy.detach();
709 bool attached() const {
710 return node_observer_proxy.attached();
720 /// \brief Default constructor.
722 /// Default constructor.
723 /// You have to call save() to actually make a snapshot.
725 : digraph(0), node_observer_proxy(*this),
726 arc_observer_proxy(*this) {}
728 /// \brief Constructor that immediately makes a snapshot.
730 /// This constructor immediately makes a snapshot of the given digraph.
731 Snapshot(ListDigraph &gr)
732 : node_observer_proxy(*this),
733 arc_observer_proxy(*this) {
737 /// \brief Make a snapshot.
739 /// This function makes a snapshot of the given digraph.
740 /// It can be called more than once. In case of a repeated
741 /// call, the previous snapshot gets lost.
742 void save(ListDigraph &gr) {
750 /// \brief Undo the changes until the last snapshot.
752 /// This function undos the changes until the last snapshot
753 /// created by save() or Snapshot(ListDigraph&).
756 for(std::list<Arc>::iterator it = added_arcs.begin();
757 it != added_arcs.end(); ++it) {
760 for(std::list<Node>::iterator it = added_nodes.begin();
761 it != added_nodes.end(); ++it) {
767 /// \brief Returns \c true if the snapshot is valid.
769 /// This function returns \c true if the snapshot is valid.
779 class ListGraphBase {
790 int prev_out, next_out;
793 std::vector<NodeT> nodes;
799 std::vector<ArcT> arcs;
805 typedef ListGraphBase Graph;
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;}
857 : nodes(), first_node(-1),
858 first_free_node(-1), arcs(), first_free_arc(-1) {}
861 int maxNodeId() const { return nodes.size()-1; }
862 int maxEdgeId() const { return arcs.size() / 2 - 1; }
863 int maxArcId() const { return arcs.size()-1; }
865 Node source(Arc e) const { return Node(arcs[e.id ^ 1].target); }
866 Node target(Arc e) const { return Node(arcs[e.id].target); }
868 Node u(Edge e) const { return Node(arcs[2 * e.id].target); }
869 Node v(Edge e) const { return Node(arcs[2 * e.id + 1].target); }
871 static bool direction(Arc e) {
872 return (e.id & 1) == 1;
875 static Arc direct(Edge e, bool d) {
876 return Arc(e.id * 2 + (d ? 1 : 0));
879 void first(Node& node) const {
880 node.id = first_node;
883 void next(Node& node) const {
884 node.id = nodes[node.id].next;
887 void first(Arc& e) const {
889 while (n != -1 && nodes[n].first_out == -1) {
892 e.id = (n == -1) ? -1 : nodes[n].first_out;
895 void next(Arc& e) const {
896 if (arcs[e.id].next_out != -1) {
897 e.id = arcs[e.id].next_out;
899 int n = nodes[arcs[e.id ^ 1].target].next;
900 while(n != -1 && nodes[n].first_out == -1) {
903 e.id = (n == -1) ? -1 : nodes[n].first_out;
907 void first(Edge& e) const {
910 e.id = nodes[n].first_out;
911 while ((e.id & 1) != 1) {
912 e.id = arcs[e.id].next_out;
923 void next(Edge& e) const {
924 int n = arcs[e.id * 2].target;
925 e.id = arcs[(e.id * 2) | 1].next_out;
926 while ((e.id & 1) != 1) {
927 e.id = arcs[e.id].next_out;
935 e.id = nodes[n].first_out;
936 while ((e.id & 1) != 1) {
937 e.id = arcs[e.id].next_out;
948 void firstOut(Arc &e, const Node& v) const {
949 e.id = nodes[v.id].first_out;
951 void nextOut(Arc &e) const {
952 e.id = arcs[e.id].next_out;
955 void firstIn(Arc &e, const Node& v) const {
956 e.id = ((nodes[v.id].first_out) ^ 1);
957 if (e.id == -2) e.id = -1;
959 void nextIn(Arc &e) const {
960 e.id = ((arcs[e.id ^ 1].next_out) ^ 1);
961 if (e.id == -2) e.id = -1;
964 void firstInc(Edge &e, bool& d, const Node& v) const {
965 int a = nodes[v.id].first_out;
974 void nextInc(Edge &e, bool& d) const {
975 int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
985 static int id(Node v) { return v.id; }
986 static int id(Arc e) { return e.id; }
987 static int id(Edge e) { return e.id; }
989 static Node nodeFromId(int id) { return Node(id);}
990 static Arc arcFromId(int id) { return Arc(id);}
991 static Edge edgeFromId(int id) { return Edge(id);}
993 bool valid(Node n) const {
994 return n.id >= 0 && n.id < static_cast<int>(nodes.size()) &&
995 nodes[n.id].prev != -2;
998 bool valid(Arc a) const {
999 return a.id >= 0 && a.id < static_cast<int>(arcs.size()) &&
1000 arcs[a.id].prev_out != -2;
1003 bool valid(Edge e) const {
1004 return e.id >= 0 && 2 * e.id < static_cast<int>(arcs.size()) &&
1005 arcs[2 * e.id].prev_out != -2;
1011 if(first_free_node==-1) {
1013 nodes.push_back(NodeT());
1015 n = first_free_node;
1016 first_free_node = nodes[n].next;
1019 nodes[n].next = first_node;
1020 if (first_node != -1) nodes[first_node].prev = n;
1024 nodes[n].first_out = -1;
1029 Edge addEdge(Node u, Node v) {
1032 if (first_free_arc == -1) {
1034 arcs.push_back(ArcT());
1035 arcs.push_back(ArcT());
1038 first_free_arc = arcs[n].next_out;
1041 arcs[n].target = u.id;
1042 arcs[n | 1].target = v.id;
1044 arcs[n].next_out = nodes[v.id].first_out;
1045 if (nodes[v.id].first_out != -1) {
1046 arcs[nodes[v.id].first_out].prev_out = n;
1048 arcs[n].prev_out = -1;
1049 nodes[v.id].first_out = n;
1051 arcs[n | 1].next_out = nodes[u.id].first_out;
1052 if (nodes[u.id].first_out != -1) {
1053 arcs[nodes[u.id].first_out].prev_out = (n | 1);
1055 arcs[n | 1].prev_out = -1;
1056 nodes[u.id].first_out = (n | 1);
1061 void erase(const Node& node) {
1064 if(nodes[n].next != -1) {
1065 nodes[nodes[n].next].prev = nodes[n].prev;
1068 if(nodes[n].prev != -1) {
1069 nodes[nodes[n].prev].next = nodes[n].next;
1071 first_node = nodes[n].next;
1074 nodes[n].next = first_free_node;
1075 first_free_node = n;
1079 void erase(const Edge& edge) {
1080 int n = edge.id * 2;
1082 if (arcs[n].next_out != -1) {
1083 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1086 if (arcs[n].prev_out != -1) {
1087 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1089 nodes[arcs[n | 1].target].first_out = arcs[n].next_out;
1092 if (arcs[n | 1].next_out != -1) {
1093 arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out;
1096 if (arcs[n | 1].prev_out != -1) {
1097 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1099 nodes[arcs[n].target].first_out = arcs[n | 1].next_out;
1102 arcs[n].next_out = first_free_arc;
1104 arcs[n].prev_out = -2;
1105 arcs[n | 1].prev_out = -2;
1112 first_node = first_free_node = first_free_arc = -1;
1117 void changeV(Edge e, Node n) {
1118 if(arcs[2 * e.id].next_out != -1) {
1119 arcs[arcs[2 * e.id].next_out].prev_out = arcs[2 * e.id].prev_out;
1121 if(arcs[2 * e.id].prev_out != -1) {
1122 arcs[arcs[2 * e.id].prev_out].next_out =
1123 arcs[2 * e.id].next_out;
1125 nodes[arcs[(2 * e.id) | 1].target].first_out =
1126 arcs[2 * e.id].next_out;
1129 if (nodes[n.id].first_out != -1) {
1130 arcs[nodes[n.id].first_out].prev_out = 2 * e.id;
1132 arcs[(2 * e.id) | 1].target = n.id;
1133 arcs[2 * e.id].prev_out = -1;
1134 arcs[2 * e.id].next_out = nodes[n.id].first_out;
1135 nodes[n.id].first_out = 2 * e.id;
1138 void changeU(Edge e, Node n) {
1139 if(arcs[(2 * e.id) | 1].next_out != -1) {
1140 arcs[arcs[(2 * e.id) | 1].next_out].prev_out =
1141 arcs[(2 * e.id) | 1].prev_out;
1143 if(arcs[(2 * e.id) | 1].prev_out != -1) {
1144 arcs[arcs[(2 * e.id) | 1].prev_out].next_out =
1145 arcs[(2 * e.id) | 1].next_out;
1147 nodes[arcs[2 * e.id].target].first_out =
1148 arcs[(2 * e.id) | 1].next_out;
1151 if (nodes[n.id].first_out != -1) {
1152 arcs[nodes[n.id].first_out].prev_out = ((2 * e.id) | 1);
1154 arcs[2 * e.id].target = n.id;
1155 arcs[(2 * e.id) | 1].prev_out = -1;
1156 arcs[(2 * e.id) | 1].next_out = nodes[n.id].first_out;
1157 nodes[n.id].first_out = ((2 * e.id) | 1);
1162 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
1165 /// \addtogroup graphs
1168 ///A general undirected graph structure.
1170 ///\ref ListGraph is a versatile and fast undirected graph
1171 ///implementation based on linked lists that are stored in
1172 ///\c std::vector structures.
1174 ///This type fully conforms to the \ref concepts::Graph "Graph concept"
1175 ///and it also provides several useful additional functionalities.
1176 ///Most of its member functions and nested classes are documented
1177 ///only in the concept class.
1179 ///\sa concepts::Graph
1181 class ListGraph : public ExtendedListGraphBase {
1182 typedef ExtendedListGraphBase Parent;
1185 /// Graphs are \e not copy constructible. Use GraphCopy instead.
1186 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
1187 /// \brief Assignment of a graph to another one is \e not allowed.
1188 /// Use GraphCopy instead.
1189 void operator=(const ListGraph &) {}
1197 typedef Parent::OutArcIt IncEdgeIt;
1199 /// \brief Add a new node to the graph.
1201 /// This function adds a new node to the graph.
1202 /// \return The new node.
1203 Node addNode() { return Parent::addNode(); }
1205 /// \brief Add a new edge to the graph.
1207 /// This function adds a new edge to the graph between nodes
1208 /// \c u and \c v with inherent orientation from node \c u to
1210 /// \return The new edge.
1211 Edge addEdge(Node u, Node v) {
1212 return Parent::addEdge(u, v);
1215 ///\brief Erase a node from the graph.
1217 /// This function erases the given node from the graph.
1218 void erase(Node n) { Parent::erase(n); }
1220 ///\brief Erase an edge from the graph.
1222 /// This function erases the given edge from the graph.
1223 void erase(Edge e) { Parent::erase(e); }
1224 /// Node validity check
1226 /// This function gives back \c true if the given node is valid,
1227 /// i.e. it is a real node of the graph.
1229 /// \warning A removed node could become valid again if new nodes are
1230 /// added to the graph.
1231 bool valid(Node n) const { return Parent::valid(n); }
1232 /// Edge validity check
1234 /// This function gives back \c true if the given edge is valid,
1235 /// i.e. it is a real edge of the graph.
1237 /// \warning A removed edge could become valid again if new edges are
1238 /// added to the graph.
1239 bool valid(Edge e) const { return Parent::valid(e); }
1240 /// Arc validity check
1242 /// This function gives back \c true if the given arc is valid,
1243 /// i.e. it is a real arc of the graph.
1245 /// \warning A removed arc could become valid again if new edges are
1246 /// added to the graph.
1247 bool valid(Arc a) const { return Parent::valid(a); }
1249 /// \brief Change the first node of an edge.
1251 /// This function changes the first node of the given edge \c e to \c n.
1253 ///\note \c EdgeIt and \c ArcIt iterators referencing the
1254 ///changed edge are invalidated and all other iterators whose
1255 ///base node is the changed node are also invalidated.
1257 ///\warning This functionality cannot be used together with the
1258 ///Snapshot feature.
1259 void changeU(Edge e, Node n) {
1260 Parent::changeU(e,n);
1262 /// \brief Change the second node of an edge.
1264 /// This function changes the second node of the given edge \c e to \c n.
1266 ///\note \c EdgeIt iterators referencing the changed edge remain
1267 ///valid, however \c ArcIt iterators referencing the changed edge and
1268 ///all other iterators whose base node is the changed node are also
1271 ///\warning This functionality cannot be used together with the
1272 ///Snapshot feature.
1273 void changeV(Edge e, Node n) {
1274 Parent::changeV(e,n);
1277 /// \brief Contract two nodes.
1279 /// This function contracts the given two nodes.
1280 /// Node \c b is removed, but instead of deleting
1281 /// its incident edges, they are joined to node \c a.
1282 /// If the last parameter \c r is \c true (this is the default value),
1283 /// then the newly created loops are removed.
1285 /// \note The moved edges are joined to node \c a using changeU()
1286 /// or changeV(), thus all edge and arc iterators whose base node is
1287 /// \c b are invalidated.
1288 /// Moreover all iterators referencing node \c b or the removed
1289 /// loops are also invalidated. Other iterators remain valid.
1291 ///\warning This functionality cannot be used together with the
1292 ///Snapshot feature.
1293 void contract(Node a, Node b, bool r = true) {
1294 for(IncEdgeIt e(*this, b); e!=INVALID;) {
1295 IncEdgeIt f = e; ++f;
1296 if (r && runningNode(e) == a) {
1298 } else if (u(e) == b) {
1310 ///This function erases all nodes and arcs from the graph.
1316 /// Reserve memory for nodes.
1318 /// Using this function, it is possible to avoid superfluous memory
1319 /// allocation: if you know that the graph you want to build will
1320 /// be large (e.g. it will contain millions of nodes and/or edges),
1321 /// then it is worth reserving space for this amount before starting
1322 /// to build the graph.
1323 /// \sa reserveEdge()
1324 void reserveNode(int n) { nodes.reserve(n); };
1326 /// Reserve memory for edges.
1328 /// Using this function, it is possible to avoid superfluous memory
1329 /// allocation: if you know that the graph you want to build will
1330 /// be large (e.g. it will contain millions of nodes and/or edges),
1331 /// then it is worth reserving space for this amount before starting
1332 /// to build the graph.
1333 /// \sa reserveNode()
1334 void reserveEdge(int m) { arcs.reserve(2 * m); };
1336 /// \brief Class to make a snapshot of the graph and restore
1339 /// Class to make a snapshot of the graph and restore it later.
1341 /// The newly added nodes and edges can be removed
1342 /// using the restore() function.
1344 /// \note After a state is restored, you cannot restore a later state,
1345 /// i.e. you cannot add the removed nodes and edges again using
1346 /// another Snapshot instance.
1348 /// \warning Node and edge deletions and other modifications
1349 /// (e.g. changing the end-nodes of edges or contracting nodes)
1350 /// cannot be restored. These events invalidate the snapshot.
1351 /// However the edges and nodes that were added to the graph after
1352 /// making the current snapshot can be removed without invalidating it.
1356 typedef Parent::NodeNotifier NodeNotifier;
1358 class NodeObserverProxy : public NodeNotifier::ObserverBase {
1361 NodeObserverProxy(Snapshot& _snapshot)
1362 : snapshot(_snapshot) {}
1364 using NodeNotifier::ObserverBase::attach;
1365 using NodeNotifier::ObserverBase::detach;
1366 using NodeNotifier::ObserverBase::attached;
1370 virtual void add(const Node& node) {
1371 snapshot.addNode(node);
1373 virtual void add(const std::vector<Node>& nodes) {
1374 for (int i = nodes.size() - 1; i >= 0; ++i) {
1375 snapshot.addNode(nodes[i]);
1378 virtual void erase(const Node& node) {
1379 snapshot.eraseNode(node);
1381 virtual void erase(const std::vector<Node>& nodes) {
1382 for (int i = 0; i < int(nodes.size()); ++i) {
1383 snapshot.eraseNode(nodes[i]);
1386 virtual void build() {
1388 std::vector<Node> nodes;
1389 for (notifier()->first(node); node != INVALID;
1390 notifier()->next(node)) {
1391 nodes.push_back(node);
1393 for (int i = nodes.size() - 1; i >= 0; --i) {
1394 snapshot.addNode(nodes[i]);
1397 virtual void clear() {
1399 for (notifier()->first(node); node != INVALID;
1400 notifier()->next(node)) {
1401 snapshot.eraseNode(node);
1408 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1411 EdgeObserverProxy(Snapshot& _snapshot)
1412 : snapshot(_snapshot) {}
1414 using EdgeNotifier::ObserverBase::attach;
1415 using EdgeNotifier::ObserverBase::detach;
1416 using EdgeNotifier::ObserverBase::attached;
1420 virtual void add(const Edge& edge) {
1421 snapshot.addEdge(edge);
1423 virtual void add(const std::vector<Edge>& edges) {
1424 for (int i = edges.size() - 1; i >= 0; ++i) {
1425 snapshot.addEdge(edges[i]);
1428 virtual void erase(const Edge& edge) {
1429 snapshot.eraseEdge(edge);
1431 virtual void erase(const std::vector<Edge>& edges) {
1432 for (int i = 0; i < int(edges.size()); ++i) {
1433 snapshot.eraseEdge(edges[i]);
1436 virtual void build() {
1438 std::vector<Edge> edges;
1439 for (notifier()->first(edge); edge != INVALID;
1440 notifier()->next(edge)) {
1441 edges.push_back(edge);
1443 for (int i = edges.size() - 1; i >= 0; --i) {
1444 snapshot.addEdge(edges[i]);
1447 virtual void clear() {
1449 for (notifier()->first(edge); edge != INVALID;
1450 notifier()->next(edge)) {
1451 snapshot.eraseEdge(edge);
1460 NodeObserverProxy node_observer_proxy;
1461 EdgeObserverProxy edge_observer_proxy;
1463 std::list<Node> added_nodes;
1464 std::list<Edge> added_edges;
1467 void addNode(const Node& node) {
1468 added_nodes.push_front(node);
1470 void eraseNode(const Node& node) {
1471 std::list<Node>::iterator it =
1472 std::find(added_nodes.begin(), added_nodes.end(), node);
1473 if (it == added_nodes.end()) {
1475 edge_observer_proxy.detach();
1476 throw NodeNotifier::ImmediateDetach();
1478 added_nodes.erase(it);
1482 void addEdge(const Edge& edge) {
1483 added_edges.push_front(edge);
1485 void eraseEdge(const Edge& edge) {
1486 std::list<Edge>::iterator it =
1487 std::find(added_edges.begin(), added_edges.end(), edge);
1488 if (it == added_edges.end()) {
1490 node_observer_proxy.detach();
1491 throw EdgeNotifier::ImmediateDetach();
1493 added_edges.erase(it);
1497 void attach(ListGraph &_graph) {
1499 node_observer_proxy.attach(graph->notifier(Node()));
1500 edge_observer_proxy.attach(graph->notifier(Edge()));
1504 node_observer_proxy.detach();
1505 edge_observer_proxy.detach();
1508 bool attached() const {
1509 return node_observer_proxy.attached();
1513 added_nodes.clear();
1514 added_edges.clear();
1519 /// \brief Default constructor.
1521 /// Default constructor.
1522 /// You have to call save() to actually make a snapshot.
1524 : graph(0), node_observer_proxy(*this),
1525 edge_observer_proxy(*this) {}
1527 /// \brief Constructor that immediately makes a snapshot.
1529 /// This constructor immediately makes a snapshot of the given graph.
1530 Snapshot(ListGraph &gr)
1531 : node_observer_proxy(*this),
1532 edge_observer_proxy(*this) {
1536 /// \brief Make a snapshot.
1538 /// This function makes a snapshot of the given graph.
1539 /// It can be called more than once. In case of a repeated
1540 /// call, the previous snapshot gets lost.
1541 void save(ListGraph &gr) {
1549 /// \brief Undo the changes until the last snapshot.
1551 /// This function undos the changes until the last snapshot
1552 /// created by save() or Snapshot(ListGraph&).
1555 for(std::list<Edge>::iterator it = added_edges.begin();
1556 it != added_edges.end(); ++it) {
1559 for(std::list<Node>::iterator it = added_nodes.begin();
1560 it != added_nodes.end(); ++it) {
1566 /// \brief Returns \c true if the snapshot is valid.
1568 /// This function returns \c true if the snapshot is valid.
1569 bool valid() const {