1 // **************************************************************************
2 // * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
4 // * Author: The ALICE Off-line Project. *
5 // * Contributors are mentioned in the code where appropriate. *
7 // * Permission to use, copy, modify and distribute this software and its *
8 // * documentation strictly for non-commercial purposes is hereby granted *
9 // * without fee, provided that the above copyright notice appears in all *
10 // * copies and that both the copyright notice and this permission notice *
11 // * appear in the supporting documentation. The authors make no claims *
12 // * about the suitability of this software for any purpose. It is *
13 // * provided "as is" without express or implied warranty. *
14 // **************************************************************************
16 //-----------------------------------------------------------------------------------
17 // Jet finder based on Deterministic Annealing
18 // For further informations about the DA working features see:
19 // Phys.Lett. B601 (2004) 56-63 (http://arxiv.org/abs/hep-ph/0407214)
20 // Author: Davide Perrino (davide.perrino@ba.infn.it, davide.perrino@cern.ch)
21 //-----------------------------------------------------------------------------------
25 #include <TClonesArray.h>
26 #include "AliJetReader.h"
27 #include "AliDAJetHeader.h"
28 #include "AliDAJetFinder.h"
31 ClassImp(AliDAJetFinder)
34 //-----------------------------------------------------------------------------------
35 AliDAJetFinder::AliDAJetFinder():
56 //-----------------------------------------------------------------------------------
57 AliDAJetFinder::~AliDAJetFinder()
69 //-----------------------------------------------------------------------------------
70 void AliDAJetFinder::FindJets()
72 // Find the jets in current event
74 Float_t betaStop=100.;
81 DoubleClusters(nc,nk);
86 }while((fBeta<betaStop || nc<4) && nc<fNclustMax);
88 Int_t *xx=new Int_t[fNin];
89 EndDetAnn(nk,xx,dEtSum);
95 //-----------------------------------------------------------------------------------
96 void AliDAJetFinder::InitDetAnn(Double_t &dEtSum)
98 //Initialise the variables used by the algorithm
100 TClonesArray *lvArray = fReader->GetMomentumArray();
101 fNin = lvArray->GetEntries();
102 fNclustMax= fHeader->GetFixedCl() ? fHeader->GetNclustMax() : TMath::Max((Int_t)TMath::Sqrt(fNin),5);
103 fXEta=new Double_t[fNin]; fXPhi=new Double_t[fNin];
104 fPx = new TVectorD(fNin);
105 for (Int_t iIn=0; iIn<fNin; iIn++){
106 TLorentzVector *lv=(TLorentzVector*)lvArray->At(iIn);
107 fXEta[iIn] = lv->Eta();
108 fXPhi[iIn] = lv->Phi()<0 ? lv->Phi() + 2*TMath::Pi() : lv->Phi();
109 (*fPx)(iIn)=lv->Pt();
112 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPx)(iIn)=(*fPx)(iIn)/dEtSum;
114 Int_t njdim=2*fNclustMax+1;
115 fPyx = new TMatrixD(fNin,njdim);
116 fY = new TMatrixD(4,njdim);
117 fPy= new TVectorD(njdim);
118 fY->Zero();fPyx->Zero();fPy->Zero();
120 TMatrixDColumn(*fPyx,0)=1;
121 Double_t ypos=0,xpos=0;
122 for (Int_t iIn=0; iIn<fNin; iIn++){
123 (*fY)(0,0)+=(*fPx)(iIn)*fXEta[iIn];
124 ypos+=(*fPx)(iIn)*TMath::Sin(fXPhi[iIn]);
125 xpos+=(*fPx)(iIn)*TMath::Cos(fXPhi[iIn]);
127 (*fY)(1,0)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
131 //-----------------------------------------------------------------------------------
132 void AliDAJetFinder::DoubleClusters(Int_t nc,Int_t &nk)
134 for(Int_t iClust=0; iClust<nc; iClust++){
135 (*fPy)(iClust)=(*fPy)(iClust)/2;
136 (*fPy)(nc+iClust)=(*fPy)(iClust);
137 for(Int_t iComp=0; iComp<3; iComp++) (*fY)(iComp,nc+iClust)=(*fY)(iComp,iClust);
142 //-----------------------------------------------------------------------------------
143 void AliDAJetFinder::Annealing(Int_t nk)
145 // Main part of the algorithm
146 const Double_t pi=TMath::Pi();
147 TVectorD *py = new TVectorD(nk);
148 TVectorD *p = new TVectorD(nk);
149 TMatrixD *y = new TMatrixD(4,nk);
150 TMatrixD *y1 = new TMatrixD(4,nk);
151 TMatrixD *ry = new TMatrixD(2,nk);
152 Double_t Dist(TVectorD,TVectorD);
154 Double_t df[2]={fHeader->GetEtaCut(),pi};
156 Double_t *m = new Double_t[nk];
160 for (Int_t iClust=0; iClust<nk; iClust++){
161 for (Int_t i=0; i<3; i++)(*y1)(i,iClust)=(*fY)(i,iClust);
162 (*py)(iClust)=(*fPy)(iClust);
164 //perturbation of codevectors
165 Double_t seed=1000000*gRandom->Rndm(24);
166 ry->Randomize(-0.5,0.5,seed);
167 for (Int_t i=0; i<2; i++){
168 for (Int_t iClust=0; iClust<nk/2; iClust++)
169 (*y1)(i,iClust)+=((*ry)(i,iClust)+TMath::Sign(0.5,(*ry)(i,iClust)))*fDelta*df[i];
170 for (Int_t iClust=nk/2; iClust<nk; iClust++)
171 (*y1)(i,iClust)-=((*ry)(i,iClust-nk/2)+TMath::Sign(0.5,(*ry)(i,iClust-nk/2)))*fDelta*df[i];
174 //recalculate conditional probabilities
176 for (Int_t iIn=0; iIn<fNin; iIn++){
177 vPart(0)=fXEta[iIn]; vPart(1)=fXPhi[iIn];
178 for(Int_t iClust=0; iClust<nk; iClust++){
179 (*fPyx)(iIn,iClust)=-log((*py)(iClust))+fBeta*Dist(vPart,TMatrixDColumn(*y1,iClust));
180 m[iClust]=(*fPyx)(iIn,iClust);
183 Double_t minPyx=TMath::MinElement(nk,m);
184 for (Int_t iClust=0; iClust<nk; iClust++){
185 (*fPyx)(iIn,iClust)-=minPyx;
186 (*fPyx)(iIn,iClust)=exp(-(*fPyx)(iIn,iClust));
187 pyxNorm+=(*fPyx)(iIn,iClust);
189 for (Int_t iClust=0; iClust<nk; iClust++) (*fPyx)(iIn,iClust)/=pyxNorm;
193 //recalculate codevectors
194 for (Int_t iClust=0; iClust<nk; iClust++){
195 Double_t xpos=0,ypos=0,pxy;
196 for (Int_t iIn=0; iIn<fNin; iIn++) (*p)(iClust)+=(*fPx)(iIn)*(*fPyx)(iIn,iClust);
197 for (Int_t iIn=0; iIn<fNin; iIn++){
198 pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*p)(iClust);
199 ypos+=pxy*TMath::Sin(fXPhi[iIn]);
200 xpos+=pxy*TMath::Cos(fXPhi[iIn]);
201 (*y)(0,iClust)+=pxy*fXEta[iIn];
203 (*y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*pi;
205 //verify codevectors' stability
207 for (Int_t iClust=0; iClust<nk; iClust++){
208 chi1=TMath::CosH((*y1)(0,iClust)-(*y)(0,iClust))-TMath::Cos((*y1)(1,iClust)-(*y)(1,iClust));
209 chi1/=(2*TMath::CosH((*y1)(0,iClust))*TMath::CosH((*y)(0,iClust)));
211 if (chi1>chi) chi=chi1;
213 chi=TMath::Sqrt(chi);
214 for (Int_t iClust=0; iClust<nk; iClust++){
215 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)=(*y)(i,iClust);
216 (*py)(iClust)=(*p)(iClust);
218 if (nloop>fNloopMax){
219 if (chi<fEpsMax || nloop>500) break;
222 }while (chi>fEpsMax);
223 for (Int_t iClust=0; iClust<nk; iClust++){ //set codevectors and probability equal to those calculated
224 for (Int_t i=0; i<2; i++) (*fY)(i,iClust)=(*y)(i,iClust);
225 (*fPy)(iClust)=(*p)(iClust);
235 //-----------------------------------------------------------------------------------
236 void AliDAJetFinder::NumCl(Int_t &nc,Int_t &nk)
238 static Bool_t growcl=true;
240 if (nk==2) growcl=true;
242 //verify if two codevectors are equal within fAvDist
243 Int_t *nSame = new Int_t[nk];
244 Int_t **iSame = new Int_t*[nk];
245 Int_t **cont = new Int_t*[nk];
246 for (Int_t iClust=0; iClust<nk; iClust++) cont[iClust]=new Int_t[nk],iSame[iClust]=new Int_t[nk];
247 for (Int_t iClust=0; iClust<nk; iClust++){
248 iSame[iClust][iClust]=1;
249 for (Int_t iClust1=iClust+1; iClust1<nk; iClust1++){
250 Double_t eta = (*fY)(0,iClust) ; Double_t phi = (*fY)(1,iClust);
251 Double_t eta1 = (*fY)(0,iClust1); Double_t phi1 = (*fY)(1,iClust1);
252 Double_t distCl=(TMath::CosH(eta-eta1)-TMath::Cos(phi-phi1))/(2*TMath::CosH(eta)*TMath::CosH(eta1));
253 if (distCl < fAvDist) iSame[iClust][iClust1]=iSame[iClust1][iClust]=1;
256 ReduceClusters(iSame,nk,nc,cont,nSame);
257 if (nc >= fNclustMax) growcl=false;
258 //recalculate the nc distinct codevectors
259 TMatrixD *pyx = new TMatrixD(fNin,2*nc);
260 TVectorD *py = new TVectorD(nk);
261 TMatrixD *y1 = new TMatrixD(3,nk);
262 for (Int_t iClust=0; iClust<nc; iClust++){
263 for(Int_t j=0; j<nSame[iClust]; j++){
264 Int_t iClust1 = cont[iClust][j];
265 for (Int_t iIn=0; iIn<fNin; iIn++) (*pyx)(iIn,iClust)+=(*fPyx)(iIn,iClust1);
266 (*py)(iClust)+=(*fPy)(iClust1);
267 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)+=(*fY)(i,iClust1);
269 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
272 for (Int_t iClust=0; iClust<nc; iClust++){
273 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPyx)(iIn,iClust)=(*pyx)(iIn,iClust);
274 for (Int_t iComp=0; iComp<2; iComp++) (*fY)(iComp,iClust)=(*y1)(iComp,iClust);
275 (*fPy)(iClust)=(*py)(iClust);
278 if (growcl) DoubleClusters(nc,nk);
290 //-----------------------------------------------------------------------------------
291 void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut)
293 Int_t *nSame = new Int_t[nc];
294 Int_t *iperm = new Int_t[nc];
295 Int_t *go = new Int_t[nc];
296 for (Int_t iCl=0; iCl<nc; iCl++){
298 for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl];
302 TMath::Sort(nc,nSame,iperm,true);
304 for (Int_t iCl=0; iCl<nc; iCl++){
308 for (Int_t jCl=0; jCl<nc; jCl++){
309 if (iSame[k][jCl] == 1){
325 //-----------------------------------------------------------------------------------
326 void AliDAJetFinder::EndDetAnn(Int_t &nk,Int_t *xx,Double_t etx)
328 //now assign each particle to only one cluster
329 Double_t *clusters=new Double_t[nk];
330 for (Int_t iIn=0; iIn<fNin; iIn++){
331 for (Int_t iClust=0; iClust<nk; iClust++) clusters[iClust]=(*fPyx)(iIn,iClust);
332 xx[iIn]=TMath::LocMax(nk,clusters);
336 //recalculate codevectors, having all p(y|x)=0 or 1
340 for (Int_t iIn=0; iIn<fNin; iIn++){
341 Int_t iClust=xx[iIn];
342 (*fPyx)(iIn,iClust)=1;
343 (*fPy)(iClust)+=(*fPx)(iIn);
344 (*fY)(0,iClust)+=(*fPx)(iIn)*fXEta[iIn];
345 (*fY)(3,iClust)+=(*fPx)(iIn)*etx;
348 for (Int_t iClust=0; iClust<nk; iClust++){
349 if ((*fPy)(iClust)>0){
350 Double_t xpos=0,ypos=0,pxy;
351 for (Int_t iIn=0; iIn<fNin; iIn++){
352 pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*fPy)(iClust);
353 ypos+=pxy*TMath::Sin(fXPhi[iIn]);
354 xpos+=pxy*TMath::Cos(fXPhi[iIn]);
355 if (xx[iIn]==iClust) xx[iIn]=k;
357 (*fY)(0,k)=(*fY)(0,iClust)/(*fPy)(iClust);
358 (*fY)(1,k)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
359 (*fY)(3,k)=(*fY)(3,iClust);
366 //-----------------------------------------------------------------------------------
367 void AliDAJetFinder::StoreJets(Int_t nk,Int_t *xx)
369 //evaluate significant clusters properties
370 const Double_t pi=TMath::Pi();
371 Double_t dMeanDist=TMath::Sqrt(4*fHeader->GetEtaCut()*pi/fNin);
372 Bool_t *isJet = new Bool_t[nk];
373 Double_t *etNoBg= new Double_t[nk];
374 Double_t *dDeltaEta=new Double_t[nk];
375 Double_t *dDeltaPhi=new Double_t[nk];
376 Double_t *surf = new Double_t[nk];
377 Double_t *etDens= new Double_t[nk];
378 for (Int_t iClust=0; iClust<nk; iClust++){ //clusters loop
380 Double_t dEtaMin=10.,dEtaMax=-10.,dPhiMin=10.,dPhiMax=0.;
381 for (Int_t iIn=0; iIn<fNin; iIn++){
382 if (xx[iIn]!=iClust) continue;
383 if (fXEta[iIn] < dEtaMin) dEtaMin=fXEta[iIn];
384 if (fXEta[iIn] > dEtaMax) dEtaMax=fXEta[iIn];
385 Double_t dPhi=fXPhi[iIn]-(*fY)(1,iClust);
386 if (dPhi > pi ) dPhi-=2*pi;
387 else if (dPhi < (-1)*pi) dPhi+=2*pi;
388 if (dPhi < dPhiMin) dPhiMin=dPhi;
389 else if (dPhi > dPhiMax) dPhiMax=dPhi;
391 dDeltaEta[iClust]=dEtaMax-dEtaMin+dMeanDist;
392 dDeltaPhi[iClust]=dPhiMax-dPhiMin+dMeanDist;
393 surf[iClust]=0.25*pi*dDeltaEta[iClust]*dDeltaPhi[iClust];
394 etDens[iClust]=(*fY)(3,iClust)/surf[iClust];
397 if (fHeader->GetSelJets()){
398 for (Int_t iClust=0; iClust<nk; iClust++){
400 Double_t etDensMed=0.;
401 Double_t etDensSqr=0.;
403 for (Int_t iClust1=0; iClust1<nk; iClust1++){
405 etDensMed+=etDens[iClust1];
406 etDensSqr+=TMath::Power(etDens[iClust1],2);
410 etDensMed/=TMath::Max(norm,1);
411 etDensSqr/=TMath::Max(norm,1);
412 Double_t deltaEtDens=TMath::Sqrt(etDensSqr-TMath::Power(etDensMed,2));
413 if ((*fY)(3,iClust) > (etDensMed+deltaEtDens)*surf[iClust]) isJet[iClust]=kTRUE;
414 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
417 for (Int_t iClust=0; iClust<nk; iClust++){
419 Double_t etDensMed=0;
420 Double_t extSurf=4*fHeader->GetEtaCut()*pi;
421 for (Int_t iClust1=0; iClust1<nk; iClust1++){
422 if (!isJet[iClust1]) etDensMed+=(*fY)(3,iClust1);
423 else extSurf-=surf[iClust1];
426 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
430 for (Int_t iClust=0; iClust<nk; iClust++) isJet[iClust]=true;
435 //now add selected jets to the list
436 Int_t *inJet = new Int_t[fNin];
438 Bool_t fromAod = !strcmp(fReader->ClassName(),"AliJetAODReader");
439 if (fromAod) refs = fReader->GetReferences();
440 for (Int_t iClust=0; iClust<nk; iClust++){ //clusters loop
441 if (isJet[iClust]){ //choose cluster
443 px = (*fY)(3,iClust)*TMath::Cos((*fY)(1,iClust));
444 py = (*fY)(3,iClust)*TMath::Sin((*fY)(1,iClust));
445 pz = (*fY)(3,iClust)/TMath::Tan(2.0 * TMath::ATan(TMath::Exp(-(*fY)(0,iClust))));
446 en = TMath::Sqrt(px * px + py * py + pz * pz);
447 AliAODJet jet(px, py, pz, en);
449 for (Int_t iIn=0; iIn<fNin; iIn++) if (xx[iIn]==iClust) jet.AddTrack(refs->At(iIn));
451 printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iClust,jet.Eta(),jet.Phi(),jet.Pt());
454 delete [] dDeltaEta; delete [] dDeltaPhi;
460 //-----------------------------------------------------------------------------------
461 Double_t Dist(TVectorD x,TVectorD y)
464 const Double_t pi=TMath::Pi();
465 Double_t dphi=TMath::Abs(x(1)-y(1));
466 if (dphi > pi) dphi=2*pi-dphi;
467 Double_t dist=pow(x(0)-y(0),2)+pow(dphi,2);