#ifdef MPI
#include "SA_ClusteringSolver.h"

#include "AllSchedulers.h"

#include "util_salib.h"
//#include <strstream.h>
//#include <fstream.h>
#include <strstream>
#include <fstream>
#include <my_math.h>
#include <sys/types.h>
//#include <unistd.h>
 
//#include <mpe.h>
//#define debug(r,m) DBG __bred__(#r); 
//---- SA_ClusteringSolver ---------------------------------------------------------
 
#define SHOW_TIMES		// falls definiert - Ausgabe der gemessenen und geschaetzten Zeiten nach jeder Teilkette
 
#ifdef SHOW_TIMES
	 double measured_t0=0,measured_e0=0;
	 int measured_n;
#endif
#define nDEBUG 
 
SA_ClusteringSolver::SA_ClusteringSolver(int *argc, char ***argv, SA_Problem & prb):
	SA_ParSolver(prb),
	move(NULL),
	MinEff(1.1),	// to indicate clustering for maximizing of speedup*efficiency
	ncluster(-1),	// als Zeichen, dass Clusterstrukturen noch nicht initialisiert sind
	maxcluster(-1),
	CommunicationMode(SOLUTION),
	GlobalEquilibrium(ASYNC),
	BcastFkt(I),
	ConstantSizeMove(0),
	StateBuffer(NULL),
	time_trans(0),
	time_reset(0),	
	time_update(0),
	ChooseMove(FIRST),
	DoDistrSolAfterSubchain(NO),
	saclustsolvoutput("SA_ClusteringSolver","SA_Output.rsc")
{//debug(SA_ClusteringSolver::SA_ClusteringSolver, myrank);
	saclustsolvoutput.EnableLevelNumbers(false);
	saclustsolvoutput.EnableIdentifier(true);
	saclustsolvoutput.SetOutputLevel(10);

	saclustsolvoutput.AddVariable(1,SA_STRING, processor_name);
	saclustsolvoutput.AddVariable(2,SA_INT, &ncluster);
	saclustsolvoutput.AddVariable(3,SA_INT, &maxcluster);
	saclustsolvoutput.AddVariable(4,SA_INT, &actual_cluster);
	saclustsolvoutput.AddVariable(5,SA_DOUBLE, &MinEff);
	saclustsolvoutput.AddVariable(6,SA_DOUBLE, &time_trans);
	saclustsolvoutput.AddVariable(7,SA_DOUBLE, &time_reset);
	saclustsolvoutput.AddVariable(8,SA_DOUBLE, &time_update);
	saclustsolvoutput.AddVariable(9,SA_INT, &ConstantSizeMove);   

	saclustsolvoutput.SetPreviousOutput(SA_ParSolver::GetSolverOutput());
	 
	CommunicateInCluster_fp = & SA_ClusteringSolver::CommunicateInClusterAsyncFirst;
	int flag=0;
	MPI_Initialized(&flag);
	if ( !flag )
	{
		std::cout << "MPI nicht initialisiert! Initialisiere MPI..." << std::endl;
		std::cout << "argc " << *argc << std::endl;
		for(int j=0; j<*argc; j++)
		{
			std::cout << "argv[" << j << "] " << (*argv)[j] << std::endl;
		}
		MPI_Init(argc, argv);
		std::cout << "MPI erfolgreich initialisiert!" << std::endl;
		
	}
	else
	{
		std::cout << "MPI bereits initialisiert!" << std::endl;		
	}
 
	MPI_Comm_rank(MPI_COMM_WORLD,&myrank);

// Falls Multiprozessorbetrieb : jeder Proc. benutzt eigenen Zufallszahlstream
	if( myrank >=0 )
	{
		Select_Stream(myrank);
	}

	int dummy;
	MPI_Get_processor_name(processor_name,&dummy);
	std::cout << "Process " << myrank << " is alive on " << processor_name << std::endl;//" with pid " << getpid() << std::endl;
//MPE_Init_log();
	if (myrank == 0)
	{
//MPE_Describe_state(7, 8, "GetNeighbor",      "yellow:gray");
//MPE_Describe_state(1, 2, "ExchangeSolution", "red:vlines3");
//MPE_Describe_state(9, 10, "TryGlobalAcceptance",    "pink:light_gray");
//MPE_Describe_state(3, 4, "CollectSubchainStatistics",   "blue:gray3");
//MPE_Describe_state(11, 12, "BroadcastSubchainOrder",   "lightblue:gray3");
//MPE_Describe_state(5, 6, "ComputeChain",    "green:light_gray");
//MPE_Describe_state(103, 104, "DistributeSolutionAfterSubchain",      "magenta:gray");		
	
	// fuer ClusterSync	
		////MPE_Describe_state(1, 2, "Ssend", "red:vlines3");
		////MPE_Describe_state(9, 10, "Bcast",    "pink:light_gray");
		////MPE_Describe_state(3, 4, "Iprobe",   "blue:gray3");
		////MPE_Describe_state(11, 12, "Recv",   "lightblue:gray3");
		////MPE_Describe_state(5, 6, "Request_free",    "green:light_gray");
		////MPE_Describe_state(7, 8, "Testsome",      "yellow:gray");
		////MPE_Describe_state(103, 104, "Issend_completed",      "lightyellow:gray");
		////MPE_Describe_state(101, 102, "Issend",      "lightgreen:gray");
	}

// Initialisierung der Kommunikationsstruktur
	DefineCluster();
	
//MPE_Start_log();
////MPE_Stop_log();
  ////MPE_Log_event(7,0,"Start Sync");
	  	MPI_Barrier(MPI_COMM_WORLD);
  ////MPE_Log_event(8,0,"End Sync");
}

SA_Output *SA_ClusteringSolver::GetSolverOutput() {
  return(&saclustsolvoutput);
}

// Unterteilung der Prozessoren und Kommunikationszeiten bestimmen		
void	SA_ClusteringSolver::DefineCluster(void)
{//debug(SA_ClusteringSolver::DefineCluster, myrank);

	int i,j;
	if ( ncluster == -1 )	// Falls Unterteilung in Cluster noch nicht  durchgefuehrt ist 
	{
                int mask,np;

		MPI_Comm_size(MPI_COMM_WORLD, &np);
		ncluster = log2((unsigned int)np) + (ist2pot(np)? 0:1);	
		nproc[ncluster] = np;
		MPI_Comm_rank(MPI_COMM_WORLD,&me[ncluster]);

	// Unterteilung bestimmen
		MPI_Comm_dup(MPI_COMM_WORLD,&(cluster[ncluster]) );
		sync[ncluster].SetCluster(cluster[ncluster]);
//MPI_Comm_split(cluster[ncluster],me[ncluster] == 0, me[ncluster], &masters[ncluster]);

		mask = zwei_hoch(ncluster-1);
	  ////MPE_Log_event(1,0,"Start Split");
		for (i = ncluster-1 ; i >= 0; i--)
		{
			MPI_Comm_split(cluster[i+1], me[ncluster]&mask, me[ncluster], &cluster[i]);
			MPI_Comm_size(cluster[i],&nproc[i]);
			MPI_Comm_rank(cluster[i],&me[i]);		
			MPI_Comm_split(cluster[ncluster],me[i] == 0, me[ncluster], &masters[i]);
			sync[i].SetCluster(cluster[i]);
			mask = mask >> 1;
		}
	  ////MPE_Log_event(2,0,"End Split");
 
	} /* if (ncluster != -1)*/
}

void SA_ClusteringSolver::SetMaxCluster(int mc)
{//debug(SA_ClusteringSolver::SetMaxCluster, myrank);

	if ( maxcluster != -1)	// maxcluster was set already
	{
		std::cout << "Changing of MaxCluster is not implemented jet; sorry !\n";
		return;
	}
	maxcluster = (mc >= 0 && mc <= ncluster) ? mc:ncluster;
	DefineMasters();
}

void	SA_ClusteringSolver::DefineMasters(void)
// Masters-Unterteilung in Anh"angigkeit von maxcluster bestimmen
// auch der Kommunikator chiefs wird gesetzt
{//debug(SA_ClusteringSolver::DefineMasters, myrank);
	
	if( maxcluster < 0 || maxcluster > ncluster)
	{
		std::cout << "In SA_ClusteringSolver::DefineMasters : very bad error! Exiting !!\n"<<std::endl<<std::flush;
		exit(1);
	}
	
	int i;
	for (i = maxcluster ; i >= 0; i--)
	{
		MPI_Comm_split(cluster[maxcluster],me[i] == 0, me[maxcluster], &masters[i]);
		end_chain[i].SetCluster(masters[i]);
	}
	
	MPI_Comm_split(cluster[ncluster],me[maxcluster] == 0,me[maxcluster],&chiefs);	

	/* Gruppen auf den CHEF-Prozessoren erzeugen*/					
	if( me[maxcluster] == 0 )
	{
		masters_group = new MPI_Group[maxcluster];

		for(i=0;i<maxcluster;i++)
		{
			MPI_Comm_group(masters[i],&(masters_group[i]));
		}
		MPI_Comm_group(cluster[maxcluster],&cluster_group);
		
	}
}


