Fix a mistake.
[u/mrichter/AliRoot.git] / JETAN / AliDAJetFinder.cxx
CommitLineData
7c679be0 1// **************************************************************************
2// * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
3// * *
4// * Author: The ALICE Off-line Project. *
5// * Contributors are mentioned in the code where appropriate. *
6// * *
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// **************************************************************************
15
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//-----------------------------------------------------------------------------------
22
23#include <TMath.h>
24#include <TRandom.h>
25#include <TClonesArray.h>
26#include "AliJetReader.h"
27#include "AliDAJetHeader.h"
28#include "AliDAJetFinder.h"
29
30
31ClassImp(AliDAJetFinder)
32
33
34//-----------------------------------------------------------------------------------
35AliDAJetFinder::AliDAJetFinder():
36 fAlpha(1.01),
37 fDelta(1e-8),
38 fAvDist(1e-6),
39 fEps(1e-4),
40 fEpsMax(1e-2),
41 fNloopMax(100),
42 fBeta(0.1),
43 fNclustMax(0),
44 fPyx(0x0),
45 fY(0x0),
46 fPx(0x0),
47 fPy(0x0),
48 fXEta(0x0),
49 fXPhi(0x0),
50 fNin(0),
51 fHeader(0x0)
52{
53 // Constructor
54}
55
56//-----------------------------------------------------------------------------------
57AliDAJetFinder::~AliDAJetFinder()
58{
59 // Destructor
60 delete fHeader;
61 delete fPyx;
62 delete fY;
63 delete fPx;
64 delete fPy;
65 delete [] fXEta;
66 delete [] fXPhi;
67}
68
69//-----------------------------------------------------------------------------------
70void AliDAJetFinder::FindJets()
71{
72// Find the jets in current event
73//
74 Float_t betaStop=100.;
75
76 Double_t dEtSum=0;
77 InitDetAnn(dEtSum);
78 if (!fNin) return;
79
80 Int_t nc=1,nk;
81 DoubleClusters(nc,nk);
82 do{ //loop over beta
83 fBeta*=fAlpha;
84 Annealing(nk);
85 NumCl(nc,nk);
86 }while((fBeta<betaStop || nc<4) && nc<fNclustMax);
87
88 Int_t *xx=new Int_t[fNin];
89 EndDetAnn(nk,xx,dEtSum);
90 StoreJets(nk,xx);
91 delete [] xx;
92
93}
94
95//-----------------------------------------------------------------------------------
96void AliDAJetFinder::InitDetAnn(Double_t &dEtSum)
97{
98//Initialise the variables used by the algorithm
99 fBeta=0.1;
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();
110 dEtSum+=(*fPx)(iIn);
111 }
112 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPx)(iIn)=(*fPx)(iIn)/dEtSum;
113
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();
119 (*fPy)(0)=1;
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]);
126 }
127 (*fY)(1,0)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
128 lvArray->Delete();
129}
130
131//-----------------------------------------------------------------------------------
132void AliDAJetFinder::DoubleClusters(Int_t nc,Int_t &nk)
133{
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);
138 }
139 nk=2*nc;
140}
141
142//-----------------------------------------------------------------------------------
143void AliDAJetFinder::Annealing(Int_t nk)
144{
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);
153
154 Double_t df[2]={fHeader->GetEtaCut(),pi};
155 TVectorD vPart(2);
156 Double_t *m = new Double_t[nk];
157 Double_t chi,chi1;
158 do{
159 Int_t nloop=0;
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);
163 }
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];
172 }
173 do{
174 //recalculate conditional probabilities
175 nloop++;
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);
181 }
182 Double_t pyxNorm=0;
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);
188 }
189 for (Int_t iClust=0; iClust<nk; iClust++) (*fPyx)(iIn,iClust)/=pyxNorm;
190 }
191 p->Zero();
192 y->Zero();
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];
202 }
203 (*y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*pi;
204 }
205 //verify codevectors' stability
206 chi=0;
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)));
210 chi1*=chi1;
211 if (chi1>chi) chi=chi1;
212 }
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);
217 }
218 if (nloop>fNloopMax){
219 if (chi<fEpsMax || nloop>500) break;
220 }
221 }while (chi>fEps);
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);
226 }
227 delete py;
228 delete p;
229 delete y;
230 delete y1;
231 delete ry;
232 delete [] m;
233}
234
235//-----------------------------------------------------------------------------------
236void AliDAJetFinder::NumCl(Int_t &nc,Int_t &nk)
237{
238 static Bool_t growcl=true;
239
240 if (nk==2) growcl=true;
241 if (growcl){
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;
254 }
255 }
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);
268 }
269 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
270 }
271 if (nc > nk/2){
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);
276 }
277 nk=nc;
278 if (growcl) DoubleClusters(nc,nk);
279 }
280 delete [] nSame;
281 delete [] iSame;
282 delete [] cont;
283 delete pyx;
284 delete py;
285 delete y1;
286 }
287
288}
289
290//-----------------------------------------------------------------------------------
291void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut)
292{
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++){
297 nSame[iCl]=0;
298 for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl];
299 iperm[iCl]=iCl;
300 go[iCl]=1;
301 }
302 TMath::Sort(nc,nSame,iperm,true);
303 Int_t l=0;
304 for (Int_t iCl=0; iCl<nc; iCl++){
305 Int_t k=iperm[iCl];
306 if (go[k] == 1){
307 Int_t m=0;
308 for (Int_t jCl=0; jCl<nc; jCl++){
309 if (iSame[k][jCl] == 1){
310 cont[l][m]=jCl;
311 go[jCl]=0;
312 m++;
313 }
314 }
315 nSameOut[l]=m;
316 l++;
317 }
318 }
319 ncout=l;
320 delete [] nSame;
321 delete [] iperm;
322 delete [] go;
323}
324
325//-----------------------------------------------------------------------------------
326void AliDAJetFinder::EndDetAnn(Int_t &nk,Int_t *xx,Double_t etx)
327{
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);
333 }
334 delete [] clusters;
335
336//recalculate codevectors, having all p(y|x)=0 or 1
337 fY->Zero();
338 fPyx->Zero();
339 fPy->Zero();
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;
346 }
347 Int_t k=0;
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;
356 }
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);
360 k++;
361 }
362 }
363 nk=k;
364}
365
366//-----------------------------------------------------------------------------------
367void AliDAJetFinder::StoreJets(Int_t nk,Int_t *xx)
368{
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
379 isJet[iClust]=false;
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;
390 }
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];
395 }
396
397 if (fHeader->GetSelJets()){
398 for (Int_t iClust=0; iClust<nk; iClust++){
399 if (!isJet[iClust]){
400 Double_t etDensMed=0.;
401 Double_t etDensSqr=0.;
402 Int_t norm=0;
403 for (Int_t iClust1=0; iClust1<nk; iClust1++){
404 if(iClust1!=iClust){
405 etDensMed+=etDens[iClust1];
406 etDensSqr+=TMath::Power(etDens[iClust1],2);
407 norm++;
408 }
409 }
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];
415 }
416 }
417 for (Int_t iClust=0; iClust<nk; iClust++){
418 if (isJet[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];
424 }
425 etDensMed/=extSurf;
426 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
427 }
428 }
429 } else {
430 for (Int_t iClust=0; iClust<nk; iClust++) isJet[iClust]=true;
431 }
432 delete [] etDens;
433 delete [] surf;
434
435//now add selected jets to the list
436 Int_t *inJet = new Int_t[fNin];
437 TRefArray *refs = 0;
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
442 Float_t px,py,pz,en;
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);
448 if (fromAod)
449 for (Int_t iIn=0; iIn<fNin; iIn++) if (xx[iIn]==iClust) jet.AddTrack(refs->At(iIn));
450 AddJet(jet);
451 printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iClust,jet.Eta(),jet.Phi(),jet.Pt());
452 }
453 }
454 delete [] dDeltaEta; delete [] dDeltaPhi;
455 delete [] etNoBg;
456 delete [] isJet;
457 delete [] inJet;
458}
459
460//-----------------------------------------------------------------------------------
461Double_t Dist(TVectorD x,TVectorD y)
462{
463// Squared distance
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);
468 return dist;
469}