Hmmm...
2 * 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/erasable_graph_extender.h>
31 #include <lemon/bits/clearable_graph_extender.h>
32 #include <lemon/bits/extendable_graph_extender.h>
33 #include <lemon/bits/iterable_graph_extender.h>
34 #include <lemon/bits/alteration_notifier.h>
35 #include <lemon/bits/default_map.h>
36 #include <lemon/bits/undir_graph_extender.h>
44 \addtogroup graph_adaptors
49 Base type for the Graph Adaptors
51 \warning Graph adaptors are in even more experimental state than the other
52 parts of the lib. Use them at you own risk.
54 This is the base type for most of LEMON graph adaptors.
55 This class implements a trivial graph adaptor i.e. it only wraps the
56 functions and types of the graph. The purpose of this class is to
57 make easier implementing graph adaptors. E.g. if an adaptor is
58 considered which differs from the wrapped graph only in some of its
59 functions or types, then it can be derived from GraphAdaptor, and only the
60 differences should be implemented.
64 template<typename _Graph>
65 class GraphAdaptorBase {
68 /// \todo Is it needed?
69 typedef Graph BaseGraph;
70 typedef Graph ParentGraph;
74 GraphAdaptorBase() : graph(0) { }
75 void setGraph(Graph& _graph) { graph=&_graph; }
78 GraphAdaptorBase(Graph& _graph) : graph(&_graph) { }
80 typedef typename Graph::Node Node;
81 typedef typename Graph::Edge Edge;
83 void first(Node& i) const { graph->first(i); }
84 void first(Edge& i) const { graph->first(i); }
85 void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
86 void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
88 void next(Node& i) const { graph->next(i); }
89 void next(Edge& i) const { graph->next(i); }
90 void nextIn(Edge& i) const { graph->nextIn(i); }
91 void nextOut(Edge& i) const { graph->nextOut(i); }
93 Node source(const Edge& e) const { return graph->source(e); }
94 Node target(const Edge& e) const { return graph->target(e); }
96 int nodeNum() const { return graph->nodeNum(); }
97 int edgeNum() const { return graph->edgeNum(); }
99 Node addNode() const { return Node(graph->addNode()); }
100 Edge addEdge(const Node& source, const Node& target) const {
101 return Edge(graph->addEdge(source, target)); }
103 void erase(const Node& i) const { graph->erase(i); }
104 void erase(const Edge& i) const { graph->erase(i); }
106 void clear() const { graph->clear(); }
108 bool forward(const Edge& e) const { return graph->forward(e); }
109 bool backward(const Edge& e) const { return graph->backward(e); }
111 int id(const Node& v) const { return graph->id(v); }
112 int id(const Edge& e) const { return graph->id(e); }
114 Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
116 template <typename _Value>
117 class NodeMap : public _Graph::template NodeMap<_Value> {
119 typedef typename _Graph::template NodeMap<_Value> Parent;
120 NodeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
121 NodeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
122 : Parent(*gw.graph, value) { }
125 template <typename _Value>
126 class EdgeMap : public _Graph::template EdgeMap<_Value> {
128 typedef typename _Graph::template EdgeMap<_Value> Parent;
129 EdgeMap(const GraphAdaptorBase<_Graph>& gw) : Parent(*gw.graph) { }
130 EdgeMap(const GraphAdaptorBase<_Graph>& gw, const _Value& value)
131 : Parent(*gw.graph, value) { }
136 template <typename _Graph>
138 public IterableGraphExtender<GraphAdaptorBase<_Graph> > {
140 typedef _Graph Graph;
141 typedef IterableGraphExtender<GraphAdaptorBase<_Graph> > Parent;
143 GraphAdaptor() : Parent() { }
146 GraphAdaptor(Graph& _graph) { setGraph(_graph); }
149 template <typename _Graph>
150 class RevGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
152 typedef _Graph Graph;
153 typedef GraphAdaptorBase<_Graph> Parent;
155 RevGraphAdaptorBase() : Parent() { }
157 typedef typename Parent::Node Node;
158 typedef typename Parent::Edge Edge;
160 // using Parent::first;
161 void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
162 void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
164 // using Parent::next;
165 void nextIn(Edge& i) const { Parent::nextOut(i); }
166 void nextOut(Edge& i) const { Parent::nextIn(i); }
168 Node source(const Edge& e) const { return Parent::target(e); }
169 Node target(const Edge& e) const { return Parent::source(e); }
173 /// A graph adaptor which reverses the orientation of the edges.
175 ///\warning Graph adaptors are in even more experimental state than the other
176 ///parts of the lib. Use them at you own risk.
178 /// Let \f$G=(V, A)\f$ be a directed graph and
179 /// suppose that a graph instange \c g of type
180 /// \c ListGraph implements \f$G\f$.
184 /// For each directed edge
185 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
186 /// reversing its orientation.
187 /// Then RevGraphAdaptor implements the graph structure with node-set
188 /// \f$V\f$ and edge-set
189 /// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
190 /// reversing the orientation of its edges. The following code shows how
191 /// such an instance can be constructed.
193 /// RevGraphAdaptor<ListGraph> gw(g);
195 ///\author Marton Makai
196 template<typename _Graph>
197 class RevGraphAdaptor :
198 public IterableGraphExtender<RevGraphAdaptorBase<_Graph> > {
200 typedef _Graph Graph;
201 typedef IterableGraphExtender<
202 RevGraphAdaptorBase<_Graph> > Parent;
204 RevGraphAdaptor() { }
206 RevGraphAdaptor(_Graph& _graph) { setGraph(_graph); }
210 template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
211 class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
213 typedef _Graph Graph;
214 typedef GraphAdaptorBase<_Graph> Parent;
216 NodeFilterMap* node_filter_map;
217 EdgeFilterMap* edge_filter_map;
218 SubGraphAdaptorBase() : Parent(),
219 node_filter_map(0), edge_filter_map(0) { }
221 void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
222 node_filter_map=&_node_filter_map;
224 void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
225 edge_filter_map=&_edge_filter_map;
229 // SubGraphAdaptorBase(Graph& _graph,
230 // NodeFilterMap& _node_filter_map,
231 // EdgeFilterMap& _edge_filter_map) :
233 // node_filter_map(&node_filter_map),
234 // edge_filter_map(&edge_filter_map) { }
236 typedef typename Parent::Node Node;
237 typedef typename Parent::Edge Edge;
239 void first(Node& i) const {
241 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
243 void first(Edge& i) const {
245 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
247 void firstIn(Edge& i, const Node& n) const {
248 Parent::firstIn(i, n);
249 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
251 void firstOut(Edge& i, const Node& n) const {
252 Parent::firstOut(i, n);
253 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
256 void next(Node& i) const {
258 while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
260 void next(Edge& i) const {
262 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
264 void nextIn(Edge& i) const {
266 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
268 void nextOut(Edge& i) const {
270 while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
273 /// This function hides \c n in the graph, i.e. the iteration
274 /// jumps over it. This is done by simply setting the value of \c n
275 /// to be false in the corresponding node-map.
276 void hide(const Node& n) const { node_filter_map->set(n, false); }
278 /// This function hides \c e in the graph, i.e. the iteration
279 /// jumps over it. This is done by simply setting the value of \c e
280 /// to be false in the corresponding edge-map.
281 void hide(const Edge& e) const { edge_filter_map->set(e, false); }
283 /// The value of \c n is set to be true in the node-map which stores
284 /// hide information. If \c n was hidden previuosly, then it is shown
286 void unHide(const Node& n) const { node_filter_map->set(n, true); }
288 /// The value of \c e is set to be true in the edge-map which stores
289 /// hide information. If \c e was hidden previuosly, then it is shown
291 void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
293 /// Returns true if \c n is hidden.
294 bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
296 /// Returns true if \c n is hidden.
297 bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
299 /// \warning This is a linear time operation and works only if s
300 /// \c Graph::NodeIt is defined.
301 /// \todo assign tags.
302 int nodeNum() const {
305 for (first(n); n!=INVALID; next(n)) ++i;
309 /// \warning This is a linear time operation and works only if
310 /// \c Graph::EdgeIt is defined.
311 /// \todo assign tags.
312 int edgeNum() const {
315 for (first(e); e!=INVALID; next(e)) ++i;
322 /*! \brief A graph adaptor for hiding nodes and edges from a graph.
324 \warning Graph adaptors are in even more experimental state than the other
325 parts of the lib. Use them at you own risk.
327 SubGraphAdaptor shows the graph with filtered node-set and
329 Let \f$G=(V, A)\f$ be a directed graph
330 and suppose that the graph instance \c g of type ListGraph implements
332 Let moreover \f$b_V\f$ and
333 \f$b_A\f$ be bool-valued functions resp. on the node-set and edge-set.
334 SubGraphAdaptor<...>::NodeIt iterates
335 on the node-set \f$\{v\in V : b_V(v)=true\}\f$ and
336 SubGraphAdaptor<...>::EdgeIt iterates
337 on the edge-set \f$\{e\in A : b_A(e)=true\}\f$. Similarly,
338 SubGraphAdaptor<...>::OutEdgeIt and SubGraphAdaptor<...>::InEdgeIt iterates
339 only on edges leaving and entering a specific node which have true value.
341 We have to note that this does not mean that an
342 induced subgraph is obtained, the node-iterator cares only the filter
343 on the node-set, and the edge-iterators care only the filter on the
346 typedef ListGraph Graph;
348 typedef Graph::Node Node;
349 typedef Graph::Edge Edge;
350 Node u=g.addNode(); //node of id 0
351 Node v=g.addNode(); //node of id 1
352 Node e=g.addEdge(u, v); //edge of id 0
353 Node f=g.addEdge(v, u); //edge of id 1
354 Graph::NodeMap<bool> nm(g, true);
356 Graph::EdgeMap<bool> em(g, true);
358 typedef SubGraphAdaptor<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
360 for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
361 std::cout << ":-)" << std::endl;
362 for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
364 The output of the above code is the following.
370 Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
371 \c Graph::Node that is why \c g.id(n) can be applied.
373 For other examples see also the documentation of NodeSubGraphAdaptor and
378 template<typename _Graph, typename NodeFilterMap,
379 typename EdgeFilterMap>
380 class SubGraphAdaptor :
381 public IterableGraphExtender<
382 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
384 typedef _Graph Graph;
385 typedef IterableGraphExtender<
386 SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
388 SubGraphAdaptor() { }
390 SubGraphAdaptor(_Graph& _graph, NodeFilterMap& _node_filter_map,
391 EdgeFilterMap& _edge_filter_map) {
393 setNodeFilterMap(_node_filter_map);
394 setEdgeFilterMap(_edge_filter_map);
400 /*! \brief An adaptor for hiding nodes from a graph.
402 \warning Graph adaptors are in even more experimental state than the other
403 parts of the lib. Use them at you own risk.
405 An adaptor for hiding nodes from a graph.
406 This adaptor specializes SubGraphAdaptor in the way that only the node-set
407 can be filtered. Note that this does not mean of considering induced
408 subgraph, the edge-iterators consider the original edge-set.
411 template<typename Graph, typename NodeFilterMap>
412 class NodeSubGraphAdaptor :
413 public SubGraphAdaptor<Graph, NodeFilterMap,
414 ConstMap<typename Graph::Edge,bool> > {
416 typedef SubGraphAdaptor<Graph, NodeFilterMap,
417 ConstMap<typename Graph::Edge,bool> > Parent;
419 ConstMap<typename Graph::Edge, bool> const_true_map;
421 NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
422 Parent(), const_true_map(true) {
423 Parent::setGraph(_graph);
424 Parent::setNodeFilterMap(_node_filter_map);
425 Parent::setEdgeFilterMap(const_true_map);
430 /*! \brief An adaptor for hiding edges from a graph.
432 \warning Graph adaptors are in even more experimental state than the other
433 parts of the lib. Use them at you own risk.
435 An adaptor for hiding edges from a graph.
436 This adaptor specializes SubGraphAdaptor in the way that only the edge-set
437 can be filtered. The usefulness of this adaptor is demonstrated in the
438 problem of searching a maximum number of edge-disjoint shortest paths
440 two nodes \c s and \c t. Shortest here means being shortest w.r.t.
441 non-negative edge-lengths. Note that
442 the comprehension of the presented solution
443 need's some elementary knowledge from combinatorial optimization.
445 If a single shortest path is to be
446 searched between \c s and \c t, then this can be done easily by
447 applying the Dijkstra algorithm. What happens, if a maximum number of
448 edge-disjoint shortest paths is to be computed. It can be proved that an
449 edge can be in a shortest path if and only if it is tight with respect to
450 the potential function computed by Dijkstra. Moreover, any path containing
451 only such edges is a shortest one. Thus we have to compute a maximum number
452 of edge-disjoint paths between \c s and \c t in the graph which has edge-set
453 all the tight edges. The computation will be demonstrated on the following
454 graph, which is read from the dimacs file \ref sub_graph_adaptor_demo.dim.
455 The full source code is available in \ref sub_graph_adaptor_demo.cc.
456 If you are interested in more demo programs, you can use
457 \ref dim_to_dot.cc to generate .dot files from dimacs files.
458 The .dot file of the following figure of was generated generated by
459 the demo program \ref dim_to_dot.cc.
462 digraph lemon_dot_example {
463 node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
464 n0 [ label="0 (s)" ];
470 n6 [ label="6 (t)" ];
471 edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
472 n5 -> n6 [ label="9, length:4" ];
473 n4 -> n6 [ label="8, length:2" ];
474 n3 -> n5 [ label="7, length:1" ];
475 n2 -> n5 [ label="6, length:3" ];
476 n2 -> n6 [ label="5, length:5" ];
477 n2 -> n4 [ label="4, length:2" ];
478 n1 -> n4 [ label="3, length:3" ];
479 n0 -> n3 [ label="2, length:1" ];
480 n0 -> n2 [ label="1, length:2" ];
481 n0 -> n1 [ label="0, length:3" ];
490 readDimacs(std::cin, g, length, s, t);
492 cout << "edges with lengths (of form id, source--length->target): " << endl;
493 for(EdgeIt e(g); e!=INVALID; ++e)
494 cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
495 << length[e] << "->" << g.id(g.target(e)) << endl;
497 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
499 Next, the potential function is computed with Dijkstra.
501 typedef Dijkstra<Graph, LengthMap> Dijkstra;
502 Dijkstra dijkstra(g, length);
505 Next, we consrtruct a map which filters the edge-set to the tight edges.
507 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
509 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
511 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
512 SubGW gw(g, tight_edge_filter);
514 Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
515 with a max flow algorithm Preflow.
517 ConstMap<Edge, int> const_1_map(1);
518 Graph::EdgeMap<int> flow(g, 0);
520 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
521 preflow(gw, s, t, const_1_map, flow);
526 cout << "maximum number of edge-disjoint shortest path: "
527 << preflow.flowValue() << endl;
528 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
530 for(EdgeIt e(g); e!=INVALID; ++e)
532 cout << " " << g.id(g.source(e)) << "--"
533 << length[e] << "->" << g.id(g.target(e)) << endl;
535 The program has the following (expected :-)) output:
537 edges with lengths (of form id, source--length->target):
549 maximum number of edge-disjoint shortest path: 2
550 edges of the maximum number of edge-disjoint shortest s-t paths:
561 template<typename Graph, typename EdgeFilterMap>
562 class EdgeSubGraphAdaptor :
563 public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
566 typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
567 EdgeFilterMap> Parent;
569 ConstMap<typename Graph::Node, bool> const_true_map;
571 EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
572 Parent(), const_true_map(true) {
573 Parent::setGraph(_graph);
574 Parent::setNodeFilterMap(const_true_map);
575 Parent::setEdgeFilterMap(_edge_filter_map);
579 template <typename _Graph>
580 class UndirGraphAdaptorBase :
581 public UndirGraphExtender<GraphAdaptorBase<_Graph> > {
583 typedef _Graph Graph;
584 typedef UndirGraphExtender<GraphAdaptorBase<_Graph> > Parent;
586 UndirGraphAdaptorBase() : Parent() { }
588 typedef typename Parent::UndirEdge UndirEdge;
589 typedef typename Parent::Edge Edge;
591 /// \bug Why cant an edge say that it is forward or not???
592 /// By this, a pointer to the graph have to be stored
593 /// The implementation
594 template <typename T>
597 const UndirGraphAdaptorBase<_Graph>* g;
598 template <typename TT> friend class EdgeMap;
599 typename _Graph::template EdgeMap<T> forward_map, backward_map;
604 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g) : g(&_g),
605 forward_map(*(g->graph)), backward_map(*(g->graph)) { }
607 EdgeMap(const UndirGraphAdaptorBase<_Graph>& _g, T a) : g(&_g),
608 forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
610 void set(Edge e, T a) {
612 forward_map.set(e, a);
614 backward_map.set(e, a);
617 T operator[](Edge e) const {
619 return forward_map[e];
621 return backward_map[e];
625 template <typename T>
627 template <typename TT> friend class UndirEdgeMap;
628 typename _Graph::template EdgeMap<T> map;
631 typedef UndirEdge Key;
633 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g) :
636 UndirEdgeMap(const UndirGraphAdaptorBase<_Graph>& g, T a) :
637 map(*(g.graph), a) { }
639 void set(UndirEdge e, T a) {
643 T operator[](UndirEdge e) const {
650 /// \brief An undirected graph is made from a directed graph by an adaptor
652 /// Undocumented, untested!!!
653 /// If somebody knows nice demo application, let's polulate it.
655 /// \author Marton Makai
656 template<typename _Graph>
657 class UndirGraphAdaptor :
658 public IterableUndirGraphExtender<
659 UndirGraphAdaptorBase<_Graph> > {
661 typedef _Graph Graph;
662 typedef IterableUndirGraphExtender<
663 UndirGraphAdaptorBase<_Graph> > Parent;
665 UndirGraphAdaptor() { }
667 UndirGraphAdaptor(_Graph& _graph) {
673 template <typename _Graph,
674 typename ForwardFilterMap, typename BackwardFilterMap>
675 class SubBidirGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
677 typedef _Graph Graph;
678 typedef GraphAdaptorBase<_Graph> Parent;
680 ForwardFilterMap* forward_filter;
681 BackwardFilterMap* backward_filter;
682 SubBidirGraphAdaptorBase() : Parent(),
683 forward_filter(0), backward_filter(0) { }
685 void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
686 forward_filter=&_forward_filter;
688 void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
689 backward_filter=&_backward_filter;
693 // SubGraphAdaptorBase(Graph& _graph,
694 // NodeFilterMap& _node_filter_map,
695 // EdgeFilterMap& _edge_filter_map) :
697 // node_filter_map(&node_filter_map),
698 // edge_filter_map(&edge_filter_map) { }
700 typedef typename Parent::Node Node;
701 typedef typename _Graph::Edge GraphEdge;
702 template <typename T> class EdgeMap;
703 /// SubBidirGraphAdaptorBase<..., ..., ...>::Edge is inherited from
704 /// _Graph::Edge. It contains an extra bool flag which is true
705 /// if and only if the
706 /// edge is the backward version of the original edge.
707 class Edge : public _Graph::Edge {
708 friend class SubBidirGraphAdaptorBase<
709 Graph, ForwardFilterMap, BackwardFilterMap>;
710 template<typename T> friend class EdgeMap;
712 bool backward; //true, iff backward
715 /// \todo =false is needed, or causes problems?
716 /// If \c _backward is false, then we get an edge corresponding to the
717 /// original one, otherwise its oppositely directed pair is obtained.
718 Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
719 _Graph::Edge(e), backward(_backward) { }
720 Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
721 bool operator==(const Edge& v) const {
722 return (this->backward==v.backward &&
723 static_cast<typename _Graph::Edge>(*this)==
724 static_cast<typename _Graph::Edge>(v));
726 bool operator!=(const Edge& v) const {
727 return (this->backward!=v.backward ||
728 static_cast<typename _Graph::Edge>(*this)!=
729 static_cast<typename _Graph::Edge>(v));
733 void first(Node& i) const {
737 void first(Edge& i) const {
740 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
741 !(*forward_filter)[i]) Parent::next(i);
742 if (*static_cast<GraphEdge*>(&i)==INVALID) {
745 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
746 !(*backward_filter)[i]) Parent::next(i);
750 void firstIn(Edge& i, const Node& n) const {
751 Parent::firstIn(i, n);
753 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
754 !(*forward_filter)[i]) Parent::nextIn(i);
755 if (*static_cast<GraphEdge*>(&i)==INVALID) {
756 Parent::firstOut(i, n);
758 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
759 !(*backward_filter)[i]) Parent::nextOut(i);
763 void firstOut(Edge& i, const Node& n) const {
764 Parent::firstOut(i, n);
766 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
767 !(*forward_filter)[i]) Parent::nextOut(i);
768 if (*static_cast<GraphEdge*>(&i)==INVALID) {
769 Parent::firstIn(i, n);
771 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
772 !(*backward_filter)[i]) Parent::nextIn(i);
776 void next(Node& i) const {
780 void next(Edge& i) const {
783 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
784 !(*forward_filter)[i]) Parent::next(i);
785 if (*static_cast<GraphEdge*>(&i)==INVALID) {
788 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
789 !(*backward_filter)[i]) Parent::next(i);
793 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
794 !(*backward_filter)[i]) Parent::next(i);
798 void nextIn(Edge& i) const {
800 Node n=Parent::target(i);
802 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
803 !(*forward_filter)[i]) Parent::nextIn(i);
804 if (*static_cast<GraphEdge*>(&i)==INVALID) {
805 Parent::firstOut(i, n);
807 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
808 !(*backward_filter)[i]) Parent::nextOut(i);
812 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
813 !(*backward_filter)[i]) Parent::nextOut(i);
817 void nextOut(Edge& i) const {
819 Node n=Parent::source(i);
821 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
822 !(*forward_filter)[i]) Parent::nextOut(i);
823 if (*static_cast<GraphEdge*>(&i)==INVALID) {
824 Parent::firstIn(i, n);
826 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
827 !(*backward_filter)[i]) Parent::nextIn(i);
831 while (*static_cast<GraphEdge*>(&i)!=INVALID &&
832 !(*backward_filter)[i]) Parent::nextIn(i);
836 Node source(Edge e) const {
837 return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
838 Node target(Edge e) const {
839 return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
841 /// Gives back the opposite edge.
842 Edge opposite(const Edge& e) const {
844 f.backward=!f.backward;
848 /// \warning This is a linear time operation and works only if
849 /// \c Graph::EdgeIt is defined.
851 int edgeNum() const {
854 for (first(e); e!=INVALID; next(e)) ++i;
858 bool forward(const Edge& e) const { return !e.backward; }
859 bool backward(const Edge& e) const { return e.backward; }
861 template <typename T>
862 /// \c SubBidirGraphAdaptorBase<..., ..., ...>::EdgeMap contains two
863 /// _Graph::EdgeMap one for the forward edges and
864 /// one for the backward edges.
866 template <typename TT> friend class EdgeMap;
867 typename _Graph::template EdgeMap<T> forward_map, backward_map;
872 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
873 ForwardFilterMap, BackwardFilterMap>& g) :
874 forward_map(*(g.graph)), backward_map(*(g.graph)) { }
876 EdgeMap(const SubBidirGraphAdaptorBase<_Graph,
877 ForwardFilterMap, BackwardFilterMap>& g, T a) :
878 forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
880 void set(Edge e, T a) {
882 forward_map.set(e, a);
884 backward_map.set(e, a);
887 // typename _Graph::template EdgeMap<T>::ConstReference
888 // operator[](Edge e) const {
890 // return forward_map[e];
892 // return backward_map[e];
895 // typename _Graph::template EdgeMap<T>::Reference
896 T operator[](Edge e) const {
898 return forward_map[e];
900 return backward_map[e];
904 forward_map.update();
905 backward_map.update();
912 ///\brief An adaptor for composing a subgraph of a
913 /// bidirected graph made from a directed one.
915 /// An adaptor for composing a subgraph of a
916 /// bidirected graph made from a directed one.
918 ///\warning Graph adaptors are in even more experimental state than the other
919 ///parts of the lib. Use them at you own risk.
921 /// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
922 /// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
923 /// reversing its orientation. We are given moreover two bool valued
924 /// maps on the edge-set,
925 /// \f$forward\_filter\f$, and \f$backward\_filter\f$.
926 /// SubBidirGraphAdaptor implements the graph structure with node-set
927 /// \f$V\f$ and edge-set
928 /// \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$.
929 /// The purpose of writing + instead of union is because parallel
930 /// edges can arise. (Similarly, antiparallel edges also can arise).
931 /// In other words, a subgraph of the bidirected graph obtained, which
932 /// is given by orienting the edges of the original graph in both directions.
933 /// As the oppositely directed edges are logically different,
934 /// the maps are able to attach different values for them.
936 /// An example for such a construction is \c RevGraphAdaptor where the
937 /// forward_filter is everywhere false and the backward_filter is
938 /// everywhere true. We note that for sake of efficiency,
939 /// \c RevGraphAdaptor is implemented in a different way.
940 /// But BidirGraphAdaptor is obtained from
941 /// SubBidirGraphAdaptor by considering everywhere true
942 /// valued maps both for forward_filter and backward_filter.
944 /// The most important application of SubBidirGraphAdaptor
945 /// is ResGraphAdaptor, which stands for the residual graph in directed
946 /// flow and circulation problems.
947 /// As adaptors usually, the SubBidirGraphAdaptor implements the
948 /// above mentioned graph structure without its physical storage,
949 /// that is the whole stuff is stored in constant memory.
950 template<typename _Graph,
951 typename ForwardFilterMap, typename BackwardFilterMap>
952 class SubBidirGraphAdaptor :
953 public IterableGraphExtender<
954 SubBidirGraphAdaptorBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
956 typedef _Graph Graph;
957 typedef IterableGraphExtender<
958 SubBidirGraphAdaptorBase<
959 _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
961 SubBidirGraphAdaptor() { }
963 SubBidirGraphAdaptor(_Graph& _graph, ForwardFilterMap& _forward_filter,
964 BackwardFilterMap& _backward_filter) {
966 setForwardFilterMap(_forward_filter);
967 setBackwardFilterMap(_backward_filter);
973 ///\brief An adaptor for composing bidirected graph from a directed one.
975 ///\warning Graph adaptors are in even more experimental state than the other
976 ///parts of the lib. Use them at you own risk.
978 /// An adaptor for composing bidirected graph from a directed one.
979 /// A bidirected graph is composed over the directed one without physical
980 /// storage. As the oppositely directed edges are logically different ones
981 /// the maps are able to attach different values for them.
982 template<typename Graph>
983 class BidirGraphAdaptor :
984 public SubBidirGraphAdaptor<
986 ConstMap<typename Graph::Edge, bool>,
987 ConstMap<typename Graph::Edge, bool> > {
989 typedef SubBidirGraphAdaptor<
991 ConstMap<typename Graph::Edge, bool>,
992 ConstMap<typename Graph::Edge, bool> > Parent;
994 ConstMap<typename Graph::Edge, bool> cm;
996 BidirGraphAdaptor() : Parent(), cm(true) {
997 Parent::setForwardFilterMap(cm);
998 Parent::setBackwardFilterMap(cm);
1001 BidirGraphAdaptor(Graph& _graph) : Parent(), cm(true) {
1002 Parent::setGraph(_graph);
1003 Parent::setForwardFilterMap(cm);
1004 Parent::setBackwardFilterMap(cm);
1007 int edgeNum() const {
1008 return 2*this->graph->edgeNum();
1010 // KEEP_MAPS(Parent, BidirGraphAdaptor);
1014 template<typename Graph, typename Number,
1015 typename CapacityMap, typename FlowMap>
1016 class ResForwardFilter {
1017 // const Graph* graph;
1018 const CapacityMap* capacity;
1019 const FlowMap* flow;
1021 ResForwardFilter(/*const Graph& _graph, */
1022 const CapacityMap& _capacity, const FlowMap& _flow) :
1023 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1024 ResForwardFilter() : /*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((*flow)[e]) < Number((*capacity)[e]));
1032 template<typename Graph, typename Number,
1033 typename CapacityMap, typename FlowMap>
1034 class ResBackwardFilter {
1035 const CapacityMap* capacity;
1036 const FlowMap* flow;
1038 ResBackwardFilter(/*const Graph& _graph,*/
1039 const CapacityMap& _capacity, const FlowMap& _flow) :
1040 /*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
1041 ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
1042 void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
1043 void setFlow(const FlowMap& _flow) { flow=&_flow; }
1044 bool operator[](const typename Graph::Edge& e) const {
1045 return (Number(0) < Number((*flow)[e]));
1050 /*! \brief An adaptor for composing the residual graph for directed flow and circulation problems.
1052 An adaptor for composing the residual graph for directed flow and circulation problems.
1053 Let \f$G=(V, A)\f$ be a directed graph and let \f$F\f$ be a
1054 number type. Let moreover
1055 \f$f,c:A\to F\f$, be functions on the edge-set.
1056 In the appications of ResGraphAdaptor, \f$f\f$ usually stands for a flow
1057 and \f$c\f$ for a capacity function.
1058 Suppose that a graph instange \c g of type
1059 \c ListGraph implements \f$G\f$.
1063 Then RevGraphAdaptor implements the graph structure with node-set
1064 \f$V\f$ and edge-set \f$A_{forward}\cup A_{backward}\f$, where
1065 \f$A_{forward}=\{uv : uv\in A, f(uv)<c(uv)\}\f$ and
1066 \f$A_{backward}=\{vu : uv\in A, f(uv)>0\}\f$,
1067 i.e. the so called residual graph.
1068 When we take the union \f$A_{forward}\cup A_{backward}\f$,
1069 multilicities are counted, i.e. if an edge is in both
1070 \f$A_{forward}\f$ and \f$A_{backward}\f$, then in the adaptor it
1072 The following code shows how
1073 such an instance can be constructed.
1075 typedef ListGraph Graph;
1076 Graph::EdgeMap<int> f(g);
1077 Graph::EdgeMap<int> c(g);
1078 ResGraphAdaptor<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > gw(g);
1080 \author Marton Makai
1082 template<typename Graph, typename Number,
1083 typename CapacityMap, typename FlowMap>
1084 class ResGraphAdaptor :
1085 public SubBidirGraphAdaptor<
1087 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1088 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
1090 typedef SubBidirGraphAdaptor<
1092 ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
1093 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
1095 const CapacityMap* capacity;
1097 ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
1098 ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
1099 ResGraphAdaptor() : Parent(),
1100 capacity(0), flow(0) { }
1101 void setCapacityMap(const CapacityMap& _capacity) {
1102 capacity=&_capacity;
1103 forward_filter.setCapacity(_capacity);
1104 backward_filter.setCapacity(_capacity);
1106 void setFlowMap(FlowMap& _flow) {
1108 forward_filter.setFlow(_flow);
1109 backward_filter.setFlow(_flow);
1112 ResGraphAdaptor(Graph& _graph, const CapacityMap& _capacity,
1114 Parent(), capacity(&_capacity), flow(&_flow),
1115 forward_filter(/*_graph,*/ _capacity, _flow),
1116 backward_filter(/*_graph,*/ _capacity, _flow) {
1117 Parent::setGraph(_graph);
1118 Parent::setForwardFilterMap(forward_filter);
1119 Parent::setBackwardFilterMap(backward_filter);
1122 typedef typename Parent::Edge Edge;
1124 void augment(const Edge& e, Number a) const {
1125 if (Parent::forward(e))
1126 flow->set(e, (*flow)[e]+a);
1128 flow->set(e, (*flow)[e]-a);
1131 /// \brief Residual capacity map.
1133 /// In generic residual graphs the residual capacity can be obtained
1137 const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>* res_graph;
1139 typedef Number Value;
1141 ResCap(const ResGraphAdaptor<Graph, Number, CapacityMap, FlowMap>&
1142 _res_graph) : res_graph(&_res_graph) { }
1143 Number operator[](const Edge& e) const {
1144 if (res_graph->forward(e))
1145 return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
1147 return (*(res_graph->flow))[e];
1151 // KEEP_MAPS(Parent, ResGraphAdaptor);
1156 template <typename _Graph, typename FirstOutEdgesMap>
1157 class ErasingFirstGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
1159 typedef _Graph Graph;
1160 typedef GraphAdaptorBase<_Graph> Parent;
1162 FirstOutEdgesMap* first_out_edges;
1163 ErasingFirstGraphAdaptorBase() : Parent(),
1164 first_out_edges(0) { }
1166 void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
1167 first_out_edges=&_first_out_edges;
1172 typedef typename Parent::Node Node;
1173 typedef typename Parent::Edge Edge;
1175 void firstOut(Edge& i, const Node& n) const {
1176 i=(*first_out_edges)[n];
1179 void erase(const Edge& e) const {
1183 first_out_edges->set(n, f);
1188 /// For blocking flows.
1190 ///\warning Graph adaptors are in even more experimental state than the other
1191 ///parts of the lib. Use them at you own risk.
1193 /// This graph adaptor is used for on-the-fly
1194 /// Dinits blocking flow computations.
1195 /// For each node, an out-edge is stored which is used when the
1197 /// OutEdgeIt& first(OutEdgeIt&, const Node&)
1201 /// \author Marton Makai
1202 template <typename _Graph, typename FirstOutEdgesMap>
1203 class ErasingFirstGraphAdaptor :
1204 public IterableGraphExtender<
1205 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > {
1207 typedef _Graph Graph;
1208 typedef IterableGraphExtender<
1209 ErasingFirstGraphAdaptorBase<_Graph, FirstOutEdgesMap> > Parent;
1210 ErasingFirstGraphAdaptor(Graph& _graph,
1211 FirstOutEdgesMap& _first_out_edges) {
1213 setFirstOutEdgesMap(_first_out_edges);
1219 template <typename _Graph>
1220 class NewEdgeSetAdaptorBase {
1223 typedef _Graph Graph;
1224 typedef typename Graph::Node Node;
1225 typedef typename Graph::NodeIt NodeIt;
1230 int first_out, first_in;
1231 NodeT() : first_out(-1), first_in(-1) {}
1234 class NodesImpl : protected Graph::template NodeMap<NodeT> {
1236 typedef typename Graph::template NodeMap<NodeT> Parent;
1237 typedef NewEdgeSetAdaptorBase<Graph> Adaptor;
1243 NodesImpl(Adaptor& _adaptor, const Graph& _graph)
1244 : Parent(_graph), adaptor(_adaptor) {}
1246 virtual ~NodesImpl() {}
1248 virtual void build() {
1252 virtual void clear() {
1257 virtual void add(const Node& node) {
1262 virtual void erase(const Node& node) {
1263 adaptor._erase(node);
1264 Parent::erase(node);
1267 NodeT& operator[](const Node& node) {
1268 return Parent::operator[](node);
1271 const NodeT& operator[](const Node& node) const {
1272 return Parent::operator[](node);
1280 Node source, target;
1281 int next_out, next_in;
1282 int prev_out, prev_in;
1283 EdgeT() : prev_out(-1), prev_in(-1) {}
1286 std::vector<EdgeT> edges;
1289 int first_free_edge;
1291 virtual void _clear() = 0;
1292 virtual void _add(const Node& node) = 0;
1293 virtual void _erase(const Node& node) = 0;
1297 void initalize(const Graph& _graph, NodesImpl& _nodes) {
1305 friend class NewEdgeSetAdaptorBase<Graph>;
1307 Edge(int _id) : id(_id) {}
1311 Edge(Invalid) : id(-1) {}
1312 bool operator==(const Edge& edge) const { return id == edge.id; }
1313 bool operator!=(const Edge& edge) const { return id != edge.id; }
1314 bool operator<(const Edge& edge) const { return id < edge.id; }
1317 NewEdgeSetAdaptorBase() : first_edge(-1), first_free_edge(-1) {}
1318 virtual ~NewEdgeSetAdaptorBase() {}
1320 Edge addEdge(const Node& source, const Node& target) {
1322 if (first_free_edge == -1) {
1324 edges.push_back(EdgeT());
1326 n = first_free_edge;
1327 first_free_edge = edges[first_free_edge].next_in;
1329 edges[n].next_in = (*nodes)[target].first_in;
1330 (*nodes)[target].first_in = n;
1331 edges[n].next_out = (*nodes)[source].first_out;
1332 (*nodes)[source].first_out = n;
1333 edges[n].source = source;
1334 edges[n].target = target;
1338 void erase(const Edge& edge) {
1340 if (edges[n].prev_in != -1) {
1341 edges[edges[n].prev_in].next_in = edges[n].next_in;
1343 (*nodes)[edges[n].target].first_in = edges[n].next_in;
1345 if (edges[n].next_in != -1) {
1346 edges[edges[n].next_in].prev_in = edges[n].prev_in;
1349 if (edges[n].prev_out != -1) {
1350 edges[edges[n].prev_out].next_out = edges[n].next_out;
1352 (*nodes)[edges[n].source].first_out = edges[n].next_out;
1354 if (edges[n].next_out != -1) {
1355 edges[edges[n].next_out].prev_out = edges[n].prev_out;
1360 void first(Node& node) const {
1364 void next(Node& node) const {
1368 void first(Edge& edge) const {
1370 for (first(node); node != INVALID && (*nodes)[node].first_in == -1;
1372 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1375 void next(Edge& edge) const {
1376 if (edges[edge.id].next_in != -1) {
1377 edge.id = edges[edge.id].next_in;
1379 Node node = edges[edge.id].target;
1380 for (next(node); node != INVALID && (*nodes)[node].first_in == -1;
1382 edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1386 void firstOut(Edge& edge, const Node& node) const {
1387 edge.id = (*nodes)[node].first_out;
1390 void nextOut(Edge& edge) const {
1391 edge.id = edges[edge.id].next_out;
1394 void firstIn(Edge& edge, const Node& node) const {
1395 edge.id = (*nodes)[node].first_in;
1398 void nextIn(Edge& edge) const {
1399 edge.id = edges[edge.id].next_in;
1402 int id(const Node& node) const { return graph->id(node); }
1403 int id(const Edge& edge) const { return edge.id; }
1405 Node fromId(int id, Node) const { return graph->fromId(id, Node()); }
1406 Edge fromId(int id, Edge) const { return Edge(id); }
1408 int maxId(Node) const { return graph->maxId(Node()); };
1409 int maxId(Edge) const { return edges.size() - 1; }
1411 Node source(const Edge& edge) const { return edges[edge.id].source;}
1412 Node target(const Edge& edge) const { return edges[edge.id].target;}
1416 template <typename _Graph>
1417 class NewEdgeSetAdaptor :
1418 public ErasableGraphExtender<
1419 ClearableGraphExtender<
1420 ExtendableGraphExtender<
1421 DefaultMappableGraphExtender<
1422 IterableGraphExtender<
1423 AlterableGraphExtender<
1424 NewEdgeSetAdaptorBase<_Graph> > > > > > > {
1428 typedef ErasableGraphExtender<
1429 ClearableGraphExtender<
1430 ExtendableGraphExtender<
1431 DefaultMappableGraphExtender<
1432 IterableGraphExtender<
1433 AlterableGraphExtender<
1434 NewEdgeSetAdaptorBase<_Graph> > > > > > > Parent;
1437 typedef typename Parent::Node Node;
1438 typedef typename Parent::Edge Edge;
1442 virtual void _clear() {
1443 Parent::edges.clear();
1444 Parent::first_edge = -1;
1445 Parent::first_free_edge = -1;
1446 Parent::getNotifier(Edge()).clear();
1447 Parent::getNotifier(Node()).clear();
1450 virtual void _add(const Node& node) {
1451 Parent::getNotifier(Node()).add(node);
1454 virtual void _erase(const Node& node) {
1456 Parent::firstOut(edge, node);
1457 while (edge != INVALID) {
1458 Parent::erase(edge);
1459 Parent::firstOut(edge, node);
1462 Parent::firstIn(edge, node);
1463 while (edge != INVALID) {
1464 Parent::erase(edge);
1465 Parent::firstIn(edge, node);
1468 Parent::getNotifier(Node()).erase(node);
1472 typedef typename Parent::NodesImpl NodesImpl;
1478 NewEdgeSetAdaptor(const _Graph& _graph) : nodes(*this, _graph) {
1479 Parent::initalize(_graph, nodes);
1483 Parent::edges.clear();
1484 Parent::first_edge = -1;
1485 Parent::first_free_edge = -1;
1487 Parent::getNotifier(Edge()).clear();
1496 #endif //LEMON_GRAPH_ADAPTOR_H