[u/mrichter/AliRoot.git] / JETAN / AliDAJetFinder.cxx

//  **************************************************************************
//  * Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
//  *                                                                        *
//  * Author: The ALICE Off-line Project.                                    *
//  * Contributors are mentioned in the code where appropriate.              *
//  *                                                                        *
//  * Permission to use, copy, modify and distribute this software and its   *
//  * documentation strictly for non-commercial purposes is hereby granted   *
//  * without fee, provided that the above copyright notice appears in all   *
//  * copies and that both the copyright notice and this permission notice   *
//  * appear in the supporting documentation. The authors make no claims     *
//  * about the suitability of this software for any purpose. It is          *
//  * provided "as is" without express or implied warranty.                  *
//  **************************************************************************

//-----------------------------------------------------------------------------------
// Jet finder based on Deterministic Annealing
// For further informations about the DA working features see:
// Phys.Lett. B601 (2004) 56-63 (http://arxiv.org/abs/hep-ph/0407214)
// Author: Davide Perrino (davide.perrino@ba.infn.it, davide.perrino@cern.ch)
//-----------------------------------------------------------------------------------

#include <TMath.h>
#include <TRandom.h>
#include <TClonesArray.h>
#include "AliJetReader.h"
#include "AliDAJetHeader.h"
#include "AliDAJetFinder.h"


ClassImp(AliDAJetFinder)


//-----------------------------------------------------------------------------------
AliDAJetFinder::AliDAJetFinder():
	fAlpha(1.01),
	fDelta(1e-8),
	fAvDist(1e-6),
	fEps(1e-4),
	fEpsMax(1e-2),
	fNloopMax(100),
	fBeta(0.1),
	fNclustMax(0),
	fPyx(0x0),
	fY(0x0),
	fPx(0x0),
	fPy(0x0),
	fXEta(0x0),
	fXPhi(0x0),
	fNin(0),
	fHeader(0x0)
{
	// Constructor
}

