[ 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
60namespace vigra {
61namespace boost_graph {
62
63// vigra::boost_graph contains algorithms that are compatible to the Boost Graph Library
64using namespace boost;
65
66}} // namespace vigra::boost_graph
67
68#else // not WITH_BOOST_GRAPH
69
70// emulate the BGL-style interface
71namespace vigra {
72namespace boost_graph {
73
74struct no_property {};
75
76// tag classes were copied from boost:
77// directed_category tags
78struct directed_tag { };
79struct undirected_tag { };
80struct bidirectional_tag : public directed_tag { };
81
82// traversal_category tags
83struct incidence_graph_tag { };
84struct adjacency_graph_tag { };
85struct bidirectional_graph_tag : public incidence_graph_tag { };
86struct vertex_list_graph_tag { };
87struct edge_list_graph_tag { };
88struct adjacency_matrix_tag { };
89
90// edge_parallel_category tags
91struct allow_parallel_edge_tag { };
92struct disallow_parallel_edge_tag { };
93
94// property maps:
95struct readable_property_map_tag { };
96struct writable_property_map_tag { };
97struct read_write_property_map_tag
98 : public readable_property_map_tag,
99 public writable_property_map_tag {};
100struct lvalue_property_map_tag
101 : public read_write_property_map_tag {};
102
103struct vertex_index_t {};
104
105struct 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)
109template<class T1, class T2>
110class 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
130template<class T1, class T2>
131inline
132tie_adapter<T1, T2>
133tie(T1& t1, T2& t2)
134{
135 return tie_adapter<T1, T2>(t1, t2);
136}
137
138// graph_traits class template
139template <typename G>
140struct 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
164template <typename PropMap>
165struct 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
182namespace lemon {
183
184struct 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
197static const Invalid INVALID = Invalid();
198
199typedef vigra::VigraTrueType True;
200typedef vigra::VigraFalseType False;
201
202} // namespace lemon
203
204#endif // WITH_LEMON
205
206namespace lemon {
207
208template <class T>
209inline bool operator==(T const & t, Invalid)
210{
211 return t == T(Invalid());
212}
213
214template <class T>
215inline bool operator==(Invalid, T const & t)
216{
217 return t == T(Invalid());
218}
219
220template <class T>
221inline bool operator!=(T const & t, Invalid)
222{
223 return t != T(Invalid());
224}
225
226template <class T>
227inline bool operator!=(Invalid, T const & t)
228{
229 return t != T(Invalid());
230}
231
232} // namespace lemon
233
234namespace vigra {
235
236
237template<class GRAPH,class ITEM>
238struct GraphItemHelper;
239
240template<class GRAPH>
241struct 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
259template<class GRAPH>
260struct 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
278template<class GRAPH>
279struct 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
300namespace lemon_graph {
301
302// vigra::lemon_graph contains algorithms that are compatible to the LEMON graph library
303using namespace lemon;
304
305}} // namespace vigra::lemon_graph
306
307
308
309namespace vigra {
310namespace detail {
311
312template <typename INDEXTYPE>
313class NodeDescriptor
314{
315public:
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 }
339protected:
340 index_type id_;
341};
342
343template <typename INDEXTYPE>
344std::ostream & operator << (std::ostream & os, NodeDescriptor<INDEXTYPE> const & item)
345{
346 return os << item.id();
347}
348
349template <typename INDEXTYPE>
350class ArcDescriptor
351{
352public:
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 }
376protected:
377 index_type id_;
378};
379
380template <typename INDEXTYPE>
381std::ostream & operator << (std::ostream & os, ArcDescriptor<INDEXTYPE> const & item)
382{
383 return os << item.id();
384}
385
386} // namespace detail
387
388
389
390enum 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 */
409template <typename KEYTYPE, typename MAPPEDTYPE, ContainerTag = MapTag >
411{
412public:
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
487protected:
488 Map map_;
489};
490
491
492
493namespace 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 */
517template <typename KEYTYPE, typename MAPPEDTYPE>
518class PropertyMap<KEYTYPE, MAPPEDTYPE, VectorTag>
519{
520public:
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;
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
658protected:
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 */
671template <typename KEYTYPE, typename MAPPEDTYPE>
672class PropertyMap<KEYTYPE, MAPPEDTYPE, IndexVectorTag>
673{
674public:
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
805protected:
806 Map map_;
807 std::vector<int> indices_;
808};
809
810
811
812} // namespace vigra
813
814
815
816#endif // VIGRA_GRAPH_HXX
This iterator creates a view of another iterator and skips elements that do not fulfill a given predi...
Definition filter_iterator.hxx:88
The PropertyMap is used to store Node or Arc information of graphs.
Definition graphs.hxx:411

© 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.12.2 (Mon Apr 14 2025)