File:Chang graphs.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file ‎(SVG file, nominally 800 × 1,200 pixels, file size: 72 KB)

Summary

Description
English: The Chang Graphs.

The Chang Graphs are strongly regular graphs with parameters (28,12,6,4). On the right the tree Chang Graphs; these graphs are generated by selecting a proper switching set. On the left the originating [Triangular Graph]s T8:

the vertices in the switching set are green, the deleted edges are red and new added ones are phantom blue.
Date
Source Own work
Author Claudio Rocchini
Permission
(Reusing this file)		 CC-BY 3.0

References

Many thanks to Nadia Hamoudi for paper "The Chang graphs" at Nadia Hamoudi "The Chang graphs" archive copy at the Wayback Machine

A note: nauty software shows an automorphism group really poor for this graphs.

Source

Dirty C++ source code of graph generation and display: 

/*********************************
 * 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:#000000;stroke-width:1;fill:#0000FF\">\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:#000000;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;
}

Licensing

I, the copyright holder of this work, hereby publish it under the following licenses:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
GNU head Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.
You may select the license of your choice.

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

inception

29 September 2010

media type

image/svg+xml

checksum

7b6c7a81bb8fea0ec0d28f8ad20fee2fba387290

determination method: SHA-1

data size

73,627 byte

height

1,200 pixel

width

800 pixel

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current09:15, 29 September 2010Thumbnail for version as of 09:15, 29 September 2010800 × 1,200 (72 KB)Rocchini{{Information |Description={{en|1=The Chang Graphs. The Chang Graphs are strongly regular graphs with parameters (28,12,6,4). On the right the tree Chang Graphs; these graphs are generated by selecting a proper switching. On the left the originating [Tria
The following pages on the English Wikipedia use this file (pages on other projects are not listed):

Global file usage

The following other wikis use this file:

Retrieved from "https://en.wikipedia.org/wiki/File:Chang_graphs.svg"