ACloudViewer  3.9.4
A Modern Library for 3D Data Processing
CutPursuit_SPG.h
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------
2 // - CloudViewer: www.cloudViewer.org -
3 // ----------------------------------------------------------------------------
4 // Copyright (c) 2018-2024 www.cloudViewer.org
5 // SPDX-License-Identifier: MIT
6 // ----------------------------------------------------------------------------
7 
8 #pragma once
9 
10 #include "CutPursuit.h"
11 
12 namespace CP {
13 template <typename T>
14 struct CutPursuit_SPG : public CutPursuit<T> {
15  //=============================================================================================
16  //============================= COMPUTE ENERGY
17  //===========================================
18  //=============================================================================================
19  std::pair<T, T> compute_energy() override {
20  VertexAttributeMap<T> vertex_attribute_map =
21  boost::get(boost::vertex_bundle, this->main_graph);
22  EdgeAttributeMap<T> edge_attribute_map =
23  boost::get(boost::edge_bundle, this->main_graph);
24  // the first element pair_energy of is the fidelity and the second the
25  // penalty
26  std::pair<T, T> pair_energy;
27  T energy = 0;
28  // #pragma omp parallel for private(i_dim) if (this->parameter.parallel)
29  // schedule(static) reduction(+:energy,i)
30  for (uint32_t ind_ver = 0; ind_ver < this->nVertex; ind_ver++) {
31  VertexDescriptor<T> i_ver =
32  boost::vertex(ind_ver, this->main_graph);
33  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
34  energy += .5 * vertex_attribute_map(i_ver).weight *
35  pow(vertex_attribute_map(i_ver).observation[i_dim] -
36  vertex_attribute_map(i_ver).value[i_dim],
37  2);
38  }
39  }
40  pair_energy.first = energy;
41  energy = 0;
42  EdgeIterator<T> i_edg,
43  i_edg_end = boost::edges(this->main_graph).second;
44  for (i_edg = boost::edges(this->main_graph).first; i_edg != i_edg_end;
45  ++i_edg) {
46  if (!edge_attribute_map(*i_edg).realEdge) {
47  continue;
48  }
49  energy += .5 * edge_attribute_map(*i_edg).isActive *
50  this->parameter.reg_strenth *
51  edge_attribute_map(*i_edg).weight;
52  }
53  pair_energy.second = energy;
54  return pair_energy;
55  }
56 
57  //=============================================================================================
58  //============================= SPLIT
59  //===========================================
60  //=============================================================================================
61  size_t split()
62  override { // split the graph by trying to find the best binary
63  // partition each components is split into B and notB
64  // for each components we associate the value h_1 and
65  // h_2 to vertices in B or notB the affectation as well
66  // as h_1 and h_2 are computed alternatively
67  // tic();
68  //--------loading
69  // structures---------------------------------------------------------------
70  uint32_t nb_comp = static_cast<uint32_t>(this->components.size());
71  VertexAttributeMap<T> vertex_attribute_map =
72  boost::get(boost::vertex_bundle, this->main_graph);
73  VertexIndexMap<T> vertex_index_map =
74  boost::get(boost::vertex_index, this->main_graph);
75  // stores wether each vertex is B or not
76  std::vector<bool> binary_label(this->nVertex);
77  // initialize the binary partition with kmeans
78  this->init_labels(binary_label, true);
79 
80  // centers is the value of each binary component in the optimal
81  // partition
82  VectorOfCentroids<T> centers(nb_comp, this->dim);
83  //-----main
84  // loop----------------------------------------------------------------
85 
86  // the optimal flow is iteratively approximated
87  T unary_weight = pow(this->parameter.weight_decay,
88  -float(this->parameter.flow_steps));
89  for (uint32_t i_step = 0; i_step < this->parameter.flow_steps;
90  i_step++) {
91  unary_weight = unary_weight * this->parameter.weight_decay;
92 
93  // the regularization strength at this step
94  // compute h_1 and h_2
95  centers = VectorOfCentroids<T>(nb_comp, this->dim);
96  this->compute_centers(centers, nb_comp, binary_label);
97  this->set_capacities(centers, unary_weight);
98 
99  // update the capacities of the flow graph
100  boost::boykov_kolmogorov_max_flow(
101  this->main_graph,
102  get(&EdgeAttribute<T>::capacity, this->main_graph),
103  get(&EdgeAttribute<T>::residualCapacity, this->main_graph),
104  get(&EdgeAttribute<T>::edge_reverse, this->main_graph),
105  get(&VertexAttribute<T>::color, this->main_graph),
106  get(boost::vertex_index, this->main_graph), this->source,
107  this->sink);
108 
109  for (uint32_t ind_com = 0; ind_com < nb_comp; ind_com++) {
110  if (this->saturated_components[ind_com]) {
111  continue;
112  }
113 
114  for (uint32_t i_ver = 0;
115  i_ver < this->components[ind_com].size(); i_ver++) {
116  binary_label[vertex_index_map(
117  this->components[ind_com][i_ver])] =
118  (vertex_attribute_map(
119  this->components[ind_com][i_ver])
120  .color ==
121  vertex_attribute_map(this->sink).color);
122  }
123  }
124  }
125  size_t saturation = this->activate_edges(false);
126  return saturation;
127  }
128 
129  //=============================================================================================
130  //============================= INIT_L2 ======
131  //===========================================
132  //=============================================================================================
133  inline void init_labels(
134  std::vector<bool>& binary_label,
135  bool spatial_part) { //-----initialize the labelling for each
136  // components with
137  // kmeans------------------------------
138  VertexAttributeMap<T> vertex_attribute_map =
139  boost::get(boost::vertex_bundle, this->main_graph);
140  VertexIndexMap<T> vertex_index_map =
141  boost::get(boost::vertex_index, this->main_graph);
142  uint32_t nb_comp = static_cast<uint32_t>(this->components.size());
143  // ind_com;
144  // #pragma omp parallel for private(ind_com) //if (nb_comp>=8)
145  // schedule(dynamic)
146  uint32_t dim_spat = spatial_part ? this->dim - 0 : this->dim;
147 
148 #ifdef OPENMP
149 #pragma omp parallel for if (nb_comp >= omp_get_num_threads()) schedule(dynamic)
150 #endif
151  for (uint32_t ind_com = 0; ind_com < nb_comp; ind_com++) {
152  std::vector<std::vector<T>> kernels(2, std::vector<T>(this->dim));
153  T total_weight[2];
154  T best_energy;
155  T current_energy;
156  uint32_t comp_size =
157  static_cast<uint32_t>(this->components[ind_com].size());
158  std::vector<bool> potential_label(comp_size);
159  std::vector<T> energy_array(comp_size);
160  if (this->saturated_components[ind_com] || comp_size <= 1) {
161  continue;
162  }
163  for (uint32_t init_kmeans = 0;
164  init_kmeans < this->parameter.kmeans_resampling;
165  init_kmeans++) { // proceed to several initilialisation of
166  // kmeans and pick up the best one
167  //----- initialization with KM++ ------------------
168  uint32_t first_kernel = std::rand() % comp_size,
169  second_kernel = 0; // first kernel attributed
170  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
171  kernels[0][i_dim] =
172  vertex_attribute_map(
173  this->components[ind_com][first_kernel])
174  .observation[i_dim];
175  }
176  best_energy = 0; // now compute the square distance of each
177  // vertex to this kernel
178 #ifdef OPENMP
179 #pragma omp parallel for if (nb_comp < omp_get_num_threads()) \
180  shared(best_energy) schedule(static)
181 #endif
182  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
183  energy_array[i_ver] = 0;
184  for (uint32_t i_dim = 0; i_dim < dim_spat; i_dim++) {
185  energy_array[i_ver] +=
186  pow(vertex_attribute_map(
187  this->components[ind_com][i_ver])
188  .observation[i_dim] -
189  kernels[0][i_dim],
190  2) *
191  vertex_attribute_map(
192  this->components[ind_com][i_ver])
193  .weight;
194  }
195  best_energy += energy_array[i_ver];
196  } // we now generate a random number to determinate which node
197  // will be the second kernel
198  T random_sample = ((T)(rand())) / ((T)(RAND_MAX));
199  current_energy = best_energy * random_sample;
200  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
201  current_energy -= energy_array[i_ver];
202  if (current_energy <
203  0) { // we have selected the second kernel
204  second_kernel = i_ver;
205  break;
206  }
207  }
208  for (uint32_t i_dim = 0; i_dim < this->dim;
209  i_dim++) { // now fill the second kernel
210  kernels[1][i_dim] =
211  vertex_attribute_map(
212  this->components[ind_com][second_kernel])
213  .observation[i_dim];
214  }
215  //----main kmeans loop-----
216  for (uint32_t ite_kmeans = 0;
217  ite_kmeans < this->parameter.kmeans_ite; ite_kmeans++) {
218  //--affectation step: associate each node with its closest
219  // kernel-------------------
220 #ifdef OPENMP
221 #pragma omp parallel for if (nb_comp < omp_get_num_threads()) \
222  shared(potential_label) schedule(static)
223 #endif
224  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
225  std::vector<T> distance_kernels(2);
226  for (uint32_t i_dim = 0; i_dim < dim_spat; i_dim++) {
227  distance_kernels[0] += pow(
228  vertex_attribute_map(
229  this->components[ind_com][i_ver])
230  .observation[i_dim] -
231  kernels[0][i_dim],
232  2);
233  distance_kernels[1] += pow(
234  vertex_attribute_map(
235  this->components[ind_com][i_ver])
236  .observation[i_dim] -
237  kernels[1][i_dim],
238  2);
239  }
240  potential_label[i_ver] =
241  distance_kernels[0] > distance_kernels[1];
242  }
243  //-----computation of the new
244  // kernels----------------------------
245  total_weight[0] = 0.;
246  total_weight[1] = 0.;
247  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
248  kernels[0][i_dim] = 0;
249  kernels[1][i_dim] = 0;
250  }
251 #ifdef OPENMP
252 #pragma omp parallel for if (nb_comp < omp_get_num_threads()) \
253  shared(potential_label) schedule(static)
254 #endif
255  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
256  if (vertex_attribute_map(
257  this->components[ind_com][i_ver])
258  .weight == 0) {
259  continue;
260  }
261  if (potential_label[i_ver]) {
262  total_weight[0] +=
263  vertex_attribute_map(
264  this->components[ind_com][i_ver])
265  .weight;
266  for (uint32_t i_dim = 0; i_dim < this->dim;
267  i_dim++) {
268  kernels[0][i_dim] +=
269  vertex_attribute_map(
270  this->components[ind_com]
271  [i_ver])
272  .observation[i_dim] *
273  vertex_attribute_map(
274  this->components[ind_com]
275  [i_ver])
276  .weight;
277  }
278  } else {
279  total_weight[1] +=
280  vertex_attribute_map(
281  this->components[ind_com][i_ver])
282  .weight;
283  for (uint32_t i_dim = 0; i_dim < this->dim;
284  i_dim++) {
285  kernels[1][i_dim] +=
286  vertex_attribute_map(
287  this->components[ind_com]
288  [i_ver])
289  .observation[i_dim] *
290  vertex_attribute_map(
291  this->components[ind_com]
292  [i_ver])
293  .weight;
294  }
295  }
296  }
297 
298  if ((total_weight[0] == 0) || (total_weight[1] == 0)) {
299  break;
300  }
301  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
302  kernels[0][i_dim] = kernels[0][i_dim] / total_weight[0];
303  kernels[1][i_dim] = kernels[1][i_dim] / total_weight[1];
304  }
305  }
306  //----compute the associated energy ------
307  current_energy = 0;
308 #ifdef OPENMP
309 #pragma omp parallel for if (nb_comp < omp_get_num_threads()) \
310  shared(potential_label) schedule(static)
311 #endif
312  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
313  for (uint32_t i_dim = 0; i_dim < dim_spat; i_dim++) {
314  if (potential_label[i_ver]) {
315  current_energy +=
316  pow(vertex_attribute_map(
317  this->components[ind_com]
318  [i_ver])
319  .observation[i_dim] -
320  kernels[0][i_dim],
321  2) *
322  vertex_attribute_map(
323  this->components[ind_com][i_ver])
324  .weight;
325  } else {
326  current_energy +=
327  pow(vertex_attribute_map(
328  this->components[ind_com]
329  [i_ver])
330  .observation[i_dim] -
331  kernels[1][i_dim],
332  2) *
333  vertex_attribute_map(
334  this->components[ind_com][i_ver])
335  .weight;
336  }
337  }
338  }
339  if (current_energy < best_energy) {
340  best_energy = current_energy;
341  for (uint32_t i_ver = 0; i_ver < comp_size; i_ver++) {
342  binary_label[vertex_index_map(
343  this->components[ind_com][i_ver])] =
344  potential_label[i_ver];
345  }
346  }
347  }
348  }
349  }
350 
351  //=============================================================================================
352  //============================= COMPUTE_CENTERS_L2
353  //==========================================
354  //=============================================================================================
355  inline void compute_centers(VectorOfCentroids<T>& centers,
356  const uint32_t& nb_comp,
357  const std::vector<bool>& binary_label) {
358  // compute for each component the values of h_1 and h_2
359 #ifdef OPENMP
360 #pragma omp parallel for if (nb_comp >= omp_get_num_threads()) schedule(dynamic)
361 #endif
362  for (uint32_t ind_com = 0; ind_com < nb_comp; ind_com++) {
363  if (this->saturated_components[ind_com]) {
364  continue;
365  }
366  compute_center(centers.centroids[ind_com], ind_com, binary_label);
367  }
368  }
369 
370  //=============================================================================================
371  //============================= COMPUTE_CENTER_L2
372  //==========================================
373  //=============================================================================================
374  inline void compute_center(std::vector<std::vector<T>>& center,
375  const uint32_t& ind_com,
376  const std::vector<bool>& binary_label) {
377  // compute for each component the values of the centroids corresponding
378  // to the optimal binary partition
379  VertexAttributeMap<T> vertex_attribute_map =
380  boost::get(boost::vertex_bundle, this->main_graph);
381  VertexIndexMap<T> vertex_index_map =
382  boost::get(boost::vertex_index, this->main_graph);
383  T total_weight[2];
384  total_weight[0] = 0.;
385  total_weight[1] = 0.;
386 
387  // #pragma omp parallel for if (this->parameter.parallel)
388  for (uint32_t i_ver = 0; i_ver < this->components[ind_com].size();
389  i_ver++) {
390  if (vertex_attribute_map(this->components[ind_com][i_ver]).weight ==
391  0) {
392  continue;
393  }
394  if (binary_label[vertex_index_map(
395  this->components[ind_com][i_ver])]) {
396  total_weight[0] +=
397  vertex_attribute_map(this->components[ind_com][i_ver])
398  .weight;
399  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
400  center[0][i_dim] +=
401  vertex_attribute_map(
402  this->components[ind_com][i_ver])
403  .observation[i_dim] *
404  vertex_attribute_map(
405  this->components[ind_com][i_ver])
406  .weight;
407  }
408  } else {
409  total_weight[1] +=
410  vertex_attribute_map(this->components[ind_com][i_ver])
411  .weight;
412  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
413  center[1][i_dim] +=
414  vertex_attribute_map(
415  this->components[ind_com][i_ver])
416  .observation[i_dim] *
417  vertex_attribute_map(
418  this->components[ind_com][i_ver])
419  .weight;
420  }
421  }
422  }
423  if ((total_weight[0] == 0) || (total_weight[1] == 0)) {
424  // the component is saturated
425  // this->saturateComponent(ind_com, false);
426  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
427  center[0][i_dim] =
428  vertex_attribute_map(this->components[ind_com][0])
429  .value[i_dim];
430  center[1][i_dim] =
431  vertex_attribute_map(this->components[ind_com][0])
432  .value[i_dim];
433  }
434  } else {
435  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
436  center[0][i_dim] = center[0][i_dim] / total_weight[0];
437  center[1][i_dim] = center[1][i_dim] / total_weight[1];
438  }
439  }
440  }
441 
442  //=============================================================================================
443  //============================= SET_CAPACITIES
444  //==========================================
445  //=============================================================================================
446  inline void set_capacities(const VectorOfCentroids<T>& centers,
447  T unary_weight) {
448  VertexAttributeMap<T> vertex_attribute_map =
449  boost::get(boost::vertex_bundle, this->main_graph);
450  EdgeAttributeMap<T> edge_attribute_map =
451  boost::get(boost::edge_bundle, this->main_graph);
452  //----first compute the capacity in sink/node
453  // edges------------------------------------ #pragma omp parallel for if
454  //(this->parameter.parallel) schedule(dynamic)
455  uint32_t nb_comp = static_cast<uint32_t>(this->components.size());
456 #ifdef OPENMP
457 #pragma omp parallel for if (nb_comp >= omp_get_num_threads()) schedule(dynamic)
458 #endif
459  for (uint32_t ind_com = 0; ind_com < nb_comp; ind_com++) {
460  VertexDescriptor<T> desc_v;
461  EdgeDescriptor desc_source2v, desc_v2sink, desc_v2source;
462  T cost_B, cost_notB; // the cost of being in B or not B, local for
463  // each component
464  if (this->saturated_components[ind_com]) {
465  continue;
466  }
467  for (uint32_t i_ver = 0; i_ver < this->components[ind_com].size();
468  i_ver++) {
469  desc_v = this->components[ind_com][i_ver];
470  // because of the adjacency structure NEVER access edge
471  // (source,v) directly!
472  desc_v2source =
473  boost::edge(desc_v, this->source, this->main_graph)
474  .first;
475  desc_source2v =
476  edge_attribute_map(desc_v2source)
477  .edge_reverse; // use edge_reverse instead
478  desc_v2sink =
479  boost::edge(desc_v, this->sink, this->main_graph).first;
480  cost_B = 0;
481  cost_notB = 0;
482  if (vertex_attribute_map(desc_v).weight ==
483  0) { // no observation - no cut
484  edge_attribute_map(desc_source2v).capacity = 0;
485  edge_attribute_map(desc_v2sink).capacity = 0;
486  continue;
487  }
488  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
489  cost_B += 0.5 * vertex_attribute_map(desc_v).weight *
490  (pow(centers.centroids[ind_com][0][i_dim], 2) -
491  2 * (centers.centroids[ind_com][0][i_dim] *
492  vertex_attribute_map(desc_v)
493  .observation[i_dim]));
494  cost_notB += 0.5 * vertex_attribute_map(desc_v).weight *
495  (pow(centers.centroids[ind_com][1][i_dim], 2) -
496  2 * (centers.centroids[ind_com][1][i_dim] *
497  vertex_attribute_map(desc_v)
498  .observation[i_dim]));
499  }
500  if (cost_B > cost_notB) {
501  edge_attribute_map(desc_source2v).capacity =
502  (cost_B - cost_notB);
503  edge_attribute_map(desc_v2sink).capacity = 0.;
504  } else {
505  edge_attribute_map(desc_source2v).capacity = 0.;
506  edge_attribute_map(desc_v2sink).capacity =
507  (cost_notB - cost_B);
508  }
509  }
510  }
511  //----then set the vertex to vertex edges
512  //---------------------------------------------
513  EdgeIterator<T> i_edg, i_edg_end;
514  for (boost::tie(i_edg, i_edg_end) = boost::edges(this->main_graph);
515  i_edg != i_edg_end; ++i_edg) {
516  if (!edge_attribute_map(*i_edg).realEdge) {
517  continue;
518  }
519  if (!edge_attribute_map(*i_edg).isActive) {
520  edge_attribute_map(*i_edg).capacity =
521  edge_attribute_map(*i_edg).weight *
522  this->parameter.reg_strenth / unary_weight;
523  } else {
524  edge_attribute_map(*i_edg).capacity = 0;
525  }
526  }
527  }
528 
529  //=============================================================================================
530  //================================= COMPUTE_VALUE
531  //=========================================
532  //=============================================================================================
533  std::pair<std::vector<T>, T> compute_value(
534  const uint32_t& ind_com) override {
535  VertexAttributeMap<T> vertex_attribute_map =
536  boost::get(boost::vertex_bundle, this->main_graph);
537  T total_weight = 0;
538  std::vector<T> compValue(this->dim);
539  std::fill((compValue.begin()), (compValue.end()), 0);
540 #ifdef OPENMP
541 #pragma omp parallel for if (this->parameter.parallel) schedule(static)
542 #endif
543  for (uint32_t ind_ver = 0; ind_ver < this->components[ind_com].size();
544  ++ind_ver) {
545  total_weight +=
546  vertex_attribute_map(this->components[ind_com][ind_ver])
547  .weight;
548  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
549  compValue[i_dim] +=
550  vertex_attribute_map(this->components[ind_com][ind_ver])
551  .observation[i_dim] *
552  vertex_attribute_map(this->components[ind_com][ind_ver])
553  .weight;
554  }
555  vertex_attribute_map(this->components[ind_com][ind_ver])
556  .in_component = ind_com;
557  }
558  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
559  compValue[i_dim] = compValue[i_dim] / total_weight;
560  }
561  for (uint32_t ind_ver = 0; ind_ver < this->components[ind_com].size();
562  ++ind_ver) {
563  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
564  vertex_attribute_map(this->components[ind_com][ind_ver])
565  .value[i_dim] = compValue[i_dim];
566  }
567  }
568  return std::pair<std::vector<T>, T>(compValue, total_weight);
569  }
570 
571  //=============================================================================================
572  //================================= COMPUTE_MERGE_GAIN
573  //=========================================
574  //=============================================================================================
575  std::pair<std::vector<T>, T> compute_merge_gain(
576  const VertexDescriptor<T>& comp1,
577  const VertexDescriptor<T>& comp2) override {
578  VertexAttributeMap<T> reduced_vertex_attribute_map =
579  boost::get(boost::vertex_bundle, this->reduced_graph);
580  std::vector<T> merge_value(this->dim);
581  T gain = 0;
582  // compute the value obtained by mergeing the two connected components
583  for (uint32_t i_dim = 0; i_dim < this->dim; i_dim++) {
584  merge_value[i_dim] =
585  (reduced_vertex_attribute_map(comp1).weight *
586  reduced_vertex_attribute_map(comp1).value[i_dim] +
587  reduced_vertex_attribute_map(comp2).weight *
588  reduced_vertex_attribute_map(comp2).value[i_dim]) /
589  (reduced_vertex_attribute_map(comp1).weight +
590  reduced_vertex_attribute_map(comp2).weight);
591  gain += 0.5 *
592  (pow(merge_value[i_dim], 2) *
593  (reduced_vertex_attribute_map(comp1).weight +
594  reduced_vertex_attribute_map(comp2).weight) -
595  pow(reduced_vertex_attribute_map(comp1).value[i_dim], 2) *
596  reduced_vertex_attribute_map(comp1).weight -
597  pow(reduced_vertex_attribute_map(comp2).value[i_dim], 2) *
598  reduced_vertex_attribute_map(comp2).weight);
599  }
600  return std::pair<std::vector<T>, T>(merge_value, gain);
601  }
602 };
603 } // namespace CP
vertex_index
long vertex_index
Definition: FileIOFactory.cpp:47
VectorOfCentroids::centroids
std::vector< std::vector< std::vector< T > > > centroids
Definition: Common.h:109
CP
Definition: API.h:123
CP::VertexAttributeMap
boost::vec_adj_list_vertex_property_map< Graph< T >, Graph< T > *, VertexAttribute< T >, VertexAttribute< T > &, boost::vertex_bundle_t > VertexAttributeMap
Definition: Graph.h:92
CP::EdgeIterator
typename boost::graph_traits< Graph< T > >::edge_iterator EdgeIterator
Definition: Graph.h:84
CP::EdgeDescriptor
boost::graph_traits< boost::adjacency_list< boost::vecS, boost::vecS, boost::directedS > >::edge_descriptor EdgeDescriptor
Definition: Graph.h:22
CP::VertexDescriptor
typename boost::graph_traits< CP::Graph< T > >::vertex_descriptor VertexDescriptor
Definition: Graph.h:75
CP::VertexIndexMap
typename boost::property_map< Graph< T >, boost::vertex_index_t >::type VertexIndexMap
Definition: Graph.h:103
CP::EdgeAttributeMap
boost::adj_list_edge_property_map< boost::directed_tag, EdgeAttribute< T >, EdgeAttribute< T > &, uint64_t, CP::EdgeAttribute< T >, boost::edge_bundle_t > EdgeAttributeMap
Definition: Graph.h:100
flann::random_sample
Matrix< T > random_sample(Matrix< T > &srcMatrix, size_t size, bool remove=false)
Definition: sampling.h:40
CP::CutPursuit_SPG
Definition: CutPursuit_SPG.h:14
CP::CutPursuit_SPG::init_labels
void init_labels(std::vector< bool > &binary_label, bool spatial_part)
Definition: CutPursuit_SPG.h:133
CP::CutPursuit_SPG::compute_centers
void compute_centers(VectorOfCentroids< T > &centers, const uint32_t &nb_comp, const std::vector< bool > &binary_label)
Definition: CutPursuit_SPG.h:355
CP::CutPursuit_SPG::compute_center
void compute_center(std::vector< std::vector< T >> &center, const uint32_t &ind_com, const std::vector< bool > &binary_label)
Definition: CutPursuit_SPG.h:374
CP::CutPursuit_SPG::compute_energy
std::pair< T, T > compute_energy() override
Definition: CutPursuit_SPG.h:19
CP::CutPursuit_SPG::set_capacities
void set_capacities(const VectorOfCentroids< T > &centers, T unary_weight)
Definition: CutPursuit_SPG.h:446
CP::CutPursuit_SPG::compute_merge_gain
std::pair< std::vector< T >, T > compute_merge_gain(const VertexDescriptor< T > &comp1, const VertexDescriptor< T > &comp2) override
Definition: CutPursuit_SPG.h:575
CP::CutPursuit_SPG::compute_value
std::pair< std::vector< T >, T > compute_value(const uint32_t &ind_com) override
Definition: CutPursuit_SPG.h:533
CP::CutPursuit_SPG::split
size_t split() override
Definition: CutPursuit_SPG.h:61
CP::CutPursuit::parameter
CPparameter< T > parameter
Definition: CutPursuit.h:65
CP::CutPursuit::main_graph
Graph< T > main_graph
Definition: CutPursuit.h:45
CP::CutPursuit::components
std::vector< std::vector< VertexDescriptor< T > > > components
Definition: CutPursuit.h:49
CP::CutPursuit::sink
VertexDescriptor< T > sink
Definition: CutPursuit.h:58
CP::CutPursuit::source
VertexDescriptor< T > source
Definition: CutPursuit.h:57
CP::CutPursuit::activate_edges
size_t activate_edges(bool allows_saturation=true)
Definition: CutPursuit.h:298
CP::CutPursuit::dim
uint32_t dim
Definition: CutPursuit.h:59
CP::CutPursuit::nVertex
uint32_t nVertex
Definition: CutPursuit.h:60
CP::CutPursuit::saturated_components
std::vector< bool > saturated_components
Definition: CutPursuit.h:53
CP::CutPursuit::reduced_graph
Graph< T > reduced_graph
Definition: CutPursuit.h:46