#include <tarjan_with_attr.hh>
Inheritance diagram for oln::topo::tarjan::abstract::tarjan_with_attr< Exact >:
Public Types | |
|
typedef oln::topo::tarjan::tarjan_traits< Exact >::input_type | input_type |
| Type of input image. | |
|
typedef mlc::exact< input_type >::ret::point_type | point_type |
| Point type of image to process. | |
|
typedef mlc::exact< input_type >::ret::value_type | data_type |
| Data type of the input image. | |
|
typedef oln::mute< input_type >::ret | image_type |
| Concrete type of the input image. | |
|
typedef oln::topo::tarjan::tarjan_traits< Exact >::output_type | image_out_type |
| Type of output image. | |
|
typedef oln::topo::tarjan::tarjan_traits< Exact >::attr_type | attr_type |
| Type of attribute to use. | |
|
typedef oln::morpho::attr::attr_traits< attr_type >::env_type | env_type |
| Environment associated to attribute type. | |
|
typedef mlc::exact< image_out_type >::ret::value_type | comp_type |
| Type of components. | |
|
typedef mlc::exact_vt< tarjan_with_attr< Exact >, Exact >::ret | exact_type |
| Exact type of the class. | |
| typedef tarjan< exact_type > | super_type |
| Type of parent class. | |
Public Member Functions | |
| const attr_type & | get_attr (const comp_type &i) const |
| Return the attribute value associated to a component i. | |
Protected Member Functions | |
| tarjan_with_attr (const image_type &ima, const env_type &env) | |
| Constructor. | |
| bool | is_proc_impl (const point_type &p) const |
| Implementation of is_proc(). | |
| comp_type | find_root (const comp_type &x) const |
| Implementation of find_root(). | |
| template<class N> image_out_type | get_compute_impl (const oln::abstract::neighborhood< N > &Ng) |
| Implementation of get_compute(). | |
| comp_type | ncomps_impl () const |
| Implementation of ncomps_impl(). | |
Protected Attributes | |
| unsigned | capacity_chunk |
| unsigned | capacity |
| const image_type & | input_ |
| std::vector< comp_type > | parent_ |
|
oln::mute< input_type, comp_type >::ret | to_comp_ |
| comp_type | ncomps_ |
|
std::vector< typename mlc::exact< image_out_type >::ret::value_type > | comp_value_ |
| std::vector< attr_type > | data_ |
| env_type | env_ |
| Exact | Exact type of the class. |
Definition at line 56 of file tarjan_with_attr.hh.
|
||||||||||||||||
|
Constructor. Initialization of data structures.
Definition at line 96 of file tarjan_with_attr.hh.
00097 :
00098 capacity_chunk((ima.npoints() < 100) ? ima.npoints() : (ima.npoints() / 100)),
00099 capacity(capacity_chunk),
00100 input_(ima),
00101 parent_(),
00102 to_comp_(ima.size()),
00103 comp_value_(),
00104 env_(env)
00105 {
00106 parent_.reserve(capacity);
00107 comp_value_.reserve(capacity);
00108 data_.reserve(capacity);
00109 }
|
|
||||||||||
|
Implementation of find_root().
Definition at line 132 of file tarjan_with_attr.hh. Referenced by oln::topo::tarjan::abstract::tarjan_with_attr< mlc::exact_vt< flat_zone< T, DestType, A, Exact >, Exact >::ret >::find_root(), oln::topo::tarjan::abstract::tarjan_with_attr< mlc::exact_vt< flat_zone< T, DestType, A, Exact >, Exact >::ret >::get_attr(), oln::topo::tarjan::abstract::tarjan_with_attr< mlc::exact_vt< flat_zone< T, DestType, A, Exact >, Exact >::ret >::get_compute_impl(), and oln::topo::tarjan::flat_zone< T, DestType, A, Exact >::uni_impl().
00133 {
00134 if (parent_[x] != x)
00135 return parent_[x] = find_root(parent_[x]);
00136 return x;
00137 }
|
|
||||||||||||||
|
Implementation of get_compute().
Definition at line 149 of file tarjan_with_attr.hh.
00150 {
00151 std::vector<point_type> I(get_processing_order());
00152
00153 level::fill(to_comp_, ntg_sup_val(comp_type));
00154 to_comp_.border_adapt_assign(Ng.delta(), ntg_sup_val(comp_type));
00155 ncomps_ = 0;
00156 parent_.push_back(0);
00157 comp_value_.push_back(0);
00158 data_.push_back(attr_type());
00159
00160 // We are ready to perform stuff
00161 for (unsigned int p = 0; p < I.size(); ++p)
00162 {
00163 point_type p_p = I[p];
00164 mark_set(p_p);
00165
00166 oln_neighb_type(N) Q_prime(Ng, p_p);
00167 for_all (Q_prime)
00168 if (is_proc(Q_prime))
00169 uni(Q_prime.cur(), p_p);
00170 if (to_comp_[p_p] == (ncomps_ + 1)) // new component
00171 ++ncomps_;
00172 else
00173 {
00174 comp_value_.pop_back();
00175 parent_.pop_back();
00176 data_.pop_back();
00177 }
00178 }
00179
00180 // Resolving phase
00181 std::map<comp_type, comp_type> cmps;
00182 ncomps_ = 0;
00183 for (int p = I.size() - 1; p >= 0; --p)
00184 {
00185 point_type p_p = I[p];
00186 if (cmps.find(find_root(to_comp_[p_p])) == cmps.end())
00187 {
00188 cmps[comp_value_[find_root(to_comp_[p_p])]] = ncomps_;
00189 comp_value_[find_root(to_comp_[p_p])] = ncomps_++;
00190 }
00191 }
00192
00193 image_out_type output(input_.size());
00194 for (int p = I.size() - 1; p >= 0; --p)
00195 {
00196 point_type p_p = I[p];
00197 output[p_p] = comp_value_[find_root(to_comp_[p_p])];
00198 }
00199 return output;
00200 }
|
|
||||||||||
|
Implementation of is_proc().
Definition at line 118 of file tarjan_with_attr.hh.
00119 {
00120 return to_comp_[p] != ntg_sup_val(comp_type);
00121 };
|
|
|||||||||
|
Implementation of ncomps_impl().
Definition at line 207 of file tarjan_with_attr.hh.
00208 {
00209 return ncomps_;
00210 }
|
1.3.6-20040222