[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

graphs.hxx |

1 /************************************************************************/
2 /* */
3 /* Copyright 2011-2015 by Stefan Schmidt, Philip Schill and */
4 /* Ullrich Koethe */
5 /* */
6 /* This file is part of the VIGRA computer vision library. */
7 /* The VIGRA Website is */
8 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
9 /* Please direct questions, bug reports, and contributions to */
10 /* ullrich.koethe@iwr.uni-heidelberg.de or */
11 /* vigra@informatik.uni-hamburg.de */
12 /* */
13 /* Permission is hereby granted, free of charge, to any person */
14 /* obtaining a copy of this software and associated documentation */
15 /* files (the "Software"), to deal in the Software without */
16 /* restriction, including without limitation the rights to use, */
17 /* copy, modify, merge, publish, distribute, sublicense, and/or */
18 /* sell copies of the Software, and to permit persons to whom the */
19 /* Software is furnished to do so, subject to the following */
20 /* conditions: */
21 /* */
22 /* The above copyright notice and this permission notice shall be */
23 /* included in all copies or substantial portions of the */
24 /* Software. */
25 /* */
26 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
27 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
28 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
29 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
30 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
31 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
32 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
33 /* OTHER DEALINGS IN THE SOFTWARE. */
34 /* */
35 /************************************************************************/
36
37 /**
38 * This header provides definitions of graph-related types
39 * and optionally provides a gateway to popular graph libraries
40 * (for now, BGL is supported).
41 */
42
43 #ifndef VIGRA_GRAPH_HXX
44 #define VIGRA_GRAPH_HXX
45
46 #include <stdexcept>
47 #include <vector>
48 #include <map>
49
50 #include "metaprogramming.hxx"
51 #include "tinyvector.hxx"
52 #include "filter_iterator.hxx"
53
54 #ifdef WITH_BOOST_GRAPH
55
56 # include <boost/tuple/tuple.hpp>
57 # include <boost/graph/graph_traits.hpp>
58 # include <boost/graph/properties.hpp>
59
60 namespace vigra {
61 namespace boost_graph {
62
63 // vigra::boost_graph contains algorithms that are compatible to the Boost Graph Library
64 using namespace boost;
65
66 }} // namespace vigra::boost_graph
67
68 #else // not WITH_BOOST_GRAPH
69
70 // emulate the BGL-style interface
71 namespace vigra {
72 namespace boost_graph {
73
74 struct no_property {};
75
76 // tag classes were copied from boost:
77 // directed_category tags
78 struct directed_tag { };
79 struct undirected_tag { };
80 struct bidirectional_tag : public directed_tag { };
81
82 // traversal_category tags
83 struct incidence_graph_tag { };
84 struct adjacency_graph_tag { };
85 struct bidirectional_graph_tag : public incidence_graph_tag { };
86 struct vertex_list_graph_tag { };
87 struct edge_list_graph_tag { };
88 struct adjacency_matrix_tag { };
89
90 // edge_parallel_category tags
91 struct allow_parallel_edge_tag { };
92 struct disallow_parallel_edge_tag { };
93
94 // property maps:
95 struct readable_property_map_tag { };
96 struct writable_property_map_tag { };
97 struct read_write_property_map_tag
98 : public readable_property_map_tag,
99 public writable_property_map_tag {};
100 struct lvalue_property_map_tag
101 : public read_write_property_map_tag {};
102
103 struct vertex_index_t {};
104
105 struct edge_property_tag {};
106
107 // tie() support for std::pair, similar to Boost's one:
108 // (necessary because std::pair doesn't define a suitable assignment operator)
109 template<class T1, class T2>
110 class tie_adapter
111 {
112 public:
113 tie_adapter(T1 &x, T2 &y)
114 : x_(x), y_(y)
115 {}
116
117 template<class X, class Y>
118 tie_adapter & operator=(const std::pair<X, Y> &pair)
119 {
120 x_ = pair.first;
121 y_ = pair.second;
122 return *this;
123 }
124
125 protected:
126 T1 &x_;
127 T2 &y_;
128 };
129
130 template<class T1, class T2>
131 inline
132 tie_adapter<T1, T2>
133 tie(T1& t1, T2& t2)
134 {
135 return tie_adapter<T1, T2>(t1, t2);
136 }
137
138 // graph_traits class template
139 template <typename G>
140 struct graph_traits {
141 typedef typename G::vertex_descriptor vertex_descriptor;
142 typedef typename G::edge_descriptor edge_descriptor;
143 typedef typename G::adjacency_iterator adjacency_iterator;
144 typedef typename G::out_edge_iterator out_edge_iterator;
145 typedef typename G::in_edge_iterator in_edge_iterator;
146 typedef typename G::vertex_iterator vertex_iterator;
147 typedef typename G::edge_iterator edge_iterator;
148
149 typedef typename G::directed_category directed_category;
150 typedef typename G::edge_parallel_category edge_parallel_category;
151 typedef typename G::traversal_category traversal_category;
152
153 typedef typename G::vertices_size_type vertices_size_type;
154 typedef typename G::edges_size_type edges_size_type;
155 typedef typename G::degree_size_type degree_size_type;
156
157 static inline vertex_descriptor null_vertex()
158 {
159 return vertex_descriptor(-1);
160 }
161 };
162
163 // property_traits class template
164 template <typename PropMap>
165 struct property_traits
166 {
167 typedef typename PropMap::key_type key_type;
168 typedef typename PropMap::value_type value_type;
169 typedef typename PropMap::reference reference;
170 typedef typename PropMap::category category;
171 };
172
173 }} // namespace vigra::boost_graph
174
175 #endif // WITH_BOOST_GRAPH
176
177 #ifdef WITH_LEMON
178 # include <lemon/core.h>
179 #else // not WITH_LEMON
180
181 // emulate the lemon interface
182 namespace lemon {
183
184 struct Invalid {
185 public:
186 bool operator==(Invalid) const { return true; }
187 bool operator!=(Invalid) const { return false; }
188 bool operator< (Invalid) const { return false; }
189
190 template <class T, int N>
191 operator vigra::TinyVector<T, N>() const
192 {
193 return vigra::TinyVector<T, N>(-1);
194 }
195 };
196
197 static const Invalid INVALID = Invalid();
198
199 typedef vigra::VigraTrueType True;
200 typedef vigra::VigraFalseType False;
201
202 } // namespace lemon
203
204 #endif // WITH_LEMON
205
206 namespace lemon {
207
208 template <class T>
209 inline bool operator==(T const & t, Invalid)
210 {
211 return t == T(Invalid());
212 }
213
214 template <class T>
215 inline bool operator==(Invalid, T const & t)
216 {
217 return t == T(Invalid());
218 }
219
220 template <class T>
221 inline bool operator!=(T const & t, Invalid)
222 {
223 return t != T(Invalid());
224 }
225
226 template <class T>
227 inline bool operator!=(Invalid, T const & t)
228 {
229 return t != T(Invalid());
230 }
231
232 } // namespace lemon
233
234 namespace vigra {
235
236
237 template<class GRAPH,class ITEM>
238 struct GraphItemHelper;
239
240 template<class GRAPH>
241 struct GraphItemHelper<GRAPH,typename GRAPH::Edge>{
242 typedef typename GRAPH::index_type index_type ;
243 typedef typename GRAPH::Edge Item;
244 typedef typename GRAPH::EdgeIt ItemIt;
245
246
247 static index_type maxItemId(const GRAPH & g){
248 return g.maxEdgeId();
249 }
250 static index_type itemNum(const GRAPH & g){
251 return g.edgeNum();
252 }
253 static Item itemFromId(const GRAPH & g,const index_type id){
254 return g.edgeFromId(id);
255 }
256
257 };
258
259 template<class GRAPH>
260 struct GraphItemHelper<GRAPH,typename GRAPH::Node>{
261 typedef typename GRAPH::index_type index_type ;
262 typedef typename GRAPH::Node Item;
263 typedef typename GRAPH::NodeIt ItemIt;
264
265
266 static index_type maxItemId(const GRAPH & g){
267 return g.maxNodeId();
268 }
269 static index_type itemNum(const GRAPH & g){
270 return g.nodeNum();
271 }
272 static Item itemFromId(const GRAPH & g,const index_type id){
273 return g.nodeFromId(id);
274 }
275 };
276
277
278 template<class GRAPH>
279 struct GraphItemHelper<GRAPH,typename GRAPH::Arc>{
280 typedef typename GRAPH::index_type index_type ;
281 typedef typename GRAPH::Arc Item;
282 typedef typename GRAPH::ArcIt ItemIt;
283
284
285 static index_type maxItemId(const GRAPH & g){
286 return g.maxArcId();
287 }
288 static index_type itemNum(const GRAPH & g){
289 return g.arcNum();
290 }
291 static Item itemFromId(const GRAPH & g,const index_type id){
292 return g.arcFromId(id);
293 }
294 };
295
296
297
298
299
300 namespace lemon_graph {
301
302 // vigra::lemon_graph contains algorithms that are compatible to the LEMON graph library
303 using namespace lemon;
304
305 }} // namespace vigra::lemon_graph
306
307
308
309 namespace vigra {
310 namespace detail {
311
312 template <typename INDEXTYPE>
313 class NodeDescriptor
314 {
315 public:
316 typedef INDEXTYPE index_type;
317 NodeDescriptor(lemon::Invalid = lemon::INVALID)
318 : id_(-1)
319 {}
320 explicit NodeDescriptor(index_type const & id)
321 : id_(id)
322 {}
323 bool operator!=(NodeDescriptor const & other) const
324 {
325 return id_ != other.id_;
326 }
327 bool operator==(NodeDescriptor const & other) const
328 {
329 return id_ == other.id_;
330 }
331 bool operator<(NodeDescriptor const & other) const
332 {
333 return id_ < other.id_;
334 }
335 index_type id() const
336 {
337 return id_;
338 }
339 protected:
340 index_type id_;
341 };
342
343 template <typename INDEXTYPE>
344 std::ostream & operator << (std::ostream & os, NodeDescriptor<INDEXTYPE> const & item)
345 {
346 return os << item.id();
347 }
348
349 template <typename INDEXTYPE>
350 class ArcDescriptor
351 {
352 public:
353 typedef INDEXTYPE index_type;
354 ArcDescriptor(lemon::Invalid = lemon::INVALID)
355 : id_(-1)
356 {}
357 explicit ArcDescriptor(index_type const & id)
358 : id_(id)
359 {}
360 bool operator!=(ArcDescriptor const & other) const
361 {
362 return id_ != other.id_;
363 }
364 bool operator==(ArcDescriptor const & other) const
365 {
366 return id_ == other.id_;
367 }
368 bool operator<(ArcDescriptor const & other) const
369 {
370 return id_ < other.id_;
371 }
372 index_type id() const
373 {
374 return id_;
375 }
376 protected:
377 index_type id_;
378 };
379
380 template <typename INDEXTYPE>
381 std::ostream & operator << (std::ostream & os, ArcDescriptor<INDEXTYPE> const & item)
382 {
383 return os << item.id();
384 }
385
386 } // namespace detail
387
388
389
390 enum ContainerTag
391 {
392 MapTag,
393 VectorTag,
394 IndexVectorTag
395 };
396
397 /**
398 * @brief The PropertyMap is used to store Node or Arc information of graphs.
399 *
400 * @tparam <KEYTYPE> the key type
401 * @tparam <MAPPEDTYPE> the mapped type
402 * @tparam <ContainerTag = MapTag> whether to use a map or a vector as underlying storage
403 *
404 * @note
405 * In contrast to std::map, operator[] does not insert elements. Use insert() instead.
406 * If ContainerTag == MapTag: at() and operator[] behave like std::map::at().
407 * If ContainerTag == IndexVectorTag: at() behaves like std::map::at(). operator[] does not check if the key exists.
408 */
409 template <typename KEYTYPE, typename MAPPEDTYPE, ContainerTag = MapTag >
410 class PropertyMap
411 {
412 public:
413 typedef KEYTYPE key_type;
414 typedef MAPPEDTYPE mapped_type;
415 typedef std::pair<key_type const, mapped_type> value_type;
416 typedef value_type & reference;
417 typedef value_type const & const_reference;
418 typedef std::map<key_type, mapped_type> Map;
419 typedef typename Map::iterator iterator;
420 typedef typename Map::const_iterator const_iterator;
421
422 mapped_type & at(key_type const & k)
423 {
424 return map_.at(k);
425 }
426 mapped_type const & at(key_type const & k) const
427 {
428 return map_.at(k);
429 }
430 mapped_type & operator[](key_type const & k)
431 {
432 return map_.at(k);
433 }
434 mapped_type const & operator[](key_type const & k) const
435 {
436 return map_.at(k);
437 }
438 void insert(key_type const & k, mapped_type const & v)
439 {
440 map_[k] = v;
441 }
442 iterator begin()
443 {
444 return map_.begin();
445 }
446 const_iterator begin() const
447 {
448 return map_.begin();
449 }
450 const_iterator cbegin() const
451 {
452 return map_.cbegin();
453 }
454 iterator end()
455 {
456 return map_.end();
457 }
458 const_iterator end() const
459 {
460 return map_.end();
461 }
462 const_iterator cend() const
463 {
464 return map_.cend();
465 }
466 void clear()
467 {
468 map_.clear();
469 }
470 iterator find(key_type const & k)
471 {
472 return map_.find(k);
473 }
474 const_iterator find(key_type const & k) const
475 {
476 return map_.find(k);
477 }
478 size_t size() const
479 {
480 return map_.size();
481 }
482 size_t erase(key_type const & k)
483 {
484 return map_.erase(k);
485 }
486
487 protected:
488 Map map_;
489 };
490
491
492
493 namespace detail
494 {
495 template <typename VALUE_TYPE>
496 struct PMapValueSkipper
497 {
498 public:
499 typedef VALUE_TYPE value_type;
500 typedef typename value_type::first_type key_type;
501 PMapValueSkipper(key_type default_key)
502 :
503 default_key_(default_key)
504 {}
505 bool operator()(value_type const & v)
506 {
507 return v.first != default_key_;
508 }
509 private:
510 key_type const default_key_;
511 };
512 }
513
514 /**
515 * @brief Specialization of PropertyMap that stores the elements in a vector (size = max node id of stored elements).
516 */
517 template <typename KEYTYPE, typename MAPPEDTYPE>
518 class PropertyMap<KEYTYPE, MAPPEDTYPE, VectorTag>
519 {
520 public:
521 typedef KEYTYPE key_type;
522 typedef MAPPEDTYPE mapped_type;
523 typedef std::pair<key_type, mapped_type> value_type;
524 typedef value_type & reference;
525 typedef value_type const & const_reference;
526 typedef std::vector<value_type> Map;
527 typedef detail::PMapValueSkipper<value_type> ValueSkipper;
528 typedef FilterIterator<ValueSkipper, typename Map::iterator> iterator;
529 typedef FilterIterator<ValueSkipper, typename Map::const_iterator> const_iterator;
530
531 PropertyMap(key_type default_key = lemon::INVALID)
532 :
533 num_elements_(0),
534 default_key_(default_key)
535 {}
536
537 mapped_type & at(key_type const & k)
538 {
539 #ifdef VIGRA_CHECK_BOUNDS
540 if (k.id() < 0 || k.id() >= map_.size() || map_[k.id()].first == default_key_)
541 throw std::out_of_range("PropertyMap::at(): Key not found.");
542 #endif
543 return map_[k.id()].second;
544 }
545
546 mapped_type const & at(key_type const & k) const
547 {
548 #ifdef VIGRA_CHECK_BOUNDS
549 if (k.id() < 0 || k.id() >= map_.size() || map_[k.id()].first == default_key_)
550 throw std::out_of_range("PropertyMap::at(): Key not found.");
551 #endif
552 return map_[k.id()].second;
553 }
554
555 mapped_type & operator[](key_type const & k)
556 {
557 return map_[k.id()].second;
558 }
559
560 mapped_type const & operator[](key_type const & k) const
561 {
562 return map_[k.id()].second;
563 }
564
565 void insert(key_type const & k, mapped_type const & v)
566 {
567 if (k.id() < 0)
568 throw std::out_of_range("PropertyMap::insert(): Key must not be negative.");
569
570 if ((size_t)k.id() >= map_.size())
571 map_.resize(k.id()+1, value_type(default_key_, mapped_type()));
572
573 auto & elt = map_[k.id()];
574 if (elt.first == default_key_)
575 ++num_elements_;
576
577 elt.first = k;
578 elt.second = v;
579 }
580
581 #define MAKE_ITER(it) make_filter_iterator(ValueSkipper(default_key_), it, map_.end())
582 #define MAKE_CITER(it) make_filter_iterator(ValueSkipper(default_key_), it, map_.cend())
583
584 iterator begin()
585 {
586 return MAKE_ITER(map_.begin());
587 }
588
589 const_iterator begin() const
590 {
591 return MAKE_ITER(map_.begin());
592 }
593
594 const_iterator cbegin() const
595 {
596 return MAKE_CITER(map_.cbegin());
597 }
598
599 iterator end()
600 {
601 return MAKE_ITER(map_.end());
602 }
603
604 const_iterator end() const
605 {
606 return MAKE_ITER(map_.end());
607 }
608
609 const_iterator cend() const
610 {
611 return MAKE_CITER(map_.cend());
612 }
613
614 iterator find(key_type const & k)
615 {
616 if (k.id() < 0 || k.id() >= map_.size() || map_[k.id()].first == default_key_)
617 return end();
618 else
619 return MAKE_ITER(std::next(map_.begin(), k.id()));
620 }
621
622 const_iterator find(key_type const & k) const
623 {
624 if (k.id() < 0 || k.id() >= map_.size() || map_[k.id()].first == default_key_)
625 return end();
626 else
627 return MAKE_ITER(std::next(map_.begin(), k.id()));
628 }
629
630 #undef MAKE_ITER
631 #undef MAKE_CITER
632
633 void clear()
634 {
635 map_.clear();
636 num_elements_ = 0;
637 }
638
639 size_t size() const
640 {
641 return num_elements_;
642 }
643
644 size_t erase(key_type const & k)
645 {
646 if (k.id() < 0 || k.id() >= map_.size() || map_[k.id()].first == default_key_)
647 {
648 return 0;
649 }
650 else
651 {
652 map_[k.id()].first = default_key_;
653 --num_elements_;
654 return 1;
655 }
656 }
657
658 protected:
659 Map map_;
660 size_t num_elements_;
661 key_type default_key_;
662 };
663
664
665
666 /**
667 * @brief
668 * Specialization of PropertyMap that stores the elements in a vector (size = number of stored elements).
669 * An additional index vector is needed for bookkeeping (size = max node id of stored elements).
670 */
671 template <typename KEYTYPE, typename MAPPEDTYPE>
672 class PropertyMap<KEYTYPE, MAPPEDTYPE, IndexVectorTag>
673 {
674 public:
675 typedef KEYTYPE key_type;
676 typedef MAPPEDTYPE mapped_type;
677 typedef std::pair<key_type, mapped_type> value_type;
678 typedef value_type & reference;
679 typedef value_type const & const_reference;
680 typedef std::vector<value_type> Map;
681 typedef typename Map::iterator iterator;
682 typedef typename Map::const_iterator const_iterator;
683
684 mapped_type & at(key_type const & k)
685 {
686 #ifdef VIGRA_CHECK_BOUNDS
687 if (indices_.at(k.id()) == -1)
688 throw std::out_of_range("PropertyMap::at(): Key not found.");
689 #endif
690 return map_[indices_[k.id()]].second;
691 }
692
693 mapped_type const & at(key_type const & k) const
694 {
695 #ifdef VIGRA_CHECK_BOUNDS
696 if (indices_.at(k.id()) == -1)
697 throw std::out_of_range("PropertyMap::at(): Key not found.");
698 #endif
699 return map_[indices_[k.id()]].second;
700 }
701
702 mapped_type & operator[](key_type const & k)
703 {
704 return map_[indices_[k.id()]].second;
705 }
706
707 mapped_type const & operator[](key_type const & k) const
708 {
709 return map_[indices_[k.id()]].second;
710 }
711
712 void insert(key_type const & k, mapped_type const & v)
713 {
714 if (k.id() < 0)
715 throw std::out_of_range("PropertyMap::insert(): Key must not be negative.");
716
717 if (k.id() >= indices_.size())
718 indices_.resize(k.id()+1, -1);
719
720 if (indices_[k.id()] == -1)
721 {
722 indices_[k.id()] = map_.size();
723 map_.push_back(value_type(k, v));
724 }
725 }
726
727 iterator begin()
728 {
729 return map_.begin();
730 }
731
732 const_iterator begin() const
733 {
734 return map_.begin();
735 }
736
737 const_iterator cbegin() const
738 {
739 return map_.cend();
740 }
741
742 iterator end()
743 {
744 return map_.end();
745 }
746
747 const_iterator end() const
748 {
749 return map_.end();
750 }
751
752 const_iterator cend() const
753 {
754 return map_.cend();
755 }
756
757 void clear()
758 {
759 map_.clear();
760 indices_.clear();
761 }
762
763 iterator find(key_type const & k)
764 {
765 if (k.id() < 0 || k.id() >= indices_.size() || indices_[k.id()] == -1)
766 return map_.end();
767 else
768 return std::next(map_.begin(), indices_[k.id()]);
769 }
770
771 const_iterator find(key_type const & k) const
772 {
773 if (k.id() < 0 || k.id() >= indices_.size() || indices_[k.id()] == -1)
774 return map_.end();
775 else
776 return std::next(map_.begin(), indices_[k.id()]);
777 }
778
779 size_t size() const
780 {
781 return map_.size();
782 }
783
784 size_t erase(key_type const & k)
785 {
786 if (k.id() < 0 || k.id() >= indices_.size() || indices_[k.id()] == -1)
787 {
788 return 0;
789 }
790 else
791 {
792 // Erase the element from the index vector and the map.
793 size_t ind = indices_[k.id()];
794 indices_[k.id()] = -1;
795 map_.erase(std::next(map_.begin(), ind));
796
797 // Adjust the indices.
798 for (size_t i = 0; i < indices_.size(); ++i)
799 if (indices_[i] > ind)
800 --indices_[i];
801 return 1;
802 }
803 }
804
805 protected:
806 Map map_;
807 std::vector<int> indices_;
808 };
809
810
811
812 } // namespace vigra
813
814
815
816 #endif // VIGRA_GRAPH_HXX
vigra::FilterIterator
This iterator creates a view of another iterator and skips elements that do not fulfill a given predi...
Definition: filter_iterator.hxx:84
vigra::TinyVector< T, N >
vigra
vigra::operator==
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition: fftw3.hxx:825
vigra::PropertyMap
The PropertyMap is used to store Node or Arc information of graphs.
Definition: graphs.hxx:410
vigra::operator<
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition: fixedpoint.hxx:512
vigra::operator!=
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition: fftw3.hxx:841

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.11.1