Correcting the structure of the graph's and adaptor's map.
The template assign operators and map iterators can be used for adaptors also.
Some bugfix in the adaptors
New class SwapBpUGraphAdaptor which swaps the two nodeset of the graph.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_LIST_GRAPH_H
20 #define LEMON_LIST_GRAPH_H
24 ///\brief ListGraph, ListUGraph classes.
26 #include <lemon/bits/base_extender.h>
27 #include <lemon/bits/graph_extender.h>
29 #include <lemon/error.h>
40 int first_in, first_out;
46 int prev_in, prev_out;
47 int next_in, next_out;
50 std::vector<NodeT> nodes;
56 std::vector<EdgeT> edges;
62 typedef ListGraphBase Graph;
65 friend class ListGraphBase;
69 explicit Node(int pid) { id = pid;}
73 Node (Invalid) { id = -1; }
74 bool operator==(const Node& node) const {return id == node.id;}
75 bool operator!=(const Node& node) const {return id != node.id;}
76 bool operator<(const Node& node) const {return id < node.id;}
80 friend class ListGraphBase;
84 explicit Edge(int pid) { id = pid;}
88 Edge (Invalid) { id = -1; }
89 bool operator==(const Edge& edge) const {return id == edge.id;}
90 bool operator!=(const Edge& edge) const {return id != edge.id;}
91 bool operator<(const Edge& edge) const {return id < edge.id;}
97 : nodes(), first_node(-1),
98 first_free_node(-1), edges(), first_free_edge(-1) {}
105 int maxNodeId() const { return nodes.size()-1; }
111 int maxEdgeId() const { return edges.size()-1; }
113 Node source(Edge e) const { return Node(edges[e.id].source); }
114 Node target(Edge e) const { return Node(edges[e.id].target); }
117 void first(Node& node) const {
118 node.id = first_node;
121 void next(Node& node) const {
122 node.id = nodes[node.id].next;
126 void first(Edge& e) const {
129 n!=-1 && nodes[n].first_in == -1;
131 e.id = (n == -1) ? -1 : nodes[n].first_in;
134 void next(Edge& edge) const {
135 if (edges[edge.id].next_in != -1) {
136 edge.id = edges[edge.id].next_in;
139 for(n = nodes[edges[edge.id].target].next;
140 n!=-1 && nodes[n].first_in == -1;
142 edge.id = (n == -1) ? -1 : nodes[n].first_in;
146 void firstOut(Edge &e, const Node& v) const {
147 e.id = nodes[v.id].first_out;
149 void nextOut(Edge &e) const {
150 e.id=edges[e.id].next_out;
153 void firstIn(Edge &e, const Node& v) const {
154 e.id = nodes[v.id].first_in;
156 void nextIn(Edge &e) const {
157 e.id=edges[e.id].next_in;
161 static int id(Node v) { return v.id; }
162 static int id(Edge e) { return e.id; }
164 static Node nodeFromId(int id) { return Node(id);}
165 static Edge edgeFromId(int id) { return Edge(id);}
167 /// Adds a new node to the graph.
169 /// \warning It adds the new node to the front of the list.
170 /// (i.e. the lastly added node becomes the first.)
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 Edge addEdge(Node u, Node v) {
195 if (first_free_edge == -1) {
197 edges.push_back(EdgeT());
200 first_free_edge = edges[n].next_in;
203 edges[n].source = u.id;
204 edges[n].target = v.id;
206 edges[n].next_out = nodes[u.id].first_out;
207 if(nodes[u.id].first_out != -1) {
208 edges[nodes[u.id].first_out].prev_out = n;
211 edges[n].next_in = nodes[v.id].first_in;
212 if(nodes[v.id].first_in != -1) {
213 edges[nodes[v.id].first_in].prev_in = n;
216 edges[n].prev_in = edges[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;
241 void erase(const Edge& edge) {
244 if(edges[n].next_in!=-1) {
245 edges[edges[n].next_in].prev_in = edges[n].prev_in;
248 if(edges[n].prev_in!=-1) {
249 edges[edges[n].prev_in].next_in = edges[n].next_in;
251 nodes[edges[n].target].first_in = edges[n].next_in;
255 if(edges[n].next_out!=-1) {
256 edges[edges[n].next_out].prev_out = edges[n].prev_out;
259 if(edges[n].prev_out!=-1) {
260 edges[edges[n].prev_out].next_out = edges[n].next_out;
262 nodes[edges[n].source].first_out = edges[n].next_out;
265 edges[n].next_in = first_free_edge;
273 first_node = first_free_node = first_free_edge = -1;
277 void _changeTarget(Edge e, Node n)
279 if(edges[e.id].next_in != -1)
280 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
281 if(edges[e.id].prev_in != -1)
282 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
283 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
284 if (nodes[n.id].first_in != -1) {
285 edges[nodes[n.id].first_in].prev_in = e.id;
287 edges[e.id].target = n.id;
288 edges[e.id].prev_in = -1;
289 edges[e.id].next_in = nodes[n.id].first_in;
290 nodes[n.id].first_in = e.id;
292 void _changeSource(Edge e, Node n)
294 if(edges[e.id].next_out != -1)
295 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
296 if(edges[e.id].prev_out != -1)
297 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
298 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
299 if (nodes[n.id].first_out != -1) {
300 edges[nodes[n.id].first_out].prev_out = e.id;
302 edges[e.id].source = n.id;
303 edges[e.id].prev_out = -1;
304 edges[e.id].next_out = nodes[n.id].first_out;
305 nodes[n.id].first_out = e.id;
310 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
312 /// \addtogroup graphs
315 ///A list graph class.
317 ///This is a simple and fast erasable graph implementation.
319 ///It addition that it conforms to the
320 ///\ref concept::ErasableGraph "ErasableGraph" concept,
321 ///it also provides several additional useful extra functionalities.
322 ///\sa concept::ErasableGraph.
324 class ListGraph : public ExtendedListGraphBase {
327 typedef ExtendedListGraphBase Parent;
329 /// Changes the target of \c e to \c n
331 /// Changes the target of \c e to \c n
333 ///\note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
334 ///referencing the changed edge remain
335 ///valid. However <tt>InEdge</tt>'s are invalidated.
336 void changeTarget(Edge e, Node n) {
339 /// Changes the source of \c e to \c n
341 /// Changes the source of \c e to \c n
343 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
344 ///referencing the changed edge remain
345 ///valid. However <tt>OutEdge</tt>'s are invalidated.
346 void changeSource(Edge e, Node n) {
350 /// Invert the direction of an edge.
352 ///\note The <tt>Edge</tt>'s
353 ///referencing the changed edge remain
354 ///valid. However <tt>OutEdge</tt>'s and <tt>InEdge</tt>'s are invalidated.
355 void reverseEdge(Edge e) {
357 _changeTarget(e,source(e));
361 ///Using this it possible to avoid the superfluous memory allocation.
363 ///Using this it possible to avoid the superfluous memory allocation.
364 ///\todo more docs...
365 void reserveEdge(int n) { edges.reserve(n); };
367 ///Contract two nodes.
369 ///This function contracts two nodes.
371 ///Node \p b will be removed but instead of deleting
372 ///its neighboring edges, they will be joined to \p a.
373 ///The last parameter \p r controls whether to remove loops. \c true
374 ///means that loops will be removed.
376 ///\note The <tt>Edge</tt>s
377 ///referencing a moved edge remain
378 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
379 ///may be invalidated.
380 void contract(Node a, Node b, bool r = true)
382 for(OutEdgeIt e(*this,b);e!=INVALID;) {
385 if(r && target(e)==a) erase(e);
386 else changeSource(e,a);
389 for(InEdgeIt e(*this,b);e!=INVALID;) {
392 if(r && source(e)==a) erase(e);
393 else changeTarget(e,a);
401 ///This function splits a node. First a new node is added to the graph,
402 ///then the source of each outgoing edge of \c n is moved to this new node.
403 ///If \c connect is \c true (this is the default value), then a new edge
404 ///from \c n to the newly created node is also added.
405 ///\return The newly created node.
407 ///\note The <tt>Edge</tt>s
408 ///referencing a moved edge remain
409 ///valid. However <tt>InEdge</tt>'s and <tt>OutEdge</tt>'s
410 ///may be invalidated.
411 ///\warning This functionality cannot be used together with the Snapshot
413 ///\todo It could be implemented in a bit faster way.
414 Node split(Node n, bool connect = true)
417 for(OutEdgeIt e(*this,n);e!=INVALID;) {
423 if(connect) addEdge(n,b);
429 ///This function splits an edge. First a new node \c b is added to the graph,
430 ///then the original edge is re-targetes to \c b. Finally an edge
431 ///from \c b to the original target is added.
432 ///\return The newly created node.
433 ///\warning This functionality cannot be used together with the Snapshot
438 addEdge(b,target(e));
443 ///Class to make a snapshot of the graph and to restrore to it later.
445 ///Class to make a snapshot of the graph and to restrore to it later.
447 ///The newly added nodes and edges can be removed using the
448 ///restore() function.
450 ///\warning Edge and node deletions cannot be restored.
451 ///\warning Snapshots cannot be nested.
452 class Snapshot : protected Parent::NodeNotifier::ObserverBase,
453 protected Parent::EdgeNotifier::ObserverBase
457 class UnsupportedOperation : public LogicError {
459 virtual const char* exceptionName() const {
460 return "lemon::ListGraph::Snapshot::UnsupportedOperation";
468 std::list<Node> added_nodes;
469 std::list<Edge> added_edges;
472 virtual void add(const Node& n) {
473 added_nodes.push_back(n);
475 virtual void erase(const Node&)
477 throw UnsupportedOperation();
479 virtual void add(const Edge& n) {
480 added_edges.push_back(n);
482 virtual void erase(const Edge&)
484 throw UnsupportedOperation();
487 ///\bug What is this used for?
489 virtual void build() {}
490 ///\bug What is this used for?
492 virtual void clear() {}
494 void regist(ListGraph &_g) {
496 Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
497 Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
501 Parent::NodeNotifier::ObserverBase::detach();
502 Parent::EdgeNotifier::ObserverBase::detach();
507 ///Default constructur.
509 ///Default constructur.
510 ///To actually make a snapshot you must call save().
513 ///Constructor that immediately makes a snapshot.
515 ///This constructor immediately makes a snapshot of the graph.
516 ///\param _g The graph we make a snapshot of.
517 Snapshot(ListGraph &_g) {
520 ///\bug Is it necessary?
529 ///Make a snapshot of the graph.
531 ///This function can be called more than once. In case of a repeated
532 ///call, the previous snapshot gets lost.
533 ///\param _g The graph we make the snapshot of.
534 void save(ListGraph &_g)
544 ///Undo the changes until the last snapshot.
546 ///Undo the changes until last snapshot created by save().
548 ///\todo This function might be called undo().
552 while(!added_edges.empty()) {
553 old_g.erase(added_edges.front());
554 added_edges.pop_front();
556 while(!added_nodes.empty()) {
557 old_g.erase(added_nodes.front());
558 added_nodes.pop_front();
567 /**************** Undirected List Graph ****************/
569 typedef UGraphExtender<UGraphBaseExtender<
570 ListGraphBase> > ExtendedListUGraphBase;
572 /// \addtogroup graphs
575 ///An undirected list graph class.
577 ///This is a simple and fast erasable undirected graph implementation.
579 ///It conforms to the
580 ///\ref concept::UGraph "UGraph" concept.
582 ///\sa concept::UGraph.
584 ///\todo Snapshot, reverseEdge(), changeTarget(), changeSource(), contract()
585 ///haven't been implemented yet.
587 class ListUGraph : public ExtendedListUGraphBase {
589 typedef ExtendedListUGraphBase Parent;
590 /// \brief Changes the target of \c e to \c n
592 /// Changes the target of \c e to \c n
594 /// \note The <tt>Edge</tt>'s and <tt>OutEdge</tt>'s
595 /// referencing the changed edge remain
596 /// valid. However <tt>InEdge</tt>'s are invalidated.
597 void changeTarget(UEdge e, Node n) {
600 /// Changes the source of \c e to \c n
602 /// Changes the source of \c e to \c n
604 ///\note The <tt>Edge</tt>'s and <tt>InEdge</tt>'s
605 ///referencing the changed edge remain
606 ///valid. However <tt>OutEdge</tt>'s are invalidated.
607 void changeSource(UEdge e, Node n) {
610 /// \brief Contract two nodes.
612 /// This function contracts two nodes.
614 /// Node \p b will be removed but instead of deleting
615 /// its neighboring edges, they will be joined to \p a.
616 /// The last parameter \p r controls whether to remove loops. \c true
617 /// means that loops will be removed.
619 /// \note The <tt>Edge</tt>s
620 /// referencing a moved edge remain
622 void contract(Node a, Node b, bool r = true) {
623 for(IncEdgeIt e(*this, b); e!=INVALID;) {
624 IncEdgeIt f = e; ++f;
625 if (r && runningNode(e) == a) {
627 } else if (source(e) == b) {
639 class ListBpUGraphBase {
642 class NodeSetError : public LogicError {
643 virtual const char* exceptionName() const {
644 return "lemon::ListBpUGraph::NodeSetError";
651 int first_edge, next_node;
655 int aNode, prev_out, next_out;
656 int bNode, prev_in, next_in;
659 std::vector<NodeT> aNodes;
660 std::vector<NodeT> bNodes;
662 std::vector<EdgeT> edges;
665 int first_free_anode;
668 int first_free_bnode;
675 friend class ListBpUGraphBase;
679 explicit Node(int _id) : id(_id) {}
682 Node(Invalid) { id = -1; }
683 bool operator==(const Node i) const {return id==i.id;}
684 bool operator!=(const Node i) const {return id!=i.id;}
685 bool operator<(const Node i) const {return id<i.id;}
689 friend class ListBpUGraphBase;
693 explicit Edge(int _id) { id = _id;}
696 Edge (Invalid) { id = -1; }
697 bool operator==(const Edge i) const {return id==i.id;}
698 bool operator!=(const Edge i) const {return id!=i.id;}
699 bool operator<(const Edge i) const {return id<i.id;}
703 : first_anode(-1), first_free_anode(-1),
704 first_bnode(-1), first_free_bnode(-1),
705 first_free_edge(-1) {}
707 void firstANode(Node& node) const {
708 node.id = first_anode != -1 ? (first_anode << 1) : -1;
710 void nextANode(Node& node) const {
711 node.id = aNodes[node.id >> 1].next_node;
714 void firstBNode(Node& node) const {
715 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
717 void nextBNode(Node& node) const {
718 node.id = bNodes[node.id >> 1].next_node;
721 void first(Node& node) const {
722 if (first_anode != -1) {
723 node.id = (first_anode << 1);
724 } else if (first_bnode != -1) {
725 node.id = (first_bnode << 1) + 1;
730 void next(Node& node) const {
732 node.id = aNodes[node.id >> 1].next_node;
734 if (first_bnode != -1) {
735 node.id = (first_bnode << 1) + 1;
739 node.id = bNodes[node.id >> 1].next_node;
743 void first(Edge& edge) const {
744 int aNodeId = first_anode;
745 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
746 aNodeId = aNodes[aNodeId].next_node != -1 ?
747 aNodes[aNodeId].next_node >> 1 : -1;
750 edge.id = aNodes[aNodeId].first_edge;
755 void next(Edge& edge) const {
756 int aNodeId = edges[edge.id].aNode >> 1;
757 edge.id = edges[edge.id].next_out;
759 aNodeId = aNodes[aNodeId].next_node != -1 ?
760 aNodes[aNodeId].next_node >> 1 : -1;
761 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
762 aNodeId = aNodes[aNodeId].next_node != -1 ?
763 aNodes[aNodeId].next_node >> 1 : -1;
766 edge.id = aNodes[aNodeId].first_edge;
773 void firstOut(Edge& edge, const Node& node) const {
774 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
775 edge.id = aNodes[node.id >> 1].first_edge;
777 void nextOut(Edge& edge) const {
778 edge.id = edges[edge.id].next_out;
781 void firstIn(Edge& edge, const Node& node) const {
782 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
783 edge.id = bNodes[node.id >> 1].first_edge;
785 void nextIn(Edge& edge) const {
786 edge.id = edges[edge.id].next_in;
789 static int id(const Node& node) {
792 static Node nodeFromId(int id) {
795 int maxNodeId() const {
796 return aNodes.size() > bNodes.size() ?
797 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
800 static int id(const Edge& edge) {
803 static Edge edgeFromId(int id) {
806 int maxEdgeId() const {
810 static int aNodeId(const Node& node) {
813 static Node fromANodeId(int id) {
814 return Node(id << 1);
816 int maxANodeId() const {
817 return aNodes.size();
820 static int bNodeId(const Node& node) {
823 static Node fromBNodeId(int id) {
824 return Node((id << 1) + 1);
826 int maxBNodeId() const {
827 return bNodes.size();
830 Node aNode(const Edge& edge) const {
831 return Node(edges[edge.id].aNode);
833 Node bNode(const Edge& edge) const {
834 return Node(edges[edge.id].bNode);
837 static bool aNode(const Node& node) {
838 return (node.id & 1) == 0;
841 static bool bNode(const Node& node) {
842 return (node.id & 1) == 1;
847 if (first_free_anode == -1) {
848 aNodeId = aNodes.size();
849 aNodes.push_back(NodeT());
851 aNodeId = first_free_anode;
852 first_free_anode = aNodes[first_free_anode].next_node;
854 aNodes[aNodeId].next_node =
855 first_anode != -1 ? (first_anode << 1) : -1;
856 first_anode = aNodeId;
857 aNodes[aNodeId].first_edge = -1;
858 return Node(aNodeId << 1);
863 if (first_free_bnode == -1) {
864 bNodeId = bNodes.size();
865 bNodes.push_back(NodeT());
867 bNodeId = first_free_bnode;
868 first_free_bnode = bNodes[first_free_bnode].next_node;
870 bNodes[bNodeId].next_node =
871 first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
872 first_bnode = bNodeId;
873 bNodes[bNodeId].first_edge = -1;
874 return Node((bNodeId << 1) + 1);
877 Edge addEdge(const Node& source, const Node& target) {
878 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
880 if (first_free_edge != -1) {
881 edgeId = first_free_edge;
882 first_free_edge = edges[edgeId].next_out;
884 edgeId = edges.size();
885 edges.push_back(EdgeT());
887 if ((source.id & 1) == 0) {
888 edges[edgeId].aNode = source.id;
889 edges[edgeId].bNode = target.id;
891 edges[edgeId].aNode = target.id;
892 edges[edgeId].bNode = source.id;
894 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
895 edges[edgeId].prev_out = -1;
896 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
897 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
899 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
900 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
901 edges[edgeId].prev_in = -1;
902 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
903 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
905 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
909 void erase(const Node& node) {
911 int aNodeId = node.id >> 1;
912 aNodes[aNodeId].next_node = first_free_anode;
913 first_free_anode = aNodeId;
915 int bNodeId = node.id >> 1;
916 bNodes[bNodeId].next_node = first_free_bnode;
917 first_free_bnode = bNodeId;
921 void erase(const Edge& edge) {
922 if (edges[edge.id].prev_out != -1) {
923 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
925 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out;
927 if (edges[edge.id].next_out != -1) {
928 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
930 if (edges[edge.id].prev_in != -1) {
931 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
933 bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in;
935 if (edges[edge.id].next_in != -1) {
936 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
938 edges[edge.id].next_out = first_free_edge;
939 first_free_edge = edge.id;
947 first_free_anode = -1;
949 first_free_bnode = -1;
950 first_free_edge = -1;
956 typedef BpUGraphExtender< BpUGraphBaseExtender<
957 ListBpUGraphBase> > ExtendedListBpUGraphBase;
961 /// \brief A smart bipartite undirected graph class.
963 /// This is a bipartite undirected graph implementation.
964 /// It is conforms to the \ref concept::ErasableBpUGraph "ErasableBpUGraph"
966 /// \sa concept::BpUGraph.
968 class ListBpUGraph : public ExtendedListBpUGraphBase {};