void SA_ClusteringSolver::ShowClusters(void)
{
	for (int act_cl=0; act_cl <= ncluster; act_cl++ )
		ShowCluster(act_cl);
}
// Testausgabe der Cluster-Zusammensetzung
void SA_ClusteringSolver::ShowCluster(int act_cl, bool all)
{//debug(SA_ClusteringSolver::ShowCluster, myrank);
	
	int buf[32],
		mas[32];
	int j;
	
	for (j=0;j<32;j++)
	{
		buf[j]= mas[j] = -1;
	}
	MPI_Allgather(&me[ncluster],1,MPI_INT,buf,1,MPI_INT, cluster[act_cl]);
	MPI_Allgather(&me[ncluster],1,MPI_INT,mas,1,MPI_INT, masters[act_cl]);
 
	if (all || me[act_cl] == 0)
	{
		std::cout <<"Im cluster der Dimension " << act_cl << " des "<< me[ncluster] <<" sind " ;
		for (j = 0; j < nproc[act_cl]; j++)
			std::cout << buf[j] << " ";
 
		std::cout << std::endl;
 
		std::cout <<"Im masters der Dimension " << act_cl << " des "<< me[ncluster] <<" sind " ;
		for (j = 0; j < 32; j++)
			if ( mas[j] != -1 )
				std::cout << mas[j] << " ";
 
		std::cout << std::endl;
	}
}
 
// Zeiten fuer Austausch der Loesungen messen
// Problemdaten muessen bereits eingelesen sein und 
// State eine zul. Loesung enthalten;
// erzeugt SA_ClusteringSolver::*move
void	SA_ClusteringSolver::MeasureCommTimes(int start_cluster, int end_cluster)
{//debug(SA_ClusteringSolver::MeasureCommTimes, myrank);
//std::cout <<myrank<<" MeasureCommTimes in\n";
	if( start_cluster<0 || start_cluster > end_cluster || end_cluster >ncluster)
	{
		std::cout <<"Internal error in SA_ClusteringSolver::MeasureCommTimes - boundaries error!"<<std::endl;
		return;
	}
	
	int i,j,founder, 
		eq_dummy = 0;
	int actual_cluster_save = actual_cluster;
		
	const int FACTOR=10;	
	
	double t,dt_buf;
	
//	if ( StateBuffer == NULL )
//	{
//		StateBuffer = P->CreateSolution();
//	}
//	P->Copy(*State,*StateBuffer);	// den Zustand zwischenspeichern
	
// Die Cluster-Ebenen werden rueckwaerts durchlaufen, damit der akt. Stand nur einmal angeglichen werden muss. 

// erst alle Loesungen im groessten Cluster auf einen Stand bringen
	if(nproc[end_cluster] > 1)
		BcastSolution(*State,0,cluster[end_cluster], me[end_cluster]);
	for(i=1; i>=0 ; i--)	// beide Zeiten (update_needed == 0/1) ausmessen
	{
		for (actual_cluster=end_cluster;actual_cluster>=start_cluster;actual_cluster--)
		{
			comm_times[i][actual_cluster] = 0.;		// Initialisierung nicht vergessen !

			MPI_Barrier(cluster[actual_cluster]);
			for( j=0; j<nproc[actual_cluster]*FACTOR ; j++)
			{
				do
				{
					P->GetNeighbor(*State,Cooler->GetRelativeT());
					P->GetCost(*State);	// has to be done, because of the cycle (GetNeighbor,GetCost,{UpdateSolution | ResetSolution})
					founder = 0;
					if ( i )
					{
						if (nproc[actual_cluster] > 1)
						{
							if ( ((me[actual_cluster]+j) % nproc[actual_cluster]) == 0)
								founder = 1;
						}
						else
							founder = 1;
					}
					if ( ! founder )	/* Falls kein Uebergang gefunden werden soll*/
					{
						P->ResetSolution(*State);
					}
//if (myrank == 0 && i) std::cout <<"transmittion start\n";
//if(founder) std::cout<<"Found at n"<<myrank<<" act_cluster "<<actual_cluster<<std::endl;
					t = MPI_Wtime();
				} while ( !((this->*CommunicateInCluster_fp)( founder, ChooseMove , CommunicationMode, eq_dummy)== i) );	// je nachdem ob Loesung gefunden wurde oder nicht
				comm_times[i][actual_cluster] += MPI_Wtime() - t;
//if (myrank == 0 && i) std::cout <<"transmittion end\n";
			}
			comm_times[i][actual_cluster] /= FACTOR*nproc[actual_cluster];	// Mittelwerte bei FACTOR Versuchen
		}
//		for(j = end_cluster+1;j<MAXGROUPS;j++)	
//			comm_times[i][j]=0.;
	}

//// comm-times ueber all Rechnerknoten mitteln
//	double buffer[2][MAXGROUPS];
//	MPI_Reduce(&comm_times,&buffer,2*MAXGROUPS,MPI_DOUBLE,MPI_SUM,0,cluster[ncluster]);
//	
//	if( me[ncluster] == 0 )
//	{
//		for(j=0;j<=ncluster;j++)
//		{
//			comm_times[0][j] = buffer[0][j]/nproc[ncluster];
//			comm_times[1][j] = buffer[1][j]/nproc[ncluster];
//		}
//	}
//	P->Copy(*StateBuffer,*State);	// den Zustand wiederherstellen	
	actual_cluster = actual_cluster_save;
//std::cout <<myrank<<" MeasureCommTimes out\n";
}


SA_ClusteringSolver::~SA_ClusteringSolver()
{//debug(SA_ClusteringSolver::~SA_ClusteringSolver, myrank);
//MPE_Stop_log();
//MPE_Finish_log("FASA.log");
	MPI_Finalize();
//std::cout <<myrank<<" ~SA_ClusteringSolver()"<<std::endl;
}

// den gewaehlten SA-Algo ausfuehren
float	SA_ClusteringSolver::RunAnnealing()
{//debug(SA_ClusteringSolver::RunAnnealing, myrank);
//std::cout <<Algorithm<<" should be started!\n";

	if ( Algorithm == NULL )
	{
		if (myrank == 0 || myrank == -1)
			std::cout << "No algorithm specified !\n";
		return -1;
	}		
	else if ( strcmp(Algorithm, "SeqAlg") == 0 )
	{
		return SeqSimAnn();
	}
	else if ( strcmp(Algorithm, "ClusteredAlg") == 0 )
	{
		return ClusteredAnn();
	}
	else if ( strcmp(Algorithm, "ComputeLoopFactor") == 0 )
	{
		return ComputeLoopFactor();
	}
	else if ( strcmp(Algorithm, "Test") == 0 )
	{
		return Test();
	}
	else if ( strcmp(Algorithm, "TestProblem") == 0 )
	{
//dain(*P);
		return TestProblemImplementation();
	}
	else
	{
		if (myrank == 0 || myrank == -1)
			std::cout << "Unknown algorithm "<<Algorithm<<" specified!\n";
		return -1;
	}
}

