JETAN/AliDAJetFinder.cxx

   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
  31 ClassImp(AliDAJetFinder)
  32
  33
  34 //-----------------------------------------------------------------------------------
  35 AliDAJetFinder::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 //-----------------------------------------------------------------------------------
  57 AliDAJetFinder::~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 //-----------------------------------------------------------------------------------
  70 void 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 //-----------------------------------------------------------------------------------
  96 void 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 //-----------------------------------------------------------------------------------
 132 void 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 //-----------------------------------------------------------------------------------
 143 void 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 //-----------------------------------------------------------------------------------
 236 void 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 //-----------------------------------------------------------------------------------
 291 void 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 //-----------------------------------------------------------------------------------
 326 void 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 //-----------------------------------------------------------------------------------
 367 void 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 //-----------------------------------------------------------------------------------
 461 Double_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 }