Experimental autopackage specfile.
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>
37 /*! \addtogroup gwrappers
38 The main parts of LEMON are the different graph structures,
39 generic graph algorithms, graph concepts which couple these, and
40 graph wrappers. While the previous ones are more or less clear, the
41 latter notion needs further explanation.
42 Graph wrappers are graph classes which serve for considering graph
43 structures in different ways. A short example makes the notion much
45 Suppose that we have an instance \c g of a directed graph
46 type say \c ListGraph and an algorithm
47 \code template<typename Graph> int algorithm(const Graph&); \endcode
48 is needed to run on the reversely oriented graph.
49 It may be expensive (in time or in memory usage) to copy
50 \c g with the reverse orientation.
52 \code template<typename Graph> class RevGraphWrapper; \endcode is used.
53 The code looks as follows
56 RevGraphWrapper<ListGraph> rgw(g);
57 int result=algorithm(rgw);
59 After running the algorithm, the original graph \c g
60 remains untouched. Thus the graph wrapper used above is to consider the
61 original graph with reverse orientation.
62 This techniques gives rise to an elegant code, and
63 based on stable graph wrappers, complex algorithms can be
65 In flow, circulation and bipartite matching problems, the residual
66 graph is of particular importance. Combining a wrapper implementing
67 this, shortest path algorithms and minimum mean cycle algorithms,
68 a range of weighted and cardinality optimization algorithms can be
69 obtained. For lack of space, for other examples,
70 the interested user is referred to the detailed documentation of graph
72 The behavior of graph wrappers can be very different. Some of them keep
73 capabilities of the original graph while in other cases this would be
74 meaningless. This means that the concepts that they are a model of depend
75 on the graph wrapper, and the wrapped graph(s).
76 If an edge of \c rgw is deleted, this is carried out by
77 deleting the corresponding edge of \c g. But for a residual
78 graph, this operation has no sense.
79 Let we stand one more example here to simplify your work.
81 \code template<typename Graph> class RevGraphWrapper; \endcode
83 <tt> RevGraphWrapper(Graph& _g)</tt>.
84 This means that in a situation,
85 when a <tt> const ListGraph& </tt> reference to a graph is given,
86 then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
88 int algorithm1(const ListGraph& g) {
89 RevGraphWrapper<const ListGraph> rgw(g);
90 return algorithm2(rgw);
97 Base type for the Graph Wrappers
99 \warning Graph wrappers are in even more experimental state than the other
100 parts of the lib. Use them at you own risk.
102 This is the base type for most of LEMON graph wrappers.
103 This class implements a trivial graph wrapper i.e. it only wraps the
104 functions and types of the graph. The purpose of this class is to
105 make easier implementing graph wrappers. E.g. if a wrapper is
106 considered which differs from the wrapped graph only in some of its
107 functions or types, then it can be derived from GraphWrapper, and only the
108 differences should be implemented.
112 template<typename _Graph>
113 class GraphWrapperBase {
115 typedef _Graph Graph;
116 /// \todo Is it needed?
117 typedef Graph BaseGraph;
118 typedef Graph ParentGraph;
122 GraphWrapperBase() : graph(0) { }
123 void setGraph(Graph& _graph) { graph=&_graph; }
126 GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
128 typedef typename Graph::Node Node;
129 typedef typename Graph::Edge Edge;
131 void first(Node& i) const { graph->first(i); }
132 void first(Edge& i) const { graph->first(i); }
133 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
134 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
136 void next(Node& i) const { graph->next(i); }
137 void next(Edge& i) const { graph->next(i); }
138 void nextIn(Edge& i) const { graph->nextIn(i); }
139 void nextOut(Edge& i) const { graph->nextOut(i); }
141 Node source(const Edge& e) const { return graph->source(e); }
142 Node target(const Edge& e) const { return graph->target(e); }
144 int nodeNum() const { return graph->nodeNum(); }
145 int edgeNum() const { return graph->edgeNum(); }
147 Node addNode() const { return Node(graph->addNode()); }
148 Edge addEdge(const Node& source, const Node& target) const {
149 return Edge(graph->addEdge(source, target)); }
151 void erase(const Node& i) const { graph->erase(i); }
152 void erase(const Edge& i) const { graph->erase(i); }
154 void clear() const { graph->clear(); }
156 bool forward(const Edge& e) const { return graph->forward(e); }
157 bool backward(const Edge& e) const { return graph->backward(e); }
159 int id(const Node& v) const { return graph->id(v); }
160 int id(const Edge& e) const { return graph->id(e); }
162 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
164 template <typename _Value>
165 class NodeMap : public _Graph::template NodeMap<_Value> {
167 typedef typename _Graph::template NodeMap<_Value> Parent;
168 NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
169 NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
170 : Parent(*gw.graph, value) { }
173 template <typename _Value>
174 class EdgeMap : public _Graph::template EdgeMap<_Value> {
176 typedef typename _Graph::template EdgeMap<_Value> Parent;
177 EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
178 EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
179 : Parent(*gw.graph, value) { }
184 template <typename _Graph>
186 public IterableGraphExtender<GraphWrapperBase<_Graph> > {
188 typedef _Graph Graph;
189 typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
191 GraphWrapper() : Parent() { }
194 GraphWrapper(Graph& _graph) { setGraph(_graph); }
197 template <typename _Graph>
198 class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
200 typedef _Graph Graph;
201 typedef GraphWrapperBase<_Graph> Parent;
203 RevGraphWrapperBase() : Parent() { }
205 typedef typename Parent::Node Node;
206 typedef typename Parent::Edge Edge;
209 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
210 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
213 void nextIn(Edge& i) const { Parent::nextOut(i); }
214 void nextOut(Edge& i) const { Parent::nextIn(i); }
216 Node source(const Edge& e) const { return Parent::target(e); }
217 Node target(const Edge& e) const { return Parent::source(e); }
221 /// A graph wrapper which reverses the orientation of the edges.
223 ///\warning Graph wrappers are in even more experimental state than the other
224 ///parts of the lib. Use them at you own risk.
226 /// Let \f$G=(V, A)\f$ be a directed graph and
227 /// suppose that a graph instange \c g of type
228 /// \c ListGraph implements \f$G\f$.
232 /// For each directed edge
233 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
234 /// reversing its orientation.
235 /// Then RevGraphWrapper implements the graph structure with node-set
236 /// \f$V\f$ and edge-set
237 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
238 /// reversing the orientation of its edges. The following code shows how
239 /// such an instance can be constructed.
241 /// RevGraphWrapper<ListGraph> gw(g);
243 ///\author Marton Makai
244 template<typename _Graph>
245 class RevGraphWrapper :
246 public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
248 typedef _Graph Graph;
249 typedef IterableGraphExtender<
250 RevGraphWrapperBase<_Graph> > Parent;
252 RevGraphWrapper() { }
254 RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
258 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
259 class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
261 typedef _Graph Graph;
262 typedef GraphWrapperBase<_Graph> Parent;
264 NodeFilterMap* node_filter_map;
265 EdgeFilterMap* edge_filter_map;
266 SubGraphWrapperBase() : Parent(),
267 node_filter_map(0), edge_filter_map(0) { }
269 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
270 node_filter_map=&_node_filter_map;
272 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
273 edge_filter_map=&_edge_filter_map;
277 // SubGraphWrapperBase(Graph& _graph,
278 // NodeFilterMap& _node_filter_map,
279 // EdgeFilterMap& _edge_filter_map) :
281 // node_filter_map(&node_filter_map),
282 // edge_filter_map(&edge_filter_map) { }
284 typedef typename Parent::Node Node;
285 typedef typename Parent::Edge Edge;
287 void first(Node& i) const {
289 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
291 void first(Edge& i) const {
293 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
295 void firstIn(Edge& i, const Node& n) const {
296 Parent::firstIn(i, n);
297 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
299 void firstOut(Edge& i, const Node& n) const {
300 Parent::firstOut(i, n);
301 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
304 void next(Node& i) const {
306 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
308 void next(Edge& i) const {
310 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
312 void nextIn(Edge& i) const {
314 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
316 void nextOut(Edge& i) const {
318 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
321 /// This function hides \c n in the graph, i.e. the iteration
322 /// jumps over it. This is done by simply setting the value of \c n
323 /// to be false in the corresponding node-map.
324 void hide(const Node& n) const { node_filter_map->set(n, false); }
326 /// This function hides \c e in the graph, i.e. the iteration
327 /// jumps over it. This is done by simply setting the value of \c e
328 /// to be false in the corresponding edge-map.
329 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
331 /// The value of \c n is set to be true in the node-map which stores
332 /// hide information. If \c n was hidden previuosly, then it is shown
334 void unHide(const Node& n) const { node_filter_map->set(n, true); }
336 /// The value of \c e is set to be true in the edge-map which stores
337 /// hide information. If \c e was hidden previuosly, then it is shown
339 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
341 /// Returns true if \c n is hidden.
342 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
344 /// Returns true if \c n is hidden.
345 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
347 /// \warning This is a linear time operation and works only if s
348 /// \c Graph::NodeIt is defined.
349 /// \todo assign tags.
350 int nodeNum() const {
353 for (first(n); n!=INVALID; next(n)) ++i;
357 /// \warning This is a linear time operation and works only if
358 /// \c Graph::EdgeIt is defined.
359 /// \todo assign tags.
360 int edgeNum() const {
363 for (first(e); e!=INVALID; next(e)) ++i;
370 /*! \brief A graph wrapper for hiding nodes and edges from a graph.
372 \warning Graph wrappers are in even more experimental state than the other
373 parts of the lib. Use them at you own risk.
375 This wrapper shows a graph with filtered node-set and
377 Given a bool-valued map on the node-set and one on
378 the edge-set of the graph, the iterators show only the objects
379 having true value. We have to note that this does not mean that an
380 induced subgraph is obtained, the node-iterator cares only the filter
381 on the node-set, and the edge-iterators care only the filter on the
384 typedef SmartGraph Graph;
386 typedef Graph::Node Node;
387 typedef Graph::Edge Edge;
388 Node u=g.addNode(); //node of id 0
389 Node v=g.addNode(); //node of id 1
390 Node e=g.addEdge(u, v); //edge of id 0
391 Node f=g.addEdge(v, u); //edge of id 1
392 Graph::NodeMap<bool> nm(g, true);
394 Graph::EdgeMap<bool> em(g, true);
396 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
398 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
399 std::cout << ":-)" << std::endl;
400 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
402 The output of the above code is the following.
408 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
409 \c Graph::Node that is why \c g.id(n) can be applied.
411 For other examples see also the documentation of NodeSubGraphWrapper and
416 template<typename _Graph, typename NodeFilterMap,
417 typename EdgeFilterMap>
418 class SubGraphWrapper :
419 public IterableGraphExtender<
420 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
422 typedef _Graph Graph;
423 typedef IterableGraphExtender<
424 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
426 SubGraphWrapper() { }
428 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
429 EdgeFilterMap& _edge_filter_map) {
431 setNodeFilterMap(_node_filter_map);
432 setEdgeFilterMap(_edge_filter_map);
438 /*! \brief A wrapper for hiding nodes from a graph.
440 \warning Graph wrappers are in even more experimental state than the other
441 parts of the lib. Use them at you own risk.
443 A wrapper for hiding nodes from a graph.
444 This wrapper specializes SubGraphWrapper in the way that only the node-set
445 can be filtered. Note that this does not mean of considering induced
446 subgraph, the edge-iterators consider the original edge-set.
449 template<typename Graph, typename NodeFilterMap>
450 class NodeSubGraphWrapper :
451 public SubGraphWrapper<Graph, NodeFilterMap,
452 ConstMap<typename Graph::Edge,bool> > {
454 typedef SubGraphWrapper<Graph, NodeFilterMap,
455 ConstMap<typename Graph::Edge,bool> > Parent;
457 ConstMap<typename Graph::Edge, bool> const_true_map;
459 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
460 Parent(), const_true_map(true) {
461 Parent::setGraph(_graph);
462 Parent::setNodeFilterMap(_node_filter_map);
463 Parent::setEdgeFilterMap(const_true_map);
468 /*! \brief A wrapper for hiding edges from a graph.
470 \warning Graph wrappers are in even more experimental state than the other
471 parts of the lib. Use them at you own risk.
473 A wrapper for hiding edges from a graph.
474 This wrapper specializes SubGraphWrapper in the way that only the edge-set
475 can be filtered. The usefulness of this wrapper is demonstrated in the
476 problem of searching a maximum number of edge-disjoint shortest paths
478 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
479 non-negative edge-lengths. Note that
480 the comprehension of the presented solution
481 need's some knowledge from elementary combinatorial optimization.
483 If a single shortest path is to be
484 searched between two nodes \c s and \c t, then this can be done easily by
485 applying the Dijkstra algorithm class. What happens, if a maximum number of
486 edge-disjoint shortest paths is to be computed. It can be proved that an
487 edge can be in a shortest path if and only if it is tight with respect to
488 the potential function computed by Dijkstra. Moreover, any path containing
489 only such edges is a shortest one. Thus we have to compute a maximum number
490 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
491 all the tight edges. The computation will be demonstrated on the following
492 graph, which is read from a dimacs file.
495 digraph lemon_dot_example {
496 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
497 n0 [ label="0 (s)" ];
503 n6 [ label="6 (t)" ];
504 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
505 n5 -> n6 [ label="9, length:4" ];
506 n4 -> n6 [ label="8, length:2" ];
507 n3 -> n5 [ label="7, length:1" ];
508 n2 -> n5 [ label="6, length:3" ];
509 n2 -> n6 [ label="5, length:5" ];
510 n2 -> n4 [ label="4, length:2" ];
511 n1 -> n4 [ label="3, length:3" ];
512 n0 -> n3 [ label="2, length:1" ];
513 n0 -> n2 [ label="1, length:2" ];
514 n0 -> n1 [ label="0, length:3" ];
523 readDimacs(std::cin, g, length, s, t);
525 cout << "edges with lengths (of form id, source--length->target): " << endl;
526 for(EdgeIt e(g); e!=INVALID; ++e)
527 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
528 << length[e] << "->" << g.id(g.target(e)) << endl;
530 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
532 Next, the potential function is computed with Dijkstra.
534 typedef Dijkstra<Graph, LengthMap> Dijkstra;
535 Dijkstra dijkstra(g, length);
538 Next, we consrtruct a map which filters the edge-set to the tight edges.
540 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
542 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
544 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
545 SubGW gw(g, tight_edge_filter);
547 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
548 with a max flow algorithm Preflow.
550 ConstMap<Edge, int> const_1_map(1);
551 Graph::EdgeMap<int> flow(g, 0);
553 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
554 preflow(gw, s, t, const_1_map, flow);
559 cout << "maximum number of edge-disjoint shortest path: "
560 << preflow.flowValue() << endl;
561 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
563 for(EdgeIt e(g); e!=INVALID; ++e)
565 cout << " " << g.id(g.source(e)) << "--"
566 << length[e] << "->" << g.id(g.target(e)) << endl;
568 The program has the following (expected :-)) output:
570 edges with lengths (of form id, source--length->target):
582 maximum number of edge-disjoint shortest path: 2
583 edges of the maximum number of edge-disjoint shortest s-t paths:
594 template<typename Graph, typename EdgeFilterMap>
595 class EdgeSubGraphWrapper :
596 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
599 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
600 EdgeFilterMap> Parent;
602 ConstMap<typename Graph::Node, bool> const_true_map;
604 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
605 Parent(), const_true_map(true) {
606 Parent::setGraph(_graph);
607 Parent::setNodeFilterMap(const_true_map);
608 Parent::setEdgeFilterMap(_edge_filter_map);
613 template<typename Graph>
614 class UndirGraphWrapper : public GraphWrapper<Graph> {
616 typedef GraphWrapper<Graph> Parent;
618 UndirGraphWrapper() : GraphWrapper<Graph>() { }
621 typedef typename GraphWrapper<Graph>::Node Node;
622 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
623 typedef typename GraphWrapper<Graph>::Edge Edge;
624 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
626 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
629 friend class UndirGraphWrapper<Graph>;
630 bool out_or_in; //true iff out
631 typename Graph::OutEdgeIt out;
632 typename Graph::InEdgeIt in;
635 OutEdgeIt(const Invalid& i) : Edge(i) { }
636 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
637 out_or_in=true; _G.graph->first(out, _n);
638 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
640 operator Edge() const {
641 if (out_or_in) return Edge(out); else return Edge(in);
645 typedef OutEdgeIt InEdgeIt;
647 using GraphWrapper<Graph>::first;
648 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
649 i=OutEdgeIt(*this, p); return i;
652 using GraphWrapper<Graph>::next;
654 OutEdgeIt& next(OutEdgeIt& e) const {
656 typename Graph::Node n=this->graph->source(e.out);
657 this->graph->next(e.out);
658 if (!this->graph->valid(e.out)) {
659 e.out_or_in=false; this->graph->first(e.in, n); }
661 this->graph->next(e.in);
666 Node aNode(const OutEdgeIt& e) const {
667 if (e.out_or_in) return this->graph->source(e); else
668 return this->graph->target(e); }
669 Node bNode(const OutEdgeIt& e) const {
670 if (e.out_or_in) return this->graph->target(e); else
671 return this->graph->source(e); }
673 // KEEP_MAPS(Parent, UndirGraphWrapper);
677 // /// \brief An undirected graph template.
679 // ///\warning Graph wrappers are in even more experimental state than the other
680 // ///parts of the lib. Use them at your own risk.
682 // /// An undirected graph template.
683 // /// This class works as an undirected graph and a directed graph of
684 // /// class \c Graph is used for the physical storage.
685 // /// \ingroup graphs
686 template<typename Graph>
687 class UndirGraph : public UndirGraphWrapper<Graph> {
688 typedef UndirGraphWrapper<Graph> Parent;
692 UndirGraph() : UndirGraphWrapper<Graph>() {
693 Parent::setGraph(gr);
696 // KEEP_MAPS(Parent, UndirGraph);
700 template <typename _Graph,
701 typename ForwardFilterMap, typename BackwardFilterMap>
702 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
704 typedef _Graph Graph;
705 typedef GraphWrapperBase<_Graph> Parent;
707 ForwardFilterMap* forward_filter;
708 BackwardFilterMap* backward_filter;
709 SubBidirGraphWrapperBase() : Parent(),
710 forward_filter(0), backward_filter(0) { }
712 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
713 forward_filter=&_forward_filter;
715 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
716 backward_filter=&_backward_filter;
720 // SubGraphWrapperBase(Graph& _graph,
721 // NodeFilterMap& _node_filter_map,
722 // EdgeFilterMap& _edge_filter_map) :
724 // node_filter_map(&node_filter_map),
725 // edge_filter_map(&edge_filter_map) { }
727 typedef typename Parent::Node Node;
728 typedef typename _Graph::Edge GraphEdge;
729 template <typename T> class EdgeMap;
730 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
731 /// _Graph::Edge. It contains an extra bool flag which is true
732 /// if and only if the
733 /// edge is the backward version of the original edge.
734 class Edge : public _Graph::Edge {
735 friend class SubBidirGraphWrapperBase<
736 Graph, ForwardFilterMap, BackwardFilterMap>;
737 template<typename T> friend class EdgeMap;
739 bool backward; //true, iff backward
742 /// \todo =false is needed, or causes problems?
743 /// If \c _backward is false, then we get an edge corresponding to the
744 /// original one, otherwise its oppositely directed pair is obtained.
745 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
746 _Graph::Edge(e), backward(_backward) { }
747 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
748 bool operator==(const Edge& v) const {
749 return (this->backward==v.backward &&
750 static_cast<typename _Graph::Edge>(*this)==
751 static_cast<typename _Graph::Edge>(v));
753 bool operator!=(const Edge& v) const {
754 return (this->backward!=v.backward ||
755 static_cast<typename _Graph::Edge>(*this)!=
756 static_cast<typename _Graph::Edge>(v));
760 void first(Node& i) const {
764 void first(Edge& i) const {
767 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
768 !(*forward_filter)[i]) Parent::next(i);
769 if (*static_cast<GraphEdge*>(&i)==INVALID) {
772 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
773 !(*backward_filter)[i]) Parent::next(i);
777 void firstIn(Edge& i, const Node& n) const {
778 Parent::firstIn(i, n);
780 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
781 !(*forward_filter)[i]) Parent::nextOut(i);
782 if (*static_cast<GraphEdge*>(&i)==INVALID) {
783 Parent::firstOut(i, n);
785 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
786 !(*backward_filter)[i]) Parent::nextOut(i);
790 void firstOut(Edge& i, const Node& n) const {
791 Parent::firstOut(i, n);
793 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
794 !(*forward_filter)[i]) Parent::nextOut(i);
795 if (*static_cast<GraphEdge*>(&i)==INVALID) {
796 Parent::firstIn(i, n);
798 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
799 !(*backward_filter)[i]) Parent::nextIn(i);
803 void next(Node& i) const {
807 void next(Edge& i) const {
810 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
811 !(*forward_filter)[i]) Parent::next(i);
812 if (*static_cast<GraphEdge*>(&i)==INVALID) {
815 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
816 !(*backward_filter)[i]) Parent::next(i);
820 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
821 !(*backward_filter)[i]) Parent::next(i);
825 void nextIn(Edge& i) const {
827 Node n=Parent::target(i);
829 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
830 !(*forward_filter)[i]) Parent::nextIn(i);
831 if (*static_cast<GraphEdge*>(&i)==INVALID) {
832 Parent::firstOut(i, n);
834 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
835 !(*backward_filter)[i]) Parent::nextOut(i);
839 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
840 !(*backward_filter)[i]) Parent::nextOut(i);
844 void nextOut(Edge& i) const {
846 Node n=Parent::source(i);
848 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
849 !(*forward_filter)[i]) Parent::nextOut(i);
850 if (*static_cast<GraphEdge*>(&i)==INVALID) {
851 Parent::firstIn(i, n);
853 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
854 !(*backward_filter)[i]) Parent::nextIn(i);
858 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
859 !(*backward_filter)[i]) Parent::nextIn(i);
863 Node source(Edge e) const {
864 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
865 Node target(Edge e) const {
866 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
868 /// Gives back the opposite edge.
869 Edge opposite(const Edge& e) const {
871 f.backward=!f.backward;
875 /// \warning This is a linear time operation and works only if
876 /// \c Graph::EdgeIt is defined.
878 int edgeNum() const {
881 for (first(e); e!=INVALID; next(e)) ++i;
885 bool forward(const Edge& e) const { return !e.backward; }
886 bool backward(const Edge& e) const { return e.backward; }
888 template <typename T>
889 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
890 /// _Graph::EdgeMap one for the forward edges and
891 /// one for the backward edges.
893 template <typename TT> friend class EdgeMap;
894 typename _Graph::template EdgeMap<T> forward_map, backward_map;
899 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
900 ForwardFilterMap, BackwardFilterMap>& g) :
901 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
903 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
904 ForwardFilterMap, BackwardFilterMap>& g, T a) :
905 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
907 void set(Edge e, T a) {
909 forward_map.set(e, a);
911 backward_map.set(e, a);
914 // typename _Graph::template EdgeMap<T>::ConstReference
915 // operator[](Edge e) const {
917 // return forward_map[e];
919 // return backward_map[e];
922 // typename _Graph::template EdgeMap<T>::Reference
923 T operator[](Edge e) const {
925 return forward_map[e];
927 return backward_map[e];
931 forward_map.update();
932 backward_map.update();
939 ///\brief A wrapper for composing a subgraph of a
940 /// bidirected graph made from a directed one.
942 /// A wrapper for composing a subgraph of a
943 /// bidirected graph made from a directed one.
945 ///\warning Graph wrappers are in even more experimental state than the other
946 ///parts of the lib. Use them at you own risk.
948 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
949 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
950 /// reversing its orientation. We are given moreover two bool valued
951 /// maps on the edge-set,
952 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
953 /// SubBidirGraphWrapper implements the graph structure with node-set
954 /// \f$V\f$ and edge-set
955 /// \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$.
956 /// The purpose of writing + instead of union is because parallel
957 /// edges can arise. (Similarly, antiparallel edges also can arise).
958 /// In other words, a subgraph of the bidirected graph obtained, which
959 /// is given by orienting the edges of the original graph in both directions.
960 /// As the oppositely directed edges are logically different,
961 /// the maps are able to attach different values for them.
963 /// An example for such a construction is \c RevGraphWrapper where the
964 /// forward_filter is everywhere false and the backward_filter is
965 /// everywhere true. We note that for sake of efficiency,
966 /// \c RevGraphWrapper is implemented in a different way.
967 /// But BidirGraphWrapper is obtained from
968 /// SubBidirGraphWrapper by considering everywhere true
969 /// valued maps both for forward_filter and backward_filter.
970 /// Finally, one of the most important applications of SubBidirGraphWrapper
971 /// is ResGraphWrapper, which stands for the residual graph in directed
972 /// flow and circulation problems.
973 /// As wrappers usually, the SubBidirGraphWrapper implements the
974 /// above mentioned graph structure without its physical storage,
975 /// that is the whole stuff is stored in constant memory.
976 template<typename _Graph,
977 typename ForwardFilterMap, typename BackwardFilterMap>
978 class SubBidirGraphWrapper :
979 public IterableGraphExtender<
980 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
982 typedef _Graph Graph;
983 typedef IterableGraphExtender<
984 SubBidirGraphWrapperBase<
985 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
987 SubBidirGraphWrapper() { }
989 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
990 BackwardFilterMap& _backward_filter) {
992 setForwardFilterMap(_forward_filter);
993 setBackwardFilterMap(_backward_filter);
999 ///\brief A wrapper for composing bidirected graph from a directed one.
1001 ///\warning Graph wrappers are in even more experimental state than the other
1002 ///parts of the lib. Use them at you own risk.
1004 /// A wrapper for composing bidirected graph from a directed one.
1005 /// A bidirected graph is composed over the directed one without physical
1006 /// storage. As the oppositely directed edges are logically different ones
1007 /// the maps are able to attach different values for them.
1008 template<typename Graph>
1009 class BidirGraphWrapper :
1010 public SubBidirGraphWrapper<
1012 ConstMap<typename Graph::Edge, bool>,
1013 ConstMap<typename Graph::Edge, bool> > {
1015 typedef SubBidirGraphWrapper<
1017 ConstMap<typename Graph::Edge, bool>,
1018 ConstMap<typename Graph::Edge, bool> > Parent;
1020 ConstMap<typename Graph::Edge, bool> cm;
1022 BidirGraphWrapper() : Parent(), cm(true) {
1023 Parent::setForwardFilterMap(cm);
1024 Parent::setBackwardFilterMap(cm);
1027 BidirGraphWrapper(Graph& _graph) : Parent() {
1028 Parent::setGraph(_graph);
1029 Parent::setForwardFilterMap(cm);
1030 Parent::setBackwardFilterMap(cm);
1033 int edgeNum() const {
1034 return 2*this->graph->edgeNum();
1036 // KEEP_MAPS(Parent, BidirGraphWrapper);
1040 template<typename Graph, typename Number,
1041 typename CapacityMap, typename FlowMap>
1042 class ResForwardFilter {
1043 // const Graph* graph;
1044 const CapacityMap* capacity;
1045 const FlowMap* flow;
1047 ResForwardFilter(/*const Graph& _graph, */
1048 const CapacityMap& _capacity, const FlowMap& _flow) :
1049 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1050 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1051 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1052 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1053 bool operator[](const typename Graph::Edge& e) const {
1054 return (Number((*flow)[e]) < Number((*capacity)[e]));
1058 template<typename Graph, typename Number,
1059 typename CapacityMap, typename FlowMap>
1060 class ResBackwardFilter {
1061 const CapacityMap* capacity;
1062 const FlowMap* flow;
1064 ResBackwardFilter(/*const Graph& _graph,*/
1065 const CapacityMap& _capacity, const FlowMap& _flow) :
1066 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1067 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1068 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1069 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1070 bool operator[](const typename Graph::Edge& e) const {
1071 return (Number(0) < Number((*flow)[e]));
1076 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1078 ///\warning Graph wrappers are in even more experimental state than the other
1079 ///parts of the lib. Use them at you own risk.
1081 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1082 template<typename Graph, typename Number,
1083 typename CapacityMap, typename FlowMap>
1084 class ResGraphWrapper :
1085 public SubBidirGraphWrapper<
1087 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1088 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1090 typedef SubBidirGraphWrapper<
1092 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1093 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1095 const CapacityMap* capacity;
1097 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1098 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1099 ResGraphWrapper() : Parent(),
1100 capacity(0), flow(0) { }
1101 void setCapacityMap(const CapacityMap& _capacity) {
1102 capacity=&_capacity;
1103 forward_filter.setCapacity(_capacity);
1104 backward_filter.setCapacity(_capacity);
1106 void setFlowMap(FlowMap& _flow) {
1108 forward_filter.setFlow(_flow);
1109 backward_filter.setFlow(_flow);
1112 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1114 Parent(), capacity(&_capacity), flow(&_flow),
1115 forward_filter(/*_graph,*/ _capacity, _flow),
1116 backward_filter(/*_graph,*/ _capacity, _flow) {
1117 Parent::setGraph(_graph);
1118 Parent::setForwardFilterMap(forward_filter);
1119 Parent::setBackwardFilterMap(backward_filter);
1122 typedef typename Parent::Edge Edge;
1124 void augment(const Edge& e, Number a) const {
1125 if (Parent::forward(e))
1126 flow->set(e, (*flow)[e]+a);
1128 flow->set(e, (*flow)[e]-a);
1131 /// \brief Residual capacity map.
1133 /// In generic residual graphs the residual capacity can be obtained
1137 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1139 typedef Number Value;
1141 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1142 _res_graph) : res_graph(&_res_graph) { }
1143 Number operator[](const Edge& e) const {
1144 if (res_graph->forward(e))
1145 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1147 return (*(res_graph->flow))[e];
1151 // KEEP_MAPS(Parent, ResGraphWrapper);
1156 template <typename _Graph, typename FirstOutEdgesMap>
1157 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1159 typedef _Graph Graph;
1160 typedef GraphWrapperBase<_Graph> Parent;
1162 FirstOutEdgesMap* first_out_edges;
1163 ErasingFirstGraphWrapperBase() : Parent(),
1164 first_out_edges(0) { }
1166 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1167 first_out_edges=&_first_out_edges;
1172 typedef typename Parent::Node Node;
1173 typedef typename Parent::Edge Edge;
1175 void firstOut(Edge& i, const Node& n) const {
1176 i=(*first_out_edges)[n];
1179 void erase(const Edge& e) const {
1183 first_out_edges->set(n, f);
1188 /// For blocking flows.
1190 ///\warning Graph wrappers are in even more experimental state than the other
1191 ///parts of the lib. Use them at you own risk.
1193 /// This graph wrapper is used for on-the-fly
1194 /// Dinits blocking flow computations.
1195 /// For each node, an out-edge is stored which is used when the
1197 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1201 /// \author Marton Makai
1202 template <typename _Graph, typename FirstOutEdgesMap>
1203 class ErasingFirstGraphWrapper :
1204 public IterableGraphExtender<
1205 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1207 typedef _Graph Graph;
1208 typedef IterableGraphExtender<
1209 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1210 ErasingFirstGraphWrapper(Graph& _graph,
1211 FirstOutEdgesMap& _first_out_edges) {
1213 setFirstOutEdgesMap(_first_out_edges);
1222 #endif //LEMON_GRAPH_WRAPPER_H