// \******************************************************
// Methode ReadConfig - Liest die Konfigurations-
// daten ( geklammert mit '{' '}'  ) aus dem istream
// \******************************************************
int SA_ClusteringSolver::ReadConfig(std::istream & config)
{//debug(SA_ClusteringSolver::ReadConfig, myrank);

	char text[BUFLEN];
	config >> text; 
	if ( strcmp(text,"{") != 0)
	{
		std::cout << "Config file section for SA_ClusteringSolver does not begin with {!\n";
		return FALSE;
	}
	
	while (config >> text && ( strcmp(text,"}") != 0 ))
	{
		if (strcmp(text, "SA_Solver") == 0)
		{
			if ( ! SA_Solver::ReadConfig(config) )
			{
				std::cout <<"ReadConfing for Solver failed!\n";
				return 0;
			}
		}
		else if (strcmp(text, "SA_Scheduler") == 0)
		{
		// Instantiierung des Schedulers
			config >> text; 
			if (strcmp(text, "SA_EasyScheduler") == 0)
				{
					SetScheduler(new SA_EasyScheduler());
				}
			else if (strcmp(text, "SA_AartsScheduler") == 0)
				{
					SetScheduler(new SA_AartsScheduler());
				}
			else if (strcmp(text, "SA_TimeScheduler") == 0)
				{
					SetScheduler(new SA_TimeScheduler());
				}
			else
				{
					std::cout <<"Unknown Scheduler "<<text<<"!\n";
					return 0; 
				}
		// Einlesen der Konfigurationsdaten des Schedulers
			if ( ! Cooler->ReadConfig(config) )
			{
				std::cout <<"ReadConfing for Scheduler failed!\n";
				return 0;
			}
		}
	  else if (strcmp(text, "algorithm") == 0)
		{
		  config >> text; 
		  delete [] Algorithm;
		  Algorithm = new char[strlen(text)+1];
		  (strcpy(Algorithm, text) == 0);
		}
	  else if (strcmp(text, "CommunicateInCluster") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "Group") == 0)
		  {
			  CommunicateInCluster_fp = & SA_ClusteringSolver :: CommunicateInCluster;
		  }
		}
	  else if (strcmp(text, "CommunicationMode") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "Solution") == 0)
		  {
			  CommunicationMode  = SOLUTION;
		  }
		  else if (strcmp(text, "Move") == 0)
		  {
			  CommunicationMode  = MOVE;
		  }
		  else
			  std::cout <<"In SA_ClusteringSolver::ReadConfig unrecognized keyword \""<<text<<"\" for CommunicationMode! Leaving default mode Solution.\n";
		}
	  else if (strcmp(text, "Equilibrium") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "Local") == 0)
		  {
			  GlobalEquilibrium  = NOSYNC;
		  }
		  else if (strcmp(text, "Global") == 0)
		  {
			  GlobalEquilibrium  = ASYNC;
		  }
		  else
			  std::cout <<"In SA_ClusteringSolver::ReadConfig unrecognized keyword \""<<text<<"\" for Equilibrium! Leaving default mode Global.\n";
		}
	  else if (strcmp(text, "ConstantSizeMove") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "yes") == 0)	// Benutzer garantiert, dass das OutputMove stets gleiche Anzahl der Zeichen benutzt
		  {
			ConstantSizeMove = -1;	// Als Zeichen, dass Messung notwendig ist (erst spaeter durchfuehrbar) 
		  }
		}
	  else if (strcmp(text, "MinEff") == 0)
		{
		  config >> text; 
		  double buf = atof(text);
		  if ( 0 <= buf && buf <= 1.1)
			  MinEff = buf;
		  else
			  std::cout <<"Bad value for MinEff in the config file! Leaving default: clustering to maximize speedup*efficiency!"<<std::endl;
		}
	  else if (strcmp(text, "MaxCluster") == 0)
		{
		  config >> text; 
		  int buf = atoi(text);
		  if ( 0 <= buf && buf <= ncluster )
			  SetMaxCluster(buf);
		  else
		  {
			  SetMaxCluster(ncluster);
			  std::cout <<"Bad value "<<buf<<" for MaxCluster in the config file! Leaving default "<<maxcluster<<std::endl;
		  }
		}		
	  else if (strcmp(text, "ExchangeFunctions") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "MPI") == 0)
		  {
			  BcastFkt = PROBLEM;
		  }
		}
	  else if (strcmp(text, "DistributeSolutionAfterSubchain") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "no") == 0)
				{
					DoDistrSolAfterSubchain = NO;	// Default
				}
			else if (strcmp(text, "boltzmann") == 0)
				{
					DoDistrSolAfterSubchain = BOLTZMANN;
				}
			else if (strcmp(text, "random") == 0)
				{
					DoDistrSolAfterSubchain = RANDOM;
				}
			else if (strcmp(text, "best") == 0)
				{
					DoDistrSolAfterSubchain = BEST;
				}				
			else
				std::cout <<"Bad value for DistributeSolutionAfterSubchain in the config file! Leaving default BOLTZMANN.\n";
		}
	  else if (strcmp(text, "ChooseMove") == 0)
		{
		  config >> text; 
		  if (strcmp(text, "no") == 0)
				{
					std::cout <<"Bad value 'no' for ChooseMove in the config file! Leaving default first.\n";
					ChooseMove = FIRST;	// Default
				}
			else if (strcmp(text, "boltzmann") == 0)
				{
					ChooseMove = BOLTZMANN;
				}
			else if (strcmp(text, "random") == 0)
				{
					ChooseMove = RANDOM;
				}
			else if (strcmp(text, "first") == 0)
				{
					ChooseMove = FIRST;
				}
			else if (strcmp(text, "best") == 0)
				{
					ChooseMove = BEST;
				}				
			else
				std::cout <<"Bad value for DistributeSolutionAfterSubchain in the config file! Leaving default FIRST.\n";
		
			if ( ChooseMove != FIRST && (CommunicateInCluster_fp == & SA_ClusteringSolver::CommunicateInClusterAsyncFirst) )
			{
				CommunicateInCluster_fp = & SA_ClusteringSolver::CommunicateInClusterAsync;			
			}
		}
		
	  else 
		{
			std::cout <<"In SA_ClusteringSolver::ReadConfig unrecognized keyword \""<<text<<"\""<<std::endl;
		}
	}


	return (strcmp(text,"}") == 0 );
}


