view defical-c/src/graphmagic.cpp @ 1:758381a85d76 default tip

Incorrect printf format.
author Edho Prima Arief <me@myconan.net>
date Mon, 28 Jun 2010 14:52:19 +0700
parents ebed2bd0d300
children
line wrap: on
line source

#include "graphmagic.h"

semtd::semtd(){}

semtd::semtd(uint32_t graphType,uint32_t NumVer, uint32_t numDef)
{
	if(NumVer>3){
		this->NumVer=NumVer;
		this->numDef=numDef;
		this->graphType=graphType;
		this->TotalVer=NumVer+numDef;
		this->numEdges=0;
		this->isSureFail=false;
		this->edgeLabelAbsoluteMax=this->TotalVer*2-1;
		//initialize graph array
		//this->theGraph.resize(this->NumVer+1,vector<bool>(this->NumVer+1,false));
		for (int i=0; i<1000;i++)
		{
			for (int j=0;j<1000;j++)
			{
				this->theGraph[i][j]=false;
			}
		}
		draw(this->graphType,1,this->NumVer);
		resetLabels(0);
	}
}

void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end)
{
	switch(drawType)
	{
	case 0:
		{
			for (uint32_t i=start;i<end;i++)
				connectVertices(i,i+1);
			break;
		}
	case 1:
		{
			draw(0,start,end);
			connectVertices(start,end);
			break;
		}
	case 3:
		{
			draw(1,start+1,end);
			draw(2,start+1,end,start);
			break;
		}
	case 4:
		{
			draw(0,start+1,end);
			draw(2,start+1,end,start);
			break;
		}
	case 5:
		{
			draw(4,start+1,end);
			draw(2,start+2,end,start);
			break;
		}
	}
}

void semtd::draw(uint32_t drawType,uint32_t start,uint32_t end, uint32_t extra)
{
	switch(drawType)
	{
	case 2:
		{
			for (uint32_t i=start;i<=end;i++)
				connectVertices(i,extra);
			break;
		}
	}
}

inline void semtd::connectVertices(uint32_t a,uint32_t b)
{
	if(!this->theGraph[a][b])
	{
		this->theGraph[a][b]=this->theGraph[b][a]=true;
		this->numEdges++;
	}
}

void semtd::resetLabels(uint32_t mode)
{
	if(mode==0)
	{
		this->VerLabels.clear();
		this->VerLabels.resize(this->NumVer+1,0);
	}
	this->edgeLabels.clear();
	this->edgeLabels.resize(NumVer+1,vector<uint32_t>(NumVer+1,0));
	this->isQuickMode=false;
	this->scoreCache=-1;
	//uint32_t *edgeLabelsUsedPtr;
	//edgeLabelsUsedPtr=(uint32_t*)malloc(this->edgeLabelAbsoluteMax+1*sizeof(uint32_t));
	this->edgeLabelsUsed.clear();
	this->edgeLabelsUsed.resize(this->edgeLabelAbsoluteMax+1,0);
	this->edgeLabelMax=0;this->edgeLabelMin=this->edgeLabelAbsoluteMax;
	refreshEdgeLabelsMinMax();
}

void semtd::refreshEdgeLabelsMinMax()
{
	uint32_t i;
	for (i = 1; i <= this->edgeLabelAbsoluteMax; i++)
	{
		if (this->edgeLabelsUsed[i] > 0)
		{
			this->edgeLabelMin = i;
			break;
		}
	}
	for (int32_t x = this->edgeLabelAbsoluteMax; x >= 0; x--)
	{
		if (this->edgeLabelsUsed[x] > 0)
		{
			this->edgeLabelMax = x;
			break;
		}
	}
}

inline uint32_t semtd::edgeLabelRange()
{
	return this->edgeLabelMax-this->edgeLabelMin+1;
}

