deba@1979
|
1 |
/* -*- C++ -*-
|
deba@1979
|
2 |
*
|
deba@1979
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
deba@1979
|
4 |
*
|
deba@1979
|
5 |
* Copyright (C) 2003-2006
|
deba@1979
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@1979
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@1979
|
8 |
*
|
deba@1979
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@1979
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@1979
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@1979
|
12 |
*
|
deba@1979
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@1979
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@1979
|
15 |
* purpose.
|
deba@1979
|
16 |
*
|
deba@1979
|
17 |
*/
|
deba@1979
|
18 |
|
deba@1979
|
19 |
#ifndef LEMON_UGRAPH_ADAPTOR_H
|
deba@1979
|
20 |
#define LEMON_UGRAPH_ADAPTOR_H
|
deba@1979
|
21 |
|
deba@1979
|
22 |
///\ingroup graph_adaptors
|
deba@1979
|
23 |
///\file
|
deba@1979
|
24 |
///\brief Several graph adaptors.
|
deba@1979
|
25 |
///
|
deba@1979
|
26 |
///This file contains several useful ugraph adaptor functions.
|
deba@1979
|
27 |
///
|
deba@1979
|
28 |
///\author Balazs Dezso
|
deba@1979
|
29 |
|
deba@1979
|
30 |
#include <lemon/invalid.h>
|
deba@1979
|
31 |
#include <lemon/maps.h>
|
deba@1979
|
32 |
|
deba@1979
|
33 |
#include <lemon/bits/graph_adaptor_extender.h>
|
deba@1979
|
34 |
|
deba@1979
|
35 |
#include <lemon/traits.h>
|
deba@1979
|
36 |
|
deba@1979
|
37 |
#include <iostream>
|
deba@1979
|
38 |
|
deba@1979
|
39 |
namespace lemon {
|
deba@1979
|
40 |
|
deba@1979
|
41 |
/// \ingroup graph_adaptors
|
deba@1979
|
42 |
///
|
deba@1979
|
43 |
/// \brief Base type for the Graph Adaptors
|
deba@1979
|
44 |
///
|
deba@1979
|
45 |
/// \warning Graph adaptors are in even more experimental state than the
|
deba@1979
|
46 |
/// other parts of the lib. Use them at you own risk.
|
deba@1979
|
47 |
///
|
deba@1979
|
48 |
/// This is the base type for most of LEMON graph adaptors.
|
deba@1979
|
49 |
/// This class implements a trivial graph adaptor i.e. it only wraps the
|
deba@1979
|
50 |
/// functions and types of the graph. The purpose of this class is to
|
deba@1979
|
51 |
/// make easier implementing graph adaptors. E.g. if an adaptor is
|
deba@1979
|
52 |
/// considered which differs from the wrapped graph only in some of its
|
deba@1979
|
53 |
/// functions or types, then it can be derived from GraphAdaptor, and only
|
deba@1979
|
54 |
/// the differences should be implemented.
|
deba@1979
|
55 |
///
|
deba@1979
|
56 |
/// \author Balazs Dezso
|
deba@1979
|
57 |
template<typename _UGraph>
|
deba@1979
|
58 |
class UGraphAdaptorBase {
|
deba@1979
|
59 |
public:
|
deba@1979
|
60 |
typedef _UGraph Graph;
|
deba@1979
|
61 |
typedef Graph ParentGraph;
|
deba@1979
|
62 |
|
deba@1979
|
63 |
protected:
|
deba@1979
|
64 |
Graph* graph;
|
deba@1979
|
65 |
|
deba@1979
|
66 |
UGraphAdaptorBase() : graph(0) {}
|
deba@1979
|
67 |
|
deba@1979
|
68 |
void setGraph(Graph& _graph) { graph=&_graph; }
|
deba@1979
|
69 |
|
deba@1979
|
70 |
Graph& getGraph() { return *graph; }
|
deba@1979
|
71 |
const Graph& getGraph() const { return *graph; }
|
deba@1979
|
72 |
|
deba@1979
|
73 |
public:
|
deba@1979
|
74 |
UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}
|
deba@1979
|
75 |
|
deba@1979
|
76 |
typedef typename Graph::Node Node;
|
deba@1979
|
77 |
typedef typename Graph::Edge Edge;
|
deba@1979
|
78 |
typedef typename Graph::UEdge UEdge;
|
deba@1979
|
79 |
|
deba@1979
|
80 |
void first(Node& i) const { graph->first(i); }
|
deba@1979
|
81 |
void first(Edge& i) const { graph->first(i); }
|
deba@1979
|
82 |
void first(UEdge& i) const { graph->first(i); }
|
deba@1979
|
83 |
void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }
|
deba@1979
|
84 |
void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }
|
deba@1979
|
85 |
void firstInc(UEdge &i, bool &d, const Node &n) const {
|
deba@1979
|
86 |
graph->firstInc(i, d, n);
|
deba@1979
|
87 |
}
|
deba@1979
|
88 |
|
deba@1979
|
89 |
void next(Node& i) const { graph->next(i); }
|
deba@1979
|
90 |
void next(Edge& i) const { graph->next(i); }
|
deba@1979
|
91 |
void next(UEdge& i) const { graph->next(i); }
|
deba@1979
|
92 |
void nextIn(Edge& i) const { graph->nextIn(i); }
|
deba@1979
|
93 |
void nextOut(Edge& i) const { graph->nextOut(i); }
|
deba@1979
|
94 |
void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }
|
deba@1979
|
95 |
|
deba@1979
|
96 |
|
deba@1979
|
97 |
Node source(const UEdge& e) const { return graph->source(e); }
|
deba@1979
|
98 |
Node target(const UEdge& e) const { return graph->target(e); }
|
deba@1979
|
99 |
|
deba@1979
|
100 |
Node source(const Edge& e) const { return graph->source(e); }
|
deba@1979
|
101 |
Node target(const Edge& e) const { return graph->target(e); }
|
deba@1979
|
102 |
|
deba@1979
|
103 |
typedef NodeNumTagIndicator<Graph> NodeNumTag;
|
deba@1979
|
104 |
int nodeNum() const { return graph->nodeNum(); }
|
deba@1979
|
105 |
|
deba@1979
|
106 |
typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
|
deba@1979
|
107 |
int edgeNum() const { return graph->edgeNum(); }
|
deba@1979
|
108 |
|
deba@1979
|
109 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
|
deba@1979
|
110 |
Edge findEdge(const Node& source, const Node& target,
|
deba@1979
|
111 |
const Edge& prev = INVALID) {
|
deba@1979
|
112 |
return graph->findEdge(source, target, prev);
|
deba@1979
|
113 |
}
|
deba@1979
|
114 |
|
deba@1979
|
115 |
UEdge findUEdge(const Node& source, const Node& target,
|
deba@1979
|
116 |
const UEdge& prev = INVALID) {
|
deba@1979
|
117 |
return graph->findUEdge(source, target, prev);
|
deba@1979
|
118 |
}
|
deba@1979
|
119 |
|
deba@1979
|
120 |
Node addNode() const { return graph->addNode(); }
|
deba@1979
|
121 |
UEdge addEdge(const Node& source, const Node& target) const {
|
deba@1979
|
122 |
return graph->addEdge(source, target);
|
deba@1979
|
123 |
}
|
deba@1979
|
124 |
|
deba@1979
|
125 |
void erase(const Node& i) const { graph->erase(i); }
|
deba@1979
|
126 |
void erase(const Edge& i) const { graph->erase(i); }
|
deba@1979
|
127 |
|
deba@1979
|
128 |
void clear() const { graph->clear(); }
|
deba@1979
|
129 |
|
deba@1979
|
130 |
int id(const Node& v) const { return graph->id(v); }
|
deba@1979
|
131 |
int id(const UEdge& e) const { return graph->id(e); }
|
deba@1979
|
132 |
|
deba@1979
|
133 |
bool direction(const Edge& e) const { return graph->direction(e); }
|
deba@1979
|
134 |
Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }
|
deba@1979
|
135 |
Edge direct(const UEdge& e, const Node& n) const {
|
deba@1979
|
136 |
return graph->direct(e, n);
|
deba@1979
|
137 |
}
|
deba@1979
|
138 |
|
deba@1979
|
139 |
Node oppositeNode(const Node& n, const Edge& e) const {
|
deba@1979
|
140 |
return graph->oppositeNode(n, e);
|
deba@1979
|
141 |
}
|
deba@1979
|
142 |
|
deba@1979
|
143 |
Edge oppositeEdge(const Edge& e) const {
|
deba@1979
|
144 |
return graph->oppositeEdge(e);
|
deba@1979
|
145 |
}
|
deba@1979
|
146 |
|
deba@1979
|
147 |
|
deba@1979
|
148 |
template <typename _Value>
|
deba@1979
|
149 |
class NodeMap : public Graph::template NodeMap<_Value> {
|
deba@1979
|
150 |
public:
|
deba@1979
|
151 |
typedef typename Graph::template NodeMap<_Value> Parent;
|
deba@1979
|
152 |
explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)
|
deba@1979
|
153 |
: Parent(*ga.graph) {}
|
deba@1979
|
154 |
NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
|
deba@1979
|
155 |
: Parent(*ga.graph, value) {}
|
deba@1979
|
156 |
|
deba@1979
|
157 |
NodeMap& operator=(const NodeMap& cmap) {
|
deba@1979
|
158 |
return operator=<NodeMap>(cmap);
|
deba@1979
|
159 |
}
|
deba@1979
|
160 |
|
deba@1979
|
161 |
template <typename CMap>
|
deba@1979
|
162 |
NodeMap& operator=(const CMap& cmap) {
|
deba@1979
|
163 |
checkConcept<concept::ReadMap<Node, _Value>, CMap>();
|
deba@1979
|
164 |
const typename Parent::Graph* graph = Parent::getGraph();
|
deba@1979
|
165 |
Node it;
|
deba@1979
|
166 |
for (graph->first(it); it != INVALID; graph->next(it)) {
|
deba@1979
|
167 |
Parent::set(it, cmap[it]);
|
deba@1979
|
168 |
}
|
deba@1979
|
169 |
return *this;
|
deba@1979
|
170 |
}
|
deba@1979
|
171 |
};
|
deba@1979
|
172 |
|
deba@1979
|
173 |
template <typename _Value>
|
deba@1979
|
174 |
class EdgeMap : public Graph::template EdgeMap<_Value> {
|
deba@1979
|
175 |
public:
|
deba@1979
|
176 |
typedef typename Graph::template EdgeMap<_Value> Parent;
|
deba@1979
|
177 |
explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)
|
deba@1979
|
178 |
: Parent(*ga.graph) {}
|
deba@1979
|
179 |
EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
|
deba@1979
|
180 |
: Parent(*ga.graph, value) {}
|
deba@1979
|
181 |
|
deba@1979
|
182 |
EdgeMap& operator=(const EdgeMap& cmap) {
|
deba@1979
|
183 |
return operator=<EdgeMap>(cmap);
|
deba@1979
|
184 |
}
|
deba@1979
|
185 |
|
deba@1979
|
186 |
template <typename CMap>
|
deba@1979
|
187 |
EdgeMap& operator=(const CMap& cmap) {
|
deba@1979
|
188 |
checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
|
deba@1979
|
189 |
const typename Parent::Graph* graph = Parent::getGraph();
|
deba@1979
|
190 |
Edge it;
|
deba@1979
|
191 |
for (graph->first(it); it != INVALID; graph->next(it)) {
|
deba@1979
|
192 |
Parent::set(it, cmap[it]);
|
deba@1979
|
193 |
}
|
deba@1979
|
194 |
return *this;
|
deba@1979
|
195 |
}
|
deba@1979
|
196 |
};
|
deba@1979
|
197 |
|
deba@1979
|
198 |
template <typename _Value>
|
deba@1979
|
199 |
class UEdgeMap : public Graph::template UEdgeMap<_Value> {
|
deba@1979
|
200 |
public:
|
deba@1979
|
201 |
typedef typename Graph::template UEdgeMap<_Value> Parent;
|
deba@1979
|
202 |
explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)
|
deba@1979
|
203 |
: Parent(*ga.graph) {}
|
deba@1979
|
204 |
UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)
|
deba@1979
|
205 |
: Parent(*ga.graph, value) {}
|
deba@1979
|
206 |
|
deba@1979
|
207 |
UEdgeMap& operator=(const UEdgeMap& cmap) {
|
deba@1979
|
208 |
return operator=<UEdgeMap>(cmap);
|
deba@1979
|
209 |
}
|
deba@1979
|
210 |
|
deba@1979
|
211 |
template <typename CMap>
|
deba@1979
|
212 |
UEdgeMap& operator=(const CMap& cmap) {
|
deba@1979
|
213 |
checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
|
deba@1979
|
214 |
const typename Parent::Graph* graph = Parent::getGraph();
|
deba@1979
|
215 |
UEdge it;
|
deba@1979
|
216 |
for (graph->first(it); it != INVALID; graph->next(it)) {
|
deba@1979
|
217 |
Parent::set(it, cmap[it]);
|
deba@1979
|
218 |
}
|
deba@1979
|
219 |
return *this;
|
deba@1979
|
220 |
}
|
deba@1979
|
221 |
};
|
deba@1979
|
222 |
|
deba@1979
|
223 |
};
|
deba@1979
|
224 |
|
deba@1979
|
225 |
/// \ingroup graph_adaptors
|
deba@1979
|
226 |
template <typename _UGraph>
|
deba@1979
|
227 |
class UGraphAdaptor
|
deba@1979
|
228 |
: public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {
|
deba@1979
|
229 |
public:
|
deba@1979
|
230 |
typedef _UGraph Graph;
|
deba@1979
|
231 |
typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;
|
deba@1979
|
232 |
protected:
|
deba@1979
|
233 |
UGraphAdaptor() : Parent() {}
|
deba@1979
|
234 |
|
deba@1979
|
235 |
public:
|
deba@1979
|
236 |
explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }
|
deba@1979
|
237 |
};
|
deba@1979
|
238 |
|
deba@1979
|
239 |
template <typename _UGraph, typename NodeFilterMap,
|
deba@1979
|
240 |
typename UEdgeFilterMap, bool checked = true>
|
deba@1979
|
241 |
class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {
|
deba@1979
|
242 |
public:
|
deba@1979
|
243 |
typedef _UGraph Graph;
|
deba@1979
|
244 |
typedef UGraphAdaptorBase<_UGraph> Parent;
|
deba@1979
|
245 |
protected:
|
deba@1979
|
246 |
|
deba@1979
|
247 |
NodeFilterMap* node_filter_map;
|
deba@1979
|
248 |
UEdgeFilterMap* uedge_filter_map;
|
deba@1979
|
249 |
|
deba@1979
|
250 |
SubUGraphAdaptorBase()
|
deba@1979
|
251 |
: Parent(), node_filter_map(0), uedge_filter_map(0) { }
|
deba@1979
|
252 |
|
deba@1979
|
253 |
void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
|
deba@1979
|
254 |
node_filter_map=&_node_filter_map;
|
deba@1979
|
255 |
}
|
deba@1979
|
256 |
void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
|
deba@1979
|
257 |
uedge_filter_map=&_uedge_filter_map;
|
deba@1979
|
258 |
}
|
deba@1979
|
259 |
|
deba@1979
|
260 |
public:
|
deba@1979
|
261 |
|
deba@1979
|
262 |
typedef typename Parent::Node Node;
|
deba@1979
|
263 |
typedef typename Parent::Edge Edge;
|
deba@1979
|
264 |
typedef typename Parent::UEdge UEdge;
|
deba@1979
|
265 |
|
deba@1979
|
266 |
void first(Node& i) const {
|
deba@1979
|
267 |
Parent::first(i);
|
deba@1979
|
268 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
deba@1979
|
269 |
}
|
deba@1979
|
270 |
|
deba@1979
|
271 |
void first(Edge& i) const {
|
deba@1979
|
272 |
Parent::first(i);
|
deba@1979
|
273 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
274 |
|| !(*node_filter_map)[Parent::source(i)]
|
deba@1979
|
275 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
|
deba@1979
|
276 |
}
|
deba@1979
|
277 |
|
deba@1979
|
278 |
void first(UEdge& i) const {
|
deba@1979
|
279 |
Parent::first(i);
|
deba@1979
|
280 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
281 |
|| !(*node_filter_map)[Parent::source(i)]
|
deba@1979
|
282 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
|
deba@1979
|
283 |
}
|
deba@1979
|
284 |
|
deba@1979
|
285 |
void firstIn(Edge& i, const Node& n) const {
|
deba@1979
|
286 |
Parent::firstIn(i, n);
|
deba@1979
|
287 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
288 |
|| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
|
deba@1979
|
289 |
}
|
deba@1979
|
290 |
|
deba@1979
|
291 |
void firstOut(Edge& i, const Node& n) const {
|
deba@1979
|
292 |
Parent::firstOut(i, n);
|
deba@1979
|
293 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
294 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
|
deba@1979
|
295 |
}
|
deba@1979
|
296 |
|
deba@1979
|
297 |
void firstInc(UEdge& i, bool& d, const Node& n) const {
|
deba@1979
|
298 |
Parent::firstInc(i, d, n);
|
deba@1979
|
299 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
300 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);
|
deba@1979
|
301 |
}
|
deba@1979
|
302 |
|
deba@1979
|
303 |
void next(Node& i) const {
|
deba@1979
|
304 |
Parent::next(i);
|
deba@1979
|
305 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
deba@1979
|
306 |
}
|
deba@1979
|
307 |
|
deba@1979
|
308 |
void next(Edge& i) const {
|
deba@1979
|
309 |
Parent::next(i);
|
deba@1979
|
310 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
311 |
|| !(*node_filter_map)[Parent::source(i)]
|
deba@1979
|
312 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
|
deba@1979
|
313 |
}
|
deba@1979
|
314 |
|
deba@1979
|
315 |
void next(UEdge& i) const {
|
deba@1979
|
316 |
Parent::next(i);
|
deba@1979
|
317 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
318 |
|| !(*node_filter_map)[Parent::source(i)]
|
deba@1979
|
319 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::next(i);
|
deba@1979
|
320 |
}
|
deba@1979
|
321 |
|
deba@1979
|
322 |
void nextIn(Edge& i) const {
|
deba@1979
|
323 |
Parent::nextIn(i);
|
deba@1979
|
324 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
325 |
|| !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);
|
deba@1979
|
326 |
}
|
deba@1979
|
327 |
|
deba@1979
|
328 |
void nextOut(Edge& i) const {
|
deba@1979
|
329 |
Parent::nextOut(i);
|
deba@1979
|
330 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
331 |
|| !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);
|
deba@1979
|
332 |
}
|
deba@1979
|
333 |
|
deba@1979
|
334 |
void nextInc(UEdge& i, bool& d) const {
|
deba@1979
|
335 |
Parent::nextInc(i, d);
|
deba@1979
|
336 |
while (i!=INVALID && (!(*uedge_filter_map)[i]
|
deba@1979
|
337 |
|| !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);
|
deba@1979
|
338 |
}
|
deba@1979
|
339 |
|
deba@1979
|
340 |
///\e
|
deba@1979
|
341 |
|
deba@1979
|
342 |
/// This function hides \c n in the graph, i.e. the iteration
|
deba@1979
|
343 |
/// jumps over it. This is done by simply setting the value of \c n
|
deba@1979
|
344 |
/// to be false in the corresponding node-map.
|
deba@1979
|
345 |
void hide(const Node& n) const { node_filter_map->set(n, false); }
|
deba@1979
|
346 |
|
deba@1979
|
347 |
///\e
|
deba@1979
|
348 |
|
deba@1979
|
349 |
/// This function hides \c e in the graph, i.e. the iteration
|
deba@1979
|
350 |
/// jumps over it. This is done by simply setting the value of \c e
|
deba@1979
|
351 |
/// to be false in the corresponding edge-map.
|
deba@1979
|
352 |
void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
|
deba@1979
|
353 |
|
deba@1979
|
354 |
///\e
|
deba@1979
|
355 |
|
deba@1979
|
356 |
/// The value of \c n is set to be true in the node-map which stores
|
deba@1979
|
357 |
/// hide information. If \c n was hidden previuosly, then it is shown
|
deba@1979
|
358 |
/// again
|
deba@1979
|
359 |
void unHide(const Node& n) const { node_filter_map->set(n, true); }
|
deba@1979
|
360 |
|
deba@1979
|
361 |
///\e
|
deba@1979
|
362 |
|
deba@1979
|
363 |
/// The value of \c e is set to be true in the edge-map which stores
|
deba@1979
|
364 |
/// hide information. If \c e was hidden previuosly, then it is shown
|
deba@1979
|
365 |
/// again
|
deba@1979
|
366 |
void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
|
deba@1979
|
367 |
|
deba@1979
|
368 |
/// Returns true if \c n is hidden.
|
deba@1979
|
369 |
|
deba@1979
|
370 |
///\e
|
deba@1979
|
371 |
///
|
deba@1979
|
372 |
bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
|
deba@1979
|
373 |
|
deba@1979
|
374 |
/// Returns true if \c n is hidden.
|
deba@1979
|
375 |
|
deba@1979
|
376 |
///\e
|
deba@1979
|
377 |
///
|
deba@1979
|
378 |
bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
|
deba@1979
|
379 |
|
deba@1979
|
380 |
typedef False NodeNumTag;
|
deba@1979
|
381 |
typedef False EdgeNumTag;
|
deba@1979
|
382 |
};
|
deba@1979
|
383 |
|
deba@1979
|
384 |
template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>
|
deba@1979
|
385 |
class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>
|
deba@1979
|
386 |
: public UGraphAdaptorBase<_UGraph> {
|
deba@1979
|
387 |
public:
|
deba@1979
|
388 |
typedef _UGraph Graph;
|
deba@1979
|
389 |
typedef UGraphAdaptorBase<_UGraph> Parent;
|
deba@1979
|
390 |
protected:
|
deba@1979
|
391 |
NodeFilterMap* node_filter_map;
|
deba@1979
|
392 |
UEdgeFilterMap* uedge_filter_map;
|
deba@1979
|
393 |
SubUGraphAdaptorBase() : Parent(),
|
deba@1979
|
394 |
node_filter_map(0), uedge_filter_map(0) { }
|
deba@1979
|
395 |
|
deba@1979
|
396 |
void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
|
deba@1979
|
397 |
node_filter_map=&_node_filter_map;
|
deba@1979
|
398 |
}
|
deba@1979
|
399 |
void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {
|
deba@1979
|
400 |
uedge_filter_map=&_uedge_filter_map;
|
deba@1979
|
401 |
}
|
deba@1979
|
402 |
|
deba@1979
|
403 |
public:
|
deba@1979
|
404 |
|
deba@1979
|
405 |
typedef typename Parent::Node Node;
|
deba@1979
|
406 |
typedef typename Parent::Edge Edge;
|
deba@1979
|
407 |
typedef typename Parent::UEdge UEdge;
|
deba@1979
|
408 |
|
deba@1979
|
409 |
void first(Node& i) const {
|
deba@1979
|
410 |
Parent::first(i);
|
deba@1979
|
411 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
deba@1979
|
412 |
}
|
deba@1979
|
413 |
|
deba@1979
|
414 |
void first(Edge& i) const {
|
deba@1979
|
415 |
Parent::first(i);
|
deba@1979
|
416 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
|
deba@1979
|
417 |
}
|
deba@1979
|
418 |
|
deba@1979
|
419 |
void first(UEdge& i) const {
|
deba@1979
|
420 |
Parent::first(i);
|
deba@1979
|
421 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
|
deba@1979
|
422 |
}
|
deba@1979
|
423 |
|
deba@1979
|
424 |
void firstIn(Edge& i, const Node& n) const {
|
deba@1979
|
425 |
Parent::firstIn(i, n);
|
deba@1979
|
426 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
|
deba@1979
|
427 |
}
|
deba@1979
|
428 |
|
deba@1979
|
429 |
void firstOut(Edge& i, const Node& n) const {
|
deba@1979
|
430 |
Parent::firstOut(i, n);
|
deba@1979
|
431 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
|
deba@1979
|
432 |
}
|
deba@1979
|
433 |
|
deba@1979
|
434 |
void firstInc(UEdge& i, bool& d, const Node& n) const {
|
deba@1979
|
435 |
Parent::firstInc(i, d, n);
|
deba@1979
|
436 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
|
deba@1979
|
437 |
}
|
deba@1979
|
438 |
|
deba@1979
|
439 |
void next(Node& i) const {
|
deba@1979
|
440 |
Parent::next(i);
|
deba@1979
|
441 |
while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
|
deba@1979
|
442 |
}
|
deba@1979
|
443 |
void next(Edge& i) const {
|
deba@1979
|
444 |
Parent::next(i);
|
deba@1979
|
445 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
|
deba@1979
|
446 |
}
|
deba@1979
|
447 |
void next(UEdge& i) const {
|
deba@1979
|
448 |
Parent::next(i);
|
deba@1979
|
449 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);
|
deba@1979
|
450 |
}
|
deba@1979
|
451 |
void nextIn(Edge& i) const {
|
deba@1979
|
452 |
Parent::nextIn(i);
|
deba@1979
|
453 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);
|
deba@1979
|
454 |
}
|
deba@1979
|
455 |
|
deba@1979
|
456 |
void nextOut(Edge& i) const {
|
deba@1979
|
457 |
Parent::nextOut(i);
|
deba@1979
|
458 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);
|
deba@1979
|
459 |
}
|
deba@1979
|
460 |
void nextInc(UEdge& i, bool& d) const {
|
deba@1979
|
461 |
Parent::nextInc(i, d);
|
deba@1979
|
462 |
while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);
|
deba@1979
|
463 |
}
|
deba@1979
|
464 |
|
deba@1979
|
465 |
///\e
|
deba@1979
|
466 |
|
deba@1979
|
467 |
/// This function hides \c n in the graph, i.e. the iteration
|
deba@1979
|
468 |
/// jumps over it. This is done by simply setting the value of \c n
|
deba@1979
|
469 |
/// to be false in the corresponding node-map.
|
deba@1979
|
470 |
void hide(const Node& n) const { node_filter_map->set(n, false); }
|
deba@1979
|
471 |
|
deba@1979
|
472 |
///\e
|
deba@1979
|
473 |
|
deba@1979
|
474 |
/// This function hides \c e in the graph, i.e. the iteration
|
deba@1979
|
475 |
/// jumps over it. This is done by simply setting the value of \c e
|
deba@1979
|
476 |
/// to be false in the corresponding edge-map.
|
deba@1979
|
477 |
void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }
|
deba@1979
|
478 |
|
deba@1979
|
479 |
///\e
|
deba@1979
|
480 |
|
deba@1979
|
481 |
/// The value of \c n is set to be true in the node-map which stores
|
deba@1979
|
482 |
/// hide information. If \c n was hidden previuosly, then it is shown
|
deba@1979
|
483 |
/// again
|
deba@1979
|
484 |
void unHide(const Node& n) const { node_filter_map->set(n, true); }
|
deba@1979
|
485 |
|
deba@1979
|
486 |
///\e
|
deba@1979
|
487 |
|
deba@1979
|
488 |
/// The value of \c e is set to be true in the edge-map which stores
|
deba@1979
|
489 |
/// hide information. If \c e was hidden previuosly, then it is shown
|
deba@1979
|
490 |
/// again
|
deba@1979
|
491 |
void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }
|
deba@1979
|
492 |
|
deba@1979
|
493 |
/// Returns true if \c n is hidden.
|
deba@1979
|
494 |
|
deba@1979
|
495 |
///\e
|
deba@1979
|
496 |
///
|
deba@1979
|
497 |
bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
|
deba@1979
|
498 |
|
deba@1979
|
499 |
/// Returns true if \c n is hidden.
|
deba@1979
|
500 |
|
deba@1979
|
501 |
///\e
|
deba@1979
|
502 |
///
|
deba@1979
|
503 |
bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }
|
deba@1979
|
504 |
|
deba@1979
|
505 |
typedef False NodeNumTag;
|
deba@1979
|
506 |
typedef False EdgeNumTag;
|
deba@1979
|
507 |
};
|
deba@1979
|
508 |
|
deba@1979
|
509 |
/// \ingroup graph_adaptors
|
deba@1979
|
510 |
///
|
deba@1979
|
511 |
/// \brief A graph adaptor for hiding nodes and edges from an undirected
|
deba@1979
|
512 |
/// graph.
|
deba@1979
|
513 |
///
|
deba@1979
|
514 |
/// SubUGraphAdaptor shows the undirected graph with filtered node-set and
|
deba@1979
|
515 |
/// edge-set. If the \c checked parameter is true then it filters the edgeset
|
deba@1979
|
516 |
/// to do not get invalid edges without source or target.
|
deba@1979
|
517 |
///
|
deba@1979
|
518 |
/// If the \c checked template parameter is false then we have to note that
|
deba@1979
|
519 |
/// the node-iterator cares only the filter on the node-set, and the
|
deba@1979
|
520 |
/// edge-iterator cares only the filter on the edge-set.
|
deba@1979
|
521 |
/// This way the edge-map
|
deba@1979
|
522 |
/// should filter all edges which's source or target is filtered by the
|
deba@1979
|
523 |
/// node-filter.
|
deba@1979
|
524 |
///
|
deba@1979
|
525 |
/// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
|
deba@1979
|
526 |
/// \c Graph::Node that is why \c g.id(n) can be applied.
|
deba@1979
|
527 |
///
|
deba@1979
|
528 |
template<typename _UGraph, typename NodeFilterMap,
|
deba@1979
|
529 |
typename UEdgeFilterMap, bool checked = true>
|
deba@1979
|
530 |
class SubUGraphAdaptor :
|
deba@1979
|
531 |
public UGraphAdaptorExtender<
|
deba@1979
|
532 |
SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {
|
deba@1979
|
533 |
public:
|
deba@1979
|
534 |
typedef _UGraph Graph;
|
deba@1979
|
535 |
typedef UGraphAdaptorExtender<
|
deba@1979
|
536 |
SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;
|
deba@1979
|
537 |
protected:
|
deba@1979
|
538 |
SubUGraphAdaptor() { }
|
deba@1979
|
539 |
public:
|
deba@1979
|
540 |
SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,
|
deba@1979
|
541 |
UEdgeFilterMap& _uedge_filter_map) {
|
deba@1979
|
542 |
setGraph(_graph);
|
deba@1979
|
543 |
setNodeFilterMap(_node_filter_map);
|
deba@1979
|
544 |
setUEdgeFilterMap(_uedge_filter_map);
|
deba@1979
|
545 |
}
|
deba@1979
|
546 |
};
|
deba@1979
|
547 |
|
deba@1980
|
548 |
template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
|
deba@1980
|
549 |
SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
|
deba@1980
|
550 |
subUGraphAdaptor(const UGraph& graph,
|
deba@1980
|
551 |
NodeFilterMap& nfm, EdgeFilterMap& efm) {
|
deba@1980
|
552 |
return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>
|
deba@1980
|
553 |
(graph, nfm, efm);
|
deba@1980
|
554 |
}
|
deba@1980
|
555 |
|
deba@1980
|
556 |
template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
|
deba@1980
|
557 |
SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
|
deba@1980
|
558 |
subUGraphAdaptor(const UGraph& graph,
|
deba@1980
|
559 |
NodeFilterMap& nfm, EdgeFilterMap& efm) {
|
deba@1980
|
560 |
return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>
|
deba@1980
|
561 |
(graph, nfm, efm);
|
deba@1980
|
562 |
}
|
deba@1980
|
563 |
|
deba@1980
|
564 |
template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
|
deba@1980
|
565 |
SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
|
deba@1980
|
566 |
subUGraphAdaptor(const UGraph& graph,
|
deba@1980
|
567 |
NodeFilterMap& nfm, EdgeFilterMap& efm) {
|
deba@1980
|
568 |
return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>
|
deba@1980
|
569 |
(graph, nfm, efm);
|
deba@1980
|
570 |
}
|
deba@1980
|
571 |
|
deba@1980
|
572 |
template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>
|
deba@1980
|
573 |
SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>
|
deba@1980
|
574 |
subUGraphAdaptor(const UGraph& graph,
|
deba@1980
|
575 |
NodeFilterMap& nfm, EdgeFilterMap& efm) {
|
deba@1980
|
576 |
return SubUGraphAdaptor<const UGraph, const NodeFilterMap,
|
deba@1980
|
577 |
const EdgeFilterMap>(graph, nfm, efm);
|
deba@1980
|
578 |
}
|
deba@1980
|
579 |
|
deba@1979
|
580 |
/// \ingroup graph_adaptors
|
deba@1979
|
581 |
///
|
deba@1980
|
582 |
/// \brief An adaptor for hiding nodes from an undirected graph.
|
deba@1979
|
583 |
///
|
deba@1979
|
584 |
///
|
deba@1979
|
585 |
/// An adaptor for hiding nodes from an undirected graph.
|
deba@1979
|
586 |
/// This adaptor specializes SubUGraphAdaptor in the way that only
|
deba@1979
|
587 |
/// the node-set
|
deba@1979
|
588 |
/// can be filtered. In usual case the checked parameter is true, we get the
|
deba@1979
|
589 |
/// induced subgraph. But if the checked parameter is false then we can only
|
deba@1979
|
590 |
/// filter only isolated nodes.
|
deba@1979
|
591 |
template<typename _UGraph, typename NodeFilterMap, bool checked = true>
|
deba@1979
|
592 |
class NodeSubUGraphAdaptor :
|
deba@1979
|
593 |
public SubUGraphAdaptor<_UGraph, NodeFilterMap,
|
deba@1979
|
594 |
ConstMap<typename _UGraph::UEdge, bool>, checked> {
|
deba@1979
|
595 |
public:
|
deba@1979
|
596 |
typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,
|
deba@1979
|
597 |
ConstMap<typename _UGraph::UEdge, bool> > Parent;
|
deba@1979
|
598 |
typedef _UGraph Graph;
|
deba@1979
|
599 |
protected:
|
deba@1985
|
600 |
ConstMap<typename _UGraph::UEdge, bool> const_true_map;
|
deba@1979
|
601 |
public:
|
deba@1979
|
602 |
NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :
|
deba@1979
|
603 |
Parent(), const_true_map(true) {
|
deba@1979
|
604 |
Parent::setGraph(_graph);
|
deba@1979
|
605 |
Parent::setNodeFilterMap(_node_filter_map);
|
deba@1979
|
606 |
Parent::setUEdgeFilterMap(const_true_map);
|
deba@1979
|
607 |
}
|
deba@1979
|
608 |
};
|
deba@1979
|
609 |
|
deba@1979
|
610 |
template<typename UGraph, typename NodeFilterMap>
|
deba@1979
|
611 |
NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>
|
deba@1979
|
612 |
nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {
|
deba@1979
|
613 |
return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);
|
deba@1979
|
614 |
}
|
deba@1979
|
615 |
|
deba@1979
|
616 |
template<typename UGraph, typename NodeFilterMap>
|
deba@1979
|
617 |
NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>
|
deba@1979
|
618 |
nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {
|
deba@1979
|
619 |
return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);
|
deba@1979
|
620 |
}
|
deba@1979
|
621 |
|
deba@1979
|
622 |
|
deba@1979
|
623 |
/// \brief An adaptor for hiding undirected edges from an undirected graph.
|
deba@1979
|
624 |
///
|
deba@1979
|
625 |
/// \warning Graph adaptors are in even more experimental state
|
deba@1979
|
626 |
/// than the other parts of the lib. Use them at you own risk.
|
deba@1979
|
627 |
///
|
deba@1979
|
628 |
/// An adaptor for hiding undirected edges from an undirected graph.
|
deba@1979
|
629 |
/// This adaptor specializes SubUGraphAdaptor in the way that
|
deba@1979
|
630 |
/// only the edge-set
|
deba@1979
|
631 |
/// can be filtered.
|
deba@1979
|
632 |
template<typename _UGraph, typename UEdgeFilterMap>
|
deba@1979
|
633 |
class EdgeSubUGraphAdaptor :
|
deba@1979
|
634 |
public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
|
deba@1979
|
635 |
UEdgeFilterMap, false> {
|
deba@1979
|
636 |
public:
|
deba@1979
|
637 |
typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,
|
deba@1979
|
638 |
UEdgeFilterMap, false> Parent;
|
deba@1979
|
639 |
typedef _UGraph Graph;
|
deba@1979
|
640 |
protected:
|
deba@1979
|
641 |
ConstMap<typename Graph::Node, bool> const_true_map;
|
deba@1979
|
642 |
public:
|
deba@1979
|
643 |
EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :
|
deba@1979
|
644 |
Parent(), const_true_map(true) {
|
deba@1979
|
645 |
Parent::setGraph(_graph);
|
deba@1979
|
646 |
Parent::setNodeFilterMap(const_true_map);
|
deba@1979
|
647 |
Parent::setUEdgeFilterMap(_uedge_filter_map);
|
deba@1979
|
648 |
}
|
deba@1979
|
649 |
};
|
deba@1979
|
650 |
|
deba@1979
|
651 |
template<typename UGraph, typename EdgeFilterMap>
|
deba@1979
|
652 |
EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>
|
deba@1979
|
653 |
edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {
|
deba@1979
|
654 |
return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);
|
deba@1979
|
655 |
}
|
deba@1979
|
656 |
|
deba@1979
|
657 |
template<typename UGraph, typename EdgeFilterMap>
|
deba@1979
|
658 |
EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>
|
deba@1979
|
659 |
edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {
|
deba@1979
|
660 |
return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);
|
deba@1979
|
661 |
}
|
deba@1979
|
662 |
|
deba@1979
|
663 |
template <typename _UGraph, typename _DirectionMap>
|
deba@1980
|
664 |
class DirUGraphAdaptorBase {
|
deba@1979
|
665 |
public:
|
deba@1979
|
666 |
|
deba@1979
|
667 |
typedef _UGraph Graph;
|
deba@1979
|
668 |
typedef _DirectionMap DirectionMap;
|
deba@1979
|
669 |
|
deba@1979
|
670 |
typedef typename _UGraph::Node Node;
|
deba@1979
|
671 |
typedef typename _UGraph::UEdge Edge;
|
deba@1979
|
672 |
|
deba@1979
|
673 |
void first(Node& i) const { graph->first(i); }
|
deba@1979
|
674 |
void first(Edge& i) const { graph->first(i); }
|
deba@1979
|
675 |
void firstIn(Edge& i, const Node& n) const {
|
deba@1979
|
676 |
bool d;
|
deba@1979
|
677 |
graph->firstInc(i, d, n);
|
deba@1979
|
678 |
while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
|
deba@1979
|
679 |
}
|
deba@1979
|
680 |
void firstOut(Edge& i, const Node& n ) const {
|
deba@1979
|
681 |
bool d;
|
deba@1979
|
682 |
graph->firstInc(i, d, n);
|
deba@1979
|
683 |
while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
|
deba@1979
|
684 |
}
|
deba@1979
|
685 |
|
deba@1979
|
686 |
void next(Node& i) const { graph->next(i); }
|
deba@1979
|
687 |
void next(Edge& i) const { graph->next(i); }
|
deba@1979
|
688 |
void nextIn(Edge& i) const {
|
deba@1979
|
689 |
bool d = !(*direction)[i];
|
deba@1979
|
690 |
graph->nextInc(i, d);
|
deba@1979
|
691 |
while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);
|
deba@1979
|
692 |
}
|
deba@1979
|
693 |
void nextOut(Edge& i) const {
|
deba@1979
|
694 |
bool d = (*direction)[i];
|
deba@1979
|
695 |
graph->nextInc(i, d);
|
deba@1979
|
696 |
while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);
|
deba@1979
|
697 |
}
|
deba@1979
|
698 |
|
deba@1979
|
699 |
Node source(const Edge& e) const {
|
deba@1979
|
700 |
return (*direction)[e] ? graph->source(e) : graph->target(e);
|
deba@1979
|
701 |
}
|
deba@1979
|
702 |
Node target(const Edge& e) const {
|
deba@1979
|
703 |
return (*direction)[e] ? graph->target(e) : graph->source(e);
|
deba@1979
|
704 |
}
|
deba@1979
|
705 |
|
deba@1979
|
706 |
typedef NodeNumTagIndicator<Graph> NodeNumTag;
|
deba@1979
|
707 |
int nodeNum() const { return graph->nodeNum(); }
|
deba@1979
|
708 |
|
deba@1979
|
709 |
typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
|
deba@1979
|
710 |
int edgeNum() const { return graph->uEdgeNum(); }
|
deba@1979
|
711 |
|
deba@1979
|
712 |
typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
|
deba@1979
|
713 |
Edge findEdge(const Node& source, const Node& target,
|
deba@1979
|
714 |
const Edge& prev = INVALID) {
|
deba@1979
|
715 |
Edge edge = prev;
|
deba@1979
|
716 |
bool d = edge == INVALID ? true : (*direction)[edge];
|
deba@1979
|
717 |
if (d) {
|
deba@1979
|
718 |
edge = graph->findUEdge(source, target, edge);
|
deba@1979
|
719 |
while (edge != INVALID && !(*direction)[edge]) {
|
deba@1979
|
720 |
graph->findUEdge(source, target, edge);
|
deba@1979
|
721 |
}
|
deba@1979
|
722 |
if (edge != INVALID) return edge;
|
deba@1979
|
723 |
}
|
deba@1979
|
724 |
graph->findUEdge(target, source, edge);
|
deba@1979
|
725 |
while (edge != INVALID && (*direction)[edge]) {
|
deba@1979
|
726 |
graph->findUEdge(source, target, edge);
|
deba@1979
|
727 |
}
|
deba@1979
|
728 |
return edge;
|
deba@1979
|
729 |
}
|
deba@1979
|
730 |
|
deba@1979
|
731 |
Node addNode() const {
|
deba@1979
|
732 |
return Node(graph->addNode());
|
deba@1979
|
733 |
}
|
deba@1979
|
734 |
|
deba@1979
|
735 |
Edge addEdge(const Node& source, const Node& target) const {
|
deba@1979
|
736 |
Edge edge = graph->addEdge(source, target);
|
deba@1979
|
737 |
(*direction)[edge] = graph->source(edge) == source;
|
deba@1979
|
738 |
return edge;
|
deba@1979
|
739 |
}
|
deba@1979
|
740 |
|
deba@1979
|
741 |
void erase(const Node& i) const { graph->erase(i); }
|
deba@1979
|
742 |
void erase(const Edge& i) const { graph->erase(i); }
|
deba@1979
|
743 |
|
deba@1979
|
744 |
void clear() const { graph->clear(); }
|
deba@1979
|
745 |
|
deba@1979
|
746 |
int id(const Node& v) const { return graph->id(v); }
|
deba@1979
|
747 |
int id(const Edge& e) const { return graph->id(e); }
|
deba@1979
|
748 |
|
deba@1979
|
749 |
void reverseEdge(const Edge& edge) {
|
deba@1979
|
750 |
direction->set(edge, !(*direction)[edge]);
|
deba@1979
|
751 |
}
|
deba@1979
|
752 |
|
deba@1979
|
753 |
template <typename _Value>
|
deba@1979
|
754 |
class NodeMap : public _UGraph::template NodeMap<_Value> {
|
deba@1979
|
755 |
public:
|
deba@1979
|
756 |
typedef typename _UGraph::template NodeMap<_Value> Parent;
|
deba@1980
|
757 |
explicit NodeMap(const DirUGraphAdaptorBase& ga)
|
deba@1979
|
758 |
: Parent(*ga.graph) { }
|
deba@1980
|
759 |
NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
|
deba@1979
|
760 |
: Parent(*ga.graph, value) { }
|
deba@1979
|
761 |
};
|
deba@1979
|
762 |
|
deba@1979
|
763 |
template <typename _Value>
|
deba@1979
|
764 |
class EdgeMap : public _UGraph::template UEdgeMap<_Value> {
|
deba@1979
|
765 |
public:
|
deba@1980
|
766 |
typedef typename _UGraph::template UEdgeMap<_Value> Parent;
|
deba@1980
|
767 |
explicit EdgeMap(const DirUGraphAdaptorBase& ga)
|
deba@1979
|
768 |
: Parent(*ga.graph) { }
|
deba@1980
|
769 |
EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)
|
deba@1979
|
770 |
: Parent(*ga.graph, value) { }
|
deba@1979
|
771 |
};
|
deba@1979
|
772 |
|
deba@1979
|
773 |
|
deba@1979
|
774 |
|
deba@1979
|
775 |
protected:
|
deba@1979
|
776 |
Graph* graph;
|
deba@1979
|
777 |
DirectionMap* direction;
|
deba@1979
|
778 |
|
deba@1979
|
779 |
void setDirectionMap(DirectionMap& _direction) {
|
deba@1979
|
780 |
direction = &_direction;
|
deba@1979
|
781 |
}
|
deba@1979
|
782 |
|
deba@1979
|
783 |
void setGraph(Graph& _graph) {
|
deba@1979
|
784 |
graph = &_graph;
|
deba@1979
|
785 |
}
|
deba@1979
|
786 |
|
deba@1979
|
787 |
};
|
deba@1979
|
788 |
|
deba@1979
|
789 |
|
deba@1980
|
790 |
/// \ingroup graph_adaptors
|
deba@1980
|
791 |
/// \brief A directed graph is made from a undirected graph by an adaptor
|
deba@1980
|
792 |
///
|
deba@1980
|
793 |
/// This adaptor gives a direction for each uedge in the undirected graph.
|
deba@1980
|
794 |
/// The direction of the edges stored in the DirectionMap. This map is
|
deba@1980
|
795 |
/// a bool map on the undirected edges. If the uedge is mapped to true
|
deba@1980
|
796 |
/// then the direction of the directed edge will be the same as the
|
deba@1980
|
797 |
/// default direction of the uedge. The edges can be easily reverted
|
deba@1980
|
798 |
/// by the reverseEdge member in the adaptor.
|
deba@1980
|
799 |
template<typename _Graph,
|
deba@1980
|
800 |
typename DirectionMap = typename _Graph::template UEdgeMap<bool> >
|
deba@1980
|
801 |
class DirUGraphAdaptor :
|
deba@1979
|
802 |
public GraphAdaptorExtender<
|
deba@1980
|
803 |
DirUGraphAdaptorBase<_Graph, DirectionMap> > {
|
deba@1979
|
804 |
public:
|
deba@1979
|
805 |
typedef _Graph Graph;
|
deba@1979
|
806 |
typedef GraphAdaptorExtender<
|
deba@1980
|
807 |
DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;
|
deba@1979
|
808 |
protected:
|
deba@1980
|
809 |
DirUGraphAdaptor() { }
|
deba@1979
|
810 |
public:
|
deba@1980
|
811 |
DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {
|
deba@1979
|
812 |
setGraph(_graph);
|
deba@1979
|
813 |
setDirectionMap(_direction_map);
|
deba@1979
|
814 |
}
|
deba@1979
|
815 |
};
|
deba@1979
|
816 |
|
deba@1979
|
817 |
template<typename UGraph, typename DirectionMap>
|
deba@1980
|
818 |
DirUGraphAdaptor<const UGraph, DirectionMap>
|
deba@1980
|
819 |
dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {
|
deba@1980
|
820 |
return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);
|
deba@1979
|
821 |
}
|
deba@1979
|
822 |
|
deba@1979
|
823 |
template<typename UGraph, typename DirectionMap>
|
deba@1980
|
824 |
DirUGraphAdaptor<const UGraph, const DirectionMap>
|
deba@1980
|
825 |
dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {
|
deba@1980
|
826 |
return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);
|
deba@1979
|
827 |
}
|
deba@1979
|
828 |
|
deba@1979
|
829 |
}
|
deba@1979
|
830 |
|
deba@1979
|
831 |
#endif
|