float SA_ClusteringSolver::ClusteredAnn()
{//debug(SA_ClusteringSolver::ClusteredAnn, myrank);
 
int ChainsAtLevel = 0; // hilfsvariable, um nur wenige teilketten bei jedem ClusteringLevel mit MPE zu protokollieren
 
	SA_ClusteringScheduler * ClustCooler = (SA_ClusteringScheduler *)Cooler;
	
	clock_t starttime, endtime;
	int		move_found, 
			frozen_flag, equilibrium_flag,
			eq_dummy=0;
			
	// Hilfsvariablen fuer die Messungen  waehrend des Laufs
#ifdef SHOW_TIMES	
	double	tim,nt;	// nummer der Iteration (echte, nicht gerechnete!),bei der letzter akz. "Ubergang gefunden wurde 		
#endif
	double	mes_t,mes_time_trans=0,mes_time_reset=0,dbl_buf;	
	int		mes_n_trans,mes_n_reset,mes_comm_n[2];
	
	if(maxcluster < 0 )	//  if maxcluster not set in the cfg-file
		SetMaxCluster(ncluster);
			
	InitStates();
	if( move == NULL)
		move = P->CreateMove();
			
	if ( ConstantSizeMove != 0)
		SetMoveSize();		
//Setzen der Cooling-Parameter 
	ClustCooler->StartClock();
	ClustCooler->WarmingUp(*P,*State,*BestSolution, cluster[maxcluster]);
	if( me[ncluster] == 0 )
		ShowConfig();
	MeasureCommTimes(0,maxcluster);
	actual_cluster = 0;
//	actual_cluster = (2<=maxcluster) ? 2 : 0; In diesem Fall soll DistributeSolutionAfterClustering() aufgerufen werden.
P->GetInitialSolution(*State);	// wichtig, falls initaccratio niedrig - allgemeinere L"osung gesucht
Cooler->SetStartE(P->GetCost(*State));
	starttime = clock();
 
 
	ClustCooler->SetClusterNumber( nproc[maxcluster]/nproc[actual_cluster],nproc[actual_cluster] );
	
	do
	{		
		DistributeSolutionAfterSubchain();	// ggf. auf die gleiche Startl"osung bringen - falls erw"unscht
//MPE_Log_event(5,0,"Start Chain");

		if( ClustCooler->GetDoClustering() )
		{
//MPE_Start_log();ChainsAtLevel = 0;
				actual_cluster = ClustCooler->GetActCluster();
//std::cout<<"n"<<myrank<<" act_cluster="<<actual_cluster<<std::endl;	
				ClustCooler->SetClusterNumber( nproc[maxcluster]/nproc[actual_cluster],nproc[actual_cluster] );
 
				if ( DoDistrSolAfterSubchain == NO )	// Sonst ist es bereits nach Ende (bzw. vor dem Anfang) der Kette erledigt
					DistributeSolutionAfterClustering();
		}
		equilibrium_flag = 0;
/* Bei geg. Temperatur eine Teilkette berechnen*/
mes_time_trans = mes_time_reset = mes_comm_time[0] = mes_comm_time[1] = mes_comm_n[0] = mes_comm_n[1] = mes_n_trans = mes_n_reset = 0; 
#ifdef SHOW_TIMES
measured_t0 = measured_e0 = measured_n = 0; nt = ClustCooler->GetTotalIter();tim = MPI_Wtime(); 
#endif
		do
		{
//MPE_Log_event(7,0,"");
mes_t = MPI_Wtime();
			P->GetNeighbor(*State,ClustCooler->GetRelativeT());
//MPE_Log_event(8,0,"");
			move_found = 0;
			if ( ClustCooler->TryAcceptance( P->GetCost(*State) )) 
//			if ( ClustCooler->Accept( P->GetCost(*State) )) 
			{
mes_time_trans +=MPI_Wtime()-mes_t;mes_n_trans++;
				// Communication im actual_cluster benoetigt,
				// da akzeptierter Uebergang gefunden
				move_found = 1;

				if (ClustCooler->BestFound() )
					P->Copy(*State,*BestSolution);	
			}
			else 
			{
mes_time_trans += (dbl_buf = MPI_Wtime())-mes_t;mes_n_trans++; mes_t = dbl_buf;
				P->ResetSolution(*State);
mes_time_reset += (dbl_buf = MPI_Wtime())-mes_t;mes_n_reset++; mes_t = dbl_buf;
			}

//MPE_Log_event(9,0,"StartAllreduce");			
mes_t = MPI_Wtime();			
			if ( (this->*CommunicateInCluster_fp)(move_found,ChooseMove,CommunicationMode,equilibrium_flag) )	// ggf. Uebergang mit den anderen Cluster-Mitglieder austauschen
			{
mes_comm_time[1]+=MPI_Wtime()-mes_t;mes_comm_n[1]++;
//MPE_Log_event(10,0,"EndAllreduce");
				ClustCooler->SetNewE(P->GetCost(*State));
#ifdef SHOW_TIMES
measured_t0 += MPI_Wtime()-tim;measured_n++; measured_e0 += ClustCooler->GetTotalIter() - nt;  
tim = MPI_Wtime(); nt = ClustCooler->GetTotalIter();
#endif
			}
			else
			{
mes_comm_time[0]+=MPI_Wtime()-mes_t;mes_comm_n[0]++;
//MPE_Log_event(10,0,"EndAllreduce");
 
				
				ClustCooler->LetOldE(nproc[actual_cluster]);		// Ketter um die Anzahl der Processore im akt. Cluster verlaengern
//				ClustCooler->LetOldE();	// Kette um Eins verlaengern
			}
			if ( me[actual_cluster] == 0 )	// falls Master
			{
 
				if( GlobalEquilibrium == ASYNC)
				{
					if (  me[maxcluster] == 0 )	// falls CHIEF
					{
						equilibrium_flag = ClustCooler->Equilibrium();
						end_chain[actual_cluster].MasterSync(equilibrium_flag);
					}
					else
					{
						equilibrium_flag = end_chain[actual_cluster].MasterSync();
					} 
				}
 
				else
					equilibrium_flag = ClustCooler->Equilibrium();
					
				if (equilibrium_flag)	// falls Equilibrium erreicht
				{
					(this->*CommunicateInCluster_fp)(0,MESSAGE,CommunicationMode,equilibrium_flag);
				}
			}
//if( ClustCooler->GetE() != P->GetCost(*State) ) 
//	std::cout <<"n"<<myrank<<": state cost mismatch GetE "<<ClustCooler->GetE() <<" GetCost "<<P->GetCost(*State)<<std::endl;

		} while ( ! equilibrium_flag);
//MPE_Log_event(6,0,"End Chain");											

// set the measured time-variables
		time_trans = mes_time_trans/mes_n_trans;
		time_reset = mes_time_reset/mes_n_reset;
		mes_comm_time[0] = mes_comm_time[0]/mes_comm_n[0]; 
		mes_comm_time[1] = mes_comm_time[1]/mes_comm_n[1];
//MPE_Log_event(3,0,"Start CollectSubchainStatistics");
		if ( me[actual_cluster] == 0)		// falls ich MASTER oder CHIEF bin
			ClustCooler->CollectSubchainStatistics( masters[actual_cluster]);
//MPE_Log_event(4,0,"End CollectSubchainStatistics");

// die Kommunikationszeiten neu messen - evtl. nur nach Feststellung, dass alte Messungen nicht stimmen
if( 0 && actual_cluster<maxcluster )
{
	if( VerboseMode )
	{
		OutputLambdas();
	}
	MeasureCommTimes(actual_cluster,actual_cluster+1);
}
#ifdef SHOW_TIMES
	if( VerboseMode )
	{
		OutputLambdas();
	}
#endif

		if ( me[maxcluster] == 0 )	// falls ich der Chief bin
		{
#ifdef SHOW_TIMES
			if ( myrank == 0 )
				std::cout<<"MES comm0 " <<comm_times[0][actual_cluster]<<" "<<mes_comm_time[0]
					<<" comm1 " <<comm_times[1][actual_cluster]<<" "<<mes_comm_time[1]<<std::endl;
#endif
			if ( DoClustering())
			{
				if ( VerboseMode && myrank == 0)
					std::cout << "DoClustering "<<actual_cluster<<"+1 bei ";
				ClustCooler->SetDoClustering(1);
				ClustCooler->SetActCluster(actual_cluster+1);
			}
			else
			{
				ClustCooler->SetDoClustering(0);
			}
		}
		if ( VerboseMode && myrank==0)
		{
			ClustCooler->OutputSubchainStatistics(std::cout);
			
///			P->PrintStatistics(*State,std::cout);
//			std::cout <<std::endl; 		
		}
			
//MPE_Log_event(11,0,"Start BroadcastSubchainOrder");
		frozen_flag = ClustCooler->BroadcastSubchainOrder(cluster[maxcluster]);
//MPE_Log_event(12,0,"End BroadcastSubchainOrder");

//{ChainsAtLevel++;if(ChainsAtLevel/5 == 0) MPE_Start_log();else if (ChainsAtLevel/5 == 1)	MPE_Stop_log();}
	} while ( ! frozen_flag );
	if (ClustCooler->TimeExceeded()) {
	  std::cout << "TIME LIMIT EXPIRED!!! \n Annealing process stoppt! \n";
	}
	endtime = clock();
	SATime = (endtime - starttime)/CLOCKS_PER_SEC;
	
	BcastBestSolution(MPI_COMM_WORLD);
	PostprocTime = clock();	
	P->Postprocessing(*BestSolution);
	PostprocTime = (clock() - PostprocTime)/CLOCKS_PER_SEC;

	WriteSolutionParallel(MPI_COMM_WORLD);
	WriteLog(me[maxcluster]==0,chiefs,cluster[maxcluster]);
	if( VerboseMode )
	{
		OutputLambdas();
	}

	return P->GetCost(*BestSolution);
}

// Fuer geg. Problem den benoetigten subchainfactor bestimmen
float	SA_ClusteringSolver::ComputeLoopFactor()
{//debug(SA_ClusteringSolver::ComputeLoopFactor, myrank);

	float	LF=1.0,
			step = 0.5,
			c;
		
	SA_AartsScheduler * as	 = (SA_AartsScheduler *) Cooler;
	
	std::cout << "ClusteringSolver computes loop factor ";
	while ( LF < 100 )	// sehr lange :)
	{
		as->SetLoopFactor(LF);
		c = ClusteredAnn();
//		as->OutputStatistics(std::cout); std::cout <<std::endl;
		std::cout << ".";
		as->Reset();
		LF += step;
	}
	std::cout << std::endl;
	return c;
}

