alpar@209
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
alpar@100
|
2 |
*
|
alpar@209
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
alpar@100
|
4 |
*
|
alpar@100
|
5 |
* Copyright (C) 2003-2008
|
alpar@100
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@100
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@100
|
8 |
*
|
alpar@100
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@100
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@100
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@100
|
12 |
*
|
alpar@100
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@100
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@100
|
15 |
* purpose.
|
alpar@100
|
16 |
*
|
alpar@100
|
17 |
*/
|
alpar@100
|
18 |
|
alpar@100
|
19 |
#ifndef LEMON_GRAPH_UTILS_H
|
alpar@100
|
20 |
#define LEMON_GRAPH_UTILS_H
|
alpar@100
|
21 |
|
alpar@100
|
22 |
#include <iterator>
|
alpar@100
|
23 |
#include <vector>
|
alpar@100
|
24 |
#include <map>
|
alpar@100
|
25 |
#include <cmath>
|
alpar@100
|
26 |
#include <algorithm>
|
alpar@100
|
27 |
|
alpar@100
|
28 |
#include <lemon/bits/invalid.h>
|
alpar@100
|
29 |
#include <lemon/bits/utility.h>
|
alpar@100
|
30 |
#include <lemon/maps.h>
|
alpar@100
|
31 |
#include <lemon/bits/traits.h>
|
alpar@100
|
32 |
|
alpar@100
|
33 |
#include <lemon/bits/alteration_notifier.h>
|
alpar@100
|
34 |
#include <lemon/bits/default_map.h>
|
alpar@100
|
35 |
|
alpar@100
|
36 |
///\ingroup gutils
|
alpar@100
|
37 |
///\file
|
deba@139
|
38 |
///\brief Graph utilities.
|
alpar@100
|
39 |
|
alpar@100
|
40 |
namespace lemon {
|
alpar@100
|
41 |
|
alpar@100
|
42 |
/// \addtogroup gutils
|
alpar@100
|
43 |
/// @{
|
alpar@100
|
44 |
|
alpar@100
|
45 |
///Creates convenience typedefs for the digraph types and iterators
|
alpar@100
|
46 |
|
alpar@100
|
47 |
///This \c \#define creates convenience typedefs for the following types
|
alpar@100
|
48 |
///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
|
alpar@209
|
49 |
///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
|
deba@148
|
50 |
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
|
deba@148
|
51 |
///
|
deba@148
|
52 |
///\note If the graph type is a dependent type, ie. the graph type depend
|
deba@148
|
53 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
|
deba@148
|
54 |
///macro.
|
alpar@209
|
55 |
#define DIGRAPH_TYPEDEFS(Digraph) \
|
alpar@209
|
56 |
typedef Digraph::Node Node; \
|
alpar@209
|
57 |
typedef Digraph::NodeIt NodeIt; \
|
alpar@209
|
58 |
typedef Digraph::Arc Arc; \
|
alpar@209
|
59 |
typedef Digraph::ArcIt ArcIt; \
|
alpar@209
|
60 |
typedef Digraph::InArcIt InArcIt; \
|
alpar@209
|
61 |
typedef Digraph::OutArcIt OutArcIt; \
|
alpar@209
|
62 |
typedef Digraph::NodeMap<bool> BoolNodeMap; \
|
alpar@209
|
63 |
typedef Digraph::NodeMap<int> IntNodeMap; \
|
alpar@209
|
64 |
typedef Digraph::NodeMap<double> DoubleNodeMap; \
|
alpar@209
|
65 |
typedef Digraph::ArcMap<bool> BoolArcMap; \
|
alpar@209
|
66 |
typedef Digraph::ArcMap<int> IntArcMap; \
|
deba@148
|
67 |
typedef Digraph::ArcMap<double> DoubleArcMap
|
deba@140
|
68 |
|
deba@148
|
69 |
///Creates convenience typedefs for the digraph types and iterators
|
alpar@100
|
70 |
|
deba@148
|
71 |
///\see DIGRAPH_TYPEDEFS
|
deba@148
|
72 |
///
|
deba@148
|
73 |
///\note Use this macro, if the graph type is a dependent type,
|
deba@148
|
74 |
///ie. the graph type depend on a template parameter.
|
alpar@209
|
75 |
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
|
alpar@209
|
76 |
typedef typename Digraph::Node Node; \
|
alpar@209
|
77 |
typedef typename Digraph::NodeIt NodeIt; \
|
alpar@209
|
78 |
typedef typename Digraph::Arc Arc; \
|
alpar@209
|
79 |
typedef typename Digraph::ArcIt ArcIt; \
|
alpar@209
|
80 |
typedef typename Digraph::InArcIt InArcIt; \
|
alpar@209
|
81 |
typedef typename Digraph::OutArcIt OutArcIt; \
|
alpar@209
|
82 |
typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
|
alpar@209
|
83 |
typedef typename Digraph::template NodeMap<int> IntNodeMap; \
|
alpar@209
|
84 |
typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
|
alpar@209
|
85 |
typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
|
alpar@209
|
86 |
typedef typename Digraph::template ArcMap<int> IntArcMap; \
|
deba@148
|
87 |
typedef typename Digraph::template ArcMap<double> DoubleArcMap
|
alpar@209
|
88 |
|
alpar@100
|
89 |
///Creates convenience typedefs for the graph types and iterators
|
alpar@100
|
90 |
|
deba@139
|
91 |
///This \c \#define creates the same convenience typedefs as defined
|
deba@139
|
92 |
///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
|
deba@139
|
93 |
///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
|
deba@139
|
94 |
///\c DoubleEdgeMap.
|
deba@148
|
95 |
///
|
deba@148
|
96 |
///\note If the graph type is a dependent type, ie. the graph type depend
|
deba@148
|
97 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
|
deba@148
|
98 |
///macro.
|
alpar@209
|
99 |
#define GRAPH_TYPEDEFS(Graph) \
|
alpar@209
|
100 |
DIGRAPH_TYPEDEFS(Graph); \
|
alpar@209
|
101 |
typedef Graph::Edge Edge; \
|
alpar@209
|
102 |
typedef Graph::EdgeIt EdgeIt; \
|
alpar@209
|
103 |
typedef Graph::IncEdgeIt IncEdgeIt; \
|
alpar@209
|
104 |
typedef Graph::EdgeMap<bool> BoolEdgeMap; \
|
alpar@209
|
105 |
typedef Graph::EdgeMap<int> IntEdgeMap; \
|
deba@148
|
106 |
typedef Graph::EdgeMap<double> DoubleEdgeMap
|
deba@140
|
107 |
|
deba@148
|
108 |
///Creates convenience typedefs for the graph types and iterators
|
deba@148
|
109 |
|
deba@148
|
110 |
///\see GRAPH_TYPEDEFS
|
deba@148
|
111 |
///
|
deba@148
|
112 |
///\note Use this macro, if the graph type is a dependent type,
|
deba@148
|
113 |
///ie. the graph type depend on a template parameter.
|
alpar@209
|
114 |
#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
|
alpar@209
|
115 |
TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
|
alpar@209
|
116 |
typedef typename Graph::Edge Edge; \
|
alpar@209
|
117 |
typedef typename Graph::EdgeIt EdgeIt; \
|
alpar@209
|
118 |
typedef typename Graph::IncEdgeIt IncEdgeIt; \
|
alpar@209
|
119 |
typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
|
alpar@209
|
120 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
|
deba@148
|
121 |
typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
|
deba@139
|
122 |
|
deba@139
|
123 |
/// \brief Function to count the items in the graph.
|
alpar@100
|
124 |
///
|
deba@139
|
125 |
/// This function counts the items (nodes, arcs etc) in the graph.
|
alpar@100
|
126 |
/// The complexity of the function is O(n) because
|
alpar@100
|
127 |
/// it iterates on all of the items.
|
deba@139
|
128 |
template <typename Graph, typename Item>
|
deba@139
|
129 |
inline int countItems(const Graph& g) {
|
deba@139
|
130 |
typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
|
alpar@100
|
131 |
int num = 0;
|
alpar@100
|
132 |
for (ItemIt it(g); it != INVALID; ++it) {
|
alpar@100
|
133 |
++num;
|
alpar@100
|
134 |
}
|
alpar@100
|
135 |
return num;
|
alpar@100
|
136 |
}
|
alpar@100
|
137 |
|
alpar@100
|
138 |
// Node counting:
|
alpar@100
|
139 |
|
deba@139
|
140 |
namespace _graph_utils_bits {
|
alpar@209
|
141 |
|
deba@139
|
142 |
template <typename Graph, typename Enable = void>
|
alpar@100
|
143 |
struct CountNodesSelector {
|
deba@139
|
144 |
static int count(const Graph &g) {
|
deba@139
|
145 |
return countItems<Graph, typename Graph::Node>(g);
|
alpar@100
|
146 |
}
|
alpar@100
|
147 |
};
|
alpar@100
|
148 |
|
deba@139
|
149 |
template <typename Graph>
|
alpar@100
|
150 |
struct CountNodesSelector<
|
alpar@209
|
151 |
Graph, typename
|
alpar@209
|
152 |
enable_if<typename Graph::NodeNumTag, void>::type>
|
alpar@100
|
153 |
{
|
deba@139
|
154 |
static int count(const Graph &g) {
|
alpar@100
|
155 |
return g.nodeNum();
|
alpar@100
|
156 |
}
|
alpar@209
|
157 |
};
|
alpar@100
|
158 |
}
|
alpar@100
|
159 |
|
deba@139
|
160 |
/// \brief Function to count the nodes in the graph.
|
alpar@100
|
161 |
///
|
deba@139
|
162 |
/// This function counts the nodes in the graph.
|
alpar@100
|
163 |
/// The complexity of the function is O(n) but for some
|
deba@139
|
164 |
/// graph structures it is specialized to run in O(1).
|
alpar@100
|
165 |
///
|
alpar@209
|
166 |
/// If the graph contains a \e nodeNum() member function and a
|
alpar@100
|
167 |
/// \e NodeNumTag tag then this function calls directly the member
|
alpar@100
|
168 |
/// function to query the cardinality of the node set.
|
deba@139
|
169 |
template <typename Graph>
|
deba@139
|
170 |
inline int countNodes(const Graph& g) {
|
deba@139
|
171 |
return _graph_utils_bits::CountNodesSelector<Graph>::count(g);
|
alpar@100
|
172 |
}
|
alpar@100
|
173 |
|
deba@139
|
174 |
// Arc counting:
|
deba@139
|
175 |
|
deba@139
|
176 |
namespace _graph_utils_bits {
|
alpar@209
|
177 |
|
deba@139
|
178 |
template <typename Graph, typename Enable = void>
|
deba@139
|
179 |
struct CountArcsSelector {
|
deba@139
|
180 |
static int count(const Graph &g) {
|
deba@139
|
181 |
return countItems<Graph, typename Graph::Arc>(g);
|
alpar@100
|
182 |
}
|
alpar@100
|
183 |
};
|
alpar@100
|
184 |
|
deba@139
|
185 |
template <typename Graph>
|
deba@139
|
186 |
struct CountArcsSelector<
|
alpar@209
|
187 |
Graph,
|
alpar@209
|
188 |
typename enable_if<typename Graph::ArcNumTag, void>::type>
|
alpar@100
|
189 |
{
|
deba@139
|
190 |
static int count(const Graph &g) {
|
alpar@100
|
191 |
return g.arcNum();
|
alpar@100
|
192 |
}
|
alpar@209
|
193 |
};
|
alpar@100
|
194 |
}
|
alpar@100
|
195 |
|
deba@139
|
196 |
/// \brief Function to count the arcs in the graph.
|
alpar@100
|
197 |
///
|
deba@139
|
198 |
/// This function counts the arcs in the graph.
|
alpar@100
|
199 |
/// The complexity of the function is O(e) but for some
|
deba@139
|
200 |
/// graph structures it is specialized to run in O(1).
|
alpar@100
|
201 |
///
|
alpar@209
|
202 |
/// If the graph contains a \e arcNum() member function and a
|
deba@139
|
203 |
/// \e EdgeNumTag tag then this function calls directly the member
|
alpar@100
|
204 |
/// function to query the cardinality of the arc set.
|
deba@139
|
205 |
template <typename Graph>
|
deba@139
|
206 |
inline int countArcs(const Graph& g) {
|
deba@139
|
207 |
return _graph_utils_bits::CountArcsSelector<Graph>::count(g);
|
alpar@100
|
208 |
}
|
alpar@100
|
209 |
|
deba@139
|
210 |
// Edge counting:
|
deba@139
|
211 |
namespace _graph_utils_bits {
|
alpar@209
|
212 |
|
deba@139
|
213 |
template <typename Graph, typename Enable = void>
|
alpar@100
|
214 |
struct CountEdgesSelector {
|
deba@139
|
215 |
static int count(const Graph &g) {
|
deba@139
|
216 |
return countItems<Graph, typename Graph::Edge>(g);
|
alpar@100
|
217 |
}
|
alpar@100
|
218 |
};
|
alpar@100
|
219 |
|
deba@139
|
220 |
template <typename Graph>
|
alpar@100
|
221 |
struct CountEdgesSelector<
|
alpar@209
|
222 |
Graph,
|
alpar@209
|
223 |
typename enable_if<typename Graph::EdgeNumTag, void>::type>
|
alpar@100
|
224 |
{
|
deba@139
|
225 |
static int count(const Graph &g) {
|
alpar@100
|
226 |
return g.edgeNum();
|
alpar@100
|
227 |
}
|
alpar@209
|
228 |
};
|
alpar@100
|
229 |
}
|
alpar@100
|
230 |
|
deba@139
|
231 |
/// \brief Function to count the edges in the graph.
|
alpar@100
|
232 |
///
|
deba@139
|
233 |
/// This function counts the edges in the graph.
|
deba@139
|
234 |
/// The complexity of the function is O(m) but for some
|
deba@139
|
235 |
/// graph structures it is specialized to run in O(1).
|
alpar@100
|
236 |
///
|
alpar@209
|
237 |
/// If the graph contains a \e edgeNum() member function and a
|
deba@139
|
238 |
/// \e EdgeNumTag tag then this function calls directly the member
|
alpar@100
|
239 |
/// function to query the cardinality of the edge set.
|
deba@139
|
240 |
template <typename Graph>
|
deba@139
|
241 |
inline int countEdges(const Graph& g) {
|
deba@139
|
242 |
return _graph_utils_bits::CountEdgesSelector<Graph>::count(g);
|
alpar@100
|
243 |
|
alpar@100
|
244 |
}
|
alpar@100
|
245 |
|
alpar@100
|
246 |
|
deba@139
|
247 |
template <typename Graph, typename DegIt>
|
deba@139
|
248 |
inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
|
alpar@100
|
249 |
int num = 0;
|
alpar@100
|
250 |
for (DegIt it(_g, _n); it != INVALID; ++it) {
|
alpar@100
|
251 |
++num;
|
alpar@100
|
252 |
}
|
alpar@100
|
253 |
return num;
|
alpar@100
|
254 |
}
|
alpar@100
|
255 |
|
alpar@100
|
256 |
/// \brief Function to count the number of the out-arcs from node \c n.
|
alpar@100
|
257 |
///
|
alpar@100
|
258 |
/// This function counts the number of the out-arcs from node \c n
|
alpar@209
|
259 |
/// in the graph.
|
deba@139
|
260 |
template <typename Graph>
|
deba@139
|
261 |
inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) {
|
deba@139
|
262 |
return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n);
|
alpar@100
|
263 |
}
|
alpar@100
|
264 |
|
alpar@100
|
265 |
/// \brief Function to count the number of the in-arcs to node \c n.
|
alpar@100
|
266 |
///
|
alpar@100
|
267 |
/// This function counts the number of the in-arcs to node \c n
|
alpar@209
|
268 |
/// in the graph.
|
deba@139
|
269 |
template <typename Graph>
|
deba@139
|
270 |
inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) {
|
deba@139
|
271 |
return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n);
|
alpar@100
|
272 |
}
|
alpar@100
|
273 |
|
deba@139
|
274 |
/// \brief Function to count the number of the inc-edges to node \c n.
|
alpar@100
|
275 |
///
|
deba@139
|
276 |
/// This function counts the number of the inc-edges to node \c n
|
alpar@209
|
277 |
/// in the graph.
|
deba@139
|
278 |
template <typename Graph>
|
deba@139
|
279 |
inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) {
|
deba@139
|
280 |
return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n);
|
alpar@100
|
281 |
}
|
alpar@100
|
282 |
|
deba@139
|
283 |
namespace _graph_utils_bits {
|
alpar@209
|
284 |
|
deba@139
|
285 |
template <typename Graph, typename Enable = void>
|
alpar@100
|
286 |
struct FindArcSelector {
|
deba@139
|
287 |
typedef typename Graph::Node Node;
|
deba@139
|
288 |
typedef typename Graph::Arc Arc;
|
deba@139
|
289 |
static Arc find(const Graph &g, Node u, Node v, Arc e) {
|
alpar@100
|
290 |
if (e == INVALID) {
|
alpar@100
|
291 |
g.firstOut(e, u);
|
alpar@100
|
292 |
} else {
|
alpar@100
|
293 |
g.nextOut(e);
|
alpar@100
|
294 |
}
|
alpar@100
|
295 |
while (e != INVALID && g.target(e) != v) {
|
alpar@100
|
296 |
g.nextOut(e);
|
alpar@100
|
297 |
}
|
alpar@100
|
298 |
return e;
|
alpar@100
|
299 |
}
|
alpar@100
|
300 |
};
|
alpar@100
|
301 |
|
deba@139
|
302 |
template <typename Graph>
|
alpar@100
|
303 |
struct FindArcSelector<
|
alpar@209
|
304 |
Graph,
|
alpar@209
|
305 |
typename enable_if<typename Graph::FindEdgeTag, void>::type>
|
alpar@100
|
306 |
{
|
deba@139
|
307 |
typedef typename Graph::Node Node;
|
deba@139
|
308 |
typedef typename Graph::Arc Arc;
|
deba@139
|
309 |
static Arc find(const Graph &g, Node u, Node v, Arc prev) {
|
alpar@100
|
310 |
return g.findArc(u, v, prev);
|
alpar@100
|
311 |
}
|
alpar@209
|
312 |
};
|
alpar@100
|
313 |
}
|
alpar@100
|
314 |
|
deba@139
|
315 |
/// \brief Finds an arc between two nodes of a graph.
|
alpar@100
|
316 |
///
|
deba@139
|
317 |
/// Finds an arc from node \c u to node \c v in graph \c g.
|
alpar@100
|
318 |
///
|
alpar@100
|
319 |
/// If \c prev is \ref INVALID (this is the default value), then
|
alpar@100
|
320 |
/// it finds the first arc from \c u to \c v. Otherwise it looks for
|
alpar@100
|
321 |
/// the next arc from \c u to \c v after \c prev.
|
alpar@100
|
322 |
/// \return The found arc or \ref INVALID if there is no such an arc.
|
alpar@100
|
323 |
///
|
alpar@100
|
324 |
/// Thus you can iterate through each arc from \c u to \c v as it follows.
|
alpar@100
|
325 |
///\code
|
alpar@100
|
326 |
/// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) {
|
alpar@100
|
327 |
/// ...
|
alpar@100
|
328 |
/// }
|
alpar@100
|
329 |
///\endcode
|
alpar@100
|
330 |
///
|
alpar@100
|
331 |
///\sa ArcLookUp
|
alpar@100
|
332 |
///\sa AllArcLookUp
|
alpar@100
|
333 |
///\sa DynArcLookUp
|
alpar@100
|
334 |
///\sa ConArcIt
|
deba@139
|
335 |
template <typename Graph>
|
alpar@209
|
336 |
inline typename Graph::Arc
|
deba@139
|
337 |
findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
|
deba@139
|
338 |
typename Graph::Arc prev = INVALID) {
|
deba@139
|
339 |
return _graph_utils_bits::FindArcSelector<Graph>::find(g, u, v, prev);
|
alpar@100
|
340 |
}
|
alpar@100
|
341 |
|
alpar@100
|
342 |
/// \brief Iterator for iterating on arcs connected the same nodes.
|
alpar@100
|
343 |
///
|
alpar@209
|
344 |
/// Iterator for iterating on arcs connected the same nodes. It is
|
alpar@100
|
345 |
/// higher level interface for the findArc() function. You can
|
alpar@100
|
346 |
/// use it the following way:
|
alpar@100
|
347 |
///\code
|
deba@139
|
348 |
/// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
|
alpar@100
|
349 |
/// ...
|
alpar@100
|
350 |
/// }
|
alpar@100
|
351 |
///\endcode
|
alpar@209
|
352 |
///
|
alpar@100
|
353 |
///\sa findArc()
|
alpar@100
|
354 |
///\sa ArcLookUp
|
alpar@100
|
355 |
///\sa AllArcLookUp
|
alpar@100
|
356 |
///\sa DynArcLookUp
|
deba@139
|
357 |
template <typename _Graph>
|
deba@139
|
358 |
class ConArcIt : public _Graph::Arc {
|
alpar@100
|
359 |
public:
|
alpar@100
|
360 |
|
deba@139
|
361 |
typedef _Graph Graph;
|
deba@139
|
362 |
typedef typename Graph::Arc Parent;
|
alpar@100
|
363 |
|
deba@139
|
364 |
typedef typename Graph::Arc Arc;
|
deba@139
|
365 |
typedef typename Graph::Node Node;
|
alpar@100
|
366 |
|
alpar@100
|
367 |
/// \brief Constructor.
|
alpar@100
|
368 |
///
|
alpar@100
|
369 |
/// Construct a new ConArcIt iterating on the arcs which
|
alpar@100
|
370 |
/// connects the \c u and \c v node.
|
deba@139
|
371 |
ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
|
deba@139
|
372 |
Parent::operator=(findArc(_graph, u, v));
|
alpar@100
|
373 |
}
|
alpar@100
|
374 |
|
alpar@100
|
375 |
/// \brief Constructor.
|
alpar@100
|
376 |
///
|
alpar@209
|
377 |
/// Construct a new ConArcIt which continues the iterating from
|
alpar@100
|
378 |
/// the \c e arc.
|
deba@139
|
379 |
ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
|
alpar@209
|
380 |
|
alpar@100
|
381 |
/// \brief Increment operator.
|
alpar@100
|
382 |
///
|
alpar@100
|
383 |
/// It increments the iterator and gives back the next arc.
|
alpar@100
|
384 |
ConArcIt& operator++() {
|
alpar@209
|
385 |
Parent::operator=(findArc(_graph, _graph.source(*this),
|
alpar@209
|
386 |
_graph.target(*this), *this));
|
alpar@100
|
387 |
return *this;
|
alpar@100
|
388 |
}
|
alpar@100
|
389 |
private:
|
deba@139
|
390 |
const Graph& _graph;
|
alpar@100
|
391 |
};
|
alpar@100
|
392 |
|
deba@139
|
393 |
namespace _graph_utils_bits {
|
alpar@209
|
394 |
|
deba@139
|
395 |
template <typename Graph, typename Enable = void>
|
alpar@100
|
396 |
struct FindEdgeSelector {
|
deba@139
|
397 |
typedef typename Graph::Node Node;
|
deba@139
|
398 |
typedef typename Graph::Edge Edge;
|
deba@139
|
399 |
static Edge find(const Graph &g, Node u, Node v, Edge e) {
|
alpar@100
|
400 |
bool b;
|
alpar@100
|
401 |
if (u != v) {
|
alpar@100
|
402 |
if (e == INVALID) {
|
alpar@100
|
403 |
g.firstInc(e, b, u);
|
alpar@100
|
404 |
} else {
|
kpeter@169
|
405 |
b = g.u(e) == u;
|
alpar@100
|
406 |
g.nextInc(e, b);
|
alpar@100
|
407 |
}
|
kpeter@169
|
408 |
while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
|
alpar@100
|
409 |
g.nextInc(e, b);
|
alpar@100
|
410 |
}
|
alpar@100
|
411 |
} else {
|
alpar@100
|
412 |
if (e == INVALID) {
|
alpar@100
|
413 |
g.firstInc(e, b, u);
|
alpar@100
|
414 |
} else {
|
alpar@100
|
415 |
b = true;
|
alpar@100
|
416 |
g.nextInc(e, b);
|
alpar@100
|
417 |
}
|
kpeter@169
|
418 |
while (e != INVALID && (!b || g.v(e) != v)) {
|
alpar@100
|
419 |
g.nextInc(e, b);
|
alpar@100
|
420 |
}
|
alpar@100
|
421 |
}
|
alpar@100
|
422 |
return e;
|
alpar@100
|
423 |
}
|
alpar@100
|
424 |
};
|
alpar@100
|
425 |
|
deba@139
|
426 |
template <typename Graph>
|
alpar@100
|
427 |
struct FindEdgeSelector<
|
alpar@209
|
428 |
Graph,
|
alpar@209
|
429 |
typename enable_if<typename Graph::FindEdgeTag, void>::type>
|
alpar@100
|
430 |
{
|
deba@139
|
431 |
typedef typename Graph::Node Node;
|
deba@139
|
432 |
typedef typename Graph::Edge Edge;
|
deba@139
|
433 |
static Edge find(const Graph &g, Node u, Node v, Edge prev) {
|
alpar@100
|
434 |
return g.findEdge(u, v, prev);
|
alpar@100
|
435 |
}
|
alpar@209
|
436 |
};
|
alpar@100
|
437 |
}
|
alpar@100
|
438 |
|
deba@139
|
439 |
/// \brief Finds an edge between two nodes of a graph.
|
alpar@100
|
440 |
///
|
deba@139
|
441 |
/// Finds an edge from node \c u to node \c v in graph \c g.
|
deba@139
|
442 |
/// If the node \c u and node \c v is equal then each loop edge
|
deba@139
|
443 |
/// will be enumerated once.
|
alpar@100
|
444 |
///
|
alpar@100
|
445 |
/// If \c prev is \ref INVALID (this is the default value), then
|
alpar@100
|
446 |
/// it finds the first arc from \c u to \c v. Otherwise it looks for
|
alpar@100
|
447 |
/// the next arc from \c u to \c v after \c prev.
|
alpar@100
|
448 |
/// \return The found arc or \ref INVALID if there is no such an arc.
|
alpar@100
|
449 |
///
|
alpar@100
|
450 |
/// Thus you can iterate through each arc from \c u to \c v as it follows.
|
alpar@100
|
451 |
///\code
|
alpar@209
|
452 |
/// for(Edge e = findEdge(g,u,v); e != INVALID;
|
alpar@100
|
453 |
/// e = findEdge(g,u,v,e)) {
|
alpar@100
|
454 |
/// ...
|
alpar@100
|
455 |
/// }
|
alpar@100
|
456 |
///\endcode
|
alpar@100
|
457 |
///
|
kpeter@169
|
458 |
///\sa ConEdgeIt
|
alpar@100
|
459 |
|
deba@139
|
460 |
template <typename Graph>
|
alpar@209
|
461 |
inline typename Graph::Edge
|
deba@139
|
462 |
findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
|
deba@139
|
463 |
typename Graph::Edge p = INVALID) {
|
deba@139
|
464 |
return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
|
alpar@100
|
465 |
}
|
alpar@100
|
466 |
|
alpar@100
|
467 |
/// \brief Iterator for iterating on edges connected the same nodes.
|
alpar@100
|
468 |
///
|
alpar@209
|
469 |
/// Iterator for iterating on edges connected the same nodes. It is
|
alpar@100
|
470 |
/// higher level interface for the findEdge() function. You can
|
alpar@100
|
471 |
/// use it the following way:
|
alpar@100
|
472 |
///\code
|
deba@139
|
473 |
/// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {
|
alpar@100
|
474 |
/// ...
|
alpar@100
|
475 |
/// }
|
alpar@100
|
476 |
///\endcode
|
alpar@100
|
477 |
///
|
alpar@100
|
478 |
///\sa findEdge()
|
deba@139
|
479 |
template <typename _Graph>
|
deba@139
|
480 |
class ConEdgeIt : public _Graph::Edge {
|
alpar@100
|
481 |
public:
|
alpar@100
|
482 |
|
deba@139
|
483 |
typedef _Graph Graph;
|
deba@139
|
484 |
typedef typename Graph::Edge Parent;
|
alpar@100
|
485 |
|
deba@139
|
486 |
typedef typename Graph::Edge Edge;
|
deba@139
|
487 |
typedef typename Graph::Node Node;
|
alpar@100
|
488 |
|
alpar@100
|
489 |
/// \brief Constructor.
|
alpar@100
|
490 |
///
|
deba@139
|
491 |
/// Construct a new ConEdgeIt iterating on the edges which
|
alpar@100
|
492 |
/// connects the \c u and \c v node.
|
deba@139
|
493 |
ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
|
deba@139
|
494 |
Parent::operator=(findEdge(_graph, u, v));
|
alpar@100
|
495 |
}
|
alpar@100
|
496 |
|
alpar@100
|
497 |
/// \brief Constructor.
|
alpar@100
|
498 |
///
|
alpar@209
|
499 |
/// Construct a new ConEdgeIt which continues the iterating from
|
deba@139
|
500 |
/// the \c e edge.
|
deba@139
|
501 |
ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
|
alpar@209
|
502 |
|
alpar@100
|
503 |
/// \brief Increment operator.
|
alpar@100
|
504 |
///
|
deba@139
|
505 |
/// It increments the iterator and gives back the next edge.
|
alpar@100
|
506 |
ConEdgeIt& operator++() {
|
alpar@209
|
507 |
Parent::operator=(findEdge(_graph, _graph.u(*this),
|
alpar@209
|
508 |
_graph.v(*this), *this));
|
alpar@100
|
509 |
return *this;
|
alpar@100
|
510 |
}
|
alpar@100
|
511 |
private:
|
deba@139
|
512 |
const Graph& _graph;
|
alpar@100
|
513 |
};
|
alpar@100
|
514 |
|
deba@139
|
515 |
namespace _graph_utils_bits {
|
alpar@100
|
516 |
|
alpar@100
|
517 |
template <typename Digraph, typename Item, typename RefMap>
|
alpar@100
|
518 |
class MapCopyBase {
|
alpar@100
|
519 |
public:
|
alpar@100
|
520 |
virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
|
alpar@209
|
521 |
|
alpar@100
|
522 |
virtual ~MapCopyBase() {}
|
alpar@100
|
523 |
};
|
alpar@100
|
524 |
|
alpar@209
|
525 |
template <typename Digraph, typename Item, typename RefMap,
|
alpar@100
|
526 |
typename ToMap, typename FromMap>
|
alpar@100
|
527 |
class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
alpar@100
|
528 |
public:
|
alpar@100
|
529 |
|
alpar@209
|
530 |
MapCopy(ToMap& tmap, const FromMap& map)
|
alpar@100
|
531 |
: _tmap(tmap), _map(map) {}
|
alpar@209
|
532 |
|
alpar@100
|
533 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
alpar@100
|
534 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
alpar@100
|
535 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
alpar@100
|
536 |
_tmap.set(refMap[it], _map[it]);
|
alpar@100
|
537 |
}
|
alpar@100
|
538 |
}
|
alpar@100
|
539 |
|
alpar@100
|
540 |
private:
|
alpar@100
|
541 |
ToMap& _tmap;
|
alpar@100
|
542 |
const FromMap& _map;
|
alpar@100
|
543 |
};
|
alpar@100
|
544 |
|
alpar@100
|
545 |
template <typename Digraph, typename Item, typename RefMap, typename It>
|
alpar@100
|
546 |
class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
alpar@100
|
547 |
public:
|
alpar@100
|
548 |
|
alpar@100
|
549 |
ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}
|
alpar@209
|
550 |
|
alpar@100
|
551 |
virtual void copy(const Digraph&, const RefMap& refMap) {
|
alpar@100
|
552 |
_it = refMap[_item];
|
alpar@100
|
553 |
}
|
alpar@100
|
554 |
|
alpar@100
|
555 |
private:
|
alpar@100
|
556 |
It& _it;
|
alpar@100
|
557 |
Item _item;
|
alpar@100
|
558 |
};
|
alpar@100
|
559 |
|
alpar@100
|
560 |
template <typename Digraph, typename Item, typename RefMap, typename Ref>
|
alpar@100
|
561 |
class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
alpar@100
|
562 |
public:
|
alpar@100
|
563 |
|
alpar@100
|
564 |
RefCopy(Ref& map) : _map(map) {}
|
alpar@209
|
565 |
|
alpar@100
|
566 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
alpar@100
|
567 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
alpar@100
|
568 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
alpar@100
|
569 |
_map.set(it, refMap[it]);
|
alpar@100
|
570 |
}
|
alpar@100
|
571 |
}
|
alpar@100
|
572 |
|
alpar@100
|
573 |
private:
|
alpar@100
|
574 |
Ref& _map;
|
alpar@100
|
575 |
};
|
alpar@100
|
576 |
|
alpar@209
|
577 |
template <typename Digraph, typename Item, typename RefMap,
|
alpar@100
|
578 |
typename CrossRef>
|
alpar@100
|
579 |
class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
alpar@100
|
580 |
public:
|
alpar@100
|
581 |
|
alpar@100
|
582 |
CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
|
alpar@209
|
583 |
|
alpar@100
|
584 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
alpar@100
|
585 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
alpar@100
|
586 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
alpar@100
|
587 |
_cmap.set(refMap[it], it);
|
alpar@100
|
588 |
}
|
alpar@100
|
589 |
}
|
alpar@100
|
590 |
|
alpar@100
|
591 |
private:
|
alpar@100
|
592 |
CrossRef& _cmap;
|
alpar@100
|
593 |
};
|
alpar@100
|
594 |
|
alpar@100
|
595 |
template <typename Digraph, typename Enable = void>
|
alpar@100
|
596 |
struct DigraphCopySelector {
|
alpar@100
|
597 |
template <typename From, typename NodeRefMap, typename ArcRefMap>
|
alpar@100
|
598 |
static void copy(Digraph &to, const From& from,
|
alpar@100
|
599 |
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
|
alpar@100
|
600 |
for (typename From::NodeIt it(from); it != INVALID; ++it) {
|
alpar@100
|
601 |
nodeRefMap[it] = to.addNode();
|
alpar@100
|
602 |
}
|
alpar@100
|
603 |
for (typename From::ArcIt it(from); it != INVALID; ++it) {
|
alpar@209
|
604 |
arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
|
alpar@209
|
605 |
nodeRefMap[from.target(it)]);
|
alpar@100
|
606 |
}
|
alpar@100
|
607 |
}
|
alpar@100
|
608 |
};
|
alpar@100
|
609 |
|
alpar@100
|
610 |
template <typename Digraph>
|
alpar@100
|
611 |
struct DigraphCopySelector<
|
alpar@209
|
612 |
Digraph,
|
alpar@209
|
613 |
typename enable_if<typename Digraph::BuildTag, void>::type>
|
alpar@100
|
614 |
{
|
alpar@100
|
615 |
template <typename From, typename NodeRefMap, typename ArcRefMap>
|
alpar@100
|
616 |
static void copy(Digraph &to, const From& from,
|
alpar@100
|
617 |
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
|
alpar@100
|
618 |
to.build(from, nodeRefMap, arcRefMap);
|
alpar@100
|
619 |
}
|
alpar@100
|
620 |
};
|
alpar@100
|
621 |
|
alpar@100
|
622 |
template <typename Graph, typename Enable = void>
|
alpar@100
|
623 |
struct GraphCopySelector {
|
alpar@100
|
624 |
template <typename From, typename NodeRefMap, typename EdgeRefMap>
|
alpar@100
|
625 |
static void copy(Graph &to, const From& from,
|
alpar@100
|
626 |
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
|
alpar@100
|
627 |
for (typename From::NodeIt it(from); it != INVALID; ++it) {
|
alpar@100
|
628 |
nodeRefMap[it] = to.addNode();
|
alpar@100
|
629 |
}
|
alpar@100
|
630 |
for (typename From::EdgeIt it(from); it != INVALID; ++it) {
|
alpar@209
|
631 |
edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
|
alpar@209
|
632 |
nodeRefMap[from.v(it)]);
|
alpar@100
|
633 |
}
|
alpar@100
|
634 |
}
|
alpar@100
|
635 |
};
|
alpar@100
|
636 |
|
alpar@100
|
637 |
template <typename Graph>
|
alpar@100
|
638 |
struct GraphCopySelector<
|
alpar@209
|
639 |
Graph,
|
alpar@209
|
640 |
typename enable_if<typename Graph::BuildTag, void>::type>
|
alpar@100
|
641 |
{
|
alpar@100
|
642 |
template <typename From, typename NodeRefMap, typename EdgeRefMap>
|
alpar@100
|
643 |
static void copy(Graph &to, const From& from,
|
alpar@100
|
644 |
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
|
alpar@100
|
645 |
to.build(from, nodeRefMap, edgeRefMap);
|
alpar@100
|
646 |
}
|
alpar@100
|
647 |
};
|
alpar@100
|
648 |
|
alpar@100
|
649 |
}
|
alpar@100
|
650 |
|
alpar@100
|
651 |
/// \brief Class to copy a digraph.
|
alpar@100
|
652 |
///
|
alpar@100
|
653 |
/// Class to copy a digraph to another digraph (duplicate a digraph). The
|
alpar@100
|
654 |
/// simplest way of using it is through the \c copyDigraph() function.
|
deba@139
|
655 |
///
|
deba@139
|
656 |
/// This class not just make a copy of a graph, but it can create
|
deba@139
|
657 |
/// references and cross references between the nodes and arcs of
|
deba@139
|
658 |
/// the two graphs, it can copy maps for use with the newly created
|
deba@139
|
659 |
/// graph and copy nodes and arcs.
|
deba@139
|
660 |
///
|
deba@139
|
661 |
/// To make a copy from a graph, first an instance of DigraphCopy
|
deba@139
|
662 |
/// should be created, then the data belongs to the graph should
|
deba@139
|
663 |
/// assigned to copy. In the end, the \c run() member should be
|
deba@139
|
664 |
/// called.
|
deba@139
|
665 |
///
|
deba@139
|
666 |
/// The next code copies a graph with several data:
|
deba@139
|
667 |
///\code
|
deba@139
|
668 |
/// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
|
deba@139
|
669 |
/// // create a reference for the nodes
|
deba@139
|
670 |
/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
|
deba@139
|
671 |
/// dc.nodeRef(nr);
|
deba@139
|
672 |
/// // create a cross reference (inverse) for the arcs
|
deba@139
|
673 |
/// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
|
deba@139
|
674 |
/// dc.arcCrossRef(acr);
|
deba@139
|
675 |
/// // copy an arc map
|
deba@139
|
676 |
/// OrigGraph::ArcMap<double> oamap(orig_graph);
|
deba@139
|
677 |
/// NewGraph::ArcMap<double> namap(new_graph);
|
deba@139
|
678 |
/// dc.arcMap(namap, oamap);
|
deba@139
|
679 |
/// // copy a node
|
deba@139
|
680 |
/// OrigGraph::Node on;
|
deba@139
|
681 |
/// NewGraph::Node nn;
|
deba@139
|
682 |
/// dc.node(nn, on);
|
deba@139
|
683 |
/// // Executions of copy
|
deba@139
|
684 |
/// dc.run();
|
deba@139
|
685 |
///\endcode
|
alpar@100
|
686 |
template <typename To, typename From>
|
alpar@100
|
687 |
class DigraphCopy {
|
alpar@100
|
688 |
private:
|
alpar@100
|
689 |
|
alpar@100
|
690 |
typedef typename From::Node Node;
|
alpar@100
|
691 |
typedef typename From::NodeIt NodeIt;
|
alpar@100
|
692 |
typedef typename From::Arc Arc;
|
alpar@100
|
693 |
typedef typename From::ArcIt ArcIt;
|
alpar@100
|
694 |
|
alpar@100
|
695 |
typedef typename To::Node TNode;
|
alpar@100
|
696 |
typedef typename To::Arc TArc;
|
alpar@100
|
697 |
|
alpar@100
|
698 |
typedef typename From::template NodeMap<TNode> NodeRefMap;
|
alpar@100
|
699 |
typedef typename From::template ArcMap<TArc> ArcRefMap;
|
alpar@209
|
700 |
|
alpar@209
|
701 |
|
alpar@209
|
702 |
public:
|
alpar@100
|
703 |
|
alpar@100
|
704 |
|
alpar@100
|
705 |
/// \brief Constructor for the DigraphCopy.
|
alpar@100
|
706 |
///
|
alpar@100
|
707 |
/// It copies the content of the \c _from digraph into the
|
alpar@100
|
708 |
/// \c _to digraph.
|
alpar@209
|
709 |
DigraphCopy(To& to, const From& from)
|
deba@139
|
710 |
: _from(from), _to(to) {}
|
alpar@100
|
711 |
|
alpar@100
|
712 |
/// \brief Destructor of the DigraphCopy
|
alpar@100
|
713 |
///
|
alpar@100
|
714 |
/// Destructor of the DigraphCopy
|
alpar@100
|
715 |
~DigraphCopy() {
|
deba@139
|
716 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@139
|
717 |
delete _node_maps[i];
|
alpar@100
|
718 |
}
|
deba@139
|
719 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@139
|
720 |
delete _arc_maps[i];
|
alpar@100
|
721 |
}
|
alpar@100
|
722 |
|
alpar@100
|
723 |
}
|
alpar@100
|
724 |
|
alpar@100
|
725 |
/// \brief Copies the node references into the given map.
|
alpar@100
|
726 |
///
|
deba@139
|
727 |
/// Copies the node references into the given map. The parameter
|
deba@139
|
728 |
/// should be a map, which key type is the Node type of the source
|
deba@139
|
729 |
/// graph, while the value type is the Node type of the
|
deba@139
|
730 |
/// destination graph.
|
alpar@100
|
731 |
template <typename NodeRef>
|
alpar@100
|
732 |
DigraphCopy& nodeRef(NodeRef& map) {
|
alpar@209
|
733 |
_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
|
alpar@209
|
734 |
NodeRefMap, NodeRef>(map));
|
alpar@100
|
735 |
return *this;
|
alpar@100
|
736 |
}
|
alpar@100
|
737 |
|
alpar@100
|
738 |
/// \brief Copies the node cross references into the given map.
|
alpar@100
|
739 |
///
|
alpar@100
|
740 |
/// Copies the node cross references (reverse references) into
|
deba@139
|
741 |
/// the given map. The parameter should be a map, which key type
|
deba@139
|
742 |
/// is the Node type of the destination graph, while the value type is
|
deba@139
|
743 |
/// the Node type of the source graph.
|
alpar@100
|
744 |
template <typename NodeCrossRef>
|
alpar@100
|
745 |
DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
|
deba@139
|
746 |
_node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
|
alpar@209
|
747 |
NodeRefMap, NodeCrossRef>(map));
|
alpar@100
|
748 |
return *this;
|
alpar@100
|
749 |
}
|
alpar@100
|
750 |
|
alpar@100
|
751 |
/// \brief Make copy of the given map.
|
alpar@100
|
752 |
///
|
deba@139
|
753 |
/// Makes copy of the given map for the newly created digraph.
|
deba@139
|
754 |
/// The new map's key type is the destination graph's node type,
|
deba@139
|
755 |
/// and the copied map's key type is the source graph's node type.
|
alpar@100
|
756 |
template <typename ToMap, typename FromMap>
|
alpar@100
|
757 |
DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
|
alpar@209
|
758 |
_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
|
alpar@209
|
759 |
NodeRefMap, ToMap, FromMap>(tmap, map));
|
alpar@100
|
760 |
return *this;
|
alpar@100
|
761 |
}
|
alpar@100
|
762 |
|
alpar@100
|
763 |
/// \brief Make a copy of the given node.
|
alpar@100
|
764 |
///
|
alpar@100
|
765 |
/// Make a copy of the given node.
|
alpar@100
|
766 |
DigraphCopy& node(TNode& tnode, const Node& snode) {
|
alpar@209
|
767 |
_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
|
alpar@209
|
768 |
NodeRefMap, TNode>(tnode, snode));
|
alpar@100
|
769 |
return *this;
|
alpar@100
|
770 |
}
|
alpar@100
|
771 |
|
alpar@100
|
772 |
/// \brief Copies the arc references into the given map.
|
alpar@100
|
773 |
///
|
alpar@100
|
774 |
/// Copies the arc references into the given map.
|
alpar@100
|
775 |
template <typename ArcRef>
|
alpar@100
|
776 |
DigraphCopy& arcRef(ArcRef& map) {
|
alpar@209
|
777 |
_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
|
alpar@209
|
778 |
ArcRefMap, ArcRef>(map));
|
alpar@100
|
779 |
return *this;
|
alpar@100
|
780 |
}
|
alpar@100
|
781 |
|
alpar@100
|
782 |
/// \brief Copies the arc cross references into the given map.
|
alpar@100
|
783 |
///
|
alpar@100
|
784 |
/// Copies the arc cross references (reverse references) into
|
alpar@100
|
785 |
/// the given map.
|
alpar@100
|
786 |
template <typename ArcCrossRef>
|
alpar@100
|
787 |
DigraphCopy& arcCrossRef(ArcCrossRef& map) {
|
deba@139
|
788 |
_arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
|
alpar@209
|
789 |
ArcRefMap, ArcCrossRef>(map));
|
alpar@100
|
790 |
return *this;
|
alpar@100
|
791 |
}
|
alpar@100
|
792 |
|
alpar@100
|
793 |
/// \brief Make copy of the given map.
|
alpar@100
|
794 |
///
|
alpar@209
|
795 |
/// Makes copy of the given map for the newly created digraph.
|
alpar@100
|
796 |
/// The new map's key type is the to digraph's arc type,
|
alpar@100
|
797 |
/// and the copied map's key type is the from digraph's arc
|
alpar@209
|
798 |
/// type.
|
alpar@100
|
799 |
template <typename ToMap, typename FromMap>
|
alpar@100
|
800 |
DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
|
alpar@209
|
801 |
_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
|
alpar@209
|
802 |
ArcRefMap, ToMap, FromMap>(tmap, map));
|
alpar@100
|
803 |
return *this;
|
alpar@100
|
804 |
}
|
alpar@100
|
805 |
|
alpar@100
|
806 |
/// \brief Make a copy of the given arc.
|
alpar@100
|
807 |
///
|
alpar@100
|
808 |
/// Make a copy of the given arc.
|
alpar@100
|
809 |
DigraphCopy& arc(TArc& tarc, const Arc& sarc) {
|
alpar@209
|
810 |
_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
|
alpar@209
|
811 |
ArcRefMap, TArc>(tarc, sarc));
|
alpar@100
|
812 |
return *this;
|
alpar@100
|
813 |
}
|
alpar@100
|
814 |
|
alpar@100
|
815 |
/// \brief Executes the copies.
|
alpar@100
|
816 |
///
|
alpar@100
|
817 |
/// Executes the copies.
|
alpar@100
|
818 |
void run() {
|
deba@139
|
819 |
NodeRefMap nodeRefMap(_from);
|
deba@139
|
820 |
ArcRefMap arcRefMap(_from);
|
deba@139
|
821 |
_graph_utils_bits::DigraphCopySelector<To>::
|
deba@139
|
822 |
copy(_to, _from, nodeRefMap, arcRefMap);
|
deba@139
|
823 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@139
|
824 |
_node_maps[i]->copy(_from, nodeRefMap);
|
alpar@100
|
825 |
}
|
deba@139
|
826 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@139
|
827 |
_arc_maps[i]->copy(_from, arcRefMap);
|
alpar@209
|
828 |
}
|
alpar@100
|
829 |
}
|
alpar@100
|
830 |
|
alpar@100
|
831 |
protected:
|
alpar@100
|
832 |
|
alpar@100
|
833 |
|
deba@139
|
834 |
const From& _from;
|
deba@139
|
835 |
To& _to;
|
alpar@100
|
836 |
|
alpar@209
|
837 |
std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
|
deba@139
|
838 |
_node_maps;
|
alpar@100
|
839 |
|
alpar@209
|
840 |
std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
|
deba@139
|
841 |
_arc_maps;
|
alpar@100
|
842 |
|
alpar@100
|
843 |
};
|
alpar@100
|
844 |
|
alpar@100
|
845 |
/// \brief Copy a digraph to another digraph.
|
alpar@100
|
846 |
///
|
deba@139
|
847 |
/// Copy a digraph to another digraph. The complete usage of the
|
deba@139
|
848 |
/// function is detailed in the DigraphCopy class, but a short
|
deba@139
|
849 |
/// example shows a basic work:
|
alpar@100
|
850 |
///\code
|
alpar@100
|
851 |
/// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
|
alpar@100
|
852 |
///\endcode
|
alpar@209
|
853 |
///
|
alpar@100
|
854 |
/// After the copy the \c nr map will contain the mapping from the
|
alpar@100
|
855 |
/// nodes of the \c from digraph to the nodes of the \c to digraph and
|
alpar@100
|
856 |
/// \c ecr will contain the mapping from the arcs of the \c to digraph
|
alpar@100
|
857 |
/// to the arcs of the \c from digraph.
|
alpar@100
|
858 |
///
|
alpar@209
|
859 |
/// \see DigraphCopy
|
alpar@100
|
860 |
template <typename To, typename From>
|
alpar@100
|
861 |
DigraphCopy<To, From> copyDigraph(To& to, const From& from) {
|
alpar@100
|
862 |
return DigraphCopy<To, From>(to, from);
|
alpar@100
|
863 |
}
|
alpar@100
|
864 |
|
deba@139
|
865 |
/// \brief Class to copy a graph.
|
alpar@100
|
866 |
///
|
deba@139
|
867 |
/// Class to copy a graph to another graph (duplicate a graph). The
|
deba@139
|
868 |
/// simplest way of using it is through the \c copyGraph() function.
|
deba@139
|
869 |
///
|
deba@139
|
870 |
/// This class not just make a copy of a graph, but it can create
|
deba@139
|
871 |
/// references and cross references between the nodes, edges and arcs of
|
deba@139
|
872 |
/// the two graphs, it can copy maps for use with the newly created
|
deba@139
|
873 |
/// graph and copy nodes, edges and arcs.
|
deba@139
|
874 |
///
|
deba@139
|
875 |
/// To make a copy from a graph, first an instance of GraphCopy
|
deba@139
|
876 |
/// should be created, then the data belongs to the graph should
|
deba@139
|
877 |
/// assigned to copy. In the end, the \c run() member should be
|
deba@139
|
878 |
/// called.
|
deba@139
|
879 |
///
|
deba@139
|
880 |
/// The next code copies a graph with several data:
|
deba@139
|
881 |
///\code
|
deba@139
|
882 |
/// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph);
|
deba@139
|
883 |
/// // create a reference for the nodes
|
deba@139
|
884 |
/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
|
deba@139
|
885 |
/// dc.nodeRef(nr);
|
deba@139
|
886 |
/// // create a cross reference (inverse) for the edges
|
deba@139
|
887 |
/// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph);
|
deba@139
|
888 |
/// dc.edgeCrossRef(ecr);
|
deba@139
|
889 |
/// // copy an arc map
|
deba@139
|
890 |
/// OrigGraph::ArcMap<double> oamap(orig_graph);
|
deba@139
|
891 |
/// NewGraph::ArcMap<double> namap(new_graph);
|
deba@139
|
892 |
/// dc.arcMap(namap, oamap);
|
deba@139
|
893 |
/// // copy a node
|
deba@139
|
894 |
/// OrigGraph::Node on;
|
deba@139
|
895 |
/// NewGraph::Node nn;
|
deba@139
|
896 |
/// dc.node(nn, on);
|
deba@139
|
897 |
/// // Executions of copy
|
deba@139
|
898 |
/// dc.run();
|
deba@139
|
899 |
///\endcode
|
alpar@100
|
900 |
template <typename To, typename From>
|
alpar@100
|
901 |
class GraphCopy {
|
alpar@100
|
902 |
private:
|
alpar@100
|
903 |
|
alpar@100
|
904 |
typedef typename From::Node Node;
|
alpar@100
|
905 |
typedef typename From::NodeIt NodeIt;
|
alpar@100
|
906 |
typedef typename From::Arc Arc;
|
alpar@100
|
907 |
typedef typename From::ArcIt ArcIt;
|
alpar@100
|
908 |
typedef typename From::Edge Edge;
|
alpar@100
|
909 |
typedef typename From::EdgeIt EdgeIt;
|
alpar@100
|
910 |
|
alpar@100
|
911 |
typedef typename To::Node TNode;
|
alpar@100
|
912 |
typedef typename To::Arc TArc;
|
alpar@100
|
913 |
typedef typename To::Edge TEdge;
|
alpar@100
|
914 |
|
alpar@100
|
915 |
typedef typename From::template NodeMap<TNode> NodeRefMap;
|
alpar@100
|
916 |
typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
|
alpar@100
|
917 |
|
alpar@100
|
918 |
struct ArcRefMap {
|
deba@139
|
919 |
ArcRefMap(const To& to, const From& from,
|
alpar@209
|
920 |
const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
|
alpar@209
|
921 |
: _to(to), _from(from),
|
deba@139
|
922 |
_edge_ref(edge_ref), _node_ref(node_ref) {}
|
alpar@100
|
923 |
|
alpar@100
|
924 |
typedef typename From::Arc Key;
|
alpar@100
|
925 |
typedef typename To::Arc Value;
|
alpar@100
|
926 |
|
alpar@100
|
927 |
Value operator[](const Key& key) const {
|
deba@199
|
928 |
bool forward = _from.u(key) != _from.v(key) ?
|
alpar@209
|
929 |
_node_ref[_from.source(key)] ==
|
alpar@209
|
930 |
_to.source(_to.direct(_edge_ref[key], true)) :
|
alpar@209
|
931 |
_from.direction(key);
|
alpar@209
|
932 |
return _to.direct(_edge_ref[key], forward);
|
alpar@100
|
933 |
}
|
alpar@209
|
934 |
|
deba@139
|
935 |
const To& _to;
|
deba@139
|
936 |
const From& _from;
|
deba@139
|
937 |
const EdgeRefMap& _edge_ref;
|
deba@139
|
938 |
const NodeRefMap& _node_ref;
|
alpar@100
|
939 |
};
|
alpar@100
|
940 |
|
alpar@209
|
941 |
|
alpar@209
|
942 |
public:
|
alpar@100
|
943 |
|
alpar@100
|
944 |
|
deba@139
|
945 |
/// \brief Constructor for the GraphCopy.
|
alpar@100
|
946 |
///
|
deba@139
|
947 |
/// It copies the content of the \c _from graph into the
|
deba@139
|
948 |
/// \c _to graph.
|
alpar@209
|
949 |
GraphCopy(To& to, const From& from)
|
deba@139
|
950 |
: _from(from), _to(to) {}
|
alpar@100
|
951 |
|
deba@139
|
952 |
/// \brief Destructor of the GraphCopy
|
alpar@100
|
953 |
///
|
deba@139
|
954 |
/// Destructor of the GraphCopy
|
alpar@100
|
955 |
~GraphCopy() {
|
deba@139
|
956 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@139
|
957 |
delete _node_maps[i];
|
alpar@100
|
958 |
}
|
deba@139
|
959 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@139
|
960 |
delete _arc_maps[i];
|
alpar@100
|
961 |
}
|
deba@139
|
962 |
for (int i = 0; i < int(_edge_maps.size()); ++i) {
|
deba@139
|
963 |
delete _edge_maps[i];
|
alpar@100
|
964 |
}
|
alpar@100
|
965 |
|
alpar@100
|
966 |
}
|
alpar@100
|
967 |
|
alpar@100
|
968 |
/// \brief Copies the node references into the given map.
|
alpar@100
|
969 |
///
|
alpar@100
|
970 |
/// Copies the node references into the given map.
|
alpar@100
|
971 |
template <typename NodeRef>
|
alpar@100
|
972 |
GraphCopy& nodeRef(NodeRef& map) {
|
alpar@209
|
973 |
_node_maps.push_back(new _graph_utils_bits::RefCopy<From, Node,
|
alpar@209
|
974 |
NodeRefMap, NodeRef>(map));
|
alpar@100
|
975 |
return *this;
|
alpar@100
|
976 |
}
|
alpar@100
|
977 |
|
alpar@100
|
978 |
/// \brief Copies the node cross references into the given map.
|
alpar@100
|
979 |
///
|
alpar@100
|
980 |
/// Copies the node cross references (reverse references) into
|
alpar@100
|
981 |
/// the given map.
|
alpar@100
|
982 |
template <typename NodeCrossRef>
|
alpar@100
|
983 |
GraphCopy& nodeCrossRef(NodeCrossRef& map) {
|
deba@139
|
984 |
_node_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Node,
|
alpar@209
|
985 |
NodeRefMap, NodeCrossRef>(map));
|
alpar@100
|
986 |
return *this;
|
alpar@100
|
987 |
}
|
alpar@100
|
988 |
|
alpar@100
|
989 |
/// \brief Make copy of the given map.
|
alpar@100
|
990 |
///
|
alpar@209
|
991 |
/// Makes copy of the given map for the newly created graph.
|
deba@139
|
992 |
/// The new map's key type is the to graph's node type,
|
deba@139
|
993 |
/// and the copied map's key type is the from graph's node
|
alpar@209
|
994 |
/// type.
|
alpar@100
|
995 |
template <typename ToMap, typename FromMap>
|
alpar@100
|
996 |
GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) {
|
alpar@209
|
997 |
_node_maps.push_back(new _graph_utils_bits::MapCopy<From, Node,
|
alpar@209
|
998 |
NodeRefMap, ToMap, FromMap>(tmap, map));
|
alpar@100
|
999 |
return *this;
|
alpar@100
|
1000 |
}
|
alpar@100
|
1001 |
|
alpar@100
|
1002 |
/// \brief Make a copy of the given node.
|
alpar@100
|
1003 |
///
|
alpar@100
|
1004 |
/// Make a copy of the given node.
|
alpar@100
|
1005 |
GraphCopy& node(TNode& tnode, const Node& snode) {
|
alpar@209
|
1006 |
_node_maps.push_back(new _graph_utils_bits::ItemCopy<From, Node,
|
alpar@209
|
1007 |
NodeRefMap, TNode>(tnode, snode));
|
alpar@100
|
1008 |
return *this;
|
alpar@100
|
1009 |
}
|
alpar@100
|
1010 |
|
alpar@100
|
1011 |
/// \brief Copies the arc references into the given map.
|
alpar@100
|
1012 |
///
|
alpar@100
|
1013 |
/// Copies the arc references into the given map.
|
alpar@100
|
1014 |
template <typename ArcRef>
|
alpar@100
|
1015 |
GraphCopy& arcRef(ArcRef& map) {
|
alpar@209
|
1016 |
_arc_maps.push_back(new _graph_utils_bits::RefCopy<From, Arc,
|
alpar@209
|
1017 |
ArcRefMap, ArcRef>(map));
|
alpar@100
|
1018 |
return *this;
|
alpar@100
|
1019 |
}
|
alpar@100
|
1020 |
|
alpar@100
|
1021 |
/// \brief Copies the arc cross references into the given map.
|
alpar@100
|
1022 |
///
|
alpar@100
|
1023 |
/// Copies the arc cross references (reverse references) into
|
alpar@100
|
1024 |
/// the given map.
|
alpar@100
|
1025 |
template <typename ArcCrossRef>
|
alpar@100
|
1026 |
GraphCopy& arcCrossRef(ArcCrossRef& map) {
|
deba@139
|
1027 |
_arc_maps.push_back(new _graph_utils_bits::CrossRefCopy<From, Arc,
|
alpar@209
|
1028 |
ArcRefMap, ArcCrossRef>(map));
|
alpar@100
|
1029 |
return *this;
|
alpar@100
|
1030 |
}
|
alpar@100
|
1031 |
|
alpar@100
|
1032 |
/// \brief Make copy of the given map.
|
alpar@100
|
1033 |
///
|
alpar@209
|
1034 |
/// Makes copy of the given map for the newly created graph.
|
deba@139
|
1035 |
/// The new map's key type is the to graph's arc type,
|
deba@139
|
1036 |
/// and the copied map's key type is the from graph's arc
|
alpar@209
|
1037 |
/// type.
|
alpar@100
|
1038 |
template <typename ToMap, typename FromMap>
|
alpar@100
|
1039 |
GraphCopy& arcMap(ToMap& tmap, const FromMap& map) {
|
alpar@209
|
1040 |
_arc_maps.push_back(new _graph_utils_bits::MapCopy<From, Arc,
|
alpar@209
|
1041 |
ArcRefMap, ToMap, FromMap>(tmap, map));
|
alpar@100
|
1042 |
return *this;
|
alpar@100
|
1043 |
}
|
alpar@100
|
1044 |
|
alpar@100
|
1045 |
/// \brief Make a copy of the given arc.
|
alpar@100
|
1046 |
///
|
alpar@100
|
1047 |
/// Make a copy of the given arc.
|
alpar@100
|
1048 |
GraphCopy& arc(TArc& tarc, const Arc& sarc) {
|
alpar@209
|
1049 |
_arc_maps.push_back(new _graph_utils_bits::ItemCopy<From, Arc,
|
alpar@209
|
1050 |
ArcRefMap, TArc>(tarc, sarc));
|
alpar@100
|
1051 |
return *this;
|
alpar@100
|
1052 |
}
|
alpar@100
|
1053 |
|
alpar@100
|
1054 |
/// \brief Copies the edge references into the given map.
|
alpar@100
|
1055 |
///
|
alpar@100
|
1056 |
/// Copies the edge references into the given map.
|
alpar@100
|
1057 |
template <typename EdgeRef>
|
alpar@100
|
1058 |
GraphCopy& edgeRef(EdgeRef& map) {
|
alpar@209
|
1059 |
_edge_maps.push_back(new _graph_utils_bits::RefCopy<From, Edge,
|
alpar@209
|
1060 |
EdgeRefMap, EdgeRef>(map));
|
alpar@100
|
1061 |
return *this;
|
alpar@100
|
1062 |
}
|
alpar@100
|
1063 |
|
alpar@100
|
1064 |
/// \brief Copies the edge cross references into the given map.
|
alpar@100
|
1065 |
///
|
alpar@100
|
1066 |
/// Copies the edge cross references (reverse
|
alpar@100
|
1067 |
/// references) into the given map.
|
alpar@100
|
1068 |
template <typename EdgeCrossRef>
|
alpar@100
|
1069 |
GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
|
alpar@209
|
1070 |
_edge_maps.push_back(new _graph_utils_bits::CrossRefCopy<From,
|
alpar@209
|
1071 |
Edge, EdgeRefMap, EdgeCrossRef>(map));
|
alpar@100
|
1072 |
return *this;
|
alpar@100
|
1073 |
}
|
alpar@100
|
1074 |
|
alpar@100
|
1075 |
/// \brief Make copy of the given map.
|
alpar@100
|
1076 |
///
|
alpar@209
|
1077 |
/// Makes copy of the given map for the newly created graph.
|
deba@139
|
1078 |
/// The new map's key type is the to graph's edge type,
|
deba@139
|
1079 |
/// and the copied map's key type is the from graph's edge
|
alpar@209
|
1080 |
/// type.
|
alpar@100
|
1081 |
template <typename ToMap, typename FromMap>
|
alpar@100
|
1082 |
GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) {
|
alpar@209
|
1083 |
_edge_maps.push_back(new _graph_utils_bits::MapCopy<From, Edge,
|
alpar@209
|
1084 |
EdgeRefMap, ToMap, FromMap>(tmap, map));
|
alpar@100
|
1085 |
return *this;
|
alpar@100
|
1086 |
}
|
alpar@100
|
1087 |
|
alpar@100
|
1088 |
/// \brief Make a copy of the given edge.
|
alpar@100
|
1089 |
///
|
alpar@100
|
1090 |
/// Make a copy of the given edge.
|
alpar@100
|
1091 |
GraphCopy& edge(TEdge& tedge, const Edge& sedge) {
|
alpar@209
|
1092 |
_edge_maps.push_back(new _graph_utils_bits::ItemCopy<From, Edge,
|
alpar@209
|
1093 |
EdgeRefMap, TEdge>(tedge, sedge));
|
alpar@100
|
1094 |
return *this;
|
alpar@100
|
1095 |
}
|
alpar@100
|
1096 |
|
alpar@100
|
1097 |
/// \brief Executes the copies.
|
alpar@100
|
1098 |
///
|
alpar@100
|
1099 |
/// Executes the copies.
|
alpar@100
|
1100 |
void run() {
|
deba@139
|
1101 |
NodeRefMap nodeRefMap(_from);
|
deba@139
|
1102 |
EdgeRefMap edgeRefMap(_from);
|
deba@139
|
1103 |
ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap);
|
deba@139
|
1104 |
_graph_utils_bits::GraphCopySelector<To>::
|
deba@139
|
1105 |
copy(_to, _from, nodeRefMap, edgeRefMap);
|
deba@139
|
1106 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@139
|
1107 |
_node_maps[i]->copy(_from, nodeRefMap);
|
alpar@100
|
1108 |
}
|
deba@139
|
1109 |
for (int i = 0; i < int(_edge_maps.size()); ++i) {
|
deba@139
|
1110 |
_edge_maps[i]->copy(_from, edgeRefMap);
|
alpar@100
|
1111 |
}
|
deba@139
|
1112 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@139
|
1113 |
_arc_maps[i]->copy(_from, arcRefMap);
|
alpar@100
|
1114 |
}
|
alpar@100
|
1115 |
}
|
alpar@100
|
1116 |
|
alpar@100
|
1117 |
private:
|
alpar@209
|
1118 |
|
deba@139
|
1119 |
const From& _from;
|
deba@139
|
1120 |
To& _to;
|
alpar@100
|
1121 |
|
alpar@209
|
1122 |
std::vector<_graph_utils_bits::MapCopyBase<From, Node, NodeRefMap>* >
|
deba@139
|
1123 |
_node_maps;
|
alpar@100
|
1124 |
|
alpar@209
|
1125 |
std::vector<_graph_utils_bits::MapCopyBase<From, Arc, ArcRefMap>* >
|
deba@139
|
1126 |
_arc_maps;
|
alpar@100
|
1127 |
|
alpar@209
|
1128 |
std::vector<_graph_utils_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
|
deba@139
|
1129 |
_edge_maps;
|
alpar@100
|
1130 |
|
alpar@100
|
1131 |
};
|
alpar@100
|
1132 |
|
deba@139
|
1133 |
/// \brief Copy a graph to another graph.
|
alpar@100
|
1134 |
///
|
deba@139
|
1135 |
/// Copy a graph to another graph. The complete usage of the
|
deba@139
|
1136 |
/// function is detailed in the GraphCopy class, but a short
|
deba@139
|
1137 |
/// example shows a basic work:
|
alpar@100
|
1138 |
///\code
|
alpar@100
|
1139 |
/// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run();
|
alpar@100
|
1140 |
///\endcode
|
alpar@209
|
1141 |
///
|
alpar@100
|
1142 |
/// After the copy the \c nr map will contain the mapping from the
|
deba@139
|
1143 |
/// nodes of the \c from graph to the nodes of the \c to graph and
|
deba@139
|
1144 |
/// \c ecr will contain the mapping from the arcs of the \c to graph
|
deba@139
|
1145 |
/// to the arcs of the \c from graph.
|
alpar@100
|
1146 |
///
|
alpar@209
|
1147 |
/// \see GraphCopy
|
alpar@100
|
1148 |
template <typename To, typename From>
|
alpar@209
|
1149 |
GraphCopy<To, From>
|
alpar@100
|
1150 |
copyGraph(To& to, const From& from) {
|
alpar@100
|
1151 |
return GraphCopy<To, From>(to, from);
|
alpar@100
|
1152 |
}
|
alpar@100
|
1153 |
|
alpar@100
|
1154 |
/// @}
|
alpar@100
|
1155 |
|
deba@139
|
1156 |
/// \addtogroup graph_maps
|
alpar@100
|
1157 |
/// @{
|
alpar@100
|
1158 |
|
deba@139
|
1159 |
/// Provides an immutable and unique id for each item in the graph.
|
alpar@100
|
1160 |
|
alpar@100
|
1161 |
/// The IdMap class provides a unique and immutable id for each item of the
|
deba@139
|
1162 |
/// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
|
alpar@100
|
1163 |
/// different items (nodes) get different ids <li>\b immutable: the id of an
|
alpar@100
|
1164 |
/// item (node) does not change (even if you delete other nodes). </ul>
|
alpar@100
|
1165 |
/// Through this map you get access (i.e. can read) the inner id values of
|
deba@139
|
1166 |
/// the items stored in the graph. This map can be inverted with its member
|
deba@139
|
1167 |
/// class \c InverseMap or with the \c operator() member.
|
alpar@100
|
1168 |
///
|
deba@139
|
1169 |
template <typename _Graph, typename _Item>
|
alpar@100
|
1170 |
class IdMap {
|
alpar@100
|
1171 |
public:
|
deba@139
|
1172 |
typedef _Graph Graph;
|
alpar@100
|
1173 |
typedef int Value;
|
alpar@100
|
1174 |
typedef _Item Item;
|
alpar@100
|
1175 |
typedef _Item Key;
|
alpar@100
|
1176 |
|
alpar@100
|
1177 |
/// \brief Constructor.
|
alpar@100
|
1178 |
///
|
alpar@100
|
1179 |
/// Constructor of the map.
|
deba@139
|
1180 |
explicit IdMap(const Graph& graph) : _graph(&graph) {}
|
alpar@100
|
1181 |
|
alpar@100
|
1182 |
/// \brief Gives back the \e id of the item.
|
alpar@100
|
1183 |
///
|
alpar@100
|
1184 |
/// Gives back the immutable and unique \e id of the item.
|
deba@139
|
1185 |
int operator[](const Item& item) const { return _graph->id(item);}
|
alpar@100
|
1186 |
|
alpar@100
|
1187 |
/// \brief Gives back the item by its id.
|
alpar@100
|
1188 |
///
|
alpar@100
|
1189 |
/// Gives back the item by its id.
|
deba@139
|
1190 |
Item operator()(int id) { return _graph->fromId(id, Item()); }
|
alpar@100
|
1191 |
|
alpar@100
|
1192 |
private:
|
deba@139
|
1193 |
const Graph* _graph;
|
alpar@100
|
1194 |
|
alpar@100
|
1195 |
public:
|
alpar@100
|
1196 |
|
alpar@100
|
1197 |
/// \brief The class represents the inverse of its owner (IdMap).
|
alpar@100
|
1198 |
///
|
alpar@100
|
1199 |
/// The class represents the inverse of its owner (IdMap).
|
alpar@100
|
1200 |
/// \see inverse()
|
alpar@100
|
1201 |
class InverseMap {
|
alpar@100
|
1202 |
public:
|
alpar@100
|
1203 |
|
alpar@100
|
1204 |
/// \brief Constructor.
|
alpar@100
|
1205 |
///
|
alpar@100
|
1206 |
/// Constructor for creating an id-to-item map.
|
deba@139
|
1207 |
explicit InverseMap(const Graph& graph) : _graph(&graph) {}
|
alpar@100
|
1208 |
|
alpar@100
|
1209 |
/// \brief Constructor.
|
alpar@100
|
1210 |
///
|
alpar@100
|
1211 |
/// Constructor for creating an id-to-item map.
|
deba@139
|
1212 |
explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
|
alpar@100
|
1213 |
|
alpar@100
|
1214 |
/// \brief Gives back the given item from its id.
|
alpar@100
|
1215 |
///
|
alpar@100
|
1216 |
/// Gives back the given item from its id.
|
alpar@209
|
1217 |
///
|
deba@139
|
1218 |
Item operator[](int id) const { return _graph->fromId(id, Item());}
|
alpar@100
|
1219 |
|
alpar@100
|
1220 |
private:
|
deba@139
|
1221 |
const Graph* _graph;
|
alpar@100
|
1222 |
};
|
alpar@100
|
1223 |
|
alpar@100
|
1224 |
/// \brief Gives back the inverse of the map.
|
alpar@100
|
1225 |
///
|
alpar@100
|
1226 |
/// Gives back the inverse of the IdMap.
|
alpar@209
|
1227 |
InverseMap inverse() const { return InverseMap(*_graph);}
|
alpar@100
|
1228 |
|
alpar@100
|
1229 |
};
|
alpar@100
|
1230 |
|
alpar@209
|
1231 |
|
deba@139
|
1232 |
/// \brief General invertable graph-map type.
|
alpar@100
|
1233 |
|
alpar@209
|
1234 |
/// This type provides simple invertable graph-maps.
|
alpar@209
|
1235 |
/// The InvertableMap wraps an arbitrary ReadWriteMap
|
alpar@100
|
1236 |
/// and if a key is set to a new value then store it
|
alpar@100
|
1237 |
/// in the inverse map.
|
alpar@100
|
1238 |
///
|
alpar@100
|
1239 |
/// The values of the map can be accessed
|
alpar@100
|
1240 |
/// with stl compatible forward iterator.
|
alpar@100
|
1241 |
///
|
kpeter@157
|
1242 |
/// \tparam _Graph The graph type.
|
kpeter@157
|
1243 |
/// \tparam _Item The item type of the graph.
|
kpeter@157
|
1244 |
/// \tparam _Value The value type of the map.
|
alpar@100
|
1245 |
///
|
alpar@100
|
1246 |
/// \see IterableValueMap
|
deba@139
|
1247 |
template <typename _Graph, typename _Item, typename _Value>
|
deba@139
|
1248 |
class InvertableMap : protected DefaultMap<_Graph, _Item, _Value> {
|
alpar@100
|
1249 |
private:
|
alpar@209
|
1250 |
|
deba@139
|
1251 |
typedef DefaultMap<_Graph, _Item, _Value> Map;
|
deba@139
|
1252 |
typedef _Graph Graph;
|
alpar@100
|
1253 |
|
alpar@100
|
1254 |
typedef std::map<_Value, _Item> Container;
|
alpar@209
|
1255 |
Container _inv_map;
|
alpar@100
|
1256 |
|
alpar@100
|
1257 |
public:
|
alpar@209
|
1258 |
|
alpar@100
|
1259 |
/// The key type of InvertableMap (Node, Arc, Edge).
|
alpar@100
|
1260 |
typedef typename Map::Key Key;
|
alpar@100
|
1261 |
/// The value type of the InvertableMap.
|
alpar@100
|
1262 |
typedef typename Map::Value Value;
|
alpar@100
|
1263 |
|
alpar@100
|
1264 |
|
alpar@100
|
1265 |
|
alpar@100
|
1266 |
/// \brief Constructor.
|
alpar@100
|
1267 |
///
|
deba@139
|
1268 |
/// Construct a new InvertableMap for the graph.
|
alpar@100
|
1269 |
///
|
alpar@209
|
1270 |
explicit InvertableMap(const Graph& graph) : Map(graph) {}
|
alpar@100
|
1271 |
|
alpar@100
|
1272 |
/// \brief Forward iterator for values.
|
alpar@100
|
1273 |
///
|
alpar@100
|
1274 |
/// This iterator is an stl compatible forward
|
alpar@100
|
1275 |
/// iterator on the values of the map. The values can
|
alpar@100
|
1276 |
/// be accessed in the [beginValue, endValue) range.
|
alpar@100
|
1277 |
///
|
alpar@209
|
1278 |
class ValueIterator
|
alpar@100
|
1279 |
: public std::iterator<std::forward_iterator_tag, Value> {
|
alpar@100
|
1280 |
friend class InvertableMap;
|
alpar@100
|
1281 |
private:
|
alpar@209
|
1282 |
ValueIterator(typename Container::const_iterator _it)
|
alpar@100
|
1283 |
: it(_it) {}
|
alpar@100
|
1284 |
public:
|
alpar@209
|
1285 |
|
alpar@100
|
1286 |
ValueIterator() {}
|
alpar@100
|
1287 |
|
alpar@100
|
1288 |
ValueIterator& operator++() { ++it; return *this; }
|
alpar@209
|
1289 |
ValueIterator operator++(int) {
|
alpar@209
|
1290 |
ValueIterator tmp(*this);
|
alpar@100
|
1291 |
operator++();
|
alpar@209
|
1292 |
return tmp;
|
alpar@100
|
1293 |
}
|
alpar@100
|
1294 |
|
alpar@100
|
1295 |
const Value& operator*() const { return it->first; }
|
alpar@100
|
1296 |
const Value* operator->() const { return &(it->first); }
|
alpar@100
|
1297 |
|
alpar@100
|
1298 |
bool operator==(ValueIterator jt) const { return it == jt.it; }
|
alpar@100
|
1299 |
bool operator!=(ValueIterator jt) const { return it != jt.it; }
|
alpar@209
|
1300 |
|
alpar@100
|
1301 |
private:
|
alpar@100
|
1302 |
typename Container::const_iterator it;
|
alpar@100
|
1303 |
};
|
alpar@100
|
1304 |
|
alpar@100
|
1305 |
/// \brief Returns an iterator to the first value.
|
alpar@100
|
1306 |
///
|
alpar@209
|
1307 |
/// Returns an stl compatible iterator to the
|
alpar@100
|
1308 |
/// first value of the map. The values of the
|
alpar@100
|
1309 |
/// map can be accessed in the [beginValue, endValue)
|
alpar@100
|
1310 |
/// range.
|
alpar@100
|
1311 |
ValueIterator beginValue() const {
|
deba@139
|
1312 |
return ValueIterator(_inv_map.begin());
|
alpar@100
|
1313 |
}
|
alpar@100
|
1314 |
|
alpar@100
|
1315 |
/// \brief Returns an iterator after the last value.
|
alpar@100
|
1316 |
///
|
alpar@209
|
1317 |
/// Returns an stl compatible iterator after the
|
alpar@100
|
1318 |
/// last value of the map. The values of the
|
alpar@100
|
1319 |
/// map can be accessed in the [beginValue, endValue)
|
alpar@100
|
1320 |
/// range.
|
alpar@100
|
1321 |
ValueIterator endValue() const {
|
deba@139
|
1322 |
return ValueIterator(_inv_map.end());
|
alpar@100
|
1323 |
}
|
alpar@209
|
1324 |
|
alpar@100
|
1325 |
/// \brief The setter function of the map.
|
alpar@100
|
1326 |
///
|
alpar@100
|
1327 |
/// Sets the mapped value.
|
alpar@100
|
1328 |
void set(const Key& key, const Value& val) {
|
alpar@100
|
1329 |
Value oldval = Map::operator[](key);
|
deba@139
|
1330 |
typename Container::iterator it = _inv_map.find(oldval);
|
deba@139
|
1331 |
if (it != _inv_map.end() && it->second == key) {
|
alpar@209
|
1332 |
_inv_map.erase(it);
|
alpar@209
|
1333 |
}
|
deba@139
|
1334 |
_inv_map.insert(make_pair(val, key));
|
alpar@100
|
1335 |
Map::set(key, val);
|
alpar@100
|
1336 |
}
|
alpar@100
|
1337 |
|
alpar@100
|
1338 |
/// \brief The getter function of the map.
|
alpar@100
|
1339 |
///
|
alpar@100
|
1340 |
/// It gives back the value associated with the key.
|
alpar@209
|
1341 |
typename MapTraits<Map>::ConstReturnValue
|
alpar@100
|
1342 |
operator[](const Key& key) const {
|
alpar@100
|
1343 |
return Map::operator[](key);
|
alpar@100
|
1344 |
}
|
alpar@100
|
1345 |
|
alpar@100
|
1346 |
/// \brief Gives back the item by its value.
|
alpar@100
|
1347 |
///
|
alpar@100
|
1348 |
/// Gives back the item by its value.
|
alpar@100
|
1349 |
Key operator()(const Value& key) const {
|
deba@139
|
1350 |
typename Container::const_iterator it = _inv_map.find(key);
|
deba@139
|
1351 |
return it != _inv_map.end() ? it->second : INVALID;
|
alpar@100
|
1352 |
}
|
alpar@100
|
1353 |
|
alpar@100
|
1354 |
protected:
|
alpar@100
|
1355 |
|
alpar@100
|
1356 |
/// \brief Erase the key from the map.
|
alpar@100
|
1357 |
///
|
alpar@100
|
1358 |
/// Erase the key to the map. It is called by the
|
alpar@100
|
1359 |
/// \c AlterationNotifier.
|
alpar@100
|
1360 |
virtual void erase(const Key& key) {
|
alpar@100
|
1361 |
Value val = Map::operator[](key);
|
deba@139
|
1362 |
typename Container::iterator it = _inv_map.find(val);
|
deba@139
|
1363 |
if (it != _inv_map.end() && it->second == key) {
|
alpar@209
|
1364 |
_inv_map.erase(it);
|
alpar@100
|
1365 |
}
|
alpar@100
|
1366 |
Map::erase(key);
|
alpar@100
|
1367 |
}
|
alpar@100
|
1368 |
|
alpar@100
|
1369 |
/// \brief Erase more keys from the map.
|
alpar@100
|
1370 |
///
|
alpar@100
|
1371 |
/// Erase more keys from the map. It is called by the
|
alpar@100
|
1372 |
/// \c AlterationNotifier.
|
alpar@100
|
1373 |
virtual void erase(const std::vector<Key>& keys) {
|
alpar@100
|
1374 |
for (int i = 0; i < int(keys.size()); ++i) {
|
alpar@209
|
1375 |
Value val = Map::operator[](keys[i]);
|
alpar@209
|
1376 |
typename Container::iterator it = _inv_map.find(val);
|
alpar@209
|
1377 |
if (it != _inv_map.end() && it->second == keys[i]) {
|
alpar@209
|
1378 |
_inv_map.erase(it);
|
alpar@209
|
1379 |
}
|
alpar@100
|
1380 |
}
|
alpar@100
|
1381 |
Map::erase(keys);
|
alpar@100
|
1382 |
}
|
alpar@100
|
1383 |
|
alpar@100
|
1384 |
/// \brief Clear the keys from the map and inverse map.
|
alpar@100
|
1385 |
///
|
alpar@100
|
1386 |
/// Clear the keys from the map and inverse map. It is called by the
|
alpar@100
|
1387 |
/// \c AlterationNotifier.
|
alpar@100
|
1388 |
virtual void clear() {
|
deba@139
|
1389 |
_inv_map.clear();
|
alpar@100
|
1390 |
Map::clear();
|
alpar@100
|
1391 |
}
|
alpar@100
|
1392 |
|
alpar@100
|
1393 |
public:
|
alpar@100
|
1394 |
|
alpar@100
|
1395 |
/// \brief The inverse map type.
|
alpar@100
|
1396 |
///
|
alpar@100
|
1397 |
/// The inverse of this map. The subscript operator of the map
|
alpar@209
|
1398 |
/// gives back always the item what was last assigned to the value.
|
alpar@100
|
1399 |
class InverseMap {
|
alpar@100
|
1400 |
public:
|
alpar@100
|
1401 |
/// \brief Constructor of the InverseMap.
|
alpar@100
|
1402 |
///
|
alpar@100
|
1403 |
/// Constructor of the InverseMap.
|
alpar@209
|
1404 |
explicit InverseMap(const InvertableMap& inverted)
|
deba@139
|
1405 |
: _inverted(inverted) {}
|
alpar@100
|
1406 |
|
alpar@100
|
1407 |
/// The value type of the InverseMap.
|
alpar@100
|
1408 |
typedef typename InvertableMap::Key Value;
|
alpar@100
|
1409 |
/// The key type of the InverseMap.
|
alpar@209
|
1410 |
typedef typename InvertableMap::Value Key;
|
alpar@209
|
1411 |
|
alpar@209
|
1412 |
/// \brief Subscript operator.
|
alpar@100
|
1413 |
///
|
alpar@209
|
1414 |
/// Subscript operator. It gives back always the item
|
alpar@100
|
1415 |
/// what was last assigned to the value.
|
alpar@100
|
1416 |
Value operator[](const Key& key) const {
|
alpar@209
|
1417 |
return _inverted(key);
|
alpar@100
|
1418 |
}
|
alpar@209
|
1419 |
|
alpar@100
|
1420 |
private:
|
deba@139
|
1421 |
const InvertableMap& _inverted;
|
alpar@100
|
1422 |
};
|
alpar@100
|
1423 |
|
alpar@100
|
1424 |
/// \brief It gives back the just readable inverse map.
|
alpar@100
|
1425 |
///
|
alpar@100
|
1426 |
/// It gives back the just readable inverse map.
|
alpar@100
|
1427 |
InverseMap inverse() const {
|
alpar@100
|
1428 |
return InverseMap(*this);
|
alpar@209
|
1429 |
}
|
alpar@209
|
1430 |
|
alpar@209
|
1431 |
|
alpar@209
|
1432 |
|
alpar@100
|
1433 |
};
|
alpar@100
|
1434 |
|
alpar@209
|
1435 |
/// \brief Provides a mutable, continuous and unique descriptor for each
|
deba@139
|
1436 |
/// item in the graph.
|
alpar@100
|
1437 |
///
|
alpar@100
|
1438 |
/// The DescriptorMap class provides a unique and continuous (but mutable)
|
alpar@100
|
1439 |
/// descriptor (id) for each item of the same type (e.g. node) in the
|
deba@139
|
1440 |
/// graph. This id is <ul><li>\b unique: different items (nodes) get
|
alpar@100
|
1441 |
/// different ids <li>\b continuous: the range of the ids is the set of
|
alpar@100
|
1442 |
/// integers between 0 and \c n-1, where \c n is the number of the items of
|
alpar@100
|
1443 |
/// this type (e.g. nodes) (so the id of a node can change if you delete an
|
alpar@100
|
1444 |
/// other node, i.e. this id is mutable). </ul> This map can be inverted
|
deba@139
|
1445 |
/// with its member class \c InverseMap, or with the \c operator() member.
|
alpar@100
|
1446 |
///
|
kpeter@157
|
1447 |
/// \tparam _Graph The graph class the \c DescriptorMap belongs to.
|
alpar@209
|
1448 |
/// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
|
alpar@100
|
1449 |
/// Edge.
|
deba@139
|
1450 |
template <typename _Graph, typename _Item>
|
deba@139
|
1451 |
class DescriptorMap : protected DefaultMap<_Graph, _Item, int> {
|
alpar@100
|
1452 |
|
alpar@100
|
1453 |
typedef _Item Item;
|
deba@139
|
1454 |
typedef DefaultMap<_Graph, _Item, int> Map;
|
alpar@100
|
1455 |
|
alpar@100
|
1456 |
public:
|
deba@139
|
1457 |
/// The graph class of DescriptorMap.
|
deba@139
|
1458 |
typedef _Graph Graph;
|
alpar@100
|
1459 |
|
alpar@100
|
1460 |
/// The key type of DescriptorMap (Node, Arc, Edge).
|
alpar@100
|
1461 |
typedef typename Map::Key Key;
|
alpar@100
|
1462 |
/// The value type of DescriptorMap.
|
alpar@100
|
1463 |
typedef typename Map::Value Value;
|
alpar@100
|
1464 |
|
alpar@100
|
1465 |
/// \brief Constructor.
|
alpar@100
|
1466 |
///
|
alpar@100
|
1467 |
/// Constructor for descriptor map.
|
deba@139
|
1468 |
explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
|
alpar@100
|
1469 |
Item it;
|
alpar@209
|
1470 |
const typename Map::Notifier* nf = Map::notifier();
|
alpar@100
|
1471 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
alpar@209
|
1472 |
Map::set(it, _inv_map.size());
|
alpar@209
|
1473 |
_inv_map.push_back(it);
|
alpar@209
|
1474 |
}
|
alpar@100
|
1475 |
}
|
alpar@100
|
1476 |
|
alpar@100
|
1477 |
protected:
|
alpar@100
|
1478 |
|
alpar@100
|
1479 |
/// \brief Add a new key to the map.
|
alpar@100
|
1480 |
///
|
alpar@100
|
1481 |
/// Add a new key to the map. It is called by the
|
alpar@100
|
1482 |
/// \c AlterationNotifier.
|
alpar@100
|
1483 |
virtual void add(const Item& item) {
|
alpar@100
|
1484 |
Map::add(item);
|
deba@139
|
1485 |
Map::set(item, _inv_map.size());
|
deba@139
|
1486 |
_inv_map.push_back(item);
|
alpar@100
|
1487 |
}
|
alpar@100
|
1488 |
|
alpar@100
|
1489 |
/// \brief Add more new keys to the map.
|
alpar@100
|
1490 |
///
|
alpar@100
|
1491 |
/// Add more new keys to the map. It is called by the
|
alpar@100
|
1492 |
/// \c AlterationNotifier.
|
alpar@100
|
1493 |
virtual void add(const std::vector<Item>& items) {
|
alpar@100
|
1494 |
Map::add(items);
|
alpar@100
|
1495 |
for (int i = 0; i < int(items.size()); ++i) {
|
alpar@209
|
1496 |
Map::set(items[i], _inv_map.size());
|
alpar@209
|
1497 |
_inv_map.push_back(items[i]);
|
alpar@100
|
1498 |
}
|
alpar@100
|
1499 |
}
|
alpar@100
|
1500 |
|
alpar@100
|
1501 |
/// \brief Erase the key from the map.
|
alpar@100
|
1502 |
///
|
alpar@100
|
1503 |
/// Erase the key from the map. It is called by the
|
alpar@100
|
1504 |
/// \c AlterationNotifier.
|
alpar@100
|
1505 |
virtual void erase(const Item& item) {
|
deba@139
|
1506 |
Map::set(_inv_map.back(), Map::operator[](item));
|
deba@139
|
1507 |
_inv_map[Map::operator[](item)] = _inv_map.back();
|
deba@139
|
1508 |
_inv_map.pop_back();
|
alpar@100
|
1509 |
Map::erase(item);
|
alpar@100
|
1510 |
}
|
alpar@100
|
1511 |
|
alpar@100
|
1512 |
/// \brief Erase more keys from the map.
|
alpar@100
|
1513 |
///
|
alpar@100
|
1514 |
/// Erase more keys from the map. It is called by the
|
alpar@100
|
1515 |
/// \c AlterationNotifier.
|
alpar@100
|
1516 |
virtual void erase(const std::vector<Item>& items) {
|
alpar@100
|
1517 |
for (int i = 0; i < int(items.size()); ++i) {
|
alpar@209
|
1518 |
Map::set(_inv_map.back(), Map::operator[](items[i]));
|
alpar@209
|
1519 |
_inv_map[Map::operator[](items[i])] = _inv_map.back();
|
alpar@209
|
1520 |
_inv_map.pop_back();
|
alpar@100
|
1521 |
}
|
alpar@100
|
1522 |
Map::erase(items);
|
alpar@100
|
1523 |
}
|
alpar@100
|
1524 |
|
alpar@100
|
1525 |
/// \brief Build the unique map.
|
alpar@100
|
1526 |
///
|
alpar@100
|
1527 |
/// Build the unique map. It is called by the
|
alpar@100
|
1528 |
/// \c AlterationNotifier.
|
alpar@100
|
1529 |
virtual void build() {
|
alpar@100
|
1530 |
Map::build();
|
alpar@100
|
1531 |
Item it;
|
alpar@209
|
1532 |
const typename Map::Notifier* nf = Map::notifier();
|
alpar@100
|
1533 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
alpar@209
|
1534 |
Map::set(it, _inv_map.size());
|
alpar@209
|
1535 |
_inv_map.push_back(it);
|
alpar@209
|
1536 |
}
|
alpar@100
|
1537 |
}
|
alpar@209
|
1538 |
|
alpar@100
|
1539 |
/// \brief Clear the keys from the map.
|
alpar@100
|
1540 |
///
|
alpar@100
|
1541 |
/// Clear the keys from the map. It is called by the
|
alpar@100
|
1542 |
/// \c AlterationNotifier.
|
alpar@100
|
1543 |
virtual void clear() {
|
deba@139
|
1544 |
_inv_map.clear();
|
alpar@100
|
1545 |
Map::clear();
|
alpar@100
|
1546 |
}
|
alpar@100
|
1547 |
|
alpar@100
|
1548 |
public:
|
alpar@100
|
1549 |
|
alpar@100
|
1550 |
/// \brief Returns the maximal value plus one.
|
alpar@100
|
1551 |
///
|
alpar@100
|
1552 |
/// Returns the maximal value plus one in the map.
|
alpar@100
|
1553 |
unsigned int size() const {
|
deba@139
|
1554 |
return _inv_map.size();
|
alpar@100
|
1555 |
}
|
alpar@100
|
1556 |
|
alpar@100
|
1557 |
/// \brief Swaps the position of the two items in the map.
|
alpar@100
|
1558 |
///
|
alpar@100
|
1559 |
/// Swaps the position of the two items in the map.
|
alpar@100
|
1560 |
void swap(const Item& p, const Item& q) {
|
alpar@100
|
1561 |
int pi = Map::operator[](p);
|
alpar@100
|
1562 |
int qi = Map::operator[](q);
|
alpar@100
|
1563 |
Map::set(p, qi);
|
deba@139
|
1564 |
_inv_map[qi] = p;
|
alpar@100
|
1565 |
Map::set(q, pi);
|
deba@139
|
1566 |
_inv_map[pi] = q;
|
alpar@100
|
1567 |
}
|
alpar@100
|
1568 |
|
alpar@100
|
1569 |
/// \brief Gives back the \e descriptor of the item.
|
alpar@100
|
1570 |
///
|
alpar@100
|
1571 |
/// Gives back the mutable and unique \e descriptor of the map.
|
alpar@100
|
1572 |
int operator[](const Item& item) const {
|
alpar@100
|
1573 |
return Map::operator[](item);
|
alpar@100
|
1574 |
}
|
alpar@100
|
1575 |
|
alpar@100
|
1576 |
/// \brief Gives back the item by its descriptor.
|
alpar@100
|
1577 |
///
|
alpar@100
|
1578 |
/// Gives back th item by its descriptor.
|
alpar@100
|
1579 |
Item operator()(int id) const {
|
deba@139
|
1580 |
return _inv_map[id];
|
alpar@100
|
1581 |
}
|
alpar@209
|
1582 |
|
alpar@100
|
1583 |
private:
|
alpar@100
|
1584 |
|
alpar@100
|
1585 |
typedef std::vector<Item> Container;
|
deba@139
|
1586 |
Container _inv_map;
|
alpar@100
|
1587 |
|
alpar@100
|
1588 |
public:
|
alpar@100
|
1589 |
/// \brief The inverse map type of DescriptorMap.
|
alpar@100
|
1590 |
///
|
alpar@100
|
1591 |
/// The inverse map type of DescriptorMap.
|
alpar@100
|
1592 |
class InverseMap {
|
alpar@100
|
1593 |
public:
|
alpar@100
|
1594 |
/// \brief Constructor of the InverseMap.
|
alpar@100
|
1595 |
///
|
alpar@100
|
1596 |
/// Constructor of the InverseMap.
|
alpar@209
|
1597 |
explicit InverseMap(const DescriptorMap& inverted)
|
alpar@209
|
1598 |
: _inverted(inverted) {}
|
alpar@100
|
1599 |
|
alpar@100
|
1600 |
|
alpar@100
|
1601 |
/// The value type of the InverseMap.
|
alpar@100
|
1602 |
typedef typename DescriptorMap::Key Value;
|
alpar@100
|
1603 |
/// The key type of the InverseMap.
|
alpar@209
|
1604 |
typedef typename DescriptorMap::Value Key;
|
alpar@209
|
1605 |
|
alpar@209
|
1606 |
/// \brief Subscript operator.
|
alpar@100
|
1607 |
///
|
alpar@209
|
1608 |
/// Subscript operator. It gives back the item
|
alpar@100
|
1609 |
/// that the descriptor belongs to currently.
|
alpar@100
|
1610 |
Value operator[](const Key& key) const {
|
alpar@209
|
1611 |
return _inverted(key);
|
alpar@100
|
1612 |
}
|
alpar@100
|
1613 |
|
alpar@100
|
1614 |
/// \brief Size of the map.
|
alpar@100
|
1615 |
///
|
alpar@100
|
1616 |
/// Returns the size of the map.
|
alpar@100
|
1617 |
unsigned int size() const {
|
alpar@209
|
1618 |
return _inverted.size();
|
alpar@100
|
1619 |
}
|
alpar@209
|
1620 |
|
alpar@100
|
1621 |
private:
|
deba@139
|
1622 |
const DescriptorMap& _inverted;
|
alpar@100
|
1623 |
};
|
alpar@100
|
1624 |
|
alpar@100
|
1625 |
/// \brief Gives back the inverse of the map.
|
alpar@100
|
1626 |
///
|
alpar@100
|
1627 |
/// Gives back the inverse of the map.
|
alpar@100
|
1628 |
const InverseMap inverse() const {
|
alpar@100
|
1629 |
return InverseMap(*this);
|
alpar@100
|
1630 |
}
|
alpar@100
|
1631 |
};
|
alpar@100
|
1632 |
|
alpar@100
|
1633 |
/// \brief Returns the source of the given arc.
|
alpar@100
|
1634 |
///
|
alpar@209
|
1635 |
/// The SourceMap gives back the source Node of the given arc.
|
alpar@100
|
1636 |
/// \see TargetMap
|
alpar@100
|
1637 |
template <typename Digraph>
|
alpar@100
|
1638 |
class SourceMap {
|
alpar@100
|
1639 |
public:
|
alpar@100
|
1640 |
|
alpar@100
|
1641 |
typedef typename Digraph::Node Value;
|
alpar@100
|
1642 |
typedef typename Digraph::Arc Key;
|
alpar@100
|
1643 |
|
alpar@100
|
1644 |
/// \brief Constructor
|
alpar@100
|
1645 |
///
|
alpar@100
|
1646 |
/// Constructor
|
alpar@100
|
1647 |
/// \param _digraph The digraph that the map belongs to.
|
deba@139
|
1648 |
explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
|
alpar@100
|
1649 |
|
alpar@100
|
1650 |
/// \brief The subscript operator.
|
alpar@100
|
1651 |
///
|
alpar@100
|
1652 |
/// The subscript operator.
|
alpar@209
|
1653 |
/// \param arc The arc
|
alpar@209
|
1654 |
/// \return The source of the arc
|
alpar@100
|
1655 |
Value operator[](const Key& arc) const {
|
deba@139
|
1656 |
return _digraph.source(arc);
|
alpar@100
|
1657 |
}
|
alpar@100
|
1658 |
|
alpar@100
|
1659 |
private:
|
deba@139
|
1660 |
const Digraph& _digraph;
|
alpar@100
|
1661 |
};
|
alpar@100
|
1662 |
|
alpar@100
|
1663 |
/// \brief Returns a \ref SourceMap class.
|
alpar@100
|
1664 |
///
|
alpar@100
|
1665 |
/// This function just returns an \ref SourceMap class.
|
alpar@100
|
1666 |
/// \relates SourceMap
|
alpar@100
|
1667 |
template <typename Digraph>
|
alpar@100
|
1668 |
inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
|
alpar@100
|
1669 |
return SourceMap<Digraph>(digraph);
|
alpar@209
|
1670 |
}
|
alpar@100
|
1671 |
|
alpar@100
|
1672 |
/// \brief Returns the target of the given arc.
|
alpar@100
|
1673 |
///
|
alpar@209
|
1674 |
/// The TargetMap gives back the target Node of the given arc.
|
alpar@100
|
1675 |
/// \see SourceMap
|
alpar@100
|
1676 |
template <typename Digraph>
|
alpar@100
|
1677 |
class TargetMap {
|
alpar@100
|
1678 |
public:
|
alpar@100
|
1679 |
|
alpar@100
|
1680 |
typedef typename Digraph::Node Value;
|
alpar@100
|
1681 |
typedef typename Digraph::Arc Key;
|
alpar@100
|
1682 |
|
alpar@100
|
1683 |
/// \brief Constructor
|
alpar@100
|
1684 |
///
|
alpar@100
|
1685 |
/// Constructor
|
alpar@100
|
1686 |
/// \param _digraph The digraph that the map belongs to.
|
deba@139
|
1687 |
explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
|
alpar@100
|
1688 |
|
alpar@100
|
1689 |
/// \brief The subscript operator.
|
alpar@100
|
1690 |
///
|
alpar@100
|
1691 |
/// The subscript operator.
|
alpar@209
|
1692 |
/// \param e The arc
|
alpar@209
|
1693 |
/// \return The target of the arc
|
alpar@100
|
1694 |
Value operator[](const Key& e) const {
|
deba@139
|
1695 |
return _digraph.target(e);
|
alpar@100
|
1696 |
}
|
alpar@100
|
1697 |
|
alpar@100
|
1698 |
private:
|
deba@139
|
1699 |
const Digraph& _digraph;
|
alpar@100
|
1700 |
};
|
alpar@100
|
1701 |
|
alpar@100
|
1702 |
/// \brief Returns a \ref TargetMap class.
|
alpar@100
|
1703 |
///
|
alpar@100
|
1704 |
/// This function just returns a \ref TargetMap class.
|
alpar@100
|
1705 |
/// \relates TargetMap
|
alpar@100
|
1706 |
template <typename Digraph>
|
alpar@100
|
1707 |
inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
|
alpar@100
|
1708 |
return TargetMap<Digraph>(digraph);
|
alpar@100
|
1709 |
}
|
alpar@100
|
1710 |
|
alpar@100
|
1711 |
/// \brief Returns the "forward" directed arc view of an edge.
|
alpar@100
|
1712 |
///
|
alpar@100
|
1713 |
/// Returns the "forward" directed arc view of an edge.
|
alpar@100
|
1714 |
/// \see BackwardMap
|
deba@139
|
1715 |
template <typename Graph>
|
alpar@100
|
1716 |
class ForwardMap {
|
alpar@100
|
1717 |
public:
|
alpar@100
|
1718 |
|
deba@139
|
1719 |
typedef typename Graph::Arc Value;
|
deba@139
|
1720 |
typedef typename Graph::Edge Key;
|
alpar@100
|
1721 |
|
alpar@100
|
1722 |
/// \brief Constructor
|
alpar@100
|
1723 |
///
|
alpar@100
|
1724 |
/// Constructor
|
deba@139
|
1725 |
/// \param _graph The graph that the map belongs to.
|
deba@139
|
1726 |
explicit ForwardMap(const Graph& graph) : _graph(graph) {}
|
alpar@100
|
1727 |
|
alpar@100
|
1728 |
/// \brief The subscript operator.
|
alpar@100
|
1729 |
///
|
alpar@100
|
1730 |
/// The subscript operator.
|
alpar@209
|
1731 |
/// \param key An edge
|
alpar@209
|
1732 |
/// \return The "forward" directed arc view of edge
|
alpar@100
|
1733 |
Value operator[](const Key& key) const {
|
deba@139
|
1734 |
return _graph.direct(key, true);
|
alpar@100
|
1735 |
}
|
alpar@100
|
1736 |
|
alpar@100
|
1737 |
private:
|
deba@139
|
1738 |
const Graph& _graph;
|
alpar@100
|
1739 |
};
|
alpar@100
|
1740 |
|
alpar@100
|
1741 |
/// \brief Returns a \ref ForwardMap class.
|
alpar@100
|
1742 |
///
|
alpar@100
|
1743 |
/// This function just returns an \ref ForwardMap class.
|
alpar@100
|
1744 |
/// \relates ForwardMap
|
deba@139
|
1745 |
template <typename Graph>
|
deba@139
|
1746 |
inline ForwardMap<Graph> forwardMap(const Graph& graph) {
|
deba@139
|
1747 |
return ForwardMap<Graph>(graph);
|
alpar@100
|
1748 |
}
|
alpar@100
|
1749 |
|
alpar@100
|
1750 |
/// \brief Returns the "backward" directed arc view of an edge.
|
alpar@100
|
1751 |
///
|
alpar@100
|
1752 |
/// Returns the "backward" directed arc view of an edge.
|
alpar@100
|
1753 |
/// \see ForwardMap
|
deba@139
|
1754 |
template <typename Graph>
|
alpar@100
|
1755 |
class BackwardMap {
|
alpar@100
|
1756 |
public:
|
alpar@100
|
1757 |
|
deba@139
|
1758 |
typedef typename Graph::Arc Value;
|
deba@139
|
1759 |
typedef typename Graph::Edge Key;
|
alpar@100
|
1760 |
|
alpar@100
|
1761 |
/// \brief Constructor
|
alpar@100
|
1762 |
///
|
alpar@100
|
1763 |
/// Constructor
|
deba@139
|
1764 |
/// \param _graph The graph that the map belongs to.
|
deba@139
|
1765 |
explicit BackwardMap(const Graph& graph) : _graph(graph) {}
|
alpar@100
|
1766 |
|
alpar@100
|
1767 |
/// \brief The subscript operator.
|
alpar@100
|
1768 |
///
|
alpar@100
|
1769 |
/// The subscript operator.
|
alpar@209
|
1770 |
/// \param key An edge
|
alpar@209
|
1771 |
/// \return The "backward" directed arc view of edge
|
alpar@100
|
1772 |
Value operator[](const Key& key) const {
|
deba@139
|
1773 |
return _graph.direct(key, false);
|
alpar@100
|
1774 |
}
|
alpar@100
|
1775 |
|
alpar@100
|
1776 |
private:
|
deba@139
|
1777 |
const Graph& _graph;
|
alpar@100
|
1778 |
};
|
alpar@100
|
1779 |
|
alpar@100
|
1780 |
/// \brief Returns a \ref BackwardMap class
|
alpar@100
|
1781 |
|
alpar@100
|
1782 |
/// This function just returns a \ref BackwardMap class.
|
alpar@100
|
1783 |
/// \relates BackwardMap
|
deba@139
|
1784 |
template <typename Graph>
|
deba@139
|
1785 |
inline BackwardMap<Graph> backwardMap(const Graph& graph) {
|
deba@139
|
1786 |
return BackwardMap<Graph>(graph);
|
alpar@100
|
1787 |
}
|
alpar@100
|
1788 |
|
alpar@100
|
1789 |
/// \brief Potential difference map
|
alpar@100
|
1790 |
///
|
alpar@100
|
1791 |
/// If there is an potential map on the nodes then we
|
alpar@100
|
1792 |
/// can get an arc map as we get the substraction of the
|
alpar@100
|
1793 |
/// values of the target and source.
|
alpar@100
|
1794 |
template <typename Digraph, typename NodeMap>
|
alpar@100
|
1795 |
class PotentialDifferenceMap {
|
alpar@100
|
1796 |
public:
|
alpar@100
|
1797 |
typedef typename Digraph::Arc Key;
|
alpar@100
|
1798 |
typedef typename NodeMap::Value Value;
|
alpar@100
|
1799 |
|
alpar@100
|
1800 |
/// \brief Constructor
|
alpar@100
|
1801 |
///
|
alpar@100
|
1802 |
/// Contructor of the map
|
alpar@209
|
1803 |
explicit PotentialDifferenceMap(const Digraph& digraph,
|
alpar@209
|
1804 |
const NodeMap& potential)
|
deba@139
|
1805 |
: _digraph(digraph), _potential(potential) {}
|
alpar@100
|
1806 |
|
alpar@100
|
1807 |
/// \brief Const subscription operator
|
alpar@100
|
1808 |
///
|
alpar@100
|
1809 |
/// Const subscription operator
|
alpar@100
|
1810 |
Value operator[](const Key& arc) const {
|
alpar@209
|
1811 |
return _potential[_digraph.target(arc)] -
|
alpar@209
|
1812 |
_potential[_digraph.source(arc)];
|
alpar@100
|
1813 |
}
|
alpar@100
|
1814 |
|
alpar@100
|
1815 |
private:
|
deba@139
|
1816 |
const Digraph& _digraph;
|
deba@139
|
1817 |
const NodeMap& _potential;
|
alpar@100
|
1818 |
};
|
alpar@100
|
1819 |
|
alpar@100
|
1820 |
/// \brief Returns a PotentialDifferenceMap.
|
alpar@100
|
1821 |
///
|
alpar@100
|
1822 |
/// This function just returns a PotentialDifferenceMap.
|
alpar@100
|
1823 |
/// \relates PotentialDifferenceMap
|
alpar@100
|
1824 |
template <typename Digraph, typename NodeMap>
|
alpar@209
|
1825 |
PotentialDifferenceMap<Digraph, NodeMap>
|
alpar@100
|
1826 |
potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
|
alpar@100
|
1827 |
return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
|
alpar@100
|
1828 |
}
|
alpar@100
|
1829 |
|
alpar@100
|
1830 |
/// \brief Map of the node in-degrees.
|
alpar@100
|
1831 |
///
|
alpar@100
|
1832 |
/// This map returns the in-degree of a node. Once it is constructed,
|
alpar@100
|
1833 |
/// the degrees are stored in a standard NodeMap, so each query is done
|
alpar@100
|
1834 |
/// in constant time. On the other hand, the values are updated automatically
|
alpar@100
|
1835 |
/// whenever the digraph changes.
|
alpar@100
|
1836 |
///
|
alpar@100
|
1837 |
/// \warning Besides addNode() and addArc(), a digraph structure may provide
|
alpar@100
|
1838 |
/// alternative ways to modify the digraph. The correct behavior of InDegMap
|
alpar@100
|
1839 |
/// is not guarantied if these additional features are used. For example
|
alpar@100
|
1840 |
/// the functions \ref ListDigraph::changeSource() "changeSource()",
|
alpar@100
|
1841 |
/// \ref ListDigraph::changeTarget() "changeTarget()" and
|
alpar@100
|
1842 |
/// \ref ListDigraph::reverseArc() "reverseArc()"
|
alpar@100
|
1843 |
/// of \ref ListDigraph will \e not update the degree values correctly.
|
alpar@100
|
1844 |
///
|
alpar@100
|
1845 |
/// \sa OutDegMap
|
alpar@100
|
1846 |
|
alpar@100
|
1847 |
template <typename _Digraph>
|
alpar@209
|
1848 |
class InDegMap
|
alpar@100
|
1849 |
: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
|
alpar@100
|
1850 |
::ItemNotifier::ObserverBase {
|
alpar@100
|
1851 |
|
alpar@100
|
1852 |
public:
|
alpar@209
|
1853 |
|
alpar@100
|
1854 |
typedef _Digraph Digraph;
|
alpar@100
|
1855 |
typedef int Value;
|
alpar@100
|
1856 |
typedef typename Digraph::Node Key;
|
alpar@100
|
1857 |
|
deba@139
|
1858 |
typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
|
alpar@100
|
1859 |
::ItemNotifier::ObserverBase Parent;
|
alpar@100
|
1860 |
|
alpar@100
|
1861 |
private:
|
alpar@100
|
1862 |
|
deba@139
|
1863 |
class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
|
alpar@100
|
1864 |
public:
|
alpar@100
|
1865 |
|
deba@139
|
1866 |
typedef DefaultMap<Digraph, Key, int> Parent;
|
alpar@100
|
1867 |
|
alpar@100
|
1868 |
AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
|
alpar@209
|
1869 |
|
alpar@100
|
1870 |
virtual void add(const Key& key) {
|
alpar@209
|
1871 |
Parent::add(key);
|
alpar@209
|
1872 |
Parent::set(key, 0);
|
alpar@100
|
1873 |
}
|
alpar@100
|
1874 |
|
alpar@100
|
1875 |
virtual void add(const std::vector<Key>& keys) {
|
alpar@209
|
1876 |
Parent::add(keys);
|
alpar@209
|
1877 |
for (int i = 0; i < int(keys.size()); ++i) {
|
alpar@209
|
1878 |
Parent::set(keys[i], 0);
|
alpar@209
|
1879 |
}
|
alpar@100
|
1880 |
}
|
alpar@100
|
1881 |
|
alpar@100
|
1882 |
virtual void build() {
|
alpar@209
|
1883 |
Parent::build();
|
alpar@209
|
1884 |
Key it;
|
alpar@209
|
1885 |
typename Parent::Notifier* nf = Parent::notifier();
|
alpar@209
|
1886 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
alpar@209
|
1887 |
Parent::set(it, 0);
|
alpar@209
|
1888 |
}
|
alpar@100
|
1889 |
}
|
alpar@100
|
1890 |
};
|
alpar@100
|
1891 |
|
alpar@100
|
1892 |
public:
|
alpar@100
|
1893 |
|
alpar@100
|
1894 |
/// \brief Constructor.
|
alpar@100
|
1895 |
///
|
alpar@100
|
1896 |
/// Constructor for creating in-degree map.
|
alpar@209
|
1897 |
explicit InDegMap(const Digraph& digraph)
|
deba@139
|
1898 |
: _digraph(digraph), _deg(digraph) {
|
deba@139
|
1899 |
Parent::attach(_digraph.notifier(typename Digraph::Arc()));
|
alpar@209
|
1900 |
|
deba@139
|
1901 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
1902 |
_deg[it] = countInArcs(_digraph, it);
|
alpar@100
|
1903 |
}
|
alpar@100
|
1904 |
}
|
alpar@209
|
1905 |
|
alpar@100
|
1906 |
/// Gives back the in-degree of a Node.
|
alpar@100
|
1907 |
int operator[](const Key& key) const {
|
deba@139
|
1908 |
return _deg[key];
|
alpar@100
|
1909 |
}
|
alpar@100
|
1910 |
|
alpar@100
|
1911 |
protected:
|
alpar@209
|
1912 |
|
alpar@100
|
1913 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
1914 |
|
alpar@100
|
1915 |
virtual void add(const Arc& arc) {
|
deba@139
|
1916 |
++_deg[_digraph.target(arc)];
|
alpar@100
|
1917 |
}
|
alpar@100
|
1918 |
|
alpar@100
|
1919 |
virtual void add(const std::vector<Arc>& arcs) {
|
alpar@100
|
1920 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@139
|
1921 |
++_deg[_digraph.target(arcs[i])];
|
alpar@100
|
1922 |
}
|
alpar@100
|
1923 |
}
|
alpar@100
|
1924 |
|
alpar@100
|
1925 |
virtual void erase(const Arc& arc) {
|
deba@139
|
1926 |
--_deg[_digraph.target(arc)];
|
alpar@100
|
1927 |
}
|
alpar@100
|
1928 |
|
alpar@100
|
1929 |
virtual void erase(const std::vector<Arc>& arcs) {
|
alpar@100
|
1930 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@139
|
1931 |
--_deg[_digraph.target(arcs[i])];
|
alpar@100
|
1932 |
}
|
alpar@100
|
1933 |
}
|
alpar@100
|
1934 |
|
alpar@100
|
1935 |
virtual void build() {
|
deba@139
|
1936 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
1937 |
_deg[it] = countInArcs(_digraph, it);
|
alpar@209
|
1938 |
}
|
alpar@100
|
1939 |
}
|
alpar@100
|
1940 |
|
alpar@100
|
1941 |
virtual void clear() {
|
deba@139
|
1942 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
1943 |
_deg[it] = 0;
|
alpar@100
|
1944 |
}
|
alpar@100
|
1945 |
}
|
alpar@100
|
1946 |
private:
|
alpar@209
|
1947 |
|
deba@139
|
1948 |
const Digraph& _digraph;
|
deba@139
|
1949 |
AutoNodeMap _deg;
|
alpar@100
|
1950 |
};
|
alpar@100
|
1951 |
|
alpar@100
|
1952 |
/// \brief Map of the node out-degrees.
|
alpar@100
|
1953 |
///
|
alpar@100
|
1954 |
/// This map returns the out-degree of a node. Once it is constructed,
|
alpar@100
|
1955 |
/// the degrees are stored in a standard NodeMap, so each query is done
|
alpar@100
|
1956 |
/// in constant time. On the other hand, the values are updated automatically
|
alpar@100
|
1957 |
/// whenever the digraph changes.
|
alpar@100
|
1958 |
///
|
alpar@100
|
1959 |
/// \warning Besides addNode() and addArc(), a digraph structure may provide
|
alpar@100
|
1960 |
/// alternative ways to modify the digraph. The correct behavior of OutDegMap
|
alpar@100
|
1961 |
/// is not guarantied if these additional features are used. For example
|
alpar@100
|
1962 |
/// the functions \ref ListDigraph::changeSource() "changeSource()",
|
alpar@100
|
1963 |
/// \ref ListDigraph::changeTarget() "changeTarget()" and
|
alpar@100
|
1964 |
/// \ref ListDigraph::reverseArc() "reverseArc()"
|
alpar@100
|
1965 |
/// of \ref ListDigraph will \e not update the degree values correctly.
|
alpar@100
|
1966 |
///
|
alpar@100
|
1967 |
/// \sa InDegMap
|
alpar@100
|
1968 |
|
alpar@100
|
1969 |
template <typename _Digraph>
|
alpar@209
|
1970 |
class OutDegMap
|
alpar@100
|
1971 |
: protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
|
alpar@100
|
1972 |
::ItemNotifier::ObserverBase {
|
alpar@100
|
1973 |
|
alpar@100
|
1974 |
public:
|
alpar@209
|
1975 |
|
alpar@100
|
1976 |
typedef _Digraph Digraph;
|
alpar@100
|
1977 |
typedef int Value;
|
alpar@100
|
1978 |
typedef typename Digraph::Node Key;
|
alpar@100
|
1979 |
|
deba@139
|
1980 |
typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
|
deba@139
|
1981 |
::ItemNotifier::ObserverBase Parent;
|
deba@139
|
1982 |
|
alpar@100
|
1983 |
private:
|
alpar@100
|
1984 |
|
deba@139
|
1985 |
class AutoNodeMap : public DefaultMap<Digraph, Key, int> {
|
alpar@100
|
1986 |
public:
|
alpar@100
|
1987 |
|
deba@139
|
1988 |
typedef DefaultMap<Digraph, Key, int> Parent;
|
alpar@100
|
1989 |
|
alpar@100
|
1990 |
AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
|
alpar@209
|
1991 |
|
alpar@100
|
1992 |
virtual void add(const Key& key) {
|
alpar@209
|
1993 |
Parent::add(key);
|
alpar@209
|
1994 |
Parent::set(key, 0);
|
alpar@100
|
1995 |
}
|
alpar@100
|
1996 |
virtual void add(const std::vector<Key>& keys) {
|
alpar@209
|
1997 |
Parent::add(keys);
|
alpar@209
|
1998 |
for (int i = 0; i < int(keys.size()); ++i) {
|
alpar@209
|
1999 |
Parent::set(keys[i], 0);
|
alpar@209
|
2000 |
}
|
alpar@100
|
2001 |
}
|
alpar@100
|
2002 |
virtual void build() {
|
alpar@209
|
2003 |
Parent::build();
|
alpar@209
|
2004 |
Key it;
|
alpar@209
|
2005 |
typename Parent::Notifier* nf = Parent::notifier();
|
alpar@209
|
2006 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
alpar@209
|
2007 |
Parent::set(it, 0);
|
alpar@209
|
2008 |
}
|
alpar@100
|
2009 |
}
|
alpar@100
|
2010 |
};
|
alpar@100
|
2011 |
|
alpar@100
|
2012 |
public:
|
alpar@100
|
2013 |
|
alpar@100
|
2014 |
/// \brief Constructor.
|
alpar@100
|
2015 |
///
|
alpar@100
|
2016 |
/// Constructor for creating out-degree map.
|
alpar@209
|
2017 |
explicit OutDegMap(const Digraph& digraph)
|
deba@139
|
2018 |
: _digraph(digraph), _deg(digraph) {
|
deba@139
|
2019 |
Parent::attach(_digraph.notifier(typename Digraph::Arc()));
|
alpar@209
|
2020 |
|
deba@139
|
2021 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
2022 |
_deg[it] = countOutArcs(_digraph, it);
|
alpar@100
|
2023 |
}
|
alpar@100
|
2024 |
}
|
alpar@100
|
2025 |
|
alpar@100
|
2026 |
/// Gives back the out-degree of a Node.
|
alpar@100
|
2027 |
int operator[](const Key& key) const {
|
deba@139
|
2028 |
return _deg[key];
|
alpar@100
|
2029 |
}
|
alpar@100
|
2030 |
|
alpar@100
|
2031 |
protected:
|
alpar@209
|
2032 |
|
alpar@100
|
2033 |
typedef typename Digraph::Arc Arc;
|
alpar@100
|
2034 |
|
alpar@100
|
2035 |
virtual void add(const Arc& arc) {
|
deba@139
|
2036 |
++_deg[_digraph.source(arc)];
|
alpar@100
|
2037 |
}
|
alpar@100
|
2038 |
|
alpar@100
|
2039 |
virtual void add(const std::vector<Arc>& arcs) {
|
alpar@100
|
2040 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@139
|
2041 |
++_deg[_digraph.source(arcs[i])];
|
alpar@100
|
2042 |
}
|
alpar@100
|
2043 |
}
|
alpar@100
|
2044 |
|
alpar@100
|
2045 |
virtual void erase(const Arc& arc) {
|
deba@139
|
2046 |
--_deg[_digraph.source(arc)];
|
alpar@100
|
2047 |
}
|
alpar@100
|
2048 |
|
alpar@100
|
2049 |
virtual void erase(const std::vector<Arc>& arcs) {
|
alpar@100
|
2050 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@139
|
2051 |
--_deg[_digraph.source(arcs[i])];
|
alpar@100
|
2052 |
}
|
alpar@100
|
2053 |
}
|
alpar@100
|
2054 |
|
alpar@100
|
2055 |
virtual void build() {
|
deba@139
|
2056 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
2057 |
_deg[it] = countOutArcs(_digraph, it);
|
alpar@209
|
2058 |
}
|
alpar@100
|
2059 |
}
|
alpar@100
|
2060 |
|
alpar@100
|
2061 |
virtual void clear() {
|
deba@139
|
2062 |
for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
|
alpar@209
|
2063 |
_deg[it] = 0;
|
alpar@100
|
2064 |
}
|
alpar@100
|
2065 |
}
|
alpar@100
|
2066 |
private:
|
alpar@209
|
2067 |
|
deba@139
|
2068 |
const Digraph& _digraph;
|
deba@139
|
2069 |
AutoNodeMap _deg;
|
alpar@100
|
2070 |
};
|
alpar@100
|
2071 |
|
alpar@100
|
2072 |
|
alpar@100
|
2073 |
///Dynamic arc look up between given endpoints.
|
alpar@209
|
2074 |
|
alpar@100
|
2075 |
///\ingroup gutils
|
alpar@100
|
2076 |
///Using this class, you can find an arc in a digraph from a given
|
alpar@100
|
2077 |
///source to a given target in amortized time <em>O(log d)</em>,
|
alpar@100
|
2078 |
///where <em>d</em> is the out-degree of the source node.
|
alpar@100
|
2079 |
///
|
alpar@100
|
2080 |
///It is possible to find \e all parallel arcs between two nodes with
|
alpar@100
|
2081 |
///the \c findFirst() and \c findNext() members.
|
alpar@100
|
2082 |
///
|
alpar@100
|
2083 |
///See the \ref ArcLookUp and \ref AllArcLookUp classes if your
|
deba@139
|
2084 |
///digraph is not changed so frequently.
|
alpar@100
|
2085 |
///
|
alpar@100
|
2086 |
///This class uses a self-adjusting binary search tree, Sleator's
|
alpar@100
|
2087 |
///and Tarjan's Splay tree for guarantee the logarithmic amortized
|
alpar@100
|
2088 |
///time bound for arc lookups. This class also guarantees the
|
alpar@100
|
2089 |
///optimal time bound in a constant factor for any distribution of
|
alpar@100
|
2090 |
///queries.
|
alpar@100
|
2091 |
///
|
alpar@209
|
2092 |
///\tparam G The type of the underlying digraph.
|
alpar@100
|
2093 |
///
|
alpar@209
|
2094 |
///\sa ArcLookUp
|
alpar@209
|
2095 |
///\sa AllArcLookUp
|
alpar@100
|
2096 |
template<class G>
|
alpar@209
|
2097 |
class DynArcLookUp
|
alpar@100
|
2098 |
: protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
|
alpar@100
|
2099 |
{
|
alpar@100
|
2100 |
public:
|
alpar@100
|
2101 |
typedef typename ItemSetTraits<G, typename G::Arc>
|
alpar@100
|
2102 |
::ItemNotifier::ObserverBase Parent;
|
alpar@100
|
2103 |
|
deba@148
|
2104 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
alpar@100
|
2105 |
typedef G Digraph;
|
alpar@100
|
2106 |
|
alpar@100
|
2107 |
protected:
|
alpar@100
|
2108 |
|
alpar@100
|
2109 |
class AutoNodeMap : public DefaultMap<G, Node, Arc> {
|
alpar@100
|
2110 |
public:
|
alpar@100
|
2111 |
|
alpar@100
|
2112 |
typedef DefaultMap<G, Node, Arc> Parent;
|
alpar@100
|
2113 |
|
alpar@100
|
2114 |
AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
|
alpar@209
|
2115 |
|
alpar@100
|
2116 |
virtual void add(const Node& node) {
|
alpar@209
|
2117 |
Parent::add(node);
|
alpar@209
|
2118 |
Parent::set(node, INVALID);
|
alpar@100
|
2119 |
}
|
alpar@100
|
2120 |
|
alpar@100
|
2121 |
virtual void add(const std::vector<Node>& nodes) {
|
alpar@209
|
2122 |
Parent::add(nodes);
|
alpar@209
|
2123 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
alpar@209
|
2124 |
Parent::set(nodes[i], INVALID);
|
alpar@209
|
2125 |
}
|
alpar@100
|
2126 |
}
|
alpar@100
|
2127 |
|
alpar@100
|
2128 |
virtual void build() {
|
alpar@209
|
2129 |
Parent::build();
|
alpar@209
|
2130 |
Node it;
|
alpar@209
|
2131 |
typename Parent::Notifier* nf = Parent::notifier();
|
alpar@209
|
2132 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
alpar@209
|
2133 |
Parent::set(it, INVALID);
|
alpar@209
|
2134 |
}
|
alpar@100
|
2135 |
}
|
alpar@100
|
2136 |
};
|
alpar@100
|
2137 |
|
alpar@100
|
2138 |
const Digraph &_g;
|
alpar@100
|
2139 |
AutoNodeMap _head;
|
alpar@100
|
2140 |
typename Digraph::template ArcMap<Arc> _parent;
|
alpar@100
|
2141 |
typename Digraph::template ArcMap<Arc> _left;
|
alpar@100
|
2142 |
typename Digraph::template ArcMap<Arc> _right;
|
alpar@209
|
2143 |
|
alpar@100
|
2144 |
class ArcLess {
|
alpar@100
|
2145 |
const Digraph &g;
|
alpar@100
|
2146 |
public:
|
alpar@100
|
2147 |
ArcLess(const Digraph &_g) : g(_g) {}
|
alpar@209
|
2148 |
bool operator()(Arc a,Arc b) const
|
alpar@100
|
2149 |
{
|
alpar@209
|
2150 |
return g.target(a)<g.target(b);
|
alpar@100
|
2151 |
}
|
alpar@100
|
2152 |
};
|
alpar@209
|
2153 |
|
alpar@100
|
2154 |
public:
|
alpar@209
|
2155 |
|
alpar@100
|
2156 |
///Constructor
|
alpar@100
|
2157 |
|
alpar@100
|
2158 |
///Constructor.
|
alpar@100
|
2159 |
///
|
alpar@100
|
2160 |
///It builds up the search database.
|
alpar@209
|
2161 |
DynArcLookUp(const Digraph &g)
|
alpar@209
|
2162 |
: _g(g),_head(g),_parent(g),_left(g),_right(g)
|
alpar@209
|
2163 |
{
|
alpar@100
|
2164 |
Parent::attach(_g.notifier(typename Digraph::Arc()));
|
alpar@209
|
2165 |
refresh();
|
alpar@100
|
2166 |
}
|
alpar@209
|
2167 |
|
alpar@100
|
2168 |
protected:
|
alpar@100
|
2169 |
|
alpar@100
|
2170 |
virtual void add(const Arc& arc) {
|
alpar@100
|
2171 |
insert(arc);
|
alpar@100
|
2172 |
}
|
alpar@100
|
2173 |
|
alpar@100
|
2174 |
virtual void add(const std::vector<Arc>& arcs) {
|
alpar@100
|
2175 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
alpar@209
|
2176 |
insert(arcs[i]);
|
alpar@100
|
2177 |
}
|
alpar@100
|
2178 |
}
|
alpar@100
|
2179 |
|
alpar@100
|
2180 |
virtual void erase(const Arc& arc) {
|
alpar@100
|
2181 |
remove(arc);
|
alpar@100
|
2182 |
}
|
alpar@100
|
2183 |
|
alpar@100
|
2184 |
virtual void erase(const std::vector<Arc>& arcs) {
|
alpar@100
|
2185 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
alpar@209
|
2186 |
remove(arcs[i]);
|
alpar@209
|
2187 |
}
|
alpar@100
|
2188 |
}
|
alpar@100
|
2189 |
|
alpar@100
|
2190 |
virtual void build() {
|
alpar@100
|
2191 |
refresh();
|
alpar@100
|
2192 |
}
|
alpar@100
|
2193 |
|
alpar@100
|
2194 |
virtual void clear() {
|
alpar@100
|
2195 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
alpar@209
|
2196 |
_head.set(n, INVALID);
|
alpar@100
|
2197 |
}
|
alpar@100
|
2198 |
}
|
alpar@100
|
2199 |
|
alpar@100
|
2200 |
void insert(Arc arc) {
|
alpar@100
|
2201 |
Node s = _g.source(arc);
|
alpar@100
|
2202 |
Node t = _g.target(arc);
|
alpar@100
|
2203 |
_left.set(arc, INVALID);
|
alpar@100
|
2204 |
_right.set(arc, INVALID);
|
alpar@209
|
2205 |
|
alpar@100
|
2206 |
Arc e = _head[s];
|
alpar@100
|
2207 |
if (e == INVALID) {
|
alpar@209
|
2208 |
_head.set(s, arc);
|
alpar@209
|
2209 |
_parent.set(arc, INVALID);
|
alpar@209
|
2210 |
return;
|
alpar@100
|
2211 |
}
|
alpar@100
|
2212 |
while (true) {
|
alpar@209
|
2213 |
if (t < _g.target(e)) {
|
alpar@209
|
2214 |
if (_left[e] == INVALID) {
|
alpar@209
|
2215 |
_left.set(e, arc);
|
alpar@209
|
2216 |
_parent.set(arc, e);
|
alpar@209
|
2217 |
splay(arc);
|
alpar@209
|
2218 |
return;
|
alpar@209
|
2219 |
} else {
|
alpar@209
|
2220 |
e = _left[e];
|
alpar@209
|
2221 |
}
|
alpar@209
|
2222 |
} else {
|
alpar@209
|
2223 |
if (_right[e] == INVALID) {
|
alpar@209
|
2224 |
_right.set(e, arc);
|
alpar@209
|
2225 |
_parent.set(arc, e);
|
alpar@209
|
2226 |
splay(arc);
|
alpar@209
|
2227 |
return;
|
alpar@209
|
2228 |
} else {
|
alpar@209
|
2229 |
e = _right[e];
|
alpar@209
|
2230 |
}
|
alpar@209
|
2231 |
}
|
alpar@100
|
2232 |
}
|
alpar@100
|
2233 |
}
|
alpar@100
|
2234 |
|
alpar@100
|
2235 |
void remove(Arc arc) {
|
alpar@100
|
2236 |
if (_left[arc] == INVALID) {
|
alpar@209
|
2237 |
if (_right[arc] != INVALID) {
|
alpar@209
|
2238 |
_parent.set(_right[arc], _parent[arc]);
|
alpar@209
|
2239 |
}
|
alpar@209
|
2240 |
if (_parent[arc] != INVALID) {
|
alpar@209
|
2241 |
if (_left[_parent[arc]] == arc) {
|
alpar@209
|
2242 |
_left.set(_parent[arc], _right[arc]);
|
alpar@209
|
2243 |
} else {
|
alpar@209
|
2244 |
_right.set(_parent[arc], _right[arc]);
|
alpar@209
|
2245 |
}
|
alpar@209
|
2246 |
} else {
|
alpar@209
|
2247 |
_head.set(_g.source(arc), _right[arc]);
|
alpar@209
|
2248 |
}
|
alpar@100
|
2249 |
} else if (_right[arc] == INVALID) {
|
alpar@209
|
2250 |
_parent.set(_left[arc], _parent[arc]);
|
alpar@209
|
2251 |
if (_parent[arc] != INVALID) {
|
alpar@209
|
2252 |
if (_left[_parent[arc]] == arc) {
|
alpar@209
|
2253 |
_left.set(_parent[arc], _left[arc]);
|
alpar@209
|
2254 |
} else {
|
alpar@209
|
2255 |
_right.set(_parent[arc], _left[arc]);
|
alpar@209
|
2256 |
}
|
alpar@209
|
2257 |
} else {
|
alpar@209
|
2258 |
_head.set(_g.source(arc), _left[arc]);
|
alpar@209
|
2259 |
}
|
alpar@100
|
2260 |
} else {
|
alpar@209
|
2261 |
Arc e = _left[arc];
|
alpar@209
|
2262 |
if (_right[e] != INVALID) {
|
alpar@209
|
2263 |
e = _right[e];
|
alpar@209
|
2264 |
while (_right[e] != INVALID) {
|
alpar@209
|
2265 |
e = _right[e];
|
alpar@209
|
2266 |
}
|
alpar@209
|
2267 |
Arc s = _parent[e];
|
alpar@209
|
2268 |
_right.set(_parent[e], _left[e]);
|
alpar@209
|
2269 |
if (_left[e] != INVALID) {
|
alpar@209
|
2270 |
_parent.set(_left[e], _parent[e]);
|
alpar@209
|
2271 |
}
|
alpar@209
|
2272 |
|
alpar@209
|
2273 |
_left.set(e, _left[arc]);
|
alpar@209
|
2274 |
_parent.set(_left[arc], e);
|
alpar@209
|
2275 |
_right.set(e, _right[arc]);
|
alpar@209
|
2276 |
_parent.set(_right[arc], e);
|
alpar@209
|
2277 |
|
alpar@209
|
2278 |
_parent.set(e, _parent[arc]);
|
alpar@209
|
2279 |
if (_parent[arc] != INVALID) {
|
alpar@209
|
2280 |
if (_left[_parent[arc]] == arc) {
|
alpar@209
|
2281 |
_left.set(_parent[arc], e);
|
alpar@209
|
2282 |
} else {
|
alpar@209
|
2283 |
_right.set(_parent[arc], e);
|
alpar@209
|
2284 |
}
|
alpar@209
|
2285 |
}
|
alpar@209
|
2286 |
splay(s);
|
alpar@209
|
2287 |
} else {
|
alpar@209
|
2288 |
_right.set(e, _right[arc]);
|
alpar@209
|
2289 |
_parent.set(_right[arc], e);
|
alpar@209
|
2290 |
|
alpar@209
|
2291 |
if (_parent[arc] != INVALID) {
|
alpar@209
|
2292 |
if (_left[_parent[arc]] == arc) {
|
alpar@209
|
2293 |
_left.set(_parent[arc], e);
|
alpar@209
|
2294 |
} else {
|
alpar@209
|
2295 |
_right.set(_parent[arc], e);
|
alpar@209
|
2296 |
}
|
alpar@209
|
2297 |
} else {
|
alpar@209
|
2298 |
_head.set(_g.source(arc), e);
|
alpar@209
|
2299 |
}
|
alpar@209
|
2300 |
}
|
alpar@100
|
2301 |
}
|
alpar@100
|
2302 |
}
|
alpar@100
|
2303 |
|
alpar@209
|
2304 |
Arc refreshRec(std::vector<Arc> &v,int a,int b)
|
alpar@100
|
2305 |
{
|
alpar@100
|
2306 |
int m=(a+b)/2;
|
alpar@100
|
2307 |
Arc me=v[m];
|
alpar@100
|
2308 |
if (a < m) {
|
alpar@209
|
2309 |
Arc left = refreshRec(v,a,m-1);
|
alpar@209
|
2310 |
_left.set(me, left);
|
alpar@209
|
2311 |
_parent.set(left, me);
|
alpar@100
|
2312 |
} else {
|
alpar@209
|
2313 |
_left.set(me, INVALID);
|
alpar@100
|
2314 |
}
|
alpar@100
|
2315 |
if (m < b) {
|
alpar@209
|
2316 |
Arc right = refreshRec(v,m+1,b);
|
alpar@209
|
2317 |
_right.set(me, right);
|
alpar@209
|
2318 |
_parent.set(right, me);
|
alpar@100
|
2319 |
} else {
|
alpar@209
|
2320 |
_right.set(me, INVALID);
|
alpar@100
|
2321 |
}
|
alpar@100
|
2322 |
return me;
|
alpar@100
|
2323 |
}
|
alpar@100
|
2324 |
|
alpar@100
|
2325 |
void refresh() {
|
alpar@100
|
2326 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
alpar@209
|
2327 |
std::vector<Arc> v;
|
alpar@209
|
2328 |
for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
|
alpar@209
|
2329 |
if(v.size()) {
|
alpar@209
|
2330 |
std::sort(v.begin(),v.end(),ArcLess(_g));
|
alpar@209
|
2331 |
Arc head = refreshRec(v,0,v.size()-1);
|
alpar@209
|
2332 |
_head.set(n, head);
|
alpar@209
|
2333 |
_parent.set(head, INVALID);
|
alpar@209
|
2334 |
}
|
alpar@209
|
2335 |
else _head.set(n, INVALID);
|
alpar@100
|
2336 |
}
|
alpar@100
|
2337 |
}
|
alpar@100
|
2338 |
|
alpar@209
|
2339 |
void zig(Arc v) {
|
alpar@100
|
2340 |
Arc w = _parent[v];
|
alpar@100
|
2341 |
_parent.set(v, _parent[w]);
|
alpar@100
|
2342 |
_parent.set(w, v);
|
alpar@100
|
2343 |
_left.set(w, _right[v]);
|
alpar@100
|
2344 |
_right.set(v, w);
|
alpar@100
|
2345 |
if (_parent[v] != INVALID) {
|
alpar@209
|
2346 |
if (_right[_parent[v]] == w) {
|
alpar@209
|
2347 |
_right.set(_parent[v], v);
|
alpar@209
|
2348 |
} else {
|
alpar@209
|
2349 |
_left.set(_parent[v], v);
|
alpar@209
|
2350 |
}
|
alpar@100
|
2351 |
}
|
alpar@100
|
2352 |
if (_left[w] != INVALID){
|
alpar@209
|
2353 |
_parent.set(_left[w], w);
|
alpar@100
|
2354 |
}
|
alpar@100
|
2355 |
}
|
alpar@100
|
2356 |
|
alpar@209
|
2357 |
void zag(Arc v) {
|
alpar@100
|
2358 |
Arc w = _parent[v];
|
alpar@100
|
2359 |
_parent.set(v, _parent[w]);
|
alpar@100
|
2360 |
_parent.set(w, v);
|
alpar@100
|
2361 |
_right.set(w, _left[v]);
|
alpar@100
|
2362 |
_left.set(v, w);
|
alpar@100
|
2363 |
if (_parent[v] != INVALID){
|
alpar@209
|
2364 |
if (_left[_parent[v]] == w) {
|
alpar@209
|
2365 |
_left.set(_parent[v], v);
|
alpar@209
|
2366 |
} else {
|
alpar@209
|
2367 |
_right.set(_parent[v], v);
|
alpar@209
|
2368 |
}
|
alpar@100
|
2369 |
}
|
alpar@100
|
2370 |
if (_right[w] != INVALID){
|
alpar@209
|
2371 |
_parent.set(_right[w], w);
|
alpar@100
|
2372 |
}
|
alpar@100
|
2373 |
}
|
alpar@100
|
2374 |
|
alpar@100
|
2375 |
void splay(Arc v) {
|
alpar@100
|
2376 |
while (_parent[v] != INVALID) {
|
alpar@209
|
2377 |
if (v == _left[_parent[v]]) {
|
alpar@209
|
2378 |
if (_parent[_parent[v]] == INVALID) {
|
alpar@209
|
2379 |
zig(v);
|
alpar@209
|
2380 |
} else {
|
alpar@209
|
2381 |
if (_parent[v] == _left[_parent[_parent[v]]]) {
|
alpar@209
|
2382 |
zig(_parent[v]);
|
alpar@209
|
2383 |
zig(v);
|
alpar@209
|
2384 |
} else {
|
alpar@209
|
2385 |
zig(v);
|
alpar@209
|
2386 |
zag(v);
|
alpar@209
|
2387 |
}
|
alpar@209
|
2388 |
}
|
alpar@209
|
2389 |
} else {
|
alpar@209
|
2390 |
if (_parent[_parent[v]] == INVALID) {
|
alpar@209
|
2391 |
zag(v);
|
alpar@209
|
2392 |
} else {
|
alpar@209
|
2393 |
if (_parent[v] == _left[_parent[_parent[v]]]) {
|
alpar@209
|
2394 |
zag(v);
|
alpar@209
|
2395 |
zig(v);
|
alpar@209
|
2396 |
} else {
|
alpar@209
|
2397 |
zag(_parent[v]);
|
alpar@209
|
2398 |
zag(v);
|
alpar@209
|
2399 |
}
|
alpar@209
|
2400 |
}
|
alpar@209
|
2401 |
}
|
alpar@100
|
2402 |
}
|
alpar@100
|
2403 |
_head[_g.source(v)] = v;
|
alpar@100
|
2404 |
}
|
alpar@100
|
2405 |
|
alpar@100
|
2406 |
|
alpar@100
|
2407 |
public:
|
alpar@209
|
2408 |
|
alpar@100
|
2409 |
///Find an arc between two nodes.
|
alpar@209
|
2410 |
|
alpar@100
|
2411 |
///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
|
alpar@100
|
2412 |
/// <em>d</em> is the number of outgoing arcs of \c s.
|
alpar@100
|
2413 |
///\param s The source node
|
alpar@100
|
2414 |
///\param t The target node
|
alpar@100
|
2415 |
///\return An arc from \c s to \c t if there exists,
|
alpar@100
|
2416 |
///\ref INVALID otherwise.
|
alpar@100
|
2417 |
Arc operator()(Node s, Node t) const
|
alpar@100
|
2418 |
{
|
deba@139
|
2419 |
Arc a = _head[s];
|
alpar@100
|
2420 |
while (true) {
|
alpar@209
|
2421 |
if (_g.target(a) == t) {
|
alpar@209
|
2422 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2423 |
return a;
|
alpar@209
|
2424 |
} else if (t < _g.target(a)) {
|
alpar@209
|
2425 |
if (_left[a] == INVALID) {
|
alpar@209
|
2426 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2427 |
return INVALID;
|
alpar@209
|
2428 |
} else {
|
alpar@209
|
2429 |
a = _left[a];
|
alpar@209
|
2430 |
}
|
alpar@209
|
2431 |
} else {
|
alpar@209
|
2432 |
if (_right[a] == INVALID) {
|
alpar@209
|
2433 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2434 |
return INVALID;
|
alpar@209
|
2435 |
} else {
|
alpar@209
|
2436 |
a = _right[a];
|
alpar@209
|
2437 |
}
|
alpar@209
|
2438 |
}
|
alpar@100
|
2439 |
}
|
alpar@100
|
2440 |
}
|
alpar@100
|
2441 |
|
alpar@100
|
2442 |
///Find the first arc between two nodes.
|
alpar@209
|
2443 |
|
alpar@100
|
2444 |
///Find the first arc between two nodes in time
|
alpar@100
|
2445 |
/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
|
alpar@209
|
2446 |
/// outgoing arcs of \c s.
|
alpar@209
|
2447 |
///\param s The source node
|
alpar@100
|
2448 |
///\param t The target node
|
alpar@100
|
2449 |
///\return An arc from \c s to \c t if there exists, \ref INVALID
|
alpar@100
|
2450 |
/// otherwise.
|
alpar@100
|
2451 |
Arc findFirst(Node s, Node t) const
|
alpar@100
|
2452 |
{
|
deba@139
|
2453 |
Arc a = _head[s];
|
alpar@100
|
2454 |
Arc r = INVALID;
|
alpar@100
|
2455 |
while (true) {
|
alpar@209
|
2456 |
if (_g.target(a) < t) {
|
alpar@209
|
2457 |
if (_right[a] == INVALID) {
|
alpar@209
|
2458 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2459 |
return r;
|
alpar@209
|
2460 |
} else {
|
alpar@209
|
2461 |
a = _right[a];
|
alpar@209
|
2462 |
}
|
alpar@209
|
2463 |
} else {
|
alpar@209
|
2464 |
if (_g.target(a) == t) {
|
alpar@209
|
2465 |
r = a;
|
alpar@209
|
2466 |
}
|
alpar@209
|
2467 |
if (_left[a] == INVALID) {
|
alpar@209
|
2468 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2469 |
return r;
|
alpar@209
|
2470 |
} else {
|
alpar@209
|
2471 |
a = _left[a];
|
alpar@209
|
2472 |
}
|
alpar@209
|
2473 |
}
|
alpar@100
|
2474 |
}
|
alpar@100
|
2475 |
}
|
alpar@100
|
2476 |
|
alpar@100
|
2477 |
///Find the next arc between two nodes.
|
alpar@209
|
2478 |
|
alpar@100
|
2479 |
///Find the next arc between two nodes in time
|
alpar@100
|
2480 |
/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
|
alpar@209
|
2481 |
/// outgoing arcs of \c s.
|
alpar@209
|
2482 |
///\param s The source node
|
alpar@100
|
2483 |
///\param t The target node
|
alpar@100
|
2484 |
///\return An arc from \c s to \c t if there exists, \ref INVALID
|
alpar@100
|
2485 |
/// otherwise.
|
alpar@100
|
2486 |
|
alpar@100
|
2487 |
///\note If \c e is not the result of the previous \c findFirst()
|
alpar@100
|
2488 |
///operation then the amorized time bound can not be guaranteed.
|
alpar@100
|
2489 |
#ifdef DOXYGEN
|
deba@139
|
2490 |
Arc findNext(Node s, Node t, Arc a) const
|
alpar@100
|
2491 |
#else
|
deba@139
|
2492 |
Arc findNext(Node, Node t, Arc a) const
|
alpar@100
|
2493 |
#endif
|
alpar@100
|
2494 |
{
|
deba@139
|
2495 |
if (_right[a] != INVALID) {
|
alpar@209
|
2496 |
a = _right[a];
|
alpar@209
|
2497 |
while (_left[a] != INVALID) {
|
alpar@209
|
2498 |
a = _left[a];
|
alpar@209
|
2499 |
}
|
alpar@209
|
2500 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@100
|
2501 |
} else {
|
alpar@209
|
2502 |
while (_parent[a] != INVALID && _right[_parent[a]] == a) {
|
alpar@209
|
2503 |
a = _parent[a];
|
alpar@209
|
2504 |
}
|
alpar@209
|
2505 |
if (_parent[a] == INVALID) {
|
alpar@209
|
2506 |
return INVALID;
|
alpar@209
|
2507 |
} else {
|
alpar@209
|
2508 |
a = _parent[a];
|
alpar@209
|
2509 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
alpar@209
|
2510 |
}
|
alpar@100
|
2511 |
}
|
deba@139
|
2512 |
if (_g.target(a) == t) return a;
|
alpar@209
|
2513 |
else return INVALID;
|
alpar@100
|
2514 |
}
|
alpar@100
|
2515 |
|
alpar@100
|
2516 |
};
|
alpar@100
|
2517 |
|
alpar@100
|
2518 |
///Fast arc look up between given endpoints.
|
alpar@209
|
2519 |
|
alpar@100
|
2520 |
///\ingroup gutils
|
alpar@100
|
2521 |
///Using this class, you can find an arc in a digraph from a given
|
alpar@100
|
2522 |
///source to a given target in time <em>O(log d)</em>,
|
alpar@100
|
2523 |
///where <em>d</em> is the out-degree of the source node.
|
alpar@100
|
2524 |
///
|
alpar@100
|
2525 |
///It is not possible to find \e all parallel arcs between two nodes.
|
alpar@100
|
2526 |
///Use \ref AllArcLookUp for this purpose.
|
alpar@100
|
2527 |
///
|
alpar@100
|
2528 |
///\warning This class is static, so you should refresh() (or at least
|
alpar@100
|
2529 |
///refresh(Node)) this data structure
|
alpar@100
|
2530 |
///whenever the digraph changes. This is a time consuming (superlinearly
|
alpar@100
|
2531 |
///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
|
alpar@100
|
2532 |
///
|
kpeter@157
|
2533 |
///\tparam G The type of the underlying digraph.
|
alpar@100
|
2534 |
///
|
alpar@100
|
2535 |
///\sa DynArcLookUp
|
alpar@209
|
2536 |
///\sa AllArcLookUp
|
alpar@100
|
2537 |
template<class G>
|
alpar@209
|
2538 |
class ArcLookUp
|
alpar@100
|
2539 |
{
|
alpar@100
|
2540 |
public:
|
deba@148
|
2541 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
alpar@100
|
2542 |
typedef G Digraph;
|
alpar@100
|
2543 |
|
alpar@100
|
2544 |
protected:
|
alpar@100
|
2545 |
const Digraph &_g;
|
alpar@100
|
2546 |
typename Digraph::template NodeMap<Arc> _head;
|
alpar@100
|
2547 |
typename Digraph::template ArcMap<Arc> _left;
|
alpar@100
|
2548 |
typename Digraph::template ArcMap<Arc> _right;
|
alpar@209
|
2549 |
|
alpar@100
|
2550 |
class ArcLess {
|
alpar@100
|
2551 |
const Digraph &g;
|
alpar@100
|
2552 |
public:
|
alpar@100
|
2553 |
ArcLess(const Digraph &_g) : g(_g) {}
|
alpar@209
|
2554 |
bool operator()(Arc a,Arc b) const
|
alpar@100
|
2555 |
{
|
alpar@209
|
2556 |
return g.target(a)<g.target(b);
|
alpar@100
|
2557 |
}
|
alpar@100
|
2558 |
};
|
alpar@209
|
2559 |
|
alpar@100
|
2560 |
public:
|
alpar@209
|
2561 |
|
alpar@100
|
2562 |
///Constructor
|
alpar@100
|
2563 |
|
alpar@100
|
2564 |
///Constructor.
|
alpar@100
|
2565 |
///
|
alpar@100
|
2566 |
///It builds up the search database, which remains valid until the digraph
|
alpar@100
|
2567 |
///changes.
|
alpar@100
|
2568 |
ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
|
alpar@209
|
2569 |
|
alpar@100
|
2570 |
private:
|
alpar@209
|
2571 |
Arc refreshRec(std::vector<Arc> &v,int a,int b)
|
alpar@100
|
2572 |
{
|
alpar@100
|
2573 |
int m=(a+b)/2;
|
alpar@100
|
2574 |
Arc me=v[m];
|
alpar@100
|
2575 |
_left[me] = a<m?refreshRec(v,a,m-1):INVALID;
|
alpar@100
|
2576 |
_right[me] = m<b?refreshRec(v,m+1,b):INVALID;
|
alpar@100
|
2577 |
return me;
|
alpar@100
|
2578 |
}
|
alpar@100
|
2579 |
public:
|
alpar@100
|
2580 |
///Refresh the data structure at a node.
|
alpar@100
|
2581 |
|
alpar@100
|
2582 |
///Build up the search database of node \c n.
|
alpar@100
|
2583 |
///
|
alpar@100
|
2584 |
///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
|
alpar@100
|
2585 |
///the number of the outgoing arcs of \c n.
|
alpar@209
|
2586 |
void refresh(Node n)
|
alpar@100
|
2587 |
{
|
alpar@100
|
2588 |
std::vector<Arc> v;
|
alpar@100
|
2589 |
for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
|
alpar@100
|
2590 |
if(v.size()) {
|
alpar@209
|
2591 |
std::sort(v.begin(),v.end(),ArcLess(_g));
|
alpar@209
|
2592 |
_head[n]=refreshRec(v,0,v.size()-1);
|
alpar@100
|
2593 |
}
|
alpar@100
|
2594 |
else _head[n]=INVALID;
|
alpar@100
|
2595 |
}
|
alpar@100
|
2596 |
///Refresh the full data structure.
|
alpar@100
|
2597 |
|
alpar@100
|
2598 |
///Build up the full search database. In fact, it simply calls
|
alpar@100
|
2599 |
///\ref refresh(Node) "refresh(n)" for each node \c n.
|
alpar@100
|
2600 |
///
|
alpar@100
|
2601 |
///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
|
alpar@100
|
2602 |
///the number of the arcs of \c n and <em>D</em> is the maximum
|
alpar@100
|
2603 |
///out-degree of the digraph.
|
alpar@100
|
2604 |
|
alpar@209
|
2605 |
void refresh()
|
alpar@100
|
2606 |
{
|
alpar@100
|
2607 |
for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
|
alpar@100
|
2608 |
}
|
alpar@209
|
2609 |
|
alpar@100
|
2610 |
///Find an arc between two nodes.
|
alpar@209
|
2611 |
|
alpar@100
|
2612 |
///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
|
alpar@100
|
2613 |
/// <em>d</em> is the number of outgoing arcs of \c s.
|
alpar@100
|
2614 |
///\param s The source node
|
alpar@100
|
2615 |
///\param t The target node
|
alpar@100
|
2616 |
///\return An arc from \c s to \c t if there exists,
|
alpar@100
|
2617 |
///\ref INVALID otherwise.
|
alpar@100
|
2618 |
///
|
alpar@100
|
2619 |
///\warning If you change the digraph, refresh() must be called before using
|
alpar@100
|
2620 |
///this operator. If you change the outgoing arcs of
|
alpar@100
|
2621 |
///a single node \c n, then
|
alpar@100
|
2622 |
///\ref refresh(Node) "refresh(n)" is enough.
|
alpar@100
|
2623 |
///
|
alpar@100
|
2624 |
Arc operator()(Node s, Node t) const
|
alpar@100
|
2625 |
{
|
alpar@100
|
2626 |
Arc e;
|
alpar@100
|
2627 |
for(e=_head[s];
|
alpar@209
|
2628 |
e!=INVALID&&_g.target(e)!=t;
|
alpar@209
|
2629 |
e = t < _g.target(e)?_left[e]:_right[e]) ;
|
alpar@100
|
2630 |
return e;
|
alpar@100
|
2631 |
}
|
alpar@100
|
2632 |
|
alpar@100
|
2633 |
};
|
alpar@100
|
2634 |
|
alpar@100
|
2635 |
///Fast look up of all arcs between given endpoints.
|
alpar@209
|
2636 |
|
alpar@100
|
2637 |
///\ingroup gutils
|
alpar@100
|
2638 |
///This class is the same as \ref ArcLookUp, with the addition
|
alpar@100
|
2639 |
///that it makes it possible to find all arcs between given endpoints.
|
alpar@100
|
2640 |
///
|
alpar@100
|
2641 |
///\warning This class is static, so you should refresh() (or at least
|
alpar@100
|
2642 |
///refresh(Node)) this data structure
|
alpar@100
|
2643 |
///whenever the digraph changes. This is a time consuming (superlinearly
|
alpar@100
|
2644 |
///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).
|
alpar@100
|
2645 |
///
|
kpeter@157
|
2646 |
///\tparam G The type of the underlying digraph.
|
alpar@100
|
2647 |
///
|
alpar@100
|
2648 |
///\sa DynArcLookUp
|
alpar@209
|
2649 |
///\sa ArcLookUp
|
alpar@100
|
2650 |
template<class G>
|
alpar@100
|
2651 |
class AllArcLookUp : public ArcLookUp<G>
|
alpar@100
|
2652 |
{
|
alpar@100
|
2653 |
using ArcLookUp<G>::_g;
|
alpar@100
|
2654 |
using ArcLookUp<G>::_right;
|
alpar@100
|
2655 |
using ArcLookUp<G>::_left;
|
alpar@100
|
2656 |
using ArcLookUp<G>::_head;
|
alpar@100
|
2657 |
|
deba@148
|
2658 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
alpar@100
|
2659 |
typedef G Digraph;
|
alpar@209
|
2660 |
|
alpar@100
|
2661 |
typename Digraph::template ArcMap<Arc> _next;
|
alpar@209
|
2662 |
|
alpar@100
|
2663 |
Arc refreshNext(Arc head,Arc next=INVALID)
|
alpar@100
|
2664 |
{
|
alpar@100
|
2665 |
if(head==INVALID) return next;
|
alpar@100
|
2666 |
else {
|
alpar@209
|
2667 |
next=refreshNext(_right[head],next);
|
alpar@209
|
2668 |
// _next[head]=next;
|
alpar@209
|
2669 |
_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
|
alpar@209
|
2670 |
? next : INVALID;
|
alpar@209
|
2671 |
return refreshNext(_left[head],head);
|
alpar@100
|
2672 |
}
|
alpar@100
|
2673 |
}
|
alpar@209
|
2674 |
|
alpar@100
|
2675 |
void refreshNext()
|
alpar@100
|
2676 |
{
|
alpar@100
|
2677 |
for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
|
alpar@100
|
2678 |
}
|
alpar@209
|
2679 |
|
alpar@100
|
2680 |
public:
|
alpar@100
|
2681 |
///Constructor
|
alpar@100
|
2682 |
|
alpar@100
|
2683 |
///Constructor.
|
alpar@100
|
2684 |
///
|
alpar@100
|
2685 |
///It builds up the search database, which remains valid until the digraph
|
alpar@100
|
2686 |
///changes.
|
alpar@100
|
2687 |
AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
|
alpar@100
|
2688 |
|
alpar@100
|
2689 |
///Refresh the data structure at a node.
|
alpar@100
|
2690 |
|
alpar@100
|
2691 |
///Build up the search database of node \c n.
|
alpar@100
|
2692 |
///
|
alpar@100
|
2693 |
///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is
|
alpar@100
|
2694 |
///the number of the outgoing arcs of \c n.
|
alpar@209
|
2695 |
|
alpar@209
|
2696 |
void refresh(Node n)
|
alpar@100
|
2697 |
{
|
alpar@100
|
2698 |
ArcLookUp<G>::refresh(n);
|
alpar@100
|
2699 |
refreshNext(_head[n]);
|
alpar@100
|
2700 |
}
|
alpar@209
|
2701 |
|
alpar@100
|
2702 |
///Refresh the full data structure.
|
alpar@100
|
2703 |
|
alpar@100
|
2704 |
///Build up the full search database. In fact, it simply calls
|
alpar@100
|
2705 |
///\ref refresh(Node) "refresh(n)" for each node \c n.
|
alpar@100
|
2706 |
///
|
alpar@100
|
2707 |
///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is
|
alpar@100
|
2708 |
///the number of the arcs of \c n and <em>D</em> is the maximum
|
alpar@100
|
2709 |
///out-degree of the digraph.
|
alpar@100
|
2710 |
|
alpar@209
|
2711 |
void refresh()
|
alpar@100
|
2712 |
{
|
alpar@100
|
2713 |
for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
|
alpar@100
|
2714 |
}
|
alpar@209
|
2715 |
|
alpar@100
|
2716 |
///Find an arc between two nodes.
|
alpar@209
|
2717 |
|
alpar@100
|
2718 |
///Find an arc between two nodes.
|
alpar@100
|
2719 |
///\param s The source node
|
alpar@100
|
2720 |
///\param t The target node
|
alpar@100
|
2721 |
///\param prev The previous arc between \c s and \c t. It it is INVALID or
|
alpar@100
|
2722 |
///not given, the operator finds the first appropriate arc.
|
alpar@100
|
2723 |
///\return An arc from \c s to \c t after \c prev or
|
alpar@100
|
2724 |
///\ref INVALID if there is no more.
|
alpar@100
|
2725 |
///
|
alpar@100
|
2726 |
///For example, you can count the number of arcs from \c u to \c v in the
|
alpar@100
|
2727 |
///following way.
|
alpar@100
|
2728 |
///\code
|
alpar@100
|
2729 |
///AllArcLookUp<ListDigraph> ae(g);
|
alpar@100
|
2730 |
///...
|
alpar@100
|
2731 |
///int n=0;
|
alpar@100
|
2732 |
///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++;
|
alpar@100
|
2733 |
///\endcode
|
alpar@100
|
2734 |
///
|
alpar@100
|
2735 |
///Finding the first arc take <em>O(</em>log<em>d)</em> time, where
|
alpar@100
|
2736 |
/// <em>d</em> is the number of outgoing arcs of \c s. Then, the
|
alpar@100
|
2737 |
///consecutive arcs are found in constant time.
|
alpar@100
|
2738 |
///
|
alpar@100
|
2739 |
///\warning If you change the digraph, refresh() must be called before using
|
alpar@100
|
2740 |
///this operator. If you change the outgoing arcs of
|
alpar@100
|
2741 |
///a single node \c n, then
|
alpar@100
|
2742 |
///\ref refresh(Node) "refresh(n)" is enough.
|
alpar@100
|
2743 |
///
|
alpar@100
|
2744 |
#ifdef DOXYGEN
|
alpar@100
|
2745 |
Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
|
alpar@100
|
2746 |
#else
|
alpar@100
|
2747 |
using ArcLookUp<G>::operator() ;
|
alpar@100
|
2748 |
Arc operator()(Node s, Node t, Arc prev) const
|
alpar@100
|
2749 |
{
|
alpar@100
|
2750 |
return prev==INVALID?(*this)(s,t):_next[prev];
|
alpar@100
|
2751 |
}
|
alpar@100
|
2752 |
#endif
|
alpar@209
|
2753 |
|
alpar@100
|
2754 |
};
|
alpar@100
|
2755 |
|
alpar@100
|
2756 |
/// @}
|
alpar@100
|
2757 |
|
alpar@100
|
2758 |
} //END OF NAMESPACE LEMON
|
alpar@100
|
2759 |
|
alpar@100
|
2760 |
#endif
|