void semtd::setEdgeLabels(uint32_t verPos)
{
	uint32_t newLabel,i;
	for (i = 1; i <= this->NumVer; i++)
	{
		if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
		{
			newLabel = this->VerLabels[verPos] + this->VerLabels[i];
			this->edgeLabels[i][verPos] = this->edgeLabels[i][verPos] = newLabel;
			this->edgeLabelsUsed[newLabel]++;
			if (this->edgeLabelsUsed[newLabel] != 1)
				this->isSureFail = true;
		}
	}
	refreshEdgeLabelsMinMax();
}

void semtd::removeEdgeLabels(uint32_t verPos)
{
	uint32_t i;
	for (i = 1; i <= this->NumVer; i++)
	{
		if (this->VerLabels[i] > 0 && this->theGraph[verPos][i] && i != verPos)
		{
			int oldLabel = this->edgeLabels[i][verPos];
			this->edgeLabelsUsed[oldLabel]--;
			this->edgeLabels[i][verPos] = this->edgeLabels[verPos][i] = 0;
		}
	}
	refreshEdgeLabelsMinMax();
}

void semtd::SetVerLabel(uint32_t verPos,uint32_t verLabel)
{
	if (this->VerLabels[verPos] > 0) { RemoveVerLabel(verPos); }
	this->VerLabels[verPos] = verLabel;
	setEdgeLabels(verPos);
}

void semtd::RemoveVerLabel(uint32_t verPos)
{
	if (this->VerLabels[verPos] > 0)
	{
		this->VerLabels[verPos] = 0;
		removeEdgeLabels(verPos);
	}
}



bool semtd::IsValidToLabel(uint32_t verPos,uint32_t verLabel)
{
	uint32_t i,tempLabel;
	//uint32_t tempMax=this->edgeLabelMax;
	//uint32_t tempMin=this->edgeLabelMin;
	for (i = 1; i <= this->NumVer; i++)
	{
		tempLabel=this->VerLabels[i] + verLabel;
		if (i != verPos &&
			this->theGraph[i][verPos] &&
			this->VerLabels[i] > 0 &&
			this->edgeLabelsUsed[tempLabel] == 1)
		{
			return false;
		}
		/*if(tempLabel>tempMax)
		tempMax=tempLabel;
		if(tempLabel<tempMin)
		tempMin=tempLabel;
		if(!isValidRange(tempMin,tempMax))
		return false;*/
	}
	return true;
}

bool semtd::isValidRange(uint32_t min,uint32_t max)
{
	uint32_t delta=1+max-min;
	if(delta<=this->numEdges)
		return true;
	return false;
}

double semtd::SemtScore()
{
	//TODO
	return 0;
}

void semtd::FixLabel()
{
	//TODO
}

void semtd::SwapLabel()
{
	//TODO
}

