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