Correct the english name of EGRES.
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 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_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/bits/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 elementary knowledge from combinatorial optimization.
439 If a single shortest path is to be
440 searched between \c s and \c t, then this can be done easily by
441 applying the Dijkstra algorithm. 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::nextIn(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.
927 /// The most important application of SubBidirGraphWrapper
928 /// is ResGraphWrapper, which stands for the residual graph in directed
929 /// flow and circulation problems.
930 /// As wrappers usually, the SubBidirGraphWrapper implements the
931 /// above mentioned graph structure without its physical storage,
932 /// that is the whole stuff is stored in constant memory.
933 template<typename _Graph,
934 typename ForwardFilterMap, typename BackwardFilterMap>
935 class SubBidirGraphWrapper :
936 public IterableGraphExtender<
937 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
939 typedef _Graph Graph;
940 typedef IterableGraphExtender<
941 SubBidirGraphWrapperBase<
942 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
944 SubBidirGraphWrapper() { }
946 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
947 BackwardFilterMap& _backward_filter) {
949 setForwardFilterMap(_forward_filter);
950 setBackwardFilterMap(_backward_filter);
956 ///\brief A wrapper for composing bidirected graph from a directed one.
958 ///\warning Graph wrappers are in even more experimental state than the other
959 ///parts of the lib. Use them at you own risk.
961 /// A wrapper for composing bidirected graph from a directed one.
962 /// A bidirected graph is composed over the directed one without physical
963 /// storage. As the oppositely directed edges are logically different ones
964 /// the maps are able to attach different values for them.
965 template<typename Graph>
966 class BidirGraphWrapper :
967 public SubBidirGraphWrapper<
969 ConstMap<typename Graph::Edge, bool>,
970 ConstMap<typename Graph::Edge, bool> > {
972 typedef SubBidirGraphWrapper<
974 ConstMap<typename Graph::Edge, bool>,
975 ConstMap<typename Graph::Edge, bool> > Parent;
977 ConstMap<typename Graph::Edge, bool> cm;
979 BidirGraphWrapper() : Parent(), cm(true) {
980 Parent::setForwardFilterMap(cm);
981 Parent::setBackwardFilterMap(cm);
984 BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
985 Parent::setGraph(_graph);
986 Parent::setForwardFilterMap(cm);
987 Parent::setBackwardFilterMap(cm);
990 int edgeNum() const {
991 return 2*this->graph->edgeNum();
993 // KEEP_MAPS(Parent, BidirGraphWrapper);
997 template<typename Graph, typename Number,
998 typename CapacityMap, typename FlowMap>
999 class ResForwardFilter {
1000 // const Graph* graph;
1001 const CapacityMap* capacity;
1002 const FlowMap* flow;
1004 ResForwardFilter(/*const Graph& _graph, */
1005 const CapacityMap& _capacity, const FlowMap& _flow) :
1006 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1007 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1008 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1009 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1010 bool operator[](const typename Graph::Edge& e) const {
1011 return (Number((*flow)[e]) < Number((*capacity)[e]));
1015 template<typename Graph, typename Number,
1016 typename CapacityMap, typename FlowMap>
1017 class ResBackwardFilter {
1018 const CapacityMap* capacity;
1019 const FlowMap* flow;
1021 ResBackwardFilter(/*const Graph& _graph,*/
1022 const CapacityMap& _capacity, const FlowMap& _flow) :
1023 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1024 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1025 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1026 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1027 bool operator[](const typename Graph::Edge& e) const {
1028 return (Number(0) < Number((*flow)[e]));
1033 /*! \brief A wrapper for composing the residual graph for directed flow and circulation problems.
1035 A wrapper for composing the residual graph for directed flow and circulation problems.
1036 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1037 number type. Let moreover
1038 \f$f,c:A\to F\f$, be functions on the edge-set.
1039 In the appications of ResGraphWrapper, \f$f\f$ usually stands for a flow
1040 and \f$c\f$ for a capacity function.
1041 Suppose that a graph instange \c g of type
1042 \c ListGraph implements \f$G\f$.
1046 Then RevGraphWrapper implements the graph structure with node-set
1047 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1048 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1049 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1050 i.e. the so called residual graph.
1051 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1052 multilicities are counted, i.e. if an edge is in both
1053 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the wrapper it
1055 The following code shows how
1056 such an instance can be constructed.
1058 typedef ListGraph Graph;
1059 Graph::EdgeMap<int> f(g);
1060 Graph::EdgeMap<int> c(g);
1061 ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1063 \author Marton Makai
1065 template<typename Graph, typename Number,
1066 typename CapacityMap, typename FlowMap>
1067 class ResGraphWrapper :
1068 public SubBidirGraphWrapper<
1070 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1071 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1073 typedef SubBidirGraphWrapper<
1075 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1076 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1078 const CapacityMap* capacity;
1080 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1081 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1082 ResGraphWrapper() : Parent(),
1083 capacity(0), flow(0) { }
1084 void setCapacityMap(const CapacityMap& _capacity) {
1085 capacity=&_capacity;
1086 forward_filter.setCapacity(_capacity);
1087 backward_filter.setCapacity(_capacity);
1089 void setFlowMap(FlowMap& _flow) {
1091 forward_filter.setFlow(_flow);
1092 backward_filter.setFlow(_flow);
1095 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1097 Parent(), capacity(&_capacity), flow(&_flow),
1098 forward_filter(/*_graph,*/ _capacity, _flow),
1099 backward_filter(/*_graph,*/ _capacity, _flow) {
1100 Parent::setGraph(_graph);
1101 Parent::setForwardFilterMap(forward_filter);
1102 Parent::setBackwardFilterMap(backward_filter);
1105 typedef typename Parent::Edge Edge;
1107 void augment(const Edge& e, Number a) const {
1108 if (Parent::forward(e))
1109 flow->set(e, (*flow)[e]+a);
1111 flow->set(e, (*flow)[e]-a);
1114 /// \brief Residual capacity map.
1116 /// In generic residual graphs the residual capacity can be obtained
1120 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1122 typedef Number Value;
1124 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1125 _res_graph) : res_graph(&_res_graph) { }
1126 Number operator[](const Edge& e) const {
1127 if (res_graph->forward(e))
1128 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1130 return (*(res_graph->flow))[e];
1134 // KEEP_MAPS(Parent, ResGraphWrapper);
1139 template <typename _Graph, typename FirstOutEdgesMap>
1140 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1142 typedef _Graph Graph;
1143 typedef GraphWrapperBase<_Graph> Parent;
1145 FirstOutEdgesMap* first_out_edges;
1146 ErasingFirstGraphWrapperBase() : Parent(),
1147 first_out_edges(0) { }
1149 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1150 first_out_edges=&_first_out_edges;
1155 typedef typename Parent::Node Node;
1156 typedef typename Parent::Edge Edge;
1158 void firstOut(Edge& i, const Node& n) const {
1159 i=(*first_out_edges)[n];
1162 void erase(const Edge& e) const {
1166 first_out_edges->set(n, f);
1171 /// For blocking flows.
1173 ///\warning Graph wrappers are in even more experimental state than the other
1174 ///parts of the lib. Use them at you own risk.
1176 /// This graph wrapper is used for on-the-fly
1177 /// Dinits blocking flow computations.
1178 /// For each node, an out-edge is stored which is used when the
1180 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1184 /// \author Marton Makai
1185 template <typename _Graph, typename FirstOutEdgesMap>
1186 class ErasingFirstGraphWrapper :
1187 public IterableGraphExtender<
1188 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1190 typedef _Graph Graph;
1191 typedef IterableGraphExtender<
1192 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1193 ErasingFirstGraphWrapper(Graph& _graph,
1194 FirstOutEdgesMap& _first_out_edges) {
1196 setFirstOutEdgesMap(_first_out_edges);
1205 #endif //LEMON_GRAPH_WRAPPER_H