File:Critical graph sample.svg

/* (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;
}