Unionfind changes induced some bugs here. Also some augmentations made.
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_SUB_GRAPH_H
20 #define LEMON_SUB_GRAPH_H
22 #include <lemon/graph_adaptor.h>
23 #include <lemon/bits/graph_adaptor_extender.h>
24 #include <lemon/bits/default_map.h>
28 /// \brief Base for the SubGraph.
30 /// Base for the SubGraph.
31 template <typename _Graph>
32 class SubGraphBase : public GraphAdaptorBase<const _Graph> {
35 typedef SubGraphBase<_Graph> SubGraph;
36 typedef GraphAdaptorBase<const _Graph> Parent;
39 typedef typename Parent::Node Node;
40 typedef typename Parent::Edge Edge;
50 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
51 Parent::setGraph(_graph);
58 while (node != INVALID) {
59 (*nodes)[node].prev = node;
60 (*nodes)[node].firstIn = INVALID;
61 (*nodes)[node].firstOut = INVALID;
67 while (edge != INVALID) {
68 (*edges)[edge].prevOut = edge;
75 void first(Node& node) const {
78 void next(Node& node) const {
79 node = (*nodes)[node].next;
82 void first(Edge& edge) const {
83 Node node = firstNode;
84 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
85 node = (*nodes)[node].next;
87 if (node == INVALID) {
90 edge = (*nodes)[node].firstOut;
93 void next(Edge& edge) const {
94 if ((*edges)[edge].nextOut != INVALID) {
95 edge = (*edges)[edge].nextOut;
97 Node node = (*nodes)[source(edge)].next;
98 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
99 node = (*nodes)[node].next;
101 if (node == INVALID) {
104 edge = (*nodes)[node].firstOut;
109 void firstOut(Edge& edge, const Node& node) const {
110 edge = (*nodes)[node].firstOut;
112 void nextOut(Edge& edge) const {
113 edge = (*edges)[edge].nextOut;
116 void firstIn(Edge& edge, const Node& node) const {
117 edge = (*nodes)[node].firstIn;
119 void nextIn(Edge& edge) const {
120 edge = (*edges)[edge].nextIn;
123 /// \brief Returns true when the given node is hidden.
125 /// Returns true when the given node is hidden.
126 bool hidden(const Node& node) const {
127 return (*nodes)[node].prev == node;
130 /// \brief Hide the given node in the sub-graph.
132 /// Hide the given node in the sub graph. It just lace out from
133 /// the linked lists the given node. If there are incoming or outgoing
134 /// edges into or from this node then all of these will be hidden.
135 void hide(const Node& node) {
136 if (hidden(node)) return;
138 firstOut(edge, node);
139 while (edge != INVALID) {
141 firstOut(edge, node);
144 firstOut(edge, node);
145 while (edge != INVALID) {
147 firstOut(edge, node);
149 if ((*nodes)[node].prev != INVALID) {
150 (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
152 firstNode = (*nodes)[node].next;
154 if ((*nodes)[node].next != INVALID) {
155 (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
157 (*nodes)[node].prev = node;
158 (*nodes)[node].firstIn = INVALID;
159 (*nodes)[node].firstOut = INVALID;
162 /// \brief Unhide the given node in the sub-graph.
164 /// Unhide the given node in the sub graph. It just lace in the given
165 /// node into the linked lists.
166 void unHide(const Node& node) {
167 if (!hidden(node)) return;
168 (*nodes)[node].next = firstNode;
169 (*nodes)[node].prev = INVALID;
170 if ((*nodes)[node].next != INVALID) {
171 (*nodes)[(*nodes)[node].next].prev = node;
176 /// \brief Returns true when the given edge is hidden.
178 /// Returns true when the given edge is hidden.
179 bool hidden(const Edge& edge) const {
180 return (*edges)[edge].prevOut == edge;
183 /// \brief Hide the given edge in the sub-graph.
185 /// Hide the given edge in the sub graph. It just lace out from
186 /// the linked lists the given edge.
187 void hide(const Edge& edge) {
188 if (hidden(edge)) return;
189 if ((*edges)[edge].prevOut == edge) return;
190 if ((*edges)[edge].prevOut != INVALID) {
191 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
193 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
195 if ((*edges)[edge].nextOut != INVALID) {
196 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
199 if ((*edges)[edge].prevIn != INVALID) {
200 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
202 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
204 if ((*edges)[edge].nextIn != INVALID) {
205 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
207 (*edges)[edge].next = edge;
210 /// \brief Unhide the given edge in the sub-graph.
212 /// Unhide the given edge in the sub graph. It just lace in the given
213 /// edge into the linked lists. If the source or the target of the
214 /// node is hidden then it will unhide it.
215 void unHide(const Edge& edge) {
216 if (!hidden(edge)) return;
220 node = Parent::source(edge);
222 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
223 (*edges)[edge].prevOut = INVALID;
224 if ((*edges)[edge].nextOut != INVALID) {
225 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
227 (*nodes)[node].firstOut = edge;
229 node = Parent::target(edge);
231 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
232 (*edges)[edge].prevIn = INVALID;
233 if ((*edges)[edge].nextIn != INVALID) {
234 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
236 (*nodes)[node].firstIn = edge;
239 typedef False NodeNumTag;
240 typedef False EdgeNumTag;
245 Edge firstIn, firstOut;
247 class NodesImpl : public DefaultMap<Graph, Node, NodeT> {
248 friend class SubGraphBase;
250 typedef DefaultMap<Graph, Node, NodeT> Parent;
252 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
253 : Parent(_graph), adaptor(_adaptor) {}
255 virtual ~NodesImpl() {}
257 virtual void build() {
260 adaptor.Base::first(node);
261 while (node != INVALID) {
262 Parent::operator[](node).prev = node;
263 Parent::operator[](node).firstIn = INVALID;
264 Parent::operator[](node).firstOut = INVALID;
265 adaptor.Base::next(node);
269 virtual void clear() {
270 adaptor.firstNode = INVALID;
274 virtual void add(const Node& node) {
276 Parent::operator[](node).prev = node;
277 Parent::operator[](node).firstIn = INVALID;
278 Parent::operator[](node).firstOut = INVALID;
281 virtual void add(const std::vector<Node>& nodes) {
283 for (int i = 0; i < (int)nodes.size(); ++i) {
284 Parent::operator[](nodes[i]).prev = nodes[i];
285 Parent::operator[](nodes[i]).firstIn = INVALID;
286 Parent::operator[](nodes[i]).firstOut = INVALID;
290 virtual void erase(const Node& node) {
295 virtual void erase(const std::vector<Node>& nodes) {
296 for (int i = 0; i < (int)nodes.size(); ++i) {
297 adaptor.hide(nodes[i]);
299 Parent::erase(nodes);
307 Edge prevOut, nextOut;
310 class EdgesImpl : public DefaultMap<Graph, Edge, EdgeT> {
311 friend class SubGraphBase;
313 typedef DefaultMap<Graph, Edge, EdgeT> Parent;
315 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
316 : Parent(_graph), adaptor(_adaptor) {}
318 virtual ~EdgesImpl() {}
320 virtual void build() {
323 adaptor.Base::first(edge);
324 while (edge != INVALID) {
325 Parent::operator[](edge).prevOut = edge;
326 adaptor.Base::next(edge);
330 virtual void clear() {
333 while (node != INVALID) {
334 (*adaptor.nodes).firstIn = INVALID;
335 (*adaptor.nodes).firstOut = INVALID;
341 virtual void add(const Edge& edge) {
343 Parent::operator[](edge).prevOut = edge;
346 virtual void add(const std::vector<Edge>& edges) {
348 for (int i = 0; i < (int)edges.size(); ++i) {
349 Parent::operator[](edges[i]).prevOut = edges[i];
353 virtual void erase(const Edge& edge) {
358 virtual void erase(const std::vector<Edge>& edges) {
359 for (int i = 0; i < (int)edges.size(); ++i) {
360 adaptor.hide(edges[i]);
362 Parent::erase(edges);
374 /// \ingroup semi_adaptors
376 /// \brief Graph which uses a subset of another graph's nodes and edges.
378 /// Graph which uses a subset of another graph's nodes and edges. This class
379 /// is an alternative to the SubGraphAdaptor which is created for the
380 /// same reason. The main difference between the two class that it
381 /// makes linked lists on the unhidden nodes and edges what cause that
382 /// on sparse subgraphs the algorithms can be more efficient and some times
383 /// provide better time complexity. On other way this implemetation is
384 /// less efficient in most case when the subgraph filters out only
385 /// a few nodes or edges.
387 /// \see SubGraphAdaptor
388 /// \see EdgeSubGraphBase
389 template <typename Graph>
391 : public GraphAdaptorExtender< SubGraphBase<Graph> > {
393 typedef GraphAdaptorExtender< SubGraphBase<Graph> > Parent;
395 /// \brief Constructor for sub-graph.
397 /// Constructor for sub-graph. Initially all the edges and nodes
398 /// are hidden in the graph.
399 SubGraph(const Graph& _graph)
400 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
401 Parent::construct(_graph, nodes, edges);
404 typename Parent::NodesImpl nodes;
405 typename Parent::EdgesImpl edges;
408 /// \brief Base for the EdgeSubGraph.
410 /// Base for the EdgeSubGraph.
411 template <typename _Graph>
412 class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
414 typedef _Graph Graph;
415 typedef EdgeSubGraphBase<_Graph> SubGraph;
416 typedef GraphAdaptorBase<const _Graph> Parent;
419 typedef typename Parent::Node Node;
420 typedef typename Parent::Edge Edge;
428 EdgeSubGraphBase() {}
430 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
431 Parent::setGraph(_graph);
437 while (node != INVALID) {
438 (*nodes)[node].firstIn = INVALID;
439 (*nodes)[node].firstOut = INVALID;
445 while (edge != INVALID) {
446 (*edges)[edge].prevOut = edge;
453 void first(Node& node) const {
456 void next(Node& node) const {
460 void first(Edge& edge) const {
463 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
466 if (node == INVALID) {
469 edge = (*nodes)[node].firstOut;
472 void next(Edge& edge) const {
473 if ((*edges)[edge].nextOut != INVALID) {
474 edge = (*edges)[edge].nextOut;
476 Node node = source(edge);
478 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
481 if (node == INVALID) {
484 edge = (*nodes)[node].firstOut;
489 void firstOut(Edge& edge, const Node& node) const {
490 edge = (*nodes)[node].firstOut;
492 void nextOut(Edge& edge) const {
493 edge = (*edges)[edge].nextOut;
496 void firstIn(Edge& edge, const Node& node) const {
497 edge = (*nodes)[node].firstIn;
499 void nextIn(Edge& edge) const {
500 edge = (*edges)[edge].nextIn;
503 /// \brief Returns true when the given edge is hidden.
505 /// Returns true when the given edge is hidden.
506 bool hidden(const Edge& edge) const {
507 return (*edges)[edge].prevOut == edge;
510 /// \brief Hide the given edge in the sub-graph.
512 /// Hide the given edge in the sub graph. It just lace out from
513 /// the linked lists the given edge.
514 void hide(const Edge& edge) {
515 if (hidden(edge)) return;
516 if ((*edges)[edge].prevOut != INVALID) {
517 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
519 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
521 if ((*edges)[edge].nextOut != INVALID) {
522 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
525 if ((*edges)[edge].prevIn != INVALID) {
526 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
528 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
530 if ((*edges)[edge].nextIn != INVALID) {
531 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
533 (*edges)[edge].prevOut = edge;
536 /// \brief Unhide the given edge in the sub-graph.
538 /// Unhide the given edge in the sub graph. It just lace in the given
539 /// edge into the linked lists.
540 void unHide(const Edge& edge) {
541 if (!hidden(edge)) return;
544 node = Parent::source(edge);
545 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
546 (*edges)[edge].prevOut = INVALID;
547 if ((*edges)[edge].nextOut != INVALID) {
548 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
550 (*nodes)[node].firstOut = edge;
552 node = Parent::target(edge);
553 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
554 (*edges)[edge].prevIn = INVALID;
555 if ((*edges)[edge].nextIn != INVALID) {
556 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
558 (*nodes)[node].firstIn = edge;
563 Edge firstIn, firstOut;
565 class NodesImpl : public DefaultMap<Graph, Node, NodeT> {
566 friend class EdgeSubGraphBase;
568 typedef DefaultMap<Graph, Node, NodeT> Parent;
570 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
571 : Parent(_graph), adaptor(_adaptor) {}
573 virtual ~NodesImpl() {}
575 virtual void build() {
578 adaptor.Base::first(node);
579 while (node != INVALID) {
580 Parent::operator[](node).firstIn = INVALID;
581 Parent::operator[](node).firstOut = INVALID;
582 adaptor.Base::next(node);
586 virtual void add(const Node& node) {
588 Parent::operator[](node).firstIn = INVALID;
589 Parent::operator[](node).firstOut = INVALID;
592 virtual void add(const std::vector<Node>& nodes) {
594 for (int i = 0; i < (int)nodes.size(); ++i) {
595 Parent::operator[](nodes[i]).firstIn = INVALID;
596 Parent::operator[](nodes[i]).firstOut = INVALID;
605 Edge prevOut, nextOut;
608 class EdgesImpl : public DefaultMap<Graph, Edge, EdgeT> {
609 friend class EdgeSubGraphBase;
611 typedef DefaultMap<Graph, Edge, EdgeT> Parent;
613 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
614 : Parent(_graph), adaptor(_adaptor) {}
616 virtual ~EdgesImpl() {}
618 virtual void build() {
621 adaptor.Base::first(edge);
622 while (edge != INVALID) {
623 Parent::operator[](edge).prevOut = edge;
624 adaptor.Base::next(edge);
628 virtual void clear() {
630 adaptor.Base::first(node);
631 while (node != INVALID) {
632 (*adaptor.nodes)[node].firstIn = INVALID;
633 (*adaptor.nodes)[node].firstOut = INVALID;
634 adaptor.Base::next(node);
639 virtual void add(const Edge& edge) {
641 Parent::operator[](edge).prevOut = edge;
644 virtual void add(const std::vector<Edge>& edges) {
646 for (int i = 0; i < (int)edges.size(); ++i) {
647 Parent::operator[](edges[i]).prevOut = edges[i];
651 virtual void erase(const Edge& edge) {
656 virtual void erase(const std::vector<Edge>& edges) {
657 for (int i = 0; i < (int)edges.size(); ++i) {
658 adaptor.hide(edges[i]);
660 Parent::erase(edges);
671 /// \ingroup semi_adaptors
673 /// \brief Graph which uses a subset of another graph's edges.
675 /// Graph which uses a subset of another graph's edges. This class
676 /// is an alternative to the EdgeSubGraphAdaptor which is created for the
677 /// same reason. The main difference between the two class that it
678 /// makes linked lists on the unhidden edges what cause that
679 /// on sparse subgraphs the algorithms can be more efficient and some times
680 /// provide better time complexity. On other way this implemetation is
681 /// less efficient in most case when the subgraph filters out only
684 /// \see EdgeSubGraphAdaptor
685 /// \see EdgeSubGraphBase
686 template <typename Graph>
688 : public GraphAdaptorExtender< EdgeSubGraphBase<Graph> > {
690 typedef GraphAdaptorExtender< EdgeSubGraphBase<Graph> > Parent;
692 /// \brief Constructor for sub-graph.
694 /// Constructor for sub-graph. Initially all the edges are hidden in the
696 EdgeSubGraph(const Graph& _graph)
697 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
698 Parent::construct(_graph, nodes, edges);
701 typename Parent::NodesImpl nodes;
702 typename Parent::EdgesImpl edges;
706 // template<typename Graph, typename Number,
707 // typename CapacityMap, typename FlowMap>
709 // : public IterableGraphExtender<EdgeSubGraphBase<
710 // UGraphAdaptor<Graph> > > {
712 // typedef IterableGraphExtender<EdgeSubGraphBase<
713 // UGraphAdaptor<Graph> > > Parent;
716 // UGraphAdaptor<Graph> u;
718 // const CapacityMap* capacity;
721 // typename Parent::NodesImpl nodes;
722 // typename Parent::EdgesImpl edges;
724 // void setCapacityMap(const CapacityMap& _capacity) {
725 // capacity=&_capacity;
728 // void setFlowMap(FlowMap& _flow) {
734 // typedef typename UGraphAdaptor<Graph>::Node Node;
735 // typedef typename UGraphAdaptor<Graph>::Edge Edge;
736 // typedef typename UGraphAdaptor<Graph>::UEdge UEdge;
738 // ResGraphAdaptor(Graph& _graph,
739 // const CapacityMap& _capacity, FlowMap& _flow)
740 // : Parent(), u(_graph), capacity(&_capacity), flow(&_flow),
741 // nodes(*this, _graph), edges(*this, _graph) {
742 // Parent::construct(u, nodes, edges);
743 // setFlowMap(_flow);
744 // setCapacityMap(_capacity);
745 // typename Graph::Edge edge;
746 // for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
747 // if ((*flow)[edge] != (*capacity)[edge]) {
748 // Parent::unHide(direct(edge, true));
750 // if ((*flow)[edge] != 0) {
751 // Parent::unHide(direct(edge, false));
756 // void augment(const Edge& e, Number a) {
757 // if (direction(e)) {
758 // flow->set(e, (*flow)[e]+a);
760 // flow->set(e, (*flow)[e]-a);
762 // if ((*flow)[e] == (*capacity)[e]) {
765 // Parent::unHide(e);
767 // if ((*flow)[e] == 0) {
768 // Parent::hide(oppositeEdge(e));
770 // Parent::unHide(oppositeEdge(e));
774 // Number resCap(const Edge& e) {
775 // if (direction(e)) {
776 // return (*capacity)[e]-(*flow)[e];
778 // return (*flow)[e];
782 // bool direction(const Edge& edge) const {
783 // return Parent::getGraph().direction(edge);
786 // Edge direct(const UEdge& edge, bool direction) const {
787 // return Parent::getGraph().direct(edge, direction);
790 // Edge direct(const UEdge& edge, const Node& node) const {
791 // return Parent::getGraph().direct(edge, node);
794 // Edge oppositeEdge(const Edge& edge) const {
795 // return Parent::getGraph().oppositeEdge(edge);
798 // /// \brief Residual capacity map.
800 // /// In generic residual graphs the residual capacity can be obtained
804 // const ResGraphAdaptor* res_graph;
806 // typedef Number Value;
808 // ResCap(const ResGraphAdaptor& _res_graph)
809 // : res_graph(&_res_graph) {}
810 // Number operator[](const Edge& e) const {
811 // return res_graph->resCap(e);