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 /// Adds a new node to the graph.
171 /// \warning It adds the new node to the front of the list.
172 /// (i.e. the lastly added node becomes the first.)
176 if(first_free_node==-1) {
178 nodes.push_back(NodeT());
181 first_free_node = nodes[n].next;
184 nodes[n].next = first_node;
185 if(first_node != -1) nodes[first_node].prev = n;
189 nodes[n].first_in = nodes[n].first_out = -1;
194 Edge addEdge(Node u, Node v) {
197 if (first_free_edge == -1) {
199 edges.push_back(EdgeT());
202 first_free_edge = edges[n].next_in;
205 edges[n].source = u.id;
206 edges[n].target = v.id;
208 edges[n].next_out = nodes[u.id].first_out;
209 if(nodes[u.id].first_out != -1) {
210 edges[nodes[u.id].first_out].prev_out = n;
213 edges[n].next_in = nodes[v.id].first_in;
214 if(nodes[v.id].first_in != -1) {
215 edges[nodes[v.id].first_in].prev_in = n;
218 edges[n].prev_in = edges[n].prev_out = -1;
220 nodes[u.id].first_out = nodes[v.id].first_in = n;
225 void erase(const Node& node) {
228 if(nodes[n].next != -1) {
229 nodes[nodes[n].next].prev = nodes[n].prev;
232 if(nodes[n].prev != -1) {
233 nodes[nodes[n].prev].next = nodes[n].next;
235 first_node = nodes[n].next;
238 nodes[n].next = first_free_node;
243 void erase(const Edge& edge) {
246 if(edges[n].next_in!=-1) {
247 edges[edges[n].next_in].prev_in = edges[n].prev_in;
250 if(edges[n].prev_in!=-1) {
251 edges[edges[n].prev_in].next_in = edges[n].next_in;
253 nodes[edges[n].target].first_in = edges[n].next_in;
257 if(edges[n].next_out!=-1) {
258 edges[edges[n].next_out].prev_out = edges[n].prev_out;
261 if(edges[n].prev_out!=-1) {
262 edges[edges[n].prev_out].next_out = edges[n].next_out;
264 nodes[edges[n].source].first_out = edges[n].next_out;
267 edges[n].next_in = first_free_edge;
275 first_node = first_free_node = first_free_edge = -1;
279 void changeTarget(Edge e, Node n)
281 if(edges[e.id].next_in != -1)
282 edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
283 if(edges[e.id].prev_in != -1)
284 edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
285 else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
286 if (nodes[n.id].first_in != -1) {
287 edges[nodes[n.id].first_in].prev_in = e.id;
289 edges[e.id].target = n.id;
290 edges[e.id].prev_in = -1;
291 edges[e.id].next_in = nodes[n.id].first_in;
292 nodes[n.id].first_in = e.id;
294 void changeSource(Edge e, Node n)
296 if(edges[e.id].next_out != -1)
297 edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
298 if(edges[e.id].prev_out != -1)
299 edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
300 else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
301 if (nodes[n.id].first_out != -1) {
302 edges[nodes[n.id].first_out].prev_out = e.id;
304 edges[e.id].source = n.id;
305 edges[e.id].prev_out = -1;
306 edges[e.id].next_out = nodes[n.id].first_out;
307 nodes[n.id].first_out = e.id;
312 typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
314 /// \addtogroup graphs
317 ///A list graph class.
319 ///This is a simple and fast graph implementation.
321 ///It conforms to the \ref concept::Graph "Graph concept" and it
322 ///also provides several additional useful extra functionalities.
323 ///The most of the member functions and nested classes are
324 ///documented only in the concept class.
325 ///\sa concept::Graph.
327 class ListGraph : public ExtendedListGraphBase {
329 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
331 ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
333 ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
334 ///\brief Assignment of ListGraph to another one is \e not allowed.
335 ///Use GraphCopy() instead.
337 ///Assignment of ListGraph to another one is \e not allowed.
338 ///Use GraphCopy() instead.
339 void operator=(const ListGraph &) {}
342 typedef ExtendedListGraphBase Parent;
350 ///Add a new node to the graph.
352 /// \return the new node.
354 Node addNode() { return Parent::addNode(); }
356 ///Add a new edge to the graph.
358 ///Add a new edge to the graph with source node \c s
359 ///and target node \c t.
360 ///\return the new edge.
361 Edge addEdge(const Node& s, const Node& t) {
362 return Parent::addEdge(s, t);
365 /// Changes the target of \c e to \c n
367 /// Changes the target of \c e to \c n
369 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
370 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
372 ///\warning This functionality cannot be used together with the Snapshot
374 void changeTarget(Edge e, Node n) {
375 Parent::changeTarget(e,n);
377 /// Changes the source of \c e to \c n
379 /// Changes the source of \c e to \c n
381 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
382 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
384 ///\warning This functionality cannot be used together with the Snapshot
386 void changeSource(Edge e, Node n) {
387 Parent::changeSource(e,n);
390 /// Invert the direction of an edge.
392 ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
393 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
395 ///\warning This functionality cannot be used together with the Snapshot
397 void reverseEdge(Edge e) {
399 changeTarget(e,source(e));
403 /// \brief Using this it is possible to avoid the superfluous memory
406 ///Using this it is possible to avoid the superfluous memory
407 ///allocation: if you know that the graph you want to build will
408 ///contain at least 10 million nodes then it is worth reserving
409 ///space for this amount before starting to build the graph.
410 void reserveNode(int n) { nodes.reserve(n); };
412 /// \brief Using this it is possible to avoid the superfluous memory
415 ///Using this it is possible to avoid the superfluous memory
416 ///allocation: see the \ref reserveNode function.
417 void reserveEdge(int n) { edges.reserve(n); };
420 ///Contract two nodes.
422 ///This function contracts two nodes.
424 ///Node \p b will be removed but instead of deleting
425 ///incident edges, they will be joined to \p a.
426 ///The last parameter \p r controls whether to remove loops. \c true
427 ///means that loops will be removed.
429 ///\note The <tt>EdgeIt</tt>s
430 ///referencing a moved edge remain
431 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
432 ///may be invalidated.
433 ///\warning This functionality cannot be used together with the Snapshot
435 void contract(Node a, Node b, bool r = true)
437 for(OutEdgeIt e(*this,b);e!=INVALID;) {
440 if(r && target(e)==a) erase(e);
441 else changeSource(e,a);
444 for(InEdgeIt e(*this,b);e!=INVALID;) {
447 if(r && source(e)==a) erase(e);
448 else changeTarget(e,a);
456 ///This function splits a node. First a new node is added to the graph,
457 ///then the source of each outgoing edge of \c n is moved to this new node.
458 ///If \c connect is \c true (this is the default value), then a new edge
459 ///from \c n to the newly created node is also added.
460 ///\return The newly created node.
462 ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
463 ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
466 ///\warning This functionality cannot be used together with the
467 ///Snapshot feature. \todo It could be implemented in a bit
469 Node split(Node n, bool connect = true) {
471 for(OutEdgeIt e(*this,n);e!=INVALID;) {
477 if (connect) addEdge(n,b);
483 ///This function splits an edge. First a new node \c b is added to
484 ///the graph, then the original edge is re-targeted to \c
485 ///b. Finally an edge from \c b to the original target is added.
486 ///\return The newly created node.
487 ///\warning This functionality
488 ///cannot be used together with the Snapshot feature.
491 addEdge(b,target(e));
496 /// \brief Class to make a snapshot of the graph and restore
499 /// Class to make a snapshot of the graph and to restore it
502 /// The newly added nodes and edges can be removed using the
503 /// restore() function.
505 /// \warning Edge and node deletions cannot be restored.
509 class UnsupportedOperation : public LogicError {
511 virtual const char* what() const throw() {
512 return "lemon::ListGraph::Snapshot::UnsupportedOperation";
519 typedef Parent::NodeNotifier NodeNotifier;
521 class NodeObserverProxy : public NodeNotifier::ObserverBase {
524 NodeObserverProxy(Snapshot& _snapshot)
525 : snapshot(_snapshot) {}
527 using NodeNotifier::ObserverBase::attach;
528 using NodeNotifier::ObserverBase::detach;
529 using NodeNotifier::ObserverBase::attached;
533 virtual void add(const Node& node) {
534 snapshot.addNode(node);
536 virtual void add(const std::vector<Node>& nodes) {
537 for (int i = nodes.size() - 1; i >= 0; ++i) {
538 snapshot.addNode(nodes[i]);
541 virtual void erase(const Node& node) {
542 snapshot.eraseNode(node);
544 virtual void erase(const std::vector<Node>& nodes) {
545 for (int i = 0; i < (int)nodes.size(); ++i) {
546 if (!snapshot.eraseNode(nodes[i])) break;
549 virtual void build() {
550 NodeNotifier* notifier = getNotifier();
552 std::vector<Node> nodes;
553 for (notifier->first(node); node != INVALID; notifier->next(node)) {
554 nodes.push_back(node);
556 for (int i = nodes.size() - 1; i >= 0; --i) {
557 snapshot.addNode(nodes[i]);
560 virtual void clear() {
561 NodeNotifier* notifier = getNotifier();
563 for (notifier->first(node); node != INVALID; notifier->next(node)) {
564 if (!snapshot.eraseNode(node)) break;
571 class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
574 EdgeObserverProxy(Snapshot& _snapshot)
575 : snapshot(_snapshot) {}
577 using EdgeNotifier::ObserverBase::attach;
578 using EdgeNotifier::ObserverBase::detach;
579 using EdgeNotifier::ObserverBase::attached;
583 virtual void add(const Edge& edge) {
584 snapshot.addEdge(edge);
586 virtual void add(const std::vector<Edge>& edges) {
587 for (int i = edges.size() - 1; i >= 0; ++i) {
588 snapshot.addEdge(edges[i]);
591 virtual void erase(const Edge& edge) {
592 snapshot.eraseEdge(edge);
594 virtual void erase(const std::vector<Edge>& edges) {
595 for (int i = 0; i < (int)edges.size(); ++i) {
596 if (!snapshot.eraseEdge(edges[i])) break;
599 virtual void build() {
600 EdgeNotifier* notifier = getNotifier();
602 std::vector<Edge> edges;
603 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
604 edges.push_back(edge);
606 for (int i = edges.size() - 1; i >= 0; --i) {
607 snapshot.addEdge(edges[i]);
610 virtual void clear() {
611 EdgeNotifier* notifier = getNotifier();
613 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
614 if (!snapshot.eraseEdge(edge)) break;
623 NodeObserverProxy node_observer_proxy;
624 EdgeObserverProxy edge_observer_proxy;
626 std::list<Node> added_nodes;
627 std::list<Edge> added_edges;
630 void addNode(const Node& node) {
631 added_nodes.push_front(node);
633 bool eraseNode(const Node& node) {
634 std::list<Node>::iterator it =
635 std::find(added_nodes.begin(), added_nodes.end(), node);
636 if (it == added_nodes.end()) {
640 added_nodes.erase(it);
645 void addEdge(const Edge& edge) {
646 added_edges.push_front(edge);
648 bool eraseEdge(const Edge& edge) {
649 std::list<Edge>::iterator it =
650 std::find(added_edges.begin(), added_edges.end(), edge);
651 if (it == added_edges.end()) {
655 added_edges.erase(it);
660 void attach(ListGraph &_graph) {
662 node_observer_proxy.attach(graph->getNotifier(Node()));
663 edge_observer_proxy.attach(graph->getNotifier(Edge()));
667 node_observer_proxy.detach();
668 edge_observer_proxy.detach();
679 /// \brief Default constructor.
681 /// Default constructor.
682 /// To actually make a snapshot you must call save().
684 : graph(0), node_observer_proxy(*this),
685 edge_observer_proxy(*this) {}
687 /// \brief Constructor that immediately makes a snapshot.
689 /// This constructor immediately makes a snapshot of the graph.
690 /// \param _graph The graph we make a snapshot of.
691 Snapshot(ListGraph &_graph)
692 : node_observer_proxy(*this),
693 edge_observer_proxy(*this) {
697 /// \brief Make a snapshot.
699 /// Make a snapshot of the graph.
701 /// This function can be called more than once. In case of a repeated
702 /// call, the previous snapshot gets lost.
703 /// \param _graph The graph we make the snapshot of.
704 void save(ListGraph &_graph) {
709 /// \brief Undo the changes until the last snapshot.
711 /// Undo the changes until the last snapshot created by save().
714 while(!added_edges.empty()) {
715 graph->erase(added_edges.front());
716 added_edges.pop_front();
718 while(!added_nodes.empty()) {
719 graph->erase(added_nodes.front());
720 added_nodes.pop_front();
724 /// \brief Gives back true when the snapshot is valid.
726 /// Gives back true when the snapshot is valid.
728 return node_observer_proxy.attached();
736 /**************** Undirected List Graph ****************/
738 typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
739 ExtendedListUGraphBase;
741 /// \addtogroup graphs
744 ///An undirected list graph class.
746 ///This is a simple and fast undirected graph implementation.
748 ///It conforms to the
749 ///\ref concept::UGraph "UGraph concept".
751 ///\sa concept::UGraph.
753 class ListUGraph : public ExtendedListUGraphBase {
755 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
757 ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
759 ListUGraph(const ListUGraph &) :ExtendedListUGraphBase() {};
760 ///\brief Assignment of ListUGraph to another one is \e not allowed.
761 ///Use UGraphCopy() instead.
763 ///Assignment of ListUGraph to another one is \e not allowed.
764 ///Use UGraphCopy() instead.
765 void operator=(const ListUGraph &) {}
773 typedef ExtendedListUGraphBase Parent;
774 /// \brief Add a new node to the graph.
776 /// \return the new node.
778 Node addNode() { return Parent::addNode(); }
780 /// \brief Add a new edge to the graph.
782 /// Add a new edge to the graph with source node \c s
783 /// and target node \c t.
784 /// \return the new undirected edge.
785 UEdge addEdge(const Node& s, const Node& t) {
786 return Parent::addEdge(s, t);
788 /// \brief Changes the source of \c e to \c n
790 /// Changes the source of \c e to \c n
792 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
793 ///referencing the changed edge remain
794 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
795 void changeSource(UEdge e, Node n) {
796 Parent::changeSource(e,n);
798 /// \brief Changes the target of \c e to \c n
800 /// Changes the target of \c e to \c n
802 /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
803 /// valid. However the other iterators may be invalidated.
804 void changeTarget(UEdge e, Node n) {
805 Parent::changeTarget(e,n);
807 /// \brief Changes the source of \c e to \c n
809 /// Changes the source of \c e to \c n. It changes the proper
810 /// node of the represented undirected edge.
812 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
813 ///referencing the changed edge remain
814 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
815 void changeSource(Edge e, Node n) {
816 if (Parent::direction(e)) {
817 Parent::changeSource(e,n);
819 Parent::changeTarget(e,n);
822 /// \brief Changes the target of \c e to \c n
824 /// Changes the target of \c e to \c n. It changes the proper
825 /// node of the represented undirected edge.
827 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
828 ///referencing the changed edge remain
829 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
830 void changeTarget(Edge e, Node n) {
831 if (Parent::direction(e)) {
832 Parent::changeTarget(e,n);
834 Parent::changeSource(e,n);
837 /// \brief Contract two nodes.
839 /// This function contracts two nodes.
841 /// Node \p b will be removed but instead of deleting
842 /// its neighboring edges, they will be joined to \p a.
843 /// The last parameter \p r controls whether to remove loops. \c true
844 /// means that loops will be removed.
846 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
848 void contract(Node a, Node b, bool r = true) {
849 for(IncEdgeIt e(*this, b); e!=INVALID;) {
850 IncEdgeIt f = e; ++f;
851 if (r && runningNode(e) == a) {
853 } else if (source(e) == b) {
865 class ListBpUGraphBase {
868 class NodeSetError : public LogicError {
870 virtual const char* what() const throw() {
871 return "lemon::ListBpUGraph::NodeSetError";
878 int first_edge, prev, next;
882 int aNode, prev_out, next_out;
883 int bNode, prev_in, next_in;
886 std::vector<NodeT> aNodes;
887 std::vector<NodeT> bNodes;
889 std::vector<UEdgeT> edges;
892 int first_free_anode;
895 int first_free_bnode;
902 friend class ListBpUGraphBase;
906 explicit Node(int _id) : id(_id) {}
909 Node(Invalid) { id = -1; }
910 bool operator==(const Node i) const {return id==i.id;}
911 bool operator!=(const Node i) const {return id!=i.id;}
912 bool operator<(const Node i) const {return id<i.id;}
916 friend class ListBpUGraphBase;
920 explicit UEdge(int _id) { id = _id;}
923 UEdge (Invalid) { id = -1; }
924 bool operator==(const UEdge i) const {return id==i.id;}
925 bool operator!=(const UEdge i) const {return id!=i.id;}
926 bool operator<(const UEdge i) const {return id<i.id;}
930 : first_anode(-1), first_free_anode(-1),
931 first_bnode(-1), first_free_bnode(-1),
932 first_free_edge(-1) {}
934 void firstANode(Node& node) const {
935 node.id = first_anode != -1 ? (first_anode << 1) : -1;
937 void nextANode(Node& node) const {
938 node.id = aNodes[node.id >> 1].next;
941 void firstBNode(Node& node) const {
942 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
944 void nextBNode(Node& node) const {
945 node.id = bNodes[node.id >> 1].next;
948 void first(Node& node) const {
949 if (first_anode != -1) {
950 node.id = (first_anode << 1);
951 } else if (first_bnode != -1) {
952 node.id = (first_bnode << 1) + 1;
957 void next(Node& node) const {
959 node.id = aNodes[node.id >> 1].next;
961 if (first_bnode != -1) {
962 node.id = (first_bnode << 1) + 1;
966 node.id = bNodes[node.id >> 1].next;
970 void first(UEdge& edge) const {
971 int aNodeId = first_anode;
972 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
973 aNodeId = aNodes[aNodeId].next != -1 ?
974 aNodes[aNodeId].next >> 1 : -1;
977 edge.id = aNodes[aNodeId].first_edge;
982 void next(UEdge& edge) const {
983 int aNodeId = edges[edge.id].aNode >> 1;
984 edge.id = edges[edge.id].next_out;
986 aNodeId = aNodes[aNodeId].next != -1 ?
987 aNodes[aNodeId].next >> 1 : -1;
988 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
989 aNodeId = aNodes[aNodeId].next != -1 ?
990 aNodes[aNodeId].next >> 1 : -1;
993 edge.id = aNodes[aNodeId].first_edge;
1000 void firstFromANode(UEdge& edge, const Node& node) const {
1001 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1002 edge.id = aNodes[node.id >> 1].first_edge;
1004 void nextFromANode(UEdge& edge) const {
1005 edge.id = edges[edge.id].next_out;
1008 void firstFromBNode(UEdge& edge, const Node& node) const {
1009 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1010 edge.id = bNodes[node.id >> 1].first_edge;
1012 void nextFromBNode(UEdge& edge) const {
1013 edge.id = edges[edge.id].next_in;
1016 static int id(const Node& node) {
1019 static Node nodeFromId(int id) {
1022 int maxNodeId() const {
1023 return aNodes.size() > bNodes.size() ?
1024 aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
1027 static int id(const UEdge& edge) {
1030 static UEdge uEdgeFromId(int id) {
1033 int maxUEdgeId() const {
1034 return edges.size();
1037 static int aNodeId(const Node& node) {
1038 return node.id >> 1;
1040 static Node fromANodeId(int id) {
1041 return Node(id << 1);
1043 int maxANodeId() const {
1044 return aNodes.size();
1047 static int bNodeId(const Node& node) {
1048 return node.id >> 1;
1050 static Node fromBNodeId(int id) {
1051 return Node((id << 1) + 1);
1053 int maxBNodeId() const {
1054 return bNodes.size();
1057 Node aNode(const UEdge& edge) const {
1058 return Node(edges[edge.id].aNode);
1060 Node bNode(const UEdge& edge) const {
1061 return Node(edges[edge.id].bNode);
1064 static bool aNode(const Node& node) {
1065 return (node.id & 1) == 0;
1068 static bool bNode(const Node& node) {
1069 return (node.id & 1) == 1;
1074 if (first_free_anode == -1) {
1075 aNodeId = aNodes.size();
1076 aNodes.push_back(NodeT());
1078 aNodeId = first_free_anode;
1079 first_free_anode = aNodes[first_free_anode].next;
1081 if (first_anode != -1) {
1082 aNodes[aNodeId].next = first_anode << 1;
1083 aNodes[first_anode].prev = aNodeId << 1;
1085 aNodes[aNodeId].next = -1;
1087 aNodes[aNodeId].prev = -1;
1088 first_anode = aNodeId;
1089 aNodes[aNodeId].first_edge = -1;
1090 return Node(aNodeId << 1);
1095 if (first_free_bnode == -1) {
1096 bNodeId = bNodes.size();
1097 bNodes.push_back(NodeT());
1099 bNodeId = first_free_bnode;
1100 first_free_bnode = bNodes[first_free_bnode].next;
1102 if (first_bnode != -1) {
1103 bNodes[bNodeId].next = (first_bnode << 1) + 1;
1104 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
1106 bNodes[bNodeId].next = -1;
1108 first_bnode = bNodeId;
1109 bNodes[bNodeId].first_edge = -1;
1110 return Node((bNodeId << 1) + 1);
1113 UEdge addEdge(const Node& source, const Node& target) {
1114 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
1116 if (first_free_edge != -1) {
1117 edgeId = first_free_edge;
1118 first_free_edge = edges[edgeId].next_out;
1120 edgeId = edges.size();
1121 edges.push_back(UEdgeT());
1123 if ((source.id & 1) == 0) {
1124 edges[edgeId].aNode = source.id;
1125 edges[edgeId].bNode = target.id;
1127 edges[edgeId].aNode = target.id;
1128 edges[edgeId].bNode = source.id;
1130 edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
1131 edges[edgeId].prev_out = -1;
1132 if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
1133 edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
1135 aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
1136 edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
1137 edges[edgeId].prev_in = -1;
1138 if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
1139 edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
1141 bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
1142 return UEdge(edgeId);
1145 void erase(const Node& node) {
1147 int aNodeId = node.id >> 1;
1148 if (aNodes[aNodeId].prev != -1) {
1149 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
1151 first_anode = aNodes[aNodeId].next >> 1;
1153 if (aNodes[aNodeId].next != -1) {
1154 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
1156 aNodes[aNodeId].next = first_free_anode;
1157 first_free_anode = aNodeId;
1159 int bNodeId = node.id >> 1;
1160 if (bNodes[bNodeId].prev != -1) {
1161 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
1163 first_bnode = bNodes[bNodeId].next >> 1;
1165 if (bNodes[bNodeId].next != -1) {
1166 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
1168 bNodes[bNodeId].next = first_free_bnode;
1169 first_free_bnode = bNodeId;
1173 void erase(const UEdge& edge) {
1175 if (edges[edge.id].prev_out != -1) {
1176 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1178 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1180 if (edges[edge.id].next_out != -1) {
1181 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1184 if (edges[edge.id].prev_in != -1) {
1185 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1187 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1189 if (edges[edge.id].next_in != -1) {
1190 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1193 edges[edge.id].next_out = first_free_edge;
1194 first_free_edge = edge.id;
1202 first_free_anode = -1;
1204 first_free_bnode = -1;
1205 first_free_edge = -1;
1208 void changeANode(const UEdge& edge, const Node& node) {
1209 LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
1210 if (edges[edge.id].prev_out != -1) {
1211 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
1213 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
1215 if (edges[edge.id].next_out != -1) {
1216 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
1218 if (aNodes[node.id >> 1].first_edge != -1) {
1219 edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
1221 edges[edge.id].prev_out = -1;
1222 edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
1223 aNodes[node.id >> 1].first_edge = edge.id;
1224 edges[edge.id].aNode = node.id;
1227 void changeBNode(const UEdge& edge, const Node& node) {
1228 LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
1229 if (edges[edge.id].prev_in != -1) {
1230 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
1232 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
1234 if (edges[edge.id].next_in != -1) {
1235 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
1237 if (bNodes[node.id >> 1].first_edge != -1) {
1238 edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
1240 edges[edge.id].prev_in = -1;
1241 edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
1242 bNodes[node.id >> 1].first_edge = edge.id;
1243 edges[edge.id].bNode = node.id;
1249 typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
1253 /// \brief A smart bipartite undirected graph class.
1255 /// This is a bipartite undirected graph implementation.
1256 /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
1257 /// \sa concept::BpUGraph.
1259 class ListBpUGraph : public ExtendedListBpUGraphBase {
1260 /// \brief ListBpUGraph is \e not copy constructible.
1262 ///ListBpUGraph is \e not copy constructible.
1263 ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase() {};
1264 /// \brief Assignment of ListBpUGraph to another one is \e not
1267 /// Assignment of ListBpUGraph to another one is \e not allowed.
1268 void operator=(const ListBpUGraph &) {}
1270 /// \brief Constructor
1276 typedef ExtendedListBpUGraphBase Parent;
1277 /// \brief Add a new ANode to the graph.
1279 /// \return the new node.
1281 Node addANode() { return Parent::addANode(); }
1283 /// \brief Add a new BNode to the graph.
1285 /// \return the new node.
1287 Node addBNode() { return Parent::addBNode(); }
1289 /// \brief Add a new edge to the graph.
1291 /// Add a new edge to the graph with an ANode and a BNode.
1292 /// \return the new undirected edge.
1293 UEdge addEdge(const Node& s, const Node& t) {
1294 return Parent::addEdge(s, t);
1297 /// \brief Changes the ANode of \c e to \c n
1299 /// Changes the ANode of \c e to \c n
1301 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1302 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1304 void changeANode(UEdge e, Node n) {
1305 Parent::changeANode(e,n);
1308 /// \brief Changes the BNode of \c e to \c n
1310 /// Changes the BNode of \c e to \c n
1312 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1313 /// referencing the changed edge remain
1314 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1315 void changeBNode(UEdge e, Node n) {
1316 Parent::changeBNode(e,n);
1319 /// \brief Changes the source(ANode) of \c e to \c n
1321 /// Changes the source(ANode) of \c e to \c n
1323 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
1324 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1326 void changeSource(UEdge e, Node n) {
1327 Parent::changeANode(e,n);
1330 /// \brief Changes the target(BNode) of \c e to \c n
1332 /// Changes the target(BNode) of \c e to \c n
1334 /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1335 /// referencing the changed edge remain
1336 /// valid. However <tt>InEdgeIt</tt>s are invalidated.
1337 void changeTarget(UEdge e, Node n) {
1338 Parent::changeBNode(e,n);
1341 /// \brief Changes the source of \c e to \c n
1343 /// Changes the source of \c e to \c n. It changes the proper
1344 /// node of the represented undirected edge.
1346 ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
1347 ///referencing the changed edge remain
1348 ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
1349 void changeSource(Edge e, Node n) {
1350 if (Parent::direction(e)) {
1351 Parent::changeANode(e,n);
1353 Parent::changeBNode(e,n);
1356 /// \brief Changes the target of \c e to \c n
1358 /// Changes the target of \c e to \c n. It changes the proper
1359 /// node of the represented undirected edge.
1361 ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
1362 ///referencing the changed edge remain
1363 ///valid. However <tt>InEdgeIt</tt>s are invalidated.
1364 void changeTarget(Edge e, Node n) {
1365 if (Parent::direction(e)) {
1366 Parent::changeBNode(e,n);
1368 Parent::changeANode(e,n);
1371 /// \brief Contract two nodes.
1373 /// This function contracts two nodes.
1375 /// Node \p b will be removed but instead of deleting its
1376 /// neighboring edges, they will be joined to \p a. The two nodes
1377 /// should be from the same nodeset, of course.
1379 /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
1381 void contract(const Node& a, const Node& b) {
1382 LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
1383 if (Parent::aNode(a)) {
1384 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1385 IncEdgeIt f = e; ++f;
1390 for (IncEdgeIt e(*this, b); e!=INVALID;) {
1391 IncEdgeIt f = e; ++f;