- A primitive function type interface for Preflow.
- A compilation bug fixed
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 This wrapper shows a graph with filtered node-set and
323 Given a bool-valued map on the node-set and one on
324 the edge-set of the graph, the iterators show only the objects
325 having true value. We have to note that this does not mean that an
326 induced subgraph is obtained, the node-iterator cares only the filter
327 on the node-set, and the edge-iterators care only the filter on the
330 typedef SmartGraph Graph;
332 typedef Graph::Node Node;
333 typedef Graph::Edge Edge;
334 Node u=g.addNode(); //node of id 0
335 Node v=g.addNode(); //node of id 1
336 Node e=g.addEdge(u, v); //edge of id 0
337 Node f=g.addEdge(v, u); //edge of id 1
338 Graph::NodeMap<bool> nm(g, true);
340 Graph::EdgeMap<bool> em(g, true);
342 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
344 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
345 std::cout << ":-)" << std::endl;
346 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
348 The output of the above code is the following.
354 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
355 \c Graph::Node that is why \c g.id(n) can be applied.
357 For other examples see also the documentation of NodeSubGraphWrapper and
362 template<typename _Graph, typename NodeFilterMap,
363 typename EdgeFilterMap>
364 class SubGraphWrapper :
365 public IterableGraphExtender<
366 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
368 typedef _Graph Graph;
369 typedef IterableGraphExtender<
370 SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
372 SubGraphWrapper() { }
374 SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
375 EdgeFilterMap& _edge_filter_map) {
377 setNodeFilterMap(_node_filter_map);
378 setEdgeFilterMap(_edge_filter_map);
384 /*! \brief A wrapper for hiding nodes from a graph.
386 \warning Graph wrappers are in even more experimental state than the other
387 parts of the lib. Use them at you own risk.
389 A wrapper for hiding nodes from a graph.
390 This wrapper specializes SubGraphWrapper in the way that only the node-set
391 can be filtered. Note that this does not mean of considering induced
392 subgraph, the edge-iterators consider the original edge-set.
395 template<typename Graph, typename NodeFilterMap>
396 class NodeSubGraphWrapper :
397 public SubGraphWrapper<Graph, NodeFilterMap,
398 ConstMap<typename Graph::Edge,bool> > {
400 typedef SubGraphWrapper<Graph, NodeFilterMap,
401 ConstMap<typename Graph::Edge,bool> > Parent;
403 ConstMap<typename Graph::Edge, bool> const_true_map;
405 NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
406 Parent(), const_true_map(true) {
407 Parent::setGraph(_graph);
408 Parent::setNodeFilterMap(_node_filter_map);
409 Parent::setEdgeFilterMap(const_true_map);
414 /*! \brief A wrapper for hiding edges from a graph.
416 \warning Graph wrappers are in even more experimental state than the other
417 parts of the lib. Use them at you own risk.
419 A wrapper for hiding edges from a graph.
420 This wrapper specializes SubGraphWrapper in the way that only the edge-set
421 can be filtered. The usefulness of this wrapper is demonstrated in the
422 problem of searching a maximum number of edge-disjoint shortest paths
424 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
425 non-negative edge-lengths. Note that
426 the comprehension of the presented solution
427 need's some knowledge from elementary combinatorial optimization.
429 If a single shortest path is to be
430 searched between two nodes \c s and \c t, then this can be done easily by
431 applying the Dijkstra algorithm class. What happens, if a maximum number of
432 edge-disjoint shortest paths is to be computed. It can be proved that an
433 edge can be in a shortest path if and only if it is tight with respect to
434 the potential function computed by Dijkstra. Moreover, any path containing
435 only such edges is a shortest one. Thus we have to compute a maximum number
436 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
437 all the tight edges. The computation will be demonstrated on the following
438 graph, which is read from a dimacs file.
441 digraph lemon_dot_example {
442 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
443 n0 [ label="0 (s)" ];
449 n6 [ label="6 (t)" ];
450 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
451 n5 -> n6 [ label="9, length:4" ];
452 n4 -> n6 [ label="8, length:2" ];
453 n3 -> n5 [ label="7, length:1" ];
454 n2 -> n5 [ label="6, length:3" ];
455 n2 -> n6 [ label="5, length:5" ];
456 n2 -> n4 [ label="4, length:2" ];
457 n1 -> n4 [ label="3, length:3" ];
458 n0 -> n3 [ label="2, length:1" ];
459 n0 -> n2 [ label="1, length:2" ];
460 n0 -> n1 [ label="0, length:3" ];
469 readDimacs(std::cin, g, length, s, t);
471 cout << "edges with lengths (of form id, source--length->target): " << endl;
472 for(EdgeIt e(g); e!=INVALID; ++e)
473 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
474 << length[e] << "->" << g.id(g.target(e)) << endl;
476 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
478 Next, the potential function is computed with Dijkstra.
480 typedef Dijkstra<Graph, LengthMap> Dijkstra;
481 Dijkstra dijkstra(g, length);
484 Next, we consrtruct a map which filters the edge-set to the tight edges.
486 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
488 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
490 typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
491 SubGW gw(g, tight_edge_filter);
493 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
494 with a max flow algorithm Preflow.
496 ConstMap<Edge, int> const_1_map(1);
497 Graph::EdgeMap<int> flow(g, 0);
499 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
500 preflow(gw, s, t, const_1_map, flow);
505 cout << "maximum number of edge-disjoint shortest path: "
506 << preflow.flowValue() << endl;
507 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
509 for(EdgeIt e(g); e!=INVALID; ++e)
511 cout << " " << g.id(g.source(e)) << "--"
512 << length[e] << "->" << g.id(g.target(e)) << endl;
514 The program has the following (expected :-)) output:
516 edges with lengths (of form id, source--length->target):
528 maximum number of edge-disjoint shortest path: 2
529 edges of the maximum number of edge-disjoint shortest s-t paths:
540 template<typename Graph, typename EdgeFilterMap>
541 class EdgeSubGraphWrapper :
542 public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
545 typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
546 EdgeFilterMap> Parent;
548 ConstMap<typename Graph::Node, bool> const_true_map;
550 EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
551 Parent(), const_true_map(true) {
552 Parent::setGraph(_graph);
553 Parent::setNodeFilterMap(const_true_map);
554 Parent::setEdgeFilterMap(_edge_filter_map);
559 template<typename Graph>
560 class UndirGraphWrapper : public GraphWrapper<Graph> {
562 typedef GraphWrapper<Graph> Parent;
564 UndirGraphWrapper() : GraphWrapper<Graph>() { }
567 typedef typename GraphWrapper<Graph>::Node Node;
568 typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
569 typedef typename GraphWrapper<Graph>::Edge Edge;
570 typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
572 UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
575 friend class UndirGraphWrapper<Graph>;
576 bool out_or_in; //true iff out
577 typename Graph::OutEdgeIt out;
578 typename Graph::InEdgeIt in;
581 OutEdgeIt(const Invalid& i) : Edge(i) { }
582 OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
583 out_or_in=true; _G.graph->first(out, _n);
584 if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
586 operator Edge() const {
587 if (out_or_in) return Edge(out); else return Edge(in);
591 typedef OutEdgeIt InEdgeIt;
593 using GraphWrapper<Graph>::first;
594 OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
595 i=OutEdgeIt(*this, p); return i;
598 using GraphWrapper<Graph>::next;
600 OutEdgeIt& next(OutEdgeIt& e) const {
602 typename Graph::Node n=this->graph->source(e.out);
603 this->graph->next(e.out);
604 if (!this->graph->valid(e.out)) {
605 e.out_or_in=false; this->graph->first(e.in, n); }
607 this->graph->next(e.in);
612 Node aNode(const OutEdgeIt& e) const {
613 if (e.out_or_in) return this->graph->source(e); else
614 return this->graph->target(e); }
615 Node bNode(const OutEdgeIt& e) const {
616 if (e.out_or_in) return this->graph->target(e); else
617 return this->graph->source(e); }
619 // KEEP_MAPS(Parent, UndirGraphWrapper);
623 // /// \brief An undirected graph template.
625 // ///\warning Graph wrappers are in even more experimental state than the other
626 // ///parts of the lib. Use them at your own risk.
628 // /// An undirected graph template.
629 // /// This class works as an undirected graph and a directed graph of
630 // /// class \c Graph is used for the physical storage.
631 // /// \ingroup graphs
632 template<typename Graph>
633 class UndirGraph : public UndirGraphWrapper<Graph> {
634 typedef UndirGraphWrapper<Graph> Parent;
638 UndirGraph() : UndirGraphWrapper<Graph>() {
639 Parent::setGraph(gr);
642 // KEEP_MAPS(Parent, UndirGraph);
646 template <typename _Graph,
647 typename ForwardFilterMap, typename BackwardFilterMap>
648 class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
650 typedef _Graph Graph;
651 typedef GraphWrapperBase<_Graph> Parent;
653 ForwardFilterMap* forward_filter;
654 BackwardFilterMap* backward_filter;
655 SubBidirGraphWrapperBase() : Parent(),
656 forward_filter(0), backward_filter(0) { }
658 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
659 forward_filter=&_forward_filter;
661 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
662 backward_filter=&_backward_filter;
666 // SubGraphWrapperBase(Graph& _graph,
667 // NodeFilterMap& _node_filter_map,
668 // EdgeFilterMap& _edge_filter_map) :
670 // node_filter_map(&node_filter_map),
671 // edge_filter_map(&edge_filter_map) { }
673 typedef typename Parent::Node Node;
674 typedef typename _Graph::Edge GraphEdge;
675 template <typename T> class EdgeMap;
676 /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
677 /// _Graph::Edge. It contains an extra bool flag which is true
678 /// if and only if the
679 /// edge is the backward version of the original edge.
680 class Edge : public _Graph::Edge {
681 friend class SubBidirGraphWrapperBase<
682 Graph, ForwardFilterMap, BackwardFilterMap>;
683 template<typename T> friend class EdgeMap;
685 bool backward; //true, iff backward
688 /// \todo =false is needed, or causes problems?
689 /// If \c _backward is false, then we get an edge corresponding to the
690 /// original one, otherwise its oppositely directed pair is obtained.
691 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
692 _Graph::Edge(e), backward(_backward) { }
693 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
694 bool operator==(const Edge& v) const {
695 return (this->backward==v.backward &&
696 static_cast<typename _Graph::Edge>(*this)==
697 static_cast<typename _Graph::Edge>(v));
699 bool operator!=(const Edge& v) const {
700 return (this->backward!=v.backward ||
701 static_cast<typename _Graph::Edge>(*this)!=
702 static_cast<typename _Graph::Edge>(v));
706 void first(Node& i) const {
710 void first(Edge& i) const {
713 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
714 !(*forward_filter)[i]) Parent::next(i);
715 if (*static_cast<GraphEdge*>(&i)==INVALID) {
718 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
719 !(*backward_filter)[i]) Parent::next(i);
723 void firstIn(Edge& i, const Node& n) const {
724 Parent::firstIn(i, n);
726 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
727 !(*forward_filter)[i]) Parent::nextOut(i);
728 if (*static_cast<GraphEdge*>(&i)==INVALID) {
729 Parent::firstOut(i, n);
731 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
732 !(*backward_filter)[i]) Parent::nextOut(i);
736 void firstOut(Edge& i, const Node& n) const {
737 Parent::firstOut(i, n);
739 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
740 !(*forward_filter)[i]) Parent::nextOut(i);
741 if (*static_cast<GraphEdge*>(&i)==INVALID) {
742 Parent::firstIn(i, n);
744 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
745 !(*backward_filter)[i]) Parent::nextIn(i);
749 void next(Node& i) const {
753 void next(Edge& i) const {
756 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
757 !(*forward_filter)[i]) Parent::next(i);
758 if (*static_cast<GraphEdge*>(&i)==INVALID) {
761 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762 !(*backward_filter)[i]) Parent::next(i);
766 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767 !(*backward_filter)[i]) Parent::next(i);
771 void nextIn(Edge& i) const {
773 Node n=Parent::target(i);
775 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
776 !(*forward_filter)[i]) Parent::nextIn(i);
777 if (*static_cast<GraphEdge*>(&i)==INVALID) {
778 Parent::firstOut(i, n);
780 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
781 !(*backward_filter)[i]) Parent::nextOut(i);
785 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
786 !(*backward_filter)[i]) Parent::nextOut(i);
790 void nextOut(Edge& i) const {
792 Node n=Parent::source(i);
794 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
795 !(*forward_filter)[i]) Parent::nextOut(i);
796 if (*static_cast<GraphEdge*>(&i)==INVALID) {
797 Parent::firstIn(i, n);
799 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
800 !(*backward_filter)[i]) Parent::nextIn(i);
804 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
805 !(*backward_filter)[i]) Parent::nextIn(i);
809 Node source(Edge e) const {
810 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
811 Node target(Edge e) const {
812 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
814 /// Gives back the opposite edge.
815 Edge opposite(const Edge& e) const {
817 f.backward=!f.backward;
821 /// \warning This is a linear time operation and works only if
822 /// \c Graph::EdgeIt is defined.
824 int edgeNum() const {
827 for (first(e); e!=INVALID; next(e)) ++i;
831 bool forward(const Edge& e) const { return !e.backward; }
832 bool backward(const Edge& e) const { return e.backward; }
834 template <typename T>
835 /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
836 /// _Graph::EdgeMap one for the forward edges and
837 /// one for the backward edges.
839 template <typename TT> friend class EdgeMap;
840 typename _Graph::template EdgeMap<T> forward_map, backward_map;
845 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
846 ForwardFilterMap, BackwardFilterMap>& g) :
847 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
849 EdgeMap(const SubBidirGraphWrapperBase<_Graph,
850 ForwardFilterMap, BackwardFilterMap>& g, T a) :
851 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
853 void set(Edge e, T a) {
855 forward_map.set(e, a);
857 backward_map.set(e, a);
860 // typename _Graph::template EdgeMap<T>::ConstReference
861 // operator[](Edge e) const {
863 // return forward_map[e];
865 // return backward_map[e];
868 // typename _Graph::template EdgeMap<T>::Reference
869 T operator[](Edge e) const {
871 return forward_map[e];
873 return backward_map[e];
877 forward_map.update();
878 backward_map.update();
885 ///\brief A wrapper for composing a subgraph of a
886 /// bidirected graph made from a directed one.
888 /// A wrapper for composing a subgraph of a
889 /// bidirected graph made from a directed one.
891 ///\warning Graph wrappers are in even more experimental state than the other
892 ///parts of the lib. Use them at you own risk.
894 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
895 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
896 /// reversing its orientation. We are given moreover two bool valued
897 /// maps on the edge-set,
898 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
899 /// SubBidirGraphWrapper implements the graph structure with node-set
900 /// \f$V\f$ and edge-set
901 /// \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$.
902 /// The purpose of writing + instead of union is because parallel
903 /// edges can arise. (Similarly, antiparallel edges also can arise).
904 /// In other words, a subgraph of the bidirected graph obtained, which
905 /// is given by orienting the edges of the original graph in both directions.
906 /// As the oppositely directed edges are logically different,
907 /// the maps are able to attach different values for them.
909 /// An example for such a construction is \c RevGraphWrapper where the
910 /// forward_filter is everywhere false and the backward_filter is
911 /// everywhere true. We note that for sake of efficiency,
912 /// \c RevGraphWrapper is implemented in a different way.
913 /// But BidirGraphWrapper is obtained from
914 /// SubBidirGraphWrapper by considering everywhere true
915 /// valued maps both for forward_filter and backward_filter.
916 /// Finally, one of the most important applications of SubBidirGraphWrapper
917 /// is ResGraphWrapper, which stands for the residual graph in directed
918 /// flow and circulation problems.
919 /// As wrappers usually, the SubBidirGraphWrapper implements the
920 /// above mentioned graph structure without its physical storage,
921 /// that is the whole stuff is stored in constant memory.
922 template<typename _Graph,
923 typename ForwardFilterMap, typename BackwardFilterMap>
924 class SubBidirGraphWrapper :
925 public IterableGraphExtender<
926 SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
928 typedef _Graph Graph;
929 typedef IterableGraphExtender<
930 SubBidirGraphWrapperBase<
931 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
933 SubBidirGraphWrapper() { }
935 SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
936 BackwardFilterMap& _backward_filter) {
938 setForwardFilterMap(_forward_filter);
939 setBackwardFilterMap(_backward_filter);
945 ///\brief A wrapper for composing bidirected graph from a directed one.
947 ///\warning Graph wrappers are in even more experimental state than the other
948 ///parts of the lib. Use them at you own risk.
950 /// A wrapper for composing bidirected graph from a directed one.
951 /// A bidirected graph is composed over the directed one without physical
952 /// storage. As the oppositely directed edges are logically different ones
953 /// the maps are able to attach different values for them.
954 template<typename Graph>
955 class BidirGraphWrapper :
956 public SubBidirGraphWrapper<
958 ConstMap<typename Graph::Edge, bool>,
959 ConstMap<typename Graph::Edge, bool> > {
961 typedef SubBidirGraphWrapper<
963 ConstMap<typename Graph::Edge, bool>,
964 ConstMap<typename Graph::Edge, bool> > Parent;
966 ConstMap<typename Graph::Edge, bool> cm;
968 BidirGraphWrapper() : Parent(), cm(true) {
969 Parent::setForwardFilterMap(cm);
970 Parent::setBackwardFilterMap(cm);
973 BidirGraphWrapper(Graph& _graph) : Parent(), cm(true) {
974 Parent::setGraph(_graph);
975 Parent::setForwardFilterMap(cm);
976 Parent::setBackwardFilterMap(cm);
979 int edgeNum() const {
980 return 2*this->graph->edgeNum();
982 // KEEP_MAPS(Parent, BidirGraphWrapper);
986 template<typename Graph, typename Number,
987 typename CapacityMap, typename FlowMap>
988 class ResForwardFilter {
989 // const Graph* graph;
990 const CapacityMap* capacity;
993 ResForwardFilter(/*const Graph& _graph, */
994 const CapacityMap& _capacity, const FlowMap& _flow) :
995 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
996 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
997 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
998 void setFlow(const FlowMap& _flow) { flow=&_flow; }
999 bool operator[](const typename Graph::Edge& e) const {
1000 return (Number((*flow)[e]) < Number((*capacity)[e]));
1004 template<typename Graph, typename Number,
1005 typename CapacityMap, typename FlowMap>
1006 class ResBackwardFilter {
1007 const CapacityMap* capacity;
1008 const FlowMap* flow;
1010 ResBackwardFilter(/*const Graph& _graph,*/
1011 const CapacityMap& _capacity, const FlowMap& _flow) :
1012 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1013 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1014 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1015 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1016 bool operator[](const typename Graph::Edge& e) const {
1017 return (Number(0) < Number((*flow)[e]));
1022 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1024 ///\warning Graph wrappers are in even more experimental state than the other
1025 ///parts of the lib. Use them at you own risk.
1027 /// A wrapper for composing the residual graph for directed flow and circulation problems.
1028 template<typename Graph, typename Number,
1029 typename CapacityMap, typename FlowMap>
1030 class ResGraphWrapper :
1031 public SubBidirGraphWrapper<
1033 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1034 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1036 typedef SubBidirGraphWrapper<
1038 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1039 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1041 const CapacityMap* capacity;
1043 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1044 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1045 ResGraphWrapper() : Parent(),
1046 capacity(0), flow(0) { }
1047 void setCapacityMap(const CapacityMap& _capacity) {
1048 capacity=&_capacity;
1049 forward_filter.setCapacity(_capacity);
1050 backward_filter.setCapacity(_capacity);
1052 void setFlowMap(FlowMap& _flow) {
1054 forward_filter.setFlow(_flow);
1055 backward_filter.setFlow(_flow);
1058 ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
1060 Parent(), capacity(&_capacity), flow(&_flow),
1061 forward_filter(/*_graph,*/ _capacity, _flow),
1062 backward_filter(/*_graph,*/ _capacity, _flow) {
1063 Parent::setGraph(_graph);
1064 Parent::setForwardFilterMap(forward_filter);
1065 Parent::setBackwardFilterMap(backward_filter);
1068 typedef typename Parent::Edge Edge;
1070 void augment(const Edge& e, Number a) const {
1071 if (Parent::forward(e))
1072 flow->set(e, (*flow)[e]+a);
1074 flow->set(e, (*flow)[e]-a);
1077 /// \brief Residual capacity map.
1079 /// In generic residual graphs the residual capacity can be obtained
1083 const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
1085 typedef Number Value;
1087 ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
1088 _res_graph) : res_graph(&_res_graph) { }
1089 Number operator[](const Edge& e) const {
1090 if (res_graph->forward(e))
1091 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1093 return (*(res_graph->flow))[e];
1097 // KEEP_MAPS(Parent, ResGraphWrapper);
1102 template <typename _Graph, typename FirstOutEdgesMap>
1103 class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
1105 typedef _Graph Graph;
1106 typedef GraphWrapperBase<_Graph> Parent;
1108 FirstOutEdgesMap* first_out_edges;
1109 ErasingFirstGraphWrapperBase() : Parent(),
1110 first_out_edges(0) { }
1112 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1113 first_out_edges=&_first_out_edges;
1118 typedef typename Parent::Node Node;
1119 typedef typename Parent::Edge Edge;
1121 void firstOut(Edge& i, const Node& n) const {
1122 i=(*first_out_edges)[n];
1125 void erase(const Edge& e) const {
1129 first_out_edges->set(n, f);
1134 /// For blocking flows.
1136 ///\warning Graph wrappers are in even more experimental state than the other
1137 ///parts of the lib. Use them at you own risk.
1139 /// This graph wrapper is used for on-the-fly
1140 /// Dinits blocking flow computations.
1141 /// For each node, an out-edge is stored which is used when the
1143 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1147 /// \author Marton Makai
1148 template <typename _Graph, typename FirstOutEdgesMap>
1149 class ErasingFirstGraphWrapper :
1150 public IterableGraphExtender<
1151 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
1153 typedef _Graph Graph;
1154 typedef IterableGraphExtender<
1155 ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
1156 ErasingFirstGraphWrapper(Graph& _graph,
1157 FirstOutEdgesMap& _first_out_edges) {
1159 setFirstOutEdgesMap(_first_out_edges);
1168 #endif //LEMON_GRAPH_WRAPPER_H