00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef MLN_UTIL_ADJACENCY_MATRIX_HH
00027 # define MLN_UTIL_ADJACENCY_MATRIX_HH
00028
00038
00039 # include <mln/core/image/image2d.hh>
00040 # include <mln/util/set.hh>
00041 # include <mln/util/ord_pair.hh>
00042 # include <mln/trait/value_.hh>
00043 # include <mln/metal/converts_to.hh>
00044 # include <mln/debug/println.hh>
00045
00046
00047 namespace mln
00048 {
00049
00050 namespace util
00051 {
00052
00053 namespace internal
00054 {
00055
00056
00057
00058 template <typename V, typename Q>
00059 struct adjacency_matrix_impl_selector
00060 {
00062 typedef image2d<bool> adj_t;
00063
00065 adjacency_matrix_impl_selector(const V& nelements);
00066
00068 void add(const V& e1, const V& e2);
00069
00071 void remove(const V& e1, const V& e2);
00072
00074 void clear();
00075
00077 bool are_adjacent(const V& e1, const V& e2) const;
00078
00080 std::ostream& print_data_(std::ostream& ostr) const;
00081
00082 protected:
00083 adj_t adj_;
00084 };
00085
00086
00087
00088
00089 template <typename V>
00090 struct adjacency_matrix_impl_selector<V, metal::bool_<false> >
00091 {
00093 typedef util::set< util::ord_pair<V> > adj_t;
00094
00096 adjacency_matrix_impl_selector(const V& nelements);
00097
00099 void add(const V& e1, const V& e2);
00100
00102 void remove(const V& e1, const V& e2);
00103
00105 void clear();
00106
00108 bool are_adjacent(const V& e1, const V& e2) const;
00109
00111 std::ostream& print_data_(std::ostream& ostr) const;
00112
00113 protected:
00114 adj_t adj_;
00115
00116 # ifndef NDEBUG
00117 unsigned nelements_;
00118 # endif // ! NDEBUG
00119 };
00120
00121
00122 }
00123
00124
00134
00135 template <typename V = def::coord>
00136 class adjacency_matrix
00137 : private mlc_converts_to(V,unsigned)::check_t,
00138 public internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval>
00139 {
00140 typedef internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval>
00141 impl_t;
00142
00143 typedef typename impl_t::adj_t adj_t;
00144
00145 public:
00150 adjacency_matrix();
00153 adjacency_matrix(const V& nelements);
00156
00158 const adj_t& hook_data_() const;
00159 };
00160
00161
00162
00163
00164 template <typename V>
00165 std::ostream&
00166 operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj);
00167
00168
00169
00170 # ifndef MLN_INCLUDE_ONLY
00171
00172
00173 namespace internal
00174 {
00175
00176
00177
00178 template <typename V, typename Q>
00179 adjacency_matrix_impl_selector<V, Q>::adjacency_matrix_impl_selector(const V& nelements)
00180 : adj_(nelements, nelements)
00181 {
00182 clear();
00183 }
00184
00185 template <typename V, typename Q>
00186 void
00187 adjacency_matrix_impl_selector<V, Q>::add(const V& e1, const V& e2)
00188 {
00189 mln_precondition(adj_.is_valid());
00190 mln_precondition(e1 < adj_.nrows());
00191 mln_precondition(e2 < adj_.nrows());
00192
00193 if (e1 > e2)
00194 opt::at(adj_, e2, e1) = true;
00195 else
00196 opt::at(adj_, e1, e2) = true;
00197 }
00198
00199 template <typename V, typename Q>
00200 void
00201 adjacency_matrix_impl_selector<V, Q>::remove(const V& e1, const V& e2)
00202 {
00203 mln_precondition(adj_.is_valid());
00204 mln_precondition(e1 < adj_.nrows());
00205 mln_precondition(e2 < adj_.nrows());
00206
00207 if (e1 > e2)
00208 opt::at(adj_, e2, e1) = false;
00209 else
00210 opt::at(adj_, e1, e2) = false;
00211 }
00212
00213 template <typename V, typename Q>
00214 void
00215 adjacency_matrix_impl_selector<V, Q>::clear()
00216 {
00217 mln_precondition(adj_.is_valid());
00218 data::fill(adj_, false);
00219 }
00220
00221 template <typename V, typename Q>
00222 bool
00223 adjacency_matrix_impl_selector<V, Q>::are_adjacent(const V& e1,
00224 const V& e2) const
00225 {
00226 mln_precondition(adj_.is_valid());
00227 mln_precondition(e1 < adj_.nrows());
00228 mln_precondition(e2 < adj_.nrows());
00229
00230 if (e1 > e2)
00231 return opt::at(adj_, e2, e1);
00232 return opt::at(adj_, e1, e2);
00233 }
00234
00235 template <typename V, typename Q>
00236 std::ostream&
00237 adjacency_matrix_impl_selector<V, Q>::print_data_(std::ostream& ostr) const
00238 {
00239 mln_precondition(adj_.is_valid());
00240 debug::println(adj_);
00241 return ostr;
00242 }
00243
00244
00245
00246
00247
00248
00249 template <typename V>
00250 adjacency_matrix_impl_selector<V, metal::bool_<false> >
00251 ::adjacency_matrix_impl_selector(const V& nelements)
00252 {
00253 (void) nelements;
00254 # ifndef NDEBUG
00255 nelements_ = nelements;
00256 # endif // ! NDEBUG
00257 }
00258
00259 template <typename V>
00260 void
00261 adjacency_matrix_impl_selector<V, metal::bool_<false> >
00262 ::add(const V& e1, const V& e2)
00263 {
00264 mln_precondition(int(e1) < int(nelements_));
00265 mln_precondition(int(e2) < int(nelements_));
00266 adj_.insert(make::ord_pair(e1, e2));
00267 }
00268
00269 template <typename V>
00270 void
00271 adjacency_matrix_impl_selector<V, metal::bool_<false> >
00272 ::remove(const V& e1, const V& e2)
00273 {
00274 mln_precondition(int(e1) < int(nelements_));
00275 mln_precondition(int(e2) < int(nelements_));
00276 mln_precondition(adj_.has(make::ord_pair(e1, e2)));
00277 adj_.remove(make::ord_pair(e1, e2));
00278 }
00279
00280 template <typename V>
00281 void
00282 adjacency_matrix_impl_selector<V, metal::bool_<false> >::clear()
00283 {
00284 adj_.clear();
00285 }
00286
00287 template <typename V>
00288 bool
00289 adjacency_matrix_impl_selector<V, metal::bool_<false> >
00290 ::are_adjacent(const V& e1, const V& e2) const
00291 {
00292 mln_precondition(int(e1) < int(nelements_));
00293 mln_precondition(int(e2) < int(nelements_));
00294 return adj_.has(make::ord_pair(e1, e2));
00295 }
00296
00297 template <typename V>
00298 std::ostream&
00299 adjacency_matrix_impl_selector<V, metal::bool_<false> >::print_data_(std::ostream& ostr) const
00300 {
00301 return ostr << adj_;
00302 }
00303
00304 }
00305
00306
00307 template <typename V>
00308 adjacency_matrix<V>::adjacency_matrix()
00309 : impl_t()
00310 {
00311 }
00312
00313
00314 template <typename V>
00315 adjacency_matrix<V>::adjacency_matrix(const V& nelements)
00316 : impl_t(nelements)
00317 {
00318 }
00319
00320
00321 template <typename V>
00322 std::ostream&
00323 operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj)
00324 {
00325 return adj.print_data_(ostr);
00326 }
00327
00328
00329 # endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH
00330
00331 }
00332
00333 }
00334
00335
00336 #endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH