/*********************************
 * Drawing the Chang Graphs
 * (C) 2010 Claudio Rocchini
 * CC-BY 3.0
 * Many thanks to Nadia Hamoudi for
 * "The Chang graphs".
 *********************************/
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <vector>
#include <set>
#include <algorithm>
const double PI = 3.1415926535897932384626433832795;

class point2 { public: double x,y; };

typedef std::pair<size_t,size_t> edge;

class graph {
public:
	size_t nv;
	std::vector<edge> edges;
	int find_edge( const edge & e ) const {
		std::vector<edge>::const_iterator i = std::find(edges.begin(),edges.end(),e);
		return  i==edges.end() ? -1 : i - edges.begin();
	}
};

bool is_strong_regular( const graph & g, int & K, int & LAMDA, int & MU ) {
	int i,j,k;
	std::vector<bool> MA(g.nv*g.nv); std::fill(MA.begin(),MA.end(),false);
	std::vector<edge>::const_iterator q;
	K = -1;
	for(q=g.edges.begin();q!=g.edges.end();++q) {
		MA[(*q).first+g.nv*(*q).second] = true;
		MA[(*q).second+g.nv*(*q).first] = true;
	}
	std::vector<int> adj(g.nv);
	std::fill(adj.begin(),adj.end(),0);
	for(k=0;k<int(g.nv*g.nv);++k) if(MA[k]) {
		i = k%g.nv; j = k/g.nv;
		if(i<j) { ++adj[i]; ++adj[j]; }
	}
	for(i=1;i<int(g.nv);++i) if(adj[0]!=adj[i])
		return false;
	K = adj[0];
	LAMDA = -1; MU = -1;
	for(i=0;i<int(g.nv)-1;++i) for(j=i+1;j<int(g.nv);++j) {
		int n = 0;
		for(k=0;k<int(g.nv);++k) if(k!=i && k!=j)
			if( MA[i*g.nv+k] && MA[j*g.nv+k] ) ++n;
		if( MA[i*g.nv+j] ) {
			if(LAMDA==-1) LAMDA = n;
			else if(LAMDA!=n )
				return false;
		} else {
			if(MU==-1) MU = n;
			else if(MU!=n )
				return false;
		}
	}
	return true;
}

void make_K(graph & g, size_t n, std::vector<point2> & pos) {
	g.nv = n; g.edges.clear();
	for(size_t i=0;i<n-1;++i)
	for(size_t j=i+1;j<n;++j)
		g.edges.push_back(edge(i,j));
	pos.resize(n);
	for(size_t k=0;k<n;++k) {
		const double a = 2*PI*k/n + PI/2;
		pos[k].x = cos(a);
		pos[k].y = sin(a);
	}
}

void make_line( const graph & g, const std::vector<point2> & ipos, graph & l, std::vector<point2> & opos ) {
	l.nv = g.edges.size();
	l.edges.clear();
	for(size_t i=0;i<g.edges.size()-1;++i)
	for(size_t j=i+1;j<g.edges.size();++j)
		if(g.edges[i].first ==g.edges[j].first  || g.edges[i].first ==g.edges[j].second ||
		   g.edges[i].second==g.edges[j].first  || g.edges[i].second==g.edges[j].second )
				l.edges.push_back( edge(i,j) );
	opos.resize(l.nv);
	for(size_t k=0;k<g.edges.size();++k) {
		opos[k].x = (ipos[g.edges[k].first].x + ipos[g.edges[k].second].x)/2;
		opos[k].y = (ipos[g.edges[k].first].y + ipos[g.edges[k].second].y)/2;
	}
}

void invert( const graph & g, const std::set<size_t> & iset, graph & ig ) {
	size_t i,j;
	std::set<edge> re;
	ig.nv = g.nv; ig.edges.clear();
	for(i=0;i<g.edges.size();++i) {
		bool inf = iset.find(g.edges[i].first )!=iset.end();
		bool ins = iset.find(g.edges[i].second)!=iset.end();
		if(inf ^ ins) re.insert(g.edges[i]);
		else          ig.edges.push_back(g.edges[i]);
	}
	for(i=0;i<g.nv-1;++i)
	for(j=i+1;j<g.nv;++j) {
		bool inf = iset.find(i)!=iset.end();
		bool ins = iset.find(j)!=iset.end();
		if((inf ^ ins) && re.find(edge(i,j))==re.end())
			ig.edges.push_back(edge(i,j));
	}
}

const double SX = 800;
const double SY = 1200;
const double RR = 7;
const double BO = 10;

void save_svg2_start( FILE * fo ) {
	fprintf(fo,
		"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
		"<svg\n"
		"xmlns:svg=\"http://www.w3.org/2000/svg\"\n"
		"xmlns=\"http://www.w3.org/2000/svg\"\n"
		"version=\"1.0\"\n"
		"width=\"%g\"\n" "height=\"%g\"\n"
		"id=\"changgraphs\">\n"
		,SX,SY
	);
}

void save_svg2( FILE * fo, const graph & g, const std::vector<point2> & pos, const std::set<size_t> & rset,
	double ox, double oy ) {
	std::vector<double> px(g.nv);
	std::vector<double> py(g.nv);
	int i;
	const double R = ((SX/2-BO*2)/2);
		
	for(i=0;i<int(g.nv);++i) {
		px[i] = ox+SX/4 + R*pos[i].x;
		py[i] = oy+SY/6 + R*pos[i].y;
	}

	const int ecolor[3][3] = { {0,0,0},{128,0,0},{0,0,64} };
	fprintf(fo,"<g style=\"stroke:#%02X%02X%02X;stroke-width:1.5;stroke-opacity:0.2\">\n"
		,ecolor[2][0],ecolor[2][1],ecolor[2][2]);
	for(int a=0;a<int(g.nv)-1;++a)
	for(int b=a+1;b<int(g.nv);++b)
	{
		bool f1 = rset.find(a)==rset.end();
		bool f2 = rset.find(b)==rset.end();
		if(f1==f2) continue;
		if( g.find_edge( edge(a,b) )==-1 )
			fprintf(fo,
					"<line x1=\"%3.1lf\" y1=\"%3.1lf\" x2=\"%3.1lf\" y2=\"%3.1lf\"/>\n"
					,px[a],py[a]
					,px[b],py[b]
				);
	}
	fprintf(fo,"</g>\n");
	for(int mode=0;mode<2;++mode) {
		fprintf(fo,"<g style=\"stroke:#%02X%02X%02X;stroke-width:1.5;stroke-opacity:0.75\">\n"
			,ecolor[mode][0],ecolor[mode][1],ecolor[mode][2]);
		for(i=0;i<int(g.edges.size());++i)
		{
			bool f1 = rset.find(g.edges[i].first)==rset.end();
			bool f2 = rset.find(g.edges[i].second)==rset.end();
			if( (mode==0 && f1==f2) || (mode==1 && f1!=f2) )
				fprintf(fo,
					"<line x1=\"%3.1lf\" y1=\"%3.1lf\" x2=\"%3.1lf\" y2=\"%3.1lf\"/>\n"
					,px[g.edges[i].first ],py[g.edges[i].first ]
					,px[g.edges[i].second],py[g.edges[i].second]
				);
		}
		fprintf(fo,"</g>\n");
	}

	fprintf(fo,"<g id=\"nodes\" style=\"stroke:#000;stroke-width:1;fill:#00F\">\n");
	for(i=0;i<int(g.nv);++i) if(rset.find(i)==rset.end())
		fprintf(fo,"<circle cx=\"%3.1lf\" cy=\"%3.1lf\" r=\"%g\"/>\n",px[i],py[i],RR);
	fprintf(fo,"</g>\n");
	fprintf(fo,"<g id=\"nodes\" style=\"stroke:#000;stroke-width:1;fill:#00E000\">\n");
	for(i=0;i<int(g.nv);++i) if(rset.find(i)!=rset.end())
		fprintf(fo,"<circle cx=\"%3.1lf\" cy=\"%3.1lf\" r=\"%g\"/>\n",px[i],py[i],RR);
	fprintf(fo,"</g>\n");

}

void save_svg2_end( FILE * fo ) {
	fprintf(fo,"</svg>\n");
}

int main() {
	size_t i;
	graph K8,T8,chang1,chang2,chang3;
	std::vector<point2> k8_pos,t8_pos;
	std::set<size_t> empty,rset1,rset2,rset3;
	make_K(K8,8,k8_pos);            printf("%u %u\n",K8.nv,K8.edges.size());
	make_line(K8,k8_pos,T8,t8_pos); printf("%u %u\n",T8.nv,T8.edges.size());
	int K,LAMBDA,MU;
	if(!is_strong_regular(T8,K,LAMBDA,MU)) printf("error");
	else printf("t8: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);

	FILE * fo = fopen("c:\\temp\\chang_graphs.svg","w");
	save_svg2_start(fo);

	std::vector<edge> fourK2;
	fourK2.push_back( edge(0,1) ); fourK2.push_back( edge(2,3) );
	fourK2.push_back( edge(4,5) ); fourK2.push_back( edge(6,7) );
	for(i=0;i<fourK2.size();++i) rset1.insert( K8.find_edge( fourK2[i] ) );
	invert(T8,rset1,chang1);
	if(!is_strong_regular(chang1,K,LAMBDA,MU)) printf("error");
	else printf("chang1: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
	save_svg2(fo,T8,t8_pos,rset1,0,0);
	save_svg2(fo,chang1,t8_pos,empty,SX/2,0);

	std::vector<edge> c8;
	c8.push_back( edge(0,1) ); c8.push_back( edge(1,2) );
	c8.push_back( edge(2,3) ); c8.push_back( edge(3,4) );
	c8.push_back( edge(4,5) ); c8.push_back( edge(5,6) );
	c8.push_back( edge(6,7) ); c8.push_back( edge(0,7) );
	for(i=0;i<c8.size();++i) rset2.insert( K8.find_edge( c8[i] ) );
	invert(T8,rset2,chang2);
	if(!is_strong_regular(chang2,K,LAMBDA,MU)) printf("error");
	else printf("chang2: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
	save_svg2(fo,T8,t8_pos,rset2,0,SY/3);
	save_svg2(fo,chang2,t8_pos,empty,SX/2,SY/3);

	std::vector<edge> c3uc5;
	c3uc5.push_back( edge(0,3) ); c3uc5.push_back( edge(3,5) );
	c3uc5.push_back( edge(0,5) );
	c3uc5.push_back( edge(1,2) ); c3uc5.push_back( edge(2,4) );
	c3uc5.push_back( edge(4,6) ); c3uc5.push_back( edge(6,7) );
	c3uc5.push_back( edge(1,7) );
	for(i=0;i<c3uc5.size();++i) rset3.insert( K8.find_edge( c3uc5[i] ) );
	invert(T8,rset3,chang3);
	if(!is_strong_regular(chang3,K,LAMBDA,MU)) printf("error\n");
	else printf("chang3: %u %d %d %d\n",T8.nv,K,LAMBDA,MU);
	save_svg2(fo,T8,t8_pos,rset3,0,SY*2/3);
	save_svg2(fo,chang3,t8_pos,empty,SX/2,SY*2/3);

	save_svg2_end(fo);
	fclose(fo);
	return 0;
}