//-----------------------------------------------------------------------------------
AliDAJetFinder::~AliDAJetFinder()
{
	// Destructor
        delete fHeader;
	delete fPyx;
	delete fY;
	delete fPx;
	delete fPy;
	delete [] fXEta;
	delete [] fXPhi;
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::FindJets()  
{
// Find the jets in current event
// 
	Float_t betaStop=100.;

	Double_t dEtSum=0;
	InitDetAnn(dEtSum);
	if (!fNin) return;

	Int_t nc=1,nk;
	DoubleClusters(nc,nk);
	do{					//loop over beta
		fBeta*=fAlpha;
		Annealing(nk);
		NumCl(nc,nk);
	}while((fBeta<betaStop || nc<4) && nc<fNclustMax);

	Int_t *xx=new Int_t[fNin];
	EndDetAnn(nk,xx,dEtSum);
	StoreJets(nk,xx);
	delete [] xx;

}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::InitDetAnn(Double_t &dEtSum)
{
//Initialise the variables used by the algorithm
	fBeta=0.1;
	TClonesArray *lvArray = fReader->GetMomentumArray();
	fNin = lvArray->GetEntries();
	fNclustMax= fHeader->GetFixedCl() ? fHeader->GetNclustMax() : TMath::Max((Int_t)TMath::Sqrt(fNin),5);
	fXEta=new Double_t[fNin]; fXPhi=new Double_t[fNin];
	fPx = new TVectorD(fNin);
	for (Int_t iIn=0; iIn<fNin; iIn++){
		TLorentzVector *lv=(TLorentzVector*)lvArray->At(iIn);
		fXEta[iIn] = lv->Eta();
		fXPhi[iIn] = lv->Phi()<0 ? lv->Phi() + 2*TMath::Pi() : lv->Phi();
		(*fPx)(iIn)=lv->Pt();
		dEtSum+=(*fPx)(iIn);
	}
	for (Int_t iIn=0; iIn<fNin; iIn++) (*fPx)(iIn)=(*fPx)(iIn)/dEtSum;

	Int_t njdim=2*fNclustMax+1;
	fPyx = new TMatrixD(fNin,njdim);
	fY = new TMatrixD(4,njdim);
	fPy= new TVectorD(njdim);
	fY->Zero();fPyx->Zero();fPy->Zero();
	(*fPy)(0)=1;
	TMatrixDColumn(*fPyx,0)=1;
	Double_t ypos=0,xpos=0;
	for (Int_t iIn=0; iIn<fNin; iIn++){
		(*fY)(0,0)+=(*fPx)(iIn)*fXEta[iIn];
		ypos+=(*fPx)(iIn)*TMath::Sin(fXPhi[iIn]);
		xpos+=(*fPx)(iIn)*TMath::Cos(fXPhi[iIn]);
	}
	(*fY)(1,0)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
	lvArray->Delete();
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::DoubleClusters(Int_t nc,Int_t &nk)
{
	for(Int_t iClust=0; iClust<nc; iClust++){
		(*fPy)(iClust)=(*fPy)(iClust)/2;
		(*fPy)(nc+iClust)=(*fPy)(iClust);
		for(Int_t iComp=0; iComp<3; iComp++) (*fY)(iComp,nc+iClust)=(*fY)(iComp,iClust);
	}
	nk=2*nc;
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::Annealing(Int_t nk)
{
// Main part of the algorithm
	const Double_t pi=TMath::Pi();
	TVectorD *py = new TVectorD(nk);
	TVectorD *p  = new TVectorD(nk);
	TMatrixD *y  = new TMatrixD(4,nk);
	TMatrixD *y1 = new TMatrixD(4,nk);
	TMatrixD *ry = new TMatrixD(2,nk);
	Double_t Dist(TVectorD,TVectorD);

	Double_t df[2]={fHeader->GetEtaCut(),pi};
	TVectorD vPart(2);
	Double_t *m = new Double_t[nk];
	Double_t chi,chi1;
	do{
		Int_t nloop=0;
		for (Int_t iClust=0; iClust<nk; iClust++){
			for (Int_t i=0; i<3; i++)(*y1)(i,iClust)=(*fY)(i,iClust);
			(*py)(iClust)=(*fPy)(iClust);
		}
	//perturbation of codevectors
		Double_t seed=1000000*gRandom->Rndm(24);
		ry->Randomize(-0.5,0.5,seed);
		for (Int_t i=0; i<2; i++){
			for (Int_t iClust=0; iClust<nk/2; iClust++)
				(*y1)(i,iClust)+=((*ry)(i,iClust)+TMath::Sign(0.5,(*ry)(i,iClust)))*fDelta*df[i];
			for (Int_t iClust=nk/2; iClust<nk; iClust++)
				(*y1)(i,iClust)-=((*ry)(i,iClust-nk/2)+TMath::Sign(0.5,(*ry)(i,iClust-nk/2)))*fDelta*df[i];
		}
		do{
	//recalculate conditional probabilities
			nloop++;
			for (Int_t iIn=0; iIn<fNin; iIn++){
				vPart(0)=fXEta[iIn]; vPart(1)=fXPhi[iIn];
				for(Int_t iClust=0; iClust<nk; iClust++){
					(*fPyx)(iIn,iClust)=-log((*py)(iClust))+fBeta*Dist(vPart,TMatrixDColumn(*y1,iClust));
					m[iClust]=(*fPyx)(iIn,iClust);
				}
				Double_t pyxNorm=0;
				Double_t minPyx=TMath::MinElement(nk,m);
				for (Int_t iClust=0; iClust<nk; iClust++){
					(*fPyx)(iIn,iClust)-=minPyx;
					(*fPyx)(iIn,iClust)=exp(-(*fPyx)(iIn,iClust));
					pyxNorm+=(*fPyx)(iIn,iClust);
				}
				for (Int_t iClust=0; iClust<nk; iClust++) (*fPyx)(iIn,iClust)/=pyxNorm;
			}
			p->Zero();
			y->Zero();
	//recalculate codevectors
			for (Int_t iClust=0; iClust<nk; iClust++){
				Double_t xpos=0,ypos=0,pxy;
				for (Int_t iIn=0; iIn<fNin; iIn++) (*p)(iClust)+=(*fPx)(iIn)*(*fPyx)(iIn,iClust);
				for (Int_t iIn=0; iIn<fNin; iIn++){
					pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*p)(iClust);
					ypos+=pxy*TMath::Sin(fXPhi[iIn]);
					xpos+=pxy*TMath::Cos(fXPhi[iIn]);
					(*y)(0,iClust)+=pxy*fXEta[iIn];
				}
				(*y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*pi;
			}
	//verify codevectors' stability
			chi=0;
			for (Int_t iClust=0; iClust<nk; iClust++){
				chi1=TMath::CosH((*y1)(0,iClust)-(*y)(0,iClust))-TMath::Cos((*y1)(1,iClust)-(*y)(1,iClust));
				chi1/=(2*TMath::CosH((*y1)(0,iClust))*TMath::CosH((*y)(0,iClust)));
				chi1*=chi1;
				if (chi1>chi) chi=chi1;
			}
			chi=TMath::Sqrt(chi);
			for (Int_t iClust=0; iClust<nk; iClust++){
				for (Int_t i=0; i<2; i++) (*y1)(i,iClust)=(*y)(i,iClust);
				(*py)(iClust)=(*p)(iClust);
			}
			if (nloop>fNloopMax){
				if (chi<fEpsMax || nloop>500) break;
			}
		}while (chi>fEps);
	}while (chi>fEpsMax);
	for (Int_t iClust=0; iClust<nk; iClust++){				//set codevectors and probability equal to those calculated
		for (Int_t i=0; i<2; i++) (*fY)(i,iClust)=(*y)(i,iClust);
		(*fPy)(iClust)=(*p)(iClust);
	}
    delete py;
    delete p;
    delete y;
    delete y1;
    delete ry;
	delete [] m;
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::NumCl(Int_t &nc,Int_t &nk)
{
	static Bool_t growcl=true;
	
	if (nk==2) growcl=true;
	if (growcl){
//verify if two codevectors are equal within fAvDist
		Int_t *nSame = new Int_t[nk];
		Int_t **iSame = new Int_t*[nk];
		Int_t **cont = new Int_t*[nk];
		for (Int_t iClust=0; iClust<nk; iClust++) cont[iClust]=new Int_t[nk],iSame[iClust]=new Int_t[nk];
		for (Int_t iClust=0; iClust<nk; iClust++){
			iSame[iClust][iClust]=1;
			for (Int_t iClust1=iClust+1; iClust1<nk; iClust1++){
				Double_t eta  = (*fY)(0,iClust) ; Double_t phi  = (*fY)(1,iClust);
				Double_t eta1 = (*fY)(0,iClust1); Double_t phi1 = (*fY)(1,iClust1);
				Double_t distCl=(TMath::CosH(eta-eta1)-TMath::Cos(phi-phi1))/(2*TMath::CosH(eta)*TMath::CosH(eta1));
				if (distCl < fAvDist) iSame[iClust][iClust1]=iSame[iClust1][iClust]=1;
			}
		}
		ReduceClusters(iSame,nk,nc,cont,nSame);
		if (nc >= fNclustMax) growcl=false;
//recalculate the nc distinct codevectors
		TMatrixD *pyx = new TMatrixD(fNin,2*nc);
		TVectorD *py = new TVectorD(nk);
		TMatrixD *y1  = new TMatrixD(3,nk);
		for (Int_t iClust=0; iClust<nc; iClust++){
			for(Int_t j=0; j<nSame[iClust]; j++){
				Int_t iClust1 = cont[iClust][j];
				for (Int_t iIn=0; iIn<fNin; iIn++) (*pyx)(iIn,iClust)+=(*fPyx)(iIn,iClust1);
				(*py)(iClust)+=(*fPy)(iClust1);
				for (Int_t i=0; i<2; i++) (*y1)(i,iClust)+=(*fY)(i,iClust1);
			}
			for (Int_t i=0; i<2; i++) (*y1)(i,iClust)/=nSame[iClust];
		}
		if (nc > nk/2){
			for (Int_t iClust=0; iClust<nc; iClust++){
				for (Int_t iIn=0; iIn<fNin; iIn++) (*fPyx)(iIn,iClust)=(*pyx)(iIn,iClust);
				for (Int_t iComp=0; iComp<2; iComp++) (*fY)(iComp,iClust)=(*y1)(iComp,iClust);
				(*fPy)(iClust)=(*py)(iClust);
			}
			nk=nc;
			if (growcl) DoubleClusters(nc,nk);
		}
		delete [] nSame;
		delete [] iSame;
		delete [] cont;
		delete pyx;
		delete py;
		delete y1;
	}

}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::ReduceClusters(Int_t **iSame,Int_t nc,Int_t &ncout,Int_t **cont,Int_t *nSameOut)
{
	Int_t *nSame = new Int_t[nc];
	Int_t *iperm = new Int_t[nc];
	Int_t *go = new Int_t[nc];
	for (Int_t iCl=0; iCl<nc; iCl++){
		nSame[iCl]=0;
		for (Int_t jCl=0; jCl<nc; jCl++) nSame[iCl]+=iSame[iCl][jCl];
		iperm[iCl]=iCl;
		go[iCl]=1;
	}
	TMath::Sort(nc,nSame,iperm,true);
	Int_t l=0;
	for (Int_t iCl=0; iCl<nc; iCl++){
		Int_t k=iperm[iCl];
		if (go[k] == 1){
			Int_t m=0;
			for (Int_t jCl=0; jCl<nc; jCl++){
				if (iSame[k][jCl] == 1){
					cont[l][m]=jCl;
					go[jCl]=0;
					m++;
				}
			}
			nSameOut[l]=m;
			l++;
		}
	}
	ncout=l;
	delete [] nSame;
	delete [] iperm;
	delete [] go;
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::EndDetAnn(Int_t &nk,Int_t *xx,Double_t etx)
{
//now assign each particle to only one cluster
	Double_t *clusters=new Double_t[nk];
	for (Int_t iIn=0; iIn<fNin; iIn++){
		for (Int_t iClust=0; iClust<nk; iClust++) clusters[iClust]=(*fPyx)(iIn,iClust);
		xx[iIn]=TMath::LocMax(nk,clusters);
	}
    delete [] clusters;
	
//recalculate codevectors, having all p(y|x)=0 or 1
	fY->Zero();
	fPyx->Zero();
	fPy->Zero();
	for (Int_t iIn=0; iIn<fNin; iIn++){
		Int_t iClust=xx[iIn];
		(*fPyx)(iIn,iClust)=1;
		(*fPy)(iClust)+=(*fPx)(iIn);
		(*fY)(0,iClust)+=(*fPx)(iIn)*fXEta[iIn];
		(*fY)(3,iClust)+=(*fPx)(iIn)*etx;
	}
	Int_t k=0;
	for (Int_t iClust=0; iClust<nk; iClust++){
		if ((*fPy)(iClust)>0){
			Double_t xpos=0,ypos=0,pxy;
			for (Int_t iIn=0; iIn<fNin; iIn++){
				pxy=(*fPx)(iIn)*(*fPyx)(iIn,iClust)/(*fPy)(iClust);
				ypos+=pxy*TMath::Sin(fXPhi[iIn]);
				xpos+=pxy*TMath::Cos(fXPhi[iIn]);
				if (xx[iIn]==iClust) xx[iIn]=k;
			}
			(*fY)(0,k)=(*fY)(0,iClust)/(*fPy)(iClust);
			(*fY)(1,k)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2*TMath::Pi();
			(*fY)(3,k)=(*fY)(3,iClust);
			k++;
		}
	}
	nk=k;
}

//-----------------------------------------------------------------------------------
void AliDAJetFinder::StoreJets(Int_t nk,Int_t *xx)
{
//evaluate significant clusters properties
	const Double_t pi=TMath::Pi();
	Double_t dMeanDist=TMath::Sqrt(4*fHeader->GetEtaCut()*pi/fNin);
	Bool_t   *isJet = new Bool_t[nk];
	Double_t *etNoBg= new Double_t[nk];
	Double_t *dDeltaEta=new Double_t[nk];
	Double_t *dDeltaPhi=new Double_t[nk];
	Double_t *surf  = new Double_t[nk];
	Double_t *etDens= new Double_t[nk];
	for (Int_t iClust=0; iClust<nk; iClust++){									//clusters loop
		isJet[iClust]=false;
		Double_t dEtaMin=10.,dEtaMax=-10.,dPhiMin=10.,dPhiMax=0.;
		for (Int_t iIn=0; iIn<fNin; iIn++){
			if (xx[iIn]!=iClust) continue;
			if (fXEta[iIn] < dEtaMin) dEtaMin=fXEta[iIn];
			if (fXEta[iIn] > dEtaMax) dEtaMax=fXEta[iIn];
			Double_t dPhi=fXPhi[iIn]-(*fY)(1,iClust);
			if      (dPhi > pi     ) dPhi-=2*pi;
			else if (dPhi < (-1)*pi) dPhi+=2*pi;
			if      (dPhi < dPhiMin) dPhiMin=dPhi;
			else if (dPhi > dPhiMax) dPhiMax=dPhi;
		}
		dDeltaEta[iClust]=dEtaMax-dEtaMin+dMeanDist;
		dDeltaPhi[iClust]=dPhiMax-dPhiMin+dMeanDist;
		surf[iClust]=0.25*pi*dDeltaEta[iClust]*dDeltaPhi[iClust];
		etDens[iClust]=(*fY)(3,iClust)/surf[iClust];
	}

	if (fHeader->GetSelJets()){
		for (Int_t iClust=0; iClust<nk; iClust++){
			if (!isJet[iClust]){
				Double_t etDensMed=0.;
				Double_t etDensSqr=0.;
				Int_t norm=0;
				for (Int_t iClust1=0; iClust1<nk; iClust1++){
					if(iClust1!=iClust){
						etDensMed+=etDens[iClust1];
						etDensSqr+=TMath::Power(etDens[iClust1],2);
						norm++;
					}
				}
				etDensMed/=TMath::Max(norm,1);
				etDensSqr/=TMath::Max(norm,1);
				Double_t deltaEtDens=TMath::Sqrt(etDensSqr-TMath::Power(etDensMed,2));
				if ((*fY)(3,iClust) > (etDensMed+deltaEtDens)*surf[iClust]) isJet[iClust]=kTRUE;
				etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
			}
		}
		for (Int_t iClust=0; iClust<nk; iClust++){
			if (isJet[iClust]){
				Double_t etDensMed=0;
				Double_t extSurf=4*fHeader->GetEtaCut()*pi;
				for (Int_t iClust1=0; iClust1<nk; iClust1++){
					if (!isJet[iClust1]) etDensMed+=(*fY)(3,iClust1);
					else extSurf-=surf[iClust1];
				}
				etDensMed/=extSurf;
				etNoBg[iClust]=(*fY)(3,iClust)-etDensMed*surf[iClust];
			}
		}
	} else {
		for (Int_t iClust=0; iClust<nk; iClust++) isJet[iClust]=true;
	}
	delete [] etDens;
	delete [] surf;
	
//now add selected jets to the list
	Int_t *inJet = new Int_t[fNin];
	TRefArray *refs = 0;
	Bool_t fromAod = !strcmp(fReader->ClassName(),"AliJetAODReader");
	if (fromAod) refs = fReader->GetReferences();
	for (Int_t iClust=0; iClust<nk; iClust++){									//clusters loop
		if (isJet[iClust]){														//choose cluster
			Float_t px,py,pz,en;
			px = (*fY)(3,iClust)*TMath::Cos((*fY)(1,iClust));
			py = (*fY)(3,iClust)*TMath::Sin((*fY)(1,iClust));
			pz = (*fY)(3,iClust)/TMath::Tan(2.0 * TMath::ATan(TMath::Exp(-(*fY)(0,iClust))));
			en = TMath::Sqrt(px * px + py * py + pz * pz);
			AliAODJet jet(px, py, pz, en);
			if (fromAod) 
			    for (Int_t iIn=0; iIn<fNin; iIn++) if (xx[iIn]==iClust) jet.AddTrack(refs->At(iIn));
			AddJet(jet);
			printf("jet %d, Eta: %f, Phi: %f, Et: %f\n",iClust,jet.Eta(),jet.Phi(),jet.Pt());
		}
	}
	delete [] dDeltaEta; delete [] dDeltaPhi;
	delete [] etNoBg;
	delete [] isJet;
	delete [] inJet;
}

//-----------------------------------------------------------------------------------
Double_t Dist(TVectorD x,TVectorD y)
{
// Squared distance
	const Double_t pi=TMath::Pi();
	Double_t dphi=TMath::Abs(x(1)-y(1));
	if (dphi > pi) dphi=2*pi-dphi;
	Double_t dist=pow(x(0)-y(0),2)+pow(dphi,2);
	return dist;
}
Commit	Line	Data
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
	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)+2TMath::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))+fBetaDist(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)+=pxyfXEta[iIn];
202	}
203	(y)(1,iClust)=(atan2(ypos,xpos)>0) ? atan2(ypos,xpos) : atan2(ypos,xpos)+2pi;
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/=(2TMath::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))/(2TMath::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,2nc);
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)+2TMath::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(4fHeader->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+=2pi;
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.25pidDeltaEta[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)-etDensMedsurf[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=4fHeader->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)-etDensMedsurf[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	}