// Austauschfunktion fuer alle CommunicateInCluster 
// liefert 0 falls Fehler waehrend des Austauschs
int SA_ClusteringSolver::ExchangeState(int moved, int root,COMM_MODE comm_m)
// Ueberlegen : evtl. muesste ResetSolution bei comm_m NICHT durchgefuehrt werden, 
// da Zeitaufwendig und die Loesung wird sowieso komplett uebernommen 
{//debug(SA_ClusteringSolver::ExchangeState, myrank);
//MPE_Log_event(1,0,"StartCommCluster");
	int errstate = 1;
	
	if( moved && (me[actual_cluster] != root))	// Falls mein akzeptierter Uebergang NICHT genommen wurde
	{
		P->ResetSolution(*State);
	} 
	
	if( comm_m == SOLUTION )
	{
		if ( me[actual_cluster] == root )
		{
			P->UpdateSolution(*State);
		}
		if ( nproc[actual_cluster] > 1 )
			errstate = BcastSolution(*State, root, cluster[actual_cluster], me[actual_cluster]);
	}
	else if ( comm_m == MOVE )
		if ( nproc[actual_cluster] > 1 )
			errstate = BcastApplyMove(*State, root, cluster[actual_cluster], me[actual_cluster]);
	else
	{
		std::cout <<"Unknown communication mode "<<comm_m<<std::endl;		  
		errstate =  0;
	}
//MPE_Log_event(2,0,"EndCommCluster");
	
	return errstate;
}
int SA_ClusteringSolver::CommunicateInClusterOld(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE comm_m, int & equilibrium)
// verallgemeingerte "Accept" : einen der akzeptierten Uebergang ermitteln und ggf. auf
// alle Prozessoren verteilen
{//debug(SA_ClusteringSolver::CommunicateInClusterOld, myrank);
	
	if (nproc[actual_cluster] == 1)		// Falls trivialer Cluster
	{
		if( move_accepted )
			P->UpdateSolution(*State);
		return move_accepted;
	}
  ////MPE_Log_event(9,0,"StartAllreduce");
// Communication im actual_cluster gefordert?
	
	int moved = move_accepted;
	
	if (  exch_m == MESSAGE)
		move_accepted = 1;
		
	int update_need;
	MPI_Allreduce(&move_accepted,&update_need,1,MPI_INT,MPI_LOR,cluster[actual_cluster]);

	if ( !update_need )
		return 0;
	float cost = P->GetCost(*State);
	if (  exch_m == MESSAGE) // eine negative Nachricht verschicken
	{
		move_accepted = 1;
		cost = -1;	
	}
	
	int root=0;	// Nummer des Prozessors, dessen Zustand uebernommen wird
	if (sync[actual_cluster].ClusterSyncGroup( move_accepted,cost,exch_m,&root ) )
	{
		ExchangeState(moved, root ,comm_m);
		return 1;
	}
	else if (root < 0)	// Falls eine Nachricht uebermittelt wurde
	{
		equilibrium = 1;
		if(moved)	// Falls aber mein Uebergang akzeptiert wurde 
		{
			P->ResetSolution(*State);
		}
	}
	return 0;		
}
int SA_ClusteringSolver::CommunicateInCluster(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE comm_m, int & equilibrium)
// verallgemeingerte "Accept" : einen der akzeptierten Uebergang ermitteln und ggf. auf
// alle Prozessoren verteilen;
// veraenderte Version : erheblich schneller bei gefunden,
//						 leicht langsamer bei nicht gefunden.
{//debug(SA_ClusteringSolver::CommunicateInCluster, myrank);

	if (nproc[actual_cluster] == 1)		// Falls trivialer Cluster
	{
		if( move_accepted )
			P->UpdateSolution(*State);
		return move_accepted;
	}
	
	int moved = move_accepted;
	float cost = P->GetCost(*State);
	if (  exch_m == MESSAGE) // eine negative Nachricht verschicken
	{
		move_accepted = 1;
		cost = -1;	
	}
	
	int root=0;	// Nummer des Prozessors, dessen Zustand uebernommen wird
	if (sync[actual_cluster].ClusterSyncGroup( move_accepted,cost,exch_m,&root ) )
	{
		ExchangeState(moved, root ,comm_m);
		return 1;
	}
	else if (root < 0)	// Falls eine Nachricht uebermittelt wurde
	{
		if(moved)	// Falls aber mein Uebergang akzeptiert wurde 
		{
			P->ResetSolution(*State);
		}
		equilibrium = 1;
	}
	return 0;		
}

int SA_ClusteringSolver::CommunicateInClusterAsync(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE comm_m, int & equilibrium)
// verallgemeingerte "Accept" : einen der akzeptierten Uebergang ermitteln und ggf. auf
// alle Prozessoren verteilen;
// Durch Benutzung von (nonblocking) Send/Receive  verbesserte Version
// 
{//debug(SA_ClusteringSolver::CommunicateInClusterAsync, myrank);
 
	if (nproc[actual_cluster] == 1)		// Falls trivialer Cluster
	{
		if( move_accepted )
			P->UpdateSolution(*State);
		return move_accepted;
	}

	int moved = move_accepted;
	float cost = P->GetCost(*State);
	if (  exch_m == MESSAGE) // eine negative Nachricht verschicken
	{
		move_accepted = 1;
	}
	
	int root=0;	// Nummer des Prozessors, dessen Zustand uebernommen wird
	if (sync[actual_cluster].ClusterSync( move_accepted,cost,exch_m,&root ) )
	{
		ExchangeState(moved, root ,comm_m);
		return 1;
	}
	else if (root < 0)	// Falls eine Nachricht uebermittelt wurde
	{
		equilibrium = 1;
		if(moved)	// Falls aber mein Uebergang akzeptiert wurde 
		{
			P->ResetSolution(*State);
		}
	}
	return 0;	
}

int SA_ClusteringSolver::CommunicateInClusterAsyncFirst(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE comm_m, int & equilibrium)
// verallgemeingerte "Accept" : einen der akzeptierten Uebergang ermitteln und ggf. auf
// alle Prozessoren verteilen;
// Durch Benutzung von (nonblocking) Send/Receive  verbesserte Version
// Sonderausf"uhrung f"ur FIRST-Modus
{//debug(SA_ClusteringSolver::CommunicateInClusterAsyncFirst, myrank);
 
	if (nproc[actual_cluster] == 1)		// Falls trivialer Cluster
	{
		if( move_accepted )
			P->UpdateSolution(*State);
		return move_accepted;
	}

	int moved = move_accepted;
	float cost = P->GetCost(*State);
	if (  exch_m == MESSAGE) // eine negative Nachricht verschicken
	{
		move_accepted = 1;
	}
	
	int root=0;	// Nummer des Prozessors, dessen Zustand uebernommen wird
	if (sync[actual_cluster].ClusterSyncFirst( move_accepted,cost,exch_m,&root ) )
	{
		ExchangeState(moved, root ,comm_m);
		return 1;
	}
	else if (root < 0)	// Falls eine Nachricht uebermittelt wurde
	{
		equilibrium = 1;
		if(moved)	// Falls aber mein Uebergang akzeptiert wurde 
		{
			P->ResetSolution(*State);
		}
	}
	return 0;	
}


// \******************************************************
// Methode OutputStatistics - Statistiken des Laufs in ein stream schreiben (Mit std::endl!)
// \******************************************************
void SA_ClusteringSolver::CreateLog(std::ostream & output, MPI_Comm comm)
{//debug(SA_ClusteringSolver::OutputStatistics, myrank);

// Besten Kostenwert nach dem Postprocessing ermitteln
	float	BestBuff,
			BestPostE = P->GetCost(*BestSolution);
			
	if ( OptType == Opt::MIN )
		MPI_Reduce(&BestPostE,&BestBuff,1,MPI_FLOAT,MPI_MIN,0,comm);
	else
		MPI_Reduce(&BestPostE,&BestBuff,1,MPI_FLOAT,MPI_MAX,0,comm);

	int me,nproc;
	
	MPI_Comm_rank(comm,&me);
	MPI_Comm_size(comm,&nproc);


	if (me == 0)
	{
//  Ausgabe der Daten: Solv= Solver, NPROC=Anzahl der Prozessoren, F=Dateiname, Z=Lese-/Rechenzeit 
		output
			<< "Solv=Cluster NPROC=" << nproc
			<< " F=" << filename(DataFileName)
			<< " Z=" << FileReadTime << "/" << InitialSolutionTime << "/" << SATime << "/" << PostprocTime
			<< " StrtSl=" << ( GetInitialSolution_fp == & SA_Problem::GetRandomSolution ? "Rnd":"Init")
			<< " ClstrCmm=" << ( CommunicateInCluster_fp == & SA_ClusteringSolver::CommunicateInCluster ? "Grp" : "Asnc" )			
			<< " ChMv="<< (  ChooseMove == FIRST  ? "first" : 
							(ChooseMove == BEST   ? "best" :
							(ChooseMove == RANDOM ? "rnd":"boltz")))
			<< " CommM=" << ( CommunicationMode == MOVE ? "Mv" : "Sl")
			<< " Equil=" << (GlobalEquilibrium == ASYNC? "Glob" : "Loc")
			<< " MinEff=" << MinEff
			<< " DoDistr=" << ( DoDistrSolAfterSubchain == NO ? "no" : 
							  ( DoDistrSolAfterSubchain == RANDOM ? "rnd": (DoDistrSolAfterSubchain == BEST ? "best":"boltz" ) ) );
		output << " ";
		Cooler->CreateLog(output,comm);
	    output << " PostE=" << BestBuff <<std::endl;
	}
	else
	{
		Cooler->CreateLog(output,comm);
	}
}

