vmap.h: Enables one to create maps with a virtual base class.
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>
26 /// \brief Base for the SubGraph.
28 /// Base for the SubGraph.
29 template <typename _Graph>
30 class SubGraphBase : public GraphAdaptorBase<const _Graph> {
33 typedef SubGraphBase<_Graph> SubGraph;
34 typedef GraphAdaptorBase<const _Graph> Parent;
37 typedef typename Parent::Node Node;
38 typedef typename Parent::Edge Edge;
48 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
49 Parent::setGraph(_graph);
56 while (node != INVALID) {
57 (*nodes)[node].prev = node;
58 (*nodes)[node].firstIn = INVALID;
59 (*nodes)[node].firstOut = INVALID;
65 while (edge != INVALID) {
66 (*edges)[edge].prevOut = edge;
73 void first(Node& node) const {
76 void next(Node& node) const {
77 node = (*nodes)[node].next;
80 void first(Edge& edge) const {
81 Node node = firstNode;
82 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
83 node = (*nodes)[node].next;
85 if (node == INVALID) {
88 edge = (*nodes)[node].firstOut;
91 void next(Edge& edge) const {
92 if ((*edges)[edge].nextOut != INVALID) {
93 edge = (*edges)[edge].nextOut;
95 Node node = (*nodes)[source(edge)].next;
96 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
97 node = (*nodes)[node].next;
99 if (node == INVALID) {
102 edge = (*nodes)[node].firstOut;
107 void firstOut(Edge& edge, const Node& node) const {
108 edge = (*nodes)[node].firstOut;
110 void nextOut(Edge& edge) const {
111 edge = (*edges)[edge].nextOut;
114 void firstIn(Edge& edge, const Node& node) const {
115 edge = (*nodes)[node].firstIn;
117 void nextIn(Edge& edge) const {
118 edge = (*edges)[edge].nextIn;
121 /// \brief Returns true when the given node is hidden.
123 /// Returns true when the given node is hidden.
124 bool hidden(const Node& node) const {
125 return (*nodes)[node].prev == node;
128 /// \brief Hide the given node in the sub-graph.
130 /// Hide the given node in the sub graph. It just lace out from
131 /// the linked lists the given node. If there are incoming or outgoing
132 /// edges into or from this node then all of these will be hidden.
133 void hide(const Node& node) {
134 if (hidden(node)) return;
136 firstOut(edge, node);
137 while (edge != INVALID) {
139 firstOut(edge, node);
142 firstOut(edge, node);
143 while (edge != INVALID) {
145 firstOut(edge, node);
147 if ((*nodes)[node].prev != INVALID) {
148 (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
150 firstNode = (*nodes)[node].next;
152 if ((*nodes)[node].next != INVALID) {
153 (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
155 (*nodes)[node].prev = node;
156 (*nodes)[node].firstIn = INVALID;
157 (*nodes)[node].firstOut = INVALID;
160 /// \brief Unhide the given node in the sub-graph.
162 /// Unhide the given node in the sub graph. It just lace in the given
163 /// node into the linked lists.
164 void unHide(const Node& node) {
165 if (!hidden(node)) return;
166 (*nodes)[node].next = firstNode;
167 (*nodes)[node].prev = INVALID;
168 if ((*nodes)[node].next != INVALID) {
169 (*nodes)[(*nodes)[node].next].prev = node;
174 /// \brief Returns true when the given edge is hidden.
176 /// Returns true when the given edge is hidden.
177 bool hidden(const Edge& edge) const {
178 return (*edges)[edge].prevOut == edge;
181 /// \brief Hide the given edge in the sub-graph.
183 /// Hide the given edge in the sub graph. It just lace out from
184 /// the linked lists the given edge.
185 void hide(const Edge& edge) {
186 if (hidden(edge)) return;
187 if ((*edges)[edge].prevOut == edge) return;
188 if ((*edges)[edge].prevOut != INVALID) {
189 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
191 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
193 if ((*edges)[edge].nextOut != INVALID) {
194 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
197 if ((*edges)[edge].prevIn != INVALID) {
198 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
200 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
202 if ((*edges)[edge].nextIn != INVALID) {
203 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
205 (*edges)[edge].next = edge;
208 /// \brief Unhide the given edge in the sub-graph.
210 /// Unhide the given edge in the sub graph. It just lace in the given
211 /// edge into the linked lists. If the source or the target of the
212 /// node is hidden then it will unhide it.
213 void unHide(const Edge& edge) {
214 if (!hidden(edge)) return;
218 node = Parent::source(edge);
220 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
221 (*edges)[edge].prevOut = INVALID;
222 if ((*edges)[edge].nextOut != INVALID) {
223 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
225 (*nodes)[node].firstOut = edge;
227 node = Parent::target(edge);
229 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
230 (*edges)[edge].prevIn = INVALID;
231 if ((*edges)[edge].nextIn != INVALID) {
232 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
234 (*nodes)[node].firstIn = edge;
237 typedef False NodeNumTag;
238 typedef False EdgeNumTag;
243 Edge firstIn, firstOut;
245 class NodesImpl : public Graph::template NodeMap<NodeT> {
246 friend class SubGraphBase;
248 typedef typename Graph::template NodeMap<NodeT> Parent;
250 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
251 : Parent(_graph), adaptor(_adaptor) {}
253 virtual ~NodesImpl() {}
255 virtual void build() {
258 adaptor.Base::first(node);
259 while (node != INVALID) {
260 Parent::operator[](node).prev = node;
261 Parent::operator[](node).firstIn = INVALID;
262 Parent::operator[](node).firstOut = INVALID;
263 adaptor.Base::next(node);
267 virtual void clear() {
268 adaptor.firstNode = INVALID;
272 virtual void add(const Node& node) {
274 Parent::operator[](node).prev = node;
275 Parent::operator[](node).firstIn = INVALID;
276 Parent::operator[](node).firstOut = INVALID;
279 virtual void add(const std::vector<Node>& nodes) {
281 for (int i = 0; i < (int)nodes.size(); ++i) {
282 Parent::operator[](nodes[i]).prev = nodes[i];
283 Parent::operator[](nodes[i]).firstIn = INVALID;
284 Parent::operator[](nodes[i]).firstOut = INVALID;
288 virtual void erase(const Node& node) {
293 virtual void erase(const std::vector<Node>& nodes) {
294 for (int i = 0; i < (int)nodes.size(); ++i) {
295 adaptor.hide(nodes[i]);
297 Parent::erase(nodes);
305 Edge prevOut, nextOut;
308 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
309 friend class SubGraphBase;
311 typedef typename Graph::template EdgeMap<EdgeT> Parent;
313 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
314 : Parent(_graph), adaptor(_adaptor) {}
316 virtual ~EdgesImpl() {}
318 virtual void build() {
321 adaptor.Base::first(edge);
322 while (edge != INVALID) {
323 Parent::operator[](edge).prevOut = edge;
324 adaptor.Base::next(edge);
328 virtual void clear() {
331 while (node != INVALID) {
332 (*adaptor.nodes).firstIn = INVALID;
333 (*adaptor.nodes).firstOut = INVALID;
339 virtual void add(const Edge& edge) {
341 Parent::operator[](edge).prevOut = edge;
344 virtual void add(const std::vector<Edge>& edges) {
346 for (int i = 0; i < (int)edges.size(); ++i) {
347 Parent::operator[](edges[i]).prevOut = edges[i];
351 virtual void erase(const Edge& edge) {
356 virtual void erase(const std::vector<Edge>& edges) {
357 for (int i = 0; i < (int)edges.size(); ++i) {
358 adaptor.hide(edges[i]);
360 Parent::erase(edges);
372 /// \ingroup semi_adaptors
374 /// \brief Graph which uses a subset of an other graph's nodes and edges.
376 /// Graph which uses a subset of an other graph's nodes and edges. This class
377 /// is an alternative to the SubGraphAdaptor which is created for the
378 /// same reason. The main difference between the two class that it
379 /// makes linked lists on the unhidden nodes and edges what cause that
380 /// on sparse subgraphs the algorithms can be more efficient and some times
381 /// provide better time complexity. On other way this implemetation is
382 /// less efficient in most case when the subgraph filters out only
383 /// a few nodes or edges.
385 /// \see SubGraphAdaptor
386 /// \see EdgeSubGraphBase
387 template <typename Graph>
389 : public IterableGraphExtender< SubGraphBase<Graph> > {
391 typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
393 /// \brief Constructor for sub-graph.
395 /// Constructor for sub-graph. Initially all the edges and nodes
396 /// are hidden in the graph.
397 SubGraph(const Graph& _graph)
398 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
399 Parent::construct(_graph, nodes, edges);
402 typename Parent::NodesImpl nodes;
403 typename Parent::EdgesImpl edges;
406 /// \brief Base for the EdgeSubGraph.
408 /// Base for the EdgeSubGraph.
409 template <typename _Graph>
410 class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
412 typedef _Graph Graph;
413 typedef EdgeSubGraphBase<_Graph> SubGraph;
414 typedef GraphAdaptorBase<const _Graph> Parent;
417 typedef typename Parent::Node Node;
418 typedef typename Parent::Edge Edge;
426 EdgeSubGraphBase() {}
428 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
429 Parent::setGraph(_graph);
435 while (node != INVALID) {
436 (*nodes)[node].firstIn = INVALID;
437 (*nodes)[node].firstOut = INVALID;
443 while (edge != INVALID) {
444 (*edges)[edge].prevOut = edge;
451 void first(Node& node) const {
454 void next(Node& node) const {
458 void first(Edge& edge) const {
461 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
464 if (node == INVALID) {
467 edge = (*nodes)[node].firstOut;
470 void next(Edge& edge) const {
471 if ((*edges)[edge].nextOut != INVALID) {
472 edge = (*edges)[edge].nextOut;
474 Node node = source(edge);
476 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
479 if (node == INVALID) {
482 edge = (*nodes)[node].firstOut;
487 void firstOut(Edge& edge, const Node& node) const {
488 edge = (*nodes)[node].firstOut;
490 void nextOut(Edge& edge) const {
491 edge = (*edges)[edge].nextOut;
494 void firstIn(Edge& edge, const Node& node) const {
495 edge = (*nodes)[node].firstIn;
497 void nextIn(Edge& edge) const {
498 edge = (*edges)[edge].nextIn;
501 /// \brief Returns true when the given edge is hidden.
503 /// Returns true when the given edge is hidden.
504 bool hidden(const Edge& edge) const {
505 return (*edges)[edge].prevOut == edge;
508 /// \brief Hide the given edge in the sub-graph.
510 /// Hide the given edge in the sub graph. It just lace out from
511 /// the linked lists the given edge.
512 void hide(const Edge& edge) {
513 if (hidden(edge)) return;
514 if ((*edges)[edge].prevOut != INVALID) {
515 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
517 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
519 if ((*edges)[edge].nextOut != INVALID) {
520 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
523 if ((*edges)[edge].prevIn != INVALID) {
524 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
526 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
528 if ((*edges)[edge].nextIn != INVALID) {
529 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
531 (*edges)[edge].prevOut = edge;
534 /// \brief Unhide the given edge in the sub-graph.
536 /// Unhide the given edge in the sub graph. It just lace in the given
537 /// edge into the linked lists.
538 void unHide(const Edge& edge) {
539 if (!hidden(edge)) return;
542 node = Parent::source(edge);
543 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
544 (*edges)[edge].prevOut = INVALID;
545 if ((*edges)[edge].nextOut != INVALID) {
546 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
548 (*nodes)[node].firstOut = edge;
550 node = Parent::target(edge);
551 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
552 (*edges)[edge].prevIn = INVALID;
553 if ((*edges)[edge].nextIn != INVALID) {
554 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
556 (*nodes)[node].firstIn = edge;
561 Edge firstIn, firstOut;
563 class NodesImpl : public Graph::template NodeMap<NodeT> {
564 friend class EdgeSubGraphBase;
566 typedef typename Graph::template NodeMap<NodeT> Parent;
568 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
569 : Parent(_graph), adaptor(_adaptor) {}
571 virtual ~NodesImpl() {}
573 virtual void build() {
576 adaptor.Base::first(node);
577 while (node != INVALID) {
578 Parent::operator[](node).firstIn = INVALID;
579 Parent::operator[](node).firstOut = INVALID;
580 adaptor.Base::next(node);
584 virtual void add(const Node& node) {
586 Parent::operator[](node).firstIn = INVALID;
587 Parent::operator[](node).firstOut = INVALID;
590 virtual void add(const std::vector<Node>& nodes) {
592 for (int i = 0; i < (int)nodes.size(); ++i) {
593 Parent::operator[](nodes[i]).firstIn = INVALID;
594 Parent::operator[](nodes[i]).firstOut = INVALID;
603 Edge prevOut, nextOut;
606 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
607 friend class EdgeSubGraphBase;
609 typedef typename Graph::template EdgeMap<EdgeT> Parent;
611 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
612 : Parent(_graph), adaptor(_adaptor) {}
614 virtual ~EdgesImpl() {}
616 virtual void build() {
619 adaptor.Base::first(edge);
620 while (edge != INVALID) {
621 Parent::operator[](edge).prevOut = edge;
622 adaptor.Base::next(edge);
626 virtual void clear() {
628 adaptor.Base::first(node);
629 while (node != INVALID) {
630 (*adaptor.nodes)[node].firstIn = INVALID;
631 (*adaptor.nodes)[node].firstOut = INVALID;
632 adaptor.Base::next(node);
637 virtual void add(const Edge& edge) {
639 Parent::operator[](edge).prevOut = edge;
642 virtual void add(const std::vector<Edge>& edges) {
644 for (int i = 0; i < (int)edges.size(); ++i) {
645 Parent::operator[](edges[i]).prevOut = edges[i];
649 virtual void erase(const Edge& edge) {
654 virtual void erase(const std::vector<Edge>& edges) {
655 for (int i = 0; i < (int)edges.size(); ++i) {
656 adaptor.hide(edges[i]);
658 Parent::erase(edges);
669 /// \ingroup semi_adaptors
671 /// \brief Graph which uses a subset of an other graph's edges.
673 /// Graph which uses a subset of an other graph's edges. This class
674 /// is an alternative to the EdgeSubGraphAdaptor which is created for the
675 /// same reason. The main difference between the two class that it
676 /// makes linked lists on the unhidden edges what cause that
677 /// on sparse subgraphs the algorithms can be more efficient and some times
678 /// provide better time complexity. On other way this implemetation is
679 /// less efficient in most case when the subgraph filters out only
682 /// \see EdgeSubGraphAdaptor
683 /// \see EdgeSubGraphBase
684 template <typename Graph>
686 : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
688 typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
690 /// \brief Constructor for sub-graph.
692 /// Constructor for sub-graph. Initially all the edges are hidden in the
694 EdgeSubGraph(const Graph& _graph)
695 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
696 Parent::construct(_graph, nodes, edges);
699 typename Parent::NodesImpl nodes;
700 typename Parent::EdgesImpl edges;
704 // template<typename Graph, typename Number,
705 // typename CapacityMap, typename FlowMap>
707 // : public IterableGraphExtender<EdgeSubGraphBase<
708 // UGraphAdaptor<Graph> > > {
710 // typedef IterableGraphExtender<EdgeSubGraphBase<
711 // UGraphAdaptor<Graph> > > Parent;
714 // UGraphAdaptor<Graph> u;
716 // const CapacityMap* capacity;
719 // typename Parent::NodesImpl nodes;
720 // typename Parent::EdgesImpl edges;
722 // void setCapacityMap(const CapacityMap& _capacity) {
723 // capacity=&_capacity;
726 // void setFlowMap(FlowMap& _flow) {
732 // typedef typename UGraphAdaptor<Graph>::Node Node;
733 // typedef typename UGraphAdaptor<Graph>::Edge Edge;
734 // typedef typename UGraphAdaptor<Graph>::UEdge UEdge;
736 // ResGraphAdaptor(Graph& _graph,
737 // const CapacityMap& _capacity, FlowMap& _flow)
738 // : Parent(), u(_graph), capacity(&_capacity), flow(&_flow),
739 // nodes(*this, _graph), edges(*this, _graph) {
740 // Parent::construct(u, nodes, edges);
741 // setFlowMap(_flow);
742 // setCapacityMap(_capacity);
743 // typename Graph::Edge edge;
744 // for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
745 // if ((*flow)[edge] != (*capacity)[edge]) {
746 // Parent::unHide(direct(edge, true));
748 // if ((*flow)[edge] != 0) {
749 // Parent::unHide(direct(edge, false));
754 // void augment(const Edge& e, Number a) {
755 // if (direction(e)) {
756 // flow->set(e, (*flow)[e]+a);
758 // flow->set(e, (*flow)[e]-a);
760 // if ((*flow)[e] == (*capacity)[e]) {
763 // Parent::unHide(e);
765 // if ((*flow)[e] == 0) {
766 // Parent::hide(oppositeEdge(e));
768 // Parent::unHide(oppositeEdge(e));
772 // Number resCap(const Edge& e) {
773 // if (direction(e)) {
774 // return (*capacity)[e]-(*flow)[e];
776 // return (*flow)[e];
780 // bool direction(const Edge& edge) const {
781 // return Parent::getGraph().direction(edge);
784 // Edge direct(const UEdge& edge, bool direction) const {
785 // return Parent::getGraph().direct(edge, direction);
788 // Edge direct(const UEdge& edge, const Node& node) const {
789 // return Parent::getGraph().direct(edge, node);
792 // Edge oppositeEdge(const Edge& edge) const {
793 // return Parent::getGraph().oppositeEdge(edge);
796 // /// \brief Residual capacity map.
798 // /// In generic residual graphs the residual capacity can be obtained
802 // const ResGraphAdaptor* res_graph;
804 // typedef Number Value;
806 // ResCap(const ResGraphAdaptor& _res_graph)
807 // : res_graph(&_res_graph) {}
808 // Number operator[](const Edge& e) const {
809 // return res_graph->resCap(e);