Page MenuHomePhorge
Files F27033567

naugroup.c
No OneTemporary
Actions

Authored By
Unknown
Size
11 KB
Referenced Files
None
Subscribers
None

naugroup.c
View Options

/* naugroup.c
Procedures for handling groups found by nauty.
*/
#include "naugroup.h"
static permrec *freelist = NULL;
static int freelist_n = 0;
static grouprec *group = NULL;
static int group_depth = 0;
DYNALLSTAT(cosetrec,coset,coset_sz);
static permrec *gens;
DYNALLSTAT(set,workset,workset_sz);
DYNALLSTAT(int,allp,allp_sz);
DYNALLSTAT(int,id,id_sz);
/**************************************************************************/
permrec
*newpermrec(int n)
/* Get a permrec of order n. This procedure and the next one are
designed to be efficient if lots of group ops are done with the
same value of n. */
{
permrec *p;
if (freelist_n != n)
{
while (freelist != NULL)
{
p = freelist;
freelist = freelist->ptr;
free(p);
}
freelist_n = n;
}
if (freelist != NULL)
{
p = freelist;
freelist = freelist->ptr;
return p;
}
p = (permrec*) malloc(sizeof(permrec)+(freelist_n-2)*sizeof(int));
if (p == NULL)
{
fprintf(ERRFILE,">E malloc failed in newpermrec()\n");
exit(1);
}
return p;
}
/**************************************************************************/
void
freepermrec(permrec *p, int n)
/* Free a permrec of given size. */
{
permrec *q;
if (p == NULL) return;
if (freelist_n != n)
{
while (freelist)
{
q = freelist;
freelist = freelist->ptr;
free(q);
}
freelist_n = n;
}
p->ptr = freelist;
freelist = p;
}
/**************************************************************************/
grouprec *
groupptr(boolean cutloose)
/* Give the address of the group structure, cutting it loose
if requested. */
{
grouprec *p;
p = group;
if (cutloose)
{
group = NULL;
group_depth = 0;
coset = NULL;
coset_sz = 0;
}
return p;
}
/**************************************************************************/
void
freegroup(grouprec *grp)
/* Free (or pretend to free) group structure. */
{
int i,j;
cosetrec *p;
permrec *q,*qq;
for (i = 0; i < grp->depth; ++i)
{
p = grp->levelinfo[i].replist;
if (p != NULL)
for (j = grp->levelinfo[i].orbitsize; --j >= 0; )
{
freepermrec(p[j].rep,grp->n);
p[j].rep = NULL;
}
}
if (grp->depth > 0)
{
p = grp->levelinfo[0].replist;
if (p != NULL && p != coset)
{
free(p);
grp->levelinfo[0].replist = NULL;
}
q = grp->levelinfo[0].gens;
while (q != NULL)
{
qq = q;
q = q->ptr;
freepermrec(qq,grp->n);
}
grp->levelinfo[0].gens = NULL;
}
}
/**************************************************************************/
void
groupautomproc(int count, int *perm, int *orbits,
int numorbits, int stabvertex, int n)
{
permrec *p;
int i;
p = newpermrec(n);
for (i = 0; i < n; ++i) p->p[i] = perm[i];
p->ptr = gens;
gens = p;
}
/**************************************************************************/
void
grouplevelproc(int *lab, int *ptn, int level, int *orbits, statsblk *stats,
int tv, int index, int tcellsize, int numcells, int cc, int n)
{
int depth;
size_t sz;
if (numcells == n) /* first call */
{
depth = level - 1;
if (group) freegroup(group);
if (depth > group_depth || !group)
{
if (depth <= 1) sz = sizeof(grouprec);
else sz = sizeof(grouprec) + (depth-1)*sizeof(levelrec);
if (group) group = (grouprec*)realloc((void*)group,sz);
else group = (grouprec*)malloc(sz);
if (group == NULL)
{
fprintf(ERRFILE,">E malloc failed in grouplevelproc\n");
exit(1);
}
group_depth = depth;
}
group->n = n;
group->depth = depth;
gens = NULL;
return;
}
group->levelinfo[level-1].fixedpt = tv;
group->levelinfo[level-1].orbitsize = index;
group->levelinfo[level-1].gens = gens;
group->levelinfo[level-1].replist = NULL;
if (level == 1) group->numorbits = stats->numorbits;
}
/**************************************************************************/
void
makecosetreps(grouprec *grp)
/* Make all coset representatives for this group */
{
int i,j,k,n,depth;
int l,index;
int *p,*q;
permrec *gen,*g;
cosetrec *cr;
int head,tail;
DYNALLSTAT(int,queue,queue_sz);
DYNALLSTAT(int,lab,lab_sz);
n = grp->n;
depth = grp->depth;
DYNALLOC1(int,queue,queue_sz,n,"malloc");
DYNALLOC1(int,lab,lab_sz,n,"malloc");
j = 0;
for (i = 0; i < depth; ++i)
j += grp->levelinfo[i].orbitsize;
if (j > 0) DYNALLOC1(cosetrec,coset,coset_sz,j,"malloc");
cr = coset;
for (i = 0; i < depth; ++i)
{
grp->levelinfo[i].replist = cr;
cr += grp->levelinfo[i].orbitsize;
}
for (i = 0; i < depth; ++i)
{
cr = grp->levelinfo[i].replist;
gen = grp->levelinfo[i].gens;
for (j = 0; j < n; ++j) lab[j] = -1;
queue[0] = grp->levelinfo[i].fixedpt;
lab[queue[0]] = 0;
cr[0].image = queue[0];
cr[0].rep = NULL;
head = 0;
tail = 1;
index = 0;
while (head < tail)
{
j = queue[head++];
p = (cr[lab[j]].rep ? cr[lab[j]].rep->p : NULL);
for (g = gen; g != NULL; g = g->ptr)
{
k = g->p[j];
if (lab[k] < 0)
{
++index;
lab[k] = index;
queue[tail++] = k;
cr[index].image = k;
cr[index].rep = newpermrec(n);
q = cr[index].rep->p;
if (p == NULL)
for (l = 0; l < n; ++l) q[l] = g->p[l];
else
for (l = 0; l < n; ++l) q[l] = g->p[p[l]];
}
}
}
}
}
/**************************************************************************/
int
permcycles(int *p, int n, int *len, boolean sort)
/* Puts in len[0..] the cycle lengths of p. If sort, sort them.
Return the number of cycles. */
{
int m,i,j,k,h,nc,leni;
m = (n + WORDSIZE - 1) / WORDSIZE;
DYNALLOC1(set,workset,workset_sz,m,"malloc");
EMPTYSET(workset,m);
nc = 0;
for (i = 0; i < n; ++i)
if (!ISELEMENT(workset,i))
{
k = 1;
for (j = p[i]; j != i; j = p[j])
{
ADDELEMENT(workset,j);
++k;
}
len[nc++] = k;
}
if (sort && nc > 1)
{
j = nc / 3;
h = 1;
do
h = 3 * h + 1;
while (h < j);
do
{
for (i = h; i < nc; ++i)
{
leni = len[i];
for (j = i; len[j-h] > leni; )
{
len[j] = len[j-h];
if ((j -= h) < h) break;
}
len[j] = leni;
}
h /= 3;
}
while (h > 0);
}
return nc;
}
/**************************************************************************/
static void
groupelts(levelrec *lr, int n, int level, void (*action)(int*,int),
int *before, int *after, int *id)
/* Recursive routine used by allgroup. */
{
int i,j,orbsize;
int *p,*cr;
cosetrec *coset;
coset = lr[level].replist;
orbsize = lr[level].orbitsize;
for (j = 0; j < orbsize; ++j)
{
cr = (coset[j].rep == NULL ? NULL : coset[j].rep->p);
if (before == NULL)
p = cr;
else if (cr == NULL)
p = before;
else
{
p = after;
for (i = 0; i < n; ++i) p[i] = cr[before[i]];
}
if (level == 0)
(*action)((p == NULL ? id : p),n);
else
groupelts(lr,n,level-1,action,p,after+n,id);
}
}
/**************************************************************************/
void
allgroup(grouprec *grp, void (*action)(int*,int))
/* Call action(p,n) for every element of the group, including the identity.
The identity is always the first call. */
{
int i,depth,n;
depth = grp->depth;
n = grp->n;
DYNALLOC1(int,id,id_sz,n,"malloc");
for (i = 0; i < n; ++i) id[i] = i;
if (depth == 0)
{
(*action)(id,n);
return;
}
DYNALLOC1(int,allp,allp_sz,n*depth,"malloc");
groupelts(grp->levelinfo,n,depth-1,action,NULL,allp,id);
}
/**************************************************************************/
static void
groupelts2(levelrec *lr, int n, int level,
void (*action)(int*,int,int*), int *before,
int *after, int *id, int *abort)
/* Recursive routine used by allgroup2. */
{
int i,j,orbsize;
int *p,*cr;
cosetrec *coset;
coset = lr[level].replist;
orbsize = lr[level].orbitsize;
for (j = 0; j < orbsize; ++j)
{
cr = (coset[j].rep == NULL ? NULL : coset[j].rep->p);
if (before == NULL)
p = cr;
else if (cr == NULL)
p = before;
else
{
p = after;
for (i = 0; i < n; ++i) p[i] = cr[before[i]];
}
if (level == 0)
(*action)((p == NULL ? id : p),n,abort);
else
groupelts2(lr,n,level-1,action,p,after+n,id,abort);
if (*abort) return;
}
}
/**************************************************************************/
int
allgroup2(grouprec *grp, void (*action)(int*,int,int*))
/* Call action(p,n,&abort) for every element of the group, including
the identity. The identity is always the first call.
If action() stores a non-zero value in abort, group generation is
aborted and the abort value is returned by this procedure. If no
non-zero value is ever returned in abort by action(), this
procedure returns 0. */
{
int i,depth,n,abort;
depth = grp->depth;
n = grp->n;
DYNALLOC1(int,id,id_sz,n,"malloc");
for (i = 0; i < n; ++i) id[i] = i;
abort = 0;
if (depth == 0)
{
(*action)(id,n,&abort);
return abort;
}
DYNALLOC1(int,allp,allp_sz,n*depth,"malloc");
groupelts2(grp->levelinfo,n,depth-1,action,NULL,allp,id,&abort);
return abort;
}
/**************************************************************************/
static void
groupelts3(levelrec *lr, int n, int level,
void (*action)(int*,int,int*,void*), int *before,
int *after, int *id, int *abort, void *userptr)
/* Recursive routine used by allgroup3. */
{
int i,j,orbsize;
int *p,*cr;
cosetrec *coset;
coset = lr[level].replist;
orbsize = lr[level].orbitsize;
for (j = 0; j < orbsize; ++j)
{
cr = (coset[j].rep == NULL ? NULL : coset[j].rep->p);
if (before == NULL)
p = cr;
else if (cr == NULL)
p = before;
else
{
p = after;
for (i = 0; i < n; ++i) p[i] = cr[before[i]];
}
if (level == 0)
(*action)((p == NULL ? id : p),n,abort,userptr);
else
groupelts3(lr,n,level-1,action,p,after+n,id,abort,userptr);
if (*abort) return;
}
}
/**************************************************************************/
int
allgroup3(grouprec *grp, void (*action)(int*,int,int*,void*), void *userptr)
/* Call action(p,n,&abort,userptr) for every element of the group,
including the identity. The identity is always the first call.
If action() stores a non-zero value in abort, group generation is
aborted and the abort value is returned by this procedure. If no
non-zero value is ever returned in abort by action(), this
procedure returns 0. The pointer userptr is not interpretted and
is passed to action() to use as it likes. */
{
int i,depth,n,abort;
depth = grp->depth;
n = grp->n;
DYNALLOC1(int,id,id_sz,n,"malloc");
for (i = 0; i < n; ++i) id[i] = i;
abort = 0;
if (depth == 0)
{
(*action)(id,n,&abort,userptr);
return abort;
}
DYNALLOC1(int,allp,allp_sz,n*depth,"malloc");
groupelts3(grp->levelinfo,n,depth-1,action,NULL,allp,id,&abort,userptr);
return abort;
}

File Metadata

Mime Type
text/x-c
Expires
Tue, Oct 27, 4:35 PM (1 d, 6 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
407434
Default Alt Text
naugroup.c (11 KB)

Event Timeline