// \******************************************************
// Methode ShowConfig - Gibt die aktuelle Konfiguration
// aus (nur zur Kontrolle).
// \******************************************************
void SA_ClusteringSolver::ShowConfig()
{//debug(SA_ClusteringSolver::ShowConfig, myrank);
	std::cout<< "SA Konfiguration:" << std::endl
		<< "\tEingabedatei:      " << DataFileName << std::endl
		<< "\tAusgabedatei:      " << OutputFileName << std::endl
		<< "\tStartSolution:     " << ( GetInitialSolution_fp == & SA_Problem::GetRandomSolution ? "Random":"Initial") <<std::endl;
	if (  maxcluster < ncluster)		
		std::cout<< "\tMaxCluster:        " << maxcluster << " von " <<ncluster << std::endl;
	std::cout<< "\tClusterComm:       " << ( CommunicateInCluster_fp == & SA_ClusteringSolver::CommunicateInCluster ?  "Group" : "Async" )<<std::endl
		<< "\tChooseMove:        " << (  ChooseMove == FIRST  ? "First" : 
										(ChooseMove == BEST   ? "Best" :
										(ChooseMove == RANDOM ? "Random":"Boltzmann"))) << std::endl
		<< "\tCommunicationMode: " << ( CommunicationMode == MOVE ? "Move" : "Solution") << std::endl
		<< "\tEquilibrium:       " << ( GlobalEquilibrium == ASYNC ? "Global" : "Local") << std::endl;
	if( MinEff >1) std::cout
		<< "\tClustering:        MAX Speedup*Efficiency\n";
	else if (MinEff > 0) std::cout
		<< "\tClustering:        MAX size with efficiency >= "<<MinEff<<std::endl;
	else std::cout
		<< "\tClustering:        MIN tau_0\n";
	std::cout<< "\tDoDistr:           " << ( DoDistrSolAfterSubchain == NO ? "no" : 
									  ( DoDistrSolAfterSubchain == RANDOM ? "random": ( DoDistrSolAfterSubchain == BEST ? "best":"bolzmann" ) ) ) << std::endl;
 
	if ( ConstantSizeMove != 0)
		std::cout << "\tConstantSizeMove:  yes\n";
	Cooler->ShowConfig(std::cout);


}

// Zeit bis zu einem erfolgten Uebergang im Cluster des Levels clst bei geg. Erwartungswert in diesem Cluster absch"atzen
double SA_ClusteringSolver::EstimateT(int clstr,double e_clstr)
{//debug(SA_ClusteringSolver::EstimateT, myrank);
	if (clstr == actual_cluster)
		return e_clstr*time_trans + (e_clstr-1)*(time_reset+mes_comm_time[0]) + mes_comm_time[1];
	else
		return e_clstr*time_trans + (e_clstr-1)*(time_reset+comm_times[0][clstr]) + comm_times[1][clstr];
}
// dilation ratio nach  Aarts (86) Seite 223  
double SA_ClusteringSolver::EstimateDilation(int clstr,double e_one,double e_clstr)
{//debug(SA_ClusteringSolver::EstimateDilation, myrank);
 
	double	efficiency_ratio,
			waiting_ratio,
			dilation;
#ifdef DEBUG
	if (clstr > ncluster)
	{
		std::cout <<"n"<<myrank<<" Error in EstimateDilation: "<<clstr<<" is more than greatest clustering level "<<ncluster<<std::endl;
		return 10.0;
	}
#endif
	
	efficiency_ratio = 1.0/(1+(nproc[clstr]-1)/e_one);
	
	if (clstr == actual_cluster)
	{	
		waiting_ratio = ((e_clstr-1)*mes_comm_time[0] + mes_comm_time[1])/EstimateT(clstr,e_clstr);
	}
	else
	{
		waiting_ratio = ((e_clstr-1)*comm_times[0][clstr] + comm_times[1][clstr])/EstimateT(clstr,e_clstr);
	}
	dilation = 1.0/((1-waiting_ratio)*efficiency_ratio);
 
#ifdef SHOW_TIMES 
std::cout<<"Bei Clusterlevel "<<clstr <<" eff_r "<<efficiency_ratio<<" wait_r "<<waiting_ratio<<" dilation_r "<<dilation<<std::endl;
#endif
 
	return dilation;
}

//double SA_ClusteringSolver::EstimateSpeedup(int clstr,double e_one,double e_clstr)
//{//debug(SA_ClusteringSolver::EstimateSpeedup, myrank);
//
//
//}

// True <=> in second cluster the product Eff*Speedup is better when in first
// clstr is the number of the first cluster, the second has the number clstr+1
bool SA_ClusteringSolver::BetterEffSp(int clstr,double e_single,double e_first, double e_second)
{//debug(SA_ClusteringSolver::BetterEffSp, myrank);
	double	Sp1,Sp2,
			t0,t1,t2;
	
	t0 = EstimateT(0,e_single);
	t1 = EstimateT(clstr,e_first);
	t2 = EstimateT(clstr+1,e_second);
	
	Sp1 = t0/t1;
	Sp2 = t0/t2;
	
#ifdef SHOW_TIMES
std::cout <<"E1 "<<Sp1/nproc[clstr] <<" SE1 "<<Sp1*Sp1/nproc[clstr] <<" E2 "<<Sp2/nproc[clstr+1]<<" SE2 "<< Sp2*Sp2/nproc[clstr+1]<<std::endl;
#endif
	return Sp1*Sp1/nproc[clstr] < Sp2*Sp2/nproc[clstr+1]; 
}

 
// Lohnt es sich, Clustergroesse zu verdoppeln
// die Entscheidung wird auf dem Proc 0 getroffen und dann 
// mit Hilfe von Scheduler verteilt
int SA_ClusteringSolver::DoClustering()
{//debug(SA_ClusteringSolver::DoClustering, myrank);

#ifndef SHOW_TIMES
	if (actual_cluster >= maxcluster)
	{
//std::cout<<"Cluster "<<actual_cluster<<std::endl;
		return 0;
	}
#endif
		
	int clustering = 0; // nicht clustern
// Zeiten, um einen akzeptierten Uebergang im aktuellen (t[0]) und (geschaetzt) im vergroesserten (t[1]) Cluster zu finden und zu verteilen
		
	if( me[maxcluster] == 0 )	// nur auf Proc 0
	{
		SA_ClusteringScheduler * as = (SA_ClusteringScheduler *)Cooler;
		double t0 = 0.0,
			t1 = 0.0,
			e0,e1,e1a,e1u,
			u_r0 = as->GetMeanUpdateRatio(),
			a_r0 = as->GetMeanAcceptRatio();
			
		if( u_r0 == 0.0)	// falls kein einziger Uebergang gefunden wurde
		{
#ifndef SHOW_TIMES
			clustering = 1;
#endif
		}
		else
		{
			e0 = 1.0/u_r0;
			if ( e0 < 1.1 )	// falls fast jeden Schritt Uebergang gefunden wurde
			{
				clustering = 0;
			}
			else
			{
#ifdef SHOW_TIMES
				t0 = EstimateT(actual_cluster,e0);
if(actual_cluster < maxcluster){
#endif
				e1u = 1.0/(1-pow( 1-u_r0 , nproc[actual_cluster+1]*1.0/nproc[actual_cluster] ));	// Schaetzung aufgrund von UpdateRatio
				e1a = 1.0/(1-pow( 1-a_r0 , nproc[actual_cluster+1]*1.0/nproc[0] ));	//Schaetzung aufgrund von AcceptRatio
				e1 = ( e1u+e1a) /2;		//Endgueltige Schaetzung
#ifdef SHOW_TIMES
				t1 = EstimateT(actual_cluster+1,e1);
}
				if( VerboseMode)
					EstimateDilation(actual_cluster,1.0/a_r0,e0);	// wegen der Ausgaben
#endif
				if( MinEff > 1.0 )	// Entscheidung nach Speedup*Effizienz -> MAX
				{
					 if (BetterEffSp(actual_cluster,1.0/a_r0,e0,e1))
						 clustering = 1;
				}
				else if ( MinEff > 0 )
				{
					if( EstimateDilation(actual_cluster+1,1.0/a_r0,e1) < 1/MinEff)
						clustering = 1;
				}
				else	// Entscheidung nach t1 < t0
				{
					if( EstimateT(actual_cluster,e0) > EstimateT(actual_cluster+1,e1))
						clustering = 1;
				}
 
#ifdef SHOW_TIMES
				if( myrank == 0 )
				{
					std::cout<<Cooler->GetTotalIter()<<" "<<Cooler->GetE()<<" "<<Cooler->GetBestE()<<" "<<Cooler->GetT()
						<<" Clstr "<<actual_cluster
						<<" gemessen t0= "<<measured_t0/measured_n	<<" e0= "<<measured_e0/measured_n 
														<<" errechnet e0= "<<e0
						<<" geschaetzt t0= "<<t0 <<" e0= "<<1.0/(1-pow(1-a_r0,nproc[actual_cluster]));
					if(actual_cluster < maxcluster)
						std::cout <<" t1= "<<t1<<" e1= "<<e1<<" e1u= "<<e1u<<" e1a= "<<e1a;
					else // damit der Ausgabeformat gleich bleibt und die Zeichentools nicht irritiert werden
						std::cout <<" t1= "<<0<<" e1= "<< 1<<" e1u= "<<1<<" e1a= "<<1;
					std::cout <<" e_single= "<<1/a_r0<<std::endl;
				}
#endif
			}
		} 
		if( clustering && actual_cluster < maxcluster && 1.0/a_r0 < nproc[actual_cluster+1])
		{		
			clustering = false;
			std::cout << "Don't cluster too early!\n";
		}
	}
#ifdef SHOW_TIMES
if(actual_cluster >= maxcluster){ return 0;}	
#endif

	return clustering;
}

