Link to home
Start Free TrialLog in
Avatar of dadadude
dadadude

asked on

code checking c++

is there a problem with the while loop in here?
because with me it looping and looping till i go minus!!!
so i decided to swtich it with IF
for (int i=0; i<n; i++)
		if (color[i] == ColorNumber)
			for (int j=0; j<NNCount; j++)
				while (a[i][NN[j]] == 1)
				{
					NN[j] = NN[NNCount - 1];
					NNCount --;
				}
}

Open in new window

ASKER CERTIFIED SOLUTION
Avatar of jkr
jkr
Flag of Germany image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
I'll be frank. This code is a bit convoluted :)

Do you really want the test in the while loop to be == 1? Do you maybe mean >0? Since there is no context to this code it is almost impossible to say what is or is not going wrong here.

It would be more helpful if you could show the whole section of code to which this snippet pertains and also explain what the different variables are and what they are likely to contain.

Avatar of dadadude
dadadude

ASKER

no problem. i'll post the whole code in here.
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. The chromatic number of a graph is the least number of colors needed for coloring of the graph. The problem here is to color a graph with its chromatic number.
Suppose that we are coloring a simple undirected graph.
Given a graph with n vertices. This algorithm will color each vertex with a number. F(x) is the color of vertex x.

the function that i am talking about is : void UpdateNN(int ColorNumber)
the code is commented.
// Graph_coloring.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "conio.h"
#include "fstream"
#include "iostream"

using namespace std;
// this program will work with graphs of which number of vertices is smaller or equal to 100
const int MAX = 100;
// necessary variables
// n is the number of vertices of the graph
int n;
// a[n][n] is the adjacency matrix of the graph
// a[i][j] = 1 if i-th and j-th vertices are adjacent
int a[MAX][MAX];
// array color[n] stores the colors of the vertices
// color[i] = 0 if we 've not colored it yet
int color[MAX];
// array degree[n] stores the degrees of the vertices
int degree[MAX];
// array NN[] stores all the vertices that is not adjacent to current vertex
int NN[MAX];
// NNCount is the number of that set
int NNCount;
// unprocessed is the number of vertices with which we 've not worked
int unprocessed;
/*=========================================================
===========================================================
					WORKING FUNCTION
===========================================================
=========================================================*/

// function that reads input from file named "input.txt" in the same folder
void GetInput()
{
	ifstream in("input.txt");
	in >> n;
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			in >> a[i][j];
	in.close();
}

// initializing function
void Init()
{
	for (int i=0; i<n; i++)
	{
		color[i] = 0;
		degree[i] = 0;
		for (int j = 0; j<n; j++)
			if (a[i][j] == 1)
				degree[i] ++;
	}
	NNCount = 0;
	unprocessed = n;
}
// this function finds the unprocessed vertex of which degree is maximum
int MaxDegreeVertex()
{
	int max = -1;
	int max_i;
	for (int i =0; i<n; i++)
		if (color[i] == 0)
			if (degree[i]>max)
			{
				max = degree[i];
				max_i = i;
			}
	return max_i;
}
// this function is for UpdateNN function
// it reset the value of scanned array
void scannedInit(int scanned[MAX])
{
	for (int i=0; i<n; i++)
		scanned[i] = 0;
}
// this function updates NN array
void UpdateNN(int ColorNumber)
{
	NNCount = 0;
	for (int i=0; i<n; i++)
		if (color[i] == 0)
		{
			NN[NNCount] = i;
			NNCount ++;
		}
	for (int i=0; i<n; i++)
		if (color[i] == ColorNumber)
			for (int j=0; j<NNCount; j++)
				while (a[i][NN[j]] == 1)
				{
					NN[j] = NN[NNCount - 1];
					NNCount --;
				}
}
// this function will find suitable y from NN
int FindSuitableY(int ColorNumber, int& VerticesInCommon)
{
	int temp,tmp_y,y;
	int scanned[MAX];
	VerticesInCommon = 0;
	for (int i=0; i<NNCount; i++)
	{
		tmp_y = NN[i];
		temp = 0;
		scannedInit(scanned);
		for (int x=0; x<n; x++)
			if (color[x] == ColorNumber)
				for (int k=0; k<n; k++)
					if (color[k] == 0 && scanned[k] == 0)
						if (a[x][k] == 1 && a[tmp_y][k] == 1)
						{
							temp ++;
							scanned[k] = 1;
						}
		if (temp > VerticesInCommon)
		{
			VerticesInCommon = temp;
			y = tmp_y;
		}
	}
	return y;
}
// find the vertex in NN of which degree is maximum
int MaxDegreeInNN()
{
	int tmp_y;
	int temp, max = 0;
	for (int i=0; i<NNCount; i++)
	{
		temp = 0;
		for (int j=0; j<n; j++)
			if (color[NN[j]] == 0 && a[i][NN[j]] == 1)
				temp ++;
		if (temp>max)
		{
			max = temp;
			tmp_y = NN[i];
		}
	}
	return tmp_y;
}
// processing function
void Coloring()
{
	int x,y;
	int ColorNumber = 0;
	int VerticesInCommon = 0;
	while (unprocessed>0)
	{
		x = MaxDegreeVertex();
		ColorNumber ++;
		color[x] = ColorNumber;
		unprocessed --;
		UpdateNN(ColorNumber);
		while (NNCount>0)
		{
			y = FindSuitableY(ColorNumber, VerticesInCommon);
			if (VerticesInCommon == 0)
				y = MaxDegreeInNN();
			color[y] = ColorNumber;
			unprocessed --;
			UpdateNN(ColorNumber);
		}
	}
}
// print out the output
void PrintOutput()
{
	for (int i=0; i<n; i++)
		cout << "Vertex " << i+1 << " is colored " << color[i] << endl;
}
// main function
void main()
{
	GetInput();
	Init();
	Coloring();
	PrintOutput();
	getch();
}

Open in new window

i want to test it if it is equal to 1. the problem is that it will be always equal to 1. since he is looping on it all the time without any check.
Have you tried the addiotnal check? I.e.
while (a[i][NN[j]] == 1 && NNCount > 0) // <--- additional check here!

Open in new window

yes jkr it worked very good. and even gave me good classification results.
But do u think it's the right thing to do? or we can change the while statement with an IF statement:
I mean
IF (a[i][NN[j]] == 1)

Open in new window


since it's just looping i don't know it's a little bit confusing. But concerning the results they were good.
i checked the classification.

i just need a couple of more minutes to test it. waiting for the output.
Actually i translated the code to python :P.
and i am studying it. the code isn't so clean.
Well, if you change the 'while' to an 'if', you no longer have a loop ;o)
yes i know. the results are ok. I guess it solved the problem.
If i have another problem i'll ask about it.

Thank you for your help. The classification results are great!!!!
Good to know ;o)
simple and Good thank you