summaryrefslogtreecommitdiff
path: root/graph-checker/nauty/nautinv.c
diff options
context:
space:
mode:
Diffstat (limited to 'graph-checker/nauty/nautinv.c')
-rw-r--r--graph-checker/nauty/nautinv.c1752
1 files changed, 1752 insertions, 0 deletions
diff --git a/graph-checker/nauty/nautinv.c b/graph-checker/nauty/nautinv.c
new file mode 100644
index 0000000..dee0b18
--- /dev/null
+++ b/graph-checker/nauty/nautinv.c
@@ -0,0 +1,1752 @@
+/*****************************************************************************
+* *
+* Vertex-invariants source file for nauty 2.8. *
+* *
+* Copyright (1989-2022) Brendan McKay. All rights reserved. *
+* Subject to waivers and disclaimers in nauty.h. *
+* *
+* CHANGE HISTORY *
+* 13-Mar-90 : initial release for version 1.5 *
+* 10-Nov-90 : changes for version 1.6 : *
+* - added dummy routine nautinv_null() *
+* 27-Aug-92 : renamed to version 1.7, no changes to this file *
+* 5-Jun-93 : renamed to version 1.7+, no changes to this file *
+* 18-Aug-93 : renamed to version 1.8, no changes to this file *
+* 17-Sep-93 : changes for version 1.9 : *
+* - added invariant routine adjacencies() *
+* 20-Jun-96 : changes for version 2.0 : *
+* - added invariants cellfano() and cellfano2() *
+* 11-Jul-96 - added dynamic allocation *
+* 21-Oct-98 - use shortish in place of short for BIGNAUTY *
+* 9-Jan-00 - added nautinv_check() *
+* 12-Feb-00 - minor code formatting *
+* 16-Nov-00 - made changes listed in nauty.h *
+* 22-Apr-01 : changes for version 2.1 : *
+* - made all large dynamic memory external to routines *
+* - added nautinv_freedyn() to free all such memory *
+* - include nautinv.h rather than naututil.h *
+* - removed nautinv_null() *
+* - added code to facilitate compilation into Magma *
+* - removed EXTDEFS *
+* 12-Jul-01 - use invararg in distances() *
+* - fixed comments in ind and cliq routines *
+* 21-Nov-01 : use NAUTYREQUIRED in nautinv_check() *
+* 10-Dec-06 : remove BIGNAUTY *
+* 10-Nov-09 : remove types shortish and permutation *
+* 23-Nov-09 : add refinvar() *
+* 12-Jun-10 : fixed identical errors in cellcliq() and cellind() *
+* 15-Jan-12 : add TLS_ATTR attributes *
+* 23-Aug-12 : fix getbigcells(), thanks to Fatih Demirkale *
+* 23-Jan-13 : add some parens to satisfy icc *
+* *
+*****************************************************************************/
+
+#define ONE_WORD_SETS
+#include "nautinv.h"
+
+#if MAXM==1
+#define M 1
+#else
+#define M m
+#endif
+
+#define MASH(l,i) ((((l) ^ 056345) + (i)) & 077777)
+ /* : expression whose long value depends only on long l and int/long i.
+ Anything goes, preferably non-commutative. */
+
+#define CLEANUP(l) ((int)((l) % 077777))
+ /* : expression whose value depends on long l and is less than 077777
+ when converted to int then short. Anything goes. */
+
+#define ACCUM(x,y) x = (((x) + (y)) & 077777)
+ /* : must be commutative. */
+
+static const int fuzz1[] = {037541,061532,005257,026416};
+static const int fuzz2[] = {006532,070236,035523,062437};
+
+#define FUZZ1(x) ((x) ^ fuzz1[(x)&3])
+#define FUZZ2(x) ((x) ^ fuzz2[(x)&3])
+
+#define MAXCLIQUE 10 /* max clique size for cliques() and maxindset() */
+
+#if MAXN
+static TLS_ATTR int workshort[MAXN+2];
+static TLS_ATTR int vv[MAXN],ww[MAXN];
+static TLS_ATTR int workperm[MAXN];
+static TLS_ATTR int bucket[MAXN+2];
+static TLS_ATTR int count[MAXN];
+static TLS_ATTR set workset[MAXM];
+static TLS_ATTR set w01[MAXM],w02[MAXM],w03[MAXM],w12[MAXM],w13[MAXM],w23[MAXM];
+static TLS_ATTR set pt0[MAXM],pt1[MAXM],pt2[MAXM];
+static TLS_ATTR set wss[MAXCLIQUE-1][MAXM];
+static TLS_ATTR set ws1[MAXM],ws2[MAXM];
+#else
+DYNALLSTAT(int,workshort,workshort_sz);
+DYNALLSTAT(int,vv,vv_sz);
+DYNALLSTAT(int,ww,ww_sz);
+DYNALLSTAT(int,workperm,workperm_sz);
+DYNALLSTAT(int,bucket,bucket_sz);
+DYNALLSTAT(int,count,count_sz);
+DYNALLSTAT(set,ws1,ws1_sz);
+DYNALLSTAT(set,ws2,ws2_sz);
+DYNALLSTAT(set,workset,workset_sz);
+DYNALLSTAT(set,w01,w01_sz);
+DYNALLSTAT(set,w02,w02_sz);
+DYNALLSTAT(set,w03,w03_sz);
+DYNALLSTAT(set,w12,w12_sz);
+DYNALLSTAT(set,w13,w13_sz);
+DYNALLSTAT(set,w23,w23_sz);
+DYNALLSTAT(set,pt0,pt0_sz);
+DYNALLSTAT(set,pt1,pt1_sz);
+DYNALLSTAT(set,pt2,pt2_sz);
+DYNALLSTAT(set,wss,wss_sz);
+#endif
+
+/* aproto: header new_nauty_protos.h */
+
+/*****************************************************************************
+* *
+* This file contains a number of procedures which compute vertex-invariants *
+* for stronger partition refinement. Since entirely different *
+* vertex-invariants seem to work better for different types of graph, we *
+* cannot do more than give a small collection of representative examples. *
+* Any serious computations with difficult graphs may well need to use *
+* specially-written vertex-invariants. The use of vertex-invariants *
+* procedures is supported by nauty from version 1.5 onwards, via the *
+* options userinvarproc, mininvarlevel, maxinvarlevel and invararg. *
+* The meaning of these fields in detail are as follows: *
+* userinvarproc is the address of the vertex-invariant procedure. If *
+* no vertex-invariants is required, this field should *
+* have the value NULL. *
+* maxinvarlevel The absolute value of this is the maximum level in the *
+* search tree at which the vertex-invariant will be *
+* computed. The root of the tree is at level 1, so the *
+* vertex-invariant will not be invoked at all if *
+* maxinvarlevel==0. Negative values of maxinvarlevel *
+* request nauty to not compute the vertex-invariant at *
+* a level greater than that of the earliest node (if any) *
+* on the path to the first leaf of the search tree at *
+* which the vertex-invariant refines the partition. *
+* mininvarlevel The absolute value of this is the minimum level in the *
+* search tree at which the vertex-invariant will be *
+* computed. The root of the tree is at level 1, so there *
+* is no effective limit if mininvarlevel is -1, 0 or 1. *
+* Negative values of mininvarlevel request nauty to not *
+* compute the vertex-invariant at a level less than *
+* that of the earliest node (if any) on the path to the *
+* first leaf of the search tree at which the *
+* vertex-invariant refines the partition. *
+* invararg is passed to the vertex-invariant procedure via the *
+* argument of the same name. It can be used by the *
+* procedure for any purpose. *
+* Note that negative values of maxinvarlevel and mininvarlevel make the *
+* canonical labelling invalid, but can speed automorphism group finding. *
+* Nauty already knows this and takes their absolute values. *
+* *
+* A vertex-invariant must be declared thus: *
+* void invarproc(g,lab,ptn,level,numcells,tvpos,invar,invararg,digraph,m,n) *
+* All of these arguments must be treated as read-only except for invar. *
+* g : the graph, exactly as passed to nauty() *
+* lab,ptn : the current partition nest (see nauty.h for the format) *
+* level : the level of this node in the search tree. *
+* numcells : the number of cells in the partition at this node. *
+* tvpos : the index in (lab,ptn) of one cell in the partition. *
+* If level <= 1, the cell will be the first fragment of the *
+* first active cell (as provided by the initial call to nauty), *
+* or the first cell, if there were no active cells. *
+* If level > 1, the cell will be the singleton cell which was *
+* created to make this node of the search tree from its parent. *
+* invararg : a copy of options.invararg *
+* digraph : a copy of options.digraph *
+* m,n : size parameters as passed to nauty() *
+* invar : an array to return the answer in. The procedure must put in *
+* each invar[i] (0 <= i < n) an invariant of the 6-tuple *
+* (<vertex i>,g,<the partition nest to this level>,level, *
+* invararg,digraph) *
+* Note that invar[] is declared as an int array. Since the *
+* absolute value of the invariant is irrelevant, only the *
+* comparative values, any short, int or long value can be *
+* assigned to the entries of invar[] without fear. However, *
+* you should assign a value less than 077777 to ensure machine- *
+* independence of the canonical labelling. *
+* *
+* The refinement procedure has already been called before the invariant *
+* procedure is called. That means that the partition is equitable if *
+* digraph==FALSE. *
+* *
+*****************************************************************************/
+
+/*****************************************************************************
+* *
+* twopaths() assigns to each vertex v the sum of the weights of each vertex *
+* which can be reached from v along a walk of length two (including itself *
+* usually). The weight of each vertex w is defined as the ordinal number *
+* of the cell containing w, starting at 1 for the first cell. *
+* *
+*****************************************************************************/
+
+void
+twopaths(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,v,w;
+ int wt;
+ set *gv,*gw;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"twopaths");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"twopaths");
+#endif
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = wt;
+ if (ptn[i] <= level) ++wt;
+ }
+
+ for (v = 0, gv = (set*)g; v < n; ++v, gv += M)
+ {
+ EMPTYSET(workset,m);
+ w = -1;
+ while ((w = nextelement(gv,M,w)) >= 0)
+ {
+ gw = GRAPHROW(g,w,m);
+ for (i = M; --i >= 0;) UNION(workset[i],gw[i]);
+ }
+ wt = 0;
+ w = -1;
+ while ((w = nextelement(workset,M,w)) >= 0) ACCUM(wt,workshort[w]);
+ invar[v] = wt;
+ }
+}
+
+/*****************************************************************************
+* *
+* quadruples() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2,v3), where w(v,v1,v2,v3) depends on the number of *
+* vertices adjacent to an odd number of {v,v1,v2,v3}, and to the cells *
+* that v,v1,v2,v3 belong to. {v,v1,v2,v3} are permitted to range over all *
+* distinct 4-tuples which contain at least one member in the cell tvpos. *
+* *
+*****************************************************************************/
+
+void
+quadruples(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ set *gw;
+ int wt;
+ int v,iv,v1,v2,v3;
+ set *gv;
+ long wv,wv1,wv2,wv3;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"quadruples");
+ DYNALLOC1(set,ws1,ws1_sz,m,"quadruples");
+ DYNALLOC1(set,workset,workset_sz,m,"quadruples");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ2(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ iv = tvpos - 1;
+ do
+ {
+ v = lab[++iv];
+ gv = GRAPHROW(g,v,m);
+ wv = workshort[v];
+ for (v1 = 0; v1 < n-2; ++v1)
+ {
+ wv1 = workshort[v1];
+ if (wv1 == wv && v1 <= v) continue;
+ wv1 += wv;
+ gw = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv[i] ^ gw[i];
+ for (v2 = v1+1; v2 < n-1; ++v2)
+ {
+ wv2 = workshort[v2];
+ if (wv2 == wv && v2 <= v) continue;
+ wv2 += wv1;
+ gw = GRAPHROW(g,v2,m);
+ for (i = M; --i >= 0;) ws1[i] = workset[i] ^ gw[i];
+ for (v3 = v2+1; v3 < n; ++v3)
+ {
+ wv3 = workshort[v3];
+ if (wv3 == wv && v3 <= v) continue;
+ wv3 += wv2;
+ gw = GRAPHROW(g,v3,m);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ if ((sw = ws1[i] ^ gw[i]) != 0) pc += POPCOUNT(sw);
+ wt = (FUZZ1(pc)+wv3) & 077777;
+ wt = FUZZ2(wt);
+ ACCUM(invar[v],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ ACCUM(invar[v3],wt);
+ }
+ }
+ }
+ }
+ while (ptn[iv] > level);
+}
+
+/*****************************************************************************
+* *
+* triples() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2), where w(v,v1,v2) depends on the number of vertices *
+* adjacent to an odd number of {v,v1,v2}, and to the cells that *
+* v,v1,v2 belong to. {v,v1,v2} are permitted to range over all distinct *
+* triples which contain at least one member in the cell tvpos. *
+* *
+*****************************************************************************/
+
+void
+triples(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ set *gw;
+ int wt;
+ int v,iv,v1,v2;
+ set *gv;
+ long wv,wv1,wv2;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"triples");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"triples");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ1(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ iv = tvpos - 1;
+ do
+ {
+ v = lab[++iv];
+ gv = GRAPHROW(g,v,m);
+ wv = workshort[v];
+ for (v1 = 0; v1 < n-1; ++v1)
+ {
+ wv1 = workshort[v1];
+ if (wv1 == wv && v1 <= v) continue;
+ wv1 += wv;
+ gw = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv[i] ^ gw[i];
+ for (v2 = v1+1; v2 < n; ++v2)
+ {
+ wv2 = workshort[v2];
+ if (wv2 == wv && v2 <= v) continue;
+ wv2 += wv1;
+ gw = GRAPHROW(g,v2,m);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ if ((sw = workset[i] ^ gw[i]) != 0) pc += POPCOUNT(sw);
+ wt = (FUZZ1(pc)+wv2) & 077777;
+ wt = FUZZ2(wt);
+ ACCUM(invar[v],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ }
+ }
+ }
+ while (ptn[iv] > level);
+}
+
+/*****************************************************************************
+* *
+* adjtriang() assigns to each vertex v a value depending on the numbers *
+* of common neighbours between each pair {v1,v2} of neighbours of v, and *
+* which cells v1 and v2 lie in. The vertices v1 and v2 must be adjacent *
+* if invararg == 0 and not adjacent if invararg == 1. *
+* *
+*****************************************************************************/
+
+void
+adjtriang(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int j,pc;
+ setword sw;
+ set *gi;
+ int wt;
+ int i,v1,v2;
+ boolean v1v2;
+ set *gv1,*gv2;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"adjtriang");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"adjtriang");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ1(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ for (v1 = 0, gv1 = g; v1 < n; ++v1, gv1 += M)
+ {
+ for (v2 = (digraph ? 0 : v1+1); v2 < n; ++v2)
+ {
+ if (v2 == v1) continue;
+ v1v2 = (ISELEMENT(gv1,v2) != 0);
+ if ((invararg == 0 && !v1v2)
+ || (invararg == 1 && v1v2)) continue;
+ wt = workshort[v1];
+ ACCUM(wt,workshort[v2]);
+ ACCUM(wt,v1v2);
+
+ gv2 = GRAPHROW(g,v2,m);
+ for (i = M; --i >= 0;) workset[i] = gv1[i] & gv2[i];
+ i = -1;
+ while ((i = nextelement(workset,M,i)) >= 0)
+ {
+ pc = 0;
+ gi = GRAPHROW(g,i,m);
+ for (j = M; --j >= 0;)
+ if ((sw = workset[j] & gi[j]) != 0) pc += POPCOUNT(sw);
+ pc = (pc + wt) & 077777;
+ ACCUM(invar[i],pc);
+ }
+ }
+ }
+}
+
+/*****************************************************************************
+* *
+* getbigcells(ptn,level,minsize,bigcells,cellstart,cellsize,n) is an *
+* auxiliary procedure to make a list of all the large cells in the current *
+* partition. On entry, ptn, level and n have their usual meanings, *
+* while minsize is the smallest size of an interesting cell. On return, *
+* bigcells is the number of cells of size at least minsize, cellstart[0...] *
+* contains their starting positions in ptn, and cellsize[0...] contain *
+* their sizes. These two arrays are in increasing order of cell size, *
+* then position. *
+* *
+*****************************************************************************/
+
+void
+getbigcells(int *ptn, int level, int minsize, int *bigcells,
+ int *cellstart, int *cellsize, int n)
+{
+ int cell1,cell2,j;
+ int si,st;
+ int bc,i,h;
+
+ bc = 0;
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+
+ if (cell2 >= cell1 + minsize - 1)
+ {
+ cellstart[bc] = cell1;
+ cellsize[bc] = cell2 - cell1 + 1;
+ ++bc;
+ }
+ }
+ *bigcells = bc;
+
+ j = bc / 3;
+ h = 1;
+ do
+ h = 3 * h + 1;
+ while (h < j);
+
+ do /* shell sort */
+ {
+ for (i = h; i < bc; ++i)
+ {
+ st = cellstart[i];
+ si = cellsize[i];
+ for (j = i; cellsize[j-h] > si ||
+ (cellsize[j-h] == si && cellstart[j-h] > st); )
+ {
+ cellsize[j] = cellsize[j-h];
+ cellstart[j] = cellstart[j-h];
+ if ((j -= h) < h) break;
+ }
+ cellsize[j] = si;
+ cellstart[j] = st;
+ }
+ h /= 3;
+ }
+ while (h > 0);
+}
+
+/*****************************************************************************
+* *
+* celltrips() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2), where w(v,v1,v2) depends on the number of vertices *
+* adjacent to an odd number of {v,v1,v2}. {v,v1,v2} are constrained to *
+* belong to the same cell. We try the cells in increasing order of size, *
+* and stop as soon as any cell splits. *
+* *
+*****************************************************************************/
+
+void
+celltrips(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ set *gw;
+ int wt;
+ int v,iv,v1,iv1,v2,iv2;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ set *gv;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"celltrips");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"celltrips");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,3,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (iv = cell1; iv <= cell2 - 2; ++iv)
+ {
+ v = lab[iv];
+ gv = GRAPHROW(g,v,m);
+ for (iv1 = iv + 1; iv1 <= cell2 - 1; ++iv1)
+ {
+ v1 = lab[iv1];
+ gw = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv[i] ^ gw[i];
+ for (iv2 = iv1 + 1; iv2 <= cell2; ++iv2)
+ {
+ v2 = lab[iv2];
+ gw = GRAPHROW(g,v2,m);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ if ((sw = workset[i] ^ gw[i]) != 0)
+ pc += POPCOUNT(sw);
+ wt = FUZZ1(pc);
+ ACCUM(invar[v],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* cellquads() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2,v3), where w(v,v1,v2,v3) depends on the number of *
+* vertices adjacent to an odd number of {v,v1,v2,v3}. {v,v1,v2,v3} are *
+* constrained to belong to the same cell. We try the cells in increasing *
+* order of size, and stop as soon as any cell splits. *
+* *
+*****************************************************************************/
+
+void
+cellquads(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ set *gw;
+ int wt;
+ int v,iv,v1,iv1,v2,iv2,v3,iv3;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ set *gv;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"cellquads");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellquads");
+ DYNALLOC1(set,ws1,ws1_sz,m,"cellquads");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,4,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (iv = cell1; iv <= cell2 - 3; ++iv)
+ {
+ v = lab[iv];
+ gv = GRAPHROW(g,v,m);
+ for (iv1 = iv + 1; iv1 <= cell2 - 2; ++iv1)
+ {
+ v1 = lab[iv1];
+ gw = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv[i] ^ gw[i];
+ for (iv2 = iv1 + 1; iv2 <= cell2 - 1; ++iv2)
+ {
+ v2 = lab[iv2];
+ gw = GRAPHROW(g,v2,m);
+ for (i = M; --i >= 0;) ws1[i] = workset[i] ^ gw[i];
+ for (iv3 = iv2 + 1; iv3 <= cell2; ++iv3)
+ {
+ v3 = lab[iv3];
+ gw = GRAPHROW(g,v3,m);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ if ((sw = ws1[i] ^ gw[i]) != 0)
+ pc += POPCOUNT(sw);
+ wt = FUZZ1(pc);
+ ACCUM(invar[v],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ ACCUM(invar[v3],wt);
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* cellquins() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2,v3,v4), where w(v,v1,v2,v3,v4) depends on the number *
+* of vertices adjacent to an odd number of {v,v1,v2,v3,v4}. *
+* {v,v1,v2,v3,v4} are constrained to belong to the same cell. We try the *
+* cells in increasing order of size, and stop as soon as any cell splits. *
+* *
+*****************************************************************************/
+
+void
+cellquins(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ set *gw;
+ int wt;
+ int v,iv,v1,iv1,v2,iv2,v3,iv3,v4,iv4;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ set *gv;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"cellquins");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellquins");
+ DYNALLOC1(set,ws1,ws1_sz,m,"cellquins");
+ DYNALLOC1(set,ws2,ws2_sz,m,"cellquins");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,5,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (iv = cell1; iv <= cell2 - 4; ++iv)
+ {
+ v = lab[iv];
+ gv = GRAPHROW(g,v,m);
+ for (iv1 = iv + 1; iv1 <= cell2 - 3; ++iv1)
+ {
+ v1 = lab[iv1];
+ gw = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv[i] ^ gw[i];
+ for (iv2 = iv1 + 1; iv2 <= cell2 - 2; ++iv2)
+ {
+ v2 = lab[iv2];
+ gw = GRAPHROW(g,v2,m);
+ for (i = M; --i >= 0;) ws1[i] = workset[i] ^ gw[i];
+ for (iv3 = iv2 + 1; iv3 <= cell2 - 1; ++iv3)
+ {
+ v3 = lab[iv3];
+ gw = GRAPHROW(g,v3,m);
+ for (i = M; --i >= 0;) ws2[i] = ws1[i] ^ gw[i];
+ for (iv4 = iv3 + 1; iv4 <= cell2; ++iv4)
+ {
+ v4 = lab[iv4];
+ gw = GRAPHROW(g,v4,m);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ if ((sw = ws2[i] ^ gw[i]) != 0)
+ pc += POPCOUNT(sw);
+ wt = FUZZ1(pc);
+ ACCUM(invar[v],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ ACCUM(invar[v3],wt);
+ ACCUM(invar[v4],wt);
+ }
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* uniqinter(s1,s2,m) returns the number in both sets if it is unique, *
+* or -1 if there is none or it is not unique. *
+*****************************************************************************/
+
+static int
+uniqinter(set *s1, set *s2, int m)
+{
+ int i,j;
+ setword w;
+
+ for (i = 0; i < M; ++i)
+ {
+ if ((w = s1[i] & s2[i]) != 0)
+ {
+ j = FIRSTBITNZ(w);
+ if (w != BITT[j]) return -1;
+ j += TIMESWORDSIZE(i);
+ for (++i; i < M; ++i)
+ if (s1[i] & s2[i]) return -1;
+ return j;
+ }
+ }
+ return -1;
+}
+
+/*****************************************************************************
+* *
+* cellfano2() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2,v3), where w(v,v1,v2,v3) depends on the number of *
+* fano-plane analogues containing {v,v1,v2,v3}. {v,v1,v2,v3} are *
+* constrained to belong to the same cell and being independent and *
+* non-collinear. We try the cells in increasing order of size, and stop *
+* as soon as any cell splits. *
+* *
+*****************************************************************************/
+
+void
+cellfano2(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ int wt;
+ int v0,v1,v2,v3,iv0,iv1,iv2,iv3;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ int nw,x01,x02,x03,x12,x13,x23;
+ int pnt0,pnt1,pnt2;
+ set *gv0,*gv1,*gv2,*gv3;
+ set *gp0,*gp1,*gp2;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellfano2");
+ DYNALLOC1(int,vv,vv_sz,n,"cellfano2");
+ DYNALLOC1(int,ww,ww_sz,n,"cellfano2");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,4,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (iv0 = cell1; iv0 <= cell2 - 3; ++iv0)
+ {
+ v0 = lab[iv0];
+ gv0 = GRAPHROW(g,v0,m);
+ nw = 0;
+ for (iv1 = iv0 + 1; iv1 <= cell2; ++iv1)
+ {
+ v1 = lab[iv1];
+ if (ISELEMENT(gv0,v1)) continue;
+ if ((x01 = uniqinter(gv0,GRAPHROW(g,v1,m),m)) < 0) continue;
+ vv[nw] = v1;
+ ww[nw] = x01;
+ ++nw;
+ }
+
+ for (iv1 = 0; iv1 < nw-2; ++iv1)
+ {
+ v1 = vv[iv1];
+ gv1 = GRAPHROW(g,v1,m);
+ x01 = ww[iv1];
+
+ for (iv2 = iv1 + 1; iv2 < nw-1; ++iv2)
+ {
+ x02 = ww[iv2];
+ if (x02 == x01) continue;
+ v2 = vv[iv2];
+ if (ISELEMENT(gv1,v2)) continue;
+ gv2 = GRAPHROW(g,v2,m);
+ if ((x12 = uniqinter(gv1,gv2,m)) < 0) continue;
+
+ for (iv3 = iv2 + 1; iv3 < nw; ++iv3)
+ {
+ x03 = ww[iv3];
+ if (x03 == x01 || x03 == x02) continue;
+ v3 = vv[iv3];
+ if (ISELEMENT(gv1,v3) || ISELEMENT(gv2,v3))
+ continue;
+ gv3 = GRAPHROW(g,v3,m);
+ if ((x13 = uniqinter(gv1,gv3,m)) < 0) continue;
+ if ((x23 = uniqinter(gv2,gv3,m)) < 0
+ || x23 == x13) continue;
+
+ if ((pnt0 = uniqinter(GRAPHROW(g,x01,m),
+ GRAPHROW(g,x23,m),m)) < 0)
+ continue;
+ if ((pnt1 = uniqinter(GRAPHROW(g,x02,m),
+ GRAPHROW(g,x13,m),m)) < 0)
+ continue;
+ if ((pnt2 = uniqinter(GRAPHROW(g,x03,m),
+ GRAPHROW(g,x12,m),m)) < 0)
+ continue;
+
+ gp0 = GRAPHROW(g,pnt0,m);
+ gp1 = GRAPHROW(g,pnt1,m);
+ gp2 = GRAPHROW(g,pnt2,m);
+
+ pc = 0;
+ for (i = M; --i >= 0;)
+ {
+ sw = gp0[i] & gp1[i] & gp2[i];
+ if (sw) pc += POPCOUNT(sw);
+ }
+ wt = FUZZ1(pc);
+ ACCUM(invar[v0],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ ACCUM(invar[v3],wt);
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* setnbhd(g,m,n,w,wn) is an auxiliary routine that sets wn to the union *
+* of the neighbours of the vertices in w. *
+* *
+*****************************************************************************/
+
+void
+setnbhd(graph *g, int m, int n, set *w, set *wn)
+{
+ int i,j;
+ set *gi;
+
+ i = nextelement(w,M,-1);
+ if (i < 0)
+ {
+ EMPTYSET(wn,M);
+ return;
+ }
+
+ gi = GRAPHROW(g,i,M);
+ for (j = M; --j >= 0;) wn[j] = gi[j];
+
+ while ((i = nextelement(w,M,i)) >= 0)
+ {
+ gi = GRAPHROW(g,i,M);
+ for (j = M; --j >= 0;) wn[j] |= gi[j];
+ }
+}
+
+/*****************************************************************************
+* *
+* cellfano() assigns to each vertex v a value depending on the set of *
+* weights w(v,v1,v2,v3), where w(v,v1,v2,v3) depends on the number of *
+* fano-plane analogues containing {v,v1,v2,v3}. {v,v1,v2,v3} are *
+* constrained to belong to the same cell and being independent. We try *
+* the cells in increasing order of size, and stop as soon as any cell *
+* splits. *
+* *
+*****************************************************************************/
+
+void
+cellfano(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,pc;
+ setword sw;
+ int wt;
+ int v0,v1,v2,v3,iv0,iv1,iv2,iv3;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ set *gv0,*gv1,*gv2,*gv3;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellfano");
+ DYNALLOC1(set,w01,w01_sz,m,"cellfano");
+ DYNALLOC1(set,w02,w02_sz,m,"cellfano");
+ DYNALLOC1(set,w03,w03_sz,m,"cellfano");
+ DYNALLOC1(set,w12,w12_sz,m,"cellfano");
+ DYNALLOC1(set,w13,w13_sz,m,"cellfano");
+ DYNALLOC1(set,w23,w23_sz,m,"cellfano");
+ DYNALLOC1(set,pt0,pt0_sz,m,"cellfano");
+ DYNALLOC1(set,pt1,pt1_sz,m,"cellfano");
+ DYNALLOC1(set,pt2,pt2_sz,m,"cellfano");
+ DYNALLOC1(set,workset,workset_sz,m,"cellfano");
+#else
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,4,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (iv0 = cell1; iv0 <= cell2 - 3; ++iv0)
+ {
+ v0 = lab[iv0];
+ gv0 = GRAPHROW(g,v0,m);
+ for (iv1 = iv0 + 1; iv1 <= cell2 - 2; ++iv1)
+ {
+ v1 = lab[iv1];
+ if (ISELEMENT(gv0,v1)) continue;
+ gv1 = GRAPHROW(g,v1,m);
+ for (i = M; --i >= 0;) workset[i] = gv0[i] & gv1[i];
+ setnbhd(g,m,n,workset,w01);
+
+ for (iv2 = iv1 + 1; iv2 <= cell2 - 1; ++iv2)
+ {
+ v2 = lab[iv2];
+ if (ISELEMENT(gv0,v2) || ISELEMENT(gv1,v2))
+ continue;
+ gv2 = GRAPHROW(g,v2,m);
+ for (i = M; --i >= 0;) workset[i] = gv0[i] & gv2[i];
+ setnbhd(g,m,n,workset,w02);
+ for (i = M; --i >= 0;) workset[i] = gv1[i] & gv2[i];
+ setnbhd(g,m,n,workset,w12);
+
+ for (iv3 = iv2 + 1; iv3 <= cell2; ++iv3)
+ {
+ v3 = lab[iv3];
+ if (ISELEMENT(gv0,v3) || ISELEMENT(gv1,v3) ||
+ ISELEMENT(gv2,v3))
+ continue;
+ gv3 = GRAPHROW(g,v3,m);
+ for (i = M; --i >= 0;) workset[i] = gv0[i] & gv3[i];
+ setnbhd(g,m,n,workset,w03);
+ for (i = M; --i >= 0;) workset[i] = gv1[i] & gv3[i];
+ setnbhd(g,m,n,workset,w13);
+ for (i = M; --i >= 0;) workset[i] = gv2[i] & gv3[i];
+ setnbhd(g,m,n,workset,w23);
+
+ for (i = M; --i >= 0;) workset[i] = w01[i] & w23[i];
+ setnbhd(g,m,n,workset,pt0);
+ for (i = M; --i >= 0;) workset[i] = w03[i] & w12[i];
+ setnbhd(g,m,n,workset,pt1);
+ for (i = M; --i >= 0;) workset[i] = w02[i] & w13[i];
+ setnbhd(g,m,n,workset,pt2);
+ pc = 0;
+ for (i = M; --i >= 0;)
+ {
+ sw = pt0[i] & pt1[i] & pt2[i];
+ if (sw) pc += POPCOUNT(sw);
+ }
+ wt = FUZZ1(pc);
+ ACCUM(invar[v0],wt);
+ ACCUM(invar[v1],wt);
+ ACCUM(invar[v2],wt);
+ ACCUM(invar[v3],wt);
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* distances() assigns to each vertex v a value depending on the number of *
+* vertices at each distance from v, and what cells they lie in. *
+* If we find any cell which is split in this manner, we don't try any *
+* further cells. *
+* *
+*****************************************************************************/
+
+void
+distances(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i;
+ set *gw;
+ int wt;
+ int d,dlim,cell1,cell2,iv,v,w;
+ boolean success;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"distances");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"distances");
+ DYNALLOC1(set,ws1,ws1_sz,m,"distances");
+ DYNALLOC1(set,ws2,ws2_sz,m,"distances");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ1(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ if (invararg > n || invararg == 0) dlim = n;
+ else dlim = invararg+1;
+
+ success = FALSE;
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ if (cell2 == cell1) continue;
+
+ for (iv = cell1; iv <= cell2; ++iv)
+ {
+ v = lab[iv];
+ EMPTYSET(ws1,m);
+ ADDELEMENT(ws1,v);
+ EMPTYSET(ws2,m);
+ ADDELEMENT(ws2,v);
+ for (d = 1; d < dlim; ++d)
+ {
+ EMPTYSET(workset,m);
+ wt = 0;
+ w = -1;
+ while ((w = nextelement(ws2,M,w)) >= 0)
+ {
+ gw = GRAPHROW(g,w,m);
+ ACCUM(wt,workshort[w]);
+ for (i = M; --i >= 0;) workset[i] |= gw[i];
+ }
+ if (wt == 0) break;
+ ACCUM(wt,d);
+ wt = FUZZ2(wt);
+ ACCUM(invar[v],wt);
+ for (i = M; --i >= 0;)
+ {
+ ws2[i] = workset[i] & ~ws1[i];
+ ws1[i] |= ws2[i];
+ }
+ }
+ if (invar[v] != invar[lab[cell1]]) success = TRUE;
+ }
+ if (success) break;
+ }
+}
+
+/*****************************************************************************
+* *
+* indsets() assigns to each vertex v a value depending on which cells the *
+* vertices which join v in an independent set lie in. The size of the *
+* independent sets which are used is the smallest of invararg and MAXCLIQUE.*
+* *
+*****************************************************************************/
+
+void
+indsets(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i;
+ int wt;
+ set *gv;
+ int ss,setsize;
+ int v[MAXCLIQUE];
+ long wv[MAXCLIQUE];
+ set *s0,*s1;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"indsets");
+ DYNALLOC2(set,wss,wss_sz,m,MAXCLIQUE-1,"indsets");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ if (invararg <= 1 || digraph) return;
+
+ if (invararg > MAXCLIQUE) setsize = MAXCLIQUE;
+ else setsize = invararg;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ2(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ for (v[0] = 0; v[0] < n; ++v[0])
+ {
+ wv[0] = workshort[v[0]];
+ s0 = (set*)wss;
+ EMPTYSET(s0,m);
+ for (i = v[0]+1; i < n; ++i) ADDELEMENT(s0,i);
+ gv = GRAPHROW(g,v[0],m);
+ for (i = M; --i >= 0;) s0[i] &= ~gv[i];
+ ss = 1;
+ v[1] = v[0];
+ while (ss > 0)
+ {
+ if (ss == setsize)
+ {
+ wt = FUZZ1(wv[ss-1]);
+ for (i = ss; --i >= 0;) ACCUM(invar[v[i]],wt);
+ --ss;
+ }
+ else if ((v[ss] = nextelement((set*)wss+M*(ss-1),M,v[ss])) < 0)
+ --ss;
+ else
+ {
+ wv[ss] = wv[ss-1] + workshort[v[ss]];
+ ++ss;
+ if (ss < setsize)
+ {
+ gv = GRAPHROW(g,v[ss-1],m);
+ s1 = (set*)wss + M*(ss-2);
+ for (i = M; --i >= 0;) s1[i+M] = s1[i] & ~gv[i];
+ v[ss] = v[ss-1];
+ }
+ }
+ }
+ }
+}
+
+/*****************************************************************************
+* *
+* cliques() assigns to each vertex v a value depending on which cells the *
+* vertices which join v in a clique lie in. The size of the cliques used *
+* is the smallest of invararg and MAXCLIQUE. *
+* *
+*****************************************************************************/
+
+void
+cliques(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i;
+ int wt;
+ set *gv;
+ int ss,setsize;
+ int v[MAXCLIQUE];
+ long wv[MAXCLIQUE];
+ set *ns;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cliques");
+ DYNALLOC2(set,wss,wss_sz,m,MAXCLIQUE-1,"cliques");
+#else
+ set wss[MAXCLIQUE-1][MAXM];
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ if (invararg <= 1 || digraph) return;
+
+ if (invararg > MAXCLIQUE) setsize = MAXCLIQUE;
+ else setsize = invararg;
+
+ wt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = FUZZ2(wt);
+ if (ptn[i] <= level) ++wt;
+ }
+
+ for (v[0] = 0; v[0] < n; ++v[0])
+ {
+ wv[0] = workshort[v[0]];
+ gv = GRAPHROW(g,v[0],m);
+ ns = (set*)wss;
+ for (i = M; --i >= 0;) ns[i] = gv[i];
+ ss = 1;
+ v[1] = v[0];
+ while (ss > 0)
+ {
+ if (ss == setsize)
+ {
+ wt = FUZZ1(wv[ss-1]);
+ for (i = ss; --i >= 0;) ACCUM(invar[v[i]],wt);
+ --ss;
+ }
+ else if ((v[ss] = nextelement((set*)wss+M*(ss-1),M,v[ss])) < 0)
+ --ss;
+ else
+ {
+ wv[ss] = wv[ss-1] + workshort[v[ss]];
+ ++ss;
+ if (ss < setsize)
+ {
+ gv = GRAPHROW(g,v[ss-1],m);
+ ns = (set*)wss + M*(ss-2);
+ for (i = M; --i >= 0;) ns[i+M] = ns[i] & gv[i];
+ v[ss] = v[ss-1];
+ }
+ }
+ }
+ }
+}
+
+/*****************************************************************************
+* *
+* cellcliq() assigns to each vertex v a value depending on the number of *
+* cliques which v lies in and which lie in the same cell as v. The size *
+* of clique counted is the smallest of invararg and MAXCLIQUE. We try the *
+* cells in increasing order of size and stop as soon as any cell splits. *
+* *
+*****************************************************************************/
+
+void
+cellcliq(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i;
+ int wt;
+ set *gv;
+ int ss,setsize;
+ int v[MAXCLIQUE];
+ set *ns;
+ int *cellstart,*cellsize;
+ int iv,icell,bigcells,cell1,cell2;
+ int pc;
+ setword sw;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"cellcliq");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellcliq");
+ DYNALLOC2(set,wss,wss_sz,m,MAXCLIQUE-1,"cellcliq");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ if (invararg <= 1 || digraph) return;
+
+ if (invararg > MAXCLIQUE) setsize = MAXCLIQUE;
+ else setsize = invararg;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,setsize > 6 ? setsize : 6,&bigcells,
+ cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+
+ EMPTYSET(workset,m);
+ for (iv = cell1; iv <= cell2; ++iv) ADDELEMENT(workset,lab[iv]);
+
+ for (iv = cell1; iv <= cell2; ++iv)
+ {
+ v[0] = lab[iv];
+ gv = GRAPHROW(g,v[0],m);
+ ns = (set*)wss;
+ pc = 0;
+
+ for (i = M; --i >= 0;)
+ {
+ ns[i] = gv[i] & workset[i];
+ if ((sw = ns[i]) != 0) pc += POPCOUNT(sw);
+ }
+ if (pc <= 1 || pc >= cellsize[icell] - 2) continue;
+
+ ss = 1;
+ v[1] = v[0];
+ while (ss > 0)
+ {
+ if (ss == setsize)
+ {
+ for (i = ss; --i >= 0;) ++invar[v[i]];
+ --ss;
+ }
+ else if ((v[ss]
+ = nextelement((set*)wss+M*(ss-1),M,v[ss])) < 0)
+ --ss;
+ else
+ {
+ ++ss;
+ if (ss < setsize)
+ {
+ gv = GRAPHROW(g,v[ss-1],m);
+ ns = (set*)wss + M*(ss-2);
+ for (i = M; --i >= 0;) ns[i+M] = ns[i] & gv[i];
+ v[ss] = v[ss-1];
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (iv = cell1 + 1; iv <= cell2; ++iv)
+ if (invar[lab[iv]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* cellind() assigns to each vertex v a value depending on the number of *
+* independent sets which v lies in and which lie in the same cell as v. *
+* The size of clique counted is the smallest of invararg and MAXCLIQUE. *
+* We try the cells in increasing order of size and stop as soon as any *
+* cell splits. *
+* *
+*****************************************************************************/
+
+void
+cellind(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i;
+ int wt;
+ set *gv;
+ int ss,setsize;
+ int v[MAXCLIQUE];
+ set *ns;
+ int *cellstart,*cellsize;
+ int iv,icell,bigcells,cell1,cell2;
+ int pc;
+ setword sw;
+
+#if !MAXN
+ DYNALLOC1(set,workset,workset_sz,m,"cellind");
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"cellind");
+ DYNALLOC2(set,wss,wss_sz,m,MAXCLIQUE-1,"cellind");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ if (invararg <= 1 || digraph) return;
+
+ if (invararg > MAXCLIQUE) setsize = MAXCLIQUE;
+ else setsize = invararg;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,setsize > 6 ? setsize : 6,&bigcells,
+ cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+
+ EMPTYSET(workset,m);
+ for (iv = cell1; iv <= cell2; ++iv) ADDELEMENT(workset,lab[iv]);
+
+ for (iv = cell1; iv <= cell2; ++iv)
+ {
+ v[0] = lab[iv];
+ gv = GRAPHROW(g,v[0],m);
+ ns = (set*)wss;
+ pc = 0;
+
+ for (i = M; --i >= 0;)
+ {
+ ns[i] = ~gv[i] & workset[i];
+ if ((sw = ns[i]) != 0) pc += POPCOUNT(sw);
+ }
+ if (pc <= 1 || pc >= cellsize[icell] - 2) continue;
+
+ ss = 1;
+ v[1] = v[0];
+ while (ss > 0)
+ {
+ if (ss == setsize)
+ {
+ for (i = ss; --i >= 0;) ++invar[v[i]];
+ --ss;
+ }
+ else if ((v[ss]
+ = nextelement((set*)wss+M*(ss-1),M,v[ss])) < 0)
+ --ss;
+ else
+ {
+ ++ss;
+ if (ss < setsize)
+ {
+ gv = GRAPHROW(g,v[ss-1],m);
+ ns = (set*)wss + M*(ss-2);
+ for (i = M; --i >= 0;) ns[i+M] = ns[i] & ~gv[i];
+ v[ss] = v[ss-1];
+ }
+ }
+ }
+ }
+ wt = invar[lab[cell1]];
+ for (iv = cell1 + 1; iv <= cell2; ++iv)
+ if (invar[lab[iv]] != wt) return;
+ }
+}
+
+/*****************************************************************************
+* *
+* adjacencies() assigns to each vertex v a code depending on which cells *
+* it is joined to and from, and how many times. It is intended to provide *
+* better partitioning that the normal refinement routine for digraphs. *
+* It will not help with undirected graphs in nauty at all. *
+* *
+*****************************************************************************/
+
+void
+adjacencies(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,v,w;
+ int vwt,wwt;
+ set *gv;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"adjacencies");
+#endif
+
+ vwt = 1;
+ for (i = 0; i < n; ++i)
+ {
+ workshort[lab[i]] = vwt;
+ if (ptn[i] <= level) ++vwt;
+ invar[i] = 0;
+ }
+
+ for (v = 0, gv = (set*)g; v < n; ++v, gv += M)
+ {
+ vwt = FUZZ1(workshort[v]);
+ wwt = 0;
+ w = -1;
+ while ((w = nextelement(gv,M,w)) >= 0)
+ {
+ ACCUM(wwt,FUZZ2(workshort[w]));
+ ACCUM(invar[w],vwt);
+ }
+ ACCUM(invar[v],wwt);
+ }
+}
+
+/*****************************************************************************
+* *
+* nautinv_check() checks that this file is compiled compatibly with the *
+* given parameters. If not, call exit(1). *
+* *
+*****************************************************************************/
+
+void
+nautinv_check(int wordsize, int m, int n, int version)
+{
+ if (wordsize != WORDSIZE)
+ {
+ fprintf(ERRFILE,"Error: WORDSIZE mismatch in nautinv.c\n");
+ exit(1);
+ }
+
+#if MAXN
+ if (m > MAXM)
+ {
+ fprintf(ERRFILE,"Error: MAXM inadequate in nautinv.c\n");
+ exit(1);
+ }
+
+ if (n > MAXN)
+ {
+ fprintf(ERRFILE,"Error: MAXN inadequate in nautinv.c\n");
+ exit(1);
+ }
+#endif
+
+ if (version < NAUTYREQUIRED)
+ {
+ fprintf(ERRFILE,"Error: nautinv.c version mismatch\n");
+ exit(1);
+ }
+}
+
+/*****************************************************************************
+* *
+* nautinv_freedyn() - free the dynamic memory in this module *
+* *
+*****************************************************************************/
+
+void
+nautinv_freedyn(void)
+{
+#if !MAXN
+ DYNFREE(workset,workset_sz);
+ DYNFREE(workshort,workshort_sz);
+ DYNFREE(ws1,ws1_sz);
+ DYNFREE(ws2,ws2_sz);
+ DYNFREE(vv,vv_sz);
+ DYNFREE(ww,ww_sz);
+ DYNFREE(w01,w01_sz);
+ DYNFREE(w02,w02_sz);
+ DYNFREE(w03,w03_sz);
+ DYNFREE(w12,w12_sz);
+ DYNFREE(w13,w13_sz);
+ DYNFREE(w23,w23_sz);
+ DYNFREE(pt0,pt0_sz);
+ DYNFREE(pt1,pt1_sz);
+ DYNFREE(pt2,pt2_sz);
+ DYNFREE(wss,wss_sz);
+#endif
+}
+
+/*===================================================================*/
+
+
+/*****************************************************************************
+* *
+* semirefine(g,lab,ptn,level,numcells,strength,active,m,n) performs a *
+* refinement operation on the partition at the specified level of the *
+* partition nest (lab,ptn). *numcells is assumed to contain the number of *
+* cells on input, and is updated. The initial set of active cells (alpha *
+* in the paper) is specified in the set active. Precisely, x is in active *
+* iff the cell starting at index x in lab is active. *
+* *code is set to a value which depends on the fine detail of the *
+* algorithm, but which is independent of the labelling of the graph. *
+* *
+*****************************************************************************/
+
+static int
+semirefine(graph *g, int *lab, int *ptn, int level, int *numcells,
+ int strength, set *active, int m, int n)
+{
+ int i,c1,c2,labc1;
+ setword x;
+ set *set1,*set2;
+ int split1,split2,cell1,cell2;
+ int cnt,bmin,bmax;
+ long longcode;
+ set *gptr;
+ int maxcell,maxpos,hint;
+
+#if !MAXN
+ DYNALLOC1(int,workperm,workperm_sz,n,"refine");
+ DYNALLOC1(set,workset,workset_sz,m,"refine");
+ DYNALLOC1(int,bucket,bucket_sz,n+2,"refine");
+ DYNALLOC1(int,count,count_sz,n,"refine");
+#endif
+
+ longcode = *numcells;
+ split1 = -1;
+ hint = 0;
+ while (*numcells < n && ((split1 = hint, ISELEMENT(active,split1))
+ || (split1 = nextelement(active,M,split1)) >= 0
+ || (split1 = nextelement(active,M,-1)) >= 0))
+ {
+ DELELEMENT(active,split1);
+ for (split2 = split1; ptn[split2] > level; ++split2) {}
+ longcode = MASH(longcode,split1+split2);
+ if (split1 == split2) /* trivial splitting cell */
+ {
+ gptr = GRAPHROW(g,lab[split1],M);
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ if (cell1 == cell2) continue;
+ c1 = cell1;
+ c2 = cell2;
+ while (c1 <= c2)
+ {
+ labc1 = lab[c1];
+ if (ISELEMENT(gptr,labc1))
+ ++c1;
+ else
+ {
+ lab[c1] = lab[c2];
+ lab[c2] = labc1;
+ --c2;
+ }
+ }
+ if (c2 >= cell1 && c1 <= cell2)
+ {
+ ptn[c2] = level;
+ longcode = MASH(longcode,FUZZ1(c2));
+ ++*numcells;
+ if (ISELEMENT(active,cell1) || c2-cell1 >= cell2-c1)
+ {
+ ADDELEMENT(active,c1);
+ if (c1 == cell2) hint = c1;
+ }
+ else
+ {
+ ADDELEMENT(active,cell1);
+ if (c2 == cell1) hint = cell1;
+ }
+ }
+ }
+ }
+ else /* nontrivial splitting cell */
+ {
+ EMPTYSET(workset,m);
+ for (i = split1; i <= split2; ++i)
+ ADDELEMENT(workset,lab[i]);
+ longcode = MASH(longcode,FUZZ2(split2-split1+1));
+
+ for (cell1 = 0; cell1 < n; cell1 = cell2 + 1)
+ {
+ for (cell2 = cell1; ptn[cell2] > level; ++cell2) {}
+ if (cell1 == cell2) continue;
+ i = cell1;
+ set1 = workset;
+ set2 = GRAPHROW(g,lab[i],m);
+ cnt = 0;
+ for (c1 = m; --c1 >= 0;)
+ if ((x = ((*set1++) & (*set2++))) != 0)
+ cnt += POPCOUNT(x);
+
+ count[i] = bmin = bmax = cnt;
+ bucket[cnt] = 1;
+ while (++i <= cell2)
+ {
+ set1 = workset;
+ set2 = GRAPHROW(g,lab[i],m);
+ cnt = 0;
+ for (c1 = m; --c1 >= 0;)
+ if ((x = ((*set1++) & (*set2++))) != 0)
+ cnt += POPCOUNT(x);
+
+ while (bmin > cnt) bucket[--bmin] = 0;
+ while (bmax < cnt) bucket[++bmax] = 0;
+ ++bucket[cnt];
+ count[i] = cnt;
+ }
+ if (bmin == bmax)
+ {
+ longcode = MASH(longcode,FUZZ1(bmin+cell1));
+ continue;
+ }
+ c1 = cell1;
+ maxcell = -1;
+ for (i = bmin; i <= bmax; ++i)
+ if (bucket[i])
+ {
+ c2 = c1 + bucket[i];
+ bucket[i] = c1;
+ longcode = MASH(longcode,i+c1);
+ if (c2-c1 > maxcell)
+ {
+ maxcell = c2-c1;
+ maxpos = c1;
+ }
+ if (c1 != cell1)
+ {
+ ADDELEMENT(active,c1);
+ if (c2-c1 == 1) hint = c1;
+ ++*numcells;
+ }
+ if (c2 <= cell2) ptn[c2-1] = level;
+ c1 = c2;
+ }
+ for (i = cell1; i <= cell2; ++i)
+ workperm[bucket[count[i]]++] = lab[i];
+ for (i = cell1; i <= cell2; ++i) lab[i] = workperm[i];
+ if (!ISELEMENT(active,cell1))
+ {
+ ADDELEMENT(active,cell1);
+ DELELEMENT(active,maxpos); /* check maxpos is alwas defined */
+ }
+ }
+ }
+ if (--strength == 0) break; /* negative is fine! */
+ }
+
+ longcode = MASH(longcode,FUZZ2(*numcells));
+ return CLEANUP(longcode);
+}
+
+void
+refinvar(graph *g, int *lab, int *ptn, int level, int numcells, int tvpos,
+ int *invar, int invararg, boolean digraph, int m, int n)
+{
+ int i,j;
+ int wt;
+ int icell,bigcells,cell1,cell2;
+ int *cellstart,*cellsize;
+ int newnumcells;
+
+#if !MAXN
+ DYNALLOC1(int,workshort,workshort_sz,n+2,"refinvar");
+ DYNALLOC1(int,vv,vv_sz,n,"refinvar");
+ DYNALLOC1(int,ww,ww_sz,n,"refinvar");
+ DYNALLOC1(set,ws1,ws1_sz,n,"refinvar");
+#endif
+
+ for (i = n; --i >= 0;) invar[i] = 0;
+
+ cellstart = workshort;
+ cellsize = workshort + (n/2);
+ getbigcells(ptn,level,2,&bigcells,cellstart,cellsize,n);
+
+ for (icell = 0; icell < bigcells; ++icell)
+ {
+ cell1 = cellstart[icell];
+ cell2 = cell1 + cellsize[icell] - 1;
+ for (i = cell1; i <= cell2; ++i)
+ {
+ for (j = 0; j < n; ++j)
+ {
+ vv[j] = lab[j];
+ ww[j] = ptn[j];
+ }
+ newnumcells = numcells + 1;
+ ww[cell1] = level;
+ EMPTYSET(ws1,m);
+ ADDELEMENT(ws1,cell1);
+ vv[i] = lab[cell1];
+ vv[cell1] = lab[i];
+ invar[lab[i]] = semirefine(g,vv,ww,level,&newnumcells,
+ invararg,ws1,m,n);
+ }
+ wt = invar[lab[cell1]];
+ for (i = cell1 + 1; i <= cell2; ++i)
+ if (invar[lab[i]] != wt) return;
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 13:00:27 +0000