// Gibt ein Abschaetzung aus, bei welcher Akzeptanzrate jeweils Clustering erfolgt, 
// in Abhaengigkeit von time_accept, time_reset_old und comm_times
// Nur auf Proc0 sinnvoll !
// gar nicht mehr sinnvoll
void SA_ClusteringSolver::EstimateClusteringPoints()
{//debug(SA_ClusteringSolver::OutputLambdas, myrank);

	if ( me[ncluster] != 0 ) 
		return;	
	if ( ncluster <= 0 )
	{
		return;
	}
	
std::cout<<"DIES IST EINE VERAELTETE ABSCHAETZUNG!\n";	
	std::cout <<"Pruefe den voraussichtlichen Zeitpunkt der Veraenderung des Clusterungslevels:\n";

	int act_cluster=0,	// der aktuelle Cluster
		ChainLength = (int)ceil(P->GetLocalN()),	// bis welcher Kettenlaenge pruefen 
		erw = 1;		// Erwartungswert auf einem Prozessor
	double a_r0,e0,e1,t0,t1;
	do
	{
		
		a_r0 = 1.0/erw;
		e0 = 1.0/(1-pow( 1-a_r0 , nproc[act_cluster]*1.0/nproc[0] ));
		e1 = 1.0/(1-pow( 1-a_r0 , nproc[act_cluster+1]*1.0/nproc[0] ));	//Schaetzung aufgrund von AcceptRatio
		t0 = EstimateT(act_cluster,e0);
		t1 = EstimateT(act_cluster,e1);
//std::cout<<erw<<" "<<e0<<" "<<e1<<" "<<t0<<" "<<t1<<std::endl;
		if ( t1/t0 > MinEff )
		{
			std::cout <<act_cluster<<" ->"<<act_cluster+1<<" bei Erwartungswert auf einem Proc="<<erw<<std::endl;
			act_cluster++;
		}
		erw++;
 
	} while (	act_cluster < ncluster &&
				erw < 10*ChainLength);
	if (act_cluster == 0 )
		std::cout << "Keine Veraenderung sinnvoll bis zum Erwartungswert auf einem Proc="<<erw<<" ,Kettenlaenge="<<ChainLength<<std::endl<<std::endl; 
	else
		std::cout<<std::endl<<std::endl;
}
 
 
// gibt das Verhaeltnis BroadcastState/ComputePerturbation 
//	fuer alle Clustergroessen aus
// Sinnvoll erst NACH WarmingUpTimed
// gar nicht mehr sinnvoll
void SA_ClusteringSolver::OutputLambdas(int procnr)
{//debug(SA_ClusteringSolver::OutputLambdas, myrank);
	if (myrank != procnr )
		return;
	if (ncluster < 1)
		return;
	int i;
	std::cout <<"n"<<procnr <<": Verhaeltnisse von der Verteilungs- zu Uebergangszeiten sind:\n";
	for( i = 1; i <=ncluster ; i++)
	{
		std::cout<<"In Cluster["<<i<<"]="<<comm_times[1][i]/(time_trans+comm_times[1][0])
			<<"\t bzw "<<comm_times[0][i]/(time_trans+time_reset+comm_times[0][0])<<" fuer nicht-akzeptierten Uebergang"<<std::endl;
	}
	std::cout << std::endl;
}


int SA_ClusteringSolver::BcastSolution(SA_Solution &sol, int root, MPI_Comm comm, int me_comm)
{//debug(SA_ClusteringSolver::BcastSolution, myrank);
	if (BcastFkt == PROBLEM) {
		return	P->BcastSolution(sol, root, comm, me_comm);
	 } else {
		return  BcastSolution_my(sol, root, comm, me_comm);
	 }
}

/**
  Broadcasts the solution by the root of the communicator.
  @param sol
  the solution which is to be broadcasted
  @param comm
  MPI communicator in which the solution is to be broadcasted 
  @param me_comm
  root, if I am the sender
  @returm
  successmode, 0 if successful 1 else 
*/
int SA_ClusteringSolver::BcastSolution_my(SA_Solution &sol, int root, MPI_Comm comm, int me_comm)
{//debug(SA_ClusteringSolver::BcastSolution_my, myrank);

	int buflen, succ_code;
	if ( me_comm == root ) 
	{
		std::ostrstream solution_stream;
		P->OutputSolution(solution_stream,sol);
		char * solution_buffer = solution_stream.str();
		buflen = solution_stream.pcount();
		MPI_Bcast(&buflen,1,MPI_INT,root,comm); // bcast the length of the solution stream
		succ_code = 
			MPI_Bcast(solution_buffer,buflen,MPI_BYTE,root,comm)  // bcast the solution stream
			== MPI_SUCCESS;
		delete solution_buffer;
	}
	else
	{
		MPI_Bcast(&buflen,1,MPI_INT,root,comm);		// get the length of the solution stream
		char * solution_buffer = new char[buflen];
		MPI_Bcast(solution_buffer,buflen,MPI_BYTE,root,comm); // get the soltution stream
		std::istrstream solution_stream(solution_buffer,buflen);
		succ_code = P->InputSolution(solution_stream,sol); // read the recieved solution stream
		delete solution_buffer;		// must be done
	}	
	return succ_code;
}
	
// Unter Voraussetzung, dass alle Loesungen im comm gleich bis auf die von root sind, 
// und die letzte sich durch genau einen Uebergang unterscheidet,
// bringe alle Loesungen auf den gleichen Stand;
// Nicht vergessen : UpdateSolution() auf die Loesung von root anzuwenden 
int	SA_ClusteringSolver::BcastApplyMove_my(SA_Solution &sol, int root, MPI_Comm comm, int me_comm)
{//debug(SA_ClusteringSolver::BcastApplyMove_my, myrank);

	int buflen, errstatus=0;
	
	if ( me_comm == root ) 
	{
		std::ostrstream solution_stream;
		P->ExtractMove(sol,*move);
		P->OutputMove(solution_stream,*move);
		char * solution_buffer = solution_stream.str();
		if ( ConstantSizeMove == 0 )	// falls Groesse von Move variabel ist
		{
			buflen = solution_stream.pcount();
			MPI_Bcast(&buflen,1,MPI_INT,root,comm);
		}
		else
			buflen = ConstantSizeMove;
		MPI_Bcast(solution_buffer,buflen,MPI_BYTE,root,comm);
		delete solution_buffer;
		P->UpdateSolution(sol);
	}
	else
	{
		if ( ConstantSizeMove == 0 )	// falls Groesse von Move variabel ist
			MPI_Bcast(&buflen,1,MPI_INT,root,comm);
		else
			buflen = ConstantSizeMove;
		char * solution_buffer = new char[buflen];
		MPI_Bcast(solution_buffer,buflen,MPI_BYTE,root,comm);

		std::istrstream solution_stream(solution_buffer,buflen);
		errstatus = P->InputApplyMoves(solution_stream,sol);
			if ( errstatus != 1 )
			{
				std::cout <<"Auf Prozessor "<<myrank<<" in SA_ClusteringSolver::BcastApplyMove : Fehler bei Ausfuehrung des Schrittes!\n";
				errstatus = 1;
			}
		delete solution_buffer;		//MUSS gemacht werden
	}	

	return errstatus;
}
 
