2 // **************************************************************************
3 // * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
5 // * Author: The ALICE Off-line Project. *
6 // * Contributors are mentioned in the code where appropriate. *
8 // * Permission to use, copy, modify and distribute this software and its *
9 // * documentation strictly for non-commercial purposes is hereby granted *
10 // * without fee, provided that the above copyright notice appears in all *
11 // * copies and that both the copyright notice and this permission notice *
12 // * appear in the supporting documentation. The authors make no claims *
13 // * about the suitability of this software for any purpose. It is *
14 // * provided "as is" without express or implied warranty. *
15 // **************************************************************************
17 //-----------------------------------------------------------------------------------
18 // Jet finder based on Deterministic Annealing
19 // For further informations about the DA working features see:
20 // Phys.Lett. B601 (2004) 56-63 (http://arxiv.org/abs/hep-ph/0407214)
21 // Author: Davide Perrino (davide.perrino@ba.infn.it, davide.perrino@cern.ch)
22 //-----------------------------------------------------------------------------------
26 #include <TClonesArray.h>
27 #include "AliJetReaderHeader.h"
28 #include "AliJetReader.h"
29 #include "AliDAJetHeader.h"
30 #include "AliDAJetFinder.h"
32 ClassImp(AliDAJetFinder)
35 //-----------------------------------------------------------------------------------
36 AliDAJetFinder::AliDAJetFinder():
52 //-----------------------------------------------------------------------------------
53 AliDAJetFinder::~AliDAJetFinder()
58 //-----------------------------------------------------------------------------------
59 void AliDAJetFinder::FindJets()
61 // Find the jets in current event
63 Float_t betaStop=100.;
64 fDebug = fHeader->GetDebug();
68 TVectorD *vPx = new TVectorD();
69 TVectorD *vPy = new TVectorD();
70 TMatrixD *mPyx= new TMatrixD();
71 TMatrixD *mY = new TMatrixD();
72 InitDetAnn(dEtSum,xData,vPx,vPy,mPyx,mY);
73 if (fNin < fNclustMax){
74 delete [] xData[0], delete [] xData[1];
82 DoubleClusters(nc,nk,vPy,mY);
85 Annealing(nk,xData,vPx,vPy,mPyx,mY);
86 NumCl(nc,nk,vPy,mPyx,mY);
87 }while((fBeta<betaStop || nc<4) && nc<fNclustMax);
89 Int_t *xx=new Int_t[fNeff];
90 EndDetAnn(nk,xData,xx,dEtSum,vPx,vPy,mPyx,mY);
91 StoreJets(nk,xData,xx,mY);
94 delete [] xData[0], delete [] xData[1];
102 //-----------------------------------------------------------------------------------
103 void AliDAJetFinder::InitDetAnn(Double_t &dEtSum,Double_t **xData,TVectorD *vPx,TVectorD *vPy,TMatrixD *mPyx,TMatrixD *mY)
105 //Initialise the variables used by the algorithm
107 fNclustMax = ((AliDAJetHeader*)fHeader)->GetFixedCl() ?
108 ((AliDAJetHeader*)fHeader)->GetNclustMax() :
109 TMath::Max((Int_t)TMath::Sqrt(fNin),5);
110 Float_t etaEff = ((AliDAJetHeader*)fHeader)->GetEtaEff();
111 TClonesArray *lvArray = fReader->GetMomentumArray();
112 Int_t nEntr = lvArray->GetEntries();
114 for (Int_t iEn=0; iEn<nEntr; iEn++) if (fReader->GetCutFlag(iEn)==1) fNin++;
116 fNeff = ((AliDAJetHeader*)fHeader)->GetNeff();
117 fNeff = TMath::Max(fNeff,fNin);
118 Double_t *xEta = new Double_t[fNeff];
119 Double_t *xPhi = new Double_t[fNeff];
120 xData[0]=xEta; xData[1]=xPhi;
121 vPx->ResizeTo(fNeff);
123 for (Int_t iEn=0; iEn<nEntr; iEn++){
124 if (fReader->GetCutFlag(iEn)==0) continue;
125 TLorentzVector *lv=(TLorentzVector*)lvArray->At(iEn);
126 xEta[iIn] = lv->Eta();
127 xPhi[iIn] = lv->Phi()<0 ? lv->Phi() + 2*TMath::Pi() : lv->Phi();
128 (*vPx)(iIn)=lv->Pt();
134 for (iIn=fNin; iIn<fNeff; iIn++){
135 xEta[iIn]=r.Uniform(-1*etaEff,etaEff);
136 xPhi[iIn]=r.Uniform(0.,2*TMath::Pi());
137 (*vPx)(iIn)=r.Uniform(0.01,0.02);
140 for (iIn=0; iIn<fNeff; iIn++) (*vPx)(iIn)=(*vPx)(iIn)/dEtSum;
142 Int_t njdim=2*fNclustMax+1;
143 mPyx->ResizeTo(fNeff,njdim);
144 mY->ResizeTo(4,njdim);
145 vPy->ResizeTo(njdim);
146 mY->Zero();mPyx->Zero();vPy->Zero();
148 TMatrixDColumn(*mPyx,0)=1;
149 Double_t ypos=0,xpos=0;
150 for (iIn=0; iIn<fNeff; iIn++){
151 (*mY)(0,0)+=(*vPx)(iIn)*xEta[iIn];
152 ypos+=(*vPx)(iIn)*TMath::Sin(xPhi[iIn]);
153 xpos+=(*vPx)(iIn)*TMath::Cos(xPhi[iIn]);
155 (*mY)(1,0)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
158 //-----------------------------------------------------------------------------------
159 void AliDAJetFinder::DoubleClusters(Int_t nc,Int_t &nk, TVectorD *vPy, TMatrixD *mY) const
161 // Return double clusters
162 for(Int_t iClust=0; iClust<nc; iClust++){
163 (*vPy)(iClust)=(*vPy)(iClust)/2;
164 (*vPy)(nc+iClust)=(*vPy)(iClust);
165 for(Int_t iComp=0; iComp<3; iComp++) (*mY)(iComp,nc+iClust)=(*mY)(iComp,iClust);
170 //-----------------------------------------------------------------------------------
171 void AliDAJetFinder::Annealing(Int_t nk,Double_t **xData, TVectorD *vPx, TVectorD *vPy, TMatrixD *mPyx, TMatrixD *mY)
173 // Main part of the algorithm
174 const Double_t pi=TMath::Pi();
175 TVectorD *py = new TVectorD(nk);
176 TVectorD *p = new TVectorD(nk);
177 TMatrixD *y = new TMatrixD(4,nk);
178 TMatrixD *y1 = new TMatrixD(4,nk);
179 TMatrixD *ry = new TMatrixD(2,nk);
180 Double_t *xEta = xData[0];
181 Double_t *xPhi = xData[1];
182 Double_t Dist(TVectorD,TVectorD);
184 Double_t df[2]={fReader->GetReaderHeader()->GetFiducialEtaMax(),pi};
186 Double_t *m = new Double_t[nk];
190 for (Int_t iClust=0; iClust<nk; iClust++){
191 for (Int_t i=0; i<3; i++)(*y1)(i,iClust)=(*mY)(i,iClust);
192 (*py)(iClust)=(*vPy)(iClust);
194 //perturbation of codevectors
195 Double_t seed=1000000*gRandom->Rndm(24);
196 ry->Randomize(-0.5,0.5,seed);
197 for (Int_t i=0; i<2; i++){
198 for (Int_t iClust=0; iClust<nk/2; iClust++)
199 (*y1)(i,iClust)+=((*ry)(i,iClust)+TMath::Sign(0.5,(*ry)(i,iClust)))*fDelta*df[i];
200 for (Int_t iClust=nk/2; iClust<nk; iClust++)
201 (*y1)(i,iClust)-=((*ry)(i,iClust-nk/2)+TMath::Sign(0.5,(*ry)(i,iClust-nk/2)))*fDelta*df[i];
204 //recalculate conditional probabilities
206 for (Int_t iIn=0; iIn<fNeff; iIn++){
207 vPart(0)=xEta[iIn]; vPart(1)=xPhi[iIn];
208 for(Int_t iClust=0; iClust<nk; iClust++){
209 (*mPyx)(iIn,iClust)=-log((*py)(iClust))+fBeta*Dist(vPart,TMatrixDColumn(*y1,iClust));
210 m[iClust]=(*mPyx)(iIn,iClust);
213 Double_t minPyx=TMath::MinElement(nk,m);
214 for (Int_t iClust=0; iClust<nk; iClust++){
215 (*mPyx)(iIn,iClust)-=minPyx;
216 (*mPyx)(iIn,iClust)=exp(-(*mPyx)(iIn,iClust));
217 pyxNorm+=(*mPyx)(iIn,iClust);
219 for (Int_t iClust=0; iClust<nk; iClust++) (*mPyx)(iIn,iClust)/=pyxNorm;
223 //recalculate codevectors
224 for (Int_t iClust=0; iClust<nk; iClust++){
225 Double_t xpos=0,ypos=0,pxy;
226 for (Int_t iIn=0; iIn<fNeff; iIn++) (*p)(iClust)+=(*vPx)(iIn)*(*mPyx)(iIn,iClust);
227 for (Int_t iIn=0; iIn<fNeff; iIn++){
228 pxy=(*vPx)(iIn)*(*mPyx)(iIn,iClust)/(*p)(iClust);
229 ypos+=pxy*TMath::Sin(xPhi[iIn]);
230 xpos+=pxy*TMath::Cos(xPhi[iIn]);
231 (*y)(0,iClust)+=pxy*xEta[iIn];
233 (*y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*pi;
235 //verify codevectors' stability
237 for (Int_t iClust=0; iClust<nk; iClust++){
238 chi1=TMath::CosH((*y1)(0,iClust)-(*y)(0,iClust))-TMath::Cos((*y1)(1,iClust)-(*y)(1,iClust));
239 chi1/=(2*TMath::CosH((*y1)(0,iClust))*TMath::CosH((*y)(0,iClust)));
241 if (chi1>chi) chi=chi1;
243 chi=TMath::Sqrt(chi);
244 for (Int_t iClust=0; iClust<nk; iClust++){
245 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)=(*y)(i,iClust);
246 (*py)(iClust)=(*p)(iClust);
248 if (nloop>fNloopMax){
249 if (chi<fEpsMax || nloop>500) break;
252 }while (chi>fEpsMax);
253 for (Int_t iClust=0; iClust<nk; iClust++){ //set codevectors and probability equal to those calculated
254 for (Int_t i=0; i<2; i++) (*mY)(i,iClust)=(*y)(i,iClust);
255 (*vPy)(iClust)=(*p)(iClust);
265 //-----------------------------------------------------------------------------------
266 void AliDAJetFinder::NumCl(Int_t &nc,Int_t &nk,TVectorD *vPy, TMatrixD *mPyx,TMatrixD *mY)
268 // Number of clusters
269 static Bool_t growcl=true;
271 if (nk==2) growcl=true;
273 //verify if two codevectors are equal within fAvDist
274 Int_t *nSame = new Int_t[nk];
275 Int_t **iSame = new Int_t*[nk];
276 Int_t **cont = new Int_t*[nk];
277 for (Int_t iClust=0; iClust<nk; iClust++) cont[iClust]=new Int_t[nk],iSame[iClust]=new Int_t[nk];
278 for (Int_t iClust=0; iClust<nk; iClust++){
279 iSame[iClust][iClust]=1;
280 for (Int_t iClust1=iClust+1; iClust1<nk; iClust1++){
281 Double_t eta = (*mY)(0,iClust) ; Double_t phi = (*mY)(1,iClust);
282 Double_t eta1 = (*mY)(0,iClust1); Double_t phi1 = (*mY)(1,iClust1);
283 Double_t distCl=(TMath::CosH(eta-eta1)-TMath::Cos(phi-phi1))/(2*TMath::CosH(eta)*TMath::CosH(eta1));
284 if (distCl < fAvDist) iSame[iClust][iClust1]=iSame[iClust1][iClust]=1;
285 else iSame[iClust][iClust1]=iSame[iClust1][iClust]=0;
288 ReduceClusters(iSame,nk,nc,cont,nSame);
289 if (nc >= fNclustMax) growcl=false;
290 //recalculate the nc distinct codevectors
291 TMatrixD *pyx = new TMatrixD(fNeff,2*nc);
292 TVectorD *py = new TVectorD(nk);
293 TMatrixD *y1 = new TMatrixD(3,nk);
294 for (Int_t iClust=0; iClust<nc; iClust++){
295 for(Int_t j=0; j<nSame[iClust]; j++){
296 Int_t iClust1 = cont[iClust][j];
297 for (Int_t iIn=0; iIn<fNeff; iIn++) (*pyx)(iIn,iClust)+=(*mPyx)(iIn,iClust1);
298 (*py)(iClust)+=(*vPy)(iClust1);
299 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)+=(*mY)(i,iClust1);
301 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
303 for (Int_t iClust=0; iClust<nk; iClust++) delete [] cont[iClust], delete [] iSame[iClust];
308 for (Int_t iClust=0; iClust<nc; iClust++){
309 for (Int_t iIn=0; iIn<fNeff; iIn++) (*mPyx)(iIn,iClust)=(*pyx)(iIn,iClust);
310 for (Int_t iComp=0; iComp<2; iComp++) (*mY)(iComp,iClust)=(*y1)(iComp,iClust);
311 (*vPy)(iClust)=(*py)(iClust);
314 if (growcl) DoubleClusters(nc,nk,vPy,mY);
323 //-----------------------------------------------------------------------------------
324 void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut) const
327 Int_t *nSame = new Int_t[nc];
328 Int_t *iperm = new Int_t[nc];
329 Int_t *go = new Int_t[nc];
330 for (Int_t iCl=0; iCl<nc; iCl++){
332 for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl], cont[iCl][jCl]=0;
336 TMath::Sort(nc,nSame,iperm,true);
338 for (Int_t iCl=0; iCl<nc; iCl++){
342 for (Int_t jCl=0; jCl<nc; jCl++){
343 if (iSame[k][jCl] == 1){
359 //-----------------------------------------------------------------------------------
360 void AliDAJetFinder::EndDetAnn(Int_t &nk,Double_t **xData,Int_t *xx,Double_t etx,TVectorD *vPx,TVectorD *vPy,TMatrixD *mPyx,TMatrixD *mY)
362 //now assign each particle to only one cluster
363 Double_t *clusters=new Double_t[nk];
364 for (Int_t iIn=0; iIn<fNeff; iIn++){
365 for (Int_t iClust=0; iClust<nk; iClust++) clusters[iClust]=(*mPyx)(iIn,iClust);
366 xx[iIn]=TMath::LocMax(nk,clusters);
370 //recalculate codevectors, having all p(y|x)=0 or 1
371 Double_t *xEta = xData[0];
372 Double_t *xPhi = xData[1];
376 for (Int_t iIn=0; iIn<fNin; iIn++){
377 Int_t iClust=xx[iIn];
378 (*mPyx)(iIn,iClust)=1;
379 (*vPy)(iClust)+=(*vPx)(iIn);
380 (*mY)(0,iClust)+=(*vPx)(iIn)*xEta[iIn];
381 (*mY)(3,iClust)+=(*vPx)(iIn)*etx;
384 for (Int_t iClust=0; iClust<nk; iClust++){
385 if ((*vPy)(iClust)>0){
386 Double_t xpos=0,ypos=0,pxy;
387 for (Int_t iIn=0; iIn<fNin; iIn++){
388 pxy=(*vPx)(iIn)*(*mPyx)(iIn,iClust)/(*vPy)(iClust);
389 ypos+=pxy*TMath::Sin(xPhi[iIn]);
390 xpos+=pxy*TMath::Cos(xPhi[iIn]);
391 if (xx[iIn]==iClust) xx[iIn]=k;
393 (*mY)(0,k)=(*mY)(0,iClust)/(*vPy)(iClust);
394 (*mY)(1,k)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
395 (*mY)(3,k)=(*mY)(3,iClust);
402 //-----------------------------------------------------------------------------------
403 void AliDAJetFinder::StoreJets(Int_t nk, Double_t **xData, Int_t *xx, TMatrixD *mY)
405 //evaluate significant clusters properties
406 const Double_t pi=TMath::Pi();
407 AliJetReaderHeader *rHeader=fReader->GetReaderHeader();
408 Float_t dFidEtaMax = rHeader->GetFiducialEtaMax();
409 Float_t dFidEtaMin = rHeader->GetFiducialEtaMin();
410 Float_t dFiducialEta= dFidEtaMax - dFidEtaMin;
411 Double_t *xEta = xData[0];
412 Double_t *xPhi = xData[1];
414 for (Int_t i=0; i<fNeff; i++) if (xEta[i]<dFidEtaMax && xEta[i]>dFidEtaMin) nEff++;
415 Double_t dMeanDist=TMath::Sqrt(2*dFiducialEta*pi/nEff);
416 Bool_t *isJet = new Bool_t[nk];
417 Double_t *etNoBg= new Double_t[nk];
418 Double_t *dDeltaEta=new Double_t[nk];
419 Double_t *dDeltaPhi=new Double_t[nk];
420 Double_t *surf = new Double_t[nk];
421 Double_t *etDens= new Double_t[nk];
422 for (Int_t iClust=0; iClust<nk; iClust++){
424 Double_t dEtaMin=10.,dEtaMax=-10.,dPhiMin=10.,dPhiMax=0.;
425 for (Int_t iIn=0; iIn<fNeff; iIn++){
426 if (xx[iIn]!=iClust || xEta[iIn]>dFidEtaMax || xEta[iIn]<dFidEtaMin) continue;
427 if (xEta[iIn] < dEtaMin) dEtaMin=xEta[iIn];
428 if (xEta[iIn] > dEtaMax) dEtaMax=xEta[iIn];
429 Double_t dPhi=xPhi[iIn]-(*mY)(1,iClust);
430 if (dPhi > pi ) dPhi-=2*pi;
431 else if (dPhi < (-1)*pi) dPhi+=2*pi;
432 if (dPhi < dPhiMin) dPhiMin=dPhi;
433 else if (dPhi > dPhiMax) dPhiMax=dPhi;
435 dDeltaEta[iClust]=dEtaMax-dEtaMin+dMeanDist;
436 dDeltaPhi[iClust]=dPhiMax-dPhiMin+dMeanDist;
437 surf[iClust]=0.25*pi*dDeltaEta[iClust]*dDeltaPhi[iClust];
438 etDens[iClust]=(*mY)(3,iClust)/surf[iClust];
441 if (((AliDAJetHeader*)fHeader)->GetSelJets()){
442 for (Int_t iClust=0; iClust<nk; iClust++){
443 if (!isJet[iClust] && (*mY)(0,iClust)<dFidEtaMax && (*mY)(0,iClust)>dFidEtaMin){
444 Double_t etDensMed=0.;
445 Double_t etDensSqr=0.;
447 for (Int_t iClust1=0; iClust1<nk; iClust1++){
448 if(iClust1!=iClust && (*mY)(0,iClust)<dFidEtaMax && (*mY)(0,iClust)>dFidEtaMin){
449 etDensMed+=etDens[iClust1];
450 etDensSqr+=TMath::Power(etDens[iClust1],2);
454 etDensMed/=TMath::Max(norm,1);
455 etDensSqr/=TMath::Max(norm,1);
456 Double_t deltaEtDens=TMath::Sqrt(etDensSqr-TMath::Power(etDensMed,2));
457 if ((*mY)(3,iClust) > (etDensMed+deltaEtDens)*surf[iClust]) isJet[iClust]=kTRUE;
458 etNoBg[iClust]=(*mY)(3,iClust)-etDensMed*surf[iClust];
461 for (Int_t iClust=0; iClust<nk; iClust++){
463 Double_t etDensMed=0;
464 Double_t extSurf=2*dFiducialEta*pi;
465 for (Int_t iClust1=0; iClust1<nk; iClust1++){
466 if (!isJet[iClust1]) etDensMed+=(*mY)(3,iClust1);
467 else extSurf-=surf[iClust1];
470 etNoBg[iClust]=(*mY)(3,iClust)-etDensMed*surf[iClust];
471 if (etNoBg[iClust]<((AliDAJetHeader*)fHeader)->GetEtMin()){
472 isJet[iClust]=kFALSE;
478 for (Int_t iClust=0; iClust<nk; iClust++){
480 etNoBg[iClust]=(*mY)(3,iClust);
486 //now add selected jets to the list
487 Int_t *iSort = new Int_t[nk];
488 TMath::Sort(nk,etNoBg,iSort,true);
491 Bool_t fromAod = !strcmp(fReader->ClassName(),"AliJetAODReader");
492 if (fromAod) refs = fReader->GetReferences();
493 for (Int_t iClust=0; iClust<nk; iClust++){ //clusters loop
495 if (isJet[iCl]){ //choose cluster
497 px = (*mY)(3,iCl)*TMath::Cos((*mY)(1,iCl));
498 py = (*mY)(3,iCl)*TMath::Sin((*mY)(1,iCl));
499 pz = (*mY)(3,iCl)/TMath::Tan(2.0 * TMath::ATan(TMath::Exp(-(*mY)(0,iCl))));
500 en = TMath::Sqrt(px * px + py * py + pz * pz);
501 AliAODJet jet(px, py, pz, en);
504 Int_t nEntr = fReader->GetMomentumArray()->GetEntries();
505 for (Int_t iEn=0; iEn<nEntr; iEn++){
506 if (fReader->GetCutFlag(iEn)==0) continue;
507 if (xx[iIn]==iCl) jet.AddTrack(refs->At(iEn));
512 if (fDebug > 0) printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iCl,jet.Eta(),jet.Phi(),jet.Pt());
515 delete [] dDeltaEta; delete [] dDeltaPhi;
521 //-----------------------------------------------------------------------------------
522 Double_t Dist(TVectorD x,TVectorD y)
525 const Double_t pi=TMath::Pi();
526 Double_t dphi=TMath::Abs(x(1)-y(1));
527 if (dphi > pi) dphi=2*pi-dphi;
528 Double_t dist=pow(x(0)-y(0),2)+pow(dphi,2);