git://git.uio.no / u / mrichter / AliRoot.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
setting status to pending when touch file fails
[u/mrichter/AliRoot.git] / JETAN / AliDAJetFinder.cxx
CommitLineData
9e4cc50d 1
7c679be0 2// **************************************************************************
3// * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
4// * *
5// * Author: The ALICE Off-line Project. *
6// * Contributors are mentioned in the code where appropriate. *
7// * *
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// **************************************************************************
16
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//-----------------------------------------------------------------------------------
23
24#include <TMath.h>
25#include <TRandom.h>
26#include <TClonesArray.h>
27#include "AliJetReader.h"
28#include "AliDAJetHeader.h"
29#include "AliDAJetFinder.h"
30
31
32ClassImp(AliDAJetFinder)
33
34
35//-----------------------------------------------------------------------------------
36AliDAJetFinder::AliDAJetFinder():
37 fAlpha(1.01),
38 fDelta(1e-8),
39 fAvDist(1e-6),
40 fEps(1e-4),
41 fEpsMax(1e-2),
42 fNloopMax(100),
43 fBeta(0.1),
44 fNclustMax(0),
45 fPyx(0x0),
46 fY(0x0),
47 fPx(0x0),
48 fPy(0x0),
49 fXEta(0x0),
50 fXPhi(0x0),
9e4cc50d 51 fNin(0)
7c679be0 52{
53 // Constructor
54}
55
56//-----------------------------------------------------------------------------------
57AliDAJetFinder::~AliDAJetFinder()
58{
59 // Destructor
7c679be0 60 delete fPyx;
61 delete fY;
62 delete fPx;
63 delete fPy;
64 delete [] fXEta;
65 delete [] fXPhi;
66}
67
68//-----------------------------------------------------------------------------------
69void AliDAJetFinder::FindJets()
70{
71// Find the jets in current event
72//
73 Float_t betaStop=100.;
74
75 Double_t dEtSum=0;
76 InitDetAnn(dEtSum);
77 if (!fNin) return;
78
79 Int_t nc=1,nk;
80 DoubleClusters(nc,nk);
81 do{ //loop over beta
82 fBeta*=fAlpha;
83 Annealing(nk);
84 NumCl(nc,nk);
85 }while((fBeta<betaStop || nc<4) && nc<fNclustMax);
86
87 Int_t *xx=new Int_t[fNin];
88 EndDetAnn(nk,xx,dEtSum);
89 StoreJets(nk,xx);
90 delete [] xx;
91
92}
93
94//-----------------------------------------------------------------------------------
95void AliDAJetFinder::InitDetAnn(Double_t &dEtSum)
96{
97//Initialise the variables used by the algorithm
98 fBeta=0.1;
99 TClonesArray *lvArray = fReader->GetMomentumArray();
100 fNin = lvArray->GetEntries();
9e4cc50d 101 fNclustMax= ((AliDAJetHeader*)fHeader)->GetFixedCl() ?
102 ((AliDAJetHeader*)fHeader)->GetNclustMax()
103 :
104 TMath::Max((Int_t)TMath::Sqrt(fNin),5);
7c679be0 105 fXEta=new Double_t[fNin]; fXPhi=new Double_t[fNin];
106 fPx = new TVectorD(fNin);
107 for (Int_t iIn=0; iIn<fNin; iIn++){
108 TLorentzVector *lv=(TLorentzVector*)lvArray->At(iIn);
109 fXEta[iIn] = lv->Eta();
110 fXPhi[iIn] = lv->Phi()<0 ? lv->Phi() + 2*TMath::Pi() : lv->Phi();
111 (*fPx)(iIn)=lv->Pt();
112 dEtSum+=(*fPx)(iIn);
113 }
114 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPx)(iIn)=(*fPx)(iIn)/dEtSum;
115
116 Int_t njdim=2*fNclustMax+1;
117 fPyx = new TMatrixD(fNin,njdim);
118 fY = new TMatrixD(4,njdim);
119 fPy= new TVectorD(njdim);
120 fY->Zero();fPyx->Zero();fPy->Zero();
121 (*fPy)(0)=1;
122 TMatrixDColumn(*fPyx,0)=1;
123 Double_t ypos=0,xpos=0;
124 for (Int_t iIn=0; iIn<fNin; iIn++){
125 (*fY)(0,0)+=(*fPx)(iIn)*fXEta[iIn];
126 ypos+=(*fPx)(iIn)*TMath::Sin(fXPhi[iIn]);
127 xpos+=(*fPx)(iIn)*TMath::Cos(fXPhi[iIn]);
128 }
129 (*fY)(1,0)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
130 lvArray->Delete();
131}
132
133//-----------------------------------------------------------------------------------
134void AliDAJetFinder::DoubleClusters(Int_t nc,Int_t &nk)
135{
136 for(Int_t iClust=0; iClust<nc; iClust++){
137 (*fPy)(iClust)=(*fPy)(iClust)/2;
138 (*fPy)(nc+iClust)=(*fPy)(iClust);
139 for(Int_t iComp=0; iComp<3; iComp++) (*fY)(iComp,nc+iClust)=(*fY)(iComp,iClust);
140 }
141 nk=2*nc;
142}
143
144//-----------------------------------------------------------------------------------
145void AliDAJetFinder::Annealing(Int_t nk)
146{
147// Main part of the algorithm
148 const Double_t pi=TMath::Pi();
149 TVectorD *py = new TVectorD(nk);
150 TVectorD *p = new TVectorD(nk);
151 TMatrixD *y = new TMatrixD(4,nk);
152 TMatrixD *y1 = new TMatrixD(4,nk);
153 TMatrixD *ry = new TMatrixD(2,nk);
154 Double_t Dist(TVectorD,TVectorD);
155
9e4cc50d 156 Double_t df[2]={((AliDAJetHeader*)fHeader)->GetEtaCut(),pi};
7c679be0 157 TVectorD vPart(2);
158 Double_t *m = new Double_t[nk];
159 Double_t chi,chi1;
160 do{
161 Int_t nloop=0;
162 for (Int_t iClust=0; iClust<nk; iClust++){
163 for (Int_t i=0; i<3; i++)(*y1)(i,iClust)=(*fY)(i,iClust);
164 (*py)(iClust)=(*fPy)(iClust);
165 }
166 //perturbation of codevectors
167 Double_t seed=1000000*gRandom->Rndm(24);
168 ry->Randomize(-0.5,0.5,seed);
169 for (Int_t i=0; i<2; i++){
170 for (Int_t iClust=0; iClust<nk/2; iClust++)
171 (*y1)(i,iClust)+=((*ry)(i,iClust)+TMath::Sign(0.5,(*ry)(i,iClust)))*fDelta*df[i];
172 for (Int_t iClust=nk/2; iClust<nk; iClust++)
173 (*y1)(i,iClust)-=((*ry)(i,iClust-nk/2)+TMath::Sign(0.5,(*ry)(i,iClust-nk/2)))*fDelta*df[i];
174 }
175 do{
176 //recalculate conditional probabilities
177 nloop++;
178 for (Int_t iIn=0; iIn<fNin; iIn++){
179 vPart(0)=fXEta[iIn]; vPart(1)=fXPhi[iIn];
180 for(Int_t iClust=0; iClust<nk; iClust++){
181 (*fPyx)(iIn,iClust)=-log((*py)(iClust))+fBeta*Dist(vPart,TMatrixDColumn(*y1,iClust));
182 m[iClust]=(*fPyx)(iIn,iClust);
183 }
184 Double_t pyxNorm=0;
185 Double_t minPyx=TMath::MinElement(nk,m);
186 for (Int_t iClust=0; iClust<nk; iClust++){
187 (*fPyx)(iIn,iClust)-=minPyx;
188 (*fPyx)(iIn,iClust)=exp(-(*fPyx)(iIn,iClust));
189 pyxNorm+=(*fPyx)(iIn,iClust);
190 }
191 for (Int_t iClust=0; iClust<nk; iClust++) (*fPyx)(iIn,iClust)/=pyxNorm;
192 }
193 p->Zero();
194 y->Zero();
195 //recalculate codevectors
196 for (Int_t iClust=0; iClust<nk; iClust++){
197 Double_t xpos=0,ypos=0,pxy;
198 for (Int_t iIn=0; iIn<fNin; iIn++) (*p)(iClust)+=(*fPx)(iIn)*(*fPyx)(iIn,iClust);
199 for (Int_t iIn=0; iIn<fNin; iIn++){
200 pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*p)(iClust);
201 ypos+=pxy*TMath::Sin(fXPhi[iIn]);
202 xpos+=pxy*TMath::Cos(fXPhi[iIn]);
203 (*y)(0,iClust)+=pxy*fXEta[iIn];
204 }
205 (*y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*pi;
206 }
207 //verify codevectors' stability
208 chi=0;
209 for (Int_t iClust=0; iClust<nk; iClust++){
210 chi1=TMath::CosH((*y1)(0,iClust)-(*y)(0,iClust))-TMath::Cos((*y1)(1,iClust)-(*y)(1,iClust));
211 chi1/=(2*TMath::CosH((*y1)(0,iClust))*TMath::CosH((*y)(0,iClust)));
212 chi1*=chi1;
213 if (chi1>chi) chi=chi1;
214 }
215 chi=TMath::Sqrt(chi);
216 for (Int_t iClust=0; iClust<nk; iClust++){
217 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)=(*y)(i,iClust);
218 (*py)(iClust)=(*p)(iClust);
219 }
220 if (nloop>fNloopMax){
221 if (chi<fEpsMax || nloop>500) break;
222 }
223 }while (chi>fEps);
224 }while (chi>fEpsMax);
225 for (Int_t iClust=0; iClust<nk; iClust++){ //set codevectors and probability equal to those calculated
226 for (Int_t i=0; i<2; i++) (*fY)(i,iClust)=(*y)(i,iClust);
227 (*fPy)(iClust)=(*p)(iClust);
228 }
229 delete py;
230 delete p;
231 delete y;
232 delete y1;
233 delete ry;
234 delete [] m;
235}
236
237//-----------------------------------------------------------------------------------
238void AliDAJetFinder::NumCl(Int_t &nc,Int_t &nk)
239{
240 static Bool_t growcl=true;
241
242 if (nk==2) growcl=true;
243 if (growcl){
244//verify if two codevectors are equal within fAvDist
245 Int_t *nSame = new Int_t[nk];
246 Int_t **iSame = new Int_t*[nk];
247 Int_t **cont = new Int_t*[nk];
248 for (Int_t iClust=0; iClust<nk; iClust++) cont[iClust]=new Int_t[nk],iSame[iClust]=new Int_t[nk];
249 for (Int_t iClust=0; iClust<nk; iClust++){
250 iSame[iClust][iClust]=1;
251 for (Int_t iClust1=iClust+1; iClust1<nk; iClust1++){
252 Double_t eta = (*fY)(0,iClust) ; Double_t phi = (*fY)(1,iClust);
253 Double_t eta1 = (*fY)(0,iClust1); Double_t phi1 = (*fY)(1,iClust1);
254 Double_t distCl=(TMath::CosH(eta-eta1)-TMath::Cos(phi-phi1))/(2*TMath::CosH(eta)*TMath::CosH(eta1));
255 if (distCl < fAvDist) iSame[iClust][iClust1]=iSame[iClust1][iClust]=1;
852db00e 256 else iSame[iClust][iClust1]=iSame[iClust1][iClust]=0;
7c679be0 257 }
258 }
259 ReduceClusters(iSame,nk,nc,cont,nSame);
260 if (nc >= fNclustMax) growcl=false;
261//recalculate the nc distinct codevectors
262 TMatrixD *pyx = new TMatrixD(fNin,2*nc);
263 TVectorD *py = new TVectorD(nk);
264 TMatrixD *y1 = new TMatrixD(3,nk);
265 for (Int_t iClust=0; iClust<nc; iClust++){
266 for(Int_t j=0; j<nSame[iClust]; j++){
267 Int_t iClust1 = cont[iClust][j];
268 for (Int_t iIn=0; iIn<fNin; iIn++) (*pyx)(iIn,iClust)+=(*fPyx)(iIn,iClust1);
269 (*py)(iClust)+=(*fPy)(iClust1);
270 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)+=(*fY)(i,iClust1);
271 }
272 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
273 }
852db00e 274 for (Int_t iClust=0; iClust<nk; iClust++) delete [] cont[iClust], delete [] iSame[iClust];
275 delete [] iSame;
276 delete [] cont;
277 delete [] nSame;
7c679be0 278 if (nc > nk/2){
279 for (Int_t iClust=0; iClust<nc; iClust++){
280 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPyx)(iIn,iClust)=(*pyx)(iIn,iClust);
281 for (Int_t iComp=0; iComp<2; iComp++) (*fY)(iComp,iClust)=(*y1)(iComp,iClust);
282 (*fPy)(iClust)=(*py)(iClust);
283 }
284 nk=nc;
285 if (growcl) DoubleClusters(nc,nk);
286 }
7c679be0 287 delete pyx;
288 delete py;
289 delete y1;
290 }
291
292}
293
294//-----------------------------------------------------------------------------------
295void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut)
296{
297 Int_t *nSame = new Int_t[nc];
298 Int_t *iperm = new Int_t[nc];
299 Int_t *go = new Int_t[nc];
300 for (Int_t iCl=0; iCl<nc; iCl++){
301 nSame[iCl]=0;
852db00e 302 for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl], cont[iCl][jCl]=0;
7c679be0 303 iperm[iCl]=iCl;
304 go[iCl]=1;
305 }
306 TMath::Sort(nc,nSame,iperm,true);
307 Int_t l=0;
308 for (Int_t iCl=0; iCl<nc; iCl++){
309 Int_t k=iperm[iCl];
310 if (go[k] == 1){
311 Int_t m=0;
312 for (Int_t jCl=0; jCl<nc; jCl++){
313 if (iSame[k][jCl] == 1){
314 cont[l][m]=jCl;
315 go[jCl]=0;
316 m++;
317 }
318 }
319 nSameOut[l]=m;
320 l++;
321 }
322 }
323 ncout=l;
324 delete [] nSame;
325 delete [] iperm;
326 delete [] go;
327}
328
329//-----------------------------------------------------------------------------------
330void AliDAJetFinder::EndDetAnn(Int_t &nk,Int_t *xx,Double_t etx)
331{
332//now assign each particle to only one cluster
333 Double_t *clusters=new Double_t[nk];
334 for (Int_t iIn=0; iIn<fNin; iIn++){
335 for (Int_t iClust=0; iClust<nk; iClust++) clusters[iClust]=(*fPyx)(iIn,iClust);
336 xx[iIn]=TMath::LocMax(nk,clusters);
337 }
338 delete [] clusters;
339
340//recalculate codevectors, having all p(y|x)=0 or 1
341 fY->Zero();
342 fPyx->Zero();
343 fPy->Zero();
344 for (Int_t iIn=0; iIn<fNin; iIn++){
345 Int_t iClust=xx[iIn];
346 (*fPyx)(iIn,iClust)=1;
347 (*fPy)(iClust)+=(*fPx)(iIn);
348 (*fY)(0,iClust)+=(*fPx)(iIn)*fXEta[iIn];
349 (*fY)(3,iClust)+=(*fPx)(iIn)*etx;
350 }
351 Int_t k=0;
352 for (Int_t iClust=0; iClust<nk; iClust++){
353 if ((*fPy)(iClust)>0){
354 Double_t xpos=0,ypos=0,pxy;
355 for (Int_t iIn=0; iIn<fNin; iIn++){
356 pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*fPy)(iClust);
357 ypos+=pxy*TMath::Sin(fXPhi[iIn]);
358 xpos+=pxy*TMath::Cos(fXPhi[iIn]);
359 if (xx[iIn]==iClust) xx[iIn]=k;
360 }
361 (*fY)(0,k)=(*fY)(0,iClust)/(*fPy)(iClust);
362 (*fY)(1,k)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
363 (*fY)(3,k)=(*fY)(3,iClust);
364 k++;
365 }
366 }
367 nk=k;
368}
369
370//-----------------------------------------------------------------------------------
371void AliDAJetFinder::StoreJets(Int_t nk,Int_t *xx)
372{
373//evaluate significant clusters properties
374 const Double_t pi=TMath::Pi();
9e4cc50d 375 Double_t dMeanDist=TMath::Sqrt(4*((AliDAJetHeader*)fHeader)->GetEtaCut()*pi/fNin);
7c679be0 376 Bool_t *isJet = new Bool_t[nk];
377 Double_t *etNoBg= new Double_t[nk];
378 Double_t *dDeltaEta=new Double_t[nk];
379 Double_t *dDeltaPhi=new Double_t[nk];
380 Double_t *surf = new Double_t[nk];
381 Double_t *etDens= new Double_t[nk];
382 for (Int_t iClust=0; iClust<nk; iClust++){ //clusters loop
383 isJet[iClust]=false;
384 Double_t dEtaMin=10.,dEtaMax=-10.,dPhiMin=10.,dPhiMax=0.;
385 for (Int_t iIn=0; iIn<fNin; iIn++){
386 if (xx[iIn]!=iClust) continue;
387 if (fXEta[iIn] < dEtaMin) dEtaMin=fXEta[iIn];
388 if (fXEta[iIn] > dEtaMax) dEtaMax=fXEta[iIn];
389 Double_t dPhi=fXPhi[iIn]-(*fY)(1,iClust);
390 if (dPhi > pi ) dPhi-=2*pi;
391 else if (dPhi < (-1)*pi) dPhi+=2*pi;
392 if (dPhi < dPhiMin) dPhiMin=dPhi;
393 else if (dPhi > dPhiMax) dPhiMax=dPhi;
394 }
395 dDeltaEta[iClust]=dEtaMax-dEtaMin+dMeanDist;
396 dDeltaPhi[iClust]=dPhiMax-dPhiMin+dMeanDist;
397 surf[iClust]=0.25*pi*dDeltaEta[iClust]*dDeltaPhi[iClust];
398 etDens[iClust]=(*fY)(3,iClust)/surf[iClust];
399 }
400
9e4cc50d 401 if (((AliDAJetHeader*)fHeader)->GetSelJets()){
7c679be0 402 for (Int_t iClust=0; iClust<nk; iClust++){
403 if (!isJet[iClust]){
404 Double_t etDensMed=0.;
405 Double_t etDensSqr=0.;
406 Int_t norm=0;
407 for (Int_t iClust1=0; iClust1<nk; iClust1++){
408 if(iClust1!=iClust){
409 etDensMed+=etDens[iClust1];
410 etDensSqr+=TMath::Power(etDens[iClust1],2);
411 norm++;
412 }
413 }
414 etDensMed/=TMath::Max(norm,1);
415 etDensSqr/=TMath::Max(norm,1);
416 Double_t deltaEtDens=TMath::Sqrt(etDensSqr-TMath::Power(etDensMed,2));
417 if ((*fY)(3,iClust) > (etDensMed+deltaEtDens)*surf[iClust]) isJet[iClust]=kTRUE;
418 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
419 }
420 }
421 for (Int_t iClust=0; iClust<nk; iClust++){
422 if (isJet[iClust]){
423 Double_t etDensMed=0;
9e4cc50d 424 Double_t extSurf=4*((AliDAJetHeader*)fHeader)->GetEtaCut()*pi;
7c679be0 425 for (Int_t iClust1=0; iClust1<nk; iClust1++){
426 if (!isJet[iClust1]) etDensMed+=(*fY)(3,iClust1);
427 else extSurf-=surf[iClust1];
428 }
429 etDensMed/=extSurf;
430 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
10bd125d 431 if (etNoBg[iClust]<((AliDAJetHeader*)fHeader)->GetEtMin()){
432 isJet[iClust]=kFALSE;
433 iClust=-1;
434 }
7c679be0 435 }
436 }
437 } else {
438 for (Int_t iClust=0; iClust<nk; iClust++) isJet[iClust]=true;
439 }
440 delete [] etDens;
441 delete [] surf;
442
443//now add selected jets to the list
444 Int_t *inJet = new Int_t[fNin];
445 TRefArray *refs = 0;
446 Bool_t fromAod = !strcmp(fReader->ClassName(),"AliJetAODReader");
447 if (fromAod) refs = fReader->GetReferences();
448 for (Int_t iClust=0; iClust<nk; iClust++){ //clusters loop
449 if (isJet[iClust]){ //choose cluster
450 Float_t px,py,pz,en;
451 px = (*fY)(3,iClust)*TMath::Cos((*fY)(1,iClust));
452 py = (*fY)(3,iClust)*TMath::Sin((*fY)(1,iClust));
453 pz = (*fY)(3,iClust)/TMath::Tan(2.0 * TMath::ATan(TMath::Exp(-(*fY)(0,iClust))));
454 en = TMath::Sqrt(px * px + py * py + pz * pz);
455 AliAODJet jet(px, py, pz, en);
456 if (fromAod)
457 for (Int_t iIn=0; iIn<fNin; iIn++) if (xx[iIn]==iClust) jet.AddTrack(refs->At(iIn));
458 AddJet(jet);
459 printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iClust,jet.Eta(),jet.Phi(),jet.Pt());
460 }
461 }
462 delete [] dDeltaEta; delete [] dDeltaPhi;
463 delete [] etNoBg;
464 delete [] isJet;
465 delete [] inJet;
466}
467
468//-----------------------------------------------------------------------------------
469Double_t Dist(TVectorD x,TVectorD y)
470{
471// Squared distance
472 const Double_t pi=TMath::Pi();
473 Double_t dphi=TMath::Abs(x(1)-y(1));
474 if (dphi > pi) dphi=2*pi-dphi;
475 Double_t dist=pow(x(0)-y(0),2)+pow(dphi,2);
476 return dist;
477}