Cheetah - SKA - PSS - Prototype Time Domain Search Pipeline
Public Member Functions | List of all members
ska::cheetah::sps_clustering::Fof Class Reference

Friend Of Friends Clustering Algorithm for SpCandidates. More...

#include <cheetah/sps_clustering/Fof.h>

Collaboration diagram for ska::cheetah::sps_clustering::Fof:
Collaboration graph

Public Member Functions

 Fof (Config const &config)
 
void linking_length (double const &l)
 
double linking_length () const
 
template<typename NumRepType >
std::vector< std::vector< size_t > > operator() (data::SpCcl< NumRepType > const &cands)
 Group the candidates using the fof algorithm. More...
 

Detailed Description

Friend Of Friends Clustering Algorithm for SpCandidates.

Definition at line 42 of file Fof.h.

Member Function Documentation

◆ operator()()

template<typename NumRepType >
std::vector< std::vector< size_t > > ska::cheetah::sps_clustering::Fof::operator() ( data::SpCcl< NumRepType > const &  cands)

Group the candidates using the fof algorithm.

Returns
a vector containing the groups of candidates. each group is represented as a vector of indices for the candidatate in the input data.

Definition at line 100 of file Fof.cpp.

101 {
102  //auto start = std::chrono::high_resolution_clock::now();
103  std::vector<std::vector<size_t>> groups;
104 
105  typedef std::pair<PointType, size_t> ValueType;
106  typedef bgi::rtree<ValueType, bgi::linear<16>> Tree;
107 
108  std::vector< std::pair<PointType, size_t> > points;
109  points.reserve(cands.size());
110 
111  typedef typename data::SpCcl<NumRepType>::Dm Dm;
112  std::pair<Dm, Dm> dm_range = cands.dm_range();
113  Dm dm_step=(dm_range.second - dm_range.first)/static_cast<typename Dm::value_type>(std::numeric_limits<std::size_t>::max());
114  if (dm_step == 0 * pss::astrotypes::units::parsecs_per_cube_cm)
115  dm_step = (1.0 * pss::astrotypes::units::parsecs_per_cube_cm );
116 
117  if(cands.tf_blocks().size() == 0 || cands.size() == 0 ) return groups;
118 
119  auto tsamp = static_cast<boost::units::quantity<data::MilliSeconds,double>>(((*(cands.tf_blocks().begin()))->sample_interval())).value();
120  // set up a point in the clustering search space for each candidate
121  for(size_t i = 0 ; i < cands.size() ; ++i)
122  {
123  PointType point;
124  point.template set<0>(static_cast<double>((cands[i].tstart()/tsamp)/(_config.time_tolerance()/tsamp)));
125 
126  //convert to appropriate scales for proper clustering
127  point.template set<1>(static_cast<double>((cands[i].dm()).value())/((_config.dm_tolerance())).value());
128 
129  point.template set<2>(static_cast<double>(std::log2(cands[i].width().value()/tsamp)/std::log2(_config.pulse_width_tolerance().value()/tsamp)));
130 
131  //set_point(point, point.begin() + i*D);
132  points.emplace_back(point, i);
133  }
134 
135  Tree tree(points.begin(), points.end());
136 
137  while( !tree.empty())
138  {
139  std::vector<ValueType> to_add;
140  // Grab a point from the tree.
141  to_add.push_back( *tree.qbegin( bgi::satisfies([](ValueType const &){ return true; })) );
142  tree.remove( to_add.begin(), to_add.end() );
143  std::vector<ValueType> added;
144 
145  for( std::size_t to_add_i = 0L; to_add_i < to_add.size(); ++to_add_i )
146  {
147  auto it = to_add.begin() + to_add_i;
148 
149  // Build box to query
150  PointType lower = it->first;
151  add_scalar_to_point(lower, -_linking_length);
152  PointType upper = it->first;
153  add_scalar_to_point(upper, _linking_length);
154 
155  boost::geometry::model::box<PointType> box( lower, upper );
156 
157  auto within_ball = [this, &it](ValueType const &v)
158  {
159  double d2 = 0.0;
160  d2_calc(it->first, v.first, d2);
161  return d2 < _linking_length_2;
162  };
163 
164  // Find all points within a linking length of the current point.
165  tree.query( bgi::within(box) && bgi::satisfies(within_ball), std::back_inserter(added) );
166 
167  to_add.reserve(to_add.size() + added.size());
168  // Add the found points to the list so we can find their "friends" as well
169  std::copy(added.begin(), added.end(), std::back_inserter(to_add));
170 
171  // Remove any points we find from the tree as they have been assigned.
172  tree.remove( added.begin(), added.end() );
173 
174  added.clear();
175  // Early exit when we have assigned all particles to a group
176  if (tree.empty())
177  {
178  break;
179  }
180  }
181  std::vector< size_t > group;
182  for( auto p : to_add )
183  {
184  group.push_back(p.second);
185  }
186  groups.push_back(group);
187  }
188  //auto stop = std::chrono::high_resolution_clock::now();
189  //auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
190  //PANDA_LOG << "Time taken by clustering: " << duration.count() << " us";
191 
192  return groups;
193 }
MsecTimeType pulse_width_tolerance() const
: Threshold for pulse widths between two candidates to be clustered in a single group ...
Definition: Config.cpp:87
Dm dm_tolerance() const
: Threshold for DM of two candidates to be clustered in a single group
Definition: Config.cpp:77
MsecTimeType time_tolerance() const
: Threshold for time between two candidates to be clustered in a single group
Definition: Config.cpp:97
Here is the call graph for this function:

The documentation for this class was generated from the following files: