NNH< BJ, I > Class Template Reference

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>

Inheritance diagram for NNH< BJ, I >:

[legend]

Collaboration diagram for NNH< BJ, I >:

[legend]

List of all members.

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

Definition at line 102 of file NNH.hh.

Constructor & Destructor Documentation

template<class BJ, class I = _NoInfo>

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().

00107 {start(jets);}

template<class BJ, class I = _NoInfo>

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().

00108 : NNHInfo<I>(info) {start(jets);}

template<class BJ, class I = _NoInfo>

NNH< BJ, I >::~NNH ( ) [inline]

a destructor

Definition at line 124 of file NNH.hh.

References NNH< BJ, I >::briefjets.

00124          {
00125     delete[] briefjets;
00126   }

Member Function Documentation

template<class BJ , class I >

double NNH< BJ, I >::dij_min	(	int &	iA,
		int &	iB
	)			`[inline]`

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 >::briefjets, NNH< BJ, I >::NNBJ::index(), NNH< BJ, I >::n, NNH< BJ, I >::NNBJ::NN, and NNH< BJ, I >::NNBJ::NN_dist.

00213                                                                         {
00214   // find the minimum of the diJ on this round
00215   double diJ_min = briefjets[0].NN_dist;
00216   int diJ_min_jet = 0;
00217   for (int i = 1; i < n; i++) {
00218     if (briefjets[i].NN_dist < diJ_min) {
00219       diJ_min_jet = i; 
00220       diJ_min  = briefjets[i].NN_dist;
00221     }
00222   }
00223   
00224   // return information to user about recombination
00225   NNBJ * jetA = & briefjets[diJ_min_jet];
00226   //std::cout << jetA - briefjets << std::endl; 
00227   iA = jetA->index();
00228   iB = jetA->NN ? jetA->NN->index() : -1;
00229   return diJ_min;
00230 }

template<class BJ , class I >

void NNH< BJ, I >::merge_jets	(	int	iA,
		int	iB,
		const PseudoJet &	jet,
		int	jet_index
	)			`[inline]`

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 >::head, NNH< BJ, I >::NNBJ::index(), NNHInfo< I >::init_jet(), NNH< BJ, I >::n, NNH< BJ, I >::NNBJ::NN, NNH< BJ, I >::NNBJ::NN_dist, NNH< BJ, I >::set_NN_nocross(), NNH< BJ, I >::tail, and NNH< BJ, I >::where_is.

00257                                                                           {
00258 
00259   NNBJ * jetA = where_is[iA];
00260   NNBJ * jetB = where_is[iB];
00261 
00262   // If necessary relabel A & B to ensure jetB < jetA, that way if
00263   // the larger of them == newtail then that ends up being jetA and 
00264   // the new jet that is added as jetB is inserted in a position that
00265   // has a future!
00266   if (jetA < jetB) swap(jetA,jetB);
00267 
00268   // initialise jetB based on the new jet
00269   //jetB->init(jet, index);
00270   init_jet(jetB, jet, index);
00271   // and record its position (making sure we have the space)
00272   if (index >= int(where_is.size())) where_is.resize(2*index);
00273   where_is[jetB->index()] = jetB;
00274 
00275   // now update our nearest neighbour info
00276   // first reduce size of table
00277   tail--; n--;
00278   // Copy last jet contents into position of jetA
00279   *jetA = *tail;
00280   // update the info on where the tail's index is stored
00281   where_is[jetA->index()] = jetA;
00282 
00283   for (NNBJ * jetI = head; jetI != tail; jetI++) {
00284     // see if jetI had jetA or jetB as a NN -- if so recalculate the NN
00285     if (jetI->NN == jetA || jetI->NN == jetB) {
00286       set_NN_nocross(jetI, head, tail);
00287     } 
00288 
00289     // check whether new jetB is closer than jetI's current NN and
00290     // if need be update things
00291     double dist = jetI->distance(jetB);
00292     if (dist < jetI->NN_dist) {
00293       if (jetI != jetB) {
00294         jetI->NN_dist = dist;
00295         jetI->NN = jetB;
00296       }
00297     }
00298     if (dist < jetB->NN_dist) {
00299       if (jetI != jetB) {
00300         jetB->NN_dist = dist;
00301         jetB->NN      = jetI;
00302       }
00303     }
00304 
00305     // if jetI's NN is the new tail then relabel it so that it becomes jetA
00306     if (jetI->NN == tail) {jetI->NN = jetA;}
00307   }
00308 }

template<class BJ , class I >

void NNH< BJ, I >::remove_jet ( int iA ) [inline]

remove the jet pointed to by index iA

Definition at line 235 of file NNH.hh.

References NNH< BJ, I >::head, NNH< BJ, I >::NNBJ::index(), NNH< BJ, I >::n, NNH< BJ, I >::set_NN_nocross(), NNH< BJ, I >::tail, and NNH< BJ, I >::where_is.

00235                                                              {
00236   NNBJ * jetA = where_is[iA];
00237   // now update our nearest neighbour info and diJ table
00238   // first reduce size of table
00239   tail--; n--;
00240   // Copy last jet contents and diJ info into position of jetA
00241   *jetA = *tail;
00242   // update the info on where the given index is stored
00243   where_is[jetA->index()] = jetA;
00244 
00245   for (NNBJ * jetI = head; jetI != tail; jetI++) {
00246     // see if jetI had jetA or jetB as a NN -- if so recalculate the NN
00247     if (jetI->NN == jetA) set_NN_nocross(jetI, head, tail);
00248 
00249     // if jetI's NN is the new tail then relabel it so that it becomes jetA
00250     if (jetI->NN == tail) {jetI->NN = jetA;}
00251   }
00252 }

template<class BJ , class I >

void NNH< BJ, I >::set_NN_crosscheck	(	NNBJ *	jet,
		NNBJ *	begin,
		NNBJ *	end
	)			`[inline, 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.

Referenced by NNH< BJ, I >::start().

00314                                               {
00315   double NN_dist = jet->beam_distance();
00316   NNBJ * NN      = NULL;
00317   for (NNBJ * jetB = begin; jetB != end; jetB++) {
00318     double dist = jet->distance(jetB);
00319     if (dist < NN_dist) {
00320       NN_dist = dist;
00321       NN = jetB;
00322     }
00323     if (dist < jetB->NN_dist) {
00324       jetB->NN_dist = dist;
00325       jetB->NN = jet;
00326     }
00327   }
00328   jet->NN = NN;
00329   jet->NN_dist = NN_dist;
00330 }

template<class BJ , class I >

void NNH< BJ, I >::set_NN_nocross	(	NNBJ *	jet,
		NNBJ *	begin,
		NNBJ *	end
	)			`[inline, 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 >::head, NNH< BJ, I >::NNBJ::NN, NNH< BJ, I >::NNBJ::NN_dist, and NNH< BJ, I >::tail.

Referenced by NNH< BJ, I >::merge_jets(), and NNH< BJ, I >::remove_jet().

00337                                                        {
00338   double NN_dist = jet->beam_distance();
00339   NNBJ * NN      = NULL;
00340   if (head < jet) {
00341     for (NNBJ * jetB = head; jetB != jet; jetB++) {
00342       double dist = jet->distance(jetB);
00343       if (dist < NN_dist) {
00344         NN_dist = dist;
00345         NN = jetB;
00346       }
00347     }
00348   }
00349   if (tail > jet) {
00350     for (NNBJ * jetB = jet+1; jetB != tail; jetB++) {
00351       double dist = jet->distance (jetB);
00352       if (dist < NN_dist) {
00353         NN_dist = dist;
00354         NN = jetB;
00355       }
00356     }
00357   }
00358   jet->NN = NN;
00359   jet->NN_dist = NN_dist;
00360 }

template<class BJ , class I >

void NNH< BJ, I >::start ( const std::vector< PseudoJet > & jets ) [inline]

Definition at line 183 of file NNH.hh.

References NNH< BJ, I >::briefjets, NNH< BJ, I >::head, NNHInfo< I >::init_jet(), NNH< BJ, I >::n, NNH< BJ, I >::set_NN_crosscheck(), NNH< BJ, I >::tail, and NNH< BJ, I >::where_is.

Referenced by NNH< BJ, I >::NNH().

00183                                                                                    {
00184   n = jets.size();
00185   briefjets = new NNBJ[n];
00186   where_is.resize(2*n);
00187 
00188   NNBJ * jetA = briefjets;
00189   
00190   // initialise the basic jet info 
00191   for (int i = 0; i< n; i++) {
00192     //jetA->init(jets[i], i);
00193     init_jet(jetA, jets[i], i);
00194     where_is[i] = jetA;
00195     jetA++; // move on to next entry of briefjets
00196   }
00197   tail = jetA; // a semaphore for the end of briefjets
00198   head = briefjets; // a nicer way of naming start
00199 
00200   // now initialise the NN distances: jetA will run from 1..n-1; and
00201   // jetB from 0..jetA-1
00202   for (jetA = head + 1; jetA != tail; jetA++) {
00203     // set NN info for jetA based on jets running from head..jetA-1,
00204     // checking in the process whether jetA itself is an undiscovered
00205     // NN of one of those jets.
00206     set_NN_crosscheck(jetA, head, jetA);
00207   }
00208   //std::cout << "OOOO "  << briefjets[1].NN_dist << " " << briefjets[1].NN - briefjets << std::endl;
00209 }