desc: this file -- describes the contents of this folder
msamp.m: provides the source code for a sample run of various features of matlab that I am using in my research
cay.m: auxiliary script that feeds matlab the adjacency matrix for the Cayley graph of s7
circ_gen.cpp: generates the graph for circulant graphs, in the format required by nauty
sym_gen.cpp: generates the graph for Cayley graphs of the symmetric group, in the format required by nauty/matlab, depending on which part of the program is commented out
dij.cpp: implementation of Dijkstra's algorithm used to compute the diameter of the Cayley graph of s7 (which is 14)
amat: adjacency list for s7

------------------------------------------------------------------------------------------------------------------

function y = msamp()

[x,y,z]=cay();
A = sparse(x,y,z);

A

spy(A);

input('Image of the adjacency matrix of the Cayley graph for S7.');

p = symrcm(A);

spy(A(p,p));

input('Image of the same matrix after the Cuthill-McKee algorithm is run.');

[V,D,FLAG]=eigs(A,64);

input('The previous process just found the 64 largest eigenvalues of the matrix.');

diag(D)

input('These are the eigenvalues. Note that the second-largest is 1+sqrt(7).');

plot(1:5040,V(:,2));

input('Plot of the eigenfunction of one eigenvalue.');

plot(1:5040,sort(V(:,2)));

input('Plot of the values of the eigenfunction in sorted order.');

------------------------------------------------------------------------------------------------------------------

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

int **adj,N,M;
int* nums;

int main(int argc,char* argv[]){
  FILE *fout = fopen(argv[1],"w");
  sscanf(argv[2],"%d",&N);
	M = 2*(argc-3);
	adj = (int**)malloc(N*sizeof(int*));
	for(int i=0;i<N;i++)
	  adj[i]=(int*)malloc(N*sizeof(int));
	nums = (int*)malloc(M*sizeof(int));
	for(int i=3;i<argc;i++){
	  sscanf(argv[i],"%d",&nums[2*i-6]);
		nums[2*i-5]=N-nums[2*i-6];
	}
	for(int i=0;i<N;i++)
	  for(int j=0;j<M;j++){
		  adj[i][(i+nums[j])%N]=1;
		}

  fprintf(fout,"n=%d $=0 g\n",N);
  for(int i=0;i<N;i++){
	  fprintf(fout,"  %d : ",i);
	  for(int j=0;j<N;j++)
		  if(adj[i][j])
			  fprintf(fout," %d",j);
		fprintf(fout,";\n");
  }
  fprintf(fout,"$$\n");

	fclose(fout);
	return 0;
}

------------------------------------------------------------------------------------------------------------------

/*
 * Jacob Steinhardt
 * Generates Cayley graph for S_n
 */

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

#define S (2)
#define N (7)
//#define MAX (2520)
//#define MAX (3628800)
//#define MAX (40320)
#define MAX (5040)
#define SYM (1)

typedef long long int LLI;

int gens[S][N] = {
  { 1,2,3,0,4,5,6 },
	{ 4,1,2,3,5,6,0 } };

/*int gens[S][N] = {
  { 1,2,3,0,4,5,6,7 },
	{ 4,1,2,3,5,6,0,7 },
	{ 7,1,2,3,4,5,6,0 } };*/

/*int gens[S][N] = {
  { 1,2,0,3,4,5,6 },
	{ 3,1,2,4,0,5,6 },
	{ 5,1,2,3,4,6,0 } };*/

int pows[N];
int perm[N];
vector<int> adj[MAX];
map<LLI,int> m;
//bool mat[MAX][MAX];

LLI f(int* x){
  LLI r = 0;
  for(int i=0;i<N;i++)
	  r += x[i]*pows[i];
	return r;
}

LLI hcomp(int* x,int* y){
  LLI r = 0;
	for(int i=0;i<N;i++)
	  r+= x[y[i]]*pows[i];
	return r;
}

void set(int* x){
  for(int i=0;i<N;i++)
	  x[i]=i;
}

bool odd(int* x){
	int inv = 0;
  for(int i=0;i<N;i++)
	  for(int j=i+1;j<N;j++)
		  if(perm[j]<perm[i])
			  inv++;
  return inv&1;
}

int main(){
  pows[0]=1;
  for(int i=1;i<N;i++)
    pows[i]=N*pows[i-1];

  int a,b,c = 0;
	set(perm);
	do if(SYM||!odd(perm)) m[f(perm)]=c++;
	while(next_permutation(perm,perm+N));

  printf("%d %d\n",c,MAX);

  set(perm);
	do if(SYM||!odd(perm))
	  for(int i=0;i<S;i++){
		  a = m[f(perm)]; b = m[hcomp(perm,gens[i])];
			//printf("%d %d\n",a,b);
	    adj[a].push_back(b); adj[b].push_back(a);
		}
	while(next_permutation(perm,perm+N));

  printf("1\n");

  FILE *fout = fopen("s7_2.txt","w");

  fprintf(fout,"n=%d $=0 g\n",MAX);
  for(int i=0;i<MAX;i++){
	  if(i%300==0) printf("%d\n",i);
	  fprintf(fout,"  %d : ",i);
		for(int j=0;j<adj[i].size();j++){
		  fprintf(fout," %d",adj[i][j]);
			//mat[i][adj[i][j]]=1;
		}
	  fprintf(fout,";\n");
	}
	fprintf(fout,"$$\n");

  printf("%d %d\n",m[hcomp(gens[0],gens[0])]+1,m[hcomp(gens[0],gens[1])]+1);

  FILE *fout2 = fopen("cay.m","w");

  fprintf(fout2,"function [i,j,s]=cay()\n\n");

	fprintf(fout2,"i = [");
	for(int i=0;i<MAX;i++)
	  for(int j=0;j<adj[i].size();j++)
		    fprintf(fout2,"%d,",i+1);
  fprintf(fout2,"]';\n");

	fprintf(fout2,"j = [");
	for(int i=0;i<MAX;i++)
	  for(int j=0;j<adj[i].size();j++)
		    fprintf(fout2,"%d,",adj[i][j]+1);
	fprintf(fout2,"]';\n");

	fprintf(fout2,"s = [");
	for(int i=0;i<MAX;i++)
	  for(int j=0;j<adj[i].size();j++)
		    fprintf(fout2,"%d,",1);
  fprintf(fout2,"]';\n\n\n");

	fclose(fout); fclose(fout2);
  return 0;
}

