1 /* -*- C++ -*- |
|
2 * src/lemon/graph_utils.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_GRAPH_UTILS_H |
|
18 #define LEMON_GRAPH_UTILS_H |
|
19 |
|
20 #include <iterator> |
|
21 #include <vector> |
|
22 #include <map> |
|
23 |
|
24 #include <lemon/invalid.h> |
|
25 #include <lemon/utility.h> |
|
26 #include <lemon/maps.h> |
|
27 |
|
28 ///\ingroup gutils |
|
29 ///\file |
|
30 ///\brief Graph utilities. |
|
31 /// |
|
32 ///\todo Please |
|
33 ///revise the documentation. |
|
34 /// |
|
35 |
|
36 |
|
37 namespace lemon { |
|
38 |
|
39 /// \addtogroup gutils |
|
40 /// @{ |
|
41 |
|
42 /// \brief Function to count the items in the graph. |
|
43 /// |
|
44 /// This function counts the items in the graph. |
|
45 /// The complexity of the function is O(n) because |
|
46 /// it iterates on all of the items. |
|
47 |
|
48 template <typename Graph, typename ItemIt> |
|
49 inline int countItems(const Graph& g) { |
|
50 int num = 0; |
|
51 for (ItemIt it(g); it != INVALID; ++it) { |
|
52 ++num; |
|
53 } |
|
54 return num; |
|
55 } |
|
56 |
|
57 // Node counting: |
|
58 |
|
59 template <typename Graph> |
|
60 inline |
|
61 typename enable_if<typename Graph::NodeNumTag, int>::type |
|
62 _countNodes(const Graph &g) { |
|
63 return g.nodeNum(); |
|
64 } |
|
65 |
|
66 template <typename Graph> |
|
67 inline int _countNodes(Wrap<Graph> w) { |
|
68 return countItems<Graph, typename Graph::NodeIt>(w.value); |
|
69 } |
|
70 |
|
71 /// \brief Function to count the nodes in the graph. |
|
72 /// |
|
73 /// This function counts the nodes in the graph. |
|
74 /// The complexity of the function is O(n) but for some |
|
75 /// graph structure it is specialized to run in O(1). |
|
76 /// |
|
77 /// \todo refer how to specialize it |
|
78 |
|
79 template <typename Graph> |
|
80 inline int countNodes(const Graph& g) { |
|
81 return _countNodes<Graph>(g); |
|
82 } |
|
83 |
|
84 // Edge counting: |
|
85 |
|
86 template <typename Graph> |
|
87 inline |
|
88 typename enable_if<typename Graph::EdgeNumTag, int>::type |
|
89 _countEdges(const Graph &g) { |
|
90 return g.edgeNum(); |
|
91 } |
|
92 |
|
93 template <typename Graph> |
|
94 inline int _countEdges(Wrap<Graph> w) { |
|
95 return countItems<Graph, typename Graph::EdgeIt>(w.value); |
|
96 } |
|
97 |
|
98 /// \brief Function to count the edges in the graph. |
|
99 /// |
|
100 /// This function counts the edges in the graph. |
|
101 /// The complexity of the function is O(e) but for some |
|
102 /// graph structure it is specialized to run in O(1). |
|
103 |
|
104 template <typename Graph> |
|
105 inline int countEdges(const Graph& g) { |
|
106 return _countEdges<Graph>(g); |
|
107 } |
|
108 |
|
109 // Undirected edge counting: |
|
110 |
|
111 template <typename Graph> |
|
112 inline |
|
113 typename enable_if<typename Graph::EdgeNumTag, int>::type |
|
114 _countUndirEdges(const Graph &g) { |
|
115 return g.undirEdgeNum(); |
|
116 } |
|
117 |
|
118 template <typename Graph> |
|
119 inline int _countUndirEdges(Wrap<Graph> w) { |
|
120 return countItems<Graph, typename Graph::UndirEdgeIt>(w.value); |
|
121 } |
|
122 |
|
123 /// \brief Function to count the edges in the graph. |
|
124 /// |
|
125 /// This function counts the edges in the graph. |
|
126 /// The complexity of the function is O(e) but for some |
|
127 /// graph structure it is specialized to run in O(1). |
|
128 |
|
129 template <typename Graph> |
|
130 inline int countUndirEdges(const Graph& g) { |
|
131 return _countUndirEdges<Graph>(g); |
|
132 } |
|
133 |
|
134 |
|
135 |
|
136 template <typename Graph, typename DegIt> |
|
137 inline int countNodeDegree(const Graph& _g, const typename Graph::Node& _n) { |
|
138 int num = 0; |
|
139 for (DegIt it(_g, _n); it != INVALID; ++it) { |
|
140 ++num; |
|
141 } |
|
142 return num; |
|
143 } |
|
144 |
|
145 /// Finds an edge between two nodes of a graph. |
|
146 |
|
147 /// Finds an edge from node \c u to node \c v in graph \c g. |
|
148 /// |
|
149 /// If \c prev is \ref INVALID (this is the default value), then |
|
150 /// it finds the first edge from \c u to \c v. Otherwise it looks for |
|
151 /// the next edge from \c u to \c v after \c prev. |
|
152 /// \return The found edge or \ref INVALID if there is no such an edge. |
|
153 /// |
|
154 /// Thus you can iterate through each edge from \c u to \c v as it follows. |
|
155 /// \code |
|
156 /// for(Edge e=findEdge(g,u,v);e!=INVALID;e=findEdge(g,u,v,e)) { |
|
157 /// ... |
|
158 /// } |
|
159 /// \endcode |
|
160 /// \todo We may want to use the \ref concept::GraphBase "GraphBase" |
|
161 /// interface here... |
|
162 /// \bug Untested ... |
|
163 template <typename Graph> |
|
164 typename Graph::Edge findEdge(const Graph &g, |
|
165 typename Graph::Node u, typename Graph::Node v, |
|
166 typename Graph::Edge prev = INVALID) |
|
167 { |
|
168 typename Graph::OutEdgeIt e(g,prev); |
|
169 // if(prev==INVALID) g.first(e,u); |
|
170 if(prev==INVALID) e=typename Graph::OutEdgeIt(g,u); |
|
171 else ++e; |
|
172 while(e!=INVALID && g.target(e)!=v) ++e; |
|
173 return e; |
|
174 } |
|
175 |
|
176 ///\e |
|
177 |
|
178 ///\todo Please document. |
|
179 /// |
|
180 template <typename Graph> |
|
181 inline int countOutEdges(const Graph& _g, const typename Graph::Node& _n) { |
|
182 return countNodeDegree<Graph, typename Graph::OutEdgeIt>(_g, _n); |
|
183 } |
|
184 |
|
185 ///\e |
|
186 |
|
187 ///\todo Please document. |
|
188 /// |
|
189 template <typename Graph> |
|
190 inline int countInEdges(const Graph& _g, const typename Graph::Node& _n) { |
|
191 return countNodeDegree<Graph, typename Graph::InEdgeIt>(_g, _n); |
|
192 } |
|
193 |
|
194 // graph copy |
|
195 |
|
196 template < |
|
197 typename DestinationGraph, |
|
198 typename SourceGraph, |
|
199 typename NodeBijection> |
|
200 void copyNodes(DestinationGraph& _d, const SourceGraph& _s, |
|
201 NodeBijection& _nb) { |
|
202 for (typename SourceGraph::NodeIt it(_s); it != INVALID; ++it) { |
|
203 _nb[it] = _d.addNode(); |
|
204 } |
|
205 } |
|
206 |
|
207 template < |
|
208 typename DestinationGraph, |
|
209 typename SourceGraph, |
|
210 typename NodeBijection, |
|
211 typename EdgeBijection> |
|
212 void copyEdges(DestinationGraph& _d, const SourceGraph& _s, |
|
213 const NodeBijection& _nb, EdgeBijection& _eb) { |
|
214 for (typename SourceGraph::EdgeIt it(_s); it != INVALID; ++it) { |
|
215 _eb[it] = _d.addEdge(_nb[_s.source(it)], _nb[_s.target(it)]); |
|
216 } |
|
217 } |
|
218 |
|
219 template < |
|
220 typename DestinationGraph, |
|
221 typename SourceGraph, |
|
222 typename NodeBijection, |
|
223 typename EdgeBijection> |
|
224 void copyGraph(DestinationGraph& _d, const SourceGraph& _s, |
|
225 NodeBijection& _nb, EdgeBijection& _eb) { |
|
226 nodeCopy(_d, _s, _nb); |
|
227 edgeCopy(_d, _s, _nb, _eb); |
|
228 } |
|
229 |
|
230 template < |
|
231 typename _DestinationGraph, |
|
232 typename _SourceGraph, |
|
233 typename _NodeBijection |
|
234 =typename _SourceGraph::template NodeMap<typename _DestinationGraph::Node>, |
|
235 typename _EdgeBijection |
|
236 = typename _SourceGraph::template EdgeMap<typename _DestinationGraph::Edge> |
|
237 > |
|
238 class GraphCopy { |
|
239 public: |
|
240 |
|
241 typedef _DestinationGraph DestinationGraph; |
|
242 typedef _SourceGraph SourceGraph; |
|
243 |
|
244 typedef _NodeBijection NodeBijection; |
|
245 typedef _EdgeBijection EdgeBijection; |
|
246 |
|
247 protected: |
|
248 |
|
249 NodeBijection node_bijection; |
|
250 EdgeBijection edge_bijection; |
|
251 |
|
252 public: |
|
253 |
|
254 GraphCopy(DestinationGraph& _d, const SourceGraph& _s) { |
|
255 copyGraph(_d, _s, node_bijection, edge_bijection); |
|
256 } |
|
257 |
|
258 const NodeBijection& getNodeBijection() const { |
|
259 return node_bijection; |
|
260 } |
|
261 |
|
262 const EdgeBijection& getEdgeBijection() const { |
|
263 return edge_bijection; |
|
264 } |
|
265 |
|
266 }; |
|
267 |
|
268 |
|
269 template <typename _Graph, typename _Item> |
|
270 class ItemSetTraits {}; |
|
271 |
|
272 template <typename _Graph> |
|
273 class ItemSetTraits<_Graph, typename _Graph::Node> { |
|
274 public: |
|
275 |
|
276 typedef _Graph Graph; |
|
277 |
|
278 typedef typename Graph::Node Item; |
|
279 typedef typename Graph::NodeIt ItemIt; |
|
280 |
|
281 template <typename _Value> |
|
282 class Map : public Graph::template NodeMap<_Value> { |
|
283 public: |
|
284 typedef typename Graph::template NodeMap<_Value> Parent; |
|
285 typedef typename Parent::Value Value; |
|
286 |
|
287 Map(const Graph& _graph) : Parent(_graph) {} |
|
288 Map(const Graph& _graph, const Value& _value) |
|
289 : Parent(_graph, _value) {} |
|
290 }; |
|
291 |
|
292 }; |
|
293 |
|
294 template <typename _Graph> |
|
295 class ItemSetTraits<_Graph, typename _Graph::Edge> { |
|
296 public: |
|
297 |
|
298 typedef _Graph Graph; |
|
299 |
|
300 typedef typename Graph::Edge Item; |
|
301 typedef typename Graph::EdgeIt ItemIt; |
|
302 |
|
303 template <typename _Value> |
|
304 class Map : public Graph::template EdgeMap<_Value> { |
|
305 public: |
|
306 typedef typename Graph::template EdgeMap<_Value> Parent; |
|
307 typedef typename Parent::Value Value; |
|
308 |
|
309 Map(const Graph& _graph) : Parent(_graph) {} |
|
310 Map(const Graph& _graph, const Value& _value) |
|
311 : Parent(_graph, _value) {} |
|
312 }; |
|
313 |
|
314 }; |
|
315 |
|
316 template <typename _Graph> |
|
317 class ItemSetTraits<_Graph, typename _Graph::UndirEdge> { |
|
318 public: |
|
319 |
|
320 typedef _Graph Graph; |
|
321 |
|
322 typedef typename Graph::UndirEdge Item; |
|
323 typedef typename Graph::UndirEdgeIt ItemIt; |
|
324 |
|
325 template <typename _Value> |
|
326 class Map : public Graph::template UndirEdgeMap<_Value> { |
|
327 public: |
|
328 typedef typename Graph::template UndirEdgeMap<_Value> Parent; |
|
329 typedef typename Parent::Value Value; |
|
330 |
|
331 Map(const Graph& _graph) : Parent(_graph) {} |
|
332 Map(const Graph& _graph, const Value& _value) |
|
333 : Parent(_graph, _value) {} |
|
334 }; |
|
335 |
|
336 }; |
|
337 |
|
338 /// @} |
|
339 |
|
340 /// \addtogroup graph_maps |
|
341 /// @{ |
|
342 |
|
343 template <typename Map, typename Enable = void> |
|
344 struct ReferenceMapTraits { |
|
345 typedef typename Map::Value Value; |
|
346 typedef typename Map::Value& Reference; |
|
347 typedef const typename Map::Value& ConstReference; |
|
348 typedef typename Map::Value* Pointer; |
|
349 typedef const typename Map::Value* ConstPointer; |
|
350 }; |
|
351 |
|
352 template <typename Map> |
|
353 struct ReferenceMapTraits< |
|
354 Map, |
|
355 typename enable_if<typename Map::FullTypeTag, void>::type |
|
356 > { |
|
357 typedef typename Map::Value Value; |
|
358 typedef typename Map::Reference Reference; |
|
359 typedef typename Map::ConstReference ConstReference; |
|
360 typedef typename Map::Pointer Pointer; |
|
361 typedef typename Map::ConstPointer ConstPointer; |
|
362 }; |
|
363 |
|
364 /// Provides an immutable and unique id for each item in the graph. |
|
365 |
|
366 /// The IdMap class provides an unique and immutable mapping for each item |
|
367 /// in the graph. |
|
368 /// |
|
369 template <typename _Graph, typename _Item> |
|
370 class IdMap { |
|
371 public: |
|
372 typedef _Graph Graph; |
|
373 typedef int Value; |
|
374 typedef _Item Item; |
|
375 typedef _Item Key; |
|
376 |
|
377 typedef True NeedCopy; |
|
378 |
|
379 /// \brief Constructor. |
|
380 /// |
|
381 /// Constructor for creating id map. |
|
382 IdMap(const Graph& _graph) : graph(&_graph) {} |
|
383 |
|
384 /// \brief Gives back the \e id of the item. |
|
385 /// |
|
386 /// Gives back the immutable and unique \e id of the map. |
|
387 int operator[](const Item& item) const { return graph->id(item);} |
|
388 |
|
389 |
|
390 private: |
|
391 const Graph* graph; |
|
392 |
|
393 public: |
|
394 |
|
395 /// \brief The class represents the inverse of the map. |
|
396 /// |
|
397 /// The class represents the inverse of the map. |
|
398 /// \see inverse() |
|
399 class InverseMap { |
|
400 public: |
|
401 |
|
402 typedef True NeedCopy; |
|
403 |
|
404 /// \brief Constructor. |
|
405 /// |
|
406 /// Constructor for creating an id-to-item map. |
|
407 InverseMap(const Graph& _graph) : graph(&_graph) {} |
|
408 |
|
409 /// \brief Constructor. |
|
410 /// |
|
411 /// Constructor for creating an id-to-item map. |
|
412 InverseMap(const IdMap& idMap) : graph(idMap.graph) {} |
|
413 |
|
414 /// \brief Gives back the given item from its id. |
|
415 /// |
|
416 /// Gives back the given item from its id. |
|
417 /// |
|
418 Item operator[](int id) const { return graph->fromId(id, Item());} |
|
419 private: |
|
420 const Graph* graph; |
|
421 }; |
|
422 |
|
423 /// \brief Gives back the inverse of the map. |
|
424 /// |
|
425 /// Gives back the inverse of the map. |
|
426 InverseMap inverse() const { return InverseMap(*graph);} |
|
427 |
|
428 }; |
|
429 |
|
430 |
|
431 /// \brief General inversable graph-map type. |
|
432 |
|
433 /// This type provides simple inversable map functions. |
|
434 /// The InversableMap wraps an arbitrary ReadWriteMap |
|
435 /// and if a key is setted to a new value then store it |
|
436 /// in the inverse map. |
|
437 /// \param _Graph The graph type. |
|
438 /// \param _Map The map to extend with inversable functionality. |
|
439 template < |
|
440 typename _Graph, |
|
441 typename _Item, |
|
442 typename _Value, |
|
443 typename _Map |
|
444 = typename ItemSetTraits<_Graph, _Item>::template Map<_Value>::Parent |
|
445 > |
|
446 class InvertableMap : protected _Map { |
|
447 |
|
448 public: |
|
449 |
|
450 typedef _Map Map; |
|
451 typedef _Graph Graph; |
|
452 |
|
453 /// The key type of InvertableMap (Node, Edge, UndirEdge). |
|
454 typedef typename _Map::Key Key; |
|
455 /// The value type of the InvertableMap. |
|
456 typedef typename _Map::Value Value; |
|
457 |
|
458 /// \brief Constructor. |
|
459 /// |
|
460 /// Construct a new InvertableMap for the graph. |
|
461 /// |
|
462 InvertableMap(const Graph& graph) : Map(graph) {} |
|
463 |
|
464 /// \brief The setter function of the map. |
|
465 /// |
|
466 /// Sets the mapped value. |
|
467 void set(const Key& key, const Value& val) { |
|
468 Value oldval = Map::operator[](key); |
|
469 typename Container::iterator it = invMap.find(oldval); |
|
470 if (it != invMap.end() && it->second == key) { |
|
471 invMap.erase(it); |
|
472 } |
|
473 invMap.insert(make_pair(val, key)); |
|
474 Map::set(key, val); |
|
475 } |
|
476 |
|
477 /// \brief The getter function of the map. |
|
478 /// |
|
479 /// It gives back the value associated with the key. |
|
480 const Value operator[](const Key& key) const { |
|
481 return Map::operator[](key); |
|
482 } |
|
483 |
|
484 /// \brief Add a new key to the map. |
|
485 /// |
|
486 /// Add a new key to the map. It is called by the |
|
487 /// \c AlterationNotifier. |
|
488 virtual void add(const Key& key) { |
|
489 Map::add(key); |
|
490 } |
|
491 |
|
492 /// \brief Erase the key from the map. |
|
493 /// |
|
494 /// Erase the key to the map. It is called by the |
|
495 /// \c AlterationNotifier. |
|
496 virtual void erase(const Key& key) { |
|
497 Value val = Map::operator[](key); |
|
498 typename Container::iterator it = invMap.find(val); |
|
499 if (it != invMap.end() && it->second == key) { |
|
500 invMap.erase(it); |
|
501 } |
|
502 Map::erase(key); |
|
503 } |
|
504 |
|
505 /// \brief Clear the keys from the map and inverse map. |
|
506 /// |
|
507 /// Clear the keys from the map and inverse map. It is called by the |
|
508 /// \c AlterationNotifier. |
|
509 virtual void clear() { |
|
510 invMap.clear(); |
|
511 Map::clear(); |
|
512 } |
|
513 |
|
514 private: |
|
515 |
|
516 typedef std::map<Value, Key> Container; |
|
517 Container invMap; |
|
518 |
|
519 public: |
|
520 |
|
521 /// \brief The inverse map type. |
|
522 /// |
|
523 /// The inverse of this map. The subscript operator of the map |
|
524 /// gives back always the item what was last assigned to the value. |
|
525 class InverseMap { |
|
526 public: |
|
527 /// \brief Constructor of the InverseMap. |
|
528 /// |
|
529 /// Constructor of the InverseMap. |
|
530 InverseMap(const InvertableMap& _inverted) : inverted(_inverted) {} |
|
531 |
|
532 /// The value type of the InverseMap. |
|
533 typedef typename InvertableMap::Key Value; |
|
534 /// The key type of the InverseMap. |
|
535 typedef typename InvertableMap::Value Key; |
|
536 |
|
537 /// \brief Subscript operator. |
|
538 /// |
|
539 /// Subscript operator. It gives back always the item |
|
540 /// what was last assigned to the value. |
|
541 Value operator[](const Key& key) const { |
|
542 typename Container::const_iterator it = inverted.invMap.find(key); |
|
543 return it->second; |
|
544 } |
|
545 |
|
546 private: |
|
547 const InvertableMap& inverted; |
|
548 }; |
|
549 |
|
550 /// \brief It gives back the just readeable inverse map. |
|
551 /// |
|
552 /// It gives back the just readeable inverse map. |
|
553 InverseMap inverse() const { |
|
554 return InverseMap(*this); |
|
555 } |
|
556 |
|
557 |
|
558 |
|
559 }; |
|
560 |
|
561 /// \brief Provides a mutable, continuous and unique descriptor for each |
|
562 /// item in the graph. |
|
563 /// |
|
564 /// The DescriptorMap class provides a mutable, continuous and immutable |
|
565 /// mapping for each item in the graph. The value for an item may mutated |
|
566 /// on each operation when the an item erased or added to graph. |
|
567 /// |
|
568 /// \param _Graph The graph class the \c DescriptorMap belongs to. |
|
569 /// \param _Item The Item is the Key of the Map. It may be Node, Edge or |
|
570 /// UndirEdge. |
|
571 /// \param _Map A ReadWriteMap mapping from the item type to integer. |
|
572 template < |
|
573 typename _Graph, |
|
574 typename _Item, |
|
575 typename _Map |
|
576 = typename ItemSetTraits<_Graph, _Item>::template Map<int>::Parent |
|
577 > |
|
578 class DescriptorMap : protected _Map { |
|
579 |
|
580 typedef _Item Item; |
|
581 typedef _Map Map; |
|
582 |
|
583 public: |
|
584 /// The graph class of DescriptorMap. |
|
585 typedef _Graph Graph; |
|
586 |
|
587 /// The key type of DescriptorMap (Node, Edge, UndirEdge). |
|
588 typedef typename _Map::Key Key; |
|
589 /// The value type of DescriptorMap. |
|
590 typedef typename _Map::Value Value; |
|
591 |
|
592 /// \brief Constructor. |
|
593 /// |
|
594 /// Constructor for descriptor map. |
|
595 DescriptorMap(const Graph& _graph) : Map(_graph) { |
|
596 build(); |
|
597 } |
|
598 |
|
599 /// \brief Add a new key to the map. |
|
600 /// |
|
601 /// Add a new key to the map. It is called by the |
|
602 /// \c AlterationNotifier. |
|
603 virtual void add(const Item& item) { |
|
604 Map::add(item); |
|
605 Map::set(item, invMap.size()); |
|
606 invMap.push_back(item); |
|
607 } |
|
608 |
|
609 /// \brief Erase the key from the map. |
|
610 /// |
|
611 /// Erase the key to the map. It is called by the |
|
612 /// \c AlterationNotifier. |
|
613 virtual void erase(const Item& item) { |
|
614 Map::set(invMap.back(), Map::operator[](item)); |
|
615 invMap[Map::operator[](item)] = invMap.back(); |
|
616 invMap.pop_back(); |
|
617 Map::erase(item); |
|
618 } |
|
619 |
|
620 /// \brief Build the unique map. |
|
621 /// |
|
622 /// Build the unique map. It is called by the |
|
623 /// \c AlterationNotifier. |
|
624 virtual void build() { |
|
625 Map::build(); |
|
626 Item it; |
|
627 const typename Map::Graph* graph = Map::getGraph(); |
|
628 for (graph->first(it); it != INVALID; graph->next(it)) { |
|
629 Map::set(it, invMap.size()); |
|
630 invMap.push_back(it); |
|
631 } |
|
632 } |
|
633 |
|
634 /// \brief Clear the keys from the map. |
|
635 /// |
|
636 /// Clear the keys from the map. It is called by the |
|
637 /// \c AlterationNotifier. |
|
638 virtual void clear() { |
|
639 invMap.clear(); |
|
640 Map::clear(); |
|
641 } |
|
642 |
|
643 /// \brief Gives back the \e descriptor of the item. |
|
644 /// |
|
645 /// Gives back the mutable and unique \e descriptor of the map. |
|
646 int operator[](const Item& item) const { |
|
647 return Map::operator[](item); |
|
648 } |
|
649 |
|
650 private: |
|
651 |
|
652 typedef std::vector<Item> Container; |
|
653 Container invMap; |
|
654 |
|
655 public: |
|
656 /// \brief The inverse map type. |
|
657 /// |
|
658 /// The inverse map type. |
|
659 class InverseMap { |
|
660 public: |
|
661 /// \brief Constructor of the InverseMap. |
|
662 /// |
|
663 /// Constructor of the InverseMap. |
|
664 InverseMap(const DescriptorMap& _inverted) |
|
665 : inverted(_inverted) {} |
|
666 |
|
667 |
|
668 /// The value type of the InverseMap. |
|
669 typedef typename DescriptorMap::Key Value; |
|
670 /// The key type of the InverseMap. |
|
671 typedef typename DescriptorMap::Value Key; |
|
672 |
|
673 /// \brief Subscript operator. |
|
674 /// |
|
675 /// Subscript operator. It gives back the item |
|
676 /// that the descriptor belongs to currently. |
|
677 Value operator[](const Key& key) const { |
|
678 return inverted.invMap[key]; |
|
679 } |
|
680 |
|
681 private: |
|
682 const DescriptorMap& inverted; |
|
683 }; |
|
684 |
|
685 /// \brief Gives back the inverse of the map. |
|
686 /// |
|
687 /// Gives back the inverse of the map. |
|
688 const InverseMap inverse() const { |
|
689 return InverseMap(*this); |
|
690 } |
|
691 }; |
|
692 |
|
693 /// \brief Returns the source of the given edge. |
|
694 /// |
|
695 /// The SourceMap gives back the source Node of the given edge. |
|
696 /// \author Balazs Dezso |
|
697 template <typename Graph> |
|
698 class SourceMap { |
|
699 public: |
|
700 |
|
701 typedef True NeedCopy; |
|
702 |
|
703 typedef typename Graph::Node Value; |
|
704 typedef typename Graph::Edge Key; |
|
705 |
|
706 /// \brief Constructor |
|
707 /// |
|
708 /// Constructor |
|
709 /// \param _graph The graph that the map belongs to. |
|
710 SourceMap(const Graph& _graph) : graph(_graph) {} |
|
711 |
|
712 /// \brief The subscript operator. |
|
713 /// |
|
714 /// The subscript operator. |
|
715 /// \param edge The edge |
|
716 /// \return The source of the edge |
|
717 Value operator[](const Key& edge) { |
|
718 return graph.source(edge); |
|
719 } |
|
720 |
|
721 private: |
|
722 const Graph& graph; |
|
723 }; |
|
724 |
|
725 /// \brief Returns a \ref SourceMap class |
|
726 /// |
|
727 /// This function just returns an \ref SourceMap class. |
|
728 /// \relates SourceMap |
|
729 template <typename Graph> |
|
730 inline SourceMap<Graph> sourceMap(const Graph& graph) { |
|
731 return SourceMap<Graph>(graph); |
|
732 } |
|
733 |
|
734 /// \brief Returns the target of the given edge. |
|
735 /// |
|
736 /// The TargetMap gives back the target Node of the given edge. |
|
737 /// \author Balazs Dezso |
|
738 template <typename Graph> |
|
739 class TargetMap { |
|
740 public: |
|
741 |
|
742 typedef True NeedCopy; |
|
743 |
|
744 typedef typename Graph::Node Value; |
|
745 typedef typename Graph::Edge Key; |
|
746 |
|
747 /// \brief Constructor |
|
748 /// |
|
749 /// Constructor |
|
750 /// \param _graph The graph that the map belongs to. |
|
751 TargetMap(const Graph& _graph) : graph(_graph) {} |
|
752 |
|
753 /// \brief The subscript operator. |
|
754 /// |
|
755 /// The subscript operator. |
|
756 /// \param edge The edge |
|
757 /// \return The target of the edge |
|
758 Value operator[](const Key& key) { |
|
759 return graph.target(key); |
|
760 } |
|
761 |
|
762 private: |
|
763 const Graph& graph; |
|
764 }; |
|
765 |
|
766 /// \brief Returns a \ref TargetMap class |
|
767 |
|
768 /// This function just returns an \ref TargetMap class. |
|
769 /// \relates TargetMap |
|
770 template <typename Graph> |
|
771 inline TargetMap<Graph> targetMap(const Graph& graph) { |
|
772 return TargetMap<Graph>(graph); |
|
773 } |
|
774 |
|
775 /// \brief Returns the "forward" directed edge view of undirected edge. |
|
776 /// |
|
777 /// Returns the "forward" directed edge view of undirected edge. |
|
778 /// \author Balazs Dezso |
|
779 template <typename Graph> |
|
780 class ForwardMap { |
|
781 public: |
|
782 |
|
783 typedef True NeedCopy; |
|
784 |
|
785 typedef typename Graph::Edge Value; |
|
786 typedef typename Graph::UndirEdge Key; |
|
787 |
|
788 /// \brief Constructor |
|
789 /// |
|
790 /// Constructor |
|
791 /// \param _graph The graph that the map belongs to. |
|
792 ForwardMap(const Graph& _graph) : graph(_graph) {} |
|
793 |
|
794 /// \brief The subscript operator. |
|
795 /// |
|
796 /// The subscript operator. |
|
797 /// \param key An undirected edge |
|
798 /// \return The "forward" directed edge view of undirected edge |
|
799 Value operator[](const Key& key) const { |
|
800 return graph.edgeWithSource(key, graph.source(key)); |
|
801 } |
|
802 |
|
803 private: |
|
804 const Graph& graph; |
|
805 }; |
|
806 |
|
807 /// \brief Returns a \ref ForwardMap class |
|
808 |
|
809 /// This function just returns an \ref ForwardMap class. |
|
810 /// \relates ForwardMap |
|
811 template <typename Graph> |
|
812 inline ForwardMap<Graph> forwardMap(const Graph& graph) { |
|
813 return ForwardMap<Graph>(graph); |
|
814 } |
|
815 |
|
816 /// \brief Returns the "backward" directed edge view of undirected edge. |
|
817 /// |
|
818 /// Returns the "backward" directed edge view of undirected edge. |
|
819 /// \author Balazs Dezso |
|
820 template <typename Graph> |
|
821 class BackwardMap { |
|
822 public: |
|
823 typedef True NeedCopy; |
|
824 |
|
825 typedef typename Graph::Edge Value; |
|
826 typedef typename Graph::UndirEdge Key; |
|
827 |
|
828 /// \brief Constructor |
|
829 /// |
|
830 /// Constructor |
|
831 /// \param _graph The graph that the map belongs to. |
|
832 BackwardMap(const Graph& _graph) : graph(_graph) {} |
|
833 |
|
834 /// \brief The subscript operator. |
|
835 /// |
|
836 /// The subscript operator. |
|
837 /// \param key An undirected edge |
|
838 /// \return The "backward" directed edge view of undirected edge |
|
839 Value operator[](const Key& key) const { |
|
840 return graph.edgeWithSource(key, graph.target(key)); |
|
841 } |
|
842 |
|
843 private: |
|
844 const Graph& graph; |
|
845 }; |
|
846 |
|
847 /// \brief Returns a \ref BackwardMap class |
|
848 |
|
849 /// This function just returns an \ref BackwardMap class. |
|
850 /// \relates BackwardMap |
|
851 template <typename Graph> |
|
852 inline BackwardMap<Graph> backwardMap(const Graph& graph) { |
|
853 return BackwardMap<Graph>(graph); |
|
854 } |
|
855 |
|
856 |
|
857 /// @} |
|
858 |
|
859 } //END OF NAMESPACE LEMON |
|
860 |
|
861 #endif |
|