The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_LIST_GRAPH_H
20 #define LEMON_LIST_GRAPH_H
24 ///\brief ListGraph, ListUGraph classes.
26 #include <lemon/bits/graph_extender.h>
28 #include <lemon/error.h>
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<EdgeT> edges;
61 typedef ListGraphBase Graph;
64 friend class ListGraphBase;
68 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 ListGraphBase;
83 Edge(int pid) { id = pid;}
87 Edge (Invalid) { id = -1; }
88 bool operator==(const Edge& edge) const {return id == edge.id;}
89 bool operator!=(const Edge& edge) const {return id != edge.id;}
90 bool operator<(const Edge& edge) const {return id < edge.id;}
96 : nodes(), first_node(-1),
97 first_free_node(-1), edges(), first_free_edge(-1) {}
104 int maxNodeId() const { return nodes.size()-1; }
110 int maxEdgeId() const { return edges.size()-1; }
112 Node source(Edge e) const { return edges[e.id].source; }
113 Node target(Edge e) const { return edges[e.id].target; }
116 void first(Node& node) const {
117 node.id = first_node;
120 void next(Node& node) const {
121 node.id = nodes[node.id].next;
125 void first(Edge& e) const {
128 n!=-1 && nodes[n].first_in == -1;
130 e.id = (n == -1) ? -1 : nodes[n].first_in;
133 void next(Edge& edge) const {
134 if (edges[edge.id].next_in != -1) {
135 edge.id = edges[edge.id].next_in;
138 for(n = nodes[edges[edge.id].target].next;
139 n!=-1 && nodes[n].first_in == -1;
141 edge.id = (n == -1) ? -1 : nodes[n].first_in;
145 void firstOut(Edge &e, const Node& v) const {
146 e.id = nodes[v.id].first_out;
148 void nextOut(Edge &e) const {
149 e.id=edges[e.id].next_out;
152 void firstIn(Edge &e, const Node& v) const {
153 e.id = nodes[v.id].first_in;
155 void nextIn(Edge &e) const {
156 e.id=edges[e.id].next_in;
160 static int id(Node v) { return v.id; }
161 static int id(Edge e) { return e.id; }
163 static Node nodeFromId(int id) { return Node(id);}
164 static Edge edgeFromId(int id) { return Edge(id);}
166 /// Adds a new node to the graph.
168 /// \warning It adds the new node to the front of the list.
169 /// (i.e. the lastly added node becomes the first.)
173 if(first_free_node==-1) {
175 nodes.push_back(NodeT());
178 first_free_node = nodes[n].next;
181 nodes[n].next = first_node;
182 if(first_node != -1) nodes[first_node].prev = n;
186 nodes[n].first_in = nodes[n].first_out = -1;
191 Edge addEdge(Node u, Node v) {
194 if (first_free_edge == -1) {
196 edges.push_back(EdgeT());
199 first_free_edge = edges[n].next_in;
202 edges[n].source = u.id;
203 edges[n].target = v.id;
205 edges[n].next_out = nodes[u.id].first_out;
206 if(nodes[u.id].first_out != -1) {
207 edges[nodes[u.id].first_out].prev_out = n;
210 edges[n].next_in = nodes[v.id].first_in;
211 if(nodes[v.id].first_in != -1) {
212 edges[nodes[v.id].first_in].prev_in = n;
215 edges[n].prev_in = edges[n].prev_out = -1;
217 nodes[u.id].first_out = nodes[v.id].first_in = n;
222 void erase(const Node& node) {
225 if(nodes[n].next != -1) {
226 nodes[nodes[n].next].prev = nodes[n].prev;
229 if(nodes[n].prev != -1) {
230 nodes[nodes[n].prev].next = nodes[n].next;
232 first_node = nodes[n].next;
235 nodes[n].next = first_free_node;
240 void erase(const Edge& edge) {
243 if(edges[n].next_in!=-1) {
244 edges[edges[n].next_in].prev_in = edges[n].prev_in;
247 if(edges[n].prev_in!=-1) {
248 edges[edges[n].prev_in].next_in = edges[n].next_in;
250 nodes[edges[n].target].first_in = edges[n].next_in;
254 if(edges[n].next_out!=-1) {
255 edges[edges[n].next_out].prev_out = edges[n].prev_out;
258 if(edges[n].prev_out!=-1) {
259 edges[edges[n].prev_out].next_out = edges[n].next_out;
261 nodes[edges[n].source].first_out = edges[n].next_out;
264 edges[n].next_in = first_free_edge;
272 first_node = first_free_node = first_free_edge = -1;
276 void _changeTarget(Edge e, Node n)
278 if(edges[e.id].next_in != -1)
279 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
280 if(edges[e.id].prev_in != -1)
281 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
282 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
283 if (nodes[n.id].first_in != -1) {
284 edges[nodes[n.id].first_in].prev_in = e.id;
286 edges[e.id].target = n.id;
287 edges[e.id].prev_in = -1;
288 edges[e.id].next_in = nodes[n.id].first_in;
289 nodes[n.id].first_in = e.id;
291 void _changeSource(Edge e, Node n)
293 if(edges[e.id].next_out != -1)
294 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
295 if(edges[e.id].prev_out != -1)
296 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
297 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
298 if (nodes[n.id].first_out != -1) {
299 edges[nodes[n.id].first_out].prev_out = e.id;
301 edges[e.id].source = n.id;
302 edges[e.id].prev_out = -1;
303 edges[e.id].next_out = nodes[n.id].first_out;
304 nodes[n.id].first_out = e.id;
309 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
311 /// \addtogroup graphs
314 ///A list graph class.
316 ///This is a simple and fast erasable graph implementation.
318 ///It addition that it conforms to the
319 ///\ref concept::ErasableGraph "ErasableGraph" concept,
320 ///it also provides several additional useful extra functionalities.
321 ///\sa concept::ErasableGraph.
323 class ListGraph : public ExtendedListGraphBase
326 /// Changes the target of \c e to \c n
328 /// Changes the target of \c e to \c n
330 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
331 ///referencing the changed edge remain
332 ///valid. However <tt>InEdge</tt>'s are invalidated.
333 void changeTarget(Edge e, Node n) {
336 /// Changes the source of \c e to \c n
338 /// Changes the source of \c e to \c n
340 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
341 ///referencing the changed edge remain
342 ///valid. However <tt>OutEdge</tt>'s are invalidated.
343 void changeSource(Edge e, Node n) {
347 /// Invert the direction of an edge.
349 ///\note The <tt>Edge</tt>'s
350 ///referencing the changed edge remain
351 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated.
352 void reverseEdge(Edge e) {
354 _changeTarget(e,source(e));
358 ///Using this it possible to avoid the superfluous memory allocation.
360 ///Using this it possible to avoid the superfluous memory allocation.
361 ///\todo more docs...
362 void reserveEdge(int n) { edges.reserve(n); };
364 ///Contract two nodes.
366 ///This function contracts two nodes.
368 ///Node \p b will be removed but instead of deleting
369 ///its neighboring edges, they will be joined to \p a.
370 ///The last parameter \p r controls whether to remove loops. \c true
371 ///means that loops will be removed.
373 ///\note The <tt>Edge</tt>s
374 ///referencing a moved edge remain
375 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
376 ///may be invalidated.
377 void contract(Node a, Node b, bool r = true)
379 for(OutEdgeIt e(*this,b);e!=INVALID;) {
382 if(r && target(e)==a) erase(e);
383 else changeSource(e,a);
386 for(InEdgeIt e(*this,b);e!=INVALID;) {
389 if(r && source(e)==a) erase(e);
390 else changeTarget(e,a);
398 ///This function splits a node. First a new node is added to the graph,
399 ///then the source of each outgoing edge of \c n is moved to this new node.
400 ///If \c connect is \c true (this is the default value), then a new edge
401 ///from \c n to the newly created node is also added.
402 ///\return The newly created node.
404 ///\note The <tt>Edge</tt>s
405 ///referencing a moved edge remain
406 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
407 ///may be invalidated.
408 ///\warning This functionality cannot be used together with the Snapshot
410 ///\todo It could be implemented in a bit faster way.
411 Node split(Node n, bool connect = true)
414 for(OutEdgeIt e(*this,n);e!=INVALID;) {
420 if(connect) addEdge(n,b);
426 ///This function splits an edge. First a new node \c b is added to the graph,
427 ///then the original edge is re-targetes to \c b. Finally an edge
428 ///from \c b to the original target is added.
429 ///\return The newly created node.
430 ///\warning This functionality cannot be used together with the Snapshot
435 addEdge(b,target(e));
440 ///Class to make a snapshot of the graph and to restrore to it later.
442 ///Class to make a snapshot of the graph and to restrore to it later.
444 ///The newly added nodes and edges can be removed using the
445 ///restore() function.
447 ///\warning Edge and node deletions cannot be restored.
448 ///\warning Snapshots cannot be nested.
449 class Snapshot : protected AlterationNotifier<Node>::ObserverBase,
450 protected AlterationNotifier<Edge>::ObserverBase
454 class UnsupportedOperation : public LogicError {
456 virtual const char* exceptionName() const {
457 return "lemon::ListGraph::Snapshot::UnsupportedOperation";
465 std::list<Node> added_nodes;
466 std::list<Edge> added_edges;
469 virtual void add(const Node& n) {
470 added_nodes.push_back(n);
472 virtual void erase(const Node&)
474 throw UnsupportedOperation();
476 virtual void add(const Edge& n) {
477 added_edges.push_back(n);
479 virtual void erase(const Edge&)
481 throw UnsupportedOperation();
484 ///\bug What is this used for?
486 virtual void build() {}
487 ///\bug What is this used for?
489 virtual void clear() {}
491 void regist(ListGraph &_g) {
493 AlterationNotifier<Node>::ObserverBase::
494 attach(g->getNotifier(Node()));
495 AlterationNotifier<Edge>::ObserverBase::
496 attach(g->getNotifier(Edge()));
500 AlterationNotifier<Node>::ObserverBase::
502 AlterationNotifier<Edge>::ObserverBase::
508 ///Default constructur.
510 ///Default constructur.
511 ///To actually make a snapshot you must call save().
514 ///Constructor that immediately makes a snapshot.
516 ///This constructor immediately makes a snapshot of the graph.
517 ///\param _g The graph we make a snapshot of.
518 Snapshot(ListGraph &_g) {
521 ///\bug Is it necessary?
530 ///Make a snapshot of the graph.
532 ///This function can be called more than once. In case of a repeated
533 ///call, the previous snapshot gets lost.
534 ///\param _g The graph we make the snapshot of.
535 void save(ListGraph &_g)
545 ///Undo the changes until the last snapshot.
547 ///Undo the changes until last snapshot created by save().
549 ///\todo This function might be called undo().
553 while(!added_edges.empty()) {
554 old_g.erase(added_edges.front());
555 added_edges.pop_front();
557 while(!added_nodes.empty()) {
558 old_g.erase(added_nodes.front());
559 added_nodes.pop_front();
568 /**************** Undirected List Graph ****************/
570 typedef UGraphExtender<UGraphBaseExtender<
571 ListGraphBase> > ExtendedListUGraphBase;
573 /// \addtogroup graphs
576 ///An undirected list graph class.
578 ///This is a simple and fast erasable undirected graph implementation.
580 ///It conforms to the
581 ///\ref concept::UGraph "UGraph" concept.
583 ///\sa concept::UGraph.
585 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
586 ///haven't been implemented yet.
588 class ListUGraph : public ExtendedListUGraphBase {
590 typedef ExtendedListUGraphBase Parent;
591 /// \brief Changes the target of \c e to \c n
593 /// Changes the target of \c e to \c n
595 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
596 /// referencing the changed edge remain
597 /// valid. However <tt>InEdge</tt>'s are invalidated.
598 void changeTarget(UEdge e, Node n) {
601 /// Changes the source of \c e to \c n
603 /// Changes the source of \c e to \c n
605 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
606 ///referencing the changed edge remain
607 ///valid. However <tt>OutEdge</tt>'s are invalidated.
608 void changeSource(UEdge e, Node n) {
611 /// \brief Contract two nodes.
613 /// This function contracts two nodes.
615 /// Node \p b will be removed but instead of deleting
616 /// its neighboring edges, they will be joined to \p a.
617 /// The last parameter \p r controls whether to remove loops. \c true
618 /// means that loops will be removed.
620 /// \note The <tt>Edge</tt>s
621 /// referencing a moved edge remain
623 void contract(Node a, Node b, bool r = true) {
624 for(IncEdgeIt e(*this, b); e!=INVALID;) {
625 IncEdgeIt f = e; ++f;
626 if (r && runningNode(e) == a) {
628 } else if (source(e) == b) {
640 class ListBpUGraphBase {
643 class NodeSetError : public LogicError {
644 virtual const char* exceptionName() const {
645 return "lemon::ListBpUGraph::NodeSetError";
652 int first_edge, next_node;
656 int aNode, prev_out, next_out;
657 int bNode, prev_in, next_in;
660 std::vector<NodeT> aNodes;
661 std::vector<NodeT> bNodes;
663 std::vector<EdgeT> edges;
666 int first_free_anode;
669 int first_free_bnode;
676 friend class ListBpUGraphBase;
680 Node(int _id) : id(_id) {}
683 Node(Invalid) { id = -1; }
684 bool operator==(const Node i) const {return id==i.id;}
685 bool operator!=(const Node i) const {return id!=i.id;}
686 bool operator<(const Node i) const {return id<i.id;}
690 friend class ListBpUGraphBase;
694 Edge(int _id) { id = _id;}
697 Edge (Invalid) { id = -1; }
698 bool operator==(const Edge i) const {return id==i.id;}
699 bool operator!=(const Edge i) const {return id!=i.id;}
700 bool operator<(const Edge i) const {return id<i.id;}
704 : first_anode(-1), first_free_anode(-1),
705 first_bnode(-1), first_free_bnode(-1),
706 first_free_edge(-1) {}
708 void firstANode(Node& node) const {
709 node.id = first_anode != -1 ? (first_anode << 1) : -1;
711 void nextANode(Node& node) const {
712 node.id = aNodes[node.id >> 1].next_node;
715 void firstBNode(Node& node) const {
716 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
718 void nextBNode(Node& node) const {
719 node.id = bNodes[node.id >> 1].next_node;
722 void first(Node& node) const {
723 if (first_anode != -1) {
724 node.id = (first_anode << 1);
725 } else if (first_bnode != -1) {
726 node.id = (first_bnode << 1) + 1;
731 void next(Node& node) const {
733 node.id = aNodes[node.id >> 1].next_node;
735 if (first_bnode != -1) {
736 node.id = (first_bnode << 1) + 1;
740 node.id = bNodes[node.id >> 1].next_node;
744 void first(Edge& edge) const {
745 int aNodeId = first_anode;
746 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
747 aNodeId = aNodes[aNodeId].next_node != -1 ?
748 aNodes[aNodeId].next_node >> 1 : -1;
751 edge.id = aNodes[aNodeId].first_edge;
756 void next(Edge& edge) const {
757 int aNodeId = edges[edge.id].aNode >> 1;
758 edge.id = edges[edge.id].next_out;
760 aNodeId = aNodes[aNodeId].next_node != -1 ?
761 aNodes[aNodeId].next_node >> 1 : -1;
762 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
763 aNodeId = aNodes[aNodeId].next_node != -1 ?
764 aNodes[aNodeId].next_node >> 1 : -1;
767 edge.id = aNodes[aNodeId].first_edge;
774 void firstOut(Edge& edge, const Node& node) const {
775 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
776 edge.id = aNodes[node.id >> 1].first_edge;
778 void nextOut(Edge& edge) const {
779 edge.id = edges[edge.id].next_out;
782 void firstIn(Edge& edge, const Node& node) const {
783 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
784 edge.id = bNodes[node.id >> 1].first_edge;
786 void nextIn(Edge& edge) const {
787 edge.id = edges[edge.id].next_in;
790 static int id(const Node& node) {
793 static Node nodeFromId(int id) {
796 int maxNodeId() const {
797 return aNodes.size() > bNodes.size() ?
798 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
801 static int id(const Edge& edge) {
804 static Edge edgeFromId(int id) {
807 int maxEdgeId() const {
811 static int aNodeId(const Node& node) {
814 static Node fromANodeId(int id, Node) {
815 return Node(id << 1);
817 int maxANodeId() const {
818 return aNodes.size();
821 static int bNodeId(const Node& node) {
824 static Node fromBNodeId(int id) {
825 return Node((id << 1) + 1);
827 int maxBNodeId() const {
828 return bNodes.size();
831 Node aNode(const Edge& edge) const {
832 return Node(edges[edge.id].aNode);
834 Node bNode(const Edge& edge) const {
835 return Node(edges[edge.id].bNode);
838 static bool aNode(const Node& node) {
839 return (node.id & 1) == 0;
842 static bool bNode(const Node& node) {
843 return (node.id & 1) == 1;
848 if (first_free_anode == -1) {
849 aNodeId = aNodes.size();
850 aNodes.push_back(NodeT());
852 aNodeId = first_free_anode;
853 first_free_anode = aNodes[first_free_anode].next_node;
855 aNodes[aNodeId].next_node =
856 first_anode != -1 ? (first_anode << 1) : -1;
857 first_anode = aNodeId;
858 aNodes[aNodeId].first_edge = -1;
859 return Node(aNodeId << 1);
864 if (first_free_bnode == -1) {
865 bNodeId = bNodes.size();
866 bNodes.push_back(NodeT());
868 bNodeId = first_free_bnode;
869 first_free_bnode = bNodes[first_free_bnode].next_node;
871 bNodes[bNodeId].next_node =
872 first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
873 first_bnode = bNodeId;
874 bNodes[bNodeId].first_edge = -1;
875 return Node((bNodeId << 1) + 1);
878 Edge addEdge(const Node& source, const Node& target) {
879 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
881 if (first_free_edge != -1) {
882 edgeId = first_free_edge;
883 first_free_edge = edges[edgeId].next_out;
885 edgeId = edges.size();
886 edges.push_back(EdgeT());
888 if ((source.id & 1) == 0) {
889 edges[edgeId].aNode = source.id;
890 edges[edgeId].bNode = target.id;
892 edges[edgeId].aNode = target.id;
893 edges[edgeId].bNode = source.id;
895 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
896 edges[edgeId].prev_out = -1;
897 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
898 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
900 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
901 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
902 edges[edgeId].prev_in = -1;
903 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
904 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
906 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
910 void erase(const Node& node) {
912 int aNodeId = node.id >> 1;
913 aNodes[aNodeId].next_node = first_free_anode;
914 first_free_anode = aNodeId;
916 int bNodeId = node.id >> 1;
917 bNodes[bNodeId].next_node = first_free_bnode;
918 first_free_bnode = bNodeId;
922 void erase(const Edge& edge) {
923 if (edges[edge.id].prev_out != -1) {
924 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
926 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
928 if (edges[edge.id].next_out != -1) {
929 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
931 if (edges[edge.id].prev_in != -1) {
932 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
934 bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
936 if (edges[edge.id].next_in != -1) {
937 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
939 edges[edge.id].next_out = first_free_edge;
940 first_free_edge = edge.id;
948 first_free_anode = -1;
950 first_free_bnode = -1;
951 first_free_edge = -1;
957 typedef BpUGraphExtender< BpUGraphBaseExtender<
958 ListBpUGraphBase> > ExtendedListBpUGraphBase;
962 /// \brief A smart bipartite undirected graph class.
964 /// This is a bipartite undirected graph implementation.
965 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
967 /// \sa concept::BpUGraph.
969 class ListBpUGraph : public ExtendedListBpUGraphBase {};