Completions.
2 * src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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_GRAPH_WRAPPER_H
18 #define LEMON_GRAPH_WRAPPER_H
22 ///\brief Several graph wrappers.
24 ///This file contains several useful graph wrapper functions.
26 ///\author Marton Makai
28 #include <lemon/invalid.h>
29 #include <lemon/maps.h>
30 #include <lemon/iterable_graph_extender.h>
43 Base type for the Graph Wrappers
45 \warning Graph wrappers are in even more experimental state than the other
46 parts of the lib. Use them at you own risk.
48 This is the base type for most of LEMON graph wrappers.
49 This class implements a trivial graph wrapper i.e. it only wraps the
50 functions and types of the graph. The purpose of this class is to
51 make easier implementing graph wrappers. E.g. if a wrapper is
52 considered which differs from the wrapped graph only in some of its
53 functions or types, then it can be derived from GraphWrapper, and only the
54 differences should be implemented.
58 template<typename _Graph>
59 class GraphWrapperBase {
62 /// \todo Is it needed?
63 typedef Graph BaseGraph;
64 typedef Graph ParentGraph;
68 GraphWrapperBase() : graph(0) { }
69 void setGraph(Graph& _graph) { graph=&_graph; }
72 GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
74 typedef typename Graph::Node Node;
75 typedef typename Graph::Edge Edge;
77 void first(Node& i) const { graph->first(i); }
78 void first(Edge& i) const { graph->first(i); }
79 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
80 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
82 void next(Node& i) const { graph->next(i); }
83 void next(Edge& i) const { graph->next(i); }
84 void nextIn(Edge& i) const { graph->nextIn(i); }
85 void nextOut(Edge& i) const { graph->nextOut(i); }
87 Node source(const Edge& e) const { return graph->source(e); }
88 Node target(const Edge& e) const { return graph->target(e); }
90 int nodeNum() const { return graph->nodeNum(); }
91 int edgeNum() const { return graph->edgeNum(); }
93 Node addNode() const { return Node(graph->addNode()); }
94 Edge addEdge(const Node& source, const Node& target) const {
95 return Edge(graph->addEdge(source, target)); }
97 void erase(const Node& i) const { graph->erase(i); }
98 void erase(const Edge& i) const { graph->erase(i); }
100 void clear() const { graph->clear(); }
102 bool forward(const Edge& e) const { return graph->forward(e); }
103 bool backward(const Edge& e) const { return graph->backward(e); }
105 int id(const Node& v) const { return graph->id(v); }
106 int id(const Edge& e) const { return graph->id(e); }
108 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
110 template <typename _Value>
111 class NodeMap : public _Graph::template NodeMap<_Value> {
113 typedef typename _Graph::template NodeMap<_Value> Parent;
114 NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
115 NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
116 : Parent(*gw.graph, value) { }
119 template <typename _Value>
120 class EdgeMap : public _Graph::template EdgeMap<_Value> {
122 typedef typename _Graph::template EdgeMap<_Value> Parent;
123 EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
124 EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
125 : Parent(*gw.graph, value) { }
130 template <typename _Graph>
132 public IterableGraphExtender<GraphWrapperBase<_Graph> > {
134 typedef _Graph Graph;
135 typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
137 GraphWrapper() : Parent() { }
140 GraphWrapper(Graph& _graph) { setGraph(_graph); }
143 template <typename _Graph>
144 class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
146 typedef _Graph Graph;
147 typedef GraphWrapperBase<_Graph> Parent;
149 RevGraphWrapperBase() : Parent() { }
151 typedef typename Parent::Node Node;
152 typedef typename Parent::Edge Edge;
155 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
156 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
159 void nextIn(Edge& i) const { Parent::nextOut(i); }
160 void nextOut(Edge& i) const { Parent::nextIn(i); }
162 Node source(const Edge& e) const { return Parent::target(e); }
163 Node target(const Edge& e) const { return Parent::source(e); }
167 /// A graph wrapper which reverses the orientation of the edges.
169 ///\warning Graph wrappers are in even more experimental state than the other
170 ///parts of the lib. Use them at you own risk.
172 /// Let \f$G=(V, A)\f$ be a directed graph and
173 /// suppose that a graph instange \c g of type
174 /// \c ListGraph implements \f$G\f$.
178 /// For each directed edge
179 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
180 /// reversing its orientation.
181 /// Then RevGraphWrapper implements the graph structure with node-set
182 /// \f$V\f$ and edge-set
183 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
184 /// reversing the orientation of its edges. The following code shows how
185 /// such an instance can be constructed.
187 /// RevGraphWrapper<ListGraph> gw(g);
189 ///\author Marton Makai
190 template<typename _Graph>
191 class RevGraphWrapper :
192 public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
194 typedef _Graph Graph;
195 typedef IterableGraphExtender<
196 RevGraphWrapperBase<_Graph> > Parent;
198 RevGraphWrapper() { }
200 RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
204 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
205 class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
207 typedef _Graph Graph;
208 typedef GraphWrapperBase<_Graph> Parent;
210 NodeFilterMap* node_filter_map;
211 EdgeFilterMap* edge_filter_map;
212 SubGraphWrapperBase() : Parent(),
213 node_filter_map(0), edge_filter_map(0) { }
215 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
216 node_filter_map=&_node_filter_map;
218 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
219 edge_filter_map=&_edge_filter_map;
223 // SubGraphWrapperBase(Graph& _graph,
224 // NodeFilterMap& _node_filter_map,
225 // EdgeFilterMap& _edge_filter_map) :
227 // node_filter_map(&node_filter_map),
228 // edge_filter_map(&edge_filter_map) { }
230 typedef typename Parent::Node Node;
231 typedef typename Parent::Edge Edge;
233 void first(Node& i) const {
235 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
237 void first(Edge& i) const {
239 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
241 void firstIn(Edge& i, const Node& n) const {
242 Parent::firstIn(i, n);
243 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
245 void firstOut(Edge& i, const Node& n) const {
246 Parent::firstOut(i, n);
247 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
250 void next(Node& i) const {
252 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
254 void next(Edge& i) const {
256 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
258 void nextIn(Edge& i) const {
260 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
262 void nextOut(Edge& i) const {
264 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
267 /// This function hides \c n in the graph, i.e. the iteration
268 /// jumps over it. This is done by simply setting the value of \c n
269 /// to be false in the corresponding node-map.
270 void hide(const Node& n) const { node_filter_map->set(n, false); }
272 /// This function hides \c e in the graph, i.e. the iteration
273 /// jumps over it. This is done by simply setting the value of \c e
274 /// to be false in the corresponding edge-map.
275 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
277 /// The value of \c n is set to be true in the node-map which stores
278 /// hide information. If \c n was hidden previuosly, then it is shown
280 void unHide(const Node& n) const { node_filter_map->set(n, true); }
282 /// The value of \c e is set to be true in the edge-map which stores
283 /// hide information. If \c e was hidden previuosly, then it is shown
285 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
287 /// Returns true if \c n is hidden.
288 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
290 /// Returns true if \c n is hidden.
291 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
293 /// \warning This is a linear time operation and works only if s
294 /// \c Graph::NodeIt is defined.
295 /// \todo assign tags.
296 int nodeNum() const {
299 for (first(n); n!=INVALID; next(n)) ++i;
303 /// \warning This is a linear time operation and works only if
304 /// \c Graph::EdgeIt is defined.
305 /// \todo assign tags.
306 int edgeNum() const {
309 for (first(e); e!=INVALID; next(e)) ++i;
316 /*! \brief A graph wrapper for hiding nodes and edges from a graph.
318 \warning Graph wrappers are in even more experimental state than the other
319 parts of the lib. Use them at you own risk.
321 SubGraphWrapper shows the graph with filtered node-set and
323 Let \f$G=(V, A)\f$ be a directed graph
324 and suppose that the graph instance \c g of type ListGraph implements
326 Let moreover \f$b_V\f$ and
327 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
328 SubGraphWrapper<...>::NodeIt iterates
329 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
330 SubGraphWrapper<...>::EdgeIt iterates
331 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
332 SubGraphWrapper<...>::OutEdgeIt and SubGraphWrapper<...>::InEdgeIt iterates
333 only on edges leaving and entering a specific node which have true value.
335 We have to note that this does not mean that an
336 induced subgraph is obtained, the node-iterator cares only the filter
337 on the node-set, and the edge-iterators care only the filter on the
340 typedef ListGraph Graph;
342 typedef Graph::Node Node;
343 typedef Graph::Edge Edge;
344 Node u=g.addNode(); //node of id 0
345 Node v=g.addNode(); //node of id 1
346 Node e=g.addEdge(u, v); //edge of id 0
347 Node f=g.addEdge(v, u); //edge of id 1
348 Graph::NodeMap<bool> nm(g, true);
350 Graph::EdgeMap<bool> em(g, true);
352 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
354 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
355 std::cout << ":-)" << std::endl;
356 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
358 The output of the above code is the following.
364 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
365 \c Graph::Node that is why \c g.id(n) can be applied.
367 For other examples see also the documentation of NodeSubGraphWrapper and
372 template<typename _Graph, typename NodeFilterMap,
373 typename EdgeFilterMap>
374 class SubGraphWrapper :
375 public IterableGraphExtender<
376 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
378 typedef _Graph Graph;
379 typedef IterableGraphExtender<
380 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
382 SubGraphWrapper() { }
384 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
385 EdgeFilterMap& _edge_filter_map) {
387 setNodeFilterMap(_node_filter_map);
388 setEdgeFilterMap(_edge_filter_map);
394 /*! \brief A wrapper for hiding nodes from a graph.
396 \warning Graph wrappers are in even more experimental state than the other
397 parts of the lib. Use them at you own risk.
399 A wrapper for hiding nodes from a graph.
400 This wrapper specializes SubGraphWrapper in the way that only the node-set
401 can be filtered. Note that this does not mean of considering induced
402 subgraph, the edge-iterators consider the original edge-set.
405 template<typename Graph, typename NodeFilterMap>
406 class NodeSubGraphWrapper :
407 public SubGraphWrapper<Graph, NodeFilterMap,
408 ConstMap<typename Graph::Edge,bool> > {
410 typedef SubGraphWrapper<Graph, NodeFilterMap,
411 ConstMap<typename Graph::Edge,bool> > Parent;
413 ConstMap<typename Graph::Edge, bool> const_true_map;
415 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
416 Parent(), const_true_map(true) {
417 Parent::setGraph(_graph);
418 Parent::setNodeFilterMap(_node_filter_map);
419 Parent::setEdgeFilterMap(const_true_map);
424 /*! \brief A wrapper for hiding edges from a graph.
426 \warning Graph wrappers are in even more experimental state than the other
427 parts of the lib. Use them at you own risk.
429 A wrapper for hiding edges from a graph.
430 This wrapper specializes SubGraphWrapper in the way that only the edge-set
431 can be filtered. The usefulness of this wrapper is demonstrated in the
432 problem of searching a maximum number of edge-disjoint shortest paths
434 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
435 non-negative edge-lengths. Note that
436 the comprehension of the presented solution
437 need's some knowledge from elementary combinatorial optimization.
439 If a single shortest path is to be
440 searched between two nodes \c s and \c t, then this can be done easily by
441 applying the Dijkstra algorithm class. What happens, if a maximum number of
442 edge-disjoint shortest paths is to be computed. It can be proved that an
443 edge can be in a shortest path if and only if it is tight with respect to
444 the potential function computed by Dijkstra. Moreover, any path containing
445 only such edges is a shortest one. Thus we have to compute a maximum number
446 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
447 all the tight edges. The computation will be demonstrated on the following
448 graph, which is read from a dimacs file.
451 digraph lemon_dot_example {
452 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
453 n0 [ label="0 (s)" ];
459 n6 [ label="6 (t)" ];
460 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
461 n5 -> n6 [ label="9, length:4" ];
462 n4 -> n6 [ label="8, length:2" ];
463 n3 -> n5 [ label="7, length:1" ];
464 n2 -> n5 [ label="6, length:3" ];
465 n2 -> n6 [ label="5, length:5" ];
466 n2 -> n4 [ label="4, length:2" ];
467 n1 -> n4 [ label="3, length:3" ];
468 n0 -> n3 [ label="2, length:1" ];
469 n0 -> n2 [ label="1, length:2" ];
470 n0 -> n1 [ label="0, length:3" ];
479 readDimacs(std::cin, g, length, s, t);
481 cout << "edges with lengths (of form id, source--length->target): " << endl;
482 for(EdgeIt e(g); e!=INVALID; ++e)
483 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
484 << length[e] << "->" << g.id(g.target(e)) << endl;
486 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
488 Next, the potential function is computed with Dijkstra.
490 typedef Dijkstra<Graph, LengthMap> Dijkstra;
491 Dijkstra dijkstra(g, length);
494 Next, we consrtruct a map which filters the edge-set to the tight edges.
496 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
498 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
500 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
501 SubGW gw(g, tight_edge_filter);
503 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
504 with a max flow algorithm Preflow.
506 ConstMap<Edge, int> const_1_map(1);
507 Graph::EdgeMap<int> flow(g, 0);
509 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
510 preflow(gw, s, t, const_1_map, flow);
515 cout << "maximum number of edge-disjoint shortest path: "
516 << preflow.flowValue() << endl;
517 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
519 for(EdgeIt e(g); e!=INVALID; ++e)
521 cout << " " << g.id(g.source(e)) << "--"
522 << length[e] << "->" << g.id(g.target(e)) << endl;
524 The program has the following (expected :-)) output:
526 edges with lengths (of form id, source--length->target):
538 maximum number of edge-disjoint shortest path: 2
539 edges of the maximum number of edge-disjoint shortest s-t paths:
550 template<typename Graph, typename EdgeFilterMap>
551 class EdgeSubGraphWrapper :
552 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
555 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
556 EdgeFilterMap> Parent;
558 ConstMap<typename Graph::Node, bool> const_true_map;
560 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
561 Parent(), const_true_map(true) {
562 Parent::setGraph(_graph);
563 Parent::setNodeFilterMap(const_true_map);
564 Parent::setEdgeFilterMap(_edge_filter_map);
569 template<typename Graph>
570 class UndirGraphWrapper : public GraphWrapper<Graph> {
572 typedef GraphWrapper<Graph> Parent;
574 UndirGraphWrapper() : GraphWrapper<Graph>() { }
577 typedef typename GraphWrapper<Graph>::Node Node;
578 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
579 typedef typename GraphWrapper<Graph>::Edge Edge;
580 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
582 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
585 friend class UndirGraphWrapper<Graph>;
586 bool out_or_in; //true iff out
587 typename Graph::OutEdgeIt out;
588 typename Graph::InEdgeIt in;
591 OutEdgeIt(const Invalid& i) : Edge(i) { }
592 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
593 out_or_in=true; _G.graph->first(out, _n);
594 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
596 operator Edge() const {
597 if (out_or_in) return Edge(out); else return Edge(in);
601 typedef OutEdgeIt InEdgeIt;
603 using GraphWrapper<Graph>::first;
604 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
605 i=OutEdgeIt(*this, p); return i;
608 using GraphWrapper<Graph>::next;
610 OutEdgeIt& next(OutEdgeIt& e) const {
612 typename Graph::Node n=this->graph->source(e.out);
613 this->graph->next(e.out);
614 if (!this->graph->valid(e.out)) {
615 e.out_or_in=false; this->graph->first(e.in, n); }
617 this->graph->next(e.in);
622 Node aNode(const OutEdgeIt& e) const {
623 if (e.out_or_in) return this->graph->source(e); else
624 return this->graph->target(e); }
625 Node bNode(const OutEdgeIt& e) const {
626 if (e.out_or_in) return this->graph->target(e); else
627 return this->graph->source(e); }
629 // KEEP_MAPS(Parent, UndirGraphWrapper);
633 // /// \brief An undirected graph template.
635 // ///\warning Graph wrappers are in even more experimental state than the other
636 // ///parts of the lib. Use them at your own risk.
638 // /// An undirected graph template.
639 // /// This class works as an undirected graph and a directed graph of
640 // /// class \c Graph is used for the physical storage.
641 // /// \ingroup graphs
642 template<typename Graph>
643 class UndirGraph : public UndirGraphWrapper<Graph> {
644 typedef UndirGraphWrapper<Graph> Parent;
648 UndirGraph() : UndirGraphWrapper<Graph>() {
649 Parent::setGraph(gr);
652 // KEEP_MAPS(Parent, UndirGraph);
656 template <typename _Graph,
657 typename ForwardFilterMap, typename BackwardFilterMap>
658 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
660 typedef _Graph Graph;
661 typedef GraphWrapperBase<_Graph> Parent;
663 ForwardFilterMap* forward_filter;
664 BackwardFilterMap* backward_filter;
665 SubBidirGraphWrapperBase() : Parent(),
666 forward_filter(0), backward_filter(0) { }
668 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
669 forward_filter=&_forward_filter;
671 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
672 backward_filter=&_backward_filter;
676 // SubGraphWrapperBase(Graph& _graph,
677 // NodeFilterMap& _node_filter_map,
678 // EdgeFilterMap& _edge_filter_map) :
680 // node_filter_map(&node_filter_map),
681 // edge_filter_map(&edge_filter_map) { }
683 typedef typename Parent::Node Node;
684 typedef typename _Graph::Edge GraphEdge;
685 template <typename T> class EdgeMap;
686 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
687 /// _Graph::Edge. It contains an extra bool flag which is true
688 /// if and only if the
689 /// edge is the backward version of the original edge.
690 class Edge : public _Graph::Edge {
691 friend class SubBidirGraphWrapperBase<
692 Graph, ForwardFilterMap, BackwardFilterMap>;
693 template<typename T> friend class EdgeMap;
695 bool backward; //true, iff backward
698 /// \todo =false is needed, or causes problems?
699 /// If \c _backward is false, then we get an edge corresponding to the
700 /// original one, otherwise its oppositely directed pair is obtained.
701 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
702 _Graph::Edge(e), backward(_backward) { }
703 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
704 bool operator==(const Edge& v) const {
705 return (this->backward==v.backward &&
706 static_cast<typename _Graph::Edge>(*this)==
707 static_cast<typename _Graph::Edge>(v));
709 bool operator!=(const Edge& v) const {
710 return (this->backward!=v.backward ||
711 static_cast<typename _Graph::Edge>(*this)!=
712 static_cast<typename _Graph::Edge>(v));
716 void first(Node& i) const {
720 void first(Edge& i) const {
723 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
724 !(*forward_filter)[i]) Parent::next(i);
725 if (*static_cast<GraphEdge*>(&i)==INVALID) {
728 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
729 !(*backward_filter)[i]) Parent::next(i);
733 void firstIn(Edge& i, const Node& n) const {
734 Parent::firstIn(i, n);
736 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
737 !(*forward_filter)[i]) Parent::nextOut(i);
738 if (*static_cast<GraphEdge*>(&i)==INVALID) {
739 Parent::firstOut(i, n);
741 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
742 !(*backward_filter)[i]) Parent::nextOut(i);
746 void firstOut(Edge& i, const Node& n) const {
747 Parent::firstOut(i, n);
749 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
750 !(*forward_filter)[i]) Parent::nextOut(i);
751 if (*static_cast<GraphEdge*>(&i)==INVALID) {
752 Parent::firstIn(i, n);
754 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
755 !(*backward_filter)[i]) Parent::nextIn(i);
759 void next(Node& i) const {
763 void next(Edge& i) const {
766 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767 !(*forward_filter)[i]) Parent::next(i);
768 if (*static_cast<GraphEdge*>(&i)==INVALID) {
771 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
772 !(*backward_filter)[i]) Parent::next(i);
776 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
777 !(*backward_filter)[i]) Parent::next(i);
781 void nextIn(Edge& i) const {
783 Node n=Parent::target(i);
785 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
786 !(*forward_filter)[i]) Parent::nextIn(i);
787 if (*static_cast<GraphEdge*>(&i)==INVALID) {
788 Parent::firstOut(i, n);
790 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
791 !(*backward_filter)[i]) Parent::nextOut(i);
795 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
796 !(*backward_filter)[i]) Parent::nextOut(i);
800 void nextOut(Edge& i) const {
802 Node n=Parent::source(i);
804 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
805 !(*forward_filter)[i]) Parent::nextOut(i);
806 if (*static_cast<GraphEdge*>(&i)==INVALID) {
807 Parent::firstIn(i, n);
809 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
810 !(*backward_filter)[i]) Parent::nextIn(i);
814 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
815 !(*backward_filter)[i]) Parent::nextIn(i);
819 Node source(Edge e) const {
820 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
821 Node target(Edge e) const {
822 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
824 /// Gives back the opposite edge.
825 Edge opposite(const Edge& e) const {
827 f.backward=!f.backward;
831 /// \warning This is a linear time operation and works only if
832 /// \c Graph::EdgeIt is defined.
834 int edgeNum() const {
837 for (first(e); e!=INVALID; next(e)) ++i;
841 bool forward(const Edge& e) const { return !e.backward; }
842 bool backward(const Edge& e) const { return e.backward; }
844 template <typename T>
845 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
846 /// _Graph::EdgeMap one for the forward edges and
847 /// one for the backward edges.
849 template <typename TT> friend class EdgeMap;
850 typename _Graph::template EdgeMap<T> forward_map, backward_map;
855 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
856 ForwardFilterMap, BackwardFilterMap>& g) :
857 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
859 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
860 ForwardFilterMap, BackwardFilterMap>& g, T a) :
861 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
863 void set(Edge e, T a) {
865 forward_map.set(e, a);
867 backward_map.set(e, a);
870 // typename _Graph::template EdgeMap<T>::ConstReference
871 // operator[](Edge e) const {
873 // return forward_map[e];
875 // return backward_map[e];
878 // typename _Graph::template EdgeMap<T>::Reference
879 T operator[](Edge e) const {
881 return forward_map[e];
883 return backward_map[e];
887 forward_map.update();
888 backward_map.update();
895 ///\brief A wrapper for composing a subgraph of a
896 /// bidirected graph made from a directed one.
898 /// A wrapper for composing a subgraph of a
899 /// bidirected graph made from a directed one.
901 ///\warning Graph wrappers are in even more experimental state than the other
902 ///parts of the lib. Use them at you own risk.
904 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
905 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
906 /// reversing its orientation. We are given moreover two bool valued
907 /// maps on the edge-set,
908 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
909 /// SubBidirGraphWrapper implements the graph structure with node-set
910 /// \f$V\f$ and edge-set
911 /// \f$\{e : e\in A \mbox{ and } forward\_filter(e) \mbox{ is true}\}+\{\bar e : e\in A \mbox{ and } backward\_filter(e) \mbox{ is true}\}\f$.
912 /// The purpose of writing + instead of union is because parallel
913 /// edges can arise. (Similarly, antiparallel edges also can arise).
914 /// In other words, a subgraph of the bidirected graph obtained, which
915 /// is given by orienting the edges of the original graph in both directions.
916 /// As the oppositely directed edges are logically different,
917 /// the maps are able to attach different values for them.
919 /// An example for such a construction is \c RevGraphWrapper where the
920 /// forward_filter is everywhere false and the backward_filter is
921 /// everywhere true. We note that for sake of efficiency,
922 /// \c RevGraphWrapper is implemented in a different way.
923 /// But BidirGraphWrapper is obtained from
924 /// SubBidirGraphWrapper by considering everywhere true
925 /// valued maps both for forward_filter and backward_filter.
926 /// Finally, one of the most important applications of SubBidirGraphWrapper
927 /// is ResGraphWrapper, which stands for the residual graph in directed
928 /// flow and circulation problems.
929 /// As wrappers usually, the SubBidirGraphWrapper implements the
930 /// above mentioned graph structure without its physical storage,
931 /// that is the whole stuff is stored in constant memory.
932 template<typename _Graph,
933 typename ForwardFilterMap, typename BackwardFilterMap>
934 class SubBidirGraphWrapper :
935 public IterableGraphExtender<
936 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
938 typedef _Graph Graph;
939 typedef IterableGraphExtender<
940 SubBidirGraphWrapperBase<
941 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
943 SubBidirGraphWrapper() { }
945 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
946 BackwardFilterMap& _backward_filter) {
948 setForwardFilterMap(_forward_filter);
949 setBackwardFilterMap(_backward_filter);
955 ///\brief A wrapper for composing bidirected graph from a directed one.
957 ///\warning Graph wrappers are in even more experimental state than the other
958 ///parts of the lib. Use them at you own risk.
960 /// A wrapper for composing bidirected graph from a directed one.
961 /// A bidirected graph is composed over the directed one without physical
962 /// storage. As the oppositely directed edges are logically different ones
963 /// the maps are able to attach different values for them.
964 template<typename Graph>
965 class BidirGraphWrapper :
966 public SubBidirGraphWrapper<
968 ConstMap<typename Graph::Edge, bool>,
969 ConstMap<typename Graph::Edge, bool> > {
971 typedef SubBidirGraphWrapper<
973 ConstMap<typename Graph::Edge, bool>,
974 ConstMap<typename Graph::Edge, bool> > Parent;
976 ConstMap<typename Graph::Edge, bool> cm;
978 BidirGraphWrapper() : Parent(), cm(true) {
979 Parent::setForwardFilterMap(cm);
980 Parent::setBackwardFilterMap(cm);
983 BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
984 Parent::setGraph(_graph);
985 Parent::setForwardFilterMap(cm);
986 Parent::setBackwardFilterMap(cm);
989 int edgeNum() const {
990 return 2*this->graph->edgeNum();
992 // KEEP_MAPS(Parent, BidirGraphWrapper);
996 template<typename Graph, typename Number,
997 typename CapacityMap, typename FlowMap>
998 class ResForwardFilter {
999 // const Graph* graph;
1000 const CapacityMap* capacity;
1001 const FlowMap* flow;
1003 ResForwardFilter(/*const Graph& _graph, */
1004 const CapacityMap& _capacity, const FlowMap& _flow) :
1005 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1006 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1007 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1008 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1009 bool operator[](const typename Graph::Edge& e) const {
1010 return (Number((*flow)[e]) < Number((*capacity)[e]));
1014 template<typename Graph, typename Number,
1015 typename CapacityMap, typename FlowMap>
1016 class ResBackwardFilter {
1017 const CapacityMap* capacity;
1018 const FlowMap* flow;
1020 ResBackwardFilter(/*const Graph& _graph,*/
1021 const CapacityMap& _capacity, const FlowMap& _flow) :
1022 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1023 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1024 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1025 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1026 bool operator[](const typename Graph::Edge& e) const {
1027 return (Number(0) < Number((*flow)[e]));
1032 /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
1034 A wrapper for composing the residual graph for directed flow and circulation problems.
1035 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1036 number type. Let moreover
1037 \f$f,c:A\to F\f$, be functions on the edge-set.
1038 In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
1039 and \f$c\f$ for a capacity function.
1040 Suppose that a graph instange \c g of type
1041 \c ListGraph implements \f$G\f$.
1045 Then RevGraphWrapper implements the graph structure with node-set
1046 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1047 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1048 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1049 i.e. the so called residual graph.
1050 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1051 multilicities are counted, i.e. if an edge is in both
1052 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
1054 The following code shows how
1055 such an instance can be constructed.
1057 typedef ListGraph Graph;
1058 Graph::EdgeMap<int> f(g);
1059 Graph::EdgeMap<int> c(g);
1060 ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1062 \author Marton Makai
1064 template<typename Graph, typename Number,
1065 typename CapacityMap, typename FlowMap>
1066 class ResGraphWrapper :
1067 public SubBidirGraphWrapper<
1069 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1070 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1072 typedef SubBidirGraphWrapper<
1074 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1075 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1077 const CapacityMap* capacity;
1079 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1080 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1081 ResGraphWrapper() : Parent(),
1082 capacity(0), flow(0) { }
1083 void setCapacityMap(const CapacityMap& _capacity) {
1084 capacity=&_capacity;
1085 forward_filter.setCapacity(_capacity);
1086 backward_filter.setCapacity(_capacity);
1088 void setFlowMap(FlowMap& _flow) {
1090 forward_filter.setFlow(_flow);
1091 backward_filter.setFlow(_flow);
1094 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1096 Parent(), capacity(&_capacity), flow(&_flow),
1097 forward_filter(/*_graph,*/ _capacity, _flow),
1098 backward_filter(/*_graph,*/ _capacity, _flow) {
1099 Parent::setGraph(_graph);
1100 Parent::setForwardFilterMap(forward_filter);
1101 Parent::setBackwardFilterMap(backward_filter);
1104 typedef typename Parent::Edge Edge;
1106 void augment(const Edge& e, Number a) const {
1107 if (Parent::forward(e))
1108 flow->set(e, (*flow)[e]+a);
1110 flow->set(e, (*flow)[e]-a);
1113 /// \brief Residual capacity map.
1115 /// In generic residual graphs the residual capacity can be obtained
1119 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1121 typedef Number Value;
1123 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1124 _res_graph) : res_graph(&_res_graph) { }
1125 Number operator[](const Edge& e) const {
1126 if (res_graph->forward(e))
1127 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1129 return (*(res_graph->flow))[e];
1133 // KEEP_MAPS(Parent, ResGraphWrapper);
1138 template <typename _Graph, typename FirstOutEdgesMap>
1139 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1141 typedef _Graph Graph;
1142 typedef GraphWrapperBase<_Graph> Parent;
1144 FirstOutEdgesMap* first_out_edges;
1145 ErasingFirstGraphWrapperBase() : Parent(),
1146 first_out_edges(0) { }
1148 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1149 first_out_edges=&_first_out_edges;
1154 typedef typename Parent::Node Node;
1155 typedef typename Parent::Edge Edge;
1157 void firstOut(Edge& i, const Node& n) const {
1158 i=(*first_out_edges)[n];
1161 void erase(const Edge& e) const {
1165 first_out_edges->set(n, f);
1170 /// For blocking flows.
1172 ///\warning Graph wrappers are in even more experimental state than the other
1173 ///parts of the lib. Use them at you own risk.
1175 /// This graph wrapper is used for on-the-fly
1176 /// Dinits blocking flow computations.
1177 /// For each node, an out-edge is stored which is used when the
1179 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1183 /// \author Marton Makai
1184 template <typename _Graph, typename FirstOutEdgesMap>
1185 class ErasingFirstGraphWrapper :
1186 public IterableGraphExtender<
1187 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1189 typedef _Graph Graph;
1190 typedef IterableGraphExtender<
1191 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1192 ErasingFirstGraphWrapper(Graph& _graph,
1193 FirstOutEdgesMap& _first_out_edges) {
1195 setFirstOutEdgesMap(_first_out_edges);
1204 #endif //LEMON_GRAPH_WRAPPER_H