Help solve closest pair problems with generic interparticle and beam distance. More...
#include <NNH.hh>
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 | |
Detailed Description
template<class BJ, class I = _NoInfo>
class fastjet::NNH< BJ, I >
Help solve closest pair problems with generic interparticle and beam distance.
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> version of the class to function, 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
Definition at line 113 of file NNH.hh.
Constructor & Destructor Documentation
| fastjet::NNH< BJ, I >::NNH | ( | const std::vector< PseudoJet > & | jets | ) | [inline] |
Member Function Documentation
| double fastjet::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 224 of file NNH.hh.
{
// 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 fastjet::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 267 of file NNH.hh.
References fastjet::swap().
{
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) std::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;}
}
}
The documentation for this class was generated from the following file:
- include/fastjet/NNH.hh
