deba@220
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
deba@220
|
2 |
*
|
deba@220
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
deba@220
|
4 |
*
|
deba@220
|
5 |
* Copyright (C) 2003-2008
|
deba@220
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
deba@220
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
deba@220
|
8 |
*
|
deba@220
|
9 |
* Permission to use, modify and distribute this software is granted
|
deba@220
|
10 |
* provided that this copyright notice appears in all copies. For
|
deba@220
|
11 |
* precise terms see the accompanying LICENSE file.
|
deba@220
|
12 |
*
|
deba@220
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
deba@220
|
14 |
* express or implied, and with no claim as to its suitability for any
|
deba@220
|
15 |
* purpose.
|
deba@220
|
16 |
*
|
deba@220
|
17 |
*/
|
deba@220
|
18 |
|
deba@220
|
19 |
#ifndef LEMON_CORE_H
|
deba@220
|
20 |
#define LEMON_CORE_H
|
deba@220
|
21 |
|
deba@220
|
22 |
#include <vector>
|
deba@220
|
23 |
#include <algorithm>
|
deba@220
|
24 |
|
deba@220
|
25 |
#include <lemon/bits/enable_if.h>
|
deba@220
|
26 |
#include <lemon/bits/traits.h>
|
alpar@327
|
27 |
#include <lemon/assert.h>
|
deba@220
|
28 |
|
deba@220
|
29 |
///\file
|
deba@220
|
30 |
///\brief LEMON core utilities.
|
kpeter@229
|
31 |
///
|
kpeter@229
|
32 |
///This header file contains core utilities for LEMON.
|
deba@233
|
33 |
///It is automatically included by all graph types, therefore it usually
|
kpeter@229
|
34 |
///do not have to be included directly.
|
deba@220
|
35 |
|
deba@220
|
36 |
namespace lemon {
|
deba@220
|
37 |
|
deba@220
|
38 |
/// \brief Dummy type to make it easier to create invalid iterators.
|
deba@220
|
39 |
///
|
deba@220
|
40 |
/// Dummy type to make it easier to create invalid iterators.
|
deba@220
|
41 |
/// See \ref INVALID for the usage.
|
deba@220
|
42 |
struct Invalid {
|
deba@220
|
43 |
public:
|
deba@220
|
44 |
bool operator==(Invalid) { return true; }
|
deba@220
|
45 |
bool operator!=(Invalid) { return false; }
|
deba@220
|
46 |
bool operator< (Invalid) { return false; }
|
deba@220
|
47 |
};
|
deba@220
|
48 |
|
deba@220
|
49 |
/// \brief Invalid iterators.
|
deba@220
|
50 |
///
|
deba@220
|
51 |
/// \ref Invalid is a global type that converts to each iterator
|
deba@220
|
52 |
/// in such a way that the value of the target iterator will be invalid.
|
deba@220
|
53 |
#ifdef LEMON_ONLY_TEMPLATES
|
deba@220
|
54 |
const Invalid INVALID = Invalid();
|
deba@220
|
55 |
#else
|
deba@220
|
56 |
extern const Invalid INVALID;
|
deba@220
|
57 |
#endif
|
deba@220
|
58 |
|
deba@220
|
59 |
/// \addtogroup gutils
|
deba@220
|
60 |
/// @{
|
deba@220
|
61 |
|
kpeter@304
|
62 |
///Create convenience typedefs for the digraph types and iterators
|
deba@220
|
63 |
|
kpeter@282
|
64 |
///This \c \#define creates convenient type definitions for the following
|
kpeter@282
|
65 |
///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,
|
deba@220
|
66 |
///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,
|
deba@220
|
67 |
///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.
|
deba@220
|
68 |
///
|
deba@220
|
69 |
///\note If the graph type is a dependent type, ie. the graph type depend
|
deba@220
|
70 |
///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()
|
deba@220
|
71 |
///macro.
|
deba@220
|
72 |
#define DIGRAPH_TYPEDEFS(Digraph) \
|
deba@220
|
73 |
typedef Digraph::Node Node; \
|
deba@220
|
74 |
typedef Digraph::NodeIt NodeIt; \
|
deba@220
|
75 |
typedef Digraph::Arc Arc; \
|
deba@220
|
76 |
typedef Digraph::ArcIt ArcIt; \
|
deba@220
|
77 |
typedef Digraph::InArcIt InArcIt; \
|
deba@220
|
78 |
typedef Digraph::OutArcIt OutArcIt; \
|
deba@220
|
79 |
typedef Digraph::NodeMap<bool> BoolNodeMap; \
|
deba@220
|
80 |
typedef Digraph::NodeMap<int> IntNodeMap; \
|
deba@220
|
81 |
typedef Digraph::NodeMap<double> DoubleNodeMap; \
|
deba@220
|
82 |
typedef Digraph::ArcMap<bool> BoolArcMap; \
|
deba@220
|
83 |
typedef Digraph::ArcMap<int> IntArcMap; \
|
kpeter@304
|
84 |
typedef Digraph::ArcMap<double> DoubleArcMap
|
deba@220
|
85 |
|
kpeter@304
|
86 |
///Create convenience typedefs for the digraph types and iterators
|
deba@220
|
87 |
|
deba@220
|
88 |
///\see DIGRAPH_TYPEDEFS
|
deba@220
|
89 |
///
|
deba@220
|
90 |
///\note Use this macro, if the graph type is a dependent type,
|
deba@220
|
91 |
///ie. the graph type depend on a template parameter.
|
deba@220
|
92 |
#define TEMPLATE_DIGRAPH_TYPEDEFS(Digraph) \
|
deba@220
|
93 |
typedef typename Digraph::Node Node; \
|
deba@220
|
94 |
typedef typename Digraph::NodeIt NodeIt; \
|
deba@220
|
95 |
typedef typename Digraph::Arc Arc; \
|
deba@220
|
96 |
typedef typename Digraph::ArcIt ArcIt; \
|
deba@220
|
97 |
typedef typename Digraph::InArcIt InArcIt; \
|
deba@220
|
98 |
typedef typename Digraph::OutArcIt OutArcIt; \
|
deba@220
|
99 |
typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \
|
deba@220
|
100 |
typedef typename Digraph::template NodeMap<int> IntNodeMap; \
|
deba@220
|
101 |
typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \
|
deba@220
|
102 |
typedef typename Digraph::template ArcMap<bool> BoolArcMap; \
|
deba@220
|
103 |
typedef typename Digraph::template ArcMap<int> IntArcMap; \
|
kpeter@304
|
104 |
typedef typename Digraph::template ArcMap<double> DoubleArcMap
|
deba@220
|
105 |
|
kpeter@304
|
106 |
///Create convenience typedefs for the graph types and iterators
|
deba@220
|
107 |
|
kpeter@282
|
108 |
///This \c \#define creates the same convenient type definitions as defined
|
deba@220
|
109 |
///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates
|
deba@220
|
110 |
///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap,
|
deba@220
|
111 |
///\c DoubleEdgeMap.
|
deba@220
|
112 |
///
|
deba@220
|
113 |
///\note If the graph type is a dependent type, ie. the graph type depend
|
kpeter@282
|
114 |
///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS()
|
deba@220
|
115 |
///macro.
|
deba@220
|
116 |
#define GRAPH_TYPEDEFS(Graph) \
|
deba@220
|
117 |
DIGRAPH_TYPEDEFS(Graph); \
|
deba@220
|
118 |
typedef Graph::Edge Edge; \
|
deba@220
|
119 |
typedef Graph::EdgeIt EdgeIt; \
|
deba@220
|
120 |
typedef Graph::IncEdgeIt IncEdgeIt; \
|
deba@220
|
121 |
typedef Graph::EdgeMap<bool> BoolEdgeMap; \
|
deba@220
|
122 |
typedef Graph::EdgeMap<int> IntEdgeMap; \
|
kpeter@304
|
123 |
typedef Graph::EdgeMap<double> DoubleEdgeMap
|
deba@220
|
124 |
|
kpeter@304
|
125 |
///Create convenience typedefs for the graph types and iterators
|
deba@220
|
126 |
|
deba@220
|
127 |
///\see GRAPH_TYPEDEFS
|
deba@220
|
128 |
///
|
deba@220
|
129 |
///\note Use this macro, if the graph type is a dependent type,
|
deba@220
|
130 |
///ie. the graph type depend on a template parameter.
|
deba@220
|
131 |
#define TEMPLATE_GRAPH_TYPEDEFS(Graph) \
|
deba@220
|
132 |
TEMPLATE_DIGRAPH_TYPEDEFS(Graph); \
|
deba@220
|
133 |
typedef typename Graph::Edge Edge; \
|
deba@220
|
134 |
typedef typename Graph::EdgeIt EdgeIt; \
|
deba@220
|
135 |
typedef typename Graph::IncEdgeIt IncEdgeIt; \
|
deba@220
|
136 |
typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \
|
deba@220
|
137 |
typedef typename Graph::template EdgeMap<int> IntEdgeMap; \
|
kpeter@304
|
138 |
typedef typename Graph::template EdgeMap<double> DoubleEdgeMap
|
deba@220
|
139 |
|
kpeter@282
|
140 |
/// \brief Function to count the items in a graph.
|
deba@220
|
141 |
///
|
kpeter@282
|
142 |
/// This function counts the items (nodes, arcs etc.) in a graph.
|
kpeter@282
|
143 |
/// The complexity of the function is linear because
|
deba@220
|
144 |
/// it iterates on all of the items.
|
deba@220
|
145 |
template <typename Graph, typename Item>
|
deba@220
|
146 |
inline int countItems(const Graph& g) {
|
deba@220
|
147 |
typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt;
|
deba@220
|
148 |
int num = 0;
|
deba@220
|
149 |
for (ItemIt it(g); it != INVALID; ++it) {
|
deba@220
|
150 |
++num;
|
deba@220
|
151 |
}
|
deba@220
|
152 |
return num;
|
deba@220
|
153 |
}
|
deba@220
|
154 |
|
deba@220
|
155 |
// Node counting:
|
deba@220
|
156 |
|
deba@220
|
157 |
namespace _core_bits {
|
deba@220
|
158 |
|
deba@220
|
159 |
template <typename Graph, typename Enable = void>
|
deba@220
|
160 |
struct CountNodesSelector {
|
deba@220
|
161 |
static int count(const Graph &g) {
|
deba@220
|
162 |
return countItems<Graph, typename Graph::Node>(g);
|
deba@220
|
163 |
}
|
deba@220
|
164 |
};
|
deba@220
|
165 |
|
deba@220
|
166 |
template <typename Graph>
|
deba@220
|
167 |
struct CountNodesSelector<
|
deba@220
|
168 |
Graph, typename
|
deba@220
|
169 |
enable_if<typename Graph::NodeNumTag, void>::type>
|
deba@220
|
170 |
{
|
deba@220
|
171 |
static int count(const Graph &g) {
|
deba@220
|
172 |
return g.nodeNum();
|
deba@220
|
173 |
}
|
deba@220
|
174 |
};
|
deba@220
|
175 |
}
|
deba@220
|
176 |
|
deba@220
|
177 |
/// \brief Function to count the nodes in the graph.
|
deba@220
|
178 |
///
|
deba@220
|
179 |
/// This function counts the nodes in the graph.
|
kpeter@282
|
180 |
/// The complexity of the function is <em>O</em>(<em>n</em>), but for some
|
kpeter@282
|
181 |
/// graph structures it is specialized to run in <em>O</em>(1).
|
deba@220
|
182 |
///
|
kpeter@282
|
183 |
/// \note If the graph contains a \c nodeNum() member function and a
|
kpeter@282
|
184 |
/// \c NodeNumTag tag then this function calls directly the member
|
deba@220
|
185 |
/// function to query the cardinality of the node set.
|
deba@220
|
186 |
template <typename Graph>
|
deba@220
|
187 |
inline int countNodes(const Graph& g) {
|
deba@220
|
188 |
return _core_bits::CountNodesSelector<Graph>::count(g);
|
deba@220
|
189 |
}
|
deba@220
|
190 |
|
deba@220
|
191 |
// Arc counting:
|
deba@220
|
192 |
|
deba@220
|
193 |
namespace _core_bits {
|
deba@220
|
194 |
|
deba@220
|
195 |
template <typename Graph, typename Enable = void>
|
deba@220
|
196 |
struct CountArcsSelector {
|
deba@220
|
197 |
static int count(const Graph &g) {
|
deba@220
|
198 |
return countItems<Graph, typename Graph::Arc>(g);
|
deba@220
|
199 |
}
|
deba@220
|
200 |
};
|
deba@220
|
201 |
|
deba@220
|
202 |
template <typename Graph>
|
deba@220
|
203 |
struct CountArcsSelector<
|
deba@220
|
204 |
Graph,
|
deba@220
|
205 |
typename enable_if<typename Graph::ArcNumTag, void>::type>
|
deba@220
|
206 |
{
|
deba@220
|
207 |
static int count(const Graph &g) {
|
deba@220
|
208 |
return g.arcNum();
|
deba@220
|
209 |
}
|
deba@220
|
210 |
};
|
deba@220
|
211 |
}
|
deba@220
|
212 |
|
deba@220
|
213 |
/// \brief Function to count the arcs in the graph.
|
deba@220
|
214 |
///
|
deba@220
|
215 |
/// This function counts the arcs in the graph.
|
kpeter@282
|
216 |
/// The complexity of the function is <em>O</em>(<em>m</em>), but for some
|
kpeter@282
|
217 |
/// graph structures it is specialized to run in <em>O</em>(1).
|
deba@220
|
218 |
///
|
kpeter@282
|
219 |
/// \note If the graph contains a \c arcNum() member function and a
|
kpeter@282
|
220 |
/// \c ArcNumTag tag then this function calls directly the member
|
deba@220
|
221 |
/// function to query the cardinality of the arc set.
|
deba@220
|
222 |
template <typename Graph>
|
deba@220
|
223 |
inline int countArcs(const Graph& g) {
|
deba@220
|
224 |
return _core_bits::CountArcsSelector<Graph>::count(g);
|
deba@220
|
225 |
}
|
deba@220
|
226 |
|
deba@220
|
227 |
// Edge counting:
|
kpeter@282
|
228 |
|
deba@220
|
229 |
namespace _core_bits {
|
deba@220
|
230 |
|
deba@220
|
231 |
template <typename Graph, typename Enable = void>
|
deba@220
|
232 |
struct CountEdgesSelector {
|
deba@220
|
233 |
static int count(const Graph &g) {
|
deba@220
|
234 |
return countItems<Graph, typename Graph::Edge>(g);
|
deba@220
|
235 |
}
|
deba@220
|
236 |
};
|
deba@220
|
237 |
|
deba@220
|
238 |
template <typename Graph>
|
deba@220
|
239 |
struct CountEdgesSelector<
|
deba@220
|
240 |
Graph,
|
deba@220
|
241 |
typename enable_if<typename Graph::EdgeNumTag, void>::type>
|
deba@220
|
242 |
{
|
deba@220
|
243 |
static int count(const Graph &g) {
|
deba@220
|
244 |
return g.edgeNum();
|
deba@220
|
245 |
}
|
deba@220
|
246 |
};
|
deba@220
|
247 |
}
|
deba@220
|
248 |
|
deba@220
|
249 |
/// \brief Function to count the edges in the graph.
|
deba@220
|
250 |
///
|
deba@220
|
251 |
/// This function counts the edges in the graph.
|
kpeter@282
|
252 |
/// The complexity of the function is <em>O</em>(<em>m</em>), but for some
|
kpeter@282
|
253 |
/// graph structures it is specialized to run in <em>O</em>(1).
|
deba@220
|
254 |
///
|
kpeter@282
|
255 |
/// \note If the graph contains a \c edgeNum() member function and a
|
kpeter@282
|
256 |
/// \c EdgeNumTag tag then this function calls directly the member
|
deba@220
|
257 |
/// function to query the cardinality of the edge set.
|
deba@220
|
258 |
template <typename Graph>
|
deba@220
|
259 |
inline int countEdges(const Graph& g) {
|
deba@220
|
260 |
return _core_bits::CountEdgesSelector<Graph>::count(g);
|
deba@220
|
261 |
|
deba@220
|
262 |
}
|
deba@220
|
263 |
|
deba@220
|
264 |
|
deba@220
|
265 |
template <typename Graph, typename DegIt>
|
deba@220
|
266 |
inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) {
|
deba@220
|
267 |
int num = 0;
|
deba@220
|
268 |
for (DegIt it(_g, _n); it != INVALID; ++it) {
|
deba@220
|
269 |
++num;
|
deba@220
|
270 |
}
|
deba@220
|
271 |
return num;
|
deba@220
|
272 |
}
|
deba@220
|
273 |
|
deba@220
|
274 |
/// \brief Function to count the number of the out-arcs from node \c n.
|
deba@220
|
275 |
///
|
deba@220
|
276 |
/// This function counts the number of the out-arcs from node \c n
|
kpeter@282
|
277 |
/// in the graph \c g.
|
deba@220
|
278 |
template <typename Graph>
|
kpeter@282
|
279 |
inline int countOutArcs(const Graph& g, const typename Graph::Node& n) {
|
kpeter@282
|
280 |
return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n);
|
deba@220
|
281 |
}
|
deba@220
|
282 |
|
deba@220
|
283 |
/// \brief Function to count the number of the in-arcs to node \c n.
|
deba@220
|
284 |
///
|
deba@220
|
285 |
/// This function counts the number of the in-arcs to node \c n
|
kpeter@282
|
286 |
/// in the graph \c g.
|
deba@220
|
287 |
template <typename Graph>
|
kpeter@282
|
288 |
inline int countInArcs(const Graph& g, const typename Graph::Node& n) {
|
kpeter@282
|
289 |
return countNodeDegree<Graph, typename Graph::InArcIt>(g, n);
|
deba@220
|
290 |
}
|
deba@220
|
291 |
|
deba@220
|
292 |
/// \brief Function to count the number of the inc-edges to node \c n.
|
deba@220
|
293 |
///
|
deba@220
|
294 |
/// This function counts the number of the inc-edges to node \c n
|
kpeter@282
|
295 |
/// in the undirected graph \c g.
|
deba@220
|
296 |
template <typename Graph>
|
kpeter@282
|
297 |
inline int countIncEdges(const Graph& g, const typename Graph::Node& n) {
|
kpeter@282
|
298 |
return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n);
|
deba@220
|
299 |
}
|
deba@220
|
300 |
|
deba@220
|
301 |
namespace _core_bits {
|
deba@220
|
302 |
|
deba@220
|
303 |
template <typename Digraph, typename Item, typename RefMap>
|
deba@220
|
304 |
class MapCopyBase {
|
deba@220
|
305 |
public:
|
deba@220
|
306 |
virtual void copy(const Digraph& from, const RefMap& refMap) = 0;
|
deba@220
|
307 |
|
deba@220
|
308 |
virtual ~MapCopyBase() {}
|
deba@220
|
309 |
};
|
deba@220
|
310 |
|
deba@220
|
311 |
template <typename Digraph, typename Item, typename RefMap,
|
kpeter@282
|
312 |
typename FromMap, typename ToMap>
|
deba@220
|
313 |
class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
deba@220
|
314 |
public:
|
deba@220
|
315 |
|
kpeter@282
|
316 |
MapCopy(const FromMap& map, ToMap& tmap)
|
kpeter@282
|
317 |
: _map(map), _tmap(tmap) {}
|
deba@220
|
318 |
|
deba@220
|
319 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
deba@220
|
320 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
deba@220
|
321 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
deba@220
|
322 |
_tmap.set(refMap[it], _map[it]);
|
deba@220
|
323 |
}
|
deba@220
|
324 |
}
|
deba@220
|
325 |
|
deba@220
|
326 |
private:
|
kpeter@282
|
327 |
const FromMap& _map;
|
deba@220
|
328 |
ToMap& _tmap;
|
deba@220
|
329 |
};
|
deba@220
|
330 |
|
deba@220
|
331 |
template <typename Digraph, typename Item, typename RefMap, typename It>
|
deba@220
|
332 |
class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
deba@220
|
333 |
public:
|
deba@220
|
334 |
|
kpeter@282
|
335 |
ItemCopy(const Item& item, It& it) : _item(item), _it(it) {}
|
deba@220
|
336 |
|
deba@220
|
337 |
virtual void copy(const Digraph&, const RefMap& refMap) {
|
deba@220
|
338 |
_it = refMap[_item];
|
deba@220
|
339 |
}
|
deba@220
|
340 |
|
deba@220
|
341 |
private:
|
kpeter@282
|
342 |
Item _item;
|
deba@220
|
343 |
It& _it;
|
deba@220
|
344 |
};
|
deba@220
|
345 |
|
deba@220
|
346 |
template <typename Digraph, typename Item, typename RefMap, typename Ref>
|
deba@220
|
347 |
class RefCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
deba@220
|
348 |
public:
|
deba@220
|
349 |
|
deba@220
|
350 |
RefCopy(Ref& map) : _map(map) {}
|
deba@220
|
351 |
|
deba@220
|
352 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
deba@220
|
353 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
deba@220
|
354 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
deba@220
|
355 |
_map.set(it, refMap[it]);
|
deba@220
|
356 |
}
|
deba@220
|
357 |
}
|
deba@220
|
358 |
|
deba@220
|
359 |
private:
|
deba@220
|
360 |
Ref& _map;
|
deba@220
|
361 |
};
|
deba@220
|
362 |
|
deba@220
|
363 |
template <typename Digraph, typename Item, typename RefMap,
|
deba@220
|
364 |
typename CrossRef>
|
deba@220
|
365 |
class CrossRefCopy : public MapCopyBase<Digraph, Item, RefMap> {
|
deba@220
|
366 |
public:
|
deba@220
|
367 |
|
deba@220
|
368 |
CrossRefCopy(CrossRef& cmap) : _cmap(cmap) {}
|
deba@220
|
369 |
|
deba@220
|
370 |
virtual void copy(const Digraph& digraph, const RefMap& refMap) {
|
deba@220
|
371 |
typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;
|
deba@220
|
372 |
for (ItemIt it(digraph); it != INVALID; ++it) {
|
deba@220
|
373 |
_cmap.set(refMap[it], it);
|
deba@220
|
374 |
}
|
deba@220
|
375 |
}
|
deba@220
|
376 |
|
deba@220
|
377 |
private:
|
deba@220
|
378 |
CrossRef& _cmap;
|
deba@220
|
379 |
};
|
deba@220
|
380 |
|
deba@220
|
381 |
template <typename Digraph, typename Enable = void>
|
deba@220
|
382 |
struct DigraphCopySelector {
|
deba@220
|
383 |
template <typename From, typename NodeRefMap, typename ArcRefMap>
|
kpeter@282
|
384 |
static void copy(const From& from, Digraph &to,
|
deba@220
|
385 |
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
|
deba@220
|
386 |
for (typename From::NodeIt it(from); it != INVALID; ++it) {
|
deba@220
|
387 |
nodeRefMap[it] = to.addNode();
|
deba@220
|
388 |
}
|
deba@220
|
389 |
for (typename From::ArcIt it(from); it != INVALID; ++it) {
|
deba@220
|
390 |
arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
|
deba@220
|
391 |
nodeRefMap[from.target(it)]);
|
deba@220
|
392 |
}
|
deba@220
|
393 |
}
|
deba@220
|
394 |
};
|
deba@220
|
395 |
|
deba@220
|
396 |
template <typename Digraph>
|
deba@220
|
397 |
struct DigraphCopySelector<
|
deba@220
|
398 |
Digraph,
|
deba@220
|
399 |
typename enable_if<typename Digraph::BuildTag, void>::type>
|
deba@220
|
400 |
{
|
deba@220
|
401 |
template <typename From, typename NodeRefMap, typename ArcRefMap>
|
kpeter@282
|
402 |
static void copy(const From& from, Digraph &to,
|
deba@220
|
403 |
NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) {
|
deba@220
|
404 |
to.build(from, nodeRefMap, arcRefMap);
|
deba@220
|
405 |
}
|
deba@220
|
406 |
};
|
deba@220
|
407 |
|
deba@220
|
408 |
template <typename Graph, typename Enable = void>
|
deba@220
|
409 |
struct GraphCopySelector {
|
deba@220
|
410 |
template <typename From, typename NodeRefMap, typename EdgeRefMap>
|
kpeter@282
|
411 |
static void copy(const From& from, Graph &to,
|
deba@220
|
412 |
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
|
deba@220
|
413 |
for (typename From::NodeIt it(from); it != INVALID; ++it) {
|
deba@220
|
414 |
nodeRefMap[it] = to.addNode();
|
deba@220
|
415 |
}
|
deba@220
|
416 |
for (typename From::EdgeIt it(from); it != INVALID; ++it) {
|
deba@220
|
417 |
edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
|
deba@220
|
418 |
nodeRefMap[from.v(it)]);
|
deba@220
|
419 |
}
|
deba@220
|
420 |
}
|
deba@220
|
421 |
};
|
deba@220
|
422 |
|
deba@220
|
423 |
template <typename Graph>
|
deba@220
|
424 |
struct GraphCopySelector<
|
deba@220
|
425 |
Graph,
|
deba@220
|
426 |
typename enable_if<typename Graph::BuildTag, void>::type>
|
deba@220
|
427 |
{
|
deba@220
|
428 |
template <typename From, typename NodeRefMap, typename EdgeRefMap>
|
kpeter@282
|
429 |
static void copy(const From& from, Graph &to,
|
deba@220
|
430 |
NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) {
|
deba@220
|
431 |
to.build(from, nodeRefMap, edgeRefMap);
|
deba@220
|
432 |
}
|
deba@220
|
433 |
};
|
deba@220
|
434 |
|
deba@220
|
435 |
}
|
deba@220
|
436 |
|
deba@220
|
437 |
/// \brief Class to copy a digraph.
|
deba@220
|
438 |
///
|
deba@220
|
439 |
/// Class to copy a digraph to another digraph (duplicate a digraph). The
|
kpeter@282
|
440 |
/// simplest way of using it is through the \c digraphCopy() function.
|
deba@220
|
441 |
///
|
kpeter@282
|
442 |
/// This class not only make a copy of a digraph, but it can create
|
deba@220
|
443 |
/// references and cross references between the nodes and arcs of
|
kpeter@282
|
444 |
/// the two digraphs, and it can copy maps to use with the newly created
|
kpeter@282
|
445 |
/// digraph.
|
deba@220
|
446 |
///
|
kpeter@282
|
447 |
/// To make a copy from a digraph, first an instance of DigraphCopy
|
kpeter@282
|
448 |
/// should be created, then the data belongs to the digraph should
|
deba@220
|
449 |
/// assigned to copy. In the end, the \c run() member should be
|
deba@220
|
450 |
/// called.
|
deba@220
|
451 |
///
|
kpeter@282
|
452 |
/// The next code copies a digraph with several data:
|
deba@220
|
453 |
///\code
|
kpeter@282
|
454 |
/// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
|
kpeter@282
|
455 |
/// // Create references for the nodes
|
deba@220
|
456 |
/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
|
kpeter@282
|
457 |
/// cg.nodeRef(nr);
|
kpeter@282
|
458 |
/// // Create cross references (inverse) for the arcs
|
deba@220
|
459 |
/// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph);
|
kpeter@282
|
460 |
/// cg.arcCrossRef(acr);
|
kpeter@282
|
461 |
/// // Copy an arc map
|
deba@220
|
462 |
/// OrigGraph::ArcMap<double> oamap(orig_graph);
|
deba@220
|
463 |
/// NewGraph::ArcMap<double> namap(new_graph);
|
kpeter@282
|
464 |
/// cg.arcMap(oamap, namap);
|
kpeter@282
|
465 |
/// // Copy a node
|
deba@220
|
466 |
/// OrigGraph::Node on;
|
deba@220
|
467 |
/// NewGraph::Node nn;
|
kpeter@282
|
468 |
/// cg.node(on, nn);
|
kpeter@282
|
469 |
/// // Execute copying
|
kpeter@282
|
470 |
/// cg.run();
|
deba@220
|
471 |
///\endcode
|
kpeter@282
|
472 |
template <typename From, typename To>
|
deba@220
|
473 |
class DigraphCopy {
|
deba@220
|
474 |
private:
|
deba@220
|
475 |
|
deba@220
|
476 |
typedef typename From::Node Node;
|
deba@220
|
477 |
typedef typename From::NodeIt NodeIt;
|
deba@220
|
478 |
typedef typename From::Arc Arc;
|
deba@220
|
479 |
typedef typename From::ArcIt ArcIt;
|
deba@220
|
480 |
|
deba@220
|
481 |
typedef typename To::Node TNode;
|
deba@220
|
482 |
typedef typename To::Arc TArc;
|
deba@220
|
483 |
|
deba@220
|
484 |
typedef typename From::template NodeMap<TNode> NodeRefMap;
|
deba@220
|
485 |
typedef typename From::template ArcMap<TArc> ArcRefMap;
|
deba@220
|
486 |
|
deba@220
|
487 |
public:
|
deba@220
|
488 |
|
kpeter@282
|
489 |
/// \brief Constructor of DigraphCopy.
|
deba@220
|
490 |
///
|
kpeter@282
|
491 |
/// Constructor of DigraphCopy for copying the content of the
|
kpeter@282
|
492 |
/// \c from digraph into the \c to digraph.
|
kpeter@282
|
493 |
DigraphCopy(const From& from, To& to)
|
deba@220
|
494 |
: _from(from), _to(to) {}
|
deba@220
|
495 |
|
kpeter@282
|
496 |
/// \brief Destructor of DigraphCopy
|
deba@220
|
497 |
///
|
kpeter@282
|
498 |
/// Destructor of DigraphCopy.
|
deba@220
|
499 |
~DigraphCopy() {
|
deba@220
|
500 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@220
|
501 |
delete _node_maps[i];
|
deba@220
|
502 |
}
|
deba@220
|
503 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@220
|
504 |
delete _arc_maps[i];
|
deba@220
|
505 |
}
|
deba@220
|
506 |
|
deba@220
|
507 |
}
|
deba@220
|
508 |
|
kpeter@282
|
509 |
/// \brief Copy the node references into the given map.
|
deba@220
|
510 |
///
|
kpeter@282
|
511 |
/// This function copies the node references into the given map.
|
kpeter@282
|
512 |
/// The parameter should be a map, whose key type is the Node type of
|
kpeter@282
|
513 |
/// the source digraph, while the value type is the Node type of the
|
kpeter@282
|
514 |
/// destination digraph.
|
deba@220
|
515 |
template <typename NodeRef>
|
deba@220
|
516 |
DigraphCopy& nodeRef(NodeRef& map) {
|
deba@220
|
517 |
_node_maps.push_back(new _core_bits::RefCopy<From, Node,
|
deba@220
|
518 |
NodeRefMap, NodeRef>(map));
|
deba@220
|
519 |
return *this;
|
deba@220
|
520 |
}
|
deba@220
|
521 |
|
kpeter@282
|
522 |
/// \brief Copy the node cross references into the given map.
|
deba@220
|
523 |
///
|
kpeter@282
|
524 |
/// This function copies the node cross references (reverse references)
|
kpeter@282
|
525 |
/// into the given map. The parameter should be a map, whose key type
|
kpeter@282
|
526 |
/// is the Node type of the destination digraph, while the value type is
|
kpeter@282
|
527 |
/// the Node type of the source digraph.
|
deba@220
|
528 |
template <typename NodeCrossRef>
|
deba@220
|
529 |
DigraphCopy& nodeCrossRef(NodeCrossRef& map) {
|
deba@220
|
530 |
_node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
|
deba@220
|
531 |
NodeRefMap, NodeCrossRef>(map));
|
deba@220
|
532 |
return *this;
|
deba@220
|
533 |
}
|
deba@220
|
534 |
|
kpeter@282
|
535 |
/// \brief Make a copy of the given node map.
|
deba@220
|
536 |
///
|
kpeter@282
|
537 |
/// This function makes a copy of the given node map for the newly
|
kpeter@282
|
538 |
/// created digraph.
|
kpeter@282
|
539 |
/// The key type of the new map \c tmap should be the Node type of the
|
kpeter@282
|
540 |
/// destination digraph, and the key type of the original map \c map
|
kpeter@282
|
541 |
/// should be the Node type of the source digraph.
|
kpeter@282
|
542 |
template <typename FromMap, typename ToMap>
|
kpeter@282
|
543 |
DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
|
deba@220
|
544 |
_node_maps.push_back(new _core_bits::MapCopy<From, Node,
|
kpeter@282
|
545 |
NodeRefMap, FromMap, ToMap>(map, tmap));
|
deba@220
|
546 |
return *this;
|
deba@220
|
547 |
}
|
deba@220
|
548 |
|
deba@220
|
549 |
/// \brief Make a copy of the given node.
|
deba@220
|
550 |
///
|
kpeter@282
|
551 |
/// This function makes a copy of the given node.
|
kpeter@282
|
552 |
DigraphCopy& node(const Node& node, TNode& tnode) {
|
deba@220
|
553 |
_node_maps.push_back(new _core_bits::ItemCopy<From, Node,
|
kpeter@282
|
554 |
NodeRefMap, TNode>(node, tnode));
|
deba@220
|
555 |
return *this;
|
deba@220
|
556 |
}
|
deba@220
|
557 |
|
kpeter@282
|
558 |
/// \brief Copy the arc references into the given map.
|
deba@220
|
559 |
///
|
kpeter@282
|
560 |
/// This function copies the arc references into the given map.
|
kpeter@282
|
561 |
/// The parameter should be a map, whose key type is the Arc type of
|
kpeter@282
|
562 |
/// the source digraph, while the value type is the Arc type of the
|
kpeter@282
|
563 |
/// destination digraph.
|
deba@220
|
564 |
template <typename ArcRef>
|
deba@220
|
565 |
DigraphCopy& arcRef(ArcRef& map) {
|
deba@220
|
566 |
_arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
|
deba@220
|
567 |
ArcRefMap, ArcRef>(map));
|
deba@220
|
568 |
return *this;
|
deba@220
|
569 |
}
|
deba@220
|
570 |
|
kpeter@282
|
571 |
/// \brief Copy the arc cross references into the given map.
|
deba@220
|
572 |
///
|
kpeter@282
|
573 |
/// This function copies the arc cross references (reverse references)
|
kpeter@282
|
574 |
/// into the given map. The parameter should be a map, whose key type
|
kpeter@282
|
575 |
/// is the Arc type of the destination digraph, while the value type is
|
kpeter@282
|
576 |
/// the Arc type of the source digraph.
|
deba@220
|
577 |
template <typename ArcCrossRef>
|
deba@220
|
578 |
DigraphCopy& arcCrossRef(ArcCrossRef& map) {
|
deba@220
|
579 |
_arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
|
deba@220
|
580 |
ArcRefMap, ArcCrossRef>(map));
|
deba@220
|
581 |
return *this;
|
deba@220
|
582 |
}
|
deba@220
|
583 |
|
kpeter@282
|
584 |
/// \brief Make a copy of the given arc map.
|
deba@220
|
585 |
///
|
kpeter@282
|
586 |
/// This function makes a copy of the given arc map for the newly
|
kpeter@282
|
587 |
/// created digraph.
|
kpeter@282
|
588 |
/// The key type of the new map \c tmap should be the Arc type of the
|
kpeter@282
|
589 |
/// destination digraph, and the key type of the original map \c map
|
kpeter@282
|
590 |
/// should be the Arc type of the source digraph.
|
kpeter@282
|
591 |
template <typename FromMap, typename ToMap>
|
kpeter@282
|
592 |
DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
|
deba@220
|
593 |
_arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
|
kpeter@282
|
594 |
ArcRefMap, FromMap, ToMap>(map, tmap));
|
deba@220
|
595 |
return *this;
|
deba@220
|
596 |
}
|
deba@220
|
597 |
|
deba@220
|
598 |
/// \brief Make a copy of the given arc.
|
deba@220
|
599 |
///
|
kpeter@282
|
600 |
/// This function makes a copy of the given arc.
|
kpeter@282
|
601 |
DigraphCopy& arc(const Arc& arc, TArc& tarc) {
|
deba@220
|
602 |
_arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
|
kpeter@282
|
603 |
ArcRefMap, TArc>(arc, tarc));
|
deba@220
|
604 |
return *this;
|
deba@220
|
605 |
}
|
deba@220
|
606 |
|
kpeter@282
|
607 |
/// \brief Execute copying.
|
deba@220
|
608 |
///
|
kpeter@282
|
609 |
/// This function executes the copying of the digraph along with the
|
kpeter@282
|
610 |
/// copying of the assigned data.
|
deba@220
|
611 |
void run() {
|
deba@220
|
612 |
NodeRefMap nodeRefMap(_from);
|
deba@220
|
613 |
ArcRefMap arcRefMap(_from);
|
deba@220
|
614 |
_core_bits::DigraphCopySelector<To>::
|
kpeter@282
|
615 |
copy(_from, _to, nodeRefMap, arcRefMap);
|
deba@220
|
616 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@220
|
617 |
_node_maps[i]->copy(_from, nodeRefMap);
|
deba@220
|
618 |
}
|
deba@220
|
619 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@220
|
620 |
_arc_maps[i]->copy(_from, arcRefMap);
|
deba@220
|
621 |
}
|
deba@220
|
622 |
}
|
deba@220
|
623 |
|
deba@220
|
624 |
protected:
|
deba@220
|
625 |
|
deba@220
|
626 |
const From& _from;
|
deba@220
|
627 |
To& _to;
|
deba@220
|
628 |
|
deba@220
|
629 |
std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
|
kpeter@282
|
630 |
_node_maps;
|
deba@220
|
631 |
|
deba@220
|
632 |
std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
|
kpeter@282
|
633 |
_arc_maps;
|
deba@220
|
634 |
|
deba@220
|
635 |
};
|
deba@220
|
636 |
|
deba@220
|
637 |
/// \brief Copy a digraph to another digraph.
|
deba@220
|
638 |
///
|
kpeter@282
|
639 |
/// This function copies a digraph to another digraph.
|
kpeter@282
|
640 |
/// The complete usage of it is detailed in the DigraphCopy class, but
|
kpeter@282
|
641 |
/// a short example shows a basic work:
|
deba@220
|
642 |
///\code
|
kpeter@282
|
643 |
/// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run();
|
deba@220
|
644 |
///\endcode
|
deba@220
|
645 |
///
|
deba@220
|
646 |
/// After the copy the \c nr map will contain the mapping from the
|
deba@220
|
647 |
/// nodes of the \c from digraph to the nodes of the \c to digraph and
|
kpeter@282
|
648 |
/// \c acr will contain the mapping from the arcs of the \c to digraph
|
deba@220
|
649 |
/// to the arcs of the \c from digraph.
|
deba@220
|
650 |
///
|
deba@220
|
651 |
/// \see DigraphCopy
|
kpeter@282
|
652 |
template <typename From, typename To>
|
kpeter@282
|
653 |
DigraphCopy<From, To> digraphCopy(const From& from, To& to) {
|
kpeter@282
|
654 |
return DigraphCopy<From, To>(from, to);
|
deba@220
|
655 |
}
|
deba@220
|
656 |
|
deba@220
|
657 |
/// \brief Class to copy a graph.
|
deba@220
|
658 |
///
|
deba@220
|
659 |
/// Class to copy a graph to another graph (duplicate a graph). The
|
kpeter@282
|
660 |
/// simplest way of using it is through the \c graphCopy() function.
|
deba@220
|
661 |
///
|
kpeter@282
|
662 |
/// This class not only make a copy of a graph, but it can create
|
deba@220
|
663 |
/// references and cross references between the nodes, edges and arcs of
|
kpeter@282
|
664 |
/// the two graphs, and it can copy maps for using with the newly created
|
kpeter@282
|
665 |
/// graph.
|
deba@220
|
666 |
///
|
deba@220
|
667 |
/// To make a copy from a graph, first an instance of GraphCopy
|
deba@220
|
668 |
/// should be created, then the data belongs to the graph should
|
deba@220
|
669 |
/// assigned to copy. In the end, the \c run() member should be
|
deba@220
|
670 |
/// called.
|
deba@220
|
671 |
///
|
deba@220
|
672 |
/// The next code copies a graph with several data:
|
deba@220
|
673 |
///\code
|
kpeter@282
|
674 |
/// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph);
|
kpeter@282
|
675 |
/// // Create references for the nodes
|
deba@220
|
676 |
/// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph);
|
kpeter@282
|
677 |
/// cg.nodeRef(nr);
|
kpeter@282
|
678 |
/// // Create cross references (inverse) for the edges
|
kpeter@282
|
679 |
/// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph);
|
kpeter@282
|
680 |
/// cg.edgeCrossRef(ecr);
|
kpeter@282
|
681 |
/// // Copy an edge map
|
kpeter@282
|
682 |
/// OrigGraph::EdgeMap<double> oemap(orig_graph);
|
kpeter@282
|
683 |
/// NewGraph::EdgeMap<double> nemap(new_graph);
|
kpeter@282
|
684 |
/// cg.edgeMap(oemap, nemap);
|
kpeter@282
|
685 |
/// // Copy a node
|
deba@220
|
686 |
/// OrigGraph::Node on;
|
deba@220
|
687 |
/// NewGraph::Node nn;
|
kpeter@282
|
688 |
/// cg.node(on, nn);
|
kpeter@282
|
689 |
/// // Execute copying
|
kpeter@282
|
690 |
/// cg.run();
|
deba@220
|
691 |
///\endcode
|
kpeter@282
|
692 |
template <typename From, typename To>
|
deba@220
|
693 |
class GraphCopy {
|
deba@220
|
694 |
private:
|
deba@220
|
695 |
|
deba@220
|
696 |
typedef typename From::Node Node;
|
deba@220
|
697 |
typedef typename From::NodeIt NodeIt;
|
deba@220
|
698 |
typedef typename From::Arc Arc;
|
deba@220
|
699 |
typedef typename From::ArcIt ArcIt;
|
deba@220
|
700 |
typedef typename From::Edge Edge;
|
deba@220
|
701 |
typedef typename From::EdgeIt EdgeIt;
|
deba@220
|
702 |
|
deba@220
|
703 |
typedef typename To::Node TNode;
|
deba@220
|
704 |
typedef typename To::Arc TArc;
|
deba@220
|
705 |
typedef typename To::Edge TEdge;
|
deba@220
|
706 |
|
deba@220
|
707 |
typedef typename From::template NodeMap<TNode> NodeRefMap;
|
deba@220
|
708 |
typedef typename From::template EdgeMap<TEdge> EdgeRefMap;
|
deba@220
|
709 |
|
deba@220
|
710 |
struct ArcRefMap {
|
kpeter@282
|
711 |
ArcRefMap(const From& from, const To& to,
|
deba@220
|
712 |
const EdgeRefMap& edge_ref, const NodeRefMap& node_ref)
|
kpeter@282
|
713 |
: _from(from), _to(to),
|
deba@220
|
714 |
_edge_ref(edge_ref), _node_ref(node_ref) {}
|
deba@220
|
715 |
|
deba@220
|
716 |
typedef typename From::Arc Key;
|
deba@220
|
717 |
typedef typename To::Arc Value;
|
deba@220
|
718 |
|
deba@220
|
719 |
Value operator[](const Key& key) const {
|
deba@220
|
720 |
bool forward = _from.u(key) != _from.v(key) ?
|
deba@220
|
721 |
_node_ref[_from.source(key)] ==
|
deba@220
|
722 |
_to.source(_to.direct(_edge_ref[key], true)) :
|
deba@220
|
723 |
_from.direction(key);
|
deba@220
|
724 |
return _to.direct(_edge_ref[key], forward);
|
deba@220
|
725 |
}
|
deba@220
|
726 |
|
kpeter@282
|
727 |
const From& _from;
|
deba@220
|
728 |
const To& _to;
|
deba@220
|
729 |
const EdgeRefMap& _edge_ref;
|
deba@220
|
730 |
const NodeRefMap& _node_ref;
|
deba@220
|
731 |
};
|
deba@220
|
732 |
|
deba@220
|
733 |
public:
|
deba@220
|
734 |
|
kpeter@282
|
735 |
/// \brief Constructor of GraphCopy.
|
deba@220
|
736 |
///
|
kpeter@282
|
737 |
/// Constructor of GraphCopy for copying the content of the
|
kpeter@282
|
738 |
/// \c from graph into the \c to graph.
|
kpeter@282
|
739 |
GraphCopy(const From& from, To& to)
|
deba@220
|
740 |
: _from(from), _to(to) {}
|
deba@220
|
741 |
|
kpeter@282
|
742 |
/// \brief Destructor of GraphCopy
|
deba@220
|
743 |
///
|
kpeter@282
|
744 |
/// Destructor of GraphCopy.
|
deba@220
|
745 |
~GraphCopy() {
|
deba@220
|
746 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@220
|
747 |
delete _node_maps[i];
|
deba@220
|
748 |
}
|
deba@220
|
749 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@220
|
750 |
delete _arc_maps[i];
|
deba@220
|
751 |
}
|
deba@220
|
752 |
for (int i = 0; i < int(_edge_maps.size()); ++i) {
|
deba@220
|
753 |
delete _edge_maps[i];
|
deba@220
|
754 |
}
|
deba@220
|
755 |
}
|
deba@220
|
756 |
|
kpeter@282
|
757 |
/// \brief Copy the node references into the given map.
|
deba@220
|
758 |
///
|
kpeter@282
|
759 |
/// This function copies the node references into the given map.
|
kpeter@282
|
760 |
/// The parameter should be a map, whose key type is the Node type of
|
kpeter@282
|
761 |
/// the source graph, while the value type is the Node type of the
|
kpeter@282
|
762 |
/// destination graph.
|
deba@220
|
763 |
template <typename NodeRef>
|
deba@220
|
764 |
GraphCopy& nodeRef(NodeRef& map) {
|
deba@220
|
765 |
_node_maps.push_back(new _core_bits::RefCopy<From, Node,
|
deba@220
|
766 |
NodeRefMap, NodeRef>(map));
|
deba@220
|
767 |
return *this;
|
deba@220
|
768 |
}
|
deba@220
|
769 |
|
kpeter@282
|
770 |
/// \brief Copy the node cross references into the given map.
|
deba@220
|
771 |
///
|
kpeter@282
|
772 |
/// This function copies the node cross references (reverse references)
|
kpeter@282
|
773 |
/// into the given map. The parameter should be a map, whose key type
|
kpeter@282
|
774 |
/// is the Node type of the destination graph, while the value type is
|
kpeter@282
|
775 |
/// the Node type of the source graph.
|
deba@220
|
776 |
template <typename NodeCrossRef>
|
deba@220
|
777 |
GraphCopy& nodeCrossRef(NodeCrossRef& map) {
|
deba@220
|
778 |
_node_maps.push_back(new _core_bits::CrossRefCopy<From, Node,
|
deba@220
|
779 |
NodeRefMap, NodeCrossRef>(map));
|
deba@220
|
780 |
return *this;
|
deba@220
|
781 |
}
|
deba@220
|
782 |
|
kpeter@282
|
783 |
/// \brief Make a copy of the given node map.
|
deba@220
|
784 |
///
|
kpeter@282
|
785 |
/// This function makes a copy of the given node map for the newly
|
kpeter@282
|
786 |
/// created graph.
|
kpeter@282
|
787 |
/// The key type of the new map \c tmap should be the Node type of the
|
kpeter@282
|
788 |
/// destination graph, and the key type of the original map \c map
|
kpeter@282
|
789 |
/// should be the Node type of the source graph.
|
kpeter@282
|
790 |
template <typename FromMap, typename ToMap>
|
kpeter@282
|
791 |
GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) {
|
deba@220
|
792 |
_node_maps.push_back(new _core_bits::MapCopy<From, Node,
|
kpeter@282
|
793 |
NodeRefMap, FromMap, ToMap>(map, tmap));
|
deba@220
|
794 |
return *this;
|
deba@220
|
795 |
}
|
deba@220
|
796 |
|
deba@220
|
797 |
/// \brief Make a copy of the given node.
|
deba@220
|
798 |
///
|
kpeter@282
|
799 |
/// This function makes a copy of the given node.
|
kpeter@282
|
800 |
GraphCopy& node(const Node& node, TNode& tnode) {
|
deba@220
|
801 |
_node_maps.push_back(new _core_bits::ItemCopy<From, Node,
|
kpeter@282
|
802 |
NodeRefMap, TNode>(node, tnode));
|
deba@220
|
803 |
return *this;
|
deba@220
|
804 |
}
|
deba@220
|
805 |
|
kpeter@282
|
806 |
/// \brief Copy the arc references into the given map.
|
deba@220
|
807 |
///
|
kpeter@282
|
808 |
/// This function copies the arc references into the given map.
|
kpeter@282
|
809 |
/// The parameter should be a map, whose key type is the Arc type of
|
kpeter@282
|
810 |
/// the source graph, while the value type is the Arc type of the
|
kpeter@282
|
811 |
/// destination graph.
|
deba@220
|
812 |
template <typename ArcRef>
|
deba@220
|
813 |
GraphCopy& arcRef(ArcRef& map) {
|
deba@220
|
814 |
_arc_maps.push_back(new _core_bits::RefCopy<From, Arc,
|
deba@220
|
815 |
ArcRefMap, ArcRef>(map));
|
deba@220
|
816 |
return *this;
|
deba@220
|
817 |
}
|
deba@220
|
818 |
|
kpeter@282
|
819 |
/// \brief Copy the arc cross references into the given map.
|
deba@220
|
820 |
///
|
kpeter@282
|
821 |
/// This function copies the arc cross references (reverse references)
|
kpeter@282
|
822 |
/// into the given map. The parameter should be a map, whose key type
|
kpeter@282
|
823 |
/// is the Arc type of the destination graph, while the value type is
|
kpeter@282
|
824 |
/// the Arc type of the source graph.
|
deba@220
|
825 |
template <typename ArcCrossRef>
|
deba@220
|
826 |
GraphCopy& arcCrossRef(ArcCrossRef& map) {
|
deba@220
|
827 |
_arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc,
|
deba@220
|
828 |
ArcRefMap, ArcCrossRef>(map));
|
deba@220
|
829 |
return *this;
|
deba@220
|
830 |
}
|
deba@220
|
831 |
|
kpeter@282
|
832 |
/// \brief Make a copy of the given arc map.
|
deba@220
|
833 |
///
|
kpeter@282
|
834 |
/// This function makes a copy of the given arc map for the newly
|
kpeter@282
|
835 |
/// created graph.
|
kpeter@282
|
836 |
/// The key type of the new map \c tmap should be the Arc type of the
|
kpeter@282
|
837 |
/// destination graph, and the key type of the original map \c map
|
kpeter@282
|
838 |
/// should be the Arc type of the source graph.
|
kpeter@282
|
839 |
template <typename FromMap, typename ToMap>
|
kpeter@282
|
840 |
GraphCopy& arcMap(const FromMap& map, ToMap& tmap) {
|
deba@220
|
841 |
_arc_maps.push_back(new _core_bits::MapCopy<From, Arc,
|
kpeter@282
|
842 |
ArcRefMap, FromMap, ToMap>(map, tmap));
|
deba@220
|
843 |
return *this;
|
deba@220
|
844 |
}
|
deba@220
|
845 |
|
deba@220
|
846 |
/// \brief Make a copy of the given arc.
|
deba@220
|
847 |
///
|
kpeter@282
|
848 |
/// This function makes a copy of the given arc.
|
kpeter@282
|
849 |
GraphCopy& arc(const Arc& arc, TArc& tarc) {
|
deba@220
|
850 |
_arc_maps.push_back(new _core_bits::ItemCopy<From, Arc,
|
kpeter@282
|
851 |
ArcRefMap, TArc>(arc, tarc));
|
deba@220
|
852 |
return *this;
|
deba@220
|
853 |
}
|
deba@220
|
854 |
|
kpeter@282
|
855 |
/// \brief Copy the edge references into the given map.
|
deba@220
|
856 |
///
|
kpeter@282
|
857 |
/// This function copies the edge references into the given map.
|
kpeter@282
|
858 |
/// The parameter should be a map, whose key type is the Edge type of
|
kpeter@282
|
859 |
/// the source graph, while the value type is the Edge type of the
|
kpeter@282
|
860 |
/// destination graph.
|
deba@220
|
861 |
template <typename EdgeRef>
|
deba@220
|
862 |
GraphCopy& edgeRef(EdgeRef& map) {
|
deba@220
|
863 |
_edge_maps.push_back(new _core_bits::RefCopy<From, Edge,
|
deba@220
|
864 |
EdgeRefMap, EdgeRef>(map));
|
deba@220
|
865 |
return *this;
|
deba@220
|
866 |
}
|
deba@220
|
867 |
|
kpeter@282
|
868 |
/// \brief Copy the edge cross references into the given map.
|
deba@220
|
869 |
///
|
kpeter@282
|
870 |
/// This function copies the edge cross references (reverse references)
|
kpeter@282
|
871 |
/// into the given map. The parameter should be a map, whose key type
|
kpeter@282
|
872 |
/// is the Edge type of the destination graph, while the value type is
|
kpeter@282
|
873 |
/// the Edge type of the source graph.
|
deba@220
|
874 |
template <typename EdgeCrossRef>
|
deba@220
|
875 |
GraphCopy& edgeCrossRef(EdgeCrossRef& map) {
|
deba@220
|
876 |
_edge_maps.push_back(new _core_bits::CrossRefCopy<From,
|
deba@220
|
877 |
Edge, EdgeRefMap, EdgeCrossRef>(map));
|
deba@220
|
878 |
return *this;
|
deba@220
|
879 |
}
|
deba@220
|
880 |
|
kpeter@282
|
881 |
/// \brief Make a copy of the given edge map.
|
deba@220
|
882 |
///
|
kpeter@282
|
883 |
/// This function makes a copy of the given edge map for the newly
|
kpeter@282
|
884 |
/// created graph.
|
kpeter@282
|
885 |
/// The key type of the new map \c tmap should be the Edge type of the
|
kpeter@282
|
886 |
/// destination graph, and the key type of the original map \c map
|
kpeter@282
|
887 |
/// should be the Edge type of the source graph.
|
kpeter@282
|
888 |
template <typename FromMap, typename ToMap>
|
kpeter@282
|
889 |
GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) {
|
deba@220
|
890 |
_edge_maps.push_back(new _core_bits::MapCopy<From, Edge,
|
kpeter@282
|
891 |
EdgeRefMap, FromMap, ToMap>(map, tmap));
|
deba@220
|
892 |
return *this;
|
deba@220
|
893 |
}
|
deba@220
|
894 |
|
deba@220
|
895 |
/// \brief Make a copy of the given edge.
|
deba@220
|
896 |
///
|
kpeter@282
|
897 |
/// This function makes a copy of the given edge.
|
kpeter@282
|
898 |
GraphCopy& edge(const Edge& edge, TEdge& tedge) {
|
deba@220
|
899 |
_edge_maps.push_back(new _core_bits::ItemCopy<From, Edge,
|
kpeter@282
|
900 |
EdgeRefMap, TEdge>(edge, tedge));
|
deba@220
|
901 |
return *this;
|
deba@220
|
902 |
}
|
deba@220
|
903 |
|
kpeter@282
|
904 |
/// \brief Execute copying.
|
deba@220
|
905 |
///
|
kpeter@282
|
906 |
/// This function executes the copying of the graph along with the
|
kpeter@282
|
907 |
/// copying of the assigned data.
|
deba@220
|
908 |
void run() {
|
deba@220
|
909 |
NodeRefMap nodeRefMap(_from);
|
deba@220
|
910 |
EdgeRefMap edgeRefMap(_from);
|
kpeter@282
|
911 |
ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap);
|
deba@220
|
912 |
_core_bits::GraphCopySelector<To>::
|
kpeter@282
|
913 |
copy(_from, _to, nodeRefMap, edgeRefMap);
|
deba@220
|
914 |
for (int i = 0; i < int(_node_maps.size()); ++i) {
|
deba@220
|
915 |
_node_maps[i]->copy(_from, nodeRefMap);
|
deba@220
|
916 |
}
|
deba@220
|
917 |
for (int i = 0; i < int(_edge_maps.size()); ++i) {
|
deba@220
|
918 |
_edge_maps[i]->copy(_from, edgeRefMap);
|
deba@220
|
919 |
}
|
deba@220
|
920 |
for (int i = 0; i < int(_arc_maps.size()); ++i) {
|
deba@220
|
921 |
_arc_maps[i]->copy(_from, arcRefMap);
|
deba@220
|
922 |
}
|
deba@220
|
923 |
}
|
deba@220
|
924 |
|
deba@220
|
925 |
private:
|
deba@220
|
926 |
|
deba@220
|
927 |
const From& _from;
|
deba@220
|
928 |
To& _to;
|
deba@220
|
929 |
|
deba@220
|
930 |
std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* >
|
kpeter@282
|
931 |
_node_maps;
|
deba@220
|
932 |
|
deba@220
|
933 |
std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* >
|
kpeter@282
|
934 |
_arc_maps;
|
deba@220
|
935 |
|
deba@220
|
936 |
std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* >
|
kpeter@282
|
937 |
_edge_maps;
|
deba@220
|
938 |
|
deba@220
|
939 |
};
|
deba@220
|
940 |
|
deba@220
|
941 |
/// \brief Copy a graph to another graph.
|
deba@220
|
942 |
///
|
kpeter@282
|
943 |
/// This function copies a graph to another graph.
|
kpeter@282
|
944 |
/// The complete usage of it is detailed in the GraphCopy class,
|
kpeter@282
|
945 |
/// but a short example shows a basic work:
|
deba@220
|
946 |
///\code
|
kpeter@282
|
947 |
/// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run();
|
deba@220
|
948 |
///\endcode
|
deba@220
|
949 |
///
|
deba@220
|
950 |
/// After the copy the \c nr map will contain the mapping from the
|
deba@220
|
951 |
/// nodes of the \c from graph to the nodes of the \c to graph and
|
kpeter@282
|
952 |
/// \c ecr will contain the mapping from the edges of the \c to graph
|
kpeter@282
|
953 |
/// to the edges of the \c from graph.
|
deba@220
|
954 |
///
|
deba@220
|
955 |
/// \see GraphCopy
|
kpeter@282
|
956 |
template <typename From, typename To>
|
kpeter@282
|
957 |
GraphCopy<From, To>
|
kpeter@282
|
958 |
graphCopy(const From& from, To& to) {
|
kpeter@282
|
959 |
return GraphCopy<From, To>(from, to);
|
deba@220
|
960 |
}
|
deba@220
|
961 |
|
deba@220
|
962 |
namespace _core_bits {
|
deba@220
|
963 |
|
deba@220
|
964 |
template <typename Graph, typename Enable = void>
|
deba@220
|
965 |
struct FindArcSelector {
|
deba@220
|
966 |
typedef typename Graph::Node Node;
|
deba@220
|
967 |
typedef typename Graph::Arc Arc;
|
deba@220
|
968 |
static Arc find(const Graph &g, Node u, Node v, Arc e) {
|
deba@220
|
969 |
if (e == INVALID) {
|
deba@220
|
970 |
g.firstOut(e, u);
|
deba@220
|
971 |
} else {
|
deba@220
|
972 |
g.nextOut(e);
|
deba@220
|
973 |
}
|
deba@220
|
974 |
while (e != INVALID && g.target(e) != v) {
|
deba@220
|
975 |
g.nextOut(e);
|
deba@220
|
976 |
}
|
deba@220
|
977 |
return e;
|
deba@220
|
978 |
}
|
deba@220
|
979 |
};
|
deba@220
|
980 |
|
deba@220
|
981 |
template <typename Graph>
|
deba@220
|
982 |
struct FindArcSelector<
|
deba@220
|
983 |
Graph,
|
kpeter@282
|
984 |
typename enable_if<typename Graph::FindArcTag, void>::type>
|
deba@220
|
985 |
{
|
deba@220
|
986 |
typedef typename Graph::Node Node;
|
deba@220
|
987 |
typedef typename Graph::Arc Arc;
|
deba@220
|
988 |
static Arc find(const Graph &g, Node u, Node v, Arc prev) {
|
deba@220
|
989 |
return g.findArc(u, v, prev);
|
deba@220
|
990 |
}
|
deba@220
|
991 |
};
|
deba@220
|
992 |
}
|
deba@220
|
993 |
|
kpeter@282
|
994 |
/// \brief Find an arc between two nodes of a digraph.
|
deba@220
|
995 |
///
|
kpeter@282
|
996 |
/// This function finds an arc from node \c u to node \c v in the
|
kpeter@282
|
997 |
/// digraph \c g.
|
deba@220
|
998 |
///
|
deba@220
|
999 |
/// If \c prev is \ref INVALID (this is the default value), then
|
deba@220
|
1000 |
/// it finds the first arc from \c u to \c v. Otherwise it looks for
|
deba@220
|
1001 |
/// the next arc from \c u to \c v after \c prev.
|
deba@220
|
1002 |
/// \return The found arc or \ref INVALID if there is no such an arc.
|
deba@220
|
1003 |
///
|
deba@220
|
1004 |
/// Thus you can iterate through each arc from \c u to \c v as it follows.
|
deba@220
|
1005 |
///\code
|
kpeter@282
|
1006 |
/// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) {
|
deba@220
|
1007 |
/// ...
|
deba@220
|
1008 |
/// }
|
deba@220
|
1009 |
///\endcode
|
deba@220
|
1010 |
///
|
kpeter@282
|
1011 |
/// \note \ref ConArcIt provides iterator interface for the same
|
kpeter@282
|
1012 |
/// functionality.
|
kpeter@282
|
1013 |
///
|
deba@220
|
1014 |
///\sa ConArcIt
|
kpeter@282
|
1015 |
///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
|
deba@220
|
1016 |
template <typename Graph>
|
deba@220
|
1017 |
inline typename Graph::Arc
|
deba@220
|
1018 |
findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v,
|
deba@220
|
1019 |
typename Graph::Arc prev = INVALID) {
|
deba@220
|
1020 |
return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev);
|
deba@220
|
1021 |
}
|
deba@220
|
1022 |
|
kpeter@282
|
1023 |
/// \brief Iterator for iterating on parallel arcs connecting the same nodes.
|
deba@220
|
1024 |
///
|
kpeter@282
|
1025 |
/// Iterator for iterating on parallel arcs connecting the same nodes. It is
|
kpeter@282
|
1026 |
/// a higher level interface for the \ref findArc() function. You can
|
deba@220
|
1027 |
/// use it the following way:
|
deba@220
|
1028 |
///\code
|
deba@220
|
1029 |
/// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) {
|
deba@220
|
1030 |
/// ...
|
deba@220
|
1031 |
/// }
|
deba@220
|
1032 |
///\endcode
|
deba@220
|
1033 |
///
|
deba@220
|
1034 |
///\sa findArc()
|
kpeter@282
|
1035 |
///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
|
deba@220
|
1036 |
template <typename _Graph>
|
deba@220
|
1037 |
class ConArcIt : public _Graph::Arc {
|
deba@220
|
1038 |
public:
|
deba@220
|
1039 |
|
deba@220
|
1040 |
typedef _Graph Graph;
|
deba@220
|
1041 |
typedef typename Graph::Arc Parent;
|
deba@220
|
1042 |
|
deba@220
|
1043 |
typedef typename Graph::Arc Arc;
|
deba@220
|
1044 |
typedef typename Graph::Node Node;
|
deba@220
|
1045 |
|
deba@220
|
1046 |
/// \brief Constructor.
|
deba@220
|
1047 |
///
|
kpeter@282
|
1048 |
/// Construct a new ConArcIt iterating on the arcs that
|
kpeter@282
|
1049 |
/// connects nodes \c u and \c v.
|
deba@220
|
1050 |
ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
|
deba@220
|
1051 |
Parent::operator=(findArc(_graph, u, v));
|
deba@220
|
1052 |
}
|
deba@220
|
1053 |
|
deba@220
|
1054 |
/// \brief Constructor.
|
deba@220
|
1055 |
///
|
kpeter@282
|
1056 |
/// Construct a new ConArcIt that continues the iterating from arc \c a.
|
deba@220
|
1057 |
ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
|
deba@220
|
1058 |
|
deba@220
|
1059 |
/// \brief Increment operator.
|
deba@220
|
1060 |
///
|
deba@220
|
1061 |
/// It increments the iterator and gives back the next arc.
|
deba@220
|
1062 |
ConArcIt& operator++() {
|
deba@220
|
1063 |
Parent::operator=(findArc(_graph, _graph.source(*this),
|
deba@220
|
1064 |
_graph.target(*this), *this));
|
deba@220
|
1065 |
return *this;
|
deba@220
|
1066 |
}
|
deba@220
|
1067 |
private:
|
deba@220
|
1068 |
const Graph& _graph;
|
deba@220
|
1069 |
};
|
deba@220
|
1070 |
|
deba@220
|
1071 |
namespace _core_bits {
|
deba@220
|
1072 |
|
deba@220
|
1073 |
template <typename Graph, typename Enable = void>
|
deba@220
|
1074 |
struct FindEdgeSelector {
|
deba@220
|
1075 |
typedef typename Graph::Node Node;
|
deba@220
|
1076 |
typedef typename Graph::Edge Edge;
|
deba@220
|
1077 |
static Edge find(const Graph &g, Node u, Node v, Edge e) {
|
deba@220
|
1078 |
bool b;
|
deba@220
|
1079 |
if (u != v) {
|
deba@220
|
1080 |
if (e == INVALID) {
|
deba@220
|
1081 |
g.firstInc(e, b, u);
|
deba@220
|
1082 |
} else {
|
deba@220
|
1083 |
b = g.u(e) == u;
|
deba@220
|
1084 |
g.nextInc(e, b);
|
deba@220
|
1085 |
}
|
deba@220
|
1086 |
while (e != INVALID && (b ? g.v(e) : g.u(e)) != v) {
|
deba@220
|
1087 |
g.nextInc(e, b);
|
deba@220
|
1088 |
}
|
deba@220
|
1089 |
} else {
|
deba@220
|
1090 |
if (e == INVALID) {
|
deba@220
|
1091 |
g.firstInc(e, b, u);
|
deba@220
|
1092 |
} else {
|
deba@220
|
1093 |
b = true;
|
deba@220
|
1094 |
g.nextInc(e, b);
|
deba@220
|
1095 |
}
|
deba@220
|
1096 |
while (e != INVALID && (!b || g.v(e) != v)) {
|
deba@220
|
1097 |
g.nextInc(e, b);
|
deba@220
|
1098 |
}
|
deba@220
|
1099 |
}
|
deba@220
|
1100 |
return e;
|
deba@220
|
1101 |
}
|
deba@220
|
1102 |
};
|
deba@220
|
1103 |
|
deba@220
|
1104 |
template <typename Graph>
|
deba@220
|
1105 |
struct FindEdgeSelector<
|
deba@220
|
1106 |
Graph,
|
deba@220
|
1107 |
typename enable_if<typename Graph::FindEdgeTag, void>::type>
|
deba@220
|
1108 |
{
|
deba@220
|
1109 |
typedef typename Graph::Node Node;
|
deba@220
|
1110 |
typedef typename Graph::Edge Edge;
|
deba@220
|
1111 |
static Edge find(const Graph &g, Node u, Node v, Edge prev) {
|
deba@220
|
1112 |
return g.findEdge(u, v, prev);
|
deba@220
|
1113 |
}
|
deba@220
|
1114 |
};
|
deba@220
|
1115 |
}
|
deba@220
|
1116 |
|
kpeter@282
|
1117 |
/// \brief Find an edge between two nodes of a graph.
|
deba@220
|
1118 |
///
|
kpeter@282
|
1119 |
/// This function finds an edge from node \c u to node \c v in graph \c g.
|
kpeter@282
|
1120 |
/// If node \c u and node \c v is equal then each loop edge
|
deba@220
|
1121 |
/// will be enumerated once.
|
deba@220
|
1122 |
///
|
deba@220
|
1123 |
/// If \c prev is \ref INVALID (this is the default value), then
|
kpeter@282
|
1124 |
/// it finds the first edge from \c u to \c v. Otherwise it looks for
|
kpeter@282
|
1125 |
/// the next edge from \c u to \c v after \c prev.
|
kpeter@282
|
1126 |
/// \return The found edge or \ref INVALID if there is no such an edge.
|
deba@220
|
1127 |
///
|
kpeter@282
|
1128 |
/// Thus you can iterate through each edge between \c u and \c v
|
kpeter@282
|
1129 |
/// as it follows.
|
deba@220
|
1130 |
///\code
|
kpeter@282
|
1131 |
/// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) {
|
deba@220
|
1132 |
/// ...
|
deba@220
|
1133 |
/// }
|
deba@220
|
1134 |
///\endcode
|
deba@220
|
1135 |
///
|
kpeter@282
|
1136 |
/// \note \ref ConEdgeIt provides iterator interface for the same
|
kpeter@282
|
1137 |
/// functionality.
|
kpeter@282
|
1138 |
///
|
deba@220
|
1139 |
///\sa ConEdgeIt
|
deba@220
|
1140 |
template <typename Graph>
|
deba@220
|
1141 |
inline typename Graph::Edge
|
deba@220
|
1142 |
findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,
|
deba@220
|
1143 |
typename Graph::Edge p = INVALID) {
|
deba@220
|
1144 |
return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p);
|
deba@220
|
1145 |
}
|
deba@220
|
1146 |
|
kpeter@282
|
1147 |
/// \brief Iterator for iterating on parallel edges connecting the same nodes.
|
deba@220
|
1148 |
///
|
kpeter@282
|
1149 |
/// Iterator for iterating on parallel edges connecting the same nodes.
|
kpeter@282
|
1150 |
/// It is a higher level interface for the findEdge() function. You can
|
deba@220
|
1151 |
/// use it the following way:
|
deba@220
|
1152 |
///\code
|
kpeter@282
|
1153 |
/// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) {
|
deba@220
|
1154 |
/// ...
|
deba@220
|
1155 |
/// }
|
deba@220
|
1156 |
///\endcode
|
deba@220
|
1157 |
///
|
deba@220
|
1158 |
///\sa findEdge()
|
deba@220
|
1159 |
template <typename _Graph>
|
deba@220
|
1160 |
class ConEdgeIt : public _Graph::Edge {
|
deba@220
|
1161 |
public:
|
deba@220
|
1162 |
|
deba@220
|
1163 |
typedef _Graph Graph;
|
deba@220
|
1164 |
typedef typename Graph::Edge Parent;
|
deba@220
|
1165 |
|
deba@220
|
1166 |
typedef typename Graph::Edge Edge;
|
deba@220
|
1167 |
typedef typename Graph::Node Node;
|
deba@220
|
1168 |
|
deba@220
|
1169 |
/// \brief Constructor.
|
deba@220
|
1170 |
///
|
kpeter@282
|
1171 |
/// Construct a new ConEdgeIt iterating on the edges that
|
kpeter@282
|
1172 |
/// connects nodes \c u and \c v.
|
deba@220
|
1173 |
ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {
|
deba@220
|
1174 |
Parent::operator=(findEdge(_graph, u, v));
|
deba@220
|
1175 |
}
|
deba@220
|
1176 |
|
deba@220
|
1177 |
/// \brief Constructor.
|
deba@220
|
1178 |
///
|
kpeter@282
|
1179 |
/// Construct a new ConEdgeIt that continues iterating from edge \c e.
|
deba@220
|
1180 |
ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
|
deba@220
|
1181 |
|
deba@220
|
1182 |
/// \brief Increment operator.
|
deba@220
|
1183 |
///
|
deba@220
|
1184 |
/// It increments the iterator and gives back the next edge.
|
deba@220
|
1185 |
ConEdgeIt& operator++() {
|
deba@220
|
1186 |
Parent::operator=(findEdge(_graph, _graph.u(*this),
|
deba@220
|
1187 |
_graph.v(*this), *this));
|
deba@220
|
1188 |
return *this;
|
deba@220
|
1189 |
}
|
deba@220
|
1190 |
private:
|
deba@220
|
1191 |
const Graph& _graph;
|
deba@220
|
1192 |
};
|
deba@220
|
1193 |
|
deba@220
|
1194 |
|
kpeter@282
|
1195 |
///Dynamic arc look-up between given endpoints.
|
deba@220
|
1196 |
|
deba@220
|
1197 |
///Using this class, you can find an arc in a digraph from a given
|
kpeter@282
|
1198 |
///source to a given target in amortized time <em>O</em>(log<em>d</em>),
|
deba@220
|
1199 |
///where <em>d</em> is the out-degree of the source node.
|
deba@220
|
1200 |
///
|
deba@220
|
1201 |
///It is possible to find \e all parallel arcs between two nodes with
|
deba@233
|
1202 |
///the \c operator() member.
|
deba@220
|
1203 |
///
|
kpeter@282
|
1204 |
///This is a dynamic data structure. Consider to use \ref ArcLookUp or
|
kpeter@282
|
1205 |
///\ref AllArcLookUp if your digraph is not changed so frequently.
|
deba@220
|
1206 |
///
|
kpeter@282
|
1207 |
///This class uses a self-adjusting binary search tree, the Splay tree
|
kpeter@282
|
1208 |
///of Sleator and Tarjan to guarantee the logarithmic amortized
|
kpeter@282
|
1209 |
///time bound for arc look-ups. This class also guarantees the
|
deba@220
|
1210 |
///optimal time bound in a constant factor for any distribution of
|
deba@220
|
1211 |
///queries.
|
deba@220
|
1212 |
///
|
deba@220
|
1213 |
///\tparam G The type of the underlying digraph.
|
deba@220
|
1214 |
///
|
deba@220
|
1215 |
///\sa ArcLookUp
|
deba@220
|
1216 |
///\sa AllArcLookUp
|
deba@220
|
1217 |
template<class G>
|
deba@220
|
1218 |
class DynArcLookUp
|
deba@220
|
1219 |
: protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
|
deba@220
|
1220 |
{
|
deba@220
|
1221 |
public:
|
deba@220
|
1222 |
typedef typename ItemSetTraits<G, typename G::Arc>
|
deba@220
|
1223 |
::ItemNotifier::ObserverBase Parent;
|
deba@220
|
1224 |
|
deba@220
|
1225 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
deba@220
|
1226 |
typedef G Digraph;
|
deba@220
|
1227 |
|
deba@220
|
1228 |
protected:
|
deba@220
|
1229 |
|
deba@220
|
1230 |
class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
|
deba@220
|
1231 |
public:
|
deba@220
|
1232 |
|
deba@220
|
1233 |
typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
|
deba@220
|
1234 |
|
deba@220
|
1235 |
AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
|
deba@220
|
1236 |
|
deba@220
|
1237 |
virtual void add(const Node& node) {
|
deba@220
|
1238 |
Parent::add(node);
|
deba@220
|
1239 |
Parent::set(node, INVALID);
|
deba@220
|
1240 |
}
|
deba@220
|
1241 |
|
deba@220
|
1242 |
virtual void add(const std::vector<Node>& nodes) {
|
deba@220
|
1243 |
Parent::add(nodes);
|
deba@220
|
1244 |
for (int i = 0; i < int(nodes.size()); ++i) {
|
deba@220
|
1245 |
Parent::set(nodes[i], INVALID);
|
deba@220
|
1246 |
}
|
deba@220
|
1247 |
}
|
deba@220
|
1248 |
|
deba@220
|
1249 |
virtual void build() {
|
deba@220
|
1250 |
Parent::build();
|
deba@220
|
1251 |
Node it;
|
deba@220
|
1252 |
typename Parent::Notifier* nf = Parent::notifier();
|
deba@220
|
1253 |
for (nf->first(it); it != INVALID; nf->next(it)) {
|
deba@220
|
1254 |
Parent::set(it, INVALID);
|
deba@220
|
1255 |
}
|
deba@220
|
1256 |
}
|
deba@220
|
1257 |
};
|
deba@220
|
1258 |
|
deba@220
|
1259 |
const Digraph &_g;
|
deba@220
|
1260 |
AutoNodeMap _head;
|
deba@220
|
1261 |
typename Digraph::template ArcMap<Arc> _parent;
|
deba@220
|
1262 |
typename Digraph::template ArcMap<Arc> _left;
|
deba@220
|
1263 |
typename Digraph::template ArcMap<Arc> _right;
|
deba@220
|
1264 |
|
deba@220
|
1265 |
class ArcLess {
|
deba@220
|
1266 |
const Digraph &g;
|
deba@220
|
1267 |
public:
|
deba@220
|
1268 |
ArcLess(const Digraph &_g) : g(_g) {}
|
deba@220
|
1269 |
bool operator()(Arc a,Arc b) const
|
deba@220
|
1270 |
{
|
deba@220
|
1271 |
return g.target(a)<g.target(b);
|
deba@220
|
1272 |
}
|
deba@220
|
1273 |
};
|
deba@220
|
1274 |
|
deba@220
|
1275 |
public:
|
deba@220
|
1276 |
|
deba@220
|
1277 |
///Constructor
|
deba@220
|
1278 |
|
deba@220
|
1279 |
///Constructor.
|
deba@220
|
1280 |
///
|
deba@220
|
1281 |
///It builds up the search database.
|
deba@220
|
1282 |
DynArcLookUp(const Digraph &g)
|
deba@220
|
1283 |
: _g(g),_head(g),_parent(g),_left(g),_right(g)
|
deba@220
|
1284 |
{
|
deba@220
|
1285 |
Parent::attach(_g.notifier(typename Digraph::Arc()));
|
deba@220
|
1286 |
refresh();
|
deba@220
|
1287 |
}
|
deba@220
|
1288 |
|
deba@220
|
1289 |
protected:
|
deba@220
|
1290 |
|
deba@220
|
1291 |
virtual void add(const Arc& arc) {
|
deba@220
|
1292 |
insert(arc);
|
deba@220
|
1293 |
}
|
deba@220
|
1294 |
|
deba@220
|
1295 |
virtual void add(const std::vector<Arc>& arcs) {
|
deba@220
|
1296 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@220
|
1297 |
insert(arcs[i]);
|
deba@220
|
1298 |
}
|
deba@220
|
1299 |
}
|
deba@220
|
1300 |
|
deba@220
|
1301 |
virtual void erase(const Arc& arc) {
|
deba@220
|
1302 |
remove(arc);
|
deba@220
|
1303 |
}
|
deba@220
|
1304 |
|
deba@220
|
1305 |
virtual void erase(const std::vector<Arc>& arcs) {
|
deba@220
|
1306 |
for (int i = 0; i < int(arcs.size()); ++i) {
|
deba@220
|
1307 |
remove(arcs[i]);
|
deba@220
|
1308 |
}
|
deba@220
|
1309 |
}
|
deba@220
|
1310 |
|
deba@220
|
1311 |
virtual void build() {
|
deba@220
|
1312 |
refresh();
|
deba@220
|
1313 |
}
|
deba@220
|
1314 |
|
deba@220
|
1315 |
virtual void clear() {
|
deba@220
|
1316 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
deba@220
|
1317 |
_head.set(n, INVALID);
|
deba@220
|
1318 |
}
|
deba@220
|
1319 |
}
|
deba@220
|
1320 |
|
deba@220
|
1321 |
void insert(Arc arc) {
|
deba@220
|
1322 |
Node s = _g.source(arc);
|
deba@220
|
1323 |
Node t = _g.target(arc);
|
deba@220
|
1324 |
_left.set(arc, INVALID);
|
deba@220
|
1325 |
_right.set(arc, INVALID);
|
deba@220
|
1326 |
|
deba@220
|
1327 |
Arc e = _head[s];
|
deba@220
|
1328 |
if (e == INVALID) {
|
deba@220
|
1329 |
_head.set(s, arc);
|
deba@220
|
1330 |
_parent.set(arc, INVALID);
|
deba@220
|
1331 |
return;
|
deba@220
|
1332 |
}
|
deba@220
|
1333 |
while (true) {
|
deba@220
|
1334 |
if (t < _g.target(e)) {
|
deba@220
|
1335 |
if (_left[e] == INVALID) {
|
deba@220
|
1336 |
_left.set(e, arc);
|
deba@220
|
1337 |
_parent.set(arc, e);
|
deba@220
|
1338 |
splay(arc);
|
deba@220
|
1339 |
return;
|
deba@220
|
1340 |
} else {
|
deba@220
|
1341 |
e = _left[e];
|
deba@220
|
1342 |
}
|
deba@220
|
1343 |
} else {
|
deba@220
|
1344 |
if (_right[e] == INVALID) {
|
deba@220
|
1345 |
_right.set(e, arc);
|
deba@220
|
1346 |
_parent.set(arc, e);
|
deba@220
|
1347 |
splay(arc);
|
deba@220
|
1348 |
return;
|
deba@220
|
1349 |
} else {
|
deba@220
|
1350 |
e = _right[e];
|
deba@220
|
1351 |
}
|
deba@220
|
1352 |
}
|
deba@220
|
1353 |
}
|
deba@220
|
1354 |
}
|
deba@220
|
1355 |
|
deba@220
|
1356 |
void remove(Arc arc) {
|
deba@220
|
1357 |
if (_left[arc] == INVALID) {
|
deba@220
|
1358 |
if (_right[arc] != INVALID) {
|
deba@220
|
1359 |
_parent.set(_right[arc], _parent[arc]);
|
deba@220
|
1360 |
}
|
deba@220
|
1361 |
if (_parent[arc] != INVALID) {
|
deba@220
|
1362 |
if (_left[_parent[arc]] == arc) {
|
deba@220
|
1363 |
_left.set(_parent[arc], _right[arc]);
|
deba@220
|
1364 |
} else {
|
deba@220
|
1365 |
_right.set(_parent[arc], _right[arc]);
|
deba@220
|
1366 |
}
|
deba@220
|
1367 |
} else {
|
deba@220
|
1368 |
_head.set(_g.source(arc), _right[arc]);
|
deba@220
|
1369 |
}
|
deba@220
|
1370 |
} else if (_right[arc] == INVALID) {
|
deba@220
|
1371 |
_parent.set(_left[arc], _parent[arc]);
|
deba@220
|
1372 |
if (_parent[arc] != INVALID) {
|
deba@220
|
1373 |
if (_left[_parent[arc]] == arc) {
|
deba@220
|
1374 |
_left.set(_parent[arc], _left[arc]);
|
deba@220
|
1375 |
} else {
|
deba@220
|
1376 |
_right.set(_parent[arc], _left[arc]);
|
deba@220
|
1377 |
}
|
deba@220
|
1378 |
} else {
|
deba@220
|
1379 |
_head.set(_g.source(arc), _left[arc]);
|
deba@220
|
1380 |
}
|
deba@220
|
1381 |
} else {
|
deba@220
|
1382 |
Arc e = _left[arc];
|
deba@220
|
1383 |
if (_right[e] != INVALID) {
|
deba@220
|
1384 |
e = _right[e];
|
deba@220
|
1385 |
while (_right[e] != INVALID) {
|
deba@220
|
1386 |
e = _right[e];
|
deba@220
|
1387 |
}
|
deba@220
|
1388 |
Arc s = _parent[e];
|
deba@220
|
1389 |
_right.set(_parent[e], _left[e]);
|
deba@220
|
1390 |
if (_left[e] != INVALID) {
|
deba@220
|
1391 |
_parent.set(_left[e], _parent[e]);
|
deba@220
|
1392 |
}
|
deba@220
|
1393 |
|
deba@220
|
1394 |
_left.set(e, _left[arc]);
|
deba@220
|
1395 |
_parent.set(_left[arc], e);
|
deba@220
|
1396 |
_right.set(e, _right[arc]);
|
deba@220
|
1397 |
_parent.set(_right[arc], e);
|
deba@220
|
1398 |
|
deba@220
|
1399 |
_parent.set(e, _parent[arc]);
|
deba@220
|
1400 |
if (_parent[arc] != INVALID) {
|
deba@220
|
1401 |
if (_left[_parent[arc]] == arc) {
|
deba@220
|
1402 |
_left.set(_parent[arc], e);
|
deba@220
|
1403 |
} else {
|
deba@220
|
1404 |
_right.set(_parent[arc], e);
|
deba@220
|
1405 |
}
|
deba@220
|
1406 |
}
|
deba@220
|
1407 |
splay(s);
|
deba@220
|
1408 |
} else {
|
deba@220
|
1409 |
_right.set(e, _right[arc]);
|
deba@220
|
1410 |
_parent.set(_right[arc], e);
|
deba@232
|
1411 |
_parent.set(e, _parent[arc]);
|
deba@220
|
1412 |
|
deba@220
|
1413 |
if (_parent[arc] != INVALID) {
|
deba@220
|
1414 |
if (_left[_parent[arc]] == arc) {
|
deba@220
|
1415 |
_left.set(_parent[arc], e);
|
deba@220
|
1416 |
} else {
|
deba@220
|
1417 |
_right.set(_parent[arc], e);
|
deba@220
|
1418 |
}
|
deba@220
|
1419 |
} else {
|
deba@220
|
1420 |
_head.set(_g.source(arc), e);
|
deba@220
|
1421 |
}
|
deba@220
|
1422 |
}
|
deba@220
|
1423 |
}
|
deba@220
|
1424 |
}
|
deba@220
|
1425 |
|
deba@220
|
1426 |
Arc refreshRec(std::vector<Arc> &v,int a,int b)
|
deba@220
|
1427 |
{
|
deba@220
|
1428 |
int m=(a+b)/2;
|
deba@220
|
1429 |
Arc me=v[m];
|
deba@220
|
1430 |
if (a < m) {
|
deba@220
|
1431 |
Arc left = refreshRec(v,a,m-1);
|
deba@220
|
1432 |
_left.set(me, left);
|
deba@220
|
1433 |
_parent.set(left, me);
|
deba@220
|
1434 |
} else {
|
deba@220
|
1435 |
_left.set(me, INVALID);
|
deba@220
|
1436 |
}
|
deba@220
|
1437 |
if (m < b) {
|
deba@220
|
1438 |
Arc right = refreshRec(v,m+1,b);
|
deba@220
|
1439 |
_right.set(me, right);
|
deba@220
|
1440 |
_parent.set(right, me);
|
deba@220
|
1441 |
} else {
|
deba@220
|
1442 |
_right.set(me, INVALID);
|
deba@220
|
1443 |
}
|
deba@220
|
1444 |
return me;
|
deba@220
|
1445 |
}
|
deba@220
|
1446 |
|
deba@220
|
1447 |
void refresh() {
|
deba@220
|
1448 |
for(NodeIt n(_g);n!=INVALID;++n) {
|
deba@220
|
1449 |
std::vector<Arc> v;
|
deba@233
|
1450 |
for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
|
deba@233
|
1451 |
if (!v.empty()) {
|
deba@220
|
1452 |
std::sort(v.begin(),v.end(),ArcLess(_g));
|
deba@220
|
1453 |
Arc head = refreshRec(v,0,v.size()-1);
|
deba@220
|
1454 |
_head.set(n, head);
|
deba@220
|
1455 |
_parent.set(head, INVALID);
|
deba@220
|
1456 |
}
|
deba@220
|
1457 |
else _head.set(n, INVALID);
|
deba@220
|
1458 |
}
|
deba@220
|
1459 |
}
|
deba@220
|
1460 |
|
deba@220
|
1461 |
void zig(Arc v) {
|
deba@220
|
1462 |
Arc w = _parent[v];
|
deba@220
|
1463 |
_parent.set(v, _parent[w]);
|
deba@220
|
1464 |
_parent.set(w, v);
|
deba@220
|
1465 |
_left.set(w, _right[v]);
|
deba@220
|
1466 |
_right.set(v, w);
|
deba@220
|
1467 |
if (_parent[v] != INVALID) {
|
deba@220
|
1468 |
if (_right[_parent[v]] == w) {
|
deba@220
|
1469 |
_right.set(_parent[v], v);
|
deba@220
|
1470 |
} else {
|
deba@220
|
1471 |
_left.set(_parent[v], v);
|
deba@220
|
1472 |
}
|
deba@220
|
1473 |
}
|
deba@220
|
1474 |
if (_left[w] != INVALID){
|
deba@220
|
1475 |
_parent.set(_left[w], w);
|
deba@220
|
1476 |
}
|
deba@220
|
1477 |
}
|
deba@220
|
1478 |
|
deba@220
|
1479 |
void zag(Arc v) {
|
deba@220
|
1480 |
Arc w = _parent[v];
|
deba@220
|
1481 |
_parent.set(v, _parent[w]);
|
deba@220
|
1482 |
_parent.set(w, v);
|
deba@220
|
1483 |
_right.set(w, _left[v]);
|
deba@220
|
1484 |
_left.set(v, w);
|
deba@220
|
1485 |
if (_parent[v] != INVALID){
|
deba@220
|
1486 |
if (_left[_parent[v]] == w) {
|
deba@220
|
1487 |
_left.set(_parent[v], v);
|
deba@220
|
1488 |
} else {
|
deba@220
|
1489 |
_right.set(_parent[v], v);
|
deba@220
|
1490 |
}
|
deba@220
|
1491 |
}
|
deba@220
|
1492 |
if (_right[w] != INVALID){
|
deba@220
|
1493 |
_parent.set(_right[w], w);
|
deba@220
|
1494 |
}
|
deba@220
|
1495 |
}
|
deba@220
|
1496 |
|
deba@220
|
1497 |
void splay(Arc v) {
|
deba@220
|
1498 |
while (_parent[v] != INVALID) {
|
deba@220
|
1499 |
if (v == _left[_parent[v]]) {
|
deba@220
|
1500 |
if (_parent[_parent[v]] == INVALID) {
|
deba@220
|
1501 |
zig(v);
|
deba@220
|
1502 |
} else {
|
deba@220
|
1503 |
if (_parent[v] == _left[_parent[_parent[v]]]) {
|
deba@220
|
1504 |
zig(_parent[v]);
|
deba@220
|
1505 |
zig(v);
|
deba@220
|
1506 |
} else {
|
deba@220
|
1507 |
zig(v);
|
deba@220
|
1508 |
zag(v);
|
deba@220
|
1509 |
}
|
deba@220
|
1510 |
}
|
deba@220
|
1511 |
} else {
|
deba@220
|
1512 |
if (_parent[_parent[v]] == INVALID) {
|
deba@220
|
1513 |
zag(v);
|
deba@220
|
1514 |
} else {
|
deba@220
|
1515 |
if (_parent[v] == _left[_parent[_parent[v]]]) {
|
deba@220
|
1516 |
zag(v);
|
deba@220
|
1517 |
zig(v);
|
deba@220
|
1518 |
} else {
|
deba@220
|
1519 |
zag(_parent[v]);
|
deba@220
|
1520 |
zag(v);
|
deba@220
|
1521 |
}
|
deba@220
|
1522 |
}
|
deba@220
|
1523 |
}
|
deba@220
|
1524 |
}
|
deba@220
|
1525 |
_head[_g.source(v)] = v;
|
deba@220
|
1526 |
}
|
deba@220
|
1527 |
|
deba@220
|
1528 |
|
deba@220
|
1529 |
public:
|
deba@220
|
1530 |
|
deba@220
|
1531 |
///Find an arc between two nodes.
|
deba@220
|
1532 |
|
deba@233
|
1533 |
///Find an arc between two nodes.
|
kpeter@282
|
1534 |
///\param s The source node.
|
kpeter@282
|
1535 |
///\param t The target node.
|
deba@233
|
1536 |
///\param p The previous arc between \c s and \c t. It it is INVALID or
|
deba@233
|
1537 |
///not given, the operator finds the first appropriate arc.
|
deba@233
|
1538 |
///\return An arc from \c s to \c t after \c p or
|
deba@233
|
1539 |
///\ref INVALID if there is no more.
|
deba@233
|
1540 |
///
|
deba@233
|
1541 |
///For example, you can count the number of arcs from \c u to \c v in the
|
deba@233
|
1542 |
///following way.
|
deba@233
|
1543 |
///\code
|
deba@233
|
1544 |
///DynArcLookUp<ListDigraph> ae(g);
|
deba@233
|
1545 |
///...
|
kpeter@282
|
1546 |
///int n = 0;
|
kpeter@282
|
1547 |
///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++;
|
deba@233
|
1548 |
///\endcode
|
deba@233
|
1549 |
///
|
kpeter@282
|
1550 |
///Finding the arcs take at most <em>O</em>(log<em>d</em>)
|
deba@233
|
1551 |
///amortized time, specifically, the time complexity of the lookups
|
deba@233
|
1552 |
///is equal to the optimal search tree implementation for the
|
deba@233
|
1553 |
///current query distribution in a constant factor.
|
deba@233
|
1554 |
///
|
deba@233
|
1555 |
///\note This is a dynamic data structure, therefore the data
|
kpeter@282
|
1556 |
///structure is updated after each graph alteration. Thus although
|
kpeter@282
|
1557 |
///this data structure is theoretically faster than \ref ArcLookUp
|
kpeter@317
|
1558 |
///and \ref AllArcLookUp, it often provides worse performance than
|
deba@233
|
1559 |
///them.
|
deba@233
|
1560 |
Arc operator()(Node s, Node t, Arc p = INVALID) const {
|
deba@233
|
1561 |
if (p == INVALID) {
|
deba@233
|
1562 |
Arc a = _head[s];
|
deba@233
|
1563 |
if (a == INVALID) return INVALID;
|
deba@233
|
1564 |
Arc r = INVALID;
|
deba@233
|
1565 |
while (true) {
|
deba@233
|
1566 |
if (_g.target(a) < t) {
|
deba@233
|
1567 |
if (_right[a] == INVALID) {
|
deba@233
|
1568 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
deba@233
|
1569 |
return r;
|
deba@233
|
1570 |
} else {
|
deba@233
|
1571 |
a = _right[a];
|
deba@233
|
1572 |
}
|
deba@233
|
1573 |
} else {
|
deba@233
|
1574 |
if (_g.target(a) == t) {
|
deba@233
|
1575 |
r = a;
|
deba@233
|
1576 |
}
|
deba@233
|
1577 |
if (_left[a] == INVALID) {
|
deba@233
|
1578 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
deba@233
|
1579 |
return r;
|
deba@233
|
1580 |
} else {
|
deba@233
|
1581 |
a = _left[a];
|
deba@233
|
1582 |
}
|
deba@233
|
1583 |
}
|
deba@233
|
1584 |
}
|
deba@233
|
1585 |
} else {
|
deba@233
|
1586 |
Arc a = p;
|
deba@233
|
1587 |
if (_right[a] != INVALID) {
|
deba@233
|
1588 |
a = _right[a];
|
deba@233
|
1589 |
while (_left[a] != INVALID) {
|
deba@233
|
1590 |
a = _left[a];
|
deba@233
|
1591 |
}
|
deba@220
|
1592 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
deba@233
|
1593 |
} else {
|
deba@233
|
1594 |
while (_parent[a] != INVALID && _right[_parent[a]] == a) {
|
deba@233
|
1595 |
a = _parent[a];
|
deba@233
|
1596 |
}
|
deba@233
|
1597 |
if (_parent[a] == INVALID) {
|
deba@220
|
1598 |
return INVALID;
|
deba@220
|
1599 |
} else {
|
deba@233
|
1600 |
a = _parent[a];
|
deba@220
|
1601 |
const_cast<DynArcLookUp&>(*this).splay(a);
|
deba@220
|
1602 |
}
|
deba@220
|
1603 |
}
|
deba@233
|
1604 |
if (_g.target(a) == t) return a;
|
deba@233
|
1605 |
else return INVALID;
|
deba@220
|
1606 |
}
|
deba@220
|
1607 |
}
|
deba@220
|
1608 |
|
deba@220
|
1609 |
};
|
deba@220
|
1610 |
|
kpeter@282
|
1611 |
///Fast arc look-up between given endpoints.
|
deba@220
|
1612 |
|
deba@220
|
1613 |
///Using this class, you can find an arc in a digraph from a given
|
kpeter@282
|
1614 |
///source to a given target in time <em>O</em>(log<em>d</em>),
|
deba@220
|
1615 |
///where <em>d</em> is the out-degree of the source node.
|
deba@220
|
1616 |
///
|
deba@220
|
1617 |
///It is not possible to find \e all parallel arcs between two nodes.
|
deba@220
|
1618 |
///Use \ref AllArcLookUp for this purpose.
|
deba@220
|
1619 |
///
|
kpeter@282
|
1620 |
///\warning This class is static, so you should call refresh() (or at
|
kpeter@282
|
1621 |
///least refresh(Node)) to refresh this data structure whenever the
|
kpeter@282
|
1622 |
///digraph changes. This is a time consuming (superlinearly proportional
|
kpeter@282
|
1623 |
///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
|
deba@220
|
1624 |
///
|
deba@220
|
1625 |
///\tparam G The type of the underlying digraph.
|
deba@220
|
1626 |
///
|
deba@220
|
1627 |
///\sa DynArcLookUp
|
deba@220
|
1628 |
///\sa AllArcLookUp
|
deba@220
|
1629 |
template<class G>
|
deba@220
|
1630 |
class ArcLookUp
|
deba@220
|
1631 |
{
|
deba@220
|
1632 |
public:
|
deba@220
|
1633 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
deba@220
|
1634 |
typedef G Digraph;
|
deba@220
|
1635 |
|
deba@220
|
1636 |
protected:
|
deba@220
|
1637 |
const Digraph &_g;
|
deba@220
|
1638 |
typename Digraph::template NodeMap<Arc> _head;
|
deba@220
|
1639 |
typename Digraph::template ArcMap<Arc> _left;
|
deba@220
|
1640 |
typename Digraph::template ArcMap<Arc> _right;
|
deba@220
|
1641 |
|
deba@220
|
1642 |
class ArcLess {
|
deba@220
|
1643 |
const Digraph &g;
|
deba@220
|
1644 |
public:
|
deba@220
|
1645 |
ArcLess(const Digraph &_g) : g(_g) {}
|
deba@220
|
1646 |
bool operator()(Arc a,Arc b) const
|
deba@220
|
1647 |
{
|
deba@220
|
1648 |
return g.target(a)<g.target(b);
|
deba@220
|
1649 |
}
|
deba@220
|
1650 |
};
|
deba@220
|
1651 |
|
deba@220
|
1652 |
public:
|
deba@220
|
1653 |
|
deba@220
|
1654 |
///Constructor
|
deba@220
|
1655 |
|
deba@220
|
1656 |
///Constructor.
|
deba@220
|
1657 |
///
|
deba@220
|
1658 |
///It builds up the search database, which remains valid until the digraph
|
deba@220
|
1659 |
///changes.
|
deba@220
|
1660 |
ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}
|
deba@220
|
1661 |
|
deba@220
|
1662 |
private:
|
deba@220
|
1663 |
Arc refreshRec(std::vector<Arc> &v,int a,int b)
|
deba@220
|
1664 |
{
|
deba@220
|
1665 |
int m=(a+b)/2;
|
deba@220
|
1666 |
Arc me=v[m];
|
deba@220
|
1667 |
_left[me] = a<m?refreshRec(v,a,m-1):INVALID;
|
deba@220
|
1668 |
_right[me] = m<b?refreshRec(v,m+1,b):INVALID;
|
deba@220
|
1669 |
return me;
|
deba@220
|
1670 |
}
|
deba@220
|
1671 |
public:
|
kpeter@282
|
1672 |
///Refresh the search data structure at a node.
|
deba@220
|
1673 |
|
deba@220
|
1674 |
///Build up the search database of node \c n.
|
deba@220
|
1675 |
///
|
kpeter@282
|
1676 |
///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em>
|
kpeter@282
|
1677 |
///is the number of the outgoing arcs of \c n.
|
deba@220
|
1678 |
void refresh(Node n)
|
deba@220
|
1679 |
{
|
deba@220
|
1680 |
std::vector<Arc> v;
|
deba@220
|
1681 |
for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
|
deba@220
|
1682 |
if(v.size()) {
|
deba@220
|
1683 |
std::sort(v.begin(),v.end(),ArcLess(_g));
|
deba@220
|
1684 |
_head[n]=refreshRec(v,0,v.size()-1);
|
deba@220
|
1685 |
}
|
deba@220
|
1686 |
else _head[n]=INVALID;
|
deba@220
|
1687 |
}
|
deba@220
|
1688 |
///Refresh the full data structure.
|
deba@220
|
1689 |
|
deba@220
|
1690 |
///Build up the full search database. In fact, it simply calls
|
deba@220
|
1691 |
///\ref refresh(Node) "refresh(n)" for each node \c n.
|
deba@220
|
1692 |
///
|
kpeter@282
|
1693 |
///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
|
kpeter@282
|
1694 |
///the number of the arcs in the digraph and <em>D</em> is the maximum
|
deba@220
|
1695 |
///out-degree of the digraph.
|
deba@220
|
1696 |
void refresh()
|
deba@220
|
1697 |
{
|
deba@220
|
1698 |
for(NodeIt n(_g);n!=INVALID;++n) refresh(n);
|
deba@220
|
1699 |
}
|
deba@220
|
1700 |
|
deba@220
|
1701 |
///Find an arc between two nodes.
|
deba@220
|
1702 |
|
kpeter@317
|
1703 |
///Find an arc between two nodes in time <em>O</em>(log<em>d</em>),
|
kpeter@317
|
1704 |
///where <em>d</em> is the number of outgoing arcs of \c s.
|
kpeter@282
|
1705 |
///\param s The source node.
|
kpeter@282
|
1706 |
///\param t The target node.
|
deba@220
|
1707 |
///\return An arc from \c s to \c t if there exists,
|
deba@220
|
1708 |
///\ref INVALID otherwise.
|
deba@220
|
1709 |
///
|
deba@220
|
1710 |
///\warning If you change the digraph, refresh() must be called before using
|
deba@220
|
1711 |
///this operator. If you change the outgoing arcs of
|
kpeter@282
|
1712 |
///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
|
deba@220
|
1713 |
Arc operator()(Node s, Node t) const
|
deba@220
|
1714 |
{
|
deba@220
|
1715 |
Arc e;
|
deba@220
|
1716 |
for(e=_head[s];
|
deba@220
|
1717 |
e!=INVALID&&_g.target(e)!=t;
|
deba@220
|
1718 |
e = t < _g.target(e)?_left[e]:_right[e]) ;
|
deba@220
|
1719 |
return e;
|
deba@220
|
1720 |
}
|
deba@220
|
1721 |
|
deba@220
|
1722 |
};
|
deba@220
|
1723 |
|
kpeter@282
|
1724 |
///Fast look-up of all arcs between given endpoints.
|
deba@220
|
1725 |
|
deba@220
|
1726 |
///This class is the same as \ref ArcLookUp, with the addition
|
kpeter@282
|
1727 |
///that it makes it possible to find all parallel arcs between given
|
kpeter@282
|
1728 |
///endpoints.
|
deba@220
|
1729 |
///
|
kpeter@282
|
1730 |
///\warning This class is static, so you should call refresh() (or at
|
kpeter@282
|
1731 |
///least refresh(Node)) to refresh this data structure whenever the
|
kpeter@282
|
1732 |
///digraph changes. This is a time consuming (superlinearly proportional
|
kpeter@282
|
1733 |
///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
|
deba@220
|
1734 |
///
|
deba@220
|
1735 |
///\tparam G The type of the underlying digraph.
|
deba@220
|
1736 |
///
|
deba@220
|
1737 |
///\sa DynArcLookUp
|
deba@220
|
1738 |
///\sa ArcLookUp
|
deba@220
|
1739 |
template<class G>
|
deba@220
|
1740 |
class AllArcLookUp : public ArcLookUp<G>
|
deba@220
|
1741 |
{
|
deba@220
|
1742 |
using ArcLookUp<G>::_g;
|
deba@220
|
1743 |
using ArcLookUp<G>::_right;
|
deba@220
|
1744 |
using ArcLookUp<G>::_left;
|
deba@220
|
1745 |
using ArcLookUp<G>::_head;
|
deba@220
|
1746 |
|
deba@220
|
1747 |
TEMPLATE_DIGRAPH_TYPEDEFS(G);
|
deba@220
|
1748 |
typedef G Digraph;
|
deba@220
|
1749 |
|
deba@220
|
1750 |
typename Digraph::template ArcMap<Arc> _next;
|
deba@220
|
1751 |
|
deba@220
|
1752 |
Arc refreshNext(Arc head,Arc next=INVALID)
|
deba@220
|
1753 |
{
|
deba@220
|
1754 |
if(head==INVALID) return next;
|
deba@220
|
1755 |
else {
|
deba@220
|
1756 |
next=refreshNext(_right[head],next);
|
deba@220
|
1757 |
_next[head]=( next!=INVALID && _g.target(next)==_g.target(head))
|
deba@220
|
1758 |
? next : INVALID;
|
deba@220
|
1759 |
return refreshNext(_left[head],head);
|
deba@220
|
1760 |
}
|
deba@220
|
1761 |
}
|
deba@220
|
1762 |
|
deba@220
|
1763 |
void refreshNext()
|
deba@220
|
1764 |
{
|
deba@220
|
1765 |
for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);
|
deba@220
|
1766 |
}
|
deba@220
|
1767 |
|
deba@220
|
1768 |
public:
|
deba@220
|
1769 |
///Constructor
|
deba@220
|
1770 |
|
deba@220
|
1771 |
///Constructor.
|
deba@220
|
1772 |
///
|
deba@220
|
1773 |
///It builds up the search database, which remains valid until the digraph
|
deba@220
|
1774 |
///changes.
|
deba@220
|
1775 |
AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
|
deba@220
|
1776 |
|
deba@220
|
1777 |
///Refresh the data structure at a node.
|
deba@220
|
1778 |
|
deba@220
|
1779 |
///Build up the search database of node \c n.
|
deba@220
|
1780 |
///
|
kpeter@282
|
1781 |
///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is
|
deba@220
|
1782 |
///the number of the outgoing arcs of \c n.
|
deba@220
|
1783 |
void refresh(Node n)
|
deba@220
|
1784 |
{
|
deba@220
|
1785 |
ArcLookUp<G>::refresh(n);
|
deba@220
|
1786 |
refreshNext(_head[n]);
|
deba@220
|
1787 |
}
|
deba@220
|
1788 |
|
deba@220
|
1789 |
///Refresh the full data structure.
|
deba@220
|
1790 |
|
deba@220
|
1791 |
///Build up the full search database. In fact, it simply calls
|
deba@220
|
1792 |
///\ref refresh(Node) "refresh(n)" for each node \c n.
|
deba@220
|
1793 |
///
|
kpeter@282
|
1794 |
///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is
|
kpeter@282
|
1795 |
///the number of the arcs in the digraph and <em>D</em> is the maximum
|
deba@220
|
1796 |
///out-degree of the digraph.
|
deba@220
|
1797 |
void refresh()
|
deba@220
|
1798 |
{
|
deba@220
|
1799 |
for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]);
|
deba@220
|
1800 |
}
|
deba@220
|
1801 |
|
deba@220
|
1802 |
///Find an arc between two nodes.
|
deba@220
|
1803 |
|
deba@220
|
1804 |
///Find an arc between two nodes.
|
kpeter@282
|
1805 |
///\param s The source node.
|
kpeter@282
|
1806 |
///\param t The target node.
|
deba@220
|
1807 |
///\param prev The previous arc between \c s and \c t. It it is INVALID or
|
deba@220
|
1808 |
///not given, the operator finds the first appropriate arc.
|
deba@220
|
1809 |
///\return An arc from \c s to \c t after \c prev or
|
deba@220
|
1810 |
///\ref INVALID if there is no more.
|
deba@220
|
1811 |
///
|
deba@220
|
1812 |
///For example, you can count the number of arcs from \c u to \c v in the
|
deba@220
|
1813 |
///following way.
|
deba@220
|
1814 |
///\code
|
deba@220
|
1815 |
///AllArcLookUp<ListDigraph> ae(g);
|
deba@220
|
1816 |
///...
|
kpeter@282
|
1817 |
///int n = 0;
|
kpeter@282
|
1818 |
///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++;
|
deba@220
|
1819 |
///\endcode
|
deba@220
|
1820 |
///
|
kpeter@317
|
1821 |
///Finding the first arc take <em>O</em>(log<em>d</em>) time,
|
kpeter@317
|
1822 |
///where <em>d</em> is the number of outgoing arcs of \c s. Then the
|
deba@220
|
1823 |
///consecutive arcs are found in constant time.
|
deba@220
|
1824 |
///
|
deba@220
|
1825 |
///\warning If you change the digraph, refresh() must be called before using
|
deba@220
|
1826 |
///this operator. If you change the outgoing arcs of
|
kpeter@282
|
1827 |
///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough.
|
deba@220
|
1828 |
///
|
deba@220
|
1829 |
#ifdef DOXYGEN
|
deba@220
|
1830 |
Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
|
deba@220
|
1831 |
#else
|
deba@220
|
1832 |
using ArcLookUp<G>::operator() ;
|
deba@220
|
1833 |
Arc operator()(Node s, Node t, Arc prev) const
|
deba@220
|
1834 |
{
|
deba@220
|
1835 |
return prev==INVALID?(*this)(s,t):_next[prev];
|
deba@220
|
1836 |
}
|
deba@220
|
1837 |
#endif
|
deba@220
|
1838 |
|
deba@220
|
1839 |
};
|
deba@220
|
1840 |
|
deba@220
|
1841 |
/// @}
|
deba@220
|
1842 |
|
deba@220
|
1843 |
} //namespace lemon
|
deba@220
|
1844 |
|
deba@220
|
1845 |
#endif
|