latest version

1 files changed, 527 insertions, 0 deletions

diff --git a/graph-checker/nauty/naugroup.c b/graph-checker/nauty/naugroup.c
new file mode 100644
index 0000000..9ec2610
--- /dev/null
+++ b/graph-checker/nauty/naugroup.c
@@ -0,0 +1,527 @@
+/* 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;
+}