Page MenuHomePhorge
Files F27037090

nautyex9.c
No OneTemporary
Actions

Authored By
Unknown
Size
3 KB
Referenced Files
None
Subscribers
None

nautyex9.c
View Options

/* This program demonstrates how known automorphisms can be given
to Traces. We compute the automorphism group of the circulant
graph of order n with i is adjacent to j iff j-i is a square
mod n. We need that -1 is a square so that the graph is
undirected, which means that the prime factors of n must be
congruent to 1 mod 4. (This is the Paley graph in the event
that p is a prime.)
*/
#include "traces.h"
int
main(int argc, char *argv[])
{
DYNALLSTAT(int,p,p_sz);
DYNALLSTAT(boolean,issquare,issquare_sz);
DYNALLSTAT(int,lab,lab_sz);
DYNALLSTAT(int,ptn,ptn_sz);
DYNALLSTAT(int,orbits,orbits_sz);
static DEFAULTOPTIONS_TRACES(options);
TracesStats stats;
/* Declare and initialize sparse graph structures */
SG_DECL(sg);
int deg,n,m,i,j;
size_t k;
permnode *gens;
/* Select option for passing generators to Traces */
options.generators = &gens;
/* Read a number of vertices and process it */
while (1)
{
printf("\nenter n : ");
if (scanf("%d",&n) == 1 && n > 2)
{
m = SETWORDSNEEDED(n);
nauty_check(WORDSIZE,m,n,NAUTYVERSIONID);
DYNALLOC1(int,lab,lab_sz,n,"malloc");
DYNALLOC1(int,ptn,ptn_sz,n,"malloc");
DYNALLOC1(int,orbits,orbits_sz,n,"malloc");
DYNALLOC1(int,p,p_sz,n,"malloc");
DYNALLOC1(boolean,issquare,issquare_sz,n,"malloc");
/* Initialise list of automorphisms */
gens = NULL;
/* Find the squares and the degree */
for (i = 0; i < n; ++i) issquare[i] = FALSE;
for (i = 0; i < n; ++i) issquare[(i*i)%n] = TRUE;
if (!issquare[n-1])
{
printf("-1 must be a square mod n; try again\n");
continue;
}
deg = 0;
for (i = 1; i < n; ++i) if (issquare[i]) ++deg;
/* Now make the graph */
SG_ALLOC(sg,n,n*deg,"malloc");
sg.nv = n; /* Number of vertices */
sg.nde = n*deg; /* Number of directed edges */
for (i = 0; i < n; ++i)
{
sg.v[i] = i*deg; /* Position of vertex i in v array */
sg.d[i] = deg; /* Degree of vertex i */
}
for (i = 0; i < n; ++i) /* Edges */
{
k = sg.v[i];
for (j = 1; j < n; ++j)
if (issquare[j]) sg.e[k++] = (i + j) % n;
}
/* Add known automorphisms */
/* We wouldn't need freeschreier() if we were only
processing one graph, but it doesn't hurt. This
is how to properly dispose of previous generators. */
freeschreier(NULL,&gens);
/* Cyclic rotation */
for (i = 0; i < n; ++i) p[i] = (i + 1) % n;
addpermutation(&gens,p,n);
/* Reflection about 0 */
for (i = 0; i < n; ++i) p[i] = (n - i) % n;
addpermutation(&gens,p,n);
/* Call Traces */
Traces(&sg,lab,ptn,orbits,&options,&stats,NULL);
printf("Automorphism group size = ");
writegroupsize(stdout,stats.grpsize1,stats.grpsize2);
printf("\n");
/* Traces left the automorphims we gave it, augmented by
any extra automorphims it found, in a circular list
pointed to by gens. See schreier.txt for documentation. */
}
else
break;
}
exit(0);
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 8:26 PM (1 d, 21 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
408043
Default Alt Text
nautyex9.c (3 KB)

Event Timeline