]> git.uio.no Git - u/mrichter/AliRoot.git/blob - JETAN/AliDAJetFinder.cxx
Warnings corrected.
[u/mrichter/AliRoot.git] / JETAN / AliDAJetFinder.cxx
1
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
32 ClassImp(AliDAJetFinder)
33
34
35 //-----------------------------------------------------------------------------------
36 AliDAJetFinder::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),
51         fNin(0)
52 {
53         // Constructor
54 }
55
56 //-----------------------------------------------------------------------------------
57 AliDAJetFinder::~AliDAJetFinder()
58 {
59         // Destructor
60         delete fPyx;
61         delete fY;
62         delete fPx;
63         delete fPy;
64         delete [] fXEta;
65         delete [] fXPhi;
66 }
67
68 //-----------------------------------------------------------------------------------
69 void 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 //-----------------------------------------------------------------------------------
95 void 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();
101         fNclustMax= ((AliDAJetHeader*)fHeader)->GetFixedCl() ? 
102             ((AliDAJetHeader*)fHeader)->GetNclustMax() 
103             : 
104             TMath::Max((Int_t)TMath::Sqrt(fNin),5);
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 //-----------------------------------------------------------------------------------
134 void 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 //-----------------------------------------------------------------------------------
145 void 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
156         Double_t df[2]={((AliDAJetHeader*)fHeader)->GetEtaCut(),pi};
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 //-----------------------------------------------------------------------------------
238 void 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;
256                         }
257                 }
258                 ReduceClusters(iSame,nk,nc,cont,nSame);
259                 if (nc >= fNclustMax) growcl=false;
260 //recalculate the nc distinct codevectors
261                 TMatrixD *pyx = new TMatrixD(fNin,2*nc);
262                 TVectorD *py = new TVectorD(nk);
263                 TMatrixD *y1  = new TMatrixD(3,nk);
264                 for (Int_t iClust=0; iClust<nc; iClust++){
265                         for(Int_t j=0; j<nSame[iClust]; j++){
266                                 Int_t iClust1 = cont[iClust][j];
267                                 for (Int_t iIn=0; iIn<fNin; iIn++) (*pyx)(iIn,iClust)+=(*fPyx)(iIn,iClust1);
268                                 (*py)(iClust)+=(*fPy)(iClust1);
269                                 for (Int_t i=0; i<2; i++) (*y1)(i,iClust)+=(*fY)(i,iClust1);
270                         }
271                         for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
272                 }
273                 if (nc > nk/2){
274                         for (Int_t iClust=0; iClust<nc; iClust++){
275                                 for (Int_t iIn=0; iIn<fNin; iIn++) (*fPyx)(iIn,iClust)=(*pyx)(iIn,iClust);
276                                 for (Int_t iComp=0; iComp<2; iComp++) (*fY)(iComp,iClust)=(*y1)(iComp,iClust);
277                                 (*fPy)(iClust)=(*py)(iClust);
278                         }
279                         nk=nc;
280                         if (growcl) DoubleClusters(nc,nk);
281                 }
282                 delete [] nSame;
283                 delete [] iSame;
284                 delete [] cont;
285                 delete pyx;
286                 delete py;
287                 delete y1;
288         }
289
290 }
291
292 //-----------------------------------------------------------------------------------
293 void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut)
294 {
295         Int_t *nSame = new Int_t[nc];
296         Int_t *iperm = new Int_t[nc];
297         Int_t *go = new Int_t[nc];
298         for (Int_t iCl=0; iCl<nc; iCl++){
299                 nSame[iCl]=0;
300                 for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl];
301                 iperm[iCl]=iCl;
302                 go[iCl]=1;
303         }
304         TMath::Sort(nc,nSame,iperm,true);
305         Int_t l=0;
306         for (Int_t iCl=0; iCl<nc; iCl++){
307                 Int_t k=iperm[iCl];
308                 if (go[k] == 1){
309                         Int_t m=0;
310                         for (Int_t jCl=0; jCl<nc; jCl++){
311                                 if (iSame[k][jCl] == 1){
312                                         cont[l][m]=jCl;
313                                         go[jCl]=0;
314                                         m++;
315                                 }
316                         }
317                         nSameOut[l]=m;
318                         l++;
319                 }
320         }
321         ncout=l;
322         delete [] nSame;
323         delete [] iperm;
324         delete [] go;
325 }
326
327 //-----------------------------------------------------------------------------------
328 void AliDAJetFinder::EndDetAnn(Int_t &nk,Int_t *xx,Double_t etx)
329 {
330 //now assign each particle to only one cluster
331         Double_t *clusters=new Double_t[nk];
332         for (Int_t iIn=0; iIn<fNin; iIn++){
333                 for (Int_t iClust=0; iClust<nk; iClust++) clusters[iClust]=(*fPyx)(iIn,iClust);
334                 xx[iIn]=TMath::LocMax(nk,clusters);
335         }
336     delete [] clusters;
337         
338 //recalculate codevectors, having all p(y|x)=0 or 1
339         fY->Zero();
340         fPyx->Zero();
341         fPy->Zero();
342         for (Int_t iIn=0; iIn<fNin; iIn++){
343                 Int_t iClust=xx[iIn];
344                 (*fPyx)(iIn,iClust)=1;
345                 (*fPy)(iClust)+=(*fPx)(iIn);
346                 (*fY)(0,iClust)+=(*fPx)(iIn)*fXEta[iIn];
347                 (*fY)(3,iClust)+=(*fPx)(iIn)*etx;
348         }
349         Int_t k=0;
350         for (Int_t iClust=0; iClust<nk; iClust++){
351                 if ((*fPy)(iClust)>0){
352                         Double_t xpos=0,ypos=0,pxy;
353                         for (Int_t iIn=0; iIn<fNin; iIn++){
354                                 pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*fPy)(iClust);
355                                 ypos+=pxy*TMath::Sin(fXPhi[iIn]);
356                                 xpos+=pxy*TMath::Cos(fXPhi[iIn]);
357                                 if (xx[iIn]==iClust) xx[iIn]=k;
358                         }
359                         (*fY)(0,k)=(*fY)(0,iClust)/(*fPy)(iClust);
360                         (*fY)(1,k)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
361                         (*fY)(3,k)=(*fY)(3,iClust);
362                         k++;
363                 }
364         }
365         nk=k;
366 }
367
368 //-----------------------------------------------------------------------------------
369 void AliDAJetFinder::StoreJets(Int_t nk,Int_t *xx)
370 {
371 //evaluate significant clusters properties
372         const Double_t pi=TMath::Pi();
373         Double_t dMeanDist=TMath::Sqrt(4*((AliDAJetHeader*)fHeader)->GetEtaCut()*pi/fNin);
374         Bool_t   *isJet = new Bool_t[nk];
375         Double_t *etNoBg= new Double_t[nk];
376         Double_t *dDeltaEta=new Double_t[nk];
377         Double_t *dDeltaPhi=new Double_t[nk];
378         Double_t *surf  = new Double_t[nk];
379         Double_t *etDens= new Double_t[nk];
380         for (Int_t iClust=0; iClust<nk; iClust++){                                                                      //clusters loop
381                 isJet[iClust]=false;
382                 Double_t dEtaMin=10.,dEtaMax=-10.,dPhiMin=10.,dPhiMax=0.;
383                 for (Int_t iIn=0; iIn<fNin; iIn++){
384                         if (xx[iIn]!=iClust) continue;
385                         if (fXEta[iIn] < dEtaMin) dEtaMin=fXEta[iIn];
386                         if (fXEta[iIn] > dEtaMax) dEtaMax=fXEta[iIn];
387                         Double_t dPhi=fXPhi[iIn]-(*fY)(1,iClust);
388                         if      (dPhi > pi     ) dPhi-=2*pi;
389                         else if (dPhi < (-1)*pi) dPhi+=2*pi;
390                         if      (dPhi < dPhiMin) dPhiMin=dPhi;
391                         else if (dPhi > dPhiMax) dPhiMax=dPhi;
392                 }
393                 dDeltaEta[iClust]=dEtaMax-dEtaMin+dMeanDist;
394                 dDeltaPhi[iClust]=dPhiMax-dPhiMin+dMeanDist;
395                 surf[iClust]=0.25*pi*dDeltaEta[iClust]*dDeltaPhi[iClust];
396                 etDens[iClust]=(*fY)(3,iClust)/surf[iClust];
397         }
398
399         if (((AliDAJetHeader*)fHeader)->GetSelJets()){
400                 for (Int_t iClust=0; iClust<nk; iClust++){
401                         if (!isJet[iClust]){
402                                 Double_t etDensMed=0.;
403                                 Double_t etDensSqr=0.;
404                                 Int_t norm=0;
405                                 for (Int_t iClust1=0; iClust1<nk; iClust1++){
406                                         if(iClust1!=iClust){
407                                                 etDensMed+=etDens[iClust1];
408                                                 etDensSqr+=TMath::Power(etDens[iClust1],2);
409                                                 norm++;
410                                         }
411                                 }
412                                 etDensMed/=TMath::Max(norm,1);
413                                 etDensSqr/=TMath::Max(norm,1);
414                                 Double_t deltaEtDens=TMath::Sqrt(etDensSqr-TMath::Power(etDensMed,2));
415                                 if ((*fY)(3,iClust) > (etDensMed+deltaEtDens)*surf[iClust]) isJet[iClust]=kTRUE;
416                                 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
417                         }
418                 }
419                 for (Int_t iClust=0; iClust<nk; iClust++){
420                         if (isJet[iClust]){
421                                 Double_t etDensMed=0;
422                                 Double_t extSurf=4*((AliDAJetHeader*)fHeader)->GetEtaCut()*pi;
423                                 for (Int_t iClust1=0; iClust1<nk; iClust1++){
424                                         if (!isJet[iClust1]) etDensMed+=(*fY)(3,iClust1);
425                                         else extSurf-=surf[iClust1];
426                                 }
427                                 etDensMed/=extSurf;
428                                 etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
429                         }
430                 }
431         } else {
432                 for (Int_t iClust=0; iClust<nk; iClust++) isJet[iClust]=true;
433         }
434         delete [] etDens;
435         delete [] surf;
436         
437 //now add selected jets to the list
438         Int_t *inJet = new Int_t[fNin];
439         TRefArray *refs = 0;
440         Bool_t fromAod = !strcmp(fReader->ClassName(),"AliJetAODReader");
441         if (fromAod) refs = fReader->GetReferences();
442         for (Int_t iClust=0; iClust<nk; iClust++){                                                                      //clusters loop
443                 if (isJet[iClust]){                                                                                                             //choose cluster
444                         Float_t px,py,pz,en;
445                         px = (*fY)(3,iClust)*TMath::Cos((*fY)(1,iClust));
446                         py = (*fY)(3,iClust)*TMath::Sin((*fY)(1,iClust));
447                         pz = (*fY)(3,iClust)/TMath::Tan(2.0 * TMath::ATan(TMath::Exp(-(*fY)(0,iClust))));
448                         en = TMath::Sqrt(px * px + py * py + pz * pz);
449                         AliAODJet jet(px, py, pz, en);
450                         if (fromAod) 
451                             for (Int_t iIn=0; iIn<fNin; iIn++) if (xx[iIn]==iClust) jet.AddTrack(refs->At(iIn));
452                         AddJet(jet);
453                         printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iClust,jet.Eta(),jet.Phi(),jet.Pt());
454                 }
455         }
456         delete [] dDeltaEta; delete [] dDeltaPhi;
457         delete [] etNoBg;
458         delete [] isJet;
459         delete [] inJet;
460 }
461
462 //-----------------------------------------------------------------------------------
463 Double_t Dist(TVectorD x,TVectorD y)
464 {
465 // Squared distance
466         const Double_t pi=TMath::Pi();
467         Double_t dphi=TMath::Abs(x(1)-y(1));
468         if (dphi > pi) dphi=2*pi-dphi;
469         Double_t dist=pow(x(0)-y(0),2)+pow(dphi,2);
470         return dist;
471 }