alpar@906
|
1 |
/* -*- C++ -*-
|
alpar@921
|
2 |
* src/lemon/graph_wrapper.h - Part of LEMON, a generic C++ optimization library
|
alpar@906
|
3 |
*
|
alpar@906
|
4 |
* Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@906
|
5 |
* (Egervary Combinatorial Optimization Research Group, EGRES).
|
alpar@906
|
6 |
*
|
alpar@906
|
7 |
* Permission to use, modify and distribute this software is granted
|
alpar@906
|
8 |
* provided that this copyright notice appears in all copies. For
|
alpar@906
|
9 |
* precise terms see the accompanying LICENSE file.
|
alpar@906
|
10 |
*
|
alpar@906
|
11 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@906
|
12 |
* express or implied, and with no claim as to its suitability for any
|
alpar@906
|
13 |
* purpose.
|
alpar@906
|
14 |
*
|
alpar@906
|
15 |
*/
|
alpar@906
|
16 |
|
alpar@921
|
17 |
#ifndef LEMON_GRAPH_WRAPPER_H
|
alpar@921
|
18 |
#define LEMON_GRAPH_WRAPPER_H
|
marci@556
|
19 |
|
marci@556
|
20 |
///\ingroup gwrappers
|
marci@556
|
21 |
///\file
|
marci@556
|
22 |
///\brief Several graph wrappers.
|
marci@556
|
23 |
///
|
marci@556
|
24 |
///This file contains several useful graph wrapper functions.
|
marci@556
|
25 |
///
|
marci@556
|
26 |
///\author Marton Makai
|
marci@556
|
27 |
|
alpar@921
|
28 |
#include <lemon/invalid.h>
|
alpar@921
|
29 |
#include <lemon/maps.h>
|
marci@992
|
30 |
#include <lemon/iterable_graph_extender.h>
|
alpar@921
|
31 |
#include <lemon/map_defines.h>
|
alpar@774
|
32 |
#include <iostream>
|
marci@556
|
33 |
|
alpar@921
|
34 |
namespace lemon {
|
marci@556
|
35 |
|
marci@556
|
36 |
// Graph wrappers
|
marci@556
|
37 |
|
marci@1004
|
38 |
/*! \addtogroup gwrappers
|
marci@1004
|
39 |
The main parts of LEMON are the different graph structures,
|
marci@1004
|
40 |
generic graph algorithms, graph concepts which couple these, and
|
marci@1004
|
41 |
graph wrappers. While the previous ones are more or less clear, the
|
marci@1004
|
42 |
latter notion needs further explanation.
|
marci@1004
|
43 |
Graph wrappers are graph classes which serve for considering graph
|
marci@1004
|
44 |
structures in different ways. A short example makes the notion much
|
marci@1004
|
45 |
clearer.
|
marci@1004
|
46 |
Suppose that we have an instance \c g of a directed graph
|
marci@1004
|
47 |
type say \c ListGraph and an algorithm
|
marci@1004
|
48 |
\code template<typename Graph> int algorithm(const Graph&); \endcode
|
marci@1004
|
49 |
is needed to run on the reversely oriented graph.
|
marci@1004
|
50 |
It may be expensive (in time or in memory usage) to copy
|
marci@1004
|
51 |
\c g with the reverse orientation.
|
marci@1004
|
52 |
Thus, a wrapper class
|
marci@1004
|
53 |
\code template<typename Graph> class RevGraphWrapper; \endcode is used.
|
marci@1004
|
54 |
The code looks as follows
|
marci@1004
|
55 |
\code
|
marci@1004
|
56 |
ListGraph g;
|
marci@1004
|
57 |
RevGraphWrapper<ListGraph> rgw(g);
|
marci@1004
|
58 |
int result=algorithm(rgw);
|
marci@1004
|
59 |
\endcode
|
marci@1004
|
60 |
After running the algorithm, the original graph \c g
|
marci@1004
|
61 |
remains untouched. Thus the graph wrapper used above is to consider the
|
marci@1004
|
62 |
original graph with reverse orientation.
|
marci@1004
|
63 |
This techniques gives rise to an elegant code, and
|
marci@1004
|
64 |
based on stable graph wrappers, complex algorithms can be
|
marci@1004
|
65 |
implemented easily.
|
marci@1004
|
66 |
In flow, circulation and bipartite matching problems, the residual
|
marci@1004
|
67 |
graph is of particular importance. Combining a wrapper implementing
|
marci@1004
|
68 |
this, shortest path algorithms and minimum mean cycle algorithms,
|
marci@1004
|
69 |
a range of weighted and cardinality optimization algorithms can be
|
marci@1004
|
70 |
obtained. For lack of space, for other examples,
|
marci@1004
|
71 |
the interested user is referred to the detailed documentation of graph
|
marci@1004
|
72 |
wrappers.
|
marci@1004
|
73 |
The behavior of graph wrappers can be very different. Some of them keep
|
marci@1004
|
74 |
capabilities of the original graph while in other cases this would be
|
marci@1004
|
75 |
meaningless. This means that the concepts that they are a model of depend
|
marci@1004
|
76 |
on the graph wrapper, and the wrapped graph(s).
|
marci@1004
|
77 |
If an edge of \c rgw is deleted, this is carried out by
|
marci@1004
|
78 |
deleting the corresponding edge of \c g. But for a residual
|
marci@1004
|
79 |
graph, this operation has no sense.
|
marci@1004
|
80 |
Let we stand one more example here to simplify your work.
|
marci@1004
|
81 |
wrapper class
|
marci@1004
|
82 |
\code template<typename Graph> class RevGraphWrapper; \endcode
|
marci@1004
|
83 |
has constructor
|
marci@1004
|
84 |
<tt> RevGraphWrapper(Graph& _g)</tt>.
|
marci@1004
|
85 |
This means that in a situation,
|
marci@1004
|
86 |
when a <tt> const ListGraph& </tt> reference to a graph is given,
|
marci@1004
|
87 |
then it have to be instantiated with <tt>Graph=const ListGraph</tt>.
|
marci@1004
|
88 |
\code
|
marci@1004
|
89 |
int algorithm1(const ListGraph& g) {
|
marci@1004
|
90 |
RevGraphWrapper<const ListGraph> rgw(g);
|
marci@1004
|
91 |
return algorithm2(rgw);
|
marci@1004
|
92 |
}
|
marci@1004
|
93 |
\endcode
|
marci@556
|
94 |
|
marci@1004
|
95 |
\addtogroup gwrappers
|
marci@1004
|
96 |
@{
|
marci@556
|
97 |
|
marci@1004
|
98 |
Base type for the Graph Wrappers
|
marci@556
|
99 |
|
marci@1004
|
100 |
\warning Graph wrappers are in even more experimental state than the other
|
marci@1004
|
101 |
parts of the lib. Use them at you own risk.
|
marci@1004
|
102 |
|
marci@1004
|
103 |
This is the base type for most of LEMON graph wrappers.
|
marci@1004
|
104 |
This class implements a trivial graph wrapper i.e. it only wraps the
|
marci@1004
|
105 |
functions and types of the graph. The purpose of this class is to
|
marci@1004
|
106 |
make easier implementing graph wrappers. E.g. if a wrapper is
|
marci@1004
|
107 |
considered which differs from the wrapped graph only in some of its
|
marci@1004
|
108 |
functions or types, then it can be derived from GraphWrapper, and only the
|
marci@1004
|
109 |
differences should be implemented.
|
marci@1004
|
110 |
|
marci@1004
|
111 |
\author Marton Makai
|
marci@1004
|
112 |
*/
|
marci@970
|
113 |
template<typename _Graph>
|
marci@970
|
114 |
class GraphWrapperBase {
|
marci@970
|
115 |
public:
|
marci@970
|
116 |
typedef _Graph Graph;
|
marci@970
|
117 |
/// \todo Is it needed?
|
marci@970
|
118 |
typedef Graph BaseGraph;
|
marci@970
|
119 |
typedef Graph ParentGraph;
|
marci@970
|
120 |
|
marci@556
|
121 |
protected:
|
marci@556
|
122 |
Graph* graph;
|
marci@970
|
123 |
GraphWrapperBase() : graph(0) { }
|
marci@556
|
124 |
void setGraph(Graph& _graph) { graph=&_graph; }
|
marci@556
|
125 |
|
marci@556
|
126 |
public:
|
marci@970
|
127 |
GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
|
marci@992
|
128 |
// GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
|
marci@556
|
129 |
|
alpar@774
|
130 |
typedef typename Graph::Node Node;
|
alpar@774
|
131 |
typedef typename Graph::Edge Edge;
|
marci@556
|
132 |
|
marci@970
|
133 |
void first(Node& i) const { graph->first(i); }
|
marci@970
|
134 |
void first(Edge& i) const { graph->first(i); }
|
marci@970
|
135 |
void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
|
marci@970
|
136 |
void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
|
marci@970
|
137 |
// NodeIt& first(NodeIt& i) const {
|
marci@970
|
138 |
// i=NodeIt(*this); return i;
|
marci@970
|
139 |
// }
|
marci@970
|
140 |
// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@970
|
141 |
// i=OutEdgeIt(*this, p); return i;
|
marci@970
|
142 |
// }
|
marci@970
|
143 |
// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
|
marci@970
|
144 |
// i=InEdgeIt(*this, p); return i;
|
marci@970
|
145 |
// }
|
marci@970
|
146 |
// EdgeIt& first(EdgeIt& i) const {
|
marci@970
|
147 |
// i=EdgeIt(*this); return i;
|
marci@970
|
148 |
// }
|
marci@556
|
149 |
|
marci@970
|
150 |
void next(Node& i) const { graph->next(i); }
|
marci@970
|
151 |
void next(Edge& i) const { graph->next(i); }
|
marci@970
|
152 |
void nextIn(Edge& i) const { graph->nextIn(i); }
|
marci@970
|
153 |
void nextOut(Edge& i) const { graph->nextOut(i); }
|
marci@970
|
154 |
|
alpar@986
|
155 |
Node source(const Edge& e) const { return graph->source(e); }
|
alpar@986
|
156 |
Node target(const Edge& e) const { return graph->target(e); }
|
alpar@986
|
157 |
// Node source(const Edge& e) const {
|
alpar@986
|
158 |
// return Node(graph->source(static_cast<typename Graph::Edge>(e))); }
|
alpar@986
|
159 |
// Node target(const Edge& e) const {
|
alpar@986
|
160 |
// return Node(graph->target(static_cast<typename Graph::Edge>(e))); }
|
marci@556
|
161 |
|
marci@556
|
162 |
int nodeNum() const { return graph->nodeNum(); }
|
marci@556
|
163 |
int edgeNum() const { return graph->edgeNum(); }
|
marci@556
|
164 |
|
marci@556
|
165 |
Node addNode() const { return Node(graph->addNode()); }
|
alpar@986
|
166 |
Edge addEdge(const Node& source, const Node& target) const {
|
alpar@986
|
167 |
return Edge(graph->addEdge(source, target)); }
|
marci@556
|
168 |
|
marci@556
|
169 |
void erase(const Node& i) const { graph->erase(i); }
|
marci@556
|
170 |
void erase(const Edge& i) const { graph->erase(i); }
|
marci@556
|
171 |
|
marci@556
|
172 |
void clear() const { graph->clear(); }
|
marci@556
|
173 |
|
alpar@736
|
174 |
bool forward(const Edge& e) const { return graph->forward(e); }
|
alpar@736
|
175 |
bool backward(const Edge& e) const { return graph->backward(e); }
|
marci@739
|
176 |
|
marci@739
|
177 |
int id(const Node& v) const { return graph->id(v); }
|
marci@739
|
178 |
int id(const Edge& e) const { return graph->id(e); }
|
marci@650
|
179 |
|
marci@738
|
180 |
Edge opposite(const Edge& e) const { return Edge(graph->opposite(e)); }
|
marci@650
|
181 |
|
marci@970
|
182 |
template <typename _Value>
|
marci@970
|
183 |
class NodeMap : public _Graph::template NodeMap<_Value> {
|
marci@970
|
184 |
public:
|
marci@970
|
185 |
typedef typename _Graph::template NodeMap<_Value> Parent;
|
marci@970
|
186 |
NodeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
|
marci@970
|
187 |
NodeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
|
marci@970
|
188 |
: Parent(*gw.graph, value) { }
|
marci@970
|
189 |
};
|
marci@556
|
190 |
|
marci@970
|
191 |
template <typename _Value>
|
marci@970
|
192 |
class EdgeMap : public _Graph::template EdgeMap<_Value> {
|
marci@970
|
193 |
public:
|
marci@970
|
194 |
typedef typename _Graph::template EdgeMap<_Value> Parent;
|
marci@970
|
195 |
EdgeMap(const GraphWrapperBase<_Graph>& gw) : Parent(*gw.graph) { }
|
marci@970
|
196 |
EdgeMap(const GraphWrapperBase<_Graph>& gw, const _Value& value)
|
marci@970
|
197 |
: Parent(*gw.graph, value) { }
|
marci@970
|
198 |
};
|
deba@877
|
199 |
|
marci@556
|
200 |
};
|
marci@556
|
201 |
|
marci@970
|
202 |
template <typename _Graph>
|
marci@970
|
203 |
class GraphWrapper :
|
marci@970
|
204 |
public IterableGraphExtender<GraphWrapperBase<_Graph> > {
|
marci@970
|
205 |
public:
|
marci@970
|
206 |
typedef _Graph Graph;
|
marci@970
|
207 |
typedef IterableGraphExtender<GraphWrapperBase<_Graph> > Parent;
|
marci@970
|
208 |
protected:
|
marci@970
|
209 |
GraphWrapper() : Parent() { }
|
marci@569
|
210 |
|
marci@970
|
211 |
public:
|
marci@970
|
212 |
GraphWrapper(Graph& _graph) { setGraph(_graph); }
|
marci@970
|
213 |
};
|
marci@569
|
214 |
|
marci@997
|
215 |
template <typename _Graph>
|
marci@997
|
216 |
class RevGraphWrapperBase : public GraphWrapperBase<_Graph> {
|
marci@997
|
217 |
public:
|
marci@997
|
218 |
typedef _Graph Graph;
|
marci@997
|
219 |
typedef GraphWrapperBase<_Graph> Parent;
|
marci@997
|
220 |
protected:
|
marci@997
|
221 |
RevGraphWrapperBase() : Parent() { }
|
marci@997
|
222 |
public:
|
marci@997
|
223 |
typedef typename Parent::Node Node;
|
marci@997
|
224 |
typedef typename Parent::Edge Edge;
|
marci@997
|
225 |
|
marci@997
|
226 |
using Parent::first;
|
marci@997
|
227 |
void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
|
marci@997
|
228 |
void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
|
marci@997
|
229 |
|
marci@997
|
230 |
using Parent::next;
|
marci@997
|
231 |
void nextIn(Edge& i) const { Parent::nextOut(i); }
|
marci@997
|
232 |
void nextOut(Edge& i) const { Parent::nextIn(i); }
|
marci@997
|
233 |
|
marci@997
|
234 |
Node source(const Edge& e) const { return Parent::target(e); }
|
marci@997
|
235 |
Node target(const Edge& e) const { return Parent::source(e); }
|
marci@997
|
236 |
};
|
marci@997
|
237 |
|
marci@997
|
238 |
|
marci@556
|
239 |
/// A graph wrapper which reverses the orientation of the edges.
|
marci@556
|
240 |
|
alpar@879
|
241 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
242 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
243 |
///
|
marci@923
|
244 |
/// Let \f$G=(V, A)\f$ be a directed graph and
|
marci@923
|
245 |
/// suppose that a graph instange \c g of type
|
marci@923
|
246 |
/// \c ListGraph implements \f$G\f$.
|
marci@923
|
247 |
/// \code
|
marci@923
|
248 |
/// ListGraph g;
|
marci@923
|
249 |
/// \endcode
|
marci@923
|
250 |
/// For each directed edge
|
marci@923
|
251 |
/// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
|
marci@923
|
252 |
/// reversing its orientation.
|
marci@923
|
253 |
/// Then RevGraphWrapper implements the graph structure with node-set
|
marci@923
|
254 |
/// \f$V\f$ and edge-set
|
marci@923
|
255 |
/// \f$\{\bar e : e\in A \}\f$, i.e. the graph obtained from \f$G\f$ be
|
marci@923
|
256 |
/// reversing the orientation of its edges. The following code shows how
|
marci@923
|
257 |
/// such an instance can be constructed.
|
marci@923
|
258 |
/// \code
|
marci@923
|
259 |
/// RevGraphWrapper<ListGraph> gw(g);
|
marci@923
|
260 |
/// \endcode
|
marci@556
|
261 |
///\author Marton Makai
|
marci@997
|
262 |
template<typename _Graph>
|
marci@997
|
263 |
class RevGraphWrapper :
|
marci@997
|
264 |
public IterableGraphExtender<RevGraphWrapperBase<_Graph> > {
|
marci@650
|
265 |
public:
|
marci@997
|
266 |
typedef _Graph Graph;
|
marci@997
|
267 |
typedef IterableGraphExtender<
|
marci@997
|
268 |
RevGraphWrapperBase<_Graph> > Parent;
|
marci@556
|
269 |
protected:
|
marci@997
|
270 |
RevGraphWrapper() { }
|
marci@556
|
271 |
public:
|
marci@997
|
272 |
RevGraphWrapper(_Graph& _graph) { setGraph(_graph); }
|
marci@997
|
273 |
};
|
marci@997
|
274 |
// template<typename Graph>
|
marci@997
|
275 |
// class RevGraphWrapper : public GraphWrapper<Graph> {
|
marci@997
|
276 |
// public:
|
marci@997
|
277 |
// typedef GraphWrapper<Graph> Parent;
|
marci@997
|
278 |
// protected:
|
marci@997
|
279 |
// RevGraphWrapper() : GraphWrapper<Graph>() { }
|
marci@997
|
280 |
// public:
|
marci@997
|
281 |
// RevGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
|
marci@997
|
282 |
// RevGraphWrapper(const RevGraphWrapper<Graph>& gw) : Parent(gw) { }
|
marci@556
|
283 |
|
marci@997
|
284 |
// typedef typename GraphWrapper<Graph>::Node Node;
|
marci@997
|
285 |
// typedef typename GraphWrapper<Graph>::Edge Edge;
|
marci@997
|
286 |
// //remark: OutEdgeIt and InEdgeIt cannot be typedef-ed to each other
|
marci@997
|
287 |
// //because this does not work is some of them are not defined in the
|
marci@997
|
288 |
// //original graph. The problem with this is that typedef-ed stuff
|
marci@997
|
289 |
// //are instantiated in c++.
|
marci@997
|
290 |
// class OutEdgeIt : public Edge {
|
marci@997
|
291 |
// const RevGraphWrapper<Graph>* gw;
|
marci@997
|
292 |
// friend class GraphWrapper<Graph>;
|
marci@997
|
293 |
// public:
|
marci@997
|
294 |
// OutEdgeIt() { }
|
marci@997
|
295 |
// OutEdgeIt(Invalid i) : Edge(i) { }
|
marci@997
|
296 |
// OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
|
marci@997
|
297 |
// Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
|
marci@997
|
298 |
// OutEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
|
marci@997
|
299 |
// Edge(e), gw(&_gw) { }
|
marci@997
|
300 |
// OutEdgeIt& operator++() {
|
marci@997
|
301 |
// *(static_cast<Edge*>(this))=
|
marci@997
|
302 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@997
|
303 |
// return *this;
|
marci@997
|
304 |
// }
|
marci@997
|
305 |
// };
|
marci@997
|
306 |
// class InEdgeIt : public Edge {
|
marci@997
|
307 |
// const RevGraphWrapper<Graph>* gw;
|
marci@997
|
308 |
// friend class GraphWrapper<Graph>;
|
marci@997
|
309 |
// public:
|
marci@997
|
310 |
// InEdgeIt() { }
|
marci@997
|
311 |
// InEdgeIt(Invalid i) : Edge(i) { }
|
marci@997
|
312 |
// InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Node& n) :
|
marci@997
|
313 |
// Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) { }
|
marci@997
|
314 |
// InEdgeIt(const RevGraphWrapper<Graph>& _gw, const Edge& e) :
|
marci@997
|
315 |
// Edge(e), gw(&_gw) { }
|
marci@997
|
316 |
// InEdgeIt& operator++() {
|
marci@997
|
317 |
// *(static_cast<Edge*>(this))=
|
marci@997
|
318 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@997
|
319 |
// return *this;
|
marci@997
|
320 |
// }
|
marci@997
|
321 |
// };
|
marci@556
|
322 |
|
marci@997
|
323 |
// using GraphWrapper<Graph>::first;
|
marci@997
|
324 |
// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@997
|
325 |
// i=OutEdgeIt(*this, p); return i;
|
marci@997
|
326 |
// }
|
marci@997
|
327 |
// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
|
marci@997
|
328 |
// i=InEdgeIt(*this, p); return i;
|
marci@997
|
329 |
// }
|
marci@556
|
330 |
|
marci@997
|
331 |
// Node source(const Edge& e) const {
|
marci@997
|
332 |
// return GraphWrapper<Graph>::target(e); }
|
marci@997
|
333 |
// Node target(const Edge& e) const {
|
marci@997
|
334 |
// return GraphWrapper<Graph>::source(e); }
|
marci@556
|
335 |
|
marci@997
|
336 |
// // KEEP_MAPS(Parent, RevGraphWrapper);
|
deba@877
|
337 |
|
marci@997
|
338 |
// };
|
marci@556
|
339 |
|
marci@992
|
340 |
|
marci@992
|
341 |
template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
|
marci@992
|
342 |
class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
|
marci@992
|
343 |
public:
|
marci@992
|
344 |
typedef _Graph Graph;
|
marci@992
|
345 |
typedef GraphWrapperBase<_Graph> Parent;
|
marci@992
|
346 |
protected:
|
marci@992
|
347 |
NodeFilterMap* node_filter_map;
|
marci@992
|
348 |
EdgeFilterMap* edge_filter_map;
|
marci@992
|
349 |
SubGraphWrapperBase() : Parent(),
|
marci@992
|
350 |
node_filter_map(0), edge_filter_map(0) { }
|
marci@775
|
351 |
|
marci@992
|
352 |
void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
|
marci@992
|
353 |
node_filter_map=&_node_filter_map;
|
marci@992
|
354 |
}
|
marci@992
|
355 |
void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
|
marci@992
|
356 |
edge_filter_map=&_edge_filter_map;
|
marci@992
|
357 |
}
|
marci@992
|
358 |
|
marci@992
|
359 |
public:
|
marci@992
|
360 |
// SubGraphWrapperBase(Graph& _graph,
|
marci@992
|
361 |
// NodeFilterMap& _node_filter_map,
|
marci@992
|
362 |
// EdgeFilterMap& _edge_filter_map) :
|
marci@992
|
363 |
// Parent(&_graph),
|
marci@992
|
364 |
// node_filter_map(&node_filter_map),
|
marci@992
|
365 |
// edge_filter_map(&edge_filter_map) { }
|
marci@992
|
366 |
|
marci@992
|
367 |
typedef typename Parent::Node Node;
|
marci@992
|
368 |
typedef typename Parent::Edge Edge;
|
marci@992
|
369 |
|
marci@992
|
370 |
void first(Node& i) const {
|
marci@992
|
371 |
Parent::first(i);
|
marci@992
|
372 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
marci@992
|
373 |
}
|
marci@992
|
374 |
void first(Edge& i) const {
|
marci@992
|
375 |
Parent::first(i);
|
marci@992
|
376 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
|
marci@992
|
377 |
}
|
marci@992
|
378 |
void firstIn(Edge& i, const Node& n) const {
|
marci@992
|
379 |
Parent::firstIn(i, n);
|
marci@992
|
380 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
|
marci@992
|
381 |
}
|
marci@992
|
382 |
void firstOut(Edge& i, const Node& n) const {
|
marci@992
|
383 |
Parent::firstOut(i, n);
|
marci@992
|
384 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
|
marci@992
|
385 |
}
|
marci@992
|
386 |
|
marci@992
|
387 |
void next(Node& i) const {
|
marci@992
|
388 |
Parent::next(i);
|
marci@992
|
389 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
marci@992
|
390 |
}
|
marci@992
|
391 |
void next(Edge& i) const {
|
marci@992
|
392 |
Parent::next(i);
|
marci@992
|
393 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
|
marci@992
|
394 |
}
|
marci@992
|
395 |
void nextIn(Edge& i) const {
|
marci@992
|
396 |
Parent::nextIn(i);
|
marci@992
|
397 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
|
marci@992
|
398 |
}
|
marci@992
|
399 |
void nextOut(Edge& i) const {
|
marci@992
|
400 |
Parent::nextOut(i);
|
marci@992
|
401 |
while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
|
marci@992
|
402 |
}
|
marci@992
|
403 |
|
marci@992
|
404 |
/// This function hides \c n in the graph, i.e. the iteration
|
marci@992
|
405 |
/// jumps over it. This is done by simply setting the value of \c n
|
marci@992
|
406 |
/// to be false in the corresponding node-map.
|
marci@992
|
407 |
void hide(const Node& n) const { node_filter_map->set(n, false); }
|
marci@992
|
408 |
|
marci@992
|
409 |
/// This function hides \c e in the graph, i.e. the iteration
|
marci@992
|
410 |
/// jumps over it. This is done by simply setting the value of \c e
|
marci@992
|
411 |
/// to be false in the corresponding edge-map.
|
marci@992
|
412 |
void hide(const Edge& e) const { edge_filter_map->set(e, false); }
|
marci@992
|
413 |
|
marci@992
|
414 |
/// The value of \c n is set to be true in the node-map which stores
|
marci@992
|
415 |
/// hide information. If \c n was hidden previuosly, then it is shown
|
marci@992
|
416 |
/// again
|
marci@992
|
417 |
void unHide(const Node& n) const { node_filter_map->set(n, true); }
|
marci@992
|
418 |
|
marci@992
|
419 |
/// The value of \c e is set to be true in the edge-map which stores
|
marci@992
|
420 |
/// hide information. If \c e was hidden previuosly, then it is shown
|
marci@992
|
421 |
/// again
|
marci@992
|
422 |
void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
|
marci@992
|
423 |
|
marci@992
|
424 |
/// Returns true if \c n is hidden.
|
marci@992
|
425 |
bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
|
marci@992
|
426 |
|
marci@992
|
427 |
/// Returns true if \c n is hidden.
|
marci@992
|
428 |
bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
|
marci@992
|
429 |
|
marci@992
|
430 |
/// \warning This is a linear time operation and works only if s
|
marci@992
|
431 |
/// \c Graph::NodeIt is defined.
|
marci@992
|
432 |
/// \todo assign tags.
|
marci@992
|
433 |
int nodeNum() const {
|
marci@992
|
434 |
int i=0;
|
marci@992
|
435 |
Node n;
|
marci@992
|
436 |
for (first(n); n!=INVALID; next(n)) ++i;
|
marci@992
|
437 |
return i;
|
marci@992
|
438 |
}
|
marci@992
|
439 |
|
marci@992
|
440 |
/// \warning This is a linear time operation and works only if
|
marci@992
|
441 |
/// \c Graph::EdgeIt is defined.
|
marci@992
|
442 |
/// \todo assign tags.
|
marci@992
|
443 |
int edgeNum() const {
|
marci@992
|
444 |
int i=0;
|
marci@992
|
445 |
Edge e;
|
marci@992
|
446 |
for (first(e); e!=INVALID; next(e)) ++i;
|
marci@992
|
447 |
return i;
|
marci@992
|
448 |
}
|
marci@992
|
449 |
|
marci@992
|
450 |
|
marci@992
|
451 |
};
|
marci@775
|
452 |
|
marci@930
|
453 |
/*! \brief A graph wrapper for hiding nodes and edges from a graph.
|
marci@556
|
454 |
|
marci@930
|
455 |
\warning Graph wrappers are in even more experimental state than the other
|
marci@930
|
456 |
parts of the lib. Use them at you own risk.
|
marci@930
|
457 |
|
marci@930
|
458 |
This wrapper shows a graph with filtered node-set and
|
marci@930
|
459 |
edge-set.
|
marci@930
|
460 |
Given a bool-valued map on the node-set and one on
|
marci@930
|
461 |
the edge-set of the graph, the iterators show only the objects
|
marci@930
|
462 |
having true value. We have to note that this does not mean that an
|
marci@930
|
463 |
induced subgraph is obtained, the node-iterator cares only the filter
|
marci@930
|
464 |
on the node-set, and the edge-iterators care only the filter on the
|
marci@930
|
465 |
edge-set.
|
marci@930
|
466 |
\code
|
marci@930
|
467 |
typedef SmartGraph Graph;
|
marci@930
|
468 |
Graph g;
|
marci@930
|
469 |
typedef Graph::Node Node;
|
marci@930
|
470 |
typedef Graph::Edge Edge;
|
marci@930
|
471 |
Node u=g.addNode(); //node of id 0
|
marci@930
|
472 |
Node v=g.addNode(); //node of id 1
|
marci@930
|
473 |
Node e=g.addEdge(u, v); //edge of id 0
|
marci@930
|
474 |
Node f=g.addEdge(v, u); //edge of id 1
|
marci@930
|
475 |
Graph::NodeMap<bool> nm(g, true);
|
marci@930
|
476 |
nm.set(u, false);
|
marci@930
|
477 |
Graph::EdgeMap<bool> em(g, true);
|
marci@930
|
478 |
em.set(e, false);
|
marci@930
|
479 |
typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>, Graph::EdgeMap<bool> > SubGW;
|
marci@930
|
480 |
SubGW gw(g, nm, em);
|
marci@930
|
481 |
for (SubGW::NodeIt n(gw); n!=INVALID; ++n) std::cout << g.id(n) << std::endl;
|
marci@930
|
482 |
std::cout << ":-)" << std::endl;
|
marci@930
|
483 |
for (SubGW::EdgeIt e(gw); e!=INVALID; ++e) std::cout << g.id(e) << std::endl;
|
marci@930
|
484 |
\endcode
|
marci@930
|
485 |
The output of the above code is the following.
|
marci@930
|
486 |
\code
|
marci@930
|
487 |
1
|
marci@930
|
488 |
:-)
|
marci@930
|
489 |
1
|
marci@930
|
490 |
\endcode
|
marci@930
|
491 |
Note that \c n is of type \c SubGW::NodeIt, but it can be converted to
|
marci@930
|
492 |
\c Graph::Node that is why \c g.id(n) can be applied.
|
marci@930
|
493 |
|
marci@933
|
494 |
For other examples see also the documentation of NodeSubGraphWrapper and
|
marci@933
|
495 |
EdgeSubGraphWrapper.
|
marci@930
|
496 |
|
marci@930
|
497 |
\author Marton Makai
|
marci@930
|
498 |
*/
|
marci@992
|
499 |
template<typename _Graph, typename NodeFilterMap,
|
marci@556
|
500 |
typename EdgeFilterMap>
|
marci@992
|
501 |
class SubGraphWrapper :
|
marci@992
|
502 |
public IterableGraphExtender<
|
marci@992
|
503 |
SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
|
marci@650
|
504 |
public:
|
marci@992
|
505 |
typedef _Graph Graph;
|
marci@992
|
506 |
typedef IterableGraphExtender<
|
marci@992
|
507 |
SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
|
marci@556
|
508 |
protected:
|
marci@992
|
509 |
SubGraphWrapper() { }
|
marci@992
|
510 |
public:
|
marci@992
|
511 |
SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
|
marci@992
|
512 |
EdgeFilterMap& _edge_filter_map) {
|
marci@992
|
513 |
setGraph(_graph);
|
marci@992
|
514 |
setNodeFilterMap(_node_filter_map);
|
marci@992
|
515 |
setEdgeFilterMap(_edge_filter_map);
|
marci@992
|
516 |
}
|
marci@992
|
517 |
};
|
marci@556
|
518 |
|
marci@992
|
519 |
// template<typename Graph, typename NodeFilterMap,
|
marci@992
|
520 |
// typename EdgeFilterMap>
|
marci@992
|
521 |
// class SubGraphWrapper : public GraphWrapper<Graph> {
|
marci@992
|
522 |
// public:
|
marci@992
|
523 |
// typedef GraphWrapper<Graph> Parent;
|
marci@992
|
524 |
// protected:
|
marci@992
|
525 |
// NodeFilterMap* node_filter_map;
|
marci@992
|
526 |
// EdgeFilterMap* edge_filter_map;
|
marci@992
|
527 |
|
marci@992
|
528 |
// SubGraphWrapper() : GraphWrapper<Graph>(),
|
marci@992
|
529 |
// node_filter_map(0), edge_filter_map(0) { }
|
marci@992
|
530 |
// void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
|
marci@992
|
531 |
// node_filter_map=&_node_filter_map;
|
marci@992
|
532 |
// }
|
marci@992
|
533 |
// void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
|
marci@992
|
534 |
// edge_filter_map=&_edge_filter_map;
|
marci@992
|
535 |
// }
|
marci@556
|
536 |
|
marci@992
|
537 |
// public:
|
marci@992
|
538 |
// SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
|
marci@992
|
539 |
// EdgeFilterMap& _edge_filter_map) :
|
marci@992
|
540 |
// GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
|
marci@992
|
541 |
// edge_filter_map(&_edge_filter_map) { }
|
marci@556
|
542 |
|
marci@992
|
543 |
// typedef typename GraphWrapper<Graph>::Node Node;
|
marci@992
|
544 |
// class NodeIt : public Node {
|
marci@992
|
545 |
// const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
|
marci@992
|
546 |
// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
|
marci@992
|
547 |
// public:
|
marci@992
|
548 |
// NodeIt() { }
|
marci@992
|
549 |
// NodeIt(Invalid i) : Node(i) { }
|
marci@992
|
550 |
// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
|
marci@992
|
551 |
// Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
|
marci@992
|
552 |
// while (*static_cast<Node*>(this)!=INVALID &&
|
marci@992
|
553 |
// !(*(gw->node_filter_map))[*this])
|
marci@992
|
554 |
// *(static_cast<Node*>(this))=
|
marci@992
|
555 |
// ++(typename Graph::NodeIt(*(gw->graph), *this));
|
marci@992
|
556 |
// }
|
marci@992
|
557 |
// NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
|
marci@992
|
558 |
// const Node& n) :
|
marci@992
|
559 |
// Node(n), gw(&_gw) { }
|
marci@992
|
560 |
// NodeIt& operator++() {
|
marci@992
|
561 |
// *(static_cast<Node*>(this))=
|
marci@992
|
562 |
// ++(typename Graph::NodeIt(*(gw->graph), *this));
|
marci@992
|
563 |
// while (*static_cast<Node*>(this)!=INVALID &&
|
marci@992
|
564 |
// !(*(gw->node_filter_map))[*this])
|
marci@992
|
565 |
// *(static_cast<Node*>(this))=
|
marci@992
|
566 |
// ++(typename Graph::NodeIt(*(gw->graph), *this));
|
marci@992
|
567 |
// return *this;
|
marci@992
|
568 |
// }
|
marci@992
|
569 |
// };
|
marci@992
|
570 |
// typedef typename GraphWrapper<Graph>::Edge Edge;
|
marci@992
|
571 |
// class OutEdgeIt : public Edge {
|
marci@992
|
572 |
// const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
|
marci@992
|
573 |
// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
|
marci@992
|
574 |
// public:
|
marci@992
|
575 |
// OutEdgeIt() { }
|
marci@992
|
576 |
// OutEdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
577 |
// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
|
marci@992
|
578 |
// Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
|
marci@992
|
579 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
580 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
581 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
582 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
583 |
// }
|
marci@992
|
584 |
// OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
|
marci@992
|
585 |
// const Edge& e) :
|
marci@992
|
586 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
587 |
// OutEdgeIt& operator++() {
|
marci@992
|
588 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
589 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
590 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
591 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
592 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
593 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
594 |
// return *this;
|
marci@992
|
595 |
// }
|
marci@992
|
596 |
// };
|
marci@992
|
597 |
// class InEdgeIt : public Edge {
|
marci@992
|
598 |
// const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
|
marci@992
|
599 |
// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
|
marci@992
|
600 |
// public:
|
marci@992
|
601 |
// InEdgeIt() { }
|
marci@992
|
602 |
// // InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
|
marci@992
|
603 |
// InEdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
604 |
// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
|
marci@992
|
605 |
// Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
|
marci@992
|
606 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
607 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
608 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
609 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
610 |
// }
|
marci@992
|
611 |
// InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
|
marci@992
|
612 |
// const Edge& e) :
|
marci@992
|
613 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
614 |
// InEdgeIt& operator++() {
|
marci@992
|
615 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
616 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
617 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
618 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
619 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
620 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
621 |
// return *this;
|
marci@992
|
622 |
// }
|
marci@992
|
623 |
// };
|
marci@992
|
624 |
// class EdgeIt : public Edge {
|
marci@992
|
625 |
// const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
|
marci@992
|
626 |
// friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
|
marci@992
|
627 |
// public:
|
marci@992
|
628 |
// EdgeIt() { }
|
marci@992
|
629 |
// EdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
630 |
// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
|
marci@992
|
631 |
// Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
|
marci@992
|
632 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
633 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
634 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
635 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
636 |
// }
|
marci@992
|
637 |
// EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
|
marci@992
|
638 |
// const Edge& e) :
|
marci@992
|
639 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
640 |
// EdgeIt& operator++() {
|
marci@992
|
641 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
642 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
643 |
// while (*static_cast<Edge*>(this)!=INVALID &&
|
marci@992
|
644 |
// !(*(gw->edge_filter_map))[*this])
|
marci@992
|
645 |
// *(static_cast<Edge*>(this))=
|
marci@992
|
646 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
647 |
// return *this;
|
marci@992
|
648 |
// }
|
marci@992
|
649 |
// };
|
marci@556
|
650 |
|
marci@992
|
651 |
// NodeIt& first(NodeIt& i) const {
|
marci@992
|
652 |
// i=NodeIt(*this); return i;
|
marci@992
|
653 |
// }
|
marci@992
|
654 |
// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@992
|
655 |
// i=OutEdgeIt(*this, p); return i;
|
marci@992
|
656 |
// }
|
marci@992
|
657 |
// InEdgeIt& first(InEdgeIt& i, const Node& p) const {
|
marci@992
|
658 |
// i=InEdgeIt(*this, p); return i;
|
marci@992
|
659 |
// }
|
marci@992
|
660 |
// EdgeIt& first(EdgeIt& i) const {
|
marci@992
|
661 |
// i=EdgeIt(*this); return i;
|
marci@992
|
662 |
// }
|
marci@556
|
663 |
|
marci@992
|
664 |
// /// This function hides \c n in the graph, i.e. the iteration
|
marci@992
|
665 |
// /// jumps over it. This is done by simply setting the value of \c n
|
marci@992
|
666 |
// /// to be false in the corresponding node-map.
|
marci@992
|
667 |
// void hide(const Node& n) const { node_filter_map->set(n, false); }
|
marci@561
|
668 |
|
marci@992
|
669 |
// /// This function hides \c e in the graph, i.e. the iteration
|
marci@992
|
670 |
// /// jumps over it. This is done by simply setting the value of \c e
|
marci@992
|
671 |
// /// to be false in the corresponding edge-map.
|
marci@992
|
672 |
// void hide(const Edge& e) const { edge_filter_map->set(e, false); }
|
marci@556
|
673 |
|
marci@992
|
674 |
// /// The value of \c n is set to be true in the node-map which stores
|
marci@992
|
675 |
// /// hide information. If \c n was hidden previuosly, then it is shown
|
marci@992
|
676 |
// /// again
|
marci@992
|
677 |
// void unHide(const Node& n) const { node_filter_map->set(n, true); }
|
marci@561
|
678 |
|
marci@992
|
679 |
// /// The value of \c e is set to be true in the edge-map which stores
|
marci@992
|
680 |
// /// hide information. If \c e was hidden previuosly, then it is shown
|
marci@992
|
681 |
// /// again
|
marci@992
|
682 |
// void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
|
marci@556
|
683 |
|
marci@992
|
684 |
// /// Returns true if \c n is hidden.
|
marci@992
|
685 |
// bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
|
marci@561
|
686 |
|
marci@992
|
687 |
// /// Returns true if \c n is hidden.
|
marci@992
|
688 |
// bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
|
marci@593
|
689 |
|
marci@992
|
690 |
// /// \warning This is a linear time operation and works only if
|
marci@992
|
691 |
// /// \c Graph::NodeIt is defined.
|
marci@992
|
692 |
// int nodeNum() const {
|
marci@992
|
693 |
// int i=0;
|
marci@992
|
694 |
// for (NodeIt n(*this); n!=INVALID; ++n) ++i;
|
marci@992
|
695 |
// return i;
|
marci@992
|
696 |
// }
|
marci@593
|
697 |
|
marci@992
|
698 |
// /// \warning This is a linear time operation and works only if
|
marci@992
|
699 |
// /// \c Graph::EdgeIt is defined.
|
marci@992
|
700 |
// int edgeNum() const {
|
marci@992
|
701 |
// int i=0;
|
marci@992
|
702 |
// for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
|
marci@992
|
703 |
// return i;
|
marci@992
|
704 |
// }
|
marci@593
|
705 |
|
marci@992
|
706 |
// // KEEP_MAPS(Parent, SubGraphWrapper);
|
marci@992
|
707 |
// };
|
marci@556
|
708 |
|
marci@569
|
709 |
|
marci@933
|
710 |
/*! \brief A wrapper for hiding nodes from a graph.
|
marci@933
|
711 |
|
marci@933
|
712 |
\warning Graph wrappers are in even more experimental state than the other
|
marci@933
|
713 |
parts of the lib. Use them at you own risk.
|
marci@933
|
714 |
|
marci@933
|
715 |
A wrapper for hiding nodes from a graph.
|
marci@933
|
716 |
This wrapper specializes SubGraphWrapper in the way that only the node-set
|
marci@933
|
717 |
can be filtered. Note that this does not mean of considering induced
|
marci@933
|
718 |
subgraph, the edge-iterators consider the original edge-set.
|
marci@933
|
719 |
\author Marton Makai
|
marci@933
|
720 |
*/
|
marci@933
|
721 |
template<typename Graph, typename NodeFilterMap>
|
marci@933
|
722 |
class NodeSubGraphWrapper :
|
marci@933
|
723 |
public SubGraphWrapper<Graph, NodeFilterMap,
|
marci@933
|
724 |
ConstMap<typename Graph::Edge,bool> > {
|
marci@933
|
725 |
public:
|
marci@933
|
726 |
typedef SubGraphWrapper<Graph, NodeFilterMap,
|
marci@933
|
727 |
ConstMap<typename Graph::Edge,bool> > Parent;
|
marci@933
|
728 |
protected:
|
marci@933
|
729 |
ConstMap<typename Graph::Edge, bool> const_true_map;
|
marci@933
|
730 |
public:
|
marci@933
|
731 |
NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
|
marci@933
|
732 |
Parent(), const_true_map(true) {
|
marci@933
|
733 |
Parent::setGraph(_graph);
|
marci@933
|
734 |
Parent::setNodeFilterMap(_node_filter_map);
|
marci@933
|
735 |
Parent::setEdgeFilterMap(const_true_map);
|
marci@933
|
736 |
}
|
marci@933
|
737 |
};
|
marci@933
|
738 |
|
marci@933
|
739 |
|
marci@932
|
740 |
/*! \brief A wrapper for hiding edges from a graph.
|
marci@932
|
741 |
|
marci@932
|
742 |
\warning Graph wrappers are in even more experimental state than the other
|
marci@932
|
743 |
parts of the lib. Use them at you own risk.
|
marci@932
|
744 |
|
marci@932
|
745 |
A wrapper for hiding edges from a graph.
|
marci@932
|
746 |
This wrapper specializes SubGraphWrapper in the way that only the edge-set
|
marci@933
|
747 |
can be filtered. The usefulness of this wrapper is demonstrated in the
|
marci@933
|
748 |
problem of searching a maximum number of edge-disjoint shortest paths
|
marci@933
|
749 |
between
|
marci@933
|
750 |
two nodes \c s and \c t. Shortest here means being shortest w.r.t.
|
marci@933
|
751 |
non-negative edge-lengths. Note that
|
marci@933
|
752 |
the comprehension of the presented solution
|
marci@933
|
753 |
need's some knowledge from elementary combinatorial optimization.
|
marci@933
|
754 |
|
marci@933
|
755 |
If a single shortest path is to be
|
marci@933
|
756 |
searched between two nodes \c s and \c t, then this can be done easily by
|
marci@933
|
757 |
applying the Dijkstra algorithm class. What happens, if a maximum number of
|
marci@933
|
758 |
edge-disjoint shortest paths is to be computed. It can be proved that an
|
marci@933
|
759 |
edge can be in a shortest path if and only if it is tight with respect to
|
marci@933
|
760 |
the potential function computed by Dijkstra. Moreover, any path containing
|
marci@933
|
761 |
only such edges is a shortest one. Thus we have to compute a maximum number
|
marci@933
|
762 |
of edge-disjoint paths between \c s and \c t in the graph which has edge-set
|
marci@933
|
763 |
all the tight edges. The computation will be demonstrated on the following
|
marci@933
|
764 |
graph, which is read from a dimacs file.
|
marci@933
|
765 |
|
marci@933
|
766 |
\dot
|
marci@933
|
767 |
digraph lemon_dot_example {
|
marci@933
|
768 |
node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
|
marci@933
|
769 |
n0 [ label="0 (s)" ];
|
marci@933
|
770 |
n1 [ label="1" ];
|
marci@933
|
771 |
n2 [ label="2" ];
|
marci@933
|
772 |
n3 [ label="3" ];
|
marci@933
|
773 |
n4 [ label="4" ];
|
marci@933
|
774 |
n5 [ label="5" ];
|
marci@933
|
775 |
n6 [ label="6 (t)" ];
|
marci@933
|
776 |
edge [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
|
marci@933
|
777 |
n5 -> n6 [ label="9, length:4" ];
|
marci@933
|
778 |
n4 -> n6 [ label="8, length:2" ];
|
marci@933
|
779 |
n3 -> n5 [ label="7, length:1" ];
|
marci@933
|
780 |
n2 -> n5 [ label="6, length:3" ];
|
marci@933
|
781 |
n2 -> n6 [ label="5, length:5" ];
|
marci@933
|
782 |
n2 -> n4 [ label="4, length:2" ];
|
marci@933
|
783 |
n1 -> n4 [ label="3, length:3" ];
|
marci@933
|
784 |
n0 -> n3 [ label="2, length:1" ];
|
marci@933
|
785 |
n0 -> n2 [ label="1, length:2" ];
|
marci@933
|
786 |
n0 -> n1 [ label="0, length:3" ];
|
marci@933
|
787 |
}
|
marci@933
|
788 |
\enddot
|
marci@933
|
789 |
|
marci@933
|
790 |
\code
|
marci@933
|
791 |
Graph g;
|
marci@933
|
792 |
Node s, t;
|
marci@933
|
793 |
LengthMap length(g);
|
marci@933
|
794 |
|
marci@933
|
795 |
readDimacs(std::cin, g, length, s, t);
|
marci@933
|
796 |
|
alpar@986
|
797 |
cout << "edges with lengths (of form id, source--length->target): " << endl;
|
marci@933
|
798 |
for(EdgeIt e(g); e!=INVALID; ++e)
|
alpar@986
|
799 |
cout << g.id(e) << ", " << g.id(g.source(e)) << "--"
|
alpar@986
|
800 |
<< length[e] << "->" << g.id(g.target(e)) << endl;
|
marci@933
|
801 |
|
marci@933
|
802 |
cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
|
marci@933
|
803 |
\endcode
|
marci@933
|
804 |
Next, the potential function is computed with Dijkstra.
|
marci@933
|
805 |
\code
|
marci@933
|
806 |
typedef Dijkstra<Graph, LengthMap> Dijkstra;
|
marci@933
|
807 |
Dijkstra dijkstra(g, length);
|
marci@933
|
808 |
dijkstra.run(s);
|
marci@933
|
809 |
\endcode
|
marci@933
|
810 |
Next, we consrtruct a map which filters the edge-set to the tight edges.
|
marci@933
|
811 |
\code
|
marci@933
|
812 |
typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
|
marci@933
|
813 |
TightEdgeFilter;
|
marci@933
|
814 |
TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
|
marci@933
|
815 |
|
marci@933
|
816 |
typedef EdgeSubGraphWrapper<Graph, TightEdgeFilter> SubGW;
|
marci@933
|
817 |
SubGW gw(g, tight_edge_filter);
|
marci@933
|
818 |
\endcode
|
marci@933
|
819 |
Then, the maximum nimber of edge-disjoint \c s-\c t paths are computed
|
marci@933
|
820 |
with a max flow algorithm Preflow.
|
marci@933
|
821 |
\code
|
marci@933
|
822 |
ConstMap<Edge, int> const_1_map(1);
|
marci@933
|
823 |
Graph::EdgeMap<int> flow(g, 0);
|
marci@933
|
824 |
|
marci@933
|
825 |
Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
|
marci@933
|
826 |
preflow(gw, s, t, const_1_map, flow);
|
marci@933
|
827 |
preflow.run();
|
marci@933
|
828 |
\endcode
|
marci@933
|
829 |
Last, the output is:
|
marci@933
|
830 |
\code
|
marci@933
|
831 |
cout << "maximum number of edge-disjoint shortest path: "
|
marci@933
|
832 |
<< preflow.flowValue() << endl;
|
marci@933
|
833 |
cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
|
marci@933
|
834 |
<< endl;
|
marci@933
|
835 |
for(EdgeIt e(g); e!=INVALID; ++e)
|
marci@933
|
836 |
if (flow[e])
|
alpar@986
|
837 |
cout << " " << g.id(g.source(e)) << "--"
|
alpar@986
|
838 |
<< length[e] << "->" << g.id(g.target(e)) << endl;
|
marci@933
|
839 |
\endcode
|
marci@933
|
840 |
The program has the following (expected :-)) output:
|
marci@933
|
841 |
\code
|
alpar@986
|
842 |
edges with lengths (of form id, source--length->target):
|
marci@933
|
843 |
9, 5--4->6
|
marci@933
|
844 |
8, 4--2->6
|
marci@933
|
845 |
7, 3--1->5
|
marci@933
|
846 |
6, 2--3->5
|
marci@933
|
847 |
5, 2--5->6
|
marci@933
|
848 |
4, 2--2->4
|
marci@933
|
849 |
3, 1--3->4
|
marci@933
|
850 |
2, 0--1->3
|
marci@933
|
851 |
1, 0--2->2
|
marci@933
|
852 |
0, 0--3->1
|
marci@933
|
853 |
s: 0 t: 6
|
marci@933
|
854 |
maximum number of edge-disjoint shortest path: 2
|
marci@933
|
855 |
edges of the maximum number of edge-disjoint shortest s-t paths:
|
marci@933
|
856 |
9, 5--4->6
|
marci@933
|
857 |
8, 4--2->6
|
marci@933
|
858 |
7, 3--1->5
|
marci@933
|
859 |
4, 2--2->4
|
marci@933
|
860 |
2, 0--1->3
|
marci@933
|
861 |
1, 0--2->2
|
marci@933
|
862 |
\endcode
|
marci@933
|
863 |
|
marci@932
|
864 |
\author Marton Makai
|
marci@932
|
865 |
*/
|
marci@932
|
866 |
template<typename Graph, typename EdgeFilterMap>
|
marci@932
|
867 |
class EdgeSubGraphWrapper :
|
marci@932
|
868 |
public SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
|
marci@932
|
869 |
EdgeFilterMap> {
|
marci@932
|
870 |
public:
|
marci@932
|
871 |
typedef SubGraphWrapper<Graph, ConstMap<typename Graph::Node,bool>,
|
marci@932
|
872 |
EdgeFilterMap> Parent;
|
marci@932
|
873 |
protected:
|
marci@932
|
874 |
ConstMap<typename Graph::Node, bool> const_true_map;
|
marci@932
|
875 |
public:
|
marci@932
|
876 |
EdgeSubGraphWrapper(Graph& _graph, EdgeFilterMap& _edge_filter_map) :
|
marci@932
|
877 |
Parent(), const_true_map(true) {
|
marci@932
|
878 |
Parent::setGraph(_graph);
|
marci@932
|
879 |
Parent::setNodeFilterMap(const_true_map);
|
marci@932
|
880 |
Parent::setEdgeFilterMap(_edge_filter_map);
|
marci@932
|
881 |
}
|
marci@932
|
882 |
};
|
marci@932
|
883 |
|
marci@569
|
884 |
|
marci@556
|
885 |
template<typename Graph>
|
marci@556
|
886 |
class UndirGraphWrapper : public GraphWrapper<Graph> {
|
marci@650
|
887 |
public:
|
marci@650
|
888 |
typedef GraphWrapper<Graph> Parent;
|
marci@556
|
889 |
protected:
|
marci@556
|
890 |
UndirGraphWrapper() : GraphWrapper<Graph>() { }
|
marci@556
|
891 |
|
marci@556
|
892 |
public:
|
marci@556
|
893 |
typedef typename GraphWrapper<Graph>::Node Node;
|
marci@556
|
894 |
typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
|
marci@556
|
895 |
typedef typename GraphWrapper<Graph>::Edge Edge;
|
marci@556
|
896 |
typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
|
marci@556
|
897 |
|
marci@556
|
898 |
UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }
|
marci@556
|
899 |
|
marci@556
|
900 |
class OutEdgeIt {
|
marci@556
|
901 |
friend class UndirGraphWrapper<Graph>;
|
marci@556
|
902 |
bool out_or_in; //true iff out
|
marci@556
|
903 |
typename Graph::OutEdgeIt out;
|
marci@556
|
904 |
typename Graph::InEdgeIt in;
|
marci@556
|
905 |
public:
|
marci@556
|
906 |
OutEdgeIt() { }
|
marci@556
|
907 |
OutEdgeIt(const Invalid& i) : Edge(i) { }
|
marci@556
|
908 |
OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
|
marci@556
|
909 |
out_or_in=true; _G.graph->first(out, _n);
|
marci@556
|
910 |
if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n); }
|
marci@556
|
911 |
}
|
marci@556
|
912 |
operator Edge() const {
|
marci@556
|
913 |
if (out_or_in) return Edge(out); else return Edge(in);
|
marci@556
|
914 |
}
|
marci@556
|
915 |
};
|
marci@556
|
916 |
|
marci@556
|
917 |
typedef OutEdgeIt InEdgeIt;
|
marci@556
|
918 |
|
marci@556
|
919 |
using GraphWrapper<Graph>::first;
|
marci@556
|
920 |
OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@556
|
921 |
i=OutEdgeIt(*this, p); return i;
|
marci@556
|
922 |
}
|
marci@556
|
923 |
|
marci@556
|
924 |
using GraphWrapper<Graph>::next;
|
alpar@878
|
925 |
|
marci@556
|
926 |
OutEdgeIt& next(OutEdgeIt& e) const {
|
marci@556
|
927 |
if (e.out_or_in) {
|
alpar@986
|
928 |
typename Graph::Node n=this->graph->source(e.out);
|
marci@556
|
929 |
this->graph->next(e.out);
|
marci@556
|
930 |
if (!this->graph->valid(e.out)) {
|
marci@556
|
931 |
e.out_or_in=false; this->graph->first(e.in, n); }
|
marci@556
|
932 |
} else {
|
marci@556
|
933 |
this->graph->next(e.in);
|
marci@556
|
934 |
}
|
marci@556
|
935 |
return e;
|
marci@556
|
936 |
}
|
marci@556
|
937 |
|
marci@556
|
938 |
Node aNode(const OutEdgeIt& e) const {
|
alpar@986
|
939 |
if (e.out_or_in) return this->graph->source(e); else
|
alpar@986
|
940 |
return this->graph->target(e); }
|
marci@556
|
941 |
Node bNode(const OutEdgeIt& e) const {
|
alpar@986
|
942 |
if (e.out_or_in) return this->graph->target(e); else
|
alpar@986
|
943 |
return this->graph->source(e); }
|
deba@877
|
944 |
|
deba@891
|
945 |
// KEEP_MAPS(Parent, UndirGraphWrapper);
|
deba@877
|
946 |
|
marci@556
|
947 |
};
|
marci@556
|
948 |
|
marci@910
|
949 |
// /// \brief An undirected graph template.
|
marci@910
|
950 |
// ///
|
marci@910
|
951 |
// ///\warning Graph wrappers are in even more experimental state than the other
|
marci@910
|
952 |
// ///parts of the lib. Use them at your own risk.
|
marci@910
|
953 |
// ///
|
marci@910
|
954 |
// /// An undirected graph template.
|
marci@910
|
955 |
// /// This class works as an undirected graph and a directed graph of
|
marci@910
|
956 |
// /// class \c Graph is used for the physical storage.
|
marci@910
|
957 |
// /// \ingroup graphs
|
marci@556
|
958 |
template<typename Graph>
|
marci@556
|
959 |
class UndirGraph : public UndirGraphWrapper<Graph> {
|
marci@556
|
960 |
typedef UndirGraphWrapper<Graph> Parent;
|
marci@556
|
961 |
protected:
|
marci@556
|
962 |
Graph gr;
|
marci@556
|
963 |
public:
|
marci@556
|
964 |
UndirGraph() : UndirGraphWrapper<Graph>() {
|
marci@556
|
965 |
Parent::setGraph(gr);
|
marci@556
|
966 |
}
|
deba@877
|
967 |
|
deba@891
|
968 |
// KEEP_MAPS(Parent, UndirGraph);
|
marci@556
|
969 |
};
|
marci@556
|
970 |
|
marci@992
|
971 |
|
marci@992
|
972 |
template <typename _Graph,
|
marci@992
|
973 |
typename ForwardFilterMap, typename BackwardFilterMap>
|
marci@992
|
974 |
class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
|
marci@992
|
975 |
public:
|
marci@992
|
976 |
typedef _Graph Graph;
|
marci@992
|
977 |
typedef GraphWrapperBase<_Graph> Parent;
|
marci@992
|
978 |
protected:
|
marci@992
|
979 |
ForwardFilterMap* forward_filter;
|
marci@992
|
980 |
BackwardFilterMap* backward_filter;
|
marci@992
|
981 |
SubBidirGraphWrapperBase() : Parent(),
|
marci@992
|
982 |
forward_filter(0), backward_filter(0) { }
|
marci@992
|
983 |
|
marci@992
|
984 |
void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
|
marci@992
|
985 |
forward_filter=&_forward_filter;
|
marci@992
|
986 |
}
|
marci@992
|
987 |
void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
|
marci@992
|
988 |
backward_filter=&_backward_filter;
|
marci@992
|
989 |
}
|
marci@992
|
990 |
|
marci@992
|
991 |
public:
|
marci@992
|
992 |
// SubGraphWrapperBase(Graph& _graph,
|
marci@992
|
993 |
// NodeFilterMap& _node_filter_map,
|
marci@992
|
994 |
// EdgeFilterMap& _edge_filter_map) :
|
marci@992
|
995 |
// Parent(&_graph),
|
marci@992
|
996 |
// node_filter_map(&node_filter_map),
|
marci@992
|
997 |
// edge_filter_map(&edge_filter_map) { }
|
marci@992
|
998 |
|
marci@992
|
999 |
typedef typename Parent::Node Node;
|
marci@992
|
1000 |
typedef typename _Graph::Edge GraphEdge;
|
marci@992
|
1001 |
template <typename T> class EdgeMap;
|
marci@992
|
1002 |
/// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
|
marci@992
|
1003 |
/// _Graph::Edge. It contains an extra bool flag which is true
|
marci@992
|
1004 |
/// if and only if the
|
marci@992
|
1005 |
/// edge is the backward version of the original edge.
|
marci@992
|
1006 |
class Edge : public _Graph::Edge {
|
marci@992
|
1007 |
friend class SubBidirGraphWrapperBase<
|
marci@992
|
1008 |
Graph, ForwardFilterMap, BackwardFilterMap>;
|
marci@992
|
1009 |
template<typename T> friend class EdgeMap;
|
marci@992
|
1010 |
protected:
|
marci@992
|
1011 |
bool backward; //true, iff backward
|
marci@992
|
1012 |
public:
|
marci@992
|
1013 |
Edge() { }
|
marci@992
|
1014 |
/// \todo =false is needed, or causes problems?
|
marci@992
|
1015 |
/// If \c _backward is false, then we get an edge corresponding to the
|
marci@992
|
1016 |
/// original one, otherwise its oppositely directed pair is obtained.
|
marci@992
|
1017 |
Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
|
marci@992
|
1018 |
_Graph::Edge(e), backward(_backward) { }
|
marci@992
|
1019 |
Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
|
marci@992
|
1020 |
bool operator==(const Edge& v) const {
|
marci@992
|
1021 |
return (this->backward==v.backward &&
|
marci@992
|
1022 |
static_cast<typename _Graph::Edge>(*this)==
|
marci@992
|
1023 |
static_cast<typename _Graph::Edge>(v));
|
marci@992
|
1024 |
}
|
marci@992
|
1025 |
bool operator!=(const Edge& v) const {
|
marci@992
|
1026 |
return (this->backward!=v.backward ||
|
marci@992
|
1027 |
static_cast<typename _Graph::Edge>(*this)!=
|
marci@992
|
1028 |
static_cast<typename _Graph::Edge>(v));
|
marci@992
|
1029 |
}
|
marci@992
|
1030 |
};
|
marci@992
|
1031 |
|
marci@992
|
1032 |
void first(Node& i) const {
|
marci@992
|
1033 |
Parent::first(i);
|
marci@992
|
1034 |
}
|
marci@992
|
1035 |
|
marci@992
|
1036 |
void first(Edge& i) const {
|
marci@992
|
1037 |
Parent::first(i);
|
marci@992
|
1038 |
i.backward=false;
|
marci@992
|
1039 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1040 |
!(*forward_filter)[i]) Parent::next(i);
|
marci@992
|
1041 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1042 |
Parent::first(i);
|
marci@992
|
1043 |
i.backward=true;
|
marci@992
|
1044 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1045 |
!(*backward_filter)[i]) Parent::next(i);
|
marci@992
|
1046 |
}
|
marci@992
|
1047 |
}
|
marci@992
|
1048 |
|
marci@992
|
1049 |
void firstIn(Edge& i, const Node& n) const {
|
marci@992
|
1050 |
Parent::firstIn(i, n);
|
marci@992
|
1051 |
i.backward=false;
|
marci@992
|
1052 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1053 |
!(*forward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1054 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1055 |
Parent::firstOut(i, n);
|
marci@992
|
1056 |
i.backward=true;
|
marci@992
|
1057 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1058 |
!(*backward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1059 |
}
|
marci@992
|
1060 |
}
|
marci@992
|
1061 |
|
marci@992
|
1062 |
void firstOut(Edge& i, const Node& n) const {
|
marci@992
|
1063 |
Parent::firstOut(i, n);
|
marci@992
|
1064 |
i.backward=false;
|
marci@992
|
1065 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1066 |
!(*forward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1067 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1068 |
Parent::firstIn(i, n);
|
marci@992
|
1069 |
i.backward=true;
|
marci@992
|
1070 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1071 |
!(*backward_filter)[i]) Parent::nextIn(i);
|
marci@992
|
1072 |
}
|
marci@992
|
1073 |
}
|
marci@992
|
1074 |
|
marci@992
|
1075 |
void next(Node& i) const {
|
marci@992
|
1076 |
Parent::next(i);
|
marci@992
|
1077 |
}
|
marci@992
|
1078 |
|
marci@992
|
1079 |
void next(Edge& i) const {
|
marci@992
|
1080 |
if (!(i.backward)) {
|
marci@992
|
1081 |
Parent::next(i);
|
marci@992
|
1082 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1083 |
!(*forward_filter)[i]) Parent::next(i);
|
marci@992
|
1084 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1085 |
Parent::first(i);
|
marci@992
|
1086 |
i.backward=true;
|
marci@992
|
1087 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1088 |
!(*backward_filter)[i]) Parent::next(i);
|
marci@992
|
1089 |
}
|
marci@992
|
1090 |
} else {
|
marci@992
|
1091 |
Parent::next(i);
|
marci@992
|
1092 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1093 |
!(*backward_filter)[i]) Parent::next(i);
|
marci@992
|
1094 |
}
|
marci@992
|
1095 |
}
|
marci@992
|
1096 |
|
marci@992
|
1097 |
void nextIn(Edge& i) const {
|
marci@992
|
1098 |
if (!(i.backward)) {
|
marci@992
|
1099 |
Node n=Parent::target(i);
|
marci@992
|
1100 |
Parent::nextIn(i);
|
marci@992
|
1101 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1102 |
!(*forward_filter)[i]) Parent::nextIn(i);
|
marci@992
|
1103 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1104 |
Parent::firstOut(i, n);
|
marci@992
|
1105 |
i.backward=true;
|
marci@992
|
1106 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1107 |
!(*backward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1108 |
}
|
marci@992
|
1109 |
} else {
|
marci@992
|
1110 |
Parent::nextOut(i);
|
marci@992
|
1111 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1112 |
!(*backward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1113 |
}
|
marci@992
|
1114 |
}
|
marci@992
|
1115 |
|
marci@992
|
1116 |
void nextOut(Edge& i) const {
|
marci@992
|
1117 |
if (!(i.backward)) {
|
marci@992
|
1118 |
Node n=Parent::source(i);
|
marci@992
|
1119 |
Parent::nextOut(i);
|
marci@992
|
1120 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1121 |
!(*forward_filter)[i]) Parent::nextOut(i);
|
marci@992
|
1122 |
if (*static_cast<GraphEdge*>(&i)==INVALID) {
|
marci@992
|
1123 |
Parent::firstIn(i, n);
|
marci@992
|
1124 |
i.backward=true;
|
marci@992
|
1125 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1126 |
!(*backward_filter)[i]) Parent::nextIn(i);
|
marci@992
|
1127 |
}
|
marci@992
|
1128 |
} else {
|
marci@992
|
1129 |
Parent::nextIn(i);
|
marci@992
|
1130 |
while (*static_cast<GraphEdge*>(&i)!=INVALID &&
|
marci@992
|
1131 |
!(*backward_filter)[i]) Parent::nextIn(i);
|
marci@992
|
1132 |
}
|
marci@992
|
1133 |
}
|
marci@992
|
1134 |
|
marci@992
|
1135 |
Node source(Edge e) const {
|
marci@992
|
1136 |
return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
|
marci@992
|
1137 |
Node target(Edge e) const {
|
marci@992
|
1138 |
return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
|
marci@992
|
1139 |
|
marci@992
|
1140 |
/// Gives back the opposite edge.
|
marci@992
|
1141 |
Edge opposite(const Edge& e) const {
|
marci@992
|
1142 |
Edge f=e;
|
marci@992
|
1143 |
f.backward=!f.backward;
|
marci@992
|
1144 |
return f;
|
marci@992
|
1145 |
}
|
marci@992
|
1146 |
|
marci@992
|
1147 |
/// \warning This is a linear time operation and works only if
|
marci@992
|
1148 |
/// \c Graph::EdgeIt is defined.
|
marci@992
|
1149 |
/// \todo hmm
|
marci@992
|
1150 |
int edgeNum() const {
|
marci@992
|
1151 |
int i=0;
|
marci@992
|
1152 |
Edge e;
|
marci@992
|
1153 |
for (first(e); e!=INVALID; next(e)) ++i;
|
marci@992
|
1154 |
return i;
|
marci@992
|
1155 |
}
|
marci@992
|
1156 |
|
marci@992
|
1157 |
bool forward(const Edge& e) const { return !e.backward; }
|
marci@992
|
1158 |
bool backward(const Edge& e) const { return e.backward; }
|
marci@992
|
1159 |
|
marci@992
|
1160 |
template <typename T>
|
marci@992
|
1161 |
/// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
|
marci@992
|
1162 |
/// _Graph::EdgeMap one for the forward edges and
|
marci@992
|
1163 |
/// one for the backward edges.
|
marci@992
|
1164 |
class EdgeMap {
|
marci@992
|
1165 |
template <typename TT> friend class EdgeMap;
|
marci@992
|
1166 |
typename _Graph::template EdgeMap<T> forward_map, backward_map;
|
marci@992
|
1167 |
public:
|
marci@992
|
1168 |
typedef T Value;
|
marci@992
|
1169 |
typedef Edge Key;
|
marci@992
|
1170 |
|
marci@992
|
1171 |
EdgeMap(const SubBidirGraphWrapperBase<_Graph,
|
marci@992
|
1172 |
ForwardFilterMap, BackwardFilterMap>& g) :
|
marci@992
|
1173 |
forward_map(*(g.graph)), backward_map(*(g.graph)) { }
|
marci@992
|
1174 |
|
marci@992
|
1175 |
EdgeMap(const SubBidirGraphWrapperBase<_Graph,
|
marci@992
|
1176 |
ForwardFilterMap, BackwardFilterMap>& g, T a) :
|
marci@992
|
1177 |
forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
|
marci@992
|
1178 |
|
marci@992
|
1179 |
void set(Edge e, T a) {
|
marci@992
|
1180 |
if (!e.backward)
|
marci@992
|
1181 |
forward_map.set(e, a);
|
marci@992
|
1182 |
else
|
marci@992
|
1183 |
backward_map.set(e, a);
|
marci@992
|
1184 |
}
|
marci@992
|
1185 |
|
marci@992
|
1186 |
// typename _Graph::template EdgeMap<T>::ConstReference
|
marci@992
|
1187 |
// operator[](Edge e) const {
|
marci@992
|
1188 |
// if (!e.backward)
|
marci@992
|
1189 |
// return forward_map[e];
|
marci@992
|
1190 |
// else
|
marci@992
|
1191 |
// return backward_map[e];
|
marci@992
|
1192 |
// }
|
marci@992
|
1193 |
|
marci@992
|
1194 |
// typename _Graph::template EdgeMap<T>::Reference
|
marci@992
|
1195 |
T operator[](Edge e) {
|
marci@992
|
1196 |
if (!e.backward)
|
marci@992
|
1197 |
return forward_map[e];
|
marci@992
|
1198 |
else
|
marci@992
|
1199 |
return backward_map[e];
|
marci@992
|
1200 |
}
|
marci@992
|
1201 |
|
marci@992
|
1202 |
void update() {
|
marci@992
|
1203 |
forward_map.update();
|
marci@992
|
1204 |
backward_map.update();
|
marci@992
|
1205 |
}
|
marci@992
|
1206 |
};
|
marci@992
|
1207 |
|
marci@992
|
1208 |
};
|
marci@569
|
1209 |
|
marci@650
|
1210 |
|
marci@650
|
1211 |
///\brief A wrapper for composing a subgraph of a
|
marci@792
|
1212 |
/// bidirected graph made from a directed one.
|
marci@612
|
1213 |
///
|
alpar@911
|
1214 |
/// A wrapper for composing a subgraph of a
|
alpar@911
|
1215 |
/// bidirected graph made from a directed one.
|
alpar@911
|
1216 |
///
|
alpar@879
|
1217 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
1218 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
1219 |
///
|
marci@923
|
1220 |
/// Let \f$G=(V, A)\f$ be a directed graph and for each directed edge
|
marci@923
|
1221 |
/// \f$e\in A\f$, let \f$\bar e\f$ denote the edge obtained by
|
marci@923
|
1222 |
/// reversing its orientation. We are given moreover two bool valued
|
marci@923
|
1223 |
/// maps on the edge-set,
|
marci@923
|
1224 |
/// \f$forward\_filter\f$, and \f$backward\_filter\f$.
|
marci@923
|
1225 |
/// SubBidirGraphWrapper implements the graph structure with node-set
|
marci@923
|
1226 |
/// \f$V\f$ and edge-set
|
marci@923
|
1227 |
/// \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$.
|
marci@792
|
1228 |
/// The purpose of writing + instead of union is because parallel
|
marci@923
|
1229 |
/// edges can arise. (Similarly, antiparallel edges also can arise).
|
marci@792
|
1230 |
/// In other words, a subgraph of the bidirected graph obtained, which
|
marci@792
|
1231 |
/// is given by orienting the edges of the original graph in both directions.
|
marci@923
|
1232 |
/// As the oppositely directed edges are logically different,
|
marci@923
|
1233 |
/// the maps are able to attach different values for them.
|
marci@923
|
1234 |
///
|
marci@923
|
1235 |
/// An example for such a construction is \c RevGraphWrapper where the
|
marci@792
|
1236 |
/// forward_filter is everywhere false and the backward_filter is
|
marci@792
|
1237 |
/// everywhere true. We note that for sake of efficiency,
|
marci@792
|
1238 |
/// \c RevGraphWrapper is implemented in a different way.
|
marci@792
|
1239 |
/// But BidirGraphWrapper is obtained from
|
marci@792
|
1240 |
/// SubBidirGraphWrapper by considering everywhere true
|
marci@910
|
1241 |
/// valued maps both for forward_filter and backward_filter.
|
marci@792
|
1242 |
/// Finally, one of the most important applications of SubBidirGraphWrapper
|
marci@792
|
1243 |
/// is ResGraphWrapper, which stands for the residual graph in directed
|
marci@792
|
1244 |
/// flow and circulation problems.
|
marci@792
|
1245 |
/// As wrappers usually, the SubBidirGraphWrapper implements the
|
marci@792
|
1246 |
/// above mentioned graph structure without its physical storage,
|
marci@923
|
1247 |
/// that is the whole stuff is stored in constant memory.
|
marci@992
|
1248 |
template<typename _Graph,
|
marci@650
|
1249 |
typename ForwardFilterMap, typename BackwardFilterMap>
|
marci@992
|
1250 |
class SubBidirGraphWrapper :
|
marci@992
|
1251 |
public IterableGraphExtender<
|
marci@992
|
1252 |
SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
|
marci@650
|
1253 |
public:
|
marci@992
|
1254 |
typedef _Graph Graph;
|
marci@992
|
1255 |
typedef IterableGraphExtender<
|
marci@992
|
1256 |
SubBidirGraphWrapperBase<
|
marci@992
|
1257 |
_Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
|
marci@569
|
1258 |
protected:
|
marci@992
|
1259 |
SubBidirGraphWrapper() { }
|
marci@992
|
1260 |
public:
|
marci@992
|
1261 |
SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
|
marci@992
|
1262 |
BackwardFilterMap& _backward_filter) {
|
marci@992
|
1263 |
setGraph(_graph);
|
marci@992
|
1264 |
setForwardFilterMap(_forward_filter);
|
marci@992
|
1265 |
setBackwardFilterMap(_backward_filter);
|
marci@992
|
1266 |
}
|
marci@992
|
1267 |
};
|
marci@650
|
1268 |
|
marci@992
|
1269 |
// template<typename Graph,
|
marci@992
|
1270 |
// typename ForwardFilterMap, typename BackwardFilterMap>
|
marci@992
|
1271 |
// class SubBidirGraphWrapper : public GraphWrapper<Graph> {
|
marci@992
|
1272 |
// public:
|
marci@992
|
1273 |
// typedef GraphWrapper<Graph> Parent;
|
marci@992
|
1274 |
// protected:
|
marci@992
|
1275 |
// ForwardFilterMap* forward_filter;
|
marci@992
|
1276 |
// BackwardFilterMap* backward_filter;
|
marci@569
|
1277 |
|
marci@992
|
1278 |
// SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
|
marci@992
|
1279 |
// void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
|
marci@992
|
1280 |
// forward_filter=&_forward_filter;
|
marci@992
|
1281 |
// }
|
marci@992
|
1282 |
// void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
|
marci@992
|
1283 |
// backward_filter=&_backward_filter;
|
marci@992
|
1284 |
// }
|
marci@569
|
1285 |
|
marci@992
|
1286 |
// public:
|
marci@569
|
1287 |
|
marci@992
|
1288 |
// SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
|
marci@992
|
1289 |
// BackwardFilterMap& _backward_filter) :
|
marci@992
|
1290 |
// GraphWrapper<Graph>(_graph),
|
marci@992
|
1291 |
// forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
|
marci@992
|
1292 |
// SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1293 |
// ForwardFilterMap, BackwardFilterMap>& gw) :
|
marci@992
|
1294 |
// Parent(gw),
|
marci@992
|
1295 |
// forward_filter(gw.forward_filter),
|
marci@992
|
1296 |
// backward_filter(gw.backward_filter) { }
|
marci@569
|
1297 |
|
marci@992
|
1298 |
// class Edge;
|
marci@992
|
1299 |
// class OutEdgeIt;
|
marci@992
|
1300 |
// friend class Edge;
|
marci@992
|
1301 |
// friend class OutEdgeIt;
|
marci@621
|
1302 |
|
marci@992
|
1303 |
// template<typename T> class EdgeMap;
|
marci@621
|
1304 |
|
marci@992
|
1305 |
// typedef typename GraphWrapper<Graph>::Node Node;
|
marci@569
|
1306 |
|
marci@992
|
1307 |
// typedef typename Graph::Edge GraphEdge;
|
marci@992
|
1308 |
// /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
|
marci@992
|
1309 |
// /// Graph::Edge. It contains an extra bool flag which is true
|
marci@992
|
1310 |
// /// if and only if the
|
marci@992
|
1311 |
// /// edge is the backward version of the original edge.
|
marci@992
|
1312 |
// class Edge : public Graph::Edge {
|
marci@992
|
1313 |
// friend class SubBidirGraphWrapper<Graph,
|
marci@992
|
1314 |
// ForwardFilterMap, BackwardFilterMap>;
|
marci@992
|
1315 |
// template<typename T> friend class EdgeMap;
|
marci@992
|
1316 |
// protected:
|
marci@992
|
1317 |
// bool backward; //true, iff backward
|
marci@992
|
1318 |
// public:
|
marci@992
|
1319 |
// Edge() { }
|
marci@992
|
1320 |
// /// \todo =false is needed, or causes problems?
|
marci@992
|
1321 |
// /// If \c _backward is false, then we get an edge corresponding to the
|
marci@992
|
1322 |
// /// original one, otherwise its oppositely directed pair is obtained.
|
marci@992
|
1323 |
// Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
|
marci@992
|
1324 |
// Graph::Edge(e), backward(_backward) { }
|
marci@992
|
1325 |
// Edge(Invalid i) : Graph::Edge(i), backward(true) { }
|
marci@992
|
1326 |
// bool operator==(const Edge& v) const {
|
marci@992
|
1327 |
// return (this->backward==v.backward &&
|
marci@992
|
1328 |
// static_cast<typename Graph::Edge>(*this)==
|
marci@992
|
1329 |
// static_cast<typename Graph::Edge>(v));
|
marci@992
|
1330 |
// }
|
marci@992
|
1331 |
// bool operator!=(const Edge& v) const {
|
marci@992
|
1332 |
// return (this->backward!=v.backward ||
|
marci@992
|
1333 |
// static_cast<typename Graph::Edge>(*this)!=
|
marci@992
|
1334 |
// static_cast<typename Graph::Edge>(v));
|
marci@992
|
1335 |
// }
|
marci@992
|
1336 |
// };
|
marci@569
|
1337 |
|
marci@992
|
1338 |
// class OutEdgeIt : public Edge {
|
marci@992
|
1339 |
// friend class SubBidirGraphWrapper<Graph,
|
marci@992
|
1340 |
// ForwardFilterMap, BackwardFilterMap>;
|
marci@992
|
1341 |
// protected:
|
marci@992
|
1342 |
// const SubBidirGraphWrapper<Graph,
|
marci@992
|
1343 |
// ForwardFilterMap, BackwardFilterMap>* gw;
|
marci@992
|
1344 |
// public:
|
marci@992
|
1345 |
// OutEdgeIt() { }
|
marci@992
|
1346 |
// OutEdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
1347 |
// OutEdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1348 |
// ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
|
marci@992
|
1349 |
// Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
|
marci@992
|
1350 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1351 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1352 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1353 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1354 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1355 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1356 |
// Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
|
marci@992
|
1357 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1358 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1359 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1360 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1361 |
// }
|
marci@992
|
1362 |
// }
|
marci@992
|
1363 |
// OutEdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1364 |
// ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
|
marci@992
|
1365 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
1366 |
// OutEdgeIt& operator++() {
|
marci@992
|
1367 |
// if (!this->backward) {
|
marci@992
|
1368 |
// Node n=gw->source(*this);
|
marci@992
|
1369 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1370 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1371 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1372 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1373 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1374 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1375 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1376 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1377 |
// Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
|
marci@992
|
1378 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1379 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1380 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1381 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1382 |
// }
|
marci@992
|
1383 |
// } else {
|
marci@992
|
1384 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1385 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1386 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1387 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1388 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1389 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1390 |
// }
|
marci@992
|
1391 |
// return *this;
|
marci@992
|
1392 |
// }
|
marci@992
|
1393 |
// };
|
marci@569
|
1394 |
|
marci@992
|
1395 |
// class InEdgeIt : public Edge {
|
marci@992
|
1396 |
// friend class SubBidirGraphWrapper<Graph,
|
marci@992
|
1397 |
// ForwardFilterMap, BackwardFilterMap>;
|
marci@992
|
1398 |
// protected:
|
marci@992
|
1399 |
// const SubBidirGraphWrapper<Graph,
|
marci@992
|
1400 |
// ForwardFilterMap, BackwardFilterMap>* gw;
|
marci@992
|
1401 |
// public:
|
marci@992
|
1402 |
// InEdgeIt() { }
|
marci@992
|
1403 |
// InEdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
1404 |
// InEdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1405 |
// ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
|
marci@992
|
1406 |
// Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
|
marci@992
|
1407 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1408 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1409 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1410 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1411 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1412 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1413 |
// Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
|
marci@992
|
1414 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1415 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1416 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1417 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1418 |
// }
|
marci@992
|
1419 |
// }
|
marci@992
|
1420 |
// InEdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1421 |
// ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
|
marci@992
|
1422 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
1423 |
// InEdgeIt& operator++() {
|
marci@992
|
1424 |
// if (!this->backward) {
|
marci@992
|
1425 |
// Node n=gw->source(*this);
|
marci@992
|
1426 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1427 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1428 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1429 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1430 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1431 |
// ++(typename Graph::InEdgeIt(*(gw->graph), *this));
|
marci@992
|
1432 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1433 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1434 |
// Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
|
marci@992
|
1435 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1436 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1437 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1438 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1439 |
// }
|
marci@992
|
1440 |
// } else {
|
marci@992
|
1441 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1442 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1443 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1444 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1445 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1446 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@992
|
1447 |
// }
|
marci@992
|
1448 |
// return *this;
|
marci@992
|
1449 |
// }
|
marci@992
|
1450 |
// };
|
marci@569
|
1451 |
|
marci@992
|
1452 |
// class EdgeIt : public Edge {
|
marci@992
|
1453 |
// friend class SubBidirGraphWrapper<Graph,
|
marci@992
|
1454 |
// ForwardFilterMap, BackwardFilterMap>;
|
marci@992
|
1455 |
// protected:
|
marci@992
|
1456 |
// const SubBidirGraphWrapper<Graph,
|
marci@992
|
1457 |
// ForwardFilterMap, BackwardFilterMap>* gw;
|
marci@992
|
1458 |
// public:
|
marci@992
|
1459 |
// EdgeIt() { }
|
marci@992
|
1460 |
// EdgeIt(Invalid i) : Edge(i) { }
|
marci@992
|
1461 |
// EdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1462 |
// ForwardFilterMap, BackwardFilterMap>& _gw) :
|
marci@992
|
1463 |
// Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
|
marci@992
|
1464 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1465 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1466 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1467 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1468 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1469 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1470 |
// Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
|
marci@992
|
1471 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1472 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1473 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1474 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1475 |
// }
|
marci@992
|
1476 |
// }
|
marci@992
|
1477 |
// EdgeIt(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1478 |
// ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
|
marci@992
|
1479 |
// Edge(e), gw(&_gw) { }
|
marci@992
|
1480 |
// EdgeIt& operator++() {
|
marci@992
|
1481 |
// if (!this->backward) {
|
marci@992
|
1482 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1483 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1484 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1485 |
// !(*(gw->forward_filter))[*this])
|
marci@992
|
1486 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1487 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1488 |
// if (*static_cast<GraphEdge*>(this)==INVALID) {
|
marci@992
|
1489 |
// *static_cast<Edge*>(this)=
|
marci@992
|
1490 |
// Edge(typename Graph::EdgeIt(*(gw->graph)), true);
|
marci@992
|
1491 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1492 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1493 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1494 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1495 |
// }
|
marci@992
|
1496 |
// } else {
|
marci@992
|
1497 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1498 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1499 |
// while (*static_cast<GraphEdge*>(this)!=INVALID &&
|
marci@992
|
1500 |
// !(*(gw->backward_filter))[*this])
|
marci@992
|
1501 |
// *(static_cast<GraphEdge*>(this))=
|
marci@992
|
1502 |
// ++(typename Graph::EdgeIt(*(gw->graph), *this));
|
marci@992
|
1503 |
// }
|
marci@992
|
1504 |
// return *this;
|
marci@992
|
1505 |
// }
|
marci@992
|
1506 |
// };
|
marci@992
|
1507 |
|
marci@992
|
1508 |
// // using GraphWrapper<Graph>::first;
|
marci@992
|
1509 |
// // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@992
|
1510 |
// // i=OutEdgeIt(*this, p); return i;
|
marci@992
|
1511 |
// // }
|
marci@992
|
1512 |
// // InEdgeIt& first(InEdgeIt& i, const Node& p) const {
|
marci@992
|
1513 |
// // i=InEdgeIt(*this, p); return i;
|
marci@992
|
1514 |
// // }
|
marci@992
|
1515 |
// // EdgeIt& first(EdgeIt& i) const {
|
marci@992
|
1516 |
// // i=EdgeIt(*this); return i;
|
marci@992
|
1517 |
// // }
|
marci@556
|
1518 |
|
marci@569
|
1519 |
|
marci@992
|
1520 |
// Node source(Edge e) const {
|
marci@992
|
1521 |
// return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
|
marci@992
|
1522 |
// Node target(Edge e) const {
|
marci@992
|
1523 |
// return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
|
marci@569
|
1524 |
|
marci@992
|
1525 |
// /// Gives back the opposite edge.
|
marci@992
|
1526 |
// Edge opposite(const Edge& e) const {
|
marci@992
|
1527 |
// Edge f=e;
|
marci@992
|
1528 |
// f.backward=!f.backward;
|
marci@992
|
1529 |
// return f;
|
marci@992
|
1530 |
// }
|
marci@572
|
1531 |
|
marci@992
|
1532 |
// /// \warning This is a linear time operation and works only if
|
marci@992
|
1533 |
// /// \c Graph::EdgeIt is defined.
|
marci@992
|
1534 |
// int edgeNum() const {
|
marci@992
|
1535 |
// int i=0;
|
marci@992
|
1536 |
// for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
|
marci@992
|
1537 |
// return i;
|
marci@992
|
1538 |
// }
|
marci@569
|
1539 |
|
marci@992
|
1540 |
// bool forward(const Edge& e) const { return !e.backward; }
|
marci@992
|
1541 |
// bool backward(const Edge& e) const { return e.backward; }
|
marci@569
|
1542 |
|
marci@569
|
1543 |
|
marci@992
|
1544 |
// template <typename T>
|
marci@992
|
1545 |
// /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
|
marci@992
|
1546 |
// /// Graph::EdgeMap one for the forward edges and
|
marci@992
|
1547 |
// /// one for the backward edges.
|
marci@992
|
1548 |
// class EdgeMap {
|
marci@992
|
1549 |
// template <typename TT> friend class EdgeMap;
|
marci@992
|
1550 |
// typename Graph::template EdgeMap<T> forward_map, backward_map;
|
marci@992
|
1551 |
// public:
|
marci@992
|
1552 |
// typedef T Value;
|
marci@992
|
1553 |
// typedef Edge Key;
|
deba@891
|
1554 |
|
marci@992
|
1555 |
// EdgeMap(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1556 |
// ForwardFilterMap, BackwardFilterMap>& g) :
|
marci@992
|
1557 |
// forward_map(*(g.graph)), backward_map(*(g.graph)) { }
|
deba@891
|
1558 |
|
marci@992
|
1559 |
// EdgeMap(const SubBidirGraphWrapper<Graph,
|
marci@992
|
1560 |
// ForwardFilterMap, BackwardFilterMap>& g, T a) :
|
marci@992
|
1561 |
// forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
|
deba@891
|
1562 |
|
marci@992
|
1563 |
// template <typename TT>
|
marci@992
|
1564 |
// EdgeMap(const EdgeMap<TT>& copy)
|
marci@992
|
1565 |
// : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
|
deba@891
|
1566 |
|
marci@992
|
1567 |
// template <typename TT>
|
marci@992
|
1568 |
// EdgeMap& operator=(const EdgeMap<TT>& copy) {
|
marci@992
|
1569 |
// forward_map = copy.forward_map;
|
marci@992
|
1570 |
// backward_map = copy.backward_map;
|
marci@992
|
1571 |
// return *this;
|
marci@992
|
1572 |
// }
|
deba@891
|
1573 |
|
marci@992
|
1574 |
// void set(Edge e, T a) {
|
marci@992
|
1575 |
// if (!e.backward)
|
marci@992
|
1576 |
// forward_map.set(e, a);
|
marci@992
|
1577 |
// else
|
marci@992
|
1578 |
// backward_map.set(e, a);
|
marci@992
|
1579 |
// }
|
deba@891
|
1580 |
|
marci@992
|
1581 |
// typename Graph::template EdgeMap<T>::ConstReference
|
marci@992
|
1582 |
// operator[](Edge e) const {
|
marci@992
|
1583 |
// if (!e.backward)
|
marci@992
|
1584 |
// return forward_map[e];
|
marci@992
|
1585 |
// else
|
marci@992
|
1586 |
// return backward_map[e];
|
marci@992
|
1587 |
// }
|
deba@891
|
1588 |
|
marci@992
|
1589 |
// typename Graph::template EdgeMap<T>::Reference
|
marci@992
|
1590 |
// operator[](Edge e) {
|
marci@992
|
1591 |
// if (!e.backward)
|
marci@992
|
1592 |
// return forward_map[e];
|
marci@992
|
1593 |
// else
|
marci@992
|
1594 |
// return backward_map[e];
|
marci@992
|
1595 |
// }
|
deba@891
|
1596 |
|
marci@992
|
1597 |
// void update() {
|
marci@992
|
1598 |
// forward_map.update();
|
marci@992
|
1599 |
// backward_map.update();
|
marci@992
|
1600 |
// }
|
marci@992
|
1601 |
// };
|
deba@877
|
1602 |
|
deba@877
|
1603 |
|
marci@992
|
1604 |
// // KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
|
deba@877
|
1605 |
|
marci@992
|
1606 |
// };
|
marci@569
|
1607 |
|
marci@650
|
1608 |
|
marci@650
|
1609 |
///\brief A wrapper for composing bidirected graph from a directed one.
|
marci@650
|
1610 |
///
|
alpar@879
|
1611 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
1612 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
1613 |
///
|
marci@650
|
1614 |
/// A wrapper for composing bidirected graph from a directed one.
|
marci@650
|
1615 |
/// A bidirected graph is composed over the directed one without physical
|
marci@650
|
1616 |
/// storage. As the oppositely directed edges are logically different ones
|
marci@650
|
1617 |
/// the maps are able to attach different values for them.
|
marci@650
|
1618 |
template<typename Graph>
|
marci@650
|
1619 |
class BidirGraphWrapper :
|
marci@650
|
1620 |
public SubBidirGraphWrapper<
|
marci@650
|
1621 |
Graph,
|
marci@650
|
1622 |
ConstMap<typename Graph::Edge, bool>,
|
marci@650
|
1623 |
ConstMap<typename Graph::Edge, bool> > {
|
marci@650
|
1624 |
public:
|
marci@650
|
1625 |
typedef SubBidirGraphWrapper<
|
marci@650
|
1626 |
Graph,
|
marci@650
|
1627 |
ConstMap<typename Graph::Edge, bool>,
|
marci@650
|
1628 |
ConstMap<typename Graph::Edge, bool> > Parent;
|
marci@650
|
1629 |
protected:
|
marci@650
|
1630 |
ConstMap<typename Graph::Edge, bool> cm;
|
marci@650
|
1631 |
|
marci@655
|
1632 |
BidirGraphWrapper() : Parent(), cm(true) {
|
marci@655
|
1633 |
Parent::setForwardFilterMap(cm);
|
marci@655
|
1634 |
Parent::setBackwardFilterMap(cm);
|
marci@655
|
1635 |
}
|
marci@650
|
1636 |
public:
|
marci@650
|
1637 |
BidirGraphWrapper(Graph& _graph) : Parent() {
|
marci@650
|
1638 |
Parent::setGraph(_graph);
|
marci@650
|
1639 |
Parent::setForwardFilterMap(cm);
|
marci@650
|
1640 |
Parent::setBackwardFilterMap(cm);
|
marci@650
|
1641 |
}
|
marci@738
|
1642 |
|
marci@738
|
1643 |
int edgeNum() const {
|
marci@738
|
1644 |
return 2*this->graph->edgeNum();
|
marci@738
|
1645 |
}
|
deba@891
|
1646 |
// KEEP_MAPS(Parent, BidirGraphWrapper);
|
marci@650
|
1647 |
};
|
marci@650
|
1648 |
|
marci@650
|
1649 |
|
marci@612
|
1650 |
/// \brief A bidirected graph template.
|
marci@612
|
1651 |
///
|
alpar@879
|
1652 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
1653 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
1654 |
///
|
marci@612
|
1655 |
/// A bidirected graph template.
|
marci@612
|
1656 |
/// Such a bidirected graph stores each pair of oppositely directed edges
|
marci@612
|
1657 |
/// ones in the memory, i.e. a directed graph of type
|
marci@612
|
1658 |
/// \c Graph is used for that.
|
marci@612
|
1659 |
/// As the oppositely directed edges are logically different ones
|
marci@612
|
1660 |
/// the maps are able to attach different values for them.
|
marci@612
|
1661 |
/// \ingroup graphs
|
marci@612
|
1662 |
template<typename Graph>
|
marci@612
|
1663 |
class BidirGraph : public BidirGraphWrapper<Graph> {
|
marci@650
|
1664 |
public:
|
marci@612
|
1665 |
typedef UndirGraphWrapper<Graph> Parent;
|
marci@612
|
1666 |
protected:
|
marci@612
|
1667 |
Graph gr;
|
marci@612
|
1668 |
public:
|
marci@612
|
1669 |
BidirGraph() : BidirGraphWrapper<Graph>() {
|
marci@612
|
1670 |
Parent::setGraph(gr);
|
marci@612
|
1671 |
}
|
deba@891
|
1672 |
// KEEP_MAPS(Parent, BidirGraph);
|
marci@612
|
1673 |
};
|
marci@569
|
1674 |
|
marci@556
|
1675 |
|
marci@650
|
1676 |
|
marci@650
|
1677 |
template<typename Graph, typename Number,
|
marci@650
|
1678 |
typename CapacityMap, typename FlowMap>
|
marci@658
|
1679 |
class ResForwardFilter {
|
marci@658
|
1680 |
// const Graph* graph;
|
marci@650
|
1681 |
const CapacityMap* capacity;
|
marci@650
|
1682 |
const FlowMap* flow;
|
marci@650
|
1683 |
public:
|
marci@658
|
1684 |
ResForwardFilter(/*const Graph& _graph, */
|
marci@658
|
1685 |
const CapacityMap& _capacity, const FlowMap& _flow) :
|
marci@658
|
1686 |
/*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
|
marci@658
|
1687 |
ResForwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
|
marci@656
|
1688 |
void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
|
marci@656
|
1689 |
void setFlow(const FlowMap& _flow) { flow=&_flow; }
|
marci@650
|
1690 |
bool operator[](const typename Graph::Edge& e) const {
|
marci@738
|
1691 |
return (Number((*flow)[e]) < Number((*capacity)[e]));
|
marci@650
|
1692 |
}
|
marci@650
|
1693 |
};
|
marci@650
|
1694 |
|
marci@650
|
1695 |
template<typename Graph, typename Number,
|
marci@650
|
1696 |
typename CapacityMap, typename FlowMap>
|
marci@658
|
1697 |
class ResBackwardFilter {
|
marci@650
|
1698 |
const CapacityMap* capacity;
|
marci@650
|
1699 |
const FlowMap* flow;
|
marci@650
|
1700 |
public:
|
marci@658
|
1701 |
ResBackwardFilter(/*const Graph& _graph,*/
|
marci@658
|
1702 |
const CapacityMap& _capacity, const FlowMap& _flow) :
|
marci@658
|
1703 |
/*graph(&_graph),*/ capacity(&_capacity), flow(&_flow) { }
|
marci@658
|
1704 |
ResBackwardFilter() : /*graph(0),*/ capacity(0), flow(0) { }
|
marci@656
|
1705 |
void setCapacity(const CapacityMap& _capacity) { capacity=&_capacity; }
|
marci@656
|
1706 |
void setFlow(const FlowMap& _flow) { flow=&_flow; }
|
marci@650
|
1707 |
bool operator[](const typename Graph::Edge& e) const {
|
marci@738
|
1708 |
return (Number(0) < Number((*flow)[e]));
|
marci@650
|
1709 |
}
|
marci@650
|
1710 |
};
|
marci@650
|
1711 |
|
marci@653
|
1712 |
|
marci@653
|
1713 |
/// A wrapper for composing the residual graph for directed flow and circulation problems.
|
marci@650
|
1714 |
|
alpar@879
|
1715 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
1716 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
1717 |
///
|
marci@653
|
1718 |
/// A wrapper for composing the residual graph for directed flow and circulation problems.
|
marci@650
|
1719 |
template<typename Graph, typename Number,
|
marci@650
|
1720 |
typename CapacityMap, typename FlowMap>
|
marci@653
|
1721 |
class ResGraphWrapper :
|
marci@650
|
1722 |
public SubBidirGraphWrapper<
|
marci@650
|
1723 |
Graph,
|
marci@658
|
1724 |
ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
|
marci@658
|
1725 |
ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > {
|
marci@650
|
1726 |
public:
|
marci@650
|
1727 |
typedef SubBidirGraphWrapper<
|
marci@650
|
1728 |
Graph,
|
marci@658
|
1729 |
ResForwardFilter<Graph, Number, CapacityMap, FlowMap>,
|
marci@658
|
1730 |
ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> > Parent;
|
marci@650
|
1731 |
protected:
|
marci@650
|
1732 |
const CapacityMap* capacity;
|
marci@650
|
1733 |
FlowMap* flow;
|
marci@658
|
1734 |
ResForwardFilter<Graph, Number, CapacityMap, FlowMap> forward_filter;
|
marci@658
|
1735 |
ResBackwardFilter<Graph, Number, CapacityMap, FlowMap> backward_filter;
|
marci@658
|
1736 |
ResGraphWrapper() : Parent(),
|
marci@658
|
1737 |
capacity(0), flow(0) { }
|
marci@658
|
1738 |
void setCapacityMap(const CapacityMap& _capacity) {
|
marci@658
|
1739 |
capacity=&_capacity;
|
marci@658
|
1740 |
forward_filter.setCapacity(_capacity);
|
marci@658
|
1741 |
backward_filter.setCapacity(_capacity);
|
marci@658
|
1742 |
}
|
marci@658
|
1743 |
void setFlowMap(FlowMap& _flow) {
|
marci@658
|
1744 |
flow=&_flow;
|
marci@658
|
1745 |
forward_filter.setFlow(_flow);
|
marci@658
|
1746 |
backward_filter.setFlow(_flow);
|
marci@658
|
1747 |
}
|
marci@650
|
1748 |
public:
|
marci@653
|
1749 |
ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity,
|
marci@650
|
1750 |
FlowMap& _flow) :
|
marci@650
|
1751 |
Parent(), capacity(&_capacity), flow(&_flow),
|
marci@658
|
1752 |
forward_filter(/*_graph,*/ _capacity, _flow),
|
marci@658
|
1753 |
backward_filter(/*_graph,*/ _capacity, _flow) {
|
marci@650
|
1754 |
Parent::setGraph(_graph);
|
marci@650
|
1755 |
Parent::setForwardFilterMap(forward_filter);
|
marci@650
|
1756 |
Parent::setBackwardFilterMap(backward_filter);
|
marci@650
|
1757 |
}
|
marci@650
|
1758 |
|
marci@660
|
1759 |
typedef typename Parent::Edge Edge;
|
marci@660
|
1760 |
|
marci@660
|
1761 |
void augment(const Edge& e, Number a) const {
|
marci@650
|
1762 |
if (Parent::forward(e))
|
marci@650
|
1763 |
flow->set(e, (*flow)[e]+a);
|
marci@650
|
1764 |
else
|
marci@650
|
1765 |
flow->set(e, (*flow)[e]-a);
|
marci@650
|
1766 |
}
|
marci@650
|
1767 |
|
marci@660
|
1768 |
/// \brief Residual capacity map.
|
marci@660
|
1769 |
///
|
marci@910
|
1770 |
/// In generic residual graphs the residual capacity can be obtained
|
marci@910
|
1771 |
/// as a map.
|
marci@660
|
1772 |
class ResCap {
|
marci@660
|
1773 |
protected:
|
marci@660
|
1774 |
const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>* res_graph;
|
marci@660
|
1775 |
public:
|
alpar@987
|
1776 |
typedef Number Value;
|
alpar@987
|
1777 |
typedef Edge Key;
|
marci@888
|
1778 |
ResCap(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>&
|
marci@888
|
1779 |
_res_graph) : res_graph(&_res_graph) { }
|
marci@660
|
1780 |
Number operator[](const Edge& e) const {
|
marci@660
|
1781 |
if (res_graph->forward(e))
|
marci@660
|
1782 |
return (*(res_graph->capacity))[e]-(*(res_graph->flow))[e];
|
marci@660
|
1783 |
else
|
marci@660
|
1784 |
return (*(res_graph->flow))[e];
|
marci@660
|
1785 |
}
|
marci@660
|
1786 |
};
|
marci@660
|
1787 |
|
deba@891
|
1788 |
// KEEP_MAPS(Parent, ResGraphWrapper);
|
marci@650
|
1789 |
};
|
marci@650
|
1790 |
|
marci@650
|
1791 |
|
marci@998
|
1792 |
|
marci@998
|
1793 |
template <typename _Graph, typename FirstOutEdgesMap>
|
marci@998
|
1794 |
class ErasingFirstGraphWrapperBase : public GraphWrapperBase<_Graph> {
|
marci@998
|
1795 |
public:
|
marci@998
|
1796 |
typedef _Graph Graph;
|
marci@998
|
1797 |
typedef GraphWrapperBase<_Graph> Parent;
|
marci@998
|
1798 |
protected:
|
marci@998
|
1799 |
FirstOutEdgesMap* first_out_edges;
|
marci@998
|
1800 |
ErasingFirstGraphWrapperBase() : Parent(),
|
marci@998
|
1801 |
first_out_edges(0) { }
|
marci@998
|
1802 |
|
marci@998
|
1803 |
void setFirstOutEdgesMap(FirstOutEdgesMap& _first_out_edges) {
|
marci@998
|
1804 |
first_out_edges=&_first_out_edges;
|
marci@998
|
1805 |
}
|
marci@998
|
1806 |
|
marci@998
|
1807 |
public:
|
marci@998
|
1808 |
|
marci@998
|
1809 |
typedef typename Parent::Node Node;
|
marci@998
|
1810 |
typedef typename Parent::Edge Edge;
|
marci@998
|
1811 |
|
marci@998
|
1812 |
// using Parent::first;
|
marci@998
|
1813 |
// void first(Node& i) const {
|
marci@998
|
1814 |
// Parent::first(i);
|
marci@998
|
1815 |
// while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
marci@998
|
1816 |
// }
|
marci@998
|
1817 |
// void first(Edge& i) const {
|
marci@998
|
1818 |
// Parent::first(i);
|
marci@998
|
1819 |
// while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
|
marci@998
|
1820 |
// }
|
marci@998
|
1821 |
// void firstIn(Edge& i, const Node& n) const {
|
marci@998
|
1822 |
// Parent::firstIn(i, n);
|
marci@998
|
1823 |
// while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
|
marci@998
|
1824 |
// }
|
marci@998
|
1825 |
void firstOut(Edge& i, const Node& n) const {
|
marci@998
|
1826 |
i=(*first_out_edges)[n];
|
marci@998
|
1827 |
}
|
marci@998
|
1828 |
|
marci@998
|
1829 |
void erase(const Edge& e) const {
|
marci@998
|
1830 |
Node n=source(e);
|
marci@998
|
1831 |
Edge f=e;
|
marci@998
|
1832 |
Parent::nextOut(f);
|
marci@998
|
1833 |
first_out_edges->set(n, f);
|
marci@998
|
1834 |
}
|
marci@998
|
1835 |
// void next(Node& i) const {
|
marci@998
|
1836 |
// Parent::next(i);
|
marci@998
|
1837 |
// while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
marci@998
|
1838 |
// }
|
marci@998
|
1839 |
// void next(Edge& i) const {
|
marci@998
|
1840 |
// Parent::next(i);
|
marci@998
|
1841 |
// while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
|
marci@998
|
1842 |
// }
|
marci@998
|
1843 |
// void nextIn(Edge& i) const {
|
marci@998
|
1844 |
// Parent::nextIn(i);
|
marci@998
|
1845 |
// while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
|
marci@998
|
1846 |
// }
|
marci@998
|
1847 |
// void nextOut(Edge& i) const {
|
marci@998
|
1848 |
// Parent::nextOut(i);
|
marci@998
|
1849 |
// while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
|
marci@998
|
1850 |
// }
|
marci@998
|
1851 |
};
|
marci@998
|
1852 |
|
marci@998
|
1853 |
|
marci@612
|
1854 |
/// For blocking flows.
|
marci@556
|
1855 |
|
alpar@879
|
1856 |
///\warning Graph wrappers are in even more experimental state than the other
|
alpar@879
|
1857 |
///parts of the lib. Use them at you own risk.
|
alpar@879
|
1858 |
///
|
marci@792
|
1859 |
/// This graph wrapper is used for on-the-fly
|
marci@792
|
1860 |
/// Dinits blocking flow computations.
|
marci@612
|
1861 |
/// For each node, an out-edge is stored which is used when the
|
marci@612
|
1862 |
/// \code
|
marci@612
|
1863 |
/// OutEdgeIt& first(OutEdgeIt&, const Node&)
|
marci@612
|
1864 |
/// \endcode
|
marci@612
|
1865 |
/// is called.
|
marci@556
|
1866 |
///
|
marci@792
|
1867 |
/// \author Marton Makai
|
marci@998
|
1868 |
template <typename _Graph, typename FirstOutEdgesMap>
|
marci@998
|
1869 |
class ErasingFirstGraphWrapper :
|
marci@998
|
1870 |
public IterableGraphExtender<
|
marci@998
|
1871 |
ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > {
|
marci@650
|
1872 |
public:
|
marci@998
|
1873 |
typedef _Graph Graph;
|
marci@998
|
1874 |
typedef IterableGraphExtender<
|
marci@998
|
1875 |
ErasingFirstGraphWrapperBase<_Graph, FirstOutEdgesMap> > Parent;
|
marci@556
|
1876 |
ErasingFirstGraphWrapper(Graph& _graph,
|
marci@998
|
1877 |
FirstOutEdgesMap& _first_out_edges) {
|
marci@998
|
1878 |
setGraph(_graph);
|
marci@998
|
1879 |
setFirstOutEdgesMap(_first_out_edges);
|
marci@998
|
1880 |
}
|
marci@970
|
1881 |
// using GraphWrapper<Graph>::first;
|
marci@970
|
1882 |
// OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@970
|
1883 |
// i=OutEdgeIt(*this, p); return i;
|
marci@970
|
1884 |
// }
|
marci@998
|
1885 |
};
|
marci@998
|
1886 |
// template<typename Graph, typename FirstOutEdgesMap>
|
marci@998
|
1887 |
// class ErasingFirstGraphWrapper : public GraphWrapper<Graph> {
|
marci@998
|
1888 |
// public:
|
marci@998
|
1889 |
// typedef GraphWrapper<Graph> Parent;
|
marci@998
|
1890 |
// protected:
|
marci@998
|
1891 |
// FirstOutEdgesMap* first_out_edges;
|
marci@998
|
1892 |
// public:
|
marci@998
|
1893 |
// ErasingFirstGraphWrapper(Graph& _graph,
|
marci@998
|
1894 |
// FirstOutEdgesMap& _first_out_edges) :
|
marci@998
|
1895 |
// GraphWrapper<Graph>(_graph), first_out_edges(&_first_out_edges) { }
|
deba@877
|
1896 |
|
marci@998
|
1897 |
// typedef typename GraphWrapper<Graph>::Node Node;
|
marci@998
|
1898 |
// typedef typename GraphWrapper<Graph>::Edge Edge;
|
marci@998
|
1899 |
// class OutEdgeIt : public Edge {
|
marci@998
|
1900 |
// friend class GraphWrapper<Graph>;
|
marci@998
|
1901 |
// friend class ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>;
|
marci@998
|
1902 |
// const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>* gw;
|
marci@998
|
1903 |
// public:
|
marci@998
|
1904 |
// OutEdgeIt() { }
|
marci@998
|
1905 |
// OutEdgeIt(Invalid i) : Edge(i) { }
|
marci@998
|
1906 |
// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
|
marci@998
|
1907 |
// const Node& n) :
|
marci@998
|
1908 |
// Edge((*(_gw.first_out_edges))[n]), gw(&_gw) { }
|
marci@998
|
1909 |
// OutEdgeIt(const ErasingFirstGraphWrapper<Graph, FirstOutEdgesMap>& _gw,
|
marci@998
|
1910 |
// const Edge& e) :
|
marci@998
|
1911 |
// Edge(e), gw(&_gw) { }
|
marci@998
|
1912 |
// OutEdgeIt& operator++() {
|
marci@998
|
1913 |
// *(static_cast<Edge*>(this))=
|
marci@998
|
1914 |
// ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
|
marci@998
|
1915 |
// return *this;
|
marci@998
|
1916 |
// }
|
marci@998
|
1917 |
// };
|
marci@998
|
1918 |
|
marci@998
|
1919 |
// // using GraphWrapper<Graph>::first;
|
marci@998
|
1920 |
// // OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
|
marci@998
|
1921 |
// // i=OutEdgeIt(*this, p); return i;
|
marci@998
|
1922 |
// // }
|
marci@998
|
1923 |
// void erase(const Edge& e) const {
|
marci@998
|
1924 |
// Node n=source(e);
|
marci@998
|
1925 |
// typename Graph::OutEdgeIt f(*Parent::graph, n);
|
marci@998
|
1926 |
// ++f;
|
marci@998
|
1927 |
// first_out_edges->set(n, f);
|
marci@998
|
1928 |
// }
|
marci@998
|
1929 |
|
marci@998
|
1930 |
// // KEEP_MAPS(Parent, ErasingFirstGraphWrapper);
|
marci@998
|
1931 |
// };
|
marci@556
|
1932 |
|
marci@556
|
1933 |
///@}
|
marci@556
|
1934 |
|
alpar@921
|
1935 |
} //namespace lemon
|
marci@556
|
1936 |
|
alpar@921
|
1937 |
#endif //LEMON_GRAPH_WRAPPER_H
|
marci@556
|
1938 |
|