If default value of a new map is constant, the newly created elements will get that value as well. Documentation is added to BrokenEdge, MapStorage and GraphDisplazCanvas classes.
2 * lemon/sub_graph.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
17 #ifndef LEMON_SUB_GRAPH_H
18 #define LEMON_SUB_GRAPH_H
20 #include <lemon/graph_adaptor.h>
24 /// \brief Base for the SubGraph.
26 /// Base for the SubGraph.
27 template <typename _Graph>
28 class SubGraphBase : public GraphAdaptorBase<const _Graph> {
31 typedef SubGraphBase<_Graph> SubGraph;
32 typedef GraphAdaptorBase<const _Graph> Parent;
35 typedef typename Parent::Node Node;
36 typedef typename Parent::Edge Edge;
46 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
47 Parent::setGraph(_graph);
54 while (node != INVALID) {
55 (*nodes)[node].prev = node;
56 (*nodes)[node].firstIn = INVALID;
57 (*nodes)[node].firstOut = INVALID;
63 while (edge != INVALID) {
64 (*edges)[edge].prevOut = edge;
71 void first(Node& node) const {
74 void next(Node& node) const {
75 node = (*nodes)[node].next;
78 void first(Edge& edge) const {
79 Node node = firstNode;
80 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
81 node = (*nodes)[node].next;
83 if (node == INVALID) {
86 edge = (*nodes)[node].firstOut;
89 void next(Edge& edge) const {
90 if ((*edges)[edge].nextOut != INVALID) {
91 edge = (*edges)[edge].nextOut;
93 Node node = (*nodes)[source(edge)].next;
94 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
95 node = (*nodes)[node].next;
97 if (node == INVALID) {
100 edge = (*nodes)[node].firstOut;
105 void firstOut(Edge& edge, const Node& node) const {
106 edge = (*nodes)[node].firstOut;
108 void nextOut(Edge& edge) const {
109 edge = (*edges)[edge].nextOut;
112 void firstIn(Edge& edge, const Node& node) const {
113 edge = (*nodes)[node].firstIn;
115 void nextIn(Edge& edge) const {
116 edge = (*edges)[edge].nextIn;
119 /// \brief Returns true when the given node is hidden.
121 /// Returns true when the given node is hidden.
122 bool hidden(const Node& node) const {
123 return (*nodes)[node].prev == node;
126 /// \brief Hide the given node in the sub-graph.
128 /// Hide the given node in the sub graph. It just lace out from
129 /// the linked lists the given node. If there are incoming or outgoing
130 /// edges into or from this node then all of these will be hidden.
131 void hide(const Node& node) {
132 if (hidden(node)) return;
134 firstOut(edge, node);
135 while (edge != INVALID) {
137 firstOut(edge, node);
140 firstOut(edge, node);
141 while (edge != INVALID) {
143 firstOut(edge, node);
145 if ((*nodes)[node].prev != INVALID) {
146 (*nodes)[(*nodes)[node].prev].next = (*nodes)[node].next;
148 firstNode = (*nodes)[node].next;
150 if ((*nodes)[node].next != INVALID) {
151 (*nodes)[(*nodes)[node].next].prev = (*nodes)[node].prev;
153 (*nodes)[node].prev = node;
154 (*nodes)[node].firstIn = INVALID;
155 (*nodes)[node].firstOut = INVALID;
158 /// \brief Unhide the given node in the sub-graph.
160 /// Unhide the given node in the sub graph. It just lace in the given
161 /// node into the linked lists.
162 void unHide(const Node& node) {
163 if (!hidden(node)) return;
164 (*nodes)[node].next = firstNode;
165 (*nodes)[node].prev = INVALID;
166 if ((*nodes)[node].next != INVALID) {
167 (*nodes)[(*nodes)[node].next].prev = node;
172 /// \brief Returns true when the given edge is hidden.
174 /// Returns true when the given edge is hidden.
175 bool hidden(const Edge& edge) const {
176 return (*edges)[edge].prevOut == edge;
179 /// \brief Hide the given edge in the sub-graph.
181 /// Hide the given edge in the sub graph. It just lace out from
182 /// the linked lists the given edge.
183 void hide(const Edge& edge) {
184 if (hidden(edge)) return;
185 if ((*edges)[edge].prevOut == edge) return;
186 if ((*edges)[edge].prevOut != INVALID) {
187 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
189 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
191 if ((*edges)[edge].nextOut != INVALID) {
192 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
195 if ((*edges)[edge].prevIn != INVALID) {
196 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
198 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
200 if ((*edges)[edge].nextIn != INVALID) {
201 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
203 (*edges)[edge].next = edge;
206 /// \brief Unhide the given edge in the sub-graph.
208 /// Unhide the given edge in the sub graph. It just lace in the given
209 /// edge into the linked lists. If the source or the target of the
210 /// node is hidden then it will unhide it.
211 void unHide(const Edge& edge) {
212 if (!hidden(edge)) return;
216 node = Parent::source(edge);
218 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
219 (*edges)[edge].prevOut = INVALID;
220 if ((*edges)[edge].nextOut != INVALID) {
221 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
223 (*nodes)[node].firstOut = edge;
225 node = Parent::target(edge);
227 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
228 (*edges)[edge].prevIn = INVALID;
229 if ((*edges)[edge].nextIn != INVALID) {
230 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
232 (*nodes)[node].firstIn = edge;
235 typedef False NodeNumTag;
236 typedef False EdgeNumTag;
241 Edge firstIn, firstOut;
243 class NodesImpl : public Graph::template NodeMap<NodeT> {
244 friend class SubGraphBase;
246 typedef typename Graph::template NodeMap<NodeT> Parent;
248 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
249 : Parent(_graph), adaptor(_adaptor) {}
251 virtual ~NodesImpl() {}
253 virtual void build() {
256 adaptor.Base::first(node);
257 while (node != INVALID) {
258 Parent::operator[](node).prev = node;
259 Parent::operator[](node).firstIn = INVALID;
260 Parent::operator[](node).firstOut = INVALID;
261 adaptor.Base::next(node);
265 virtual void clear() {
266 adaptor.firstNode = INVALID;
270 virtual void add(const Node& node) {
272 Parent::operator[](node).prev = node;
273 Parent::operator[](node).firstIn = INVALID;
274 Parent::operator[](node).firstOut = INVALID;
276 virtual void add(const std::vector<Node>& nodes) {
278 for (int i = 0; i < (int)nodes.size(); ++i) {
279 Parent::operator[](nodes[i]).prev = nodes[i];
280 Parent::operator[](nodes[i]).firstIn = INVALID;
281 Parent::operator[](nodes[i]).firstOut = INVALID;
285 virtual void erase(const Node& node) {
290 virtual void erase(const std::vector<Node>& nodes) {
291 for (int i = 0; i < (int)nodes.size(); ++i) {
292 adaptor.hide(nodes[i]);
294 Parent::erase(nodes);
302 Edge prevOut, nextOut;
305 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
306 friend class SubGraphBase;
308 typedef typename Graph::template EdgeMap<EdgeT> Parent;
310 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
311 : Parent(_graph), adaptor(_adaptor) {}
313 virtual ~EdgesImpl() {}
315 virtual void build() {
318 adaptor.Base::first(edge);
319 while (edge != INVALID) {
320 Parent::operator[](edge).prevOut = edge;
321 adaptor.Base::next(edge);
325 virtual void clear() {
328 while (node != INVALID) {
329 (*adaptor.nodes).firstIn = INVALID;
330 (*adaptor.nodes).firstOut = INVALID;
336 virtual void add(const Edge& edge) {
338 Parent::operator[](edge).prevOut = edge;
341 virtual void add(const std::vector<Edge>& edges) {
343 for (int i = 0; i < (int)edges.size(); ++i) {
344 Parent::operator[](edges[i]).prevOut = edges[i];
348 virtual void erase(const Edge& edge) {
353 virtual void erase(const std::vector<Edge>& edges) {
354 for (int i = 0; i < (int)edges.size(); ++i) {
355 adaptor.hide(edges[i]);
369 /// \ingroup semi_adaptors
371 /// \brief Graph which uses a subset of an other graph's nodes and edges.
373 /// Graph which uses a subset of an other graph's nodes and edges. This class
374 /// is an alternative to the SubGraphAdaptor which is created for the
375 /// same reason. The main difference between the two class that it
376 /// makes linked lists on the unhidden nodes and edges what cause that
377 /// on sparse subgraphs the algorithms can be more efficient and some times
378 /// provide better time complexity. On other way this implemetation is
379 /// less efficient in most case when the subgraph filters out only
380 /// a few nodes or edges.
382 /// \see SubGraphAdaptor
383 /// \see EdgeSubGraphBase
384 template <typename Graph>
386 : public IterableGraphExtender< SubGraphBase<Graph> > {
388 typedef IterableGraphExtender< SubGraphBase<Graph> > Parent;
390 /// \brief Constructor for sub-graph.
392 /// Constructor for sub-graph. Initially all the edges and nodes
393 /// are hidden in the graph.
394 SubGraph(const Graph& _graph)
395 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
396 Parent::construct(_graph, nodes, edges);
399 typename Parent::NodesImpl nodes;
400 typename Parent::EdgesImpl edges;
403 /// \brief Base for the EdgeSubGraph.
405 /// Base for the EdgeSubGraph.
406 template <typename _Graph>
407 class EdgeSubGraphBase : public GraphAdaptorBase<const _Graph> {
409 typedef _Graph Graph;
410 typedef EdgeSubGraphBase<_Graph> SubGraph;
411 typedef GraphAdaptorBase<const _Graph> Parent;
414 typedef typename Parent::Node Node;
415 typedef typename Parent::Edge Edge;
423 EdgeSubGraphBase() {}
425 void construct(const Graph& _graph, NodesImpl& _nodes, EdgesImpl& _edges) {
426 Parent::setGraph(_graph);
432 while (node != INVALID) {
433 (*nodes)[node].firstIn = INVALID;
434 (*nodes)[node].firstOut = INVALID;
440 while (edge != INVALID) {
441 (*edges)[edge].prevOut = edge;
448 void first(Node& node) const {
451 void next(Node& node) const {
455 void first(Edge& edge) const {
458 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
461 if (node == INVALID) {
464 edge = (*nodes)[node].firstOut;
467 void next(Edge& edge) const {
468 if ((*edges)[edge].nextOut != INVALID) {
469 edge = (*edges)[edge].nextOut;
471 Node node = source(edge);
473 while (node != INVALID && (*nodes)[node].firstOut == INVALID) {
476 if (node == INVALID) {
479 edge = (*nodes)[node].firstOut;
484 void firstOut(Edge& edge, const Node& node) const {
485 edge = (*nodes)[node].firstOut;
487 void nextOut(Edge& edge) const {
488 edge = (*edges)[edge].nextOut;
491 void firstIn(Edge& edge, const Node& node) const {
492 edge = (*nodes)[node].firstIn;
494 void nextIn(Edge& edge) const {
495 edge = (*edges)[edge].nextIn;
498 /// \brief Returns true when the given edge is hidden.
500 /// Returns true when the given edge is hidden.
501 bool hidden(const Edge& edge) const {
502 return (*edges)[edge].prevOut == edge;
505 /// \brief Hide the given edge in the sub-graph.
507 /// Hide the given edge in the sub graph. It just lace out from
508 /// the linked lists the given edge.
509 void hide(const Edge& edge) {
510 if (hidden(edge)) return;
511 if ((*edges)[edge].prevOut != INVALID) {
512 (*edges)[(*edges)[edge].prevOut].nextOut = (*edges)[edge].nextOut;
514 (*nodes)[source(edge)].firstOut = (*edges)[edge].nextOut;
516 if ((*edges)[edge].nextOut != INVALID) {
517 (*edges)[(*edges)[edge].nextOut].prevOut = (*edges)[edge].prevOut;
520 if ((*edges)[edge].prevIn != INVALID) {
521 (*edges)[(*edges)[edge].prevIn].nextIn = (*edges)[edge].nextIn;
523 (*nodes)[target(edge)].firstIn = (*edges)[edge].nextIn;
525 if ((*edges)[edge].nextIn != INVALID) {
526 (*edges)[(*edges)[edge].nextIn].prevIn = (*edges)[edge].prevIn;
528 (*edges)[edge].prevOut = edge;
531 /// \brief Unhide the given edge in the sub-graph.
533 /// Unhide the given edge in the sub graph. It just lace in the given
534 /// edge into the linked lists.
535 void unHide(const Edge& edge) {
536 if (!hidden(edge)) return;
539 node = Parent::source(edge);
540 (*edges)[edge].nextOut = (*nodes)[node].firstOut;
541 (*edges)[edge].prevOut = INVALID;
542 if ((*edges)[edge].nextOut != INVALID) {
543 (*edges)[(*edges)[edge].nextOut].prevOut = edge;
545 (*nodes)[node].firstOut = edge;
547 node = Parent::target(edge);
548 (*edges)[edge].nextIn = (*nodes)[node].firstIn;
549 (*edges)[edge].prevIn = INVALID;
550 if ((*edges)[edge].nextIn != INVALID) {
551 (*edges)[(*edges)[edge].nextIn].prevIn = edge;
553 (*nodes)[node].firstIn = edge;
558 Edge firstIn, firstOut;
560 class NodesImpl : public Graph::template NodeMap<NodeT> {
561 friend class EdgeSubGraphBase;
563 typedef typename Graph::template NodeMap<NodeT> Parent;
565 NodesImpl(SubGraph& _adaptor, const Graph& _graph)
566 : Parent(_graph), adaptor(_adaptor) {}
568 virtual ~NodesImpl() {}
570 virtual void build() {
573 adaptor.Base::first(node);
574 while (node != INVALID) {
575 Parent::operator[](node).firstIn = INVALID;
576 Parent::operator[](node).firstOut = INVALID;
577 adaptor.Base::next(node);
581 virtual void add(const Node& node) {
583 Parent::operator[](node).firstIn = INVALID;
584 Parent::operator[](node).firstOut = INVALID;
592 Edge prevOut, nextOut;
595 class EdgesImpl : public Graph::template EdgeMap<EdgeT> {
596 friend class EdgeSubGraphBase;
598 typedef typename Graph::template EdgeMap<EdgeT> Parent;
600 EdgesImpl(SubGraph& _adaptor, const Graph& _graph)
601 : Parent(_graph), adaptor(_adaptor) {}
603 virtual ~EdgesImpl() {}
605 virtual void build() {
608 adaptor.Base::first(edge);
609 while (edge != INVALID) {
610 Parent::operator[](edge).prevOut = edge;
611 adaptor.Base::next(edge);
615 virtual void clear() {
617 adaptor.Base::first(node);
618 while (node != INVALID) {
619 (*adaptor.nodes)[node].firstIn = INVALID;
620 (*adaptor.nodes)[node].firstOut = INVALID;
621 adaptor.Base::next(node);
626 virtual void add(const Edge& edge) {
628 Parent::operator[](edge).prevOut = edge;
631 virtual void add(const std::vector<Edge>& edges) {
633 for (int i = 0; i < (int)edges.size(); ++i) {
634 Parent::operator[](edges[i]).prevOut = edges[i];
638 virtual void erase(const Edge& edge) {
643 virtual void erase(const std::vector<Edge>& edges) {
644 for (int i = 0; i < (int)edges.size(); ++i) {
645 adaptor.hide(edges[i]);
658 /// \ingroup semi_adaptors
660 /// \brief Graph which uses a subset of an other graph's edges.
662 /// Graph which uses a subset of an other graph's edges. This class
663 /// is an alternative to the EdgeSubGraphAdaptor which is created for the
664 /// same reason. The main difference between the two class that it
665 /// makes linked lists on the unhidden edges what cause that
666 /// on sparse subgraphs the algorithms can be more efficient and some times
667 /// provide better time complexity. On other way this implemetation is
668 /// less efficient in most case when the subgraph filters out only
671 /// \see EdgeSubGraphAdaptor
672 /// \see EdgeSubGraphBase
673 template <typename Graph>
675 : public IterableGraphExtender< EdgeSubGraphBase<Graph> > {
677 typedef IterableGraphExtender< EdgeSubGraphBase<Graph> > Parent;
679 /// \brief Constructor for sub-graph.
681 /// Constructor for sub-graph. Initially all the edges are hidden in the
683 EdgeSubGraph(const Graph& _graph)
684 : Parent(), nodes(*this, _graph), edges(*this, _graph) {
685 Parent::construct(_graph, nodes, edges);
688 typename Parent::NodesImpl nodes;
689 typename Parent::EdgesImpl edges;
693 // template<typename Graph, typename Number,
694 // typename CapacityMap, typename FlowMap>
696 // : public IterableGraphExtender<EdgeSubGraphBase<
697 // UndirGraphAdaptor<Graph> > > {
699 // typedef IterableGraphExtender<EdgeSubGraphBase<
700 // UndirGraphAdaptor<Graph> > > Parent;
703 // UndirGraphAdaptor<Graph> undir;
705 // const CapacityMap* capacity;
708 // typename Parent::NodesImpl nodes;
709 // typename Parent::EdgesImpl edges;
711 // void setCapacityMap(const CapacityMap& _capacity) {
712 // capacity=&_capacity;
715 // void setFlowMap(FlowMap& _flow) {
721 // typedef typename UndirGraphAdaptor<Graph>::Node Node;
722 // typedef typename UndirGraphAdaptor<Graph>::Edge Edge;
723 // typedef typename UndirGraphAdaptor<Graph>::UndirEdge UndirEdge;
725 // ResGraphAdaptor(Graph& _graph,
726 // const CapacityMap& _capacity, FlowMap& _flow)
727 // : Parent(), undir(_graph), capacity(&_capacity), flow(&_flow),
728 // nodes(*this, _graph), edges(*this, _graph) {
729 // Parent::construct(undir, nodes, edges);
730 // setFlowMap(_flow);
731 // setCapacityMap(_capacity);
732 // typename Graph::Edge edge;
733 // for (_graph.first(edge); edge != INVALID; _graph.next(edge)) {
734 // if ((*flow)[edge] != (*capacity)[edge]) {
735 // Parent::unHide(direct(edge, true));
737 // if ((*flow)[edge] != 0) {
738 // Parent::unHide(direct(edge, false));
743 // void augment(const Edge& e, Number a) {
744 // if (direction(e)) {
745 // flow->set(e, (*flow)[e]+a);
747 // flow->set(e, (*flow)[e]-a);
749 // if ((*flow)[e] == (*capacity)[e]) {
752 // Parent::unHide(e);
754 // if ((*flow)[e] == 0) {
755 // Parent::hide(oppositeEdge(e));
757 // Parent::unHide(oppositeEdge(e));
761 // Number resCap(const Edge& e) {
762 // if (direction(e)) {
763 // return (*capacity)[e]-(*flow)[e];
765 // return (*flow)[e];
769 // bool direction(const Edge& edge) const {
770 // return Parent::getGraph().direction(edge);
773 // Edge direct(const UndirEdge& edge, bool direction) const {
774 // return Parent::getGraph().direct(edge, direction);
777 // Edge direct(const UndirEdge& edge, const Node& node) const {
778 // return Parent::getGraph().direct(edge, node);
781 // Edge oppositeEdge(const Edge& edge) const {
782 // return Parent::getGraph().oppositeEdge(edge);
785 // /// \brief Residual capacity map.
787 // /// In generic residual graphs the residual capacity can be obtained
791 // const ResGraphAdaptor* res_graph;
793 // typedef Number Value;
795 // ResCap(const ResGraphAdaptor& _res_graph)
796 // : res_graph(&_res_graph) {}
797 // Number operator[](const Edge& e) const {
798 // return res_graph->resCap(e);