IO with undirected edgesets and undirected graphs.
Missing features:
InfoReader,
aliased edges in undir edgesets
2 * src/lemon/graph_adaptor.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_ADAPTOR_H
18 #define LEMON_GRAPH_ADAPTOR_H
20 ///\ingroup graph_adaptors
22 ///\brief Several graph adaptors.
24 ///This file contains several useful graph adaptor functions.
26 ///\author Marton Makai
28 #include <lemon/invalid.h>
29 #include <lemon/maps.h>
30 #include <lemon/bits/iterable_graph_extender.h>
31 #include <lemon/bits/undir_graph_extender.h>
39 \addtogroup graph_adaptors
44 Base type for the Graph Adaptors
46 \warning Graph adaptors are in even more experimental state than the other
47 parts of the lib. Use them at you own risk.
49 This is the base type for most of LEMON graph adaptors.
50 This class implements a trivial graph adaptor i.e. it only wraps the
51 functions and types of the graph. The purpose of this class is to
52 make easier implementing graph adaptors. E.g. if an adaptor is
53 considered which differs from the wrapped graph only in some of its
54 functions or types, then it can be derived from GraphAdaptor, and only the
55 differences should be implemented.
59 template<typename _Graph>
60 class GraphAdaptorBase {
63 /// \todo Is it needed?
64 typedef Graph BaseGraph;
65 typedef Graph ParentGraph;
69 GraphAdaptorBase() : graph(0) { }
70 void setGraph(Graph& _graph) { graph=&_graph; }
73 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
75 typedef typename Graph::Node Node;
76 typedef typename Graph::Edge Edge;
78 void first(Node& i) const { graph->first(i); }
79 void first(Edge& i) const { graph->first(i); }
80 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
81 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
83 void next(Node& i) const { graph->next(i); }
84 void next(Edge& i) const { graph->next(i); }
85 void nextIn(Edge& i) const { graph->nextIn(i); }
86 void nextOut(Edge& i) const { graph->nextOut(i); }
88 Node source(const Edge& e) const { return graph->source(e); }
89 Node target(const Edge& e) const { return graph->target(e); }
91 int nodeNum() const { return graph->nodeNum(); }
92 int edgeNum() const { return graph->edgeNum(); }
94 Node addNode() const { return Node(graph->addNode()); }
95 Edge addEdge(const Node& source, const Node& target) const {
96 return Edge(graph->addEdge(source, target)); }
98 void erase(const Node& i) const { graph->erase(i); }
99 void erase(const Edge& i) const { graph->erase(i); }
101 void clear() const { graph->clear(); }
103 bool forward(const Edge& e) const { return graph->forward(e); }
104 bool backward(const Edge& e) const { return graph->backward(e); }
106 int id(const Node& v) const { return graph->id(v); }
107 int id(const Edge& e) const { return graph->id(e); }
109 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
111 template <typename _Value>
112 class NodeMap : public _Graph::template NodeMap<_Value> {
114 typedef typename _Graph::template NodeMap<_Value> Parent;
115 NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
116 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
117 : Parent(*gw.graph, value) { }
120 template <typename _Value>
121 class EdgeMap : public _Graph::template EdgeMap<_Value> {
123 typedef typename _Graph::template EdgeMap<_Value> Parent;
124 EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
125 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
126 : Parent(*gw.graph, value) { }
131 template <typename _Graph>
133 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
135 typedef _Graph Graph;
136 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
138 GraphAdaptor() : Parent() { }
141 GraphAdaptor(Graph& _graph) { setGraph(_graph); }
144 template <typename _Graph>
145 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
147 typedef _Graph Graph;
148 typedef GraphAdaptorBase<_Graph> Parent;
150 RevGraphAdaptorBase() : Parent() { }
152 typedef typename Parent::Node Node;
153 typedef typename Parent::Edge Edge;
155 // using Parent::first;
156 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
157 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
159 // using Parent::next;
160 void nextIn(Edge& i) const { Parent::nextOut(i); }
161 void nextOut(Edge& i) const { Parent::nextIn(i); }
163 Node source(const Edge& e) const { return Parent::target(e); }
164 Node target(const Edge& e) const { return Parent::source(e); }
168 /// A graph adaptor which reverses the orientation of the edges.
170 ///\warning Graph adaptors are in even more experimental state than the other
171 ///parts of the lib. Use them at you own risk.
173 /// Let \f$G=(V, A)\f$ be a directed graph and
174 /// suppose that a graph instange \c g of type
175 /// \c ListGraph implements \f$G\f$.
179 /// For each directed edge
180 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
181 /// reversing its orientation.
182 /// Then RevGraphAdaptor implements the graph structure with node-set
183 /// \f$V\f$ and edge-set
184 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
185 /// reversing the orientation of its edges. The following code shows how
186 /// such an instance can be constructed.
188 /// RevGraphAdaptor<ListGraph> gw(g);
190 ///\author Marton Makai
191 template<typename _Graph>
192 class RevGraphAdaptor :
193 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
195 typedef _Graph Graph;
196 typedef IterableGraphExtender<
197 RevGraphAdaptorBase<_Graph> > Parent;
199 RevGraphAdaptor() { }
201 RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
205 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
206 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
208 typedef _Graph Graph;
209 typedef GraphAdaptorBase<_Graph> Parent;
211 NodeFilterMap* node_filter_map;
212 EdgeFilterMap* edge_filter_map;
213 SubGraphAdaptorBase() : Parent(),
214 node_filter_map(0), edge_filter_map(0) { }
216 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
217 node_filter_map=&_node_filter_map;
219 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
220 edge_filter_map=&_edge_filter_map;
224 // SubGraphAdaptorBase(Graph& _graph,
225 // NodeFilterMap& _node_filter_map,
226 // EdgeFilterMap& _edge_filter_map) :
228 // node_filter_map(&node_filter_map),
229 // edge_filter_map(&edge_filter_map) { }
231 typedef typename Parent::Node Node;
232 typedef typename Parent::Edge Edge;
234 void first(Node& i) const {
236 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
238 void first(Edge& i) const {
240 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
242 void firstIn(Edge& i, const Node& n) const {
243 Parent::firstIn(i, n);
244 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
246 void firstOut(Edge& i, const Node& n) const {
247 Parent::firstOut(i, n);
248 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
251 void next(Node& i) const {
253 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
255 void next(Edge& i) const {
257 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
259 void nextIn(Edge& i) const {
261 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
263 void nextOut(Edge& i) const {
265 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
268 /// This function hides \c n in the graph, i.e. the iteration
269 /// jumps over it. This is done by simply setting the value of \c n
270 /// to be false in the corresponding node-map.
271 void hide(const Node& n) const { node_filter_map->set(n, false); }
273 /// This function hides \c e in the graph, i.e. the iteration
274 /// jumps over it. This is done by simply setting the value of \c e
275 /// to be false in the corresponding edge-map.
276 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
278 /// The value of \c n is set to be true in the node-map which stores
279 /// hide information. If \c n was hidden previuosly, then it is shown
281 void unHide(const Node& n) const { node_filter_map->set(n, true); }
283 /// The value of \c e is set to be true in the edge-map which stores
284 /// hide information. If \c e was hidden previuosly, then it is shown
286 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
288 /// Returns true if \c n is hidden.
289 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
291 /// Returns true if \c n is hidden.
292 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
294 /// \warning This is a linear time operation and works only if s
295 /// \c Graph::NodeIt is defined.
296 /// \todo assign tags.
297 int nodeNum() const {
300 for (first(n); n!=INVALID; next(n)) ++i;
304 /// \warning This is a linear time operation and works only if
305 /// \c Graph::EdgeIt is defined.
306 /// \todo assign tags.
307 int edgeNum() const {
310 for (first(e); e!=INVALID; next(e)) ++i;
317 /*! \brief A graph adaptor for hiding nodes and edges from a graph.
319 \warning Graph adaptors are in even more experimental state than the other
320 parts of the lib. Use them at you own risk.
322 SubGraphAdaptor shows the graph with filtered node-set and
324 Let \f$G=(V, A)\f$ be a directed graph
325 and suppose that the graph instance \c g of type ListGraph implements
327 Let moreover \f$b_V\f$ and
328 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
329 SubGraphAdaptor<...>::NodeIt iterates
330 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
331 SubGraphAdaptor<...>::EdgeIt iterates
332 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
333 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
334 only on edges leaving and entering a specific node which have true value.
336 We have to note that this does not mean that an
337 induced subgraph is obtained, the node-iterator cares only the filter
338 on the node-set, and the edge-iterators care only the filter on the
341 typedef ListGraph Graph;
343 typedef Graph::Node Node;
344 typedef Graph::Edge Edge;
345 Node u=g.addNode(); //node of id 0
346 Node v=g.addNode(); //node of id 1
347 Node e=g.addEdge(u, v); //edge of id 0
348 Node f=g.addEdge(v, u); //edge of id 1
349 Graph::NodeMap<bool> nm(g, true);
351 Graph::EdgeMap<bool> em(g, true);
353 typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
355 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
356 std::cout << ":-)" << std::endl;
357 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
359 The output of the above code is the following.
365 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
366 \c Graph::Node that is why \c g.id(n) can be applied.
368 For other examples see also the documentation of NodeSubGraphAdaptor and
373 template<typename _Graph, typename NodeFilterMap,
374 typename EdgeFilterMap>
375 class SubGraphAdaptor :
376 public IterableGraphExtender<
377 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
379 typedef _Graph Graph;
380 typedef IterableGraphExtender<
381 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
383 SubGraphAdaptor() { }
385 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
386 EdgeFilterMap& _edge_filter_map) {
388 setNodeFilterMap(_node_filter_map);
389 setEdgeFilterMap(_edge_filter_map);
395 /*! \brief An adaptor for hiding nodes from a graph.
397 \warning Graph adaptors are in even more experimental state than the other
398 parts of the lib. Use them at you own risk.
400 An adaptor for hiding nodes from a graph.
401 This adaptor specializes SubGraphAdaptor in the way that only the node-set
402 can be filtered. Note that this does not mean of considering induced
403 subgraph, the edge-iterators consider the original edge-set.
406 template<typename Graph, typename NodeFilterMap>
407 class NodeSubGraphAdaptor :
408 public SubGraphAdaptor<Graph, NodeFilterMap,
409 ConstMap<typename Graph::Edge,bool> > {
411 typedef SubGraphAdaptor<Graph, NodeFilterMap,
412 ConstMap<typename Graph::Edge,bool> > Parent;
414 ConstMap<typename Graph::Edge, bool> const_true_map;
416 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
417 Parent(), const_true_map(true) {
418 Parent::setGraph(_graph);
419 Parent::setNodeFilterMap(_node_filter_map);
420 Parent::setEdgeFilterMap(const_true_map);
425 /*! \brief An adaptor for hiding edges from a graph.
427 \warning Graph adaptors are in even more experimental state than the other
428 parts of the lib. Use them at you own risk.
430 An adaptor for hiding edges from a graph.
431 This adaptor specializes SubGraphAdaptor in the way that only the edge-set
432 can be filtered. The usefulness of this adaptor is demonstrated in the
433 problem of searching a maximum number of edge-disjoint shortest paths
435 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
436 non-negative edge-lengths. Note that
437 the comprehension of the presented solution
438 need's some elementary knowledge from combinatorial optimization.
440 If a single shortest path is to be
441 searched between \c s and \c t, then this can be done easily by
442 applying the Dijkstra algorithm. What happens, if a maximum number of
443 edge-disjoint shortest paths is to be computed. It can be proved that an
444 edge can be in a shortest path if and only if it is tight with respect to
445 the potential function computed by Dijkstra. Moreover, any path containing
446 only such edges is a shortest one. Thus we have to compute a maximum number
447 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
448 all the tight edges. The computation will be demonstrated on the following
449 graph, which is read from a dimacs file.
452 digraph lemon_dot_example {
453 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
454 n0 [ label="0 (s)" ];
460 n6 [ label="6 (t)" ];
461 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
462 n5 -> n6 [ label="9, length:4" ];
463 n4 -> n6 [ label="8, length:2" ];
464 n3 -> n5 [ label="7, length:1" ];
465 n2 -> n5 [ label="6, length:3" ];
466 n2 -> n6 [ label="5, length:5" ];
467 n2 -> n4 [ label="4, length:2" ];
468 n1 -> n4 [ label="3, length:3" ];
469 n0 -> n3 [ label="2, length:1" ];
470 n0 -> n2 [ label="1, length:2" ];
471 n0 -> n1 [ label="0, length:3" ];
480 readDimacs(std::cin, g, length, s, t);
482 cout << "edges with lengths (of form id, source--length->target): " << endl;
483 for(EdgeIt e(g); e!=INVALID; ++e)
484 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
485 << length[e] << "->" << g.id(g.target(e)) << endl;
487 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
489 Next, the potential function is computed with Dijkstra.
491 typedef Dijkstra<Graph, LengthMap> Dijkstra;
492 Dijkstra dijkstra(g, length);
495 Next, we consrtruct a map which filters the edge-set to the tight edges.
497 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
499 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
501 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
502 SubGW gw(g, tight_edge_filter);
504 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
505 with a max flow algorithm Preflow.
507 ConstMap<Edge, int> const_1_map(1);
508 Graph::EdgeMap<int> flow(g, 0);
510 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
511 preflow(gw, s, t, const_1_map, flow);
516 cout << "maximum number of edge-disjoint shortest path: "
517 << preflow.flowValue() << endl;
518 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
520 for(EdgeIt e(g); e!=INVALID; ++e)
522 cout << " " << g.id(g.source(e)) << "--"
523 << length[e] << "->" << g.id(g.target(e)) << endl;
525 The program has the following (expected :-)) output:
527 edges with lengths (of form id, source--length->target):
539 maximum number of edge-disjoint shortest path: 2
540 edges of the maximum number of edge-disjoint shortest s-t paths:
551 template<typename Graph, typename EdgeFilterMap>
552 class EdgeSubGraphAdaptor :
553 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
556 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
557 EdgeFilterMap> Parent;
559 ConstMap<typename Graph::Node, bool> const_true_map;
561 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
562 Parent(), const_true_map(true) {
563 Parent::setGraph(_graph);
564 Parent::setNodeFilterMap(const_true_map);
565 Parent::setEdgeFilterMap(_edge_filter_map);
569 template <typename _Graph>
570 class UndirGraphAdaptorBase :
571 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
573 typedef _Graph Graph;
574 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
576 UndirGraphAdaptorBase() : Parent() { }
578 typedef typename Parent::UndirEdge UndirEdge;
579 typedef typename Parent::Edge Edge;
581 /// \bug Why cant an edge say that it is forward or not???
582 /// By this, a pointer to the graph have to be stored
583 /// The implementation
584 template <typename T>
587 const UndirGraphAdaptorBase<_Graph>* g;
588 template <typename TT> friend class EdgeMap;
589 typename _Graph::template EdgeMap<T> forward_map, backward_map;
594 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
595 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
597 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
598 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
600 void set(Edge e, T a) {
602 forward_map.set(e, a);
604 backward_map.set(e, a);
607 T operator[](Edge e) const {
609 return forward_map[e];
611 return backward_map[e];
615 template <typename T>
617 template <typename TT> friend class UndirEdgeMap;
618 typename _Graph::template EdgeMap<T> map;
621 typedef UndirEdge Key;
623 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
626 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
627 map(*(g.graph), a) { }
629 void set(UndirEdge e, T a) {
633 T operator[](UndirEdge e) const {
640 /// \brief An undirected graph is made from a directed graph by an adaptor
642 /// Undocumented, untested!!!
643 /// If somebody knows nice demo application, let's polulate it.
645 /// \author Marton Makai
646 template<typename _Graph>
647 class UndirGraphAdaptor :
648 public IterableUndirGraphExtender<
649 UndirGraphAdaptorBase<_Graph> > {
651 typedef _Graph Graph;
652 typedef IterableUndirGraphExtender<
653 UndirGraphAdaptorBase<_Graph> > Parent;
655 UndirGraphAdaptor() { }
657 UndirGraphAdaptor(_Graph& _graph) {
663 template <typename _Graph,
664 typename ForwardFilterMap, typename BackwardFilterMap>
665 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
667 typedef _Graph Graph;
668 typedef GraphAdaptorBase<_Graph> Parent;
670 ForwardFilterMap* forward_filter;
671 BackwardFilterMap* backward_filter;
672 SubBidirGraphAdaptorBase() : Parent(),
673 forward_filter(0), backward_filter(0) { }
675 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
676 forward_filter=&_forward_filter;
678 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
679 backward_filter=&_backward_filter;
683 // SubGraphAdaptorBase(Graph& _graph,
684 // NodeFilterMap& _node_filter_map,
685 // EdgeFilterMap& _edge_filter_map) :
687 // node_filter_map(&node_filter_map),
688 // edge_filter_map(&edge_filter_map) { }
690 typedef typename Parent::Node Node;
691 typedef typename _Graph::Edge GraphEdge;
692 template <typename T> class EdgeMap;
693 /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
694 /// _Graph::Edge. It contains an extra bool flag which is true
695 /// if and only if the
696 /// edge is the backward version of the original edge.
697 class Edge : public _Graph::Edge {
698 friend class SubBidirGraphAdaptorBase<
699 Graph, ForwardFilterMap, BackwardFilterMap>;
700 template<typename T> friend class EdgeMap;
702 bool backward; //true, iff backward
705 /// \todo =false is needed, or causes problems?
706 /// If \c _backward is false, then we get an edge corresponding to the
707 /// original one, otherwise its oppositely directed pair is obtained.
708 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
709 _Graph::Edge(e), backward(_backward) { }
710 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
711 bool operator==(const Edge& v) const {
712 return (this->backward==v.backward &&
713 static_cast<typename _Graph::Edge>(*this)==
714 static_cast<typename _Graph::Edge>(v));
716 bool operator!=(const Edge& v) const {
717 return (this->backward!=v.backward ||
718 static_cast<typename _Graph::Edge>(*this)!=
719 static_cast<typename _Graph::Edge>(v));
723 void first(Node& i) const {
727 void first(Edge& i) const {
730 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
731 !(*forward_filter)[i]) Parent::next(i);
732 if (*static_cast<GraphEdge*>(&i)==INVALID) {
735 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
736 !(*backward_filter)[i]) Parent::next(i);
740 void firstIn(Edge& i, const Node& n) const {
741 Parent::firstIn(i, n);
743 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
744 !(*forward_filter)[i]) Parent::nextIn(i);
745 if (*static_cast<GraphEdge*>(&i)==INVALID) {
746 Parent::firstOut(i, n);
748 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
749 !(*backward_filter)[i]) Parent::nextOut(i);
753 void firstOut(Edge& i, const Node& n) const {
754 Parent::firstOut(i, n);
756 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
757 !(*forward_filter)[i]) Parent::nextOut(i);
758 if (*static_cast<GraphEdge*>(&i)==INVALID) {
759 Parent::firstIn(i, n);
761 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
762 !(*backward_filter)[i]) Parent::nextIn(i);
766 void next(Node& i) const {
770 void next(Edge& i) const {
773 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
774 !(*forward_filter)[i]) Parent::next(i);
775 if (*static_cast<GraphEdge*>(&i)==INVALID) {
778 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
779 !(*backward_filter)[i]) Parent::next(i);
783 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
784 !(*backward_filter)[i]) Parent::next(i);
788 void nextIn(Edge& i) const {
790 Node n=Parent::target(i);
792 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
793 !(*forward_filter)[i]) Parent::nextIn(i);
794 if (*static_cast<GraphEdge*>(&i)==INVALID) {
795 Parent::firstOut(i, n);
797 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
798 !(*backward_filter)[i]) Parent::nextOut(i);
802 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
803 !(*backward_filter)[i]) Parent::nextOut(i);
807 void nextOut(Edge& i) const {
809 Node n=Parent::source(i);
811 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
812 !(*forward_filter)[i]) Parent::nextOut(i);
813 if (*static_cast<GraphEdge*>(&i)==INVALID) {
814 Parent::firstIn(i, n);
816 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
817 !(*backward_filter)[i]) Parent::nextIn(i);
821 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
822 !(*backward_filter)[i]) Parent::nextIn(i);
826 Node source(Edge e) const {
827 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
828 Node target(Edge e) const {
829 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
831 /// Gives back the opposite edge.
832 Edge opposite(const Edge& e) const {
834 f.backward=!f.backward;
838 /// \warning This is a linear time operation and works only if
839 /// \c Graph::EdgeIt is defined.
841 int edgeNum() const {
844 for (first(e); e!=INVALID; next(e)) ++i;
848 bool forward(const Edge& e) const { return !e.backward; }
849 bool backward(const Edge& e) const { return e.backward; }
851 template <typename T>
852 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
853 /// _Graph::EdgeMap one for the forward edges and
854 /// one for the backward edges.
856 template <typename TT> friend class EdgeMap;
857 typename _Graph::template EdgeMap<T> forward_map, backward_map;
862 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
863 ForwardFilterMap, BackwardFilterMap>& g) :
864 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
866 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
867 ForwardFilterMap, BackwardFilterMap>& g, T a) :
868 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
870 void set(Edge e, T a) {
872 forward_map.set(e, a);
874 backward_map.set(e, a);
877 // typename _Graph::template EdgeMap<T>::ConstReference
878 // operator[](Edge e) const {
880 // return forward_map[e];
882 // return backward_map[e];
885 // typename _Graph::template EdgeMap<T>::Reference
886 T operator[](Edge e) const {
888 return forward_map[e];
890 return backward_map[e];
894 forward_map.update();
895 backward_map.update();
902 ///\brief An adaptor for composing a subgraph of a
903 /// bidirected graph made from a directed one.
905 /// An adaptor for composing a subgraph of a
906 /// bidirected graph made from a directed one.
908 ///\warning Graph adaptors are in even more experimental state than the other
909 ///parts of the lib. Use them at you own risk.
911 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
912 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
913 /// reversing its orientation. We are given moreover two bool valued
914 /// maps on the edge-set,
915 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
916 /// SubBidirGraphAdaptor implements the graph structure with node-set
917 /// \f$V\f$ and edge-set
918 /// \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$.
919 /// The purpose of writing + instead of union is because parallel
920 /// edges can arise. (Similarly, antiparallel edges also can arise).
921 /// In other words, a subgraph of the bidirected graph obtained, which
922 /// is given by orienting the edges of the original graph in both directions.
923 /// As the oppositely directed edges are logically different,
924 /// the maps are able to attach different values for them.
926 /// An example for such a construction is \c RevGraphAdaptor where the
927 /// forward_filter is everywhere false and the backward_filter is
928 /// everywhere true. We note that for sake of efficiency,
929 /// \c RevGraphAdaptor is implemented in a different way.
930 /// But BidirGraphAdaptor is obtained from
931 /// SubBidirGraphAdaptor by considering everywhere true
932 /// valued maps both for forward_filter and backward_filter.
934 /// The most important application of SubBidirGraphAdaptor
935 /// is ResGraphAdaptor, which stands for the residual graph in directed
936 /// flow and circulation problems.
937 /// As adaptors usually, the SubBidirGraphAdaptor implements the
938 /// above mentioned graph structure without its physical storage,
939 /// that is the whole stuff is stored in constant memory.
940 template<typename _Graph,
941 typename ForwardFilterMap, typename BackwardFilterMap>
942 class SubBidirGraphAdaptor :
943 public IterableGraphExtender<
944 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
946 typedef _Graph Graph;
947 typedef IterableGraphExtender<
948 SubBidirGraphAdaptorBase<
949 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
951 SubBidirGraphAdaptor() { }
953 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
954 BackwardFilterMap& _backward_filter) {
956 setForwardFilterMap(_forward_filter);
957 setBackwardFilterMap(_backward_filter);
963 ///\brief An adaptor for composing bidirected graph from a directed one.
965 ///\warning Graph adaptors are in even more experimental state than the other
966 ///parts of the lib. Use them at you own risk.
968 /// An adaptor for composing bidirected graph from a directed one.
969 /// A bidirected graph is composed over the directed one without physical
970 /// storage. As the oppositely directed edges are logically different ones
971 /// the maps are able to attach different values for them.
972 template<typename Graph>
973 class BidirGraphAdaptor :
974 public SubBidirGraphAdaptor<
976 ConstMap<typename Graph::Edge, bool>,
977 ConstMap<typename Graph::Edge, bool> > {
979 typedef SubBidirGraphAdaptor<
981 ConstMap<typename Graph::Edge, bool>,
982 ConstMap<typename Graph::Edge, bool> > Parent;
984 ConstMap<typename Graph::Edge, bool> cm;
986 BidirGraphAdaptor() : Parent(), cm(true) {
987 Parent::setForwardFilterMap(cm);
988 Parent::setBackwardFilterMap(cm);
991 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
992 Parent::setGraph(_graph);
993 Parent::setForwardFilterMap(cm);
994 Parent::setBackwardFilterMap(cm);
997 int edgeNum() const {
998 return 2*this->graph->edgeNum();
1000 // KEEP_MAPS(Parent, BidirGraphAdaptor);
1004 template<typename Graph, typename Number,
1005 typename CapacityMap, typename FlowMap>
1006 class ResForwardFilter {
1007 // const Graph* graph;
1008 const CapacityMap* capacity;
1009 const FlowMap* flow;
1011 ResForwardFilter(/*const Graph& _graph, */
1012 const CapacityMap& _capacity, const FlowMap& _flow) :
1013 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1014 ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1015 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1016 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1017 bool operator[](const typename Graph::Edge& e) const {
1018 return (Number((*flow)[e]) < Number((*capacity)[e]));
1022 template<typename Graph, typename Number,
1023 typename CapacityMap, typename FlowMap>
1024 class ResBackwardFilter {
1025 const CapacityMap* capacity;
1026 const FlowMap* flow;
1028 ResBackwardFilter(/*const Graph& _graph,*/
1029 const CapacityMap& _capacity, const FlowMap& _flow) :
1030 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1031 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1032 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1033 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1034 bool operator[](const typename Graph::Edge& e) const {
1035 return (Number(0) < Number((*flow)[e]));
1040 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1042 An adaptor for composing the residual graph for directed flow and circulation problems.
1043 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1044 number type. Let moreover
1045 \f$f,c:A\to F\f$, be functions on the edge-set.
1046 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1047 and \f$c\f$ for a capacity function.
1048 Suppose that a graph instange \c g of type
1049 \c ListGraph implements \f$G\f$.
1053 Then RevGraphAdaptor implements the graph structure with node-set
1054 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1055 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1056 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1057 i.e. the so called residual graph.
1058 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1059 multilicities are counted, i.e. if an edge is in both
1060 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1062 The following code shows how
1063 such an instance can be constructed.
1065 typedef ListGraph Graph;
1066 Graph::EdgeMap<int> f(g);
1067 Graph::EdgeMap<int> c(g);
1068 ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1070 \author Marton Makai
1072 template<typename Graph, typename Number,
1073 typename CapacityMap, typename FlowMap>
1074 class ResGraphAdaptor :
1075 public SubBidirGraphAdaptor<
1077 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1078 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1080 typedef SubBidirGraphAdaptor<
1082 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1083 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1085 const CapacityMap* capacity;
1087 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1088 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1089 ResGraphAdaptor() : Parent(),
1090 capacity(0), flow(0) { }
1091 void setCapacityMap(const CapacityMap& _capacity) {
1092 capacity=&_capacity;
1093 forward_filter.setCapacity(_capacity);
1094 backward_filter.setCapacity(_capacity);
1096 void setFlowMap(FlowMap& _flow) {
1098 forward_filter.setFlow(_flow);
1099 backward_filter.setFlow(_flow);
1102 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1104 Parent(), capacity(&_capacity), flow(&_flow),
1105 forward_filter(/*_graph,*/ _capacity, _flow),
1106 backward_filter(/*_graph,*/ _capacity, _flow) {
1107 Parent::setGraph(_graph);
1108 Parent::setForwardFilterMap(forward_filter);
1109 Parent::setBackwardFilterMap(backward_filter);
1112 typedef typename Parent::Edge Edge;
1114 void augment(const Edge& e, Number a) const {
1115 if (Parent::forward(e))
1116 flow->set(e, (*flow)[e]+a);
1118 flow->set(e, (*flow)[e]-a);
1121 /// \brief Residual capacity map.
1123 /// In generic residual graphs the residual capacity can be obtained
1127 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1129 typedef Number Value;
1131 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1132 _res_graph) : res_graph(&_res_graph) { }
1133 Number operator[](const Edge& e) const {
1134 if (res_graph->forward(e))
1135 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1137 return (*(res_graph->flow))[e];
1141 // KEEP_MAPS(Parent, ResGraphAdaptor);
1146 template <typename _Graph, typename FirstOutEdgesMap>
1147 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1149 typedef _Graph Graph;
1150 typedef GraphAdaptorBase<_Graph> Parent;
1152 FirstOutEdgesMap* first_out_edges;
1153 ErasingFirstGraphAdaptorBase() : Parent(),
1154 first_out_edges(0) { }
1156 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1157 first_out_edges=&_first_out_edges;
1162 typedef typename Parent::Node Node;
1163 typedef typename Parent::Edge Edge;
1165 void firstOut(Edge& i, const Node& n) const {
1166 i=(*first_out_edges)[n];
1169 void erase(const Edge& e) const {
1173 first_out_edges->set(n, f);
1178 /// For blocking flows.
1180 ///\warning Graph adaptors are in even more experimental state than the other
1181 ///parts of the lib. Use them at you own risk.
1183 /// This graph adaptor is used for on-the-fly
1184 /// Dinits blocking flow computations.
1185 /// For each node, an out-edge is stored which is used when the
1187 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1191 /// \author Marton Makai
1192 template <typename _Graph, typename FirstOutEdgesMap>
1193 class ErasingFirstGraphAdaptor :
1194 public IterableGraphExtender<
1195 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1197 typedef _Graph Graph;
1198 typedef IterableGraphExtender<
1199 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1200 ErasingFirstGraphAdaptor(Graph& _graph,
1201 FirstOutEdgesMap& _first_out_edges) {
1203 setFirstOutEdgesMap(_first_out_edges);
1212 #endif //LEMON_GRAPH_ADAPTOR_H