summaryrefslogtreecommitdiff
path: root/nauty/gtnauty.c
diff options
context:
space:
mode:
Diffstat (limited to 'nauty/gtnauty.c')
-rw-r--r--nauty/gtnauty.c830
1 files changed, 830 insertions, 0 deletions
diff --git a/nauty/gtnauty.c b/nauty/gtnauty.c
new file mode 100644
index 0000000..e6a54ac
--- /dev/null
+++ b/nauty/gtnauty.c
@@ -0,0 +1,830 @@
+/* gtnauty.c : nauty-related routines for gtools.
+
+ Jan 15, 2001 : Increased graph order limit from 2^16-1 to 2^22-1.
+ Aug 9, 2001 : Added fgroup_inv() and fcanonise_inv()
+ Sep 15, 2004 : Completed prototypes
+ Oct 16, 2004 : DEAFULTOPTIONS_GRAPH
+ Nov 17, 2005 : Added fcanonise_inv_sg()
+ May 11, 2010 : use sorttemplates.c
+ Sep 5, 2013 : Unify format processing and remove 2^22 limit
+ Oct 14, 2017 : Include code for n=0
+ Sep 28, 2019 : Define breakcellwt
+
+**************************************************************************/
+
+#include "gtools.h" /* which includes naututil.h, nausparse.h, stdio.h */
+
+static boolean issymm;
+static set *g0;
+static int gm;
+static int fuzz2[] = {006532,070236,035523,062437};
+#define FUZZ2(x) ((x) ^ fuzz2[(x)&3])
+
+int gt_numorbits;
+
+#ifdef REFINE
+void REFINE(graph*,int*,int*,int,int*,int*,set*,int*,int,int);
+#endif
+
+#define MIN_SCHREIER 33 /* If n is this large, schreier will be
+ turned on. */
+
+/**************************************************************************/
+
+#define SORT_OF_SORT 3
+#define SORT_NAME sortwt
+#define SORT_TYPE1 int
+#define SORT_TYPE2 int
+#include "sorttemplates.c"
+/* Creates static void sortwt(int *lab, int *wt, int n) */
+
+void
+setlabptn(int *weight, int *lab, int *ptn, int n)
+/* Define (lab,ptn) with cells in increasing order of weight. */
+{
+ int i;
+
+ if (n == 0) return;
+
+ for (i = 0; i < n; ++i) lab[i] = i;
+
+ if (weight)
+ {
+ sortwt(lab,weight,n);
+ for (i = 0; i < n-1; ++i)
+ {
+ if (weight[lab[i]] != weight[lab[i+1]])
+ ptn[i] = 0;
+ else
+ ptn[i] = 1;
+ }
+ ptn[n-1] = 0;
+ }
+ else
+ {
+ for (i = 0; i < n-1; ++i) ptn[i] = 1;
+ ptn[n-1] = 0;
+ }
+}
+
+int
+breakcellwt(int *weight, int *lab, int *ptn, int n1, int n2)
+/* Break (lab[n1..n2-1],ptn[n1..n2-1]) into cells in increasing
+ order of weight. If is assumed that lab[n1..n2-1] are defined
+ but ptn[n1..n2-1] are ignored.
+ The weight of lab[i] is weight[lab[i]].
+ The number of cells is returned. */
+{
+ int i,nc;
+
+ if (n2 <= n1) return 0;
+
+ nc = 1;
+ if (weight)
+ {
+ sortwt(lab+n1,weight,n2-n1);
+ for (i = n1; i < n2-1; ++i)
+ {
+ if (weight[lab[i]] != weight[lab[i+1]])
+ {
+ ptn[i] = 0;
+ ++nc;
+ }
+ else
+ ptn[i] = 1;
+ }
+ ptn[n2-1] = 0;
+ }
+ else
+ {
+ for (i = n1; i < n2-1; ++i) ptn[i] = 1;
+ ptn[n2-1] = 0;
+ }
+
+ return nc;
+}
+
+static int
+setlabptnfmt(char *fmt, int *lab, int *ptn, set *active, int m, int n)
+/* Define (lab,ptn,active) according to format string.
+ Return number of cells */
+{
+ int i,nc;
+#if MAXN
+ int wt[MAXN];
+#else
+ DYNALLSTAT(int,wt,wt_sz);
+
+ DYNALLOC1(int,wt,wt_sz,n,"setlabptnfmt");
+#endif
+
+ if (n == 0) return 0;
+
+ EMPTYSET(active,m);
+ ADDELEMENT(active,0);
+ nc = 1;
+
+ if (fmt != NULL && fmt[0] != '\0')
+ {
+#if !MAXN
+ DYNALLOC1(int,wt,wt_sz,n,"setlabptnfmt");
+#endif
+ for (i = 0; i < n && fmt[i] != '\0'; ++i)
+ wt[i] = (unsigned char)fmt[i];
+ for ( ; i < n; ++i)
+ wt[i] = 'z';
+
+ setlabptn(wt,lab,ptn,n);
+ for (i = 0; i < n-1; ++i)
+ if (ptn[i] == 0)
+ {
+ ++nc;
+ ADDELEMENT(active,i+1);
+ }
+ }
+ else
+ {
+ for (i = 0; i < n; ++i)
+ {
+ lab[i] = i;
+ ptn[i] = 1;
+ }
+ ptn[n-1] = 0;
+ }
+
+ return nc;
+}
+
+/**************************************************************************/
+
+static boolean
+hasloops(graph *g, int m, int n)
+/* Test for loops */
+{
+ int i;
+ set *gi;
+
+ for (i = 0, gi = g; i < n; ++i, gi += m)
+ if (ISELEMENT(gi,i)) return TRUE;
+
+ return FALSE;
+}
+
+static boolean
+hasloops_sg(sparsegraph *sg)
+{
+ size_t *v,vi,j;
+ int *d,*e,n,i;
+
+ n = sg->nv;
+ SG_VDE(sg,v,d,e);
+ for (i = 0; i < n; ++i)
+ {
+ vi = v[i];
+ for (j = vi; j < vi + d[i]; ++j)
+ if (e[vi] == i) return TRUE;
+ }
+
+ return FALSE;
+}
+
+void
+fcanonise(graph *g, int m, int n, graph *h, char *fmt, boolean digraph)
+/* canonise g under format fmt; result in h.
+ fmt is either NULL (for no vertex classification) or is a string
+ with char-valued colours for the vertices. If it ends early, it
+ is assumed to continue with the colour 'z' indefinitely. */
+{
+#if MAXN
+ int lab[MAXN],ptn[MAXN],orbits[MAXN];
+ int count[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,orbits,orbits_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ int i;
+ int numcells,code;
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+
+ if (n == 0) return;
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E fcanonise: m or n too large\n");
+ ABORT(">E fcanonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"fcanonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"fcanonise");
+ DYNALLOC1(int,orbits,orbits_sz,n,"fcanonise");
+ DYNALLOC1(int,count,count_sz,n,"fcanonise");
+ DYNALLOC1(set,active,active_sz,m,"fcanonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"fcanonise");
+#endif
+
+ digraph = digraph || hasloops(g,m,n);
+
+ numcells = setlabptnfmt(fmt,lab,ptn,active,m,n);
+
+ if (m == 1)
+ refine1(g,lab,ptn,0,&numcells,count,active,&code,1,n);
+ else
+ refine(g,lab,ptn,0,&numcells,count,active,&code,m,n);
+
+ if (numcells == n || (numcells == n-1 && !digraph))
+ {
+ for (i = 0; i < n; ++i) count[i] = lab[i];
+ updatecan(g,h,count,0,m,n);
+ gt_numorbits = numcells;
+ }
+ else
+ {
+ options.getcanon = TRUE;
+ options.defaultptn = FALSE;
+ options.digraph = digraph;
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ EMPTYSET(active,m);
+ nauty(g,lab,ptn,active,orbits,&options,&stats,
+ workspace,24*m,m,n,h);
+ gt_numorbits = stats.numorbits;
+ }
+}
+
+/**************************************************************************/
+
+void
+fcanonise_inv(graph *g, int m, int n, graph *h, char *fmt,
+ void (*invarproc)(graph*,int*,int*,int,int,int,int*,int,
+ boolean,int,int), int mininvarlevel, int maxinvarlevel,
+ int invararg, boolean digraph)
+/* Canonise g under format fmt; result in h.
+ fmt is either NULL (for no vertex classification) or is a string
+ with char-valued colours for the vertices. If it ends early, it
+ is assumed to continue with the colour 'z' indefinitely.
+ This is like fcanonise() except that a invariant and its arguments
+ can be specified. */
+{
+#if MAXN
+ int lab[MAXN],ptn[MAXN],orbits[MAXN];
+ int count[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,orbits,orbits_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ int i;
+ int numcells,code;
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+
+ if (n == 0) return;
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E fcanonise: m or n too large\n");
+ ABORT(">E fcanonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"fcanonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"fcanonise");
+ DYNALLOC1(int,orbits,orbits_sz,n,"fcanonise");
+ DYNALLOC1(int,count,count_sz,n,"fcanonise");
+ DYNALLOC1(set,active,active_sz,m,"fcanonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"fcanonise");
+#endif
+
+ numcells = setlabptnfmt(fmt,lab,ptn,active,m,n);
+ digraph = digraph || hasloops(g,m,n);
+
+ if (m == 1)
+ refine1(g,lab,ptn,0,&numcells,count,active,&code,1,n);
+ else
+ refine(g,lab,ptn,0,&numcells,count,active,&code,m,n);
+
+ if (numcells == n || (!digraph && numcells >= n-1))
+ {
+ for (i = 0; i < n; ++i) count[i] = lab[i];
+ updatecan(g,h,count,0,m,n);
+ gt_numorbits = numcells;
+ }
+ else
+ {
+ options.getcanon = TRUE;
+ options.digraph = digraph;
+ options.defaultptn = FALSE;
+ if (invarproc)
+ {
+ options.invarproc = invarproc;
+ options.mininvarlevel = mininvarlevel;
+ options.maxinvarlevel = maxinvarlevel;
+ options.invararg = invararg;
+ }
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ EMPTYSET(active,m);
+ nauty(g,lab,ptn,active,orbits,&options,&stats,workspace,24*m,m,n,h);
+ gt_numorbits = stats.numorbits;
+ }
+}
+
+/**************************************************************************/
+
+void
+fcanonise_inv_sg(sparsegraph *g, int m, int n, sparsegraph *h, char *fmt,
+ void (*invarproc)(graph*,int*,int*,int,int,int,int*,int,
+ boolean,int,int), int mininvarlevel, int maxinvarlevel,
+ int invararg, boolean digraph)
+/* canonise g under format fmt; result in h.
+ fmt is either NULL (for no vertex classification) or is a string
+ with char-valued colours for the vertices. If it ends early, it
+ is assumed to continue with the colour 'z' indefinitely.
+ This is like fcanonise() except that a invariant and its arguments
+ can be specified. Version for sparse graphs. */
+{
+#if MAXN
+ int lab[MAXN],ptn[MAXN],orbits[MAXN];
+ int count[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,orbits,orbits_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ int i;
+ int numcells,code;
+ statsblk stats;
+ static DEFAULTOPTIONS_SPARSEGRAPH(options);
+
+ if (n == 0)
+ {
+ h->nv = 0;
+ h->nde = 0;
+ return;
+ }
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E fcanonise: m or n too large\n");
+ ABORT(">E fcanonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"fcanonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"fcanonise");
+ DYNALLOC1(int,orbits,orbits_sz,n,"fcanonise");
+ DYNALLOC1(int,count,count_sz,n,"fcanonise");
+ DYNALLOC1(set,active,active_sz,m,"fcanonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"fcanonise");
+#endif
+
+ numcells = setlabptnfmt(fmt,lab,ptn,active,m,n);
+ digraph = digraph || hasloops_sg(g);
+
+ refine_sg((graph*)g,lab,ptn,0,&numcells,count,active,&code,1,n);
+
+ if (numcells == n || (!digraph && numcells == n-1))
+ {
+ for (i = 0; i < n; ++i) count[i] = lab[i];
+ updatecan_sg((graph*)g,(graph*)h,count,0,m,n);
+ gt_numorbits = numcells;
+ }
+ else
+ {
+ options.getcanon = TRUE;
+ options.digraph = digraph;
+ options.defaultptn = FALSE;
+ if (invarproc)
+ {
+ options.invarproc = invarproc;
+ options.mininvarlevel = mininvarlevel;
+ options.maxinvarlevel = maxinvarlevel;
+ options.invararg = invararg;
+ }
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ EMPTYSET(active,m);
+ nauty((graph*)g,lab,ptn,active,orbits,&options,&stats,
+ workspace,24*m,m,n,(graph*)h);
+ gt_numorbits = stats.numorbits;
+ }
+}
+
+/**************************************************************************/
+
+void
+fgroup(graph *g, int m, int n, char *fmt, int *orbits, int *numorbits)
+/* Find the orbits of undirected graph g stabilised by format fmt.
+ The orbits are put into orbits[] and the number of them into *numorbits
+ fmt is either NULL (for no vertex classification) or is a string
+ with char-valued colours for the vertices. If it ends early, it
+ is assumed to continue with the colour 'z' indefinitely. */
+{
+#if MAXN
+ int lab[MAXN],ptn[MAXN];
+ int count[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ int i,j;
+ int orbrep;
+ int numcells,code;
+ boolean digraph;
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+
+ if (n == 0)
+ {
+ *numorbits = 0;
+ return;
+ }
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E fcanonise: m or n too large\n");
+ ABORT(">E fcanonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"fcanonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"fcanonise");
+ DYNALLOC1(int,count,count_sz,n,"fcanonise");
+ DYNALLOC1(set,active,active_sz,m,"fcanonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"fcanonise");
+#endif
+
+ numcells = setlabptnfmt(fmt,lab,ptn,active,m,n);
+ digraph = hasloops(g,m,n);
+
+ if (m == 1)
+ refine1(g,lab,ptn,0,&numcells,count,active,&code,1,n);
+ else
+ refine(g,lab,ptn,0,&numcells,count,active,&code,m,n);
+
+ if (cheapautom(ptn,0,digraph,n))
+ {
+ for (i = 0; i < n; )
+ {
+ if (ptn[i] == 0)
+ {
+ orbits[lab[i]] = lab[i];
+ ++i;
+ }
+ else
+ {
+ orbrep = n;
+ j = i;
+ do
+ {
+ if (lab[j] < orbrep) orbrep = lab[j];
+ } while (ptn[j++] != 0);
+
+ for (; i < j; ++i) orbits[lab[i]] = orbrep;
+ }
+ }
+ *numorbits = gt_numorbits = numcells;
+ }
+ else
+ {
+ options.getcanon = FALSE;
+ options.defaultptn = FALSE;
+ options.digraph = digraph;
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ EMPTYSET(active,m);
+ nauty(g,lab,ptn,active,orbits,&options,&stats,workspace,24*m,m,n,NULL);
+ *numorbits = gt_numorbits = stats.numorbits;
+ }
+}
+
+/**************************************************************************/
+
+void
+fgroup_inv(graph *g, int m, int n, char *fmt, int *orbits, int *numorbits,
+ void (*invarproc)(graph*,int*,int*,int,int,int,int*,int,
+ boolean,int,int), int mininvarlevel, int maxinvarlevel, int invararg)
+/* Find the orbits of undirected graph g stabilised by format fmt.
+ The orbits are put into orbits[] and the number of them into *numorbits
+ fmt is either NULL (for no vertex classification) or is a string
+ with char-valued colours for the vertices. If it ends early, it
+ is assumed to continue with the colour 'z' indefinitely.
+ This is like fgroup() except that a invariant and its arguments
+ can be specified. */
+{
+#if MAXN
+ int lab[MAXN],ptn[MAXN];
+ int count[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ int i,j;
+ int orbrep;
+ boolean digraph;
+ int numcells,code;
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+
+ if (n == 0)
+ {
+ *numorbits = 0;
+ return;
+ }
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E fcanonise: m or n too large\n");
+ ABORT(">E fcanonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"fcanonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"fcanonise");
+ DYNALLOC1(int,count,count_sz,n,"fcanonise");
+ DYNALLOC1(set,active,active_sz,m,"fcanonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"fcanonise");
+#endif
+
+ numcells = setlabptnfmt(fmt,lab,ptn,active,m,n);
+ digraph = hasloops(g,m,n);
+
+ if (m == 1)
+ refine1(g,lab,ptn,0,&numcells,count,active,&code,1,n);
+ else
+ refine(g,lab,ptn,0,&numcells,count,active,&code,m,n);
+
+ if (cheapautom(ptn,0,digraph,n))
+ {
+ for (i = 0; i < n; )
+ {
+ if (ptn[i] == 0)
+ {
+ orbits[lab[i]] = lab[i];
+ ++i;
+ }
+ else
+ {
+ orbrep = n;
+ j = i;
+ do
+ {
+ if (lab[j] < orbrep) orbrep = lab[j];
+ } while (ptn[j++] != 0);
+
+ for (; i < j; ++i) orbits[lab[i]] = orbrep;
+ }
+ }
+ *numorbits = gt_numorbits = numcells;
+ }
+ else
+ {
+ options.getcanon = FALSE;
+ options.defaultptn = FALSE;
+ options.digraph = digraph;
+ if (invarproc)
+ {
+ options.invarproc = invarproc;
+ options.mininvarlevel = mininvarlevel;
+ options.maxinvarlevel = maxinvarlevel;
+ options.invararg = invararg;
+ }
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ EMPTYSET(active,m);
+ nauty(g,lab,ptn,active,orbits,&options,&stats,workspace,24*m,m,n,NULL);
+ *numorbits = gt_numorbits = stats.numorbits;
+ }
+}
+
+/**************************************************************************/
+
+static void
+userlevel(int *lab, int *ptn, int level, int *orbits, statsblk *stats,
+ int tv, int index, int tcellsize, int numcells, int cc, int n)
+{
+ int i0,i;
+
+ if (level != 2) return;
+
+ issymm = TRUE;
+
+ i0 = nextelement(g0,gm,-1);
+ if (i0 >= 0)
+ for (i = i0; (i = nextelement(g0,gm,i)) >= 0;)
+ if (orbits[i] != i0)
+ {
+ issymm = FALSE;
+ return;
+ }
+}
+
+/*******************************************************************/
+
+/* istransitive(g,m,n,h)
+
+ g is an input undirected graph without loops
+ m,n of standard meaning.
+ h is a place to put an output graph.
+
+ If g is transitive, return 1 or 2 and put a canonically labelled
+ version of g into h. The value is 2 for symmetric graphs,
+ and 1 for other transitive graphs.
+ If g is not transitive, return 0. In that case h may or
+ may not have something in it.
+*/
+int
+istransitive(graph *g, int m, int n, graph *h)
+{
+ int i,inv;
+ set *gw;
+ short wt;
+ int d,inv0,v,w;
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+#if MAXN
+ int lab[MAXN],ptn[MAXN],orbits[MAXN];
+ long x[MAXN];
+ int count[MAXN];
+ setword workspace[24*MAXM];
+ set workset[MAXM];
+ set sofar[MAXM],frontier[MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,orbits,orbits_sz);
+ DYNALLSTAT(int,count,count_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+ DYNALLSTAT(set,workset,workset_sz);
+ DYNALLSTAT(set,sofar,sofar_sz);
+ DYNALLSTAT(set,frontier,frontier_sz);
+#endif
+
+ if (n == 0) return 2;
+
+#if MAXN
+ if (m > MAXM || n > MAXN)
+ {
+ fprintf(stderr,
+ ">E istransitive: bad input parameters (n=%d m=%d)\n",n,m);
+ exit(1);
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"istransitive");
+ DYNALLOC1(int,ptn,ptn_sz,n,"istransitive");
+ DYNALLOC1(int,orbits,orbits_sz,n,"istransitive");
+ DYNALLOC1(int,count,count_sz,n,"istransitive");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"istransitive");
+ DYNALLOC1(set,workset,workset_sz,m,"istransitive");
+ DYNALLOC1(set,sofar,sofar_sz,m,"istransitive");
+ DYNALLOC1(set,frontier,frontier_sz,m,"istransitive");
+#endif
+
+ for (v = 0; v < n; ++v)
+ {
+ inv = 0;
+ EMPTYSET(sofar,m);
+ ADDELEMENT(sofar,v);
+ EMPTYSET(frontier,m);
+ ADDELEMENT(frontier,v);
+ for (d = 1; d < n; ++d)
+ {
+ EMPTYSET(workset,m);
+ wt = 0;
+ for (w = -1; (w = nextelement(frontier,m,w)) >= 0;)
+ {
+ ++wt;
+ gw = GRAPHROW(g,w,m);
+ for (i = m; --i >= 0;) workset[i] |= gw[i];
+ }
+ if (wt == 0) break;
+ wt += (short)(0x73 ^ d);
+ wt = (short)FUZZ2(wt);
+ inv += wt;
+ for (i = m; --i >= 0;)
+ {
+ frontier[i] = workset[i] & ~sofar[i];
+ sofar[i] |= frontier[i];
+ }
+ }
+ if (v == 0) inv0 = inv;
+ else if (inv != inv0) return 0;
+ }
+
+ options.getcanon = TRUE;
+ options.userlevelproc = userlevel;
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+
+ issymm = TRUE;
+ g0 = (set*) g;
+ gm = m;
+
+ nauty(g,lab,ptn,NULL,orbits,&options,&stats,workspace,24*m,m,n,h);
+
+ if (stats.numorbits != 1) return 0;
+ else if (!issymm) return 1;
+ else return 2;
+}
+
+/**************************************************************************/
+
+void
+tg_canonise(graph *g, graph *h, int m, int n)
+/* Canonise vertex-transitive graph */
+{
+ int i;
+#if MAXN
+ int lab[MAXN],ptn[MAXN],orbits[MAXN];
+ set active[MAXM];
+ setword workspace[24*MAXM];
+#else
+ DYNALLSTAT(int,lab,lab_sz);
+ DYNALLSTAT(int,ptn,ptn_sz);
+ DYNALLSTAT(int,orbits,orbits_sz);
+ DYNALLSTAT(set,active,active_sz);
+ DYNALLSTAT(setword,workspace,workspace_sz);
+#endif
+ statsblk stats;
+ static DEFAULTOPTIONS_GRAPH(options);
+
+#if MAXN
+ if (n > MAXN || m > MAXM)
+ {
+ fprintf(stderr,">E tg_canonise: m or n too large\n");
+ ABORT(">E tg_canonise");
+ }
+#else
+ DYNALLOC1(int,lab,lab_sz,n,"tg_canonise");
+ DYNALLOC1(int,ptn,ptn_sz,n,"tg_canonise");
+ DYNALLOC1(int,orbits,orbits_sz,n,"tg_canonise");
+ DYNALLOC1(set,active,active_sz,m,"tg_canonise");
+ DYNALLOC1(setword,workspace,workspace_sz,24*m,"tg_canonise");
+#endif
+
+ if (n == 0) return;
+
+ options.getcanon = TRUE;
+ options.defaultptn = FALSE;
+#ifdef REFINE
+ options.userrefproc = REFINE;
+#endif
+
+ for (i = 0; i < n; ++i)
+ {
+ lab[i] = i;
+ ptn[i] = 1;
+ }
+ ptn[0] = ptn[n-1] = 0;
+
+ EMPTYSET(active,m);
+ ADDELEMENT(active,0);
+
+ if (n >= MIN_SCHREIER) options.schreier = TRUE;
+ nauty(g,lab,ptn,active,orbits,&options,&stats,workspace,24*m,m,n,h);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 07:28:03 +0000