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