Click here to Skip to main content
15,899,124 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
I don't usually ask questions this generally but i'm really lost.
I'm trying to color the vertexes of my graph in a way that I use the least colors possible and that none of the two vertexes next to each other have the same color.
I can't even understand the answer my program gives me when I compile it and I really don't know where I'm going wrong!!!
C++
class graphcoloring
{
	int n,m;
	int * Vcolor;
	int **w;
public:
	graphcoloring (int N)
	{
		n=N;
		m=N;
		w=new int*[n];
		for(int i=0; i<=n; ++i)
		{
			w[i]=new int[n];
		}
		Vcolor=new int[m];
	}
	
	void m_coloring(int i)
	{
		int color;
	if(promising(i))
		if(i==n)
			for(int i=1;i<=n;i++)
			{
			cout<<Vcolor[i] ;
			}
		else
			for(color=1;color<=m;color++)
			{
				Vcolor[i+1]=color;
			    m_coloring(i+1);
			}
	}
	bool promising(int i)
	{
		int j;
		bool change;
		change=true;
		j=1;
		while(j<i)
                {
                        mode="hold";
			if(w[i][j] && Vcolor[i]==Vcolor[j])
			{
				change=false;
				j++;
			}
                
			return change;
                }
	}
}
	void solve(){
     n=1;
     m=0;
	 m_coloring(1);
  }
};

int main()
{
	int n;
	cout << " n ? " ; cin >> n;
	graphcoloring s(n);
	s.solve();
	system("pause");
	return  EXIT_SUCCESS;
}
Posted
Updated 6-Jun-14 9:44am
v5
Comments
Richard MacCutchan 6-Jun-14 13:04pm    
I can't even understand the answer my program gives me when I compile it and I really don't know where I'm going wrong!!!
And I am afraid we cannot guess anything without some more detail about what results you see and why they are wrong.

Yeah - it really looks like you are lost.

Rethin your code with the pointers:

C#
int n,m;
int * Vcolor;
int **w;
public:
graphcoloring (int N)
{
n=N;
m=N;
w=new int*[n];
for(int i=0; i<=n; ++i)
{
w[i]=new int[n];
}
Vcolor=new int[m];//nice pointer but no values
}


My tip: first improve your code quality
1. rename all variables and funcitond to "speaking names"
2. use some simple class for the int* stuff
3. insert some debug output (if it works it can get removed)

good luck ;-)
 
Share this answer
 
This is a much bigger problem than you think!
See Vertex coloring[^]

Note (from the link above):
Graph coloring is computationally hard. It is NP-complete to decide if a given graph admits a k-coloring for a given k except for the cases k = 1 and k = 2. In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on planar graphs of degree 4.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900