Class to help solve closest pair problems with generic interparticle distances and a beam distance, using Anderberg's Nearest Neighbour Heuristic. More...
#include <NNH.hh>
Classes | |
| class | NNBJ |
| a class that wraps around the BJ, supplementing it with extra information such as pointers to neighbours, etc. More... | |
Public Member Functions | |
| NNH (const std::vector< PseudoJet > &jets) | |
| constructor with an initial set of jets (which will be assigned indices 0 ... | |
| NNH (const std::vector< PseudoJet > &jets, I *info) | |
| void | start (const std::vector< PseudoJet > &jets) |
| double | dij_min (int &iA, int &iB) |
| return the dij_min and indices iA, iB, for the corresponding jets. | |
| void | remove_jet (int iA) |
| remove the jet pointed to by index iA | |
| void | merge_jets (int iA, int iB, const PseudoJet &jet, int jet_index) |
| merge the jets pointed to by indices A and B and replace them with jet, assigning it an index jet_index. | |
| ~NNH () | |
| a destructor | |
Private Member Functions | |
| void | set_NN_crosscheck (NNBJ *jet, NNBJ *begin, NNBJ *end) |
| establish the nearest neighbour for jet, and cross check constistency of distances for the other jets that are encountered. | |
| void | set_NN_nocross (NNBJ *jet, NNBJ *begin, NNBJ *end) |
| establish the nearest neighbour for jet; don't cross check other jets' distances and allow jet to be contained within begin...end | |
Private Attributes | |
| NNBJ * | briefjets |
| contains the briefjets | |
| NNBJ * | head |
| semaphores for the current extent of our structure | |
| NNBJ * | tail |
| int | n |
| currently active number of jets | |
| std::vector< NNBJ * > | where_is |
| where_is[i] contains a pointer to the jet with index i | |
Detailed Description
template<class BJ, class I = _NoInfo>
class NNH< BJ, I >
Class to help solve closest pair problems with generic interparticle distances and a beam distance, using Anderberg's Nearest Neighbour Heuristic.
It is templated with a BJ (brief jet) class --- BJ should basically cache the minimal amount of information that is needed to efficiently calculate interparticle distances and particle-beam distances.
This class can be used with or without an extra "Information" template, i.e. NNB<BJ> or NNH<BJ,I>
For the NNH<BJ> class to function in the case, BJ must provide three member functions
- void BJ::init(const PseudoJet & jet); // initialise with a PseudoJet
- double BJ::distance(const BJ * other_bj_jet); // distance between this and other_bj_jet
- double BJ::beam_distance() ; // distance to the beam
For the NNH<BJ,I> version to function, the BJ::init(...) member must accept an extra argument
- void BJ::init(const PseudoJet & jet, I * info); // initialise with a PseudoJet + info
where info might be a pointer to a class that contains, e.g., information about R, or other parameters of the jet algorithm
For an example of how the NNH<BJ> class is used, see the Jade (and EECambridge) plugins
NB: the NNH algorithm is expected N^2, but has a worst case of N^3. Many QCD problems tend to place one closer to the N^3 end of the spectrum than one would like. There is scope for further progress (cf Eppstein, Cardinal & Eppstein), nevertheless the current class is already significantly faster than standard N^3 implementations.
Implementation note: this class derives from NNHInfo, which deals with storing any global information that is needed during the clustering
Constructor & Destructor Documentation
| NNH< BJ, I >::NNH | ( | const std::vector< PseudoJet > & | jets | ) | [inline] |
constructor with an initial set of jets (which will be assigned indices 0 ...
jets.size()-1
Definition at line 107 of file NNH.hh.
References NNH< BJ, I >::start().
{start(jets);}
| NNH< BJ, I >::NNH | ( | const std::vector< PseudoJet > & | jets, |
| I * | info | ||
| ) | [inline] |
Definition at line 108 of file NNH.hh.
References NNH< BJ, I >::start().
: NNHInfo<I>(info) {start(jets);}
a destructor
Definition at line 124 of file NNH.hh.
References NNH< BJ, I >::briefjets.
{
delete[] briefjets;
}
Member Function Documentation
| double NNH< BJ, I >::dij_min | ( | int & | iA, |
| int & | iB | ||
| ) |
return the dij_min and indices iA, iB, for the corresponding jets.
If iB < 0 then iA recombines with the beam
Definition at line 213 of file NNH.hh.
References NNH< BJ, I >::NNBJ::index(), and NNH< BJ, I >::NNBJ::NN.
Referenced by JadePlugin::run_clustering().
{
// find the minimum of the diJ on this round
double diJ_min = briefjets[0].NN_dist;
int diJ_min_jet = 0;
for (int i = 1; i < n; i++) {
if (briefjets[i].NN_dist < diJ_min) {
diJ_min_jet = i;
diJ_min = briefjets[i].NN_dist;
}
}
// return information to user about recombination
NNBJ * jetA = & briefjets[diJ_min_jet];
//std::cout << jetA - briefjets << std::endl;
iA = jetA->index();
iB = jetA->NN ? jetA->NN->index() : -1;
return diJ_min;
}
| void NNH< BJ, I >::merge_jets | ( | int | iA, |
| int | iB, | ||
| const PseudoJet & | jet, | ||
| int | jet_index | ||
| ) |
merge the jets pointed to by indices A and B and replace them with jet, assigning it an index jet_index.
Definition at line 256 of file NNH.hh.
References NNH< BJ, I >::NNBJ::index(), NNH< BJ, I >::NNBJ::NN, and NNH< BJ, I >::NNBJ::NN_dist.
{
NNBJ * jetA = where_is[iA];
NNBJ * jetB = where_is[iB];
// If necessary relabel A & B to ensure jetB < jetA, that way if
// the larger of them == newtail then that ends up being jetA and
// the new jet that is added as jetB is inserted in a position that
// has a future!
if (jetA < jetB) swap(jetA,jetB);
// initialise jetB based on the new jet
//jetB->init(jet, index);
init_jet(jetB, jet, index);
// and record its position (making sure we have the space)
if (index >= int(where_is.size())) where_is.resize(2*index);
where_is[jetB->index()] = jetB;
// now update our nearest neighbour info
// first reduce size of table
tail--; n--;
// Copy last jet contents into position of jetA
*jetA = *tail;
// update the info on where the tail's index is stored
where_is[jetA->index()] = jetA;
for (NNBJ * jetI = head; jetI != tail; jetI++) {
// see if jetI had jetA or jetB as a NN -- if so recalculate the NN
if (jetI->NN == jetA || jetI->NN == jetB) {
set_NN_nocross(jetI, head, tail);
}
// check whether new jetB is closer than jetI's current NN and
// if need be update things
double dist = jetI->distance(jetB);
if (dist < jetI->NN_dist) {
if (jetI != jetB) {
jetI->NN_dist = dist;
jetI->NN = jetB;
}
}
if (dist < jetB->NN_dist) {
if (jetI != jetB) {
jetB->NN_dist = dist;
jetB->NN = jetI;
}
}
// if jetI's NN is the new tail then relabel it so that it becomes jetA
if (jetI->NN == tail) {jetI->NN = jetA;}
}
}
| void NNH< BJ, I >::remove_jet | ( | int | iA | ) |
remove the jet pointed to by index iA
Definition at line 235 of file NNH.hh.
References NNH< BJ, I >::NNBJ::index().
{
NNBJ * jetA = where_is[iA];
// now update our nearest neighbour info and diJ table
// first reduce size of table
tail--; n--;
// Copy last jet contents and diJ info into position of jetA
*jetA = *tail;
// update the info on where the given index is stored
where_is[jetA->index()] = jetA;
for (NNBJ * jetI = head; jetI != tail; jetI++) {
// see if jetI had jetA or jetB as a NN -- if so recalculate the NN
if (jetI->NN == jetA) set_NN_nocross(jetI, head, tail);
// if jetI's NN is the new tail then relabel it so that it becomes jetA
if (jetI->NN == tail) {jetI->NN = jetA;}
}
}
| void NNH< BJ, I >::set_NN_crosscheck | ( | NNBJ * | jet, |
| NNBJ * | begin, | ||
| NNBJ * | end | ||
| ) | [private] |
establish the nearest neighbour for jet, and cross check constistency of distances for the other jets that are encountered.
Assumes jet not contained within begin...end
Definition at line 313 of file NNH.hh.
References NNH< BJ, I >::NNBJ::NN, and NNH< BJ, I >::NNBJ::NN_dist.
{
double NN_dist = jet->beam_distance();
NNBJ * NN = NULL;
for (NNBJ * jetB = begin; jetB != end; jetB++) {
double dist = jet->distance(jetB);
if (dist < NN_dist) {
NN_dist = dist;
NN = jetB;
}
if (dist < jetB->NN_dist) {
jetB->NN_dist = dist;
jetB->NN = jet;
}
}
jet->NN = NN;
jet->NN_dist = NN_dist;
}
| void NNH< BJ, I >::set_NN_nocross | ( | NNBJ * | jet, |
| NNBJ * | begin, | ||
| NNBJ * | end | ||
| ) | [private] |
establish the nearest neighbour for jet; don't cross check other jets' distances and allow jet to be contained within begin...end
Definition at line 336 of file NNH.hh.
References NNH< BJ, I >::NNBJ::NN, and NNH< BJ, I >::NNBJ::NN_dist.
{
double NN_dist = jet->beam_distance();
NNBJ * NN = NULL;
if (head < jet) {
for (NNBJ * jetB = head; jetB != jet; jetB++) {
double dist = jet->distance(jetB);
if (dist < NN_dist) {
NN_dist = dist;
NN = jetB;
}
}
}
if (tail > jet) {
for (NNBJ * jetB = jet+1; jetB != tail; jetB++) {
double dist = jet->distance (jetB);
if (dist < NN_dist) {
NN_dist = dist;
NN = jetB;
}
}
}
jet->NN = NN;
jet->NN_dist = NN_dist;
}
| void NNH< BJ, I >::start | ( | const std::vector< PseudoJet > & | jets | ) |
Definition at line 183 of file NNH.hh.
Referenced by NNH< BJ, I >::NNH().
{
n = jets.size();
briefjets = new NNBJ[n];
where_is.resize(2*n);
NNBJ * jetA = briefjets;
// initialise the basic jet info
for (int i = 0; i< n; i++) {
//jetA->init(jets[i], i);
init_jet(jetA, jets[i], i);
where_is[i] = jetA;
jetA++; // move on to next entry of briefjets
}
tail = jetA; // a semaphore for the end of briefjets
head = briefjets; // a nicer way of naming start
// now initialise the NN distances: jetA will run from 1..n-1; and
// jetB from 0..jetA-1
for (jetA = head + 1; jetA != tail; jetA++) {
// set NN info for jetA based on jets running from head..jetA-1,
// checking in the process whether jetA itself is an undiscovered
// NN of one of those jets.
set_NN_crosscheck(jetA, head, jetA);
}
//std::cout << "OOOO " << briefjets[1].NN_dist << " " << briefjets[1].NN - briefjets << std::endl;
}
Member Data Documentation
The documentation for this class was generated from the following file:
- include/fastjet/NNH.hh
