43#ifndef VIGRA_GRAPH_HXX
44#define VIGRA_GRAPH_HXX
50#include "metaprogramming.hxx"
51#include "tinyvector.hxx"
52#include "filter_iterator.hxx"
54#ifdef WITH_BOOST_GRAPH
56# include <boost/tuple/tuple.hpp>
57# include <boost/graph/graph_traits.hpp>
58# include <boost/graph/properties.hpp>
61namespace boost_graph {
72namespace boost_graph {
78struct directed_tag { };
79struct undirected_tag { };
80struct bidirectional_tag :
public directed_tag { };
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 { };
91struct allow_parallel_edge_tag { };
92struct disallow_parallel_edge_tag { };
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 {};
103struct vertex_index_t {};
105struct edge_property_tag {};
109template<
class T1,
class T2>
113 tie_adapter(T1 &x, T2 &y)
117 template<
class X,
class Y>
118 tie_adapter & operator=(
const std::pair<X, Y> &pair)
130template<
class T1,
class T2>
135 return tie_adapter<T1, T2>(t1, t2);
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;
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;
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;
157 static inline vertex_descriptor null_vertex()
159 return vertex_descriptor(-1);
164template <
typename PropMap>
165struct property_traits
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;
178# include <lemon/core.h>
186 bool operator==(Invalid)
const {
return true; }
187 bool operator!=(Invalid)
const {
return false; }
188 bool operator< (Invalid)
const {
return false; }
190 template <
class T,
int N>
197static const Invalid INVALID = Invalid();
199typedef vigra::VigraTrueType True;
200typedef vigra::VigraFalseType False;
209inline bool operator==(T
const & t, Invalid)
211 return t == T(Invalid());
215inline bool operator==(Invalid, T
const & t)
217 return t == T(Invalid());
221inline bool operator!=(T
const & t, Invalid)
223 return t != T(Invalid());
227inline bool operator!=(Invalid, T
const & t)
229 return t != T(Invalid());
237template<
class GRAPH,
class ITEM>
238struct GraphItemHelper;
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;
247 static index_type maxItemId(
const GRAPH & g){
248 return g.maxEdgeId();
250 static index_type itemNum(
const GRAPH & g){
253 static Item itemFromId(
const GRAPH & g,
const index_type
id){
254 return g.edgeFromId(
id);
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;
266 static index_type maxItemId(
const GRAPH & g){
267 return g.maxNodeId();
269 static index_type itemNum(
const GRAPH & g){
272 static Item itemFromId(
const GRAPH & g,
const index_type
id){
273 return g.nodeFromId(
id);
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;
285 static index_type maxItemId(
const GRAPH & g){
288 static index_type itemNum(
const GRAPH & g){
291 static Item itemFromId(
const GRAPH & g,
const index_type
id){
292 return g.arcFromId(
id);
300namespace lemon_graph {
303using namespace lemon;
312template <
typename INDEXTYPE>
316 typedef INDEXTYPE index_type;
317 NodeDescriptor(lemon::Invalid = lemon::INVALID)
320 explicit NodeDescriptor(index_type
const &
id)
323 bool operator!=(NodeDescriptor
const & other)
const
325 return id_ != other.id_;
327 bool operator==(NodeDescriptor
const & other)
const
329 return id_ == other.id_;
331 bool operator<(NodeDescriptor
const & other)
const
333 return id_ < other.id_;
335 index_type id()
const
343template <
typename INDEXTYPE>
344std::ostream & operator << (std::ostream & os, NodeDescriptor<INDEXTYPE>
const & item)
346 return os << item.id();
349template <
typename INDEXTYPE>
353 typedef INDEXTYPE index_type;
354 ArcDescriptor(lemon::Invalid = lemon::INVALID)
357 explicit ArcDescriptor(index_type
const &
id)
360 bool operator!=(ArcDescriptor
const & other)
const
362 return id_ != other.id_;
364 bool operator==(ArcDescriptor
const & other)
const
366 return id_ == other.id_;
368 bool operator<(ArcDescriptor
const & other)
const
370 return id_ < other.id_;
372 index_type id()
const
380template <
typename INDEXTYPE>
381std::ostream & operator << (std::ostream & os, ArcDescriptor<INDEXTYPE>
const & item)
383 return os << item.id();
409template <
typename KEYTYPE,
typename MAPPEDTYPE, ContainerTag = MapTag >
415 typedef std::pair<key_type const, mapped_type> value_type;
416 typedef value_type & reference;
418 typedef std::map<key_type, mapped_type> Map;
419 typedef typename Map::iterator iterator;
420 typedef typename Map::const_iterator const_iterator;
446 const_iterator begin()
const
450 const_iterator cbegin()
const
452 return map_.cbegin();
458 const_iterator end()
const
462 const_iterator cend()
const
474 const_iterator find(
key_type const &
k)
const
484 return map_.erase(
k);
495 template <
typename VALUE_TYPE>
496 struct PMapValueSkipper
500 typedef typename value_type::first_type key_type;
505 bool operator()(value_type
const & v)
507 return v.first != default_key_;
510 key_type
const default_key_;
517template <
typename KEYTYPE,
typename MAPPEDTYPE>
523 typedef std::pair<key_type, mapped_type> value_type;
524 typedef value_type & reference;
526 typedef std::vector<value_type> Map;
527 typedef detail::PMapValueSkipper<value_type> ValueSkipper;
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.");
543 return map_[
k.id()].second;
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.");
552 return map_[
k.id()].second;
557 return map_[
k.id()].second;
562 return map_[
k.id()].second;
568 throw std::out_of_range(
"PropertyMap::insert(): Key must not be negative.");
570 if ((
size_t)
k.id() >= map_.size())
571 map_.resize(
k.id()+1, value_type(default_key_,
mapped_type()));
573 auto &
elt = map_[
k.id()];
574 if (
elt.first == default_key_)
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())
586 return MAKE_ITER(map_.begin());
591 return MAKE_ITER(map_.begin());
596 return MAKE_CITER(map_.cbegin());
601 return MAKE_ITER(map_.end());
606 return MAKE_ITER(map_.end());
611 return MAKE_CITER(map_.cend());
616 if (
k.id() < 0 ||
k.id() >= map_.size() || map_[
k.id()].first == default_key_)
619 return MAKE_ITER(std::next(map_.begin(),
k.id()));
624 if (
k.id() < 0 ||
k.id() >= map_.size() || map_[
k.id()].first == default_key_)
627 return MAKE_ITER(std::next(map_.begin(),
k.id()));
641 return num_elements_;
646 if (
k.id() < 0 ||
k.id() >= map_.size() || map_[
k.id()].first == default_key_)
652 map_[
k.id()].first = default_key_;
660 size_t num_elements_;
671template <
typename KEYTYPE,
typename MAPPEDTYPE>
677 typedef std::pair<key_type, mapped_type> value_type;
678 typedef value_type & reference;
680 typedef std::vector<value_type> Map;
681 typedef typename Map::iterator iterator;
682 typedef typename Map::const_iterator const_iterator;
686#ifdef VIGRA_CHECK_BOUNDS
687 if (indices_.at(
k.id()) == -1)
688 throw std::out_of_range(
"PropertyMap::at(): Key not found.");
690 return map_[indices_[
k.id()]].second;
695#ifdef VIGRA_CHECK_BOUNDS
696 if (indices_.at(
k.id()) == -1)
697 throw std::out_of_range(
"PropertyMap::at(): Key not found.");
699 return map_[indices_[
k.id()]].second;
704 return map_[indices_[
k.id()]].second;
709 return map_[indices_[
k.id()]].second;
715 throw std::out_of_range(
"PropertyMap::insert(): Key must not be negative.");
717 if (
k.id() >= indices_.
size())
718 indices_.resize(
k.id()+1, -1);
720 if (indices_[
k.id()] == -1)
722 indices_[
k.id()] = map_.size();
723 map_.push_back(value_type(
k, v));
732 const_iterator begin()
const
737 const_iterator cbegin()
const
747 const_iterator end()
const
752 const_iterator cend()
const
765 if (
k.id() < 0 ||
k.id() >= indices_.
size() || indices_[
k.id()] == -1)
768 return std::next(map_.begin(), indices_[
k.id()]);
771 const_iterator find(
key_type const &
k)
const
773 if (
k.id() < 0 ||
k.id() >= indices_.
size() || indices_[
k.id()] == -1)
776 return std::next(map_.begin(), indices_[
k.id()]);
786 if (
k.id() < 0 ||
k.id() >= indices_.
size() || indices_[
k.id()] == -1)
793 size_t ind = indices_[
k.id()];
794 indices_[
k.id()] = -1;
795 map_.erase(std::next(map_.begin(),
ind));
798 for (
size_t i = 0;
i < indices_.
size(); ++
i)
799 if (indices_[
i] >
ind)
807 std::vector<int> indices_;
The PropertyMap is used to store Node or Arc information of graphs.
Definition graphs.hxx:411
Class for a single RGB value.
Definition rgbvalue.hxx:128
size_type size() const
Definition tinyvector.hxx:913
bool operator<(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
less than
Definition fixedpoint.hxx:512