string semtd::Print(uint32_t withDual)
{
	uint32_t i,j;
	string ret = "";
	string n = "\n";
	bool dualRun=false;
	bool keepPrinting=true;
	while (keepPrinting)
	{
		ret+="graph: ";
		switch(this->graphType)
		{
		case 3:
			{
				ret+="wheel";
				break;
			}
		case 4:
			{
				ret+="fan";
				break;
			}
		case 5:
			{
				ret+="doublefan";
				break;
			}
		default:
			{
				ret+="unknown";
				break;
			}
		}
		ret+=" | edges: "+uint32_t_to_str(this->numEdges)+" | vertices: " + uint32_t_to_str(this->NumVer)+" | deficiencies: " + uint32_t_to_str(this->numDef) + " | ";
		uint32_t edgeweight=0,k,edgelabel=0;
		for (i=1;i<=this->edgeLabelAbsoluteMax;i++)
		{
			if(this->edgeLabelsUsed[i])
			{
				edgeweight=i;
				edgelabel=this->numEdges+this->TotalVer;
				break;
			}
		}
		if(dualRun)
		{
			edgeweight=2*(this->TotalVer)+2-edgeweight;
			edgelabel=2*this->TotalVer+this->numEdges+1-edgelabel;
		}
		k=edgeweight+edgelabel;
		ret+="mnum: "+uint32_t_to_str(k)+" | ";
		for (i = 1; i <= this->NumVer; i++)
		{
			uint32_t theLabel;
			if(dualRun)
				theLabel=this->TotalVer+1-this->VerLabels[i];
			else
				theLabel=this->VerLabels[i];
			if(i==1 && this->graphType==3)
				ret+="c: " + uint32_t_to_str(theLabel) +" | l: ";
			else if(i==1 && this->graphType==4)
				ret+="c: " + uint32_t_to_str(theLabel) +" | p: ";
			else if(i==1 && this->graphType==5)
				ret+="c: " + uint32_t_to_str(theLabel) + ",";
			else if(i==2 && this->graphType==5)
				ret+=uint32_t_to_str(theLabel) + " | p: ";
			else if(i==this->NumVer)
				ret+=uint32_t_to_str(theLabel) + " | def: ";
			else
				ret+=uint32_t_to_str(theLabel)+",";
		}
		if(this->numDef>0)
		{
			vector<bool> usedLabels (this->TotalVer+1,false);
			for(i=1;i<=this->NumVer;i++)
				usedLabels[this->VerLabels[i]]=true;
			j=0;
			for(i=1;i<=this->TotalVer;i++)
			{
				uint32_t theLabel;
				if(!usedLabels[i])
				{
					if(dualRun)
						theLabel=this->TotalVer+1-i;
					else
						theLabel=i;
					if(j==this->numDef-1)
					{
						if(dualRun)
							ret+=uint32_t_to_str(theLabel)+" (dual)"+n;
						else
							ret+=uint32_t_to_str(theLabel)+n;
						j++;
					}
					else
					{
						ret+=uint32_t_to_str(theLabel)+",";
						j++;
					}
				}
			}
		}
		/*
		ret += n+"Deficiency: " + uint32_t_to_str(this->numDef);
		ret += n+"GraphViz code: " + n + "----------------------------------";
		//tempstr1<<this->graphType; //TODO: graphtype is now integer instead of string. create a convert method
		ret += n+"graph " + uint32_t_to_str(this->graphType)+ "{";
		ret += n+"graph[bgcolor=\"transparent\"]";
		ret += n+"node [fontname=\"Bitstream Vera Sans\", fontsize=\"22.00\", shape=circle, style=\"bold,filled\" fillcolor=white];";
		ret += n+"edge [style=bold];";
		ret += n+" ";
		for (i = 1; i <= this->TotalVer; i++)
		{
		ret += uint32_t_to_str(i) + ";";
		}
		for (i = 1; i <= this->NumVer; i++)
		{
		for (j = i + 1; j <= this->NumVer; j++)
		{
		if (this->theGraph[i][j])
		{
		uint32_t theLabel;
		if(dualRun)
		theLabel=this->TotalVer+1-this->VerLabels[i];
		else
		theLabel=this->VerLabels[i];
		ret += n+uint32_t_to_str(this->VerLabels[i])+ " -- " + uint32_t_to_str(theLabel)+ ";";
		}
		}
		}
		ret += n+"}";
		ret += n+"----------------------------------" + n + "End GraphViz code";*/
		if(withDual==1)
		{
			withDual=0;
			dualRun=true;
		}else
			keepPrinting=false;
	}
	return ret;
}



bool semtd::IsSemt()
{
	uint32_t i;
	if (this->isSureFail) { return false; }
	else
	{
		if (edgeLabelRange() == numEdges)
		{
			uint32_t edgeLabelMin = this->edgeLabelMin;
			uint32_t edgeLabelMax = this->edgeLabelMax;
			for (i = edgeLabelMin; i <= edgeLabelMax; i++)
			{
				if (this->edgeLabelsUsed[i] != 1)
				{
					return false;
				}
			}
			return true;
		}
	}
	return false;
}

uint32_t semtd::MinDef()
{
	uint32_t ret=0;
	switch(this->graphType)
	{
	case 3:
		switch (this->NumVer)
		{
		case 3:
		case 4:
		case 6:
		case 7:
			{
				ret = 1;
				break;
			}
		default:
			{
				ret = 2;
				break;
			}
		}
	case 4:
		{
			ret=1;
			break;
		}
	case 5:
		{
			ret = (this->NumVer - 3) / 2;
			break;
		}
	}
	return ret;
}