/* (C)2013 Claudio Rocchini CC-BY 3.0 */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <vector> #include <algorithm> const double PI = 3.1415926535897932384626433832795; typedef std::pair<int,int> edge;  int greedy_color( int N, const std::vector<edge> & edges, std::vector<int> & colors ) { 	std::vector< std::vector<int> > stars(N); 	std::vector<edge>::const_iterator ii; 	for(ii=edges.begin();ii!=edges.end();++ii) { 		stars[(*ii).first ].push_back( (*ii).second ); 		stars[(*ii).second].push_back( (*ii).first  ); 	} 	colors.resize(N); 	for(int nc=2;;++nc) { 		std::fill(colors.begin(),colors.end(),-1); colors[0] = 0; 		int p = 1; 		for(;;) { 			if(++colors[p]==nc) { 				colors[p] = -1; 				if(--p<1) break; else continue; 			} 			std::vector<int>::const_iterator jj; 			for(jj=stars[p].begin();jj!=stars[p].end();++jj) 				if(colors[*jj]==colors[p])  break; 			if(jj==stars[p].end()) if(++p==N) break; 		} 		if(p==N) return nc; 	} }  int main() { 	const int S = 600;	 	const int rgb[][3] = { 		{255,8,8},{8,255,8},{8,8,255},{255,255,8},{255,8,255},{255,255,255} 	}; 	/* Than's to for this graph: 	http://school.maths.uwa.edu.au/~gordon/remote/graphs/ */ 	const int N = 8; 	const int pe[N] = {0,2,4,1,3,5,6,7}; 	const int gr[N][7]= { 		{2,3,5,6,7,-1,-1}, {3,4,5,6,7,-1,-1}, {0,4,5,6,7,-1,-1}, 		{0,1,5,6,7,-1,-1}, {1,2,5,6,7,-1,-1}, 		{0,1,2,3,4,6,7}, {0,1,2,3,4,5,7}, {0,1,2,3,4,5,6} 	}; 	int i,j,k; 	const double R1=S/7, R2=R1*2/3, R3=8; 	double x[N],y[N]; 	for(i=0;i<5;++i) { 		x[pe[i]] = +sin(2*PI*i/5)*R1; 		y[pe[i]] = -cos(2*PI*i/5)*R1; 	} 	for(i=0;i<3;++i) { 		x[i+5] = +sin(2*PI*i/3)*R2; 		y[i+5] = -cos(2*PI*i/3)*R2; 	} 	 	FILE * fo = fopen("critical.svg","w"); 	fprintf(fo, 		"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n" 		"<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.0\" width=\"%d\" height=\"%d\" id=\"criticalg\">\n" 		,S,S 	); 	 	for(k=-1;k<N;++k) { 		double lx = S/6+((k+1)%3)*S/3; double ly = S/6+((k+1)/3)*S/3; 		std::vector<edge> edges; 		for(i=0;i<N;++i) if(i!=k) 			for(j=0;j<7;++j) 				if(gr[i][j]>i && gr[i][j]!=k) 					edges.push_back( edge(i,gr[i][j]) ); 		std::vector<int> colors; 		int nc = greedy_color(N,edges,colors); 		printf("colors = %d\n",nc); 	 		fprintf(fo,"<g style=\"stroke:#000000;stroke-width:1.5;fill:none\">\n"); 		for(i=0;i<int(edges.size());++i) 		if(edges[i].first!=k && edges[i].second!=k) 			fprintf(fo,"<line x1=\"%6.2f\" y1=\"%6.2f\" x2=\"%6.2f\" y2=\"%6.2f\"/>\n" 				,lx+x[edges[i].first ],ly+y[edges[i].first] 				,lx+x[edges[i].second],ly+y[edges[i].second] 			); 		fprintf(fo,"</g>\n");  		fprintf(fo,"<g>\n"); 		for(i=0;i<N;++i) if(i!=k) 			fprintf(fo,"<circle cx=\"%6.2f\" cy=\"%6.2f\" r=\"%g\" " 			           "style=\"stroke:#000000;stroke-width:1;stroke-opacity:1.0;fill:#%02X%02X%02X\"/>\n" 				,lx+x[i],ly+y[i],R3 				,rgb[colors[i]][0],rgb[colors[i]][1],rgb[colors[i]][2] 			); 		fprintf(fo,"</g>\n"); 	} 	 	fprintf(fo,"</svg>\n"); 	 	fclose(fo); 	 	 	return 0; }