int	SA_ClusteringSolver::BcastApplyMove(SA_Solution &sol, int root, MPI_Comm comm, int me_comm)
{//debug(SA_ClusteringSolver::BcastApplyMove, myrank);

	if (BcastFkt == PROBLEM)
		return	P->BcastApplyMove(sol, root, comm, me_comm);
	else
		return  BcastSolution_my(sol, root, comm, me_comm);
}
// gemeinsame Startloesung in jeden Cluster  ermitteln und verteilen
void SA_ClusteringSolver::DistributeSolutionAfterClustering(void)
{//debug(SA_ClusteringSolver::DistributeSolutionAfterClustering, myrank);
//std::cout <<"n"<<myrank<<": DistributeSolutionAfterClustering in cluster "<<actual_cluster<<" nproc "<<nproc[actual_cluster]<<std::endl; 
	
	if ( nproc[actual_cluster] > 1 )
	{
		int		root = -1; // Nummer des Halter der ausgewaehlten Loesung
int BOLZMAN=0;	// TRUE fuer Bolzman, False fuer Random
		if(BOLZMAN)
		{
			float	Cost = P->GetCost(*State),
					*CostBuffer = NULL;
 
			if ( me[actual_cluster] == 0 )
			{// Buffer fuer alle Kosten anlegen
				CostBuffer = new float[nproc[actual_cluster]];
			}
			MPI_Gather(&Cost,1,MPI_FLOAT,CostBuffer,1,MPI_FLOAT,0,cluster[actual_cluster]);	// Kosten sammeln
			if ( me[actual_cluster] == 0 )
			{
				int i=0;
				float InitialCost = Cooler->GetStartE();
				CostBuffer[i] = exp( (InitialCost-CostBuffer[i])/Cooler->GetT() );
				for(i=1;i<nproc[actual_cluster];i++)
					CostBuffer[i] = CostBuffer[i-1]+ exp( (InitialCost-CostBuffer[i])/Cooler->GetT() );
				float rnd = rand_float()*CostBuffer[nproc[actual_cluster]-1];
				root = 0;
				while( CostBuffer[root] < rnd && root < nproc[actual_cluster])
					root++;
			}
		}
		else // RANDOM
		{
			root = rand_int(nproc[actual_cluster]);
		}
root = nproc[actual_cluster]-1;
		MPI_Bcast(&root,1,MPI_INT,0,cluster[actual_cluster]);
//root = 0;
 
//std::cout <<"n"<<myrank<<": "<<actual_cluster<<": in cluster von "<<me[actual_cluster]<<" solution von "<<root<<" choosed!\n";
		BcastSolution(*State,root,cluster[actual_cluster],me[actual_cluster]);
//ShowCluster(actual_cluster,true);	
		if (me[actual_cluster] != root )	// my State has been changed
		{
			Cooler->SetNewE(P->GetCost(*State));
		}
//std::cout <<"n"<<myrank<<": DistributeSolutionAfterClustering in cluster "<<actual_cluster<<" E= "<<Cooler->GetE()<<" GetCost="<<P->GetCost(*State)<<std::endl;
	}
	
	return;
}
 
 
// gleiche Startloesung fuer ALLE nach Aarts Seite 227  ermitteln und verteilen
void SA_ClusteringSolver::DistributeSolutionAfterSubchain(void)
// erste Version: nuetzt die Tatsache, dass im Gewinner-Cluster die Loesung bereits an allen Knoten anliegt,
// NICHT aus.
{//debug(SA_ClusteringSolver::DistributeSolutionAfterSubchain, myrank);
 
	if ( DoDistrSolAfterSubchain == NO || actual_cluster == maxcluster)
		return;
	else		
	{
//MPE_Log_event(103,0,"Start DistributeSolutionAfterSubchain");

		int		root = -1; // Nummer des Halter der ausgewaehlten Loesung
 
		if( me[actual_cluster] == 0 ) // falls ich CHIEF oder MASTER bin
		{
			int		n_masters;	// Anzahl der Cluster
			MPI_Comm_size(masters[actual_cluster],&n_masters);
 
			if( DoDistrSolAfterSubchain == RANDOM )
			{
				root = rand_int(nproc[maxcluster]);
	//std::cout<<"After subchain solution of cluster "<<root<<" choosen!\n";
			}
			else // Werte m"ussen gesammelt werden
			{
				float	Cost = P->GetCost(*State),
						*CostBuffer = NULL;
 
				if ( me[maxcluster] == 0 )
				{// Buffer fuer alle Kosten anlegen
					CostBuffer = new float[n_masters];
				}
				MPI_Gather(&Cost,1,MPI_FLOAT,CostBuffer,1,MPI_FLOAT,0,masters[actual_cluster]);	// Kosten sammeln
				if ( me[maxcluster] == 0 )
				{
						int i=0;
	//for(i=0;i<n_masters;i++) std::cout<<" " <<CostBuffer[i]; std::cout<<std::endl;			
					if( DoDistrSolAfterSubchain == BOLTZMANN || DoDistrSolAfterSubchain == BEST )
					{
/*besten Wert berechnen */
						float best = CostBuffer[0];
						root = 0;
						for(i=1;i<n_masters;i++)
						{
							if ( Cooler->Better(CostBuffer[i],best) )
							{
								best = CostBuffer[i];
	//std::cout <<"Best "<< best <<std::endl;
								root = i;
							}
						}
						
						if ( DoDistrSolAfterSubchain == BOLTZMANN )
						{
/* entsprechen der Bolztmann-Verteilung ausgehend vom Unterschied zum Besten*/
							float temp = Cooler->GetT();
							CostBuffer[0] = exp( -fabs(best-CostBuffer[0])/ temp );
							for(i=1;i<n_masters;i++)
							{
								CostBuffer[i] = CostBuffer[i-1] + exp( -1*fabs(best-CostBuffer[i])/ temp );
							}
							float rnd = rand_float()*CostBuffer[n_masters-1];
							root = 0;
							while( CostBuffer[root] < rnd && root < n_masters)
								root++;
	//for(i=0;i<n_masters;i++) std::cout<<" " <<CostBuffer[i]; std::cout<<" "<<rnd<<std::endl;						
							
						}
					}
					
					int root_clst = root;
					MPI_Group_translate_ranks(masters_group[actual_cluster],1,&root_clst,cluster_group,&root);
	//std::cout<<"After subchain solution of cluster "<<root_clst<<" Proc "<<root <<" choosen "<<std::endl;        
				}
			}
		}
		MPI_Bcast(&root,1,MPI_INT,0,cluster[maxcluster]);
		BcastSolution(*State,root,cluster[maxcluster],me[maxcluster]);
 
		if (me[actual_cluster] != root )	// my State has been changed
		{
			Cooler->SetNewE(P->GetCost(*State));
		}
//MPE_Log_event(104,0,"End DistributeSolutionAfterSubchain");
	}
	
	return;
}
 
// Setzt ConstantSizeMove
void SA_ClusteringSolver::SetMoveSize(void)
{//debug(SA_ClusteringSolver::SetMoveSize, myrank);

	P->GetNeighbor(*State,Cooler->GetRelativeT());
	std::ostrstream solution_stream;
	P->ExtractMove(*State,*move);
	P->ResetSolution(*State);
	P->OutputMove(solution_stream,*move);
	char * solution_buffer = solution_stream.str();
	ConstantSizeMove = solution_stream.pcount();	
	delete solution_buffer;	
}

int	SA_ClusteringSolver::TestProblemImplementation()
{//debug(SA_ClusteringSolver::TestProblemImplementation, myrank);

	InitStates();
	
	float	Cost,
			Length = P->GetLocalN();
	
	int i=0,
		status=1;
	
	status = SA_ParSolver::TestProblemImplementation();

	std::cout<<"Testing IO-Operations with Solution and Move!\n";

	SA_Move	*m = P->CreateMove();		
	while( status && (i++ < Length))	// test IO-Operations mit Solution and Move  
	{
		std::strstream move_stream;
		P->Copy(*State,*BestSolution);	
		P->GetNeighbor(*State,1);
		P->ExtractMove(*State,*m);
		P->OutputMove(move_stream,*m);
		P->InputApplyMoves(move_stream,*BestSolution);
		if ( (P->GetCost(*BestSolution) - P->GetCost(*State)) > EPSILON )
		{
			status = 0;
			std::cout<< "ERROR: the solution \n"<< (*BestSolution) <<" didn't went after "<<m<<" into\n"
				<< (*State) <<" as it should!\n"; 
		}
		P->UpdateSolution(*State);
	}
	return status;  
}
 
 
float SA_ClusteringSolver::Test()
{
return 0;
}
 
 #endif