------------------------------------------------------------------------------------------------------------------

/*
   PROG: dij
	 LANG: C++
 */

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX (5040)
#define INF (1000000000)

vector<int> adj[MAX];
vector<int> dist[MAX];

bool vis[MAX];
int di[MAX];

int main(){
  FILE *fin = fopen("amat","r");
	//FILE *fout = fopen("mdist","w");
	int V,E,s,e,d; fscanf(fin,"%d %d\n",&V,&E);
	printf("%d %d\n",V,E);
	for(int i=0;i<E;i++){
	  char c;
	  do fscanf(fin,"%c",&c);
		while(c!='(');
	  fscanf(fin,"%d,%d)       %d\n",&s,&e,&d); s--; e--;
		printf("%d\n",d);
		//printf("%d %d %d\n",s,e,d);
	  adj[s].push_back(e); adj[e].push_back(s); dist[s].push_back(d); dist[e].push_back(d);
  }

	for(int i=0;i<V;i++)
	  di[i]=INF;
	
	int n = 0;
	di[0]=0;
  printf("%d\n",adj[0].size());
	getchar();

	while(n!=-1){
	  vis[n]=1;
		for(int i=0;i<adj[n].size();i++)
		  di[adj[n][i]]<?=di[n]+dist[n][i];
		n=-1;
		for(int i=0;i<V;i++)
		  if(!vis[i]&&(n==-1||di[i]<di[n]))
			  n=i;
	}
  int ma = 0;
	for(int i=0;i<V;i++){
	  ma >?= di[i];
		printf("%d %d\n",vis[i],di[i]);
	}

	printf("%d\n",ma);
	//fprintf(fout,"%d\n",di[V-1]);
	fclose(fin);
	//fclose(fout);
	return 0;
}


------------------------------------------------------------------------------------------------------------------

cay.m and amat not included due to length...here is the first few lines of each

------------------------------------------------------------------------------------------------------------------

function [i,j,s]=cay()

i = [1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12,13,13,13,13,14,14,14,14,15,15,15,15,16,16,16,16,17,17,17,17,18,18,18,18,19,19,19,19,20,20,20,20,21,21,21,21,22,22,22,22,23,23,23,23,24,24,24,24,25,25,25,25,26,26,26,26,27,27,27,27,28,28,28,28,29,29,29,29,30,30,30,30,31,31,31,31,32,32,32,32,33,33,33,33,34,34,34,34,35,35,35,35,36,36,36,36,37,37,37,37,38,38,38,38,39,39,39,39,40,40,40,40,41,41,41,41,42,42,42,42,43,43,43,43,44,44,44,44,45,45,45,45,46,46,46,46,47,47,47,47,48,48,48,48,49,49,49,49,50,50,50,50,51,51,51,51,52,52,52,52,53,53,53,53,54,54,54,54,55,55,55,55,56,56,56,56,57,57,57,57,58,58,58,58,59,59,59,59,60,60,60,60,61,61,61,61,62,62,62,62,63,63,63,63,64,64,64,64,65,65,65,65,66,66,66,66,67,67,67,67,68,68,68,68,69,69,69,69,70,70,70,70,71,71,71,71,72,72,72,72,73,73,73,73,74,74,74,74,75,75,75,75,76,76,76,76,77,77,77,77,78,78,78,78,79,79,79,79,80,80,80,80,81,81,81,81,82,82,82,82,83,83,83,83,84,84,84,84,85,85,85,85,86,86,86,86,87,87,87,87,88,88,88,88,89,89,89,89,90,90,90,90,91,91,91,91,92,92,92,92,93,93,93,93,94,94,94,94,95,95,95,95,96,96,96,96,97,97,97,97,98,98,98,98,99,99,99,99,100,100,100,100,101,101,101,101,102,102,102,102,103,103,103,103,104,104,104,104,105,105,105,105,106

------------------------------------------------------------------------------------------------------------------

5040 20160
 (865,1)        1
(2161,1)        1
(3034,1)        1
(4471,1)        1
 (866,2)        1
(2162,2)        1
(3036,2)        1
(3751,2)        1
 (867,3)        1
(2163,3)        1
(3754,3)        1
(4472,3)        1
 (868,4)        1
(2164,4)        1
(3031,4)        1
(3756,4)        1
 (869,5)        1
(2165,5)        1
(3752,5)        1
(4474,5)        1
 (870,6)        1
(2166,6)        1
(3032,6)        1
(4476,6)        1
 (889,7)        1
(2314,7)        1
(2881,7)        1
(4477,7)        1
 (890,8)        1
(2316,8)        1
(2882,8)        1
(3757,8)        1
 (891,9)        1
(2883,9)        1
(3760,9)        1
(4478,9)        1
 (892,10)       1
(2311,10)       1
(2884,10)       1
(3762,10)       1
 (893,11)       1