changeset 321 | 689f24ee83e6 |
parent 233 | 28239207a8a3 |
child 304 | 8c05947fc107 |
3:16844a528923 | 4:8b39b894a76c |
---|---|
56 #endif |
56 #endif |
57 |
57 |
58 /// \addtogroup gutils |
58 /// \addtogroup gutils |
59 /// @{ |
59 /// @{ |
60 |
60 |
61 ///Creates convenience typedefs for the digraph types and iterators |
61 ///Create convenient typedefs for the digraph types and iterators |
62 |
62 |
63 ///This \c \#define creates convenience typedefs for the following types |
63 ///This \c \#define creates convenient type definitions for the following |
64 ///of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, |
64 ///types of \c Digraph: \c Node, \c NodeIt, \c Arc, \c ArcIt, \c InArcIt, |
65 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
65 ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap, |
66 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
66 ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap. |
67 /// |
67 /// |
68 ///\note If the graph type is a dependent type, ie. the graph type depend |
68 ///\note If the graph type is a dependent type, ie. the graph type depend |
69 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
69 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
78 typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
78 typedef Digraph::NodeMap<bool> BoolNodeMap; \ |
79 typedef Digraph::NodeMap<int> IntNodeMap; \ |
79 typedef Digraph::NodeMap<int> IntNodeMap; \ |
80 typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
80 typedef Digraph::NodeMap<double> DoubleNodeMap; \ |
81 typedef Digraph::ArcMap<bool> BoolArcMap; \ |
81 typedef Digraph::ArcMap<bool> BoolArcMap; \ |
82 typedef Digraph::ArcMap<int> IntArcMap; \ |
82 typedef Digraph::ArcMap<int> IntArcMap; \ |
83 typedef Digraph::ArcMap<double> DoubleArcMap |
83 typedef Digraph::ArcMap<double> DoubleArcMap; |
84 |
84 |
85 ///Creates convenience typedefs for the digraph types and iterators |
85 ///Create convenient typedefs for the digraph types and iterators |
86 |
86 |
87 ///\see DIGRAPH_TYPEDEFS |
87 ///\see DIGRAPH_TYPEDEFS |
88 /// |
88 /// |
89 ///\note Use this macro, if the graph type is a dependent type, |
89 ///\note Use this macro, if the graph type is a dependent type, |
90 ///ie. the graph type depend on a template parameter. |
90 ///ie. the graph type depend on a template parameter. |
98 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
98 typedef typename Digraph::template NodeMap<bool> BoolNodeMap; \ |
99 typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
99 typedef typename Digraph::template NodeMap<int> IntNodeMap; \ |
100 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
100 typedef typename Digraph::template NodeMap<double> DoubleNodeMap; \ |
101 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
101 typedef typename Digraph::template ArcMap<bool> BoolArcMap; \ |
102 typedef typename Digraph::template ArcMap<int> IntArcMap; \ |
102 typedef typename Digraph::template ArcMap<int> IntArcMap; \ |
103 typedef typename Digraph::template ArcMap<double> DoubleArcMap |
103 typedef typename Digraph::template ArcMap<double> DoubleArcMap; |
104 |
104 |
105 ///Creates convenience typedefs for the graph types and iterators |
105 ///Create convenient typedefs for the graph types and iterators |
106 |
106 |
107 ///This \c \#define creates the same convenience typedefs as defined |
107 ///This \c \#define creates the same convenient type definitions as defined |
108 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates |
108 ///by \ref DIGRAPH_TYPEDEFS(Graph) and six more, namely it creates |
109 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, |
109 ///\c Edge, \c EdgeIt, \c IncEdgeIt, \c BoolEdgeMap, \c IntEdgeMap, |
110 ///\c DoubleEdgeMap. |
110 ///\c DoubleEdgeMap. |
111 /// |
111 /// |
112 ///\note If the graph type is a dependent type, ie. the graph type depend |
112 ///\note If the graph type is a dependent type, ie. the graph type depend |
113 ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS() |
113 ///on a template parameter, then use \c TEMPLATE_GRAPH_TYPEDEFS() |
114 ///macro. |
114 ///macro. |
115 #define GRAPH_TYPEDEFS(Graph) \ |
115 #define GRAPH_TYPEDEFS(Graph) \ |
116 DIGRAPH_TYPEDEFS(Graph); \ |
116 DIGRAPH_TYPEDEFS(Graph); \ |
117 typedef Graph::Edge Edge; \ |
117 typedef Graph::Edge Edge; \ |
118 typedef Graph::EdgeIt EdgeIt; \ |
118 typedef Graph::EdgeIt EdgeIt; \ |
119 typedef Graph::IncEdgeIt IncEdgeIt; \ |
119 typedef Graph::IncEdgeIt IncEdgeIt; \ |
120 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
120 typedef Graph::EdgeMap<bool> BoolEdgeMap; \ |
121 typedef Graph::EdgeMap<int> IntEdgeMap; \ |
121 typedef Graph::EdgeMap<int> IntEdgeMap; \ |
122 typedef Graph::EdgeMap<double> DoubleEdgeMap |
122 typedef Graph::EdgeMap<double> DoubleEdgeMap; |
123 |
123 |
124 ///Creates convenience typedefs for the graph types and iterators |
124 ///Create convenient typedefs for the graph types and iterators |
125 |
125 |
126 ///\see GRAPH_TYPEDEFS |
126 ///\see GRAPH_TYPEDEFS |
127 /// |
127 /// |
128 ///\note Use this macro, if the graph type is a dependent type, |
128 ///\note Use this macro, if the graph type is a dependent type, |
129 ///ie. the graph type depend on a template parameter. |
129 ///ie. the graph type depend on a template parameter. |
132 typedef typename Graph::Edge Edge; \ |
132 typedef typename Graph::Edge Edge; \ |
133 typedef typename Graph::EdgeIt EdgeIt; \ |
133 typedef typename Graph::EdgeIt EdgeIt; \ |
134 typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
134 typedef typename Graph::IncEdgeIt IncEdgeIt; \ |
135 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
135 typedef typename Graph::template EdgeMap<bool> BoolEdgeMap; \ |
136 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ |
136 typedef typename Graph::template EdgeMap<int> IntEdgeMap; \ |
137 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap |
137 typedef typename Graph::template EdgeMap<double> DoubleEdgeMap; |
138 |
138 |
139 /// \brief Function to count the items in the graph. |
139 /// \brief Function to count the items in a graph. |
140 /// |
140 /// |
141 /// This function counts the items (nodes, arcs etc) in the graph. |
141 /// This function counts the items (nodes, arcs etc.) in a graph. |
142 /// The complexity of the function is O(n) because |
142 /// The complexity of the function is linear because |
143 /// it iterates on all of the items. |
143 /// it iterates on all of the items. |
144 template <typename Graph, typename Item> |
144 template <typename Graph, typename Item> |
145 inline int countItems(const Graph& g) { |
145 inline int countItems(const Graph& g) { |
146 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
146 typedef typename ItemSetTraits<Graph, Item>::ItemIt ItemIt; |
147 int num = 0; |
147 int num = 0; |
174 } |
174 } |
175 |
175 |
176 /// \brief Function to count the nodes in the graph. |
176 /// \brief Function to count the nodes in the graph. |
177 /// |
177 /// |
178 /// This function counts the nodes in the graph. |
178 /// This function counts the nodes in the graph. |
179 /// The complexity of the function is O(n) but for some |
179 /// The complexity of the function is <em>O</em>(<em>n</em>), but for some |
180 /// graph structures it is specialized to run in O(1). |
180 /// graph structures it is specialized to run in <em>O</em>(1). |
181 /// |
181 /// |
182 /// If the graph contains a \e nodeNum() member function and a |
182 /// \note If the graph contains a \c nodeNum() member function and a |
183 /// \e NodeNumTag tag then this function calls directly the member |
183 /// \c NodeNumTag tag then this function calls directly the member |
184 /// function to query the cardinality of the node set. |
184 /// function to query the cardinality of the node set. |
185 template <typename Graph> |
185 template <typename Graph> |
186 inline int countNodes(const Graph& g) { |
186 inline int countNodes(const Graph& g) { |
187 return _core_bits::CountNodesSelector<Graph>::count(g); |
187 return _core_bits::CountNodesSelector<Graph>::count(g); |
188 } |
188 } |
210 } |
210 } |
211 |
211 |
212 /// \brief Function to count the arcs in the graph. |
212 /// \brief Function to count the arcs in the graph. |
213 /// |
213 /// |
214 /// This function counts the arcs in the graph. |
214 /// This function counts the arcs in the graph. |
215 /// The complexity of the function is O(e) but for some |
215 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some |
216 /// graph structures it is specialized to run in O(1). |
216 /// graph structures it is specialized to run in <em>O</em>(1). |
217 /// |
217 /// |
218 /// If the graph contains a \e arcNum() member function and a |
218 /// \note If the graph contains a \c arcNum() member function and a |
219 /// \e EdgeNumTag tag then this function calls directly the member |
219 /// \c ArcNumTag tag then this function calls directly the member |
220 /// function to query the cardinality of the arc set. |
220 /// function to query the cardinality of the arc set. |
221 template <typename Graph> |
221 template <typename Graph> |
222 inline int countArcs(const Graph& g) { |
222 inline int countArcs(const Graph& g) { |
223 return _core_bits::CountArcsSelector<Graph>::count(g); |
223 return _core_bits::CountArcsSelector<Graph>::count(g); |
224 } |
224 } |
225 |
225 |
226 // Edge counting: |
226 // Edge counting: |
227 |
|
227 namespace _core_bits { |
228 namespace _core_bits { |
228 |
229 |
229 template <typename Graph, typename Enable = void> |
230 template <typename Graph, typename Enable = void> |
230 struct CountEdgesSelector { |
231 struct CountEdgesSelector { |
231 static int count(const Graph &g) { |
232 static int count(const Graph &g) { |
245 } |
246 } |
246 |
247 |
247 /// \brief Function to count the edges in the graph. |
248 /// \brief Function to count the edges in the graph. |
248 /// |
249 /// |
249 /// This function counts the edges in the graph. |
250 /// This function counts the edges in the graph. |
250 /// The complexity of the function is O(m) but for some |
251 /// The complexity of the function is <em>O</em>(<em>m</em>), but for some |
251 /// graph structures it is specialized to run in O(1). |
252 /// graph structures it is specialized to run in <em>O</em>(1). |
252 /// |
253 /// |
253 /// If the graph contains a \e edgeNum() member function and a |
254 /// \note If the graph contains a \c edgeNum() member function and a |
254 /// \e EdgeNumTag tag then this function calls directly the member |
255 /// \c EdgeNumTag tag then this function calls directly the member |
255 /// function to query the cardinality of the edge set. |
256 /// function to query the cardinality of the edge set. |
256 template <typename Graph> |
257 template <typename Graph> |
257 inline int countEdges(const Graph& g) { |
258 inline int countEdges(const Graph& g) { |
258 return _core_bits::CountEdgesSelector<Graph>::count(g); |
259 return _core_bits::CountEdgesSelector<Graph>::count(g); |
259 |
260 |
270 } |
271 } |
271 |
272 |
272 /// \brief Function to count the number of the out-arcs from node \c n. |
273 /// \brief Function to count the number of the out-arcs from node \c n. |
273 /// |
274 /// |
274 /// This function counts the number of the out-arcs from node \c n |
275 /// This function counts the number of the out-arcs from node \c n |
275 /// in the graph. |
276 /// in the graph \c g. |
276 template <typename Graph> |
277 template <typename Graph> |
277 inline int countOutArcs(const Graph& _g, const typename Graph::Node& _n) { |
278 inline int countOutArcs(const Graph& g, const typename Graph::Node& n) { |
278 return countNodeDegree<Graph, typename Graph::OutArcIt>(_g, _n); |
279 return countNodeDegree<Graph, typename Graph::OutArcIt>(g, n); |
279 } |
280 } |
280 |
281 |
281 /// \brief Function to count the number of the in-arcs to node \c n. |
282 /// \brief Function to count the number of the in-arcs to node \c n. |
282 /// |
283 /// |
283 /// This function counts the number of the in-arcs to node \c n |
284 /// This function counts the number of the in-arcs to node \c n |
284 /// in the graph. |
285 /// in the graph \c g. |
285 template <typename Graph> |
286 template <typename Graph> |
286 inline int countInArcs(const Graph& _g, const typename Graph::Node& _n) { |
287 inline int countInArcs(const Graph& g, const typename Graph::Node& n) { |
287 return countNodeDegree<Graph, typename Graph::InArcIt>(_g, _n); |
288 return countNodeDegree<Graph, typename Graph::InArcIt>(g, n); |
288 } |
289 } |
289 |
290 |
290 /// \brief Function to count the number of the inc-edges to node \c n. |
291 /// \brief Function to count the number of the inc-edges to node \c n. |
291 /// |
292 /// |
292 /// This function counts the number of the inc-edges to node \c n |
293 /// This function counts the number of the inc-edges to node \c n |
293 /// in the graph. |
294 /// in the undirected graph \c g. |
294 template <typename Graph> |
295 template <typename Graph> |
295 inline int countIncEdges(const Graph& _g, const typename Graph::Node& _n) { |
296 inline int countIncEdges(const Graph& g, const typename Graph::Node& n) { |
296 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(_g, _n); |
297 return countNodeDegree<Graph, typename Graph::IncEdgeIt>(g, n); |
297 } |
298 } |
298 |
299 |
299 namespace _core_bits { |
300 namespace _core_bits { |
300 |
301 |
301 template <typename Digraph, typename Item, typename RefMap> |
302 template <typename Digraph, typename Item, typename RefMap> |
305 |
306 |
306 virtual ~MapCopyBase() {} |
307 virtual ~MapCopyBase() {} |
307 }; |
308 }; |
308 |
309 |
309 template <typename Digraph, typename Item, typename RefMap, |
310 template <typename Digraph, typename Item, typename RefMap, |
310 typename ToMap, typename FromMap> |
311 typename FromMap, typename ToMap> |
311 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { |
312 class MapCopy : public MapCopyBase<Digraph, Item, RefMap> { |
312 public: |
313 public: |
313 |
314 |
314 MapCopy(ToMap& tmap, const FromMap& map) |
315 MapCopy(const FromMap& map, ToMap& tmap) |
315 : _tmap(tmap), _map(map) {} |
316 : _map(map), _tmap(tmap) {} |
316 |
317 |
317 virtual void copy(const Digraph& digraph, const RefMap& refMap) { |
318 virtual void copy(const Digraph& digraph, const RefMap& refMap) { |
318 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; |
319 typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt; |
319 for (ItemIt it(digraph); it != INVALID; ++it) { |
320 for (ItemIt it(digraph); it != INVALID; ++it) { |
320 _tmap.set(refMap[it], _map[it]); |
321 _tmap.set(refMap[it], _map[it]); |
321 } |
322 } |
322 } |
323 } |
323 |
324 |
324 private: |
325 private: |
326 const FromMap& _map; |
|
325 ToMap& _tmap; |
327 ToMap& _tmap; |
326 const FromMap& _map; |
|
327 }; |
328 }; |
328 |
329 |
329 template <typename Digraph, typename Item, typename RefMap, typename It> |
330 template <typename Digraph, typename Item, typename RefMap, typename It> |
330 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> { |
331 class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> { |
331 public: |
332 public: |
332 |
333 |
333 ItemCopy(It& it, const Item& item) : _it(it), _item(item) {} |
334 ItemCopy(const Item& item, It& it) : _item(item), _it(it) {} |
334 |
335 |
335 virtual void copy(const Digraph&, const RefMap& refMap) { |
336 virtual void copy(const Digraph&, const RefMap& refMap) { |
336 _it = refMap[_item]; |
337 _it = refMap[_item]; |
337 } |
338 } |
338 |
339 |
339 private: |
340 private: |
341 Item _item; |
|
340 It& _it; |
342 It& _it; |
341 Item _item; |
|
342 }; |
343 }; |
343 |
344 |
344 template <typename Digraph, typename Item, typename RefMap, typename Ref> |
345 template <typename Digraph, typename Item, typename RefMap, typename Ref> |
345 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> { |
346 class RefCopy : public MapCopyBase<Digraph, Item, RefMap> { |
346 public: |
347 public: |
377 }; |
378 }; |
378 |
379 |
379 template <typename Digraph, typename Enable = void> |
380 template <typename Digraph, typename Enable = void> |
380 struct DigraphCopySelector { |
381 struct DigraphCopySelector { |
381 template <typename From, typename NodeRefMap, typename ArcRefMap> |
382 template <typename From, typename NodeRefMap, typename ArcRefMap> |
382 static void copy(Digraph &to, const From& from, |
383 static void copy(const From& from, Digraph &to, |
383 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
384 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
384 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
385 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
385 nodeRefMap[it] = to.addNode(); |
386 nodeRefMap[it] = to.addNode(); |
386 } |
387 } |
387 for (typename From::ArcIt it(from); it != INVALID; ++it) { |
388 for (typename From::ArcIt it(from); it != INVALID; ++it) { |
395 struct DigraphCopySelector< |
396 struct DigraphCopySelector< |
396 Digraph, |
397 Digraph, |
397 typename enable_if<typename Digraph::BuildTag, void>::type> |
398 typename enable_if<typename Digraph::BuildTag, void>::type> |
398 { |
399 { |
399 template <typename From, typename NodeRefMap, typename ArcRefMap> |
400 template <typename From, typename NodeRefMap, typename ArcRefMap> |
400 static void copy(Digraph &to, const From& from, |
401 static void copy(const From& from, Digraph &to, |
401 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
402 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { |
402 to.build(from, nodeRefMap, arcRefMap); |
403 to.build(from, nodeRefMap, arcRefMap); |
403 } |
404 } |
404 }; |
405 }; |
405 |
406 |
406 template <typename Graph, typename Enable = void> |
407 template <typename Graph, typename Enable = void> |
407 struct GraphCopySelector { |
408 struct GraphCopySelector { |
408 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
409 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
409 static void copy(Graph &to, const From& from, |
410 static void copy(const From& from, Graph &to, |
410 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
411 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
411 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
412 for (typename From::NodeIt it(from); it != INVALID; ++it) { |
412 nodeRefMap[it] = to.addNode(); |
413 nodeRefMap[it] = to.addNode(); |
413 } |
414 } |
414 for (typename From::EdgeIt it(from); it != INVALID; ++it) { |
415 for (typename From::EdgeIt it(from); it != INVALID; ++it) { |
422 struct GraphCopySelector< |
423 struct GraphCopySelector< |
423 Graph, |
424 Graph, |
424 typename enable_if<typename Graph::BuildTag, void>::type> |
425 typename enable_if<typename Graph::BuildTag, void>::type> |
425 { |
426 { |
426 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
427 template <typename From, typename NodeRefMap, typename EdgeRefMap> |
427 static void copy(Graph &to, const From& from, |
428 static void copy(const From& from, Graph &to, |
428 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
429 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { |
429 to.build(from, nodeRefMap, edgeRefMap); |
430 to.build(from, nodeRefMap, edgeRefMap); |
430 } |
431 } |
431 }; |
432 }; |
432 |
433 |
433 } |
434 } |
434 |
435 |
435 /// \brief Class to copy a digraph. |
436 /// \brief Class to copy a digraph. |
436 /// |
437 /// |
437 /// Class to copy a digraph to another digraph (duplicate a digraph). The |
438 /// Class to copy a digraph to another digraph (duplicate a digraph). The |
438 /// simplest way of using it is through the \c copyDigraph() function. |
439 /// simplest way of using it is through the \c digraphCopy() function. |
439 /// |
440 /// |
440 /// This class not just make a copy of a graph, but it can create |
441 /// This class not only make a copy of a digraph, but it can create |
441 /// references and cross references between the nodes and arcs of |
442 /// references and cross references between the nodes and arcs of |
442 /// the two graphs, it can copy maps for use with the newly created |
443 /// the two digraphs, and it can copy maps to use with the newly created |
443 /// graph and copy nodes and arcs. |
444 /// digraph. |
444 /// |
445 /// |
445 /// To make a copy from a graph, first an instance of DigraphCopy |
446 /// To make a copy from a digraph, first an instance of DigraphCopy |
446 /// should be created, then the data belongs to the graph should |
447 /// should be created, then the data belongs to the digraph should |
447 /// assigned to copy. In the end, the \c run() member should be |
448 /// assigned to copy. In the end, the \c run() member should be |
448 /// called. |
449 /// called. |
449 /// |
450 /// |
450 /// The next code copies a graph with several data: |
451 /// The next code copies a digraph with several data: |
451 ///\code |
452 ///\code |
452 /// DigraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); |
453 /// DigraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); |
453 /// // create a reference for the nodes |
454 /// // Create references for the nodes |
454 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
455 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
455 /// dc.nodeRef(nr); |
456 /// cg.nodeRef(nr); |
456 /// // create a cross reference (inverse) for the arcs |
457 /// // Create cross references (inverse) for the arcs |
457 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); |
458 /// NewGraph::ArcMap<OrigGraph::Arc> acr(new_graph); |
458 /// dc.arcCrossRef(acr); |
459 /// cg.arcCrossRef(acr); |
459 /// // copy an arc map |
460 /// // Copy an arc map |
460 /// OrigGraph::ArcMap<double> oamap(orig_graph); |
461 /// OrigGraph::ArcMap<double> oamap(orig_graph); |
461 /// NewGraph::ArcMap<double> namap(new_graph); |
462 /// NewGraph::ArcMap<double> namap(new_graph); |
462 /// dc.arcMap(namap, oamap); |
463 /// cg.arcMap(oamap, namap); |
463 /// // copy a node |
464 /// // Copy a node |
464 /// OrigGraph::Node on; |
465 /// OrigGraph::Node on; |
465 /// NewGraph::Node nn; |
466 /// NewGraph::Node nn; |
466 /// dc.node(nn, on); |
467 /// cg.node(on, nn); |
467 /// // Executions of copy |
468 /// // Execute copying |
468 /// dc.run(); |
469 /// cg.run(); |
469 ///\endcode |
470 ///\endcode |
470 template <typename To, typename From> |
471 template <typename From, typename To> |
471 class DigraphCopy { |
472 class DigraphCopy { |
472 private: |
473 private: |
473 |
474 |
474 typedef typename From::Node Node; |
475 typedef typename From::Node Node; |
475 typedef typename From::NodeIt NodeIt; |
476 typedef typename From::NodeIt NodeIt; |
480 typedef typename To::Arc TArc; |
481 typedef typename To::Arc TArc; |
481 |
482 |
482 typedef typename From::template NodeMap<TNode> NodeRefMap; |
483 typedef typename From::template NodeMap<TNode> NodeRefMap; |
483 typedef typename From::template ArcMap<TArc> ArcRefMap; |
484 typedef typename From::template ArcMap<TArc> ArcRefMap; |
484 |
485 |
485 |
|
486 public: |
486 public: |
487 |
487 |
488 |
488 /// \brief Constructor of DigraphCopy. |
489 /// \brief Constructor for the DigraphCopy. |
489 /// |
490 /// |
490 /// Constructor of DigraphCopy for copying the content of the |
491 /// It copies the content of the \c _from digraph into the |
491 /// \c from digraph into the \c to digraph. |
492 /// \c _to digraph. |
492 DigraphCopy(const From& from, To& to) |
493 DigraphCopy(To& to, const From& from) |
|
494 : _from(from), _to(to) {} |
493 : _from(from), _to(to) {} |
495 |
494 |
496 /// \brief Destructor of the DigraphCopy |
495 /// \brief Destructor of DigraphCopy |
497 /// |
496 /// |
498 /// Destructor of the DigraphCopy |
497 /// Destructor of DigraphCopy. |
499 ~DigraphCopy() { |
498 ~DigraphCopy() { |
500 for (int i = 0; i < int(_node_maps.size()); ++i) { |
499 for (int i = 0; i < int(_node_maps.size()); ++i) { |
501 delete _node_maps[i]; |
500 delete _node_maps[i]; |
502 } |
501 } |
503 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
502 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
504 delete _arc_maps[i]; |
503 delete _arc_maps[i]; |
505 } |
504 } |
506 |
505 |
507 } |
506 } |
508 |
507 |
509 /// \brief Copies the node references into the given map. |
508 /// \brief Copy the node references into the given map. |
510 /// |
509 /// |
511 /// Copies the node references into the given map. The parameter |
510 /// This function copies the node references into the given map. |
512 /// should be a map, which key type is the Node type of the source |
511 /// The parameter should be a map, whose key type is the Node type of |
513 /// graph, while the value type is the Node type of the |
512 /// the source digraph, while the value type is the Node type of the |
514 /// destination graph. |
513 /// destination digraph. |
515 template <typename NodeRef> |
514 template <typename NodeRef> |
516 DigraphCopy& nodeRef(NodeRef& map) { |
515 DigraphCopy& nodeRef(NodeRef& map) { |
517 _node_maps.push_back(new _core_bits::RefCopy<From, Node, |
516 _node_maps.push_back(new _core_bits::RefCopy<From, Node, |
518 NodeRefMap, NodeRef>(map)); |
517 NodeRefMap, NodeRef>(map)); |
519 return *this; |
518 return *this; |
520 } |
519 } |
521 |
520 |
522 /// \brief Copies the node cross references into the given map. |
521 /// \brief Copy the node cross references into the given map. |
523 /// |
522 /// |
524 /// Copies the node cross references (reverse references) into |
523 /// This function copies the node cross references (reverse references) |
525 /// the given map. The parameter should be a map, which key type |
524 /// into the given map. The parameter should be a map, whose key type |
526 /// is the Node type of the destination graph, while the value type is |
525 /// is the Node type of the destination digraph, while the value type is |
527 /// the Node type of the source graph. |
526 /// the Node type of the source digraph. |
528 template <typename NodeCrossRef> |
527 template <typename NodeCrossRef> |
529 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { |
528 DigraphCopy& nodeCrossRef(NodeCrossRef& map) { |
530 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, |
529 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, |
531 NodeRefMap, NodeCrossRef>(map)); |
530 NodeRefMap, NodeCrossRef>(map)); |
532 return *this; |
531 return *this; |
533 } |
532 } |
534 |
533 |
535 /// \brief Make copy of the given map. |
534 /// \brief Make a copy of the given node map. |
536 /// |
535 /// |
537 /// Makes copy of the given map for the newly created digraph. |
536 /// This function makes a copy of the given node map for the newly |
538 /// The new map's key type is the destination graph's node type, |
537 /// created digraph. |
539 /// and the copied map's key type is the source graph's node type. |
538 /// The key type of the new map \c tmap should be the Node type of the |
540 template <typename ToMap, typename FromMap> |
539 /// destination digraph, and the key type of the original map \c map |
541 DigraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { |
540 /// should be the Node type of the source digraph. |
541 template <typename FromMap, typename ToMap> |
|
542 DigraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { |
|
542 _node_maps.push_back(new _core_bits::MapCopy<From, Node, |
543 _node_maps.push_back(new _core_bits::MapCopy<From, Node, |
543 NodeRefMap, ToMap, FromMap>(tmap, map)); |
544 NodeRefMap, FromMap, ToMap>(map, tmap)); |
544 return *this; |
545 return *this; |
545 } |
546 } |
546 |
547 |
547 /// \brief Make a copy of the given node. |
548 /// \brief Make a copy of the given node. |
548 /// |
549 /// |
549 /// Make a copy of the given node. |
550 /// This function makes a copy of the given node. |
550 DigraphCopy& node(TNode& tnode, const Node& snode) { |
551 DigraphCopy& node(const Node& node, TNode& tnode) { |
551 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, |
552 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, |
552 NodeRefMap, TNode>(tnode, snode)); |
553 NodeRefMap, TNode>(node, tnode)); |
553 return *this; |
554 return *this; |
554 } |
555 } |
555 |
556 |
556 /// \brief Copies the arc references into the given map. |
557 /// \brief Copy the arc references into the given map. |
557 /// |
558 /// |
558 /// Copies the arc references into the given map. |
559 /// This function copies the arc references into the given map. |
560 /// The parameter should be a map, whose key type is the Arc type of |
|
561 /// the source digraph, while the value type is the Arc type of the |
|
562 /// destination digraph. |
|
559 template <typename ArcRef> |
563 template <typename ArcRef> |
560 DigraphCopy& arcRef(ArcRef& map) { |
564 DigraphCopy& arcRef(ArcRef& map) { |
561 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, |
565 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, |
562 ArcRefMap, ArcRef>(map)); |
566 ArcRefMap, ArcRef>(map)); |
563 return *this; |
567 return *this; |
564 } |
568 } |
565 |
569 |
566 /// \brief Copies the arc cross references into the given map. |
570 /// \brief Copy the arc cross references into the given map. |
567 /// |
571 /// |
568 /// Copies the arc cross references (reverse references) into |
572 /// This function copies the arc cross references (reverse references) |
569 /// the given map. |
573 /// into the given map. The parameter should be a map, whose key type |
574 /// is the Arc type of the destination digraph, while the value type is |
|
575 /// the Arc type of the source digraph. |
|
570 template <typename ArcCrossRef> |
576 template <typename ArcCrossRef> |
571 DigraphCopy& arcCrossRef(ArcCrossRef& map) { |
577 DigraphCopy& arcCrossRef(ArcCrossRef& map) { |
572 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, |
578 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, |
573 ArcRefMap, ArcCrossRef>(map)); |
579 ArcRefMap, ArcCrossRef>(map)); |
574 return *this; |
580 return *this; |
575 } |
581 } |
576 |
582 |
577 /// \brief Make copy of the given map. |
583 /// \brief Make a copy of the given arc map. |
578 /// |
584 /// |
579 /// Makes copy of the given map for the newly created digraph. |
585 /// This function makes a copy of the given arc map for the newly |
580 /// The new map's key type is the to digraph's arc type, |
586 /// created digraph. |
581 /// and the copied map's key type is the from digraph's arc |
587 /// The key type of the new map \c tmap should be the Arc type of the |
582 /// type. |
588 /// destination digraph, and the key type of the original map \c map |
583 template <typename ToMap, typename FromMap> |
589 /// should be the Arc type of the source digraph. |
584 DigraphCopy& arcMap(ToMap& tmap, const FromMap& map) { |
590 template <typename FromMap, typename ToMap> |
591 DigraphCopy& arcMap(const FromMap& map, ToMap& tmap) { |
|
585 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, |
592 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, |
586 ArcRefMap, ToMap, FromMap>(tmap, map)); |
593 ArcRefMap, FromMap, ToMap>(map, tmap)); |
587 return *this; |
594 return *this; |
588 } |
595 } |
589 |
596 |
590 /// \brief Make a copy of the given arc. |
597 /// \brief Make a copy of the given arc. |
591 /// |
598 /// |
592 /// Make a copy of the given arc. |
599 /// This function makes a copy of the given arc. |
593 DigraphCopy& arc(TArc& tarc, const Arc& sarc) { |
600 DigraphCopy& arc(const Arc& arc, TArc& tarc) { |
594 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, |
601 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, |
595 ArcRefMap, TArc>(tarc, sarc)); |
602 ArcRefMap, TArc>(arc, tarc)); |
596 return *this; |
603 return *this; |
597 } |
604 } |
598 |
605 |
599 /// \brief Executes the copies. |
606 /// \brief Execute copying. |
600 /// |
607 /// |
601 /// Executes the copies. |
608 /// This function executes the copying of the digraph along with the |
609 /// copying of the assigned data. |
|
602 void run() { |
610 void run() { |
603 NodeRefMap nodeRefMap(_from); |
611 NodeRefMap nodeRefMap(_from); |
604 ArcRefMap arcRefMap(_from); |
612 ArcRefMap arcRefMap(_from); |
605 _core_bits::DigraphCopySelector<To>:: |
613 _core_bits::DigraphCopySelector<To>:: |
606 copy(_to, _from, nodeRefMap, arcRefMap); |
614 copy(_from, _to, nodeRefMap, arcRefMap); |
607 for (int i = 0; i < int(_node_maps.size()); ++i) { |
615 for (int i = 0; i < int(_node_maps.size()); ++i) { |
608 _node_maps[i]->copy(_from, nodeRefMap); |
616 _node_maps[i]->copy(_from, nodeRefMap); |
609 } |
617 } |
610 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
618 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
611 _arc_maps[i]->copy(_from, arcRefMap); |
619 _arc_maps[i]->copy(_from, arcRefMap); |
612 } |
620 } |
613 } |
621 } |
614 |
622 |
615 protected: |
623 protected: |
616 |
624 |
617 |
|
618 const From& _from; |
625 const From& _from; |
619 To& _to; |
626 To& _to; |
620 |
627 |
621 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > |
628 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > |
622 _node_maps; |
629 _node_maps; |
623 |
630 |
624 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
631 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
625 _arc_maps; |
632 _arc_maps; |
626 |
633 |
627 }; |
634 }; |
628 |
635 |
629 /// \brief Copy a digraph to another digraph. |
636 /// \brief Copy a digraph to another digraph. |
630 /// |
637 /// |
631 /// Copy a digraph to another digraph. The complete usage of the |
638 /// This function copies a digraph to another digraph. |
632 /// function is detailed in the DigraphCopy class, but a short |
639 /// The complete usage of it is detailed in the DigraphCopy class, but |
633 /// example shows a basic work: |
640 /// a short example shows a basic work: |
634 ///\code |
641 ///\code |
635 /// copyDigraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); |
642 /// digraphCopy(src, trg).nodeRef(nr).arcCrossRef(acr).run(); |
636 ///\endcode |
643 ///\endcode |
637 /// |
644 /// |
638 /// After the copy the \c nr map will contain the mapping from the |
645 /// After the copy the \c nr map will contain the mapping from the |
639 /// nodes of the \c from digraph to the nodes of the \c to digraph and |
646 /// nodes of the \c from digraph to the nodes of the \c to digraph and |
640 /// \c ecr will contain the mapping from the arcs of the \c to digraph |
647 /// \c acr will contain the mapping from the arcs of the \c to digraph |
641 /// to the arcs of the \c from digraph. |
648 /// to the arcs of the \c from digraph. |
642 /// |
649 /// |
643 /// \see DigraphCopy |
650 /// \see DigraphCopy |
644 template <typename To, typename From> |
651 template <typename From, typename To> |
645 DigraphCopy<To, From> copyDigraph(To& to, const From& from) { |
652 DigraphCopy<From, To> digraphCopy(const From& from, To& to) { |
646 return DigraphCopy<To, From>(to, from); |
653 return DigraphCopy<From, To>(from, to); |
647 } |
654 } |
648 |
655 |
649 /// \brief Class to copy a graph. |
656 /// \brief Class to copy a graph. |
650 /// |
657 /// |
651 /// Class to copy a graph to another graph (duplicate a graph). The |
658 /// Class to copy a graph to another graph (duplicate a graph). The |
652 /// simplest way of using it is through the \c copyGraph() function. |
659 /// simplest way of using it is through the \c graphCopy() function. |
653 /// |
660 /// |
654 /// This class not just make a copy of a graph, but it can create |
661 /// This class not only make a copy of a graph, but it can create |
655 /// references and cross references between the nodes, edges and arcs of |
662 /// references and cross references between the nodes, edges and arcs of |
656 /// the two graphs, it can copy maps for use with the newly created |
663 /// the two graphs, and it can copy maps for using with the newly created |
657 /// graph and copy nodes, edges and arcs. |
664 /// graph. |
658 /// |
665 /// |
659 /// To make a copy from a graph, first an instance of GraphCopy |
666 /// To make a copy from a graph, first an instance of GraphCopy |
660 /// should be created, then the data belongs to the graph should |
667 /// should be created, then the data belongs to the graph should |
661 /// assigned to copy. In the end, the \c run() member should be |
668 /// assigned to copy. In the end, the \c run() member should be |
662 /// called. |
669 /// called. |
663 /// |
670 /// |
664 /// The next code copies a graph with several data: |
671 /// The next code copies a graph with several data: |
665 ///\code |
672 ///\code |
666 /// GraphCopy<NewGraph, OrigGraph> dc(new_graph, orig_graph); |
673 /// GraphCopy<OrigGraph, NewGraph> cg(orig_graph, new_graph); |
667 /// // create a reference for the nodes |
674 /// // Create references for the nodes |
668 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
675 /// OrigGraph::NodeMap<NewGraph::Node> nr(orig_graph); |
669 /// dc.nodeRef(nr); |
676 /// cg.nodeRef(nr); |
670 /// // create a cross reference (inverse) for the edges |
677 /// // Create cross references (inverse) for the edges |
671 /// NewGraph::EdgeMap<OrigGraph::Arc> ecr(new_graph); |
678 /// NewGraph::EdgeMap<OrigGraph::Edge> ecr(new_graph); |
672 /// dc.edgeCrossRef(ecr); |
679 /// cg.edgeCrossRef(ecr); |
673 /// // copy an arc map |
680 /// // Copy an edge map |
674 /// OrigGraph::ArcMap<double> oamap(orig_graph); |
681 /// OrigGraph::EdgeMap<double> oemap(orig_graph); |
675 /// NewGraph::ArcMap<double> namap(new_graph); |
682 /// NewGraph::EdgeMap<double> nemap(new_graph); |
676 /// dc.arcMap(namap, oamap); |
683 /// cg.edgeMap(oemap, nemap); |
677 /// // copy a node |
684 /// // Copy a node |
678 /// OrigGraph::Node on; |
685 /// OrigGraph::Node on; |
679 /// NewGraph::Node nn; |
686 /// NewGraph::Node nn; |
680 /// dc.node(nn, on); |
687 /// cg.node(on, nn); |
681 /// // Executions of copy |
688 /// // Execute copying |
682 /// dc.run(); |
689 /// cg.run(); |
683 ///\endcode |
690 ///\endcode |
684 template <typename To, typename From> |
691 template <typename From, typename To> |
685 class GraphCopy { |
692 class GraphCopy { |
686 private: |
693 private: |
687 |
694 |
688 typedef typename From::Node Node; |
695 typedef typename From::Node Node; |
689 typedef typename From::NodeIt NodeIt; |
696 typedef typename From::NodeIt NodeIt; |
698 |
705 |
699 typedef typename From::template NodeMap<TNode> NodeRefMap; |
706 typedef typename From::template NodeMap<TNode> NodeRefMap; |
700 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; |
707 typedef typename From::template EdgeMap<TEdge> EdgeRefMap; |
701 |
708 |
702 struct ArcRefMap { |
709 struct ArcRefMap { |
703 ArcRefMap(const To& to, const From& from, |
710 ArcRefMap(const From& from, const To& to, |
704 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) |
711 const EdgeRefMap& edge_ref, const NodeRefMap& node_ref) |
705 : _to(to), _from(from), |
712 : _from(from), _to(to), |
706 _edge_ref(edge_ref), _node_ref(node_ref) {} |
713 _edge_ref(edge_ref), _node_ref(node_ref) {} |
707 |
714 |
708 typedef typename From::Arc Key; |
715 typedef typename From::Arc Key; |
709 typedef typename To::Arc Value; |
716 typedef typename To::Arc Value; |
710 |
717 |
714 _to.source(_to.direct(_edge_ref[key], true)) : |
721 _to.source(_to.direct(_edge_ref[key], true)) : |
715 _from.direction(key); |
722 _from.direction(key); |
716 return _to.direct(_edge_ref[key], forward); |
723 return _to.direct(_edge_ref[key], forward); |
717 } |
724 } |
718 |
725 |
726 const From& _from; |
|
719 const To& _to; |
727 const To& _to; |
720 const From& _from; |
|
721 const EdgeRefMap& _edge_ref; |
728 const EdgeRefMap& _edge_ref; |
722 const NodeRefMap& _node_ref; |
729 const NodeRefMap& _node_ref; |
723 }; |
730 }; |
724 |
731 |
725 |
|
726 public: |
732 public: |
727 |
733 |
728 |
734 /// \brief Constructor of GraphCopy. |
729 /// \brief Constructor for the GraphCopy. |
735 /// |
730 /// |
736 /// Constructor of GraphCopy for copying the content of the |
731 /// It copies the content of the \c _from graph into the |
737 /// \c from graph into the \c to graph. |
732 /// \c _to graph. |
738 GraphCopy(const From& from, To& to) |
733 GraphCopy(To& to, const From& from) |
|
734 : _from(from), _to(to) {} |
739 : _from(from), _to(to) {} |
735 |
740 |
736 /// \brief Destructor of the GraphCopy |
741 /// \brief Destructor of GraphCopy |
737 /// |
742 /// |
738 /// Destructor of the GraphCopy |
743 /// Destructor of GraphCopy. |
739 ~GraphCopy() { |
744 ~GraphCopy() { |
740 for (int i = 0; i < int(_node_maps.size()); ++i) { |
745 for (int i = 0; i < int(_node_maps.size()); ++i) { |
741 delete _node_maps[i]; |
746 delete _node_maps[i]; |
742 } |
747 } |
743 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
748 for (int i = 0; i < int(_arc_maps.size()); ++i) { |
744 delete _arc_maps[i]; |
749 delete _arc_maps[i]; |
745 } |
750 } |
746 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
751 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
747 delete _edge_maps[i]; |
752 delete _edge_maps[i]; |
748 } |
753 } |
749 |
754 } |
750 } |
755 |
751 |
756 /// \brief Copy the node references into the given map. |
752 /// \brief Copies the node references into the given map. |
757 /// |
753 /// |
758 /// This function copies the node references into the given map. |
754 /// Copies the node references into the given map. |
759 /// The parameter should be a map, whose key type is the Node type of |
760 /// the source graph, while the value type is the Node type of the |
|
761 /// destination graph. |
|
755 template <typename NodeRef> |
762 template <typename NodeRef> |
756 GraphCopy& nodeRef(NodeRef& map) { |
763 GraphCopy& nodeRef(NodeRef& map) { |
757 _node_maps.push_back(new _core_bits::RefCopy<From, Node, |
764 _node_maps.push_back(new _core_bits::RefCopy<From, Node, |
758 NodeRefMap, NodeRef>(map)); |
765 NodeRefMap, NodeRef>(map)); |
759 return *this; |
766 return *this; |
760 } |
767 } |
761 |
768 |
762 /// \brief Copies the node cross references into the given map. |
769 /// \brief Copy the node cross references into the given map. |
763 /// |
770 /// |
764 /// Copies the node cross references (reverse references) into |
771 /// This function copies the node cross references (reverse references) |
765 /// the given map. |
772 /// into the given map. The parameter should be a map, whose key type |
773 /// is the Node type of the destination graph, while the value type is |
|
774 /// the Node type of the source graph. |
|
766 template <typename NodeCrossRef> |
775 template <typename NodeCrossRef> |
767 GraphCopy& nodeCrossRef(NodeCrossRef& map) { |
776 GraphCopy& nodeCrossRef(NodeCrossRef& map) { |
768 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, |
777 _node_maps.push_back(new _core_bits::CrossRefCopy<From, Node, |
769 NodeRefMap, NodeCrossRef>(map)); |
778 NodeRefMap, NodeCrossRef>(map)); |
770 return *this; |
779 return *this; |
771 } |
780 } |
772 |
781 |
773 /// \brief Make copy of the given map. |
782 /// \brief Make a copy of the given node map. |
774 /// |
783 /// |
775 /// Makes copy of the given map for the newly created graph. |
784 /// This function makes a copy of the given node map for the newly |
776 /// The new map's key type is the to graph's node type, |
785 /// created graph. |
777 /// and the copied map's key type is the from graph's node |
786 /// The key type of the new map \c tmap should be the Node type of the |
778 /// type. |
787 /// destination graph, and the key type of the original map \c map |
779 template <typename ToMap, typename FromMap> |
788 /// should be the Node type of the source graph. |
780 GraphCopy& nodeMap(ToMap& tmap, const FromMap& map) { |
789 template <typename FromMap, typename ToMap> |
790 GraphCopy& nodeMap(const FromMap& map, ToMap& tmap) { |
|
781 _node_maps.push_back(new _core_bits::MapCopy<From, Node, |
791 _node_maps.push_back(new _core_bits::MapCopy<From, Node, |
782 NodeRefMap, ToMap, FromMap>(tmap, map)); |
792 NodeRefMap, FromMap, ToMap>(map, tmap)); |
783 return *this; |
793 return *this; |
784 } |
794 } |
785 |
795 |
786 /// \brief Make a copy of the given node. |
796 /// \brief Make a copy of the given node. |
787 /// |
797 /// |
788 /// Make a copy of the given node. |
798 /// This function makes a copy of the given node. |
789 GraphCopy& node(TNode& tnode, const Node& snode) { |
799 GraphCopy& node(const Node& node, TNode& tnode) { |
790 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, |
800 _node_maps.push_back(new _core_bits::ItemCopy<From, Node, |
791 NodeRefMap, TNode>(tnode, snode)); |
801 NodeRefMap, TNode>(node, tnode)); |
792 return *this; |
802 return *this; |
793 } |
803 } |
794 |
804 |
795 /// \brief Copies the arc references into the given map. |
805 /// \brief Copy the arc references into the given map. |
796 /// |
806 /// |
797 /// Copies the arc references into the given map. |
807 /// This function copies the arc references into the given map. |
808 /// The parameter should be a map, whose key type is the Arc type of |
|
809 /// the source graph, while the value type is the Arc type of the |
|
810 /// destination graph. |
|
798 template <typename ArcRef> |
811 template <typename ArcRef> |
799 GraphCopy& arcRef(ArcRef& map) { |
812 GraphCopy& arcRef(ArcRef& map) { |
800 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, |
813 _arc_maps.push_back(new _core_bits::RefCopy<From, Arc, |
801 ArcRefMap, ArcRef>(map)); |
814 ArcRefMap, ArcRef>(map)); |
802 return *this; |
815 return *this; |
803 } |
816 } |
804 |
817 |
805 /// \brief Copies the arc cross references into the given map. |
818 /// \brief Copy the arc cross references into the given map. |
806 /// |
819 /// |
807 /// Copies the arc cross references (reverse references) into |
820 /// This function copies the arc cross references (reverse references) |
808 /// the given map. |
821 /// into the given map. The parameter should be a map, whose key type |
822 /// is the Arc type of the destination graph, while the value type is |
|
823 /// the Arc type of the source graph. |
|
809 template <typename ArcCrossRef> |
824 template <typename ArcCrossRef> |
810 GraphCopy& arcCrossRef(ArcCrossRef& map) { |
825 GraphCopy& arcCrossRef(ArcCrossRef& map) { |
811 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, |
826 _arc_maps.push_back(new _core_bits::CrossRefCopy<From, Arc, |
812 ArcRefMap, ArcCrossRef>(map)); |
827 ArcRefMap, ArcCrossRef>(map)); |
813 return *this; |
828 return *this; |
814 } |
829 } |
815 |
830 |
816 /// \brief Make copy of the given map. |
831 /// \brief Make a copy of the given arc map. |
817 /// |
832 /// |
818 /// Makes copy of the given map for the newly created graph. |
833 /// This function makes a copy of the given arc map for the newly |
819 /// The new map's key type is the to graph's arc type, |
834 /// created graph. |
820 /// and the copied map's key type is the from graph's arc |
835 /// The key type of the new map \c tmap should be the Arc type of the |
821 /// type. |
836 /// destination graph, and the key type of the original map \c map |
822 template <typename ToMap, typename FromMap> |
837 /// should be the Arc type of the source graph. |
823 GraphCopy& arcMap(ToMap& tmap, const FromMap& map) { |
838 template <typename FromMap, typename ToMap> |
839 GraphCopy& arcMap(const FromMap& map, ToMap& tmap) { |
|
824 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, |
840 _arc_maps.push_back(new _core_bits::MapCopy<From, Arc, |
825 ArcRefMap, ToMap, FromMap>(tmap, map)); |
841 ArcRefMap, FromMap, ToMap>(map, tmap)); |
826 return *this; |
842 return *this; |
827 } |
843 } |
828 |
844 |
829 /// \brief Make a copy of the given arc. |
845 /// \brief Make a copy of the given arc. |
830 /// |
846 /// |
831 /// Make a copy of the given arc. |
847 /// This function makes a copy of the given arc. |
832 GraphCopy& arc(TArc& tarc, const Arc& sarc) { |
848 GraphCopy& arc(const Arc& arc, TArc& tarc) { |
833 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, |
849 _arc_maps.push_back(new _core_bits::ItemCopy<From, Arc, |
834 ArcRefMap, TArc>(tarc, sarc)); |
850 ArcRefMap, TArc>(arc, tarc)); |
835 return *this; |
851 return *this; |
836 } |
852 } |
837 |
853 |
838 /// \brief Copies the edge references into the given map. |
854 /// \brief Copy the edge references into the given map. |
839 /// |
855 /// |
840 /// Copies the edge references into the given map. |
856 /// This function copies the edge references into the given map. |
857 /// The parameter should be a map, whose key type is the Edge type of |
|
858 /// the source graph, while the value type is the Edge type of the |
|
859 /// destination graph. |
|
841 template <typename EdgeRef> |
860 template <typename EdgeRef> |
842 GraphCopy& edgeRef(EdgeRef& map) { |
861 GraphCopy& edgeRef(EdgeRef& map) { |
843 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, |
862 _edge_maps.push_back(new _core_bits::RefCopy<From, Edge, |
844 EdgeRefMap, EdgeRef>(map)); |
863 EdgeRefMap, EdgeRef>(map)); |
845 return *this; |
864 return *this; |
846 } |
865 } |
847 |
866 |
848 /// \brief Copies the edge cross references into the given map. |
867 /// \brief Copy the edge cross references into the given map. |
849 /// |
868 /// |
850 /// Copies the edge cross references (reverse |
869 /// This function copies the edge cross references (reverse references) |
851 /// references) into the given map. |
870 /// into the given map. The parameter should be a map, whose key type |
871 /// is the Edge type of the destination graph, while the value type is |
|
872 /// the Edge type of the source graph. |
|
852 template <typename EdgeCrossRef> |
873 template <typename EdgeCrossRef> |
853 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { |
874 GraphCopy& edgeCrossRef(EdgeCrossRef& map) { |
854 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, |
875 _edge_maps.push_back(new _core_bits::CrossRefCopy<From, |
855 Edge, EdgeRefMap, EdgeCrossRef>(map)); |
876 Edge, EdgeRefMap, EdgeCrossRef>(map)); |
856 return *this; |
877 return *this; |
857 } |
878 } |
858 |
879 |
859 /// \brief Make copy of the given map. |
880 /// \brief Make a copy of the given edge map. |
860 /// |
881 /// |
861 /// Makes copy of the given map for the newly created graph. |
882 /// This function makes a copy of the given edge map for the newly |
862 /// The new map's key type is the to graph's edge type, |
883 /// created graph. |
863 /// and the copied map's key type is the from graph's edge |
884 /// The key type of the new map \c tmap should be the Edge type of the |
864 /// type. |
885 /// destination graph, and the key type of the original map \c map |
865 template <typename ToMap, typename FromMap> |
886 /// should be the Edge type of the source graph. |
866 GraphCopy& edgeMap(ToMap& tmap, const FromMap& map) { |
887 template <typename FromMap, typename ToMap> |
888 GraphCopy& edgeMap(const FromMap& map, ToMap& tmap) { |
|
867 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, |
889 _edge_maps.push_back(new _core_bits::MapCopy<From, Edge, |
868 EdgeRefMap, ToMap, FromMap>(tmap, map)); |
890 EdgeRefMap, FromMap, ToMap>(map, tmap)); |
869 return *this; |
891 return *this; |
870 } |
892 } |
871 |
893 |
872 /// \brief Make a copy of the given edge. |
894 /// \brief Make a copy of the given edge. |
873 /// |
895 /// |
874 /// Make a copy of the given edge. |
896 /// This function makes a copy of the given edge. |
875 GraphCopy& edge(TEdge& tedge, const Edge& sedge) { |
897 GraphCopy& edge(const Edge& edge, TEdge& tedge) { |
876 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, |
898 _edge_maps.push_back(new _core_bits::ItemCopy<From, Edge, |
877 EdgeRefMap, TEdge>(tedge, sedge)); |
899 EdgeRefMap, TEdge>(edge, tedge)); |
878 return *this; |
900 return *this; |
879 } |
901 } |
880 |
902 |
881 /// \brief Executes the copies. |
903 /// \brief Execute copying. |
882 /// |
904 /// |
883 /// Executes the copies. |
905 /// This function executes the copying of the graph along with the |
906 /// copying of the assigned data. |
|
884 void run() { |
907 void run() { |
885 NodeRefMap nodeRefMap(_from); |
908 NodeRefMap nodeRefMap(_from); |
886 EdgeRefMap edgeRefMap(_from); |
909 EdgeRefMap edgeRefMap(_from); |
887 ArcRefMap arcRefMap(_to, _from, edgeRefMap, nodeRefMap); |
910 ArcRefMap arcRefMap(_from, _to, edgeRefMap, nodeRefMap); |
888 _core_bits::GraphCopySelector<To>:: |
911 _core_bits::GraphCopySelector<To>:: |
889 copy(_to, _from, nodeRefMap, edgeRefMap); |
912 copy(_from, _to, nodeRefMap, edgeRefMap); |
890 for (int i = 0; i < int(_node_maps.size()); ++i) { |
913 for (int i = 0; i < int(_node_maps.size()); ++i) { |
891 _node_maps[i]->copy(_from, nodeRefMap); |
914 _node_maps[i]->copy(_from, nodeRefMap); |
892 } |
915 } |
893 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
916 for (int i = 0; i < int(_edge_maps.size()); ++i) { |
894 _edge_maps[i]->copy(_from, edgeRefMap); |
917 _edge_maps[i]->copy(_from, edgeRefMap); |
902 |
925 |
903 const From& _from; |
926 const From& _from; |
904 To& _to; |
927 To& _to; |
905 |
928 |
906 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > |
929 std::vector<_core_bits::MapCopyBase<From, Node, NodeRefMap>* > |
907 _node_maps; |
930 _node_maps; |
908 |
931 |
909 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
932 std::vector<_core_bits::MapCopyBase<From, Arc, ArcRefMap>* > |
910 _arc_maps; |
933 _arc_maps; |
911 |
934 |
912 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > |
935 std::vector<_core_bits::MapCopyBase<From, Edge, EdgeRefMap>* > |
913 _edge_maps; |
936 _edge_maps; |
914 |
937 |
915 }; |
938 }; |
916 |
939 |
917 /// \brief Copy a graph to another graph. |
940 /// \brief Copy a graph to another graph. |
918 /// |
941 /// |
919 /// Copy a graph to another graph. The complete usage of the |
942 /// This function copies a graph to another graph. |
920 /// function is detailed in the GraphCopy class, but a short |
943 /// The complete usage of it is detailed in the GraphCopy class, |
921 /// example shows a basic work: |
944 /// but a short example shows a basic work: |
922 ///\code |
945 ///\code |
923 /// copyGraph(trg, src).nodeRef(nr).arcCrossRef(ecr).run(); |
946 /// graphCopy(src, trg).nodeRef(nr).edgeCrossRef(ecr).run(); |
924 ///\endcode |
947 ///\endcode |
925 /// |
948 /// |
926 /// After the copy the \c nr map will contain the mapping from the |
949 /// After the copy the \c nr map will contain the mapping from the |
927 /// nodes of the \c from graph to the nodes of the \c to graph and |
950 /// nodes of the \c from graph to the nodes of the \c to graph and |
928 /// \c ecr will contain the mapping from the arcs of the \c to graph |
951 /// \c ecr will contain the mapping from the edges of the \c to graph |
929 /// to the arcs of the \c from graph. |
952 /// to the edges of the \c from graph. |
930 /// |
953 /// |
931 /// \see GraphCopy |
954 /// \see GraphCopy |
932 template <typename To, typename From> |
955 template <typename From, typename To> |
933 GraphCopy<To, From> |
956 GraphCopy<From, To> |
934 copyGraph(To& to, const From& from) { |
957 graphCopy(const From& from, To& to) { |
935 return GraphCopy<To, From>(to, from); |
958 return GraphCopy<From, To>(from, to); |
936 } |
959 } |
937 |
960 |
938 namespace _core_bits { |
961 namespace _core_bits { |
939 |
962 |
940 template <typename Graph, typename Enable = void> |
963 template <typename Graph, typename Enable = void> |
955 }; |
978 }; |
956 |
979 |
957 template <typename Graph> |
980 template <typename Graph> |
958 struct FindArcSelector< |
981 struct FindArcSelector< |
959 Graph, |
982 Graph, |
960 typename enable_if<typename Graph::FindEdgeTag, void>::type> |
983 typename enable_if<typename Graph::FindArcTag, void>::type> |
961 { |
984 { |
962 typedef typename Graph::Node Node; |
985 typedef typename Graph::Node Node; |
963 typedef typename Graph::Arc Arc; |
986 typedef typename Graph::Arc Arc; |
964 static Arc find(const Graph &g, Node u, Node v, Arc prev) { |
987 static Arc find(const Graph &g, Node u, Node v, Arc prev) { |
965 return g.findArc(u, v, prev); |
988 return g.findArc(u, v, prev); |
966 } |
989 } |
967 }; |
990 }; |
968 } |
991 } |
969 |
992 |
970 /// \brief Finds an arc between two nodes of a graph. |
993 /// \brief Find an arc between two nodes of a digraph. |
971 /// |
994 /// |
972 /// Finds an arc from node \c u to node \c v in graph \c g. |
995 /// This function finds an arc from node \c u to node \c v in the |
996 /// digraph \c g. |
|
973 /// |
997 /// |
974 /// If \c prev is \ref INVALID (this is the default value), then |
998 /// If \c prev is \ref INVALID (this is the default value), then |
975 /// it finds the first arc from \c u to \c v. Otherwise it looks for |
999 /// it finds the first arc from \c u to \c v. Otherwise it looks for |
976 /// the next arc from \c u to \c v after \c prev. |
1000 /// the next arc from \c u to \c v after \c prev. |
977 /// \return The found arc or \ref INVALID if there is no such an arc. |
1001 /// \return The found arc or \ref INVALID if there is no such an arc. |
978 /// |
1002 /// |
979 /// Thus you can iterate through each arc from \c u to \c v as it follows. |
1003 /// Thus you can iterate through each arc from \c u to \c v as it follows. |
980 ///\code |
1004 ///\code |
981 /// for(Arc e=findArc(g,u,v);e!=INVALID;e=findArc(g,u,v,e)) { |
1005 /// for(Arc e = findArc(g,u,v); e != INVALID; e = findArc(g,u,v,e)) { |
982 /// ... |
1006 /// ... |
983 /// } |
1007 /// } |
984 ///\endcode |
1008 ///\endcode |
985 /// |
1009 /// |
986 ///\sa ArcLookUp |
1010 /// \note \ref ConArcIt provides iterator interface for the same |
987 ///\sa AllArcLookUp |
1011 /// functionality. |
988 ///\sa DynArcLookUp |
1012 /// |
989 ///\sa ConArcIt |
1013 ///\sa ConArcIt |
1014 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp |
|
990 template <typename Graph> |
1015 template <typename Graph> |
991 inline typename Graph::Arc |
1016 inline typename Graph::Arc |
992 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
1017 findArc(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
993 typename Graph::Arc prev = INVALID) { |
1018 typename Graph::Arc prev = INVALID) { |
994 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev); |
1019 return _core_bits::FindArcSelector<Graph>::find(g, u, v, prev); |
995 } |
1020 } |
996 |
1021 |
997 /// \brief Iterator for iterating on arcs connected the same nodes. |
1022 /// \brief Iterator for iterating on parallel arcs connecting the same nodes. |
998 /// |
1023 /// |
999 /// Iterator for iterating on arcs connected the same nodes. It is |
1024 /// Iterator for iterating on parallel arcs connecting the same nodes. It is |
1000 /// higher level interface for the findArc() function. You can |
1025 /// a higher level interface for the \ref findArc() function. You can |
1001 /// use it the following way: |
1026 /// use it the following way: |
1002 ///\code |
1027 ///\code |
1003 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
1028 /// for (ConArcIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
1004 /// ... |
1029 /// ... |
1005 /// } |
1030 /// } |
1006 ///\endcode |
1031 ///\endcode |
1007 /// |
1032 /// |
1008 ///\sa findArc() |
1033 ///\sa findArc() |
1009 ///\sa ArcLookUp |
1034 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp |
1010 ///\sa AllArcLookUp |
|
1011 ///\sa DynArcLookUp |
|
1012 template <typename _Graph> |
1035 template <typename _Graph> |
1013 class ConArcIt : public _Graph::Arc { |
1036 class ConArcIt : public _Graph::Arc { |
1014 public: |
1037 public: |
1015 |
1038 |
1016 typedef _Graph Graph; |
1039 typedef _Graph Graph; |
1019 typedef typename Graph::Arc Arc; |
1042 typedef typename Graph::Arc Arc; |
1020 typedef typename Graph::Node Node; |
1043 typedef typename Graph::Node Node; |
1021 |
1044 |
1022 /// \brief Constructor. |
1045 /// \brief Constructor. |
1023 /// |
1046 /// |
1024 /// Construct a new ConArcIt iterating on the arcs which |
1047 /// Construct a new ConArcIt iterating on the arcs that |
1025 /// connects the \c u and \c v node. |
1048 /// connects nodes \c u and \c v. |
1026 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { |
1049 ConArcIt(const Graph& g, Node u, Node v) : _graph(g) { |
1027 Parent::operator=(findArc(_graph, u, v)); |
1050 Parent::operator=(findArc(_graph, u, v)); |
1028 } |
1051 } |
1029 |
1052 |
1030 /// \brief Constructor. |
1053 /// \brief Constructor. |
1031 /// |
1054 /// |
1032 /// Construct a new ConArcIt which continues the iterating from |
1055 /// Construct a new ConArcIt that continues the iterating from arc \c a. |
1033 /// the \c e arc. |
|
1034 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} |
1056 ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {} |
1035 |
1057 |
1036 /// \brief Increment operator. |
1058 /// \brief Increment operator. |
1037 /// |
1059 /// |
1038 /// It increments the iterator and gives back the next arc. |
1060 /// It increments the iterator and gives back the next arc. |
1089 return g.findEdge(u, v, prev); |
1111 return g.findEdge(u, v, prev); |
1090 } |
1112 } |
1091 }; |
1113 }; |
1092 } |
1114 } |
1093 |
1115 |
1094 /// \brief Finds an edge between two nodes of a graph. |
1116 /// \brief Find an edge between two nodes of a graph. |
1095 /// |
1117 /// |
1096 /// Finds an edge from node \c u to node \c v in graph \c g. |
1118 /// This function finds an edge from node \c u to node \c v in graph \c g. |
1097 /// If the node \c u and node \c v is equal then each loop edge |
1119 /// If node \c u and node \c v is equal then each loop edge |
1098 /// will be enumerated once. |
1120 /// will be enumerated once. |
1099 /// |
1121 /// |
1100 /// If \c prev is \ref INVALID (this is the default value), then |
1122 /// If \c prev is \ref INVALID (this is the default value), then |
1101 /// it finds the first arc from \c u to \c v. Otherwise it looks for |
1123 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
1102 /// the next arc from \c u to \c v after \c prev. |
1124 /// the next edge from \c u to \c v after \c prev. |
1103 /// \return The found arc or \ref INVALID if there is no such an arc. |
1125 /// \return The found edge or \ref INVALID if there is no such an edge. |
1104 /// |
1126 /// |
1105 /// Thus you can iterate through each arc from \c u to \c v as it follows. |
1127 /// Thus you can iterate through each edge between \c u and \c v |
1128 /// as it follows. |
|
1106 ///\code |
1129 ///\code |
1107 /// for(Edge e = findEdge(g,u,v); e != INVALID; |
1130 /// for(Edge e = findEdge(g,u,v); e != INVALID; e = findEdge(g,u,v,e)) { |
1108 /// e = findEdge(g,u,v,e)) { |
|
1109 /// ... |
1131 /// ... |
1110 /// } |
1132 /// } |
1111 ///\endcode |
1133 ///\endcode |
1112 /// |
1134 /// |
1135 /// \note \ref ConEdgeIt provides iterator interface for the same |
|
1136 /// functionality. |
|
1137 /// |
|
1113 ///\sa ConEdgeIt |
1138 ///\sa ConEdgeIt |
1114 |
|
1115 template <typename Graph> |
1139 template <typename Graph> |
1116 inline typename Graph::Edge |
1140 inline typename Graph::Edge |
1117 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
1141 findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v, |
1118 typename Graph::Edge p = INVALID) { |
1142 typename Graph::Edge p = INVALID) { |
1119 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p); |
1143 return _core_bits::FindEdgeSelector<Graph>::find(g, u, v, p); |
1120 } |
1144 } |
1121 |
1145 |
1122 /// \brief Iterator for iterating on edges connected the same nodes. |
1146 /// \brief Iterator for iterating on parallel edges connecting the same nodes. |
1123 /// |
1147 /// |
1124 /// Iterator for iterating on edges connected the same nodes. It is |
1148 /// Iterator for iterating on parallel edges connecting the same nodes. |
1125 /// higher level interface for the findEdge() function. You can |
1149 /// It is a higher level interface for the findEdge() function. You can |
1126 /// use it the following way: |
1150 /// use it the following way: |
1127 ///\code |
1151 ///\code |
1128 /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) { |
1152 /// for (ConEdgeIt<Graph> it(g, u, v); it != INVALID; ++it) { |
1129 /// ... |
1153 /// ... |
1130 /// } |
1154 /// } |
1131 ///\endcode |
1155 ///\endcode |
1132 /// |
1156 /// |
1133 ///\sa findEdge() |
1157 ///\sa findEdge() |
1141 typedef typename Graph::Edge Edge; |
1165 typedef typename Graph::Edge Edge; |
1142 typedef typename Graph::Node Node; |
1166 typedef typename Graph::Node Node; |
1143 |
1167 |
1144 /// \brief Constructor. |
1168 /// \brief Constructor. |
1145 /// |
1169 /// |
1146 /// Construct a new ConEdgeIt iterating on the edges which |
1170 /// Construct a new ConEdgeIt iterating on the edges that |
1147 /// connects the \c u and \c v node. |
1171 /// connects nodes \c u and \c v. |
1148 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { |
1172 ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) { |
1149 Parent::operator=(findEdge(_graph, u, v)); |
1173 Parent::operator=(findEdge(_graph, u, v)); |
1150 } |
1174 } |
1151 |
1175 |
1152 /// \brief Constructor. |
1176 /// \brief Constructor. |
1153 /// |
1177 /// |
1154 /// Construct a new ConEdgeIt which continues the iterating from |
1178 /// Construct a new ConEdgeIt that continues iterating from edge \c e. |
1155 /// the \c e edge. |
|
1156 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} |
1179 ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {} |
1157 |
1180 |
1158 /// \brief Increment operator. |
1181 /// \brief Increment operator. |
1159 /// |
1182 /// |
1160 /// It increments the iterator and gives back the next edge. |
1183 /// It increments the iterator and gives back the next edge. |
1166 private: |
1189 private: |
1167 const Graph& _graph; |
1190 const Graph& _graph; |
1168 }; |
1191 }; |
1169 |
1192 |
1170 |
1193 |
1171 ///Dynamic arc look up between given endpoints. |
1194 ///Dynamic arc look-up between given endpoints. |
1172 |
1195 |
1173 ///Using this class, you can find an arc in a digraph from a given |
1196 ///Using this class, you can find an arc in a digraph from a given |
1174 ///source to a given target in amortized time <em>O(log</em>d<em>)</em>, |
1197 ///source to a given target in amortized time <em>O</em>(log<em>d</em>), |
1175 ///where <em>d</em> is the out-degree of the source node. |
1198 ///where <em>d</em> is the out-degree of the source node. |
1176 /// |
1199 /// |
1177 ///It is possible to find \e all parallel arcs between two nodes with |
1200 ///It is possible to find \e all parallel arcs between two nodes with |
1178 ///the \c operator() member. |
1201 ///the \c operator() member. |
1179 /// |
1202 /// |
1180 ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your |
1203 ///This is a dynamic data structure. Consider to use \ref ArcLookUp or |
1181 ///digraph is not changed so frequently. |
1204 ///\ref AllArcLookUp if your digraph is not changed so frequently. |
1182 /// |
1205 /// |
1183 ///This class uses a self-adjusting binary search tree, Sleator's |
1206 ///This class uses a self-adjusting binary search tree, the Splay tree |
1184 ///and Tarjan's Splay tree for guarantee the logarithmic amortized |
1207 ///of Sleator and Tarjan to guarantee the logarithmic amortized |
1185 ///time bound for arc lookups. This class also guarantees the |
1208 ///time bound for arc look-ups. This class also guarantees the |
1186 ///optimal time bound in a constant factor for any distribution of |
1209 ///optimal time bound in a constant factor for any distribution of |
1187 ///queries. |
1210 ///queries. |
1188 /// |
1211 /// |
1189 ///\tparam G The type of the underlying digraph. |
1212 ///\tparam G The type of the underlying digraph. |
1190 /// |
1213 /// |
1505 public: |
1528 public: |
1506 |
1529 |
1507 ///Find an arc between two nodes. |
1530 ///Find an arc between two nodes. |
1508 |
1531 |
1509 ///Find an arc between two nodes. |
1532 ///Find an arc between two nodes. |
1510 ///\param s The source node |
1533 ///\param s The source node. |
1511 ///\param t The target node |
1534 ///\param t The target node. |
1512 ///\param p The previous arc between \c s and \c t. It it is INVALID or |
1535 ///\param p The previous arc between \c s and \c t. It it is INVALID or |
1513 ///not given, the operator finds the first appropriate arc. |
1536 ///not given, the operator finds the first appropriate arc. |
1514 ///\return An arc from \c s to \c t after \c p or |
1537 ///\return An arc from \c s to \c t after \c p or |
1515 ///\ref INVALID if there is no more. |
1538 ///\ref INVALID if there is no more. |
1516 /// |
1539 /// |
1517 ///For example, you can count the number of arcs from \c u to \c v in the |
1540 ///For example, you can count the number of arcs from \c u to \c v in the |
1518 ///following way. |
1541 ///following way. |
1519 ///\code |
1542 ///\code |
1520 ///DynArcLookUp<ListDigraph> ae(g); |
1543 ///DynArcLookUp<ListDigraph> ae(g); |
1521 ///... |
1544 ///... |
1522 ///int n=0; |
1545 ///int n = 0; |
1523 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; |
1546 ///for(Arc a = ae(u,v); a != INVALID; a = ae(u,v,a)) n++; |
1524 ///\endcode |
1547 ///\endcode |
1525 /// |
1548 /// |
1526 ///Finding the arcs take at most <em>O(</em>log<em>d)</em> |
1549 ///Finding the arcs take at most <em>O</em>(log<em>d</em>) |
1527 ///amortized time, specifically, the time complexity of the lookups |
1550 ///amortized time, specifically, the time complexity of the lookups |
1528 ///is equal to the optimal search tree implementation for the |
1551 ///is equal to the optimal search tree implementation for the |
1529 ///current query distribution in a constant factor. |
1552 ///current query distribution in a constant factor. |
1530 /// |
1553 /// |
1531 ///\note This is a dynamic data structure, therefore the data |
1554 ///\note This is a dynamic data structure, therefore the data |
1532 ///structure is updated after each graph alteration. However, |
1555 ///structure is updated after each graph alteration. Thus although |
1533 ///theoretically this data structure is faster than \c ArcLookUp |
1556 ///this data structure is theoretically faster than \ref ArcLookUp |
1534 ///or AllEdgeLookup, but it often provides worse performance than |
1557 ///and \ref AllArcLookup, it often provides worse performance than |
1535 ///them. |
1558 ///them. |
1536 /// |
|
1537 Arc operator()(Node s, Node t, Arc p = INVALID) const { |
1559 Arc operator()(Node s, Node t, Arc p = INVALID) const { |
1538 if (p == INVALID) { |
1560 if (p == INVALID) { |
1539 Arc a = _head[s]; |
1561 Arc a = _head[s]; |
1540 if (a == INVALID) return INVALID; |
1562 if (a == INVALID) return INVALID; |
1541 Arc r = INVALID; |
1563 Arc r = INVALID; |
1583 } |
1605 } |
1584 } |
1606 } |
1585 |
1607 |
1586 }; |
1608 }; |
1587 |
1609 |
1588 ///Fast arc look up between given endpoints. |
1610 ///Fast arc look-up between given endpoints. |
1589 |
1611 |
1590 ///Using this class, you can find an arc in a digraph from a given |
1612 ///Using this class, you can find an arc in a digraph from a given |
1591 ///source to a given target in time <em>O(log d)</em>, |
1613 ///source to a given target in time <em>O</em>(log<em>d</em>), |
1592 ///where <em>d</em> is the out-degree of the source node. |
1614 ///where <em>d</em> is the out-degree of the source node. |
1593 /// |
1615 /// |
1594 ///It is not possible to find \e all parallel arcs between two nodes. |
1616 ///It is not possible to find \e all parallel arcs between two nodes. |
1595 ///Use \ref AllArcLookUp for this purpose. |
1617 ///Use \ref AllArcLookUp for this purpose. |
1596 /// |
1618 /// |
1597 ///\warning This class is static, so you should refresh() (or at least |
1619 ///\warning This class is static, so you should call refresh() (or at |
1598 ///refresh(Node)) this data structure |
1620 ///least refresh(Node)) to refresh this data structure whenever the |
1599 ///whenever the digraph changes. This is a time consuming (superlinearly |
1621 ///digraph changes. This is a time consuming (superlinearly proportional |
1600 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
1622 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). |
1601 /// |
1623 /// |
1602 ///\tparam G The type of the underlying digraph. |
1624 ///\tparam G The type of the underlying digraph. |
1603 /// |
1625 /// |
1604 ///\sa DynArcLookUp |
1626 ///\sa DynArcLookUp |
1605 ///\sa AllArcLookUp |
1627 ///\sa AllArcLookUp |
1644 _left[me] = a<m?refreshRec(v,a,m-1):INVALID; |
1666 _left[me] = a<m?refreshRec(v,a,m-1):INVALID; |
1645 _right[me] = m<b?refreshRec(v,m+1,b):INVALID; |
1667 _right[me] = m<b?refreshRec(v,m+1,b):INVALID; |
1646 return me; |
1668 return me; |
1647 } |
1669 } |
1648 public: |
1670 public: |
1649 ///Refresh the data structure at a node. |
1671 ///Refresh the search data structure at a node. |
1650 |
1672 |
1651 ///Build up the search database of node \c n. |
1673 ///Build up the search database of node \c n. |
1652 /// |
1674 /// |
1653 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is |
1675 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> |
1654 ///the number of the outgoing arcs of \c n. |
1676 ///is the number of the outgoing arcs of \c n. |
1655 void refresh(Node n) |
1677 void refresh(Node n) |
1656 { |
1678 { |
1657 std::vector<Arc> v; |
1679 std::vector<Arc> v; |
1658 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); |
1680 for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e); |
1659 if(v.size()) { |
1681 if(v.size()) { |
1665 ///Refresh the full data structure. |
1687 ///Refresh the full data structure. |
1666 |
1688 |
1667 ///Build up the full search database. In fact, it simply calls |
1689 ///Build up the full search database. In fact, it simply calls |
1668 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
1690 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
1669 /// |
1691 /// |
1670 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is |
1692 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is |
1671 ///the number of the arcs of \c n and <em>D</em> is the maximum |
1693 ///the number of the arcs in the digraph and <em>D</em> is the maximum |
1672 ///out-degree of the digraph. |
1694 ///out-degree of the digraph. |
1673 |
|
1674 void refresh() |
1695 void refresh() |
1675 { |
1696 { |
1676 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
1697 for(NodeIt n(_g);n!=INVALID;++n) refresh(n); |
1677 } |
1698 } |
1678 |
1699 |
1679 ///Find an arc between two nodes. |
1700 ///Find an arc between two nodes. |
1680 |
1701 |
1681 ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where |
1702 ///Find an arc between two nodes in time <em>O</em>(log<em>d</em>), where |
1682 /// <em>d</em> is the number of outgoing arcs of \c s. |
1703 ///<em>d</em> is the number of outgoing arcs of \c s. |
1683 ///\param s The source node |
1704 ///\param s The source node. |
1684 ///\param t The target node |
1705 ///\param t The target node. |
1685 ///\return An arc from \c s to \c t if there exists, |
1706 ///\return An arc from \c s to \c t if there exists, |
1686 ///\ref INVALID otherwise. |
1707 ///\ref INVALID otherwise. |
1687 /// |
1708 /// |
1688 ///\warning If you change the digraph, refresh() must be called before using |
1709 ///\warning If you change the digraph, refresh() must be called before using |
1689 ///this operator. If you change the outgoing arcs of |
1710 ///this operator. If you change the outgoing arcs of |
1690 ///a single node \c n, then |
1711 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. |
1691 ///\ref refresh(Node) "refresh(n)" is enough. |
|
1692 /// |
|
1693 Arc operator()(Node s, Node t) const |
1712 Arc operator()(Node s, Node t) const |
1694 { |
1713 { |
1695 Arc e; |
1714 Arc e; |
1696 for(e=_head[s]; |
1715 for(e=_head[s]; |
1697 e!=INVALID&&_g.target(e)!=t; |
1716 e!=INVALID&&_g.target(e)!=t; |
1699 return e; |
1718 return e; |
1700 } |
1719 } |
1701 |
1720 |
1702 }; |
1721 }; |
1703 |
1722 |
1704 ///Fast look up of all arcs between given endpoints. |
1723 ///Fast look-up of all arcs between given endpoints. |
1705 |
1724 |
1706 ///This class is the same as \ref ArcLookUp, with the addition |
1725 ///This class is the same as \ref ArcLookUp, with the addition |
1707 ///that it makes it possible to find all arcs between given endpoints. |
1726 ///that it makes it possible to find all parallel arcs between given |
1708 /// |
1727 ///endpoints. |
1709 ///\warning This class is static, so you should refresh() (or at least |
1728 /// |
1710 ///refresh(Node)) this data structure |
1729 ///\warning This class is static, so you should call refresh() (or at |
1711 ///whenever the digraph changes. This is a time consuming (superlinearly |
1730 ///least refresh(Node)) to refresh this data structure whenever the |
1712 ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs). |
1731 ///digraph changes. This is a time consuming (superlinearly proportional |
1732 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). |
|
1713 /// |
1733 /// |
1714 ///\tparam G The type of the underlying digraph. |
1734 ///\tparam G The type of the underlying digraph. |
1715 /// |
1735 /// |
1716 ///\sa DynArcLookUp |
1736 ///\sa DynArcLookUp |
1717 ///\sa ArcLookUp |
1737 ///\sa ArcLookUp |
1731 Arc refreshNext(Arc head,Arc next=INVALID) |
1751 Arc refreshNext(Arc head,Arc next=INVALID) |
1732 { |
1752 { |
1733 if(head==INVALID) return next; |
1753 if(head==INVALID) return next; |
1734 else { |
1754 else { |
1735 next=refreshNext(_right[head],next); |
1755 next=refreshNext(_right[head],next); |
1736 // _next[head]=next; |
|
1737 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) |
1756 _next[head]=( next!=INVALID && _g.target(next)==_g.target(head)) |
1738 ? next : INVALID; |
1757 ? next : INVALID; |
1739 return refreshNext(_left[head],head); |
1758 return refreshNext(_left[head],head); |
1740 } |
1759 } |
1741 } |
1760 } |
1756 |
1775 |
1757 ///Refresh the data structure at a node. |
1776 ///Refresh the data structure at a node. |
1758 |
1777 |
1759 ///Build up the search database of node \c n. |
1778 ///Build up the search database of node \c n. |
1760 /// |
1779 /// |
1761 ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is |
1780 ///It runs in time <em>O</em>(<em>d</em> log<em>d</em>), where <em>d</em> is |
1762 ///the number of the outgoing arcs of \c n. |
1781 ///the number of the outgoing arcs of \c n. |
1763 |
|
1764 void refresh(Node n) |
1782 void refresh(Node n) |
1765 { |
1783 { |
1766 ArcLookUp<G>::refresh(n); |
1784 ArcLookUp<G>::refresh(n); |
1767 refreshNext(_head[n]); |
1785 refreshNext(_head[n]); |
1768 } |
1786 } |
1770 ///Refresh the full data structure. |
1788 ///Refresh the full data structure. |
1771 |
1789 |
1772 ///Build up the full search database. In fact, it simply calls |
1790 ///Build up the full search database. In fact, it simply calls |
1773 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
1791 ///\ref refresh(Node) "refresh(n)" for each node \c n. |
1774 /// |
1792 /// |
1775 ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is |
1793 ///It runs in time <em>O</em>(<em>m</em> log<em>D</em>), where <em>m</em> is |
1776 ///the number of the arcs of \c n and <em>D</em> is the maximum |
1794 ///the number of the arcs in the digraph and <em>D</em> is the maximum |
1777 ///out-degree of the digraph. |
1795 ///out-degree of the digraph. |
1778 |
|
1779 void refresh() |
1796 void refresh() |
1780 { |
1797 { |
1781 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); |
1798 for(NodeIt n(_g);n!=INVALID;++n) refresh(_head[n]); |
1782 } |
1799 } |
1783 |
1800 |
1784 ///Find an arc between two nodes. |
1801 ///Find an arc between two nodes. |
1785 |
1802 |
1786 ///Find an arc between two nodes. |
1803 ///Find an arc between two nodes. |
1787 ///\param s The source node |
1804 ///\param s The source node. |
1788 ///\param t The target node |
1805 ///\param t The target node. |
1789 ///\param prev The previous arc between \c s and \c t. It it is INVALID or |
1806 ///\param prev The previous arc between \c s and \c t. It it is INVALID or |
1790 ///not given, the operator finds the first appropriate arc. |
1807 ///not given, the operator finds the first appropriate arc. |
1791 ///\return An arc from \c s to \c t after \c prev or |
1808 ///\return An arc from \c s to \c t after \c prev or |
1792 ///\ref INVALID if there is no more. |
1809 ///\ref INVALID if there is no more. |
1793 /// |
1810 /// |
1794 ///For example, you can count the number of arcs from \c u to \c v in the |
1811 ///For example, you can count the number of arcs from \c u to \c v in the |
1795 ///following way. |
1812 ///following way. |
1796 ///\code |
1813 ///\code |
1797 ///AllArcLookUp<ListDigraph> ae(g); |
1814 ///AllArcLookUp<ListDigraph> ae(g); |
1798 ///... |
1815 ///... |
1799 ///int n=0; |
1816 ///int n = 0; |
1800 ///for(Arc e=ae(u,v);e!=INVALID;e=ae(u,v,e)) n++; |
1817 ///for(Arc a = ae(u,v); a != INVALID; a=ae(u,v,a)) n++; |
1801 ///\endcode |
1818 ///\endcode |
1802 /// |
1819 /// |
1803 ///Finding the first arc take <em>O(</em>log<em>d)</em> time, where |
1820 ///Finding the first arc take <em>O</em>(log<em>d</em>) time, where |
1804 /// <em>d</em> is the number of outgoing arcs of \c s. Then, the |
1821 ///<em>d</em> is the number of outgoing arcs of \c s. Then, the |
1805 ///consecutive arcs are found in constant time. |
1822 ///consecutive arcs are found in constant time. |
1806 /// |
1823 /// |
1807 ///\warning If you change the digraph, refresh() must be called before using |
1824 ///\warning If you change the digraph, refresh() must be called before using |
1808 ///this operator. If you change the outgoing arcs of |
1825 ///this operator. If you change the outgoing arcs of |
1809 ///a single node \c n, then |
1826 ///a single node \c n, then \ref refresh(Node) "refresh(n)" is enough. |
1810 ///\ref refresh(Node) "refresh(n)" is enough. |
|
1811 /// |
1827 /// |
1812 #ifdef DOXYGEN |
1828 #ifdef DOXYGEN |
1813 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} |
1829 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} |
1814 #else |
1830 #else |
1815 using ArcLookUp<G>::operator() ; |
1831 using ArcLookUp<G>::operator() ; |