Page MenuHomePhorge
Files F27036983

nautaux.c
No OneTemporary
Actions

Authored By
Unknown
Size
8 KB
Referenced Files
None
Subscribers
None

nautaux.c
View Options

/*****************************************************************************
* *
* Auxiliary procedures for use with nauty 2.5. *
* None of these procedures are needed by nauty or by dreadnaut. *
* *
* Copyright (1984-2013) Brendan McKay. All rights reserved. *
* Subject to waivers and disclaimers in nauty.h. *
* *
* CHANGE HISTORY *
* 26-Apr-89 : initial creation for Version 1.5. *
* 14-Oct-90 : renamed to version 1.6 (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 : renamed to version 1.9 (no changes to this file) *
* 24-Jan-00 : renamed to version 2.0 (no changes to this file) *
* 16-Nov-00 : made changes listed in nauty.h *
* 8-Aug-02 : updated for version 2.2 (dynamic storage) *
* 3-Nov-04 : fixed names of nautaux_freedyn() and nautaux_check() *
* 10-Dec-06 : removed BIGNAUTY *
* 10-Nov-09 : removed types permutation and shortish *
* 15-Jan-12 : add TLS_ATTR attributes *
* *
*****************************************************************************/
#define ONE_WORD_SETS
#include "naututil.h" /* which includes "nauty.h" and <stdio.h> */
#include "nautaux.h"
#if MAXM==1
#define M 1
#else
#define M m
#endif
#if !MAXN
DYNALLSTAT(set,workset,workset_sz);
DYNALLSTAT(int,workperm,workperm_sz);
#else
static TLS_ATTR set workset[MAXM]; /* used for scratch work */
static TLS_ATTR int workperm[MAXN+2];
#endif
/*****************************************************************************
* *
* ptncode(g,lab,ptn,level,m,n) returns a long integer invariant which *
* depends on the (assumed equitable) partition at the stated level, and *
* the number of edges betwen the various cells. *
* Neither nauty nor dreadnaut use this. *
* *
* GLOBALS ACCESSED: bit<r>,setinter() *
* *
*****************************************************************************/
long
ptncode(graph *g, int *lab, int *ptn, int level, int m, int n)
{
int i;
long code;
int v1,v2,nc,inter,cellend;
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
#endif
/* find all cells: put starts in workperm[0..n] */
i = nc = 0;
code = 0;
while (i < n)
{
workperm[nc++] = i;
code = ((code << 13) ^ (code >> 19)) + i;
while (ptn[i] > level) ++i;
++i;
}
workperm[nc] = n;
for (v2 = 0; v2 < nc; ++v2)
{
EMPTYSET(workset,m);
for (i = workperm[v2], cellend = workperm[v2+1] - 1;
i <= cellend; ++i)
ADDELEMENT(workset,lab[i]);
for (v1 = 0; v1 < nc; ++v1)
{
i = workperm[v1];
cellend = workperm[v1+1] - 1;
inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
code = ((code << 13) ^ (code >> 19)) + inter;
}
}
return code;
}
/*****************************************************************************
* *
* equitable(g,lab,ptn,level,m,n) checks that the partition at the given *
* level is equitable. Neither nauty nor dreadnaut use this. *
* *
* GLOBALS ACCESSED: bit<r>,setinter() *
* *
*****************************************************************************/
boolean
equitable(graph *g, int *lab, int *ptn, int level, int m, int n)
{
int i;
int v1,v2,nc,inter,cellend;
boolean ok;
/* find all cells: put starts in workperm[0..n] */
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
DYNALLOC1(set,workset,workset_sz,m,"testcanlab");
#endif
i = nc = 0;
while (i < n)
{
workperm[nc++] = i;
while (ptn[i] > level)
++i;
++i;
}
workperm[nc] = n;
ok = TRUE;
for (v2 = 0; v2 < nc && ok; ++v2)
{
EMPTYSET(workset,m);
for (i = workperm[v2], cellend = workperm[v2+1] - 1;
i <= cellend; ++i)
ADDELEMENT(workset,lab[i]);
for (v1 = 0; v1 < nc; ++v1)
{
i = workperm[v1];
cellend = workperm[v1+1] - 1;
if (i == cellend)
continue;
inter = setinter(workset,GRAPHROW(g,lab[i],M),M);
while (++i <= cellend)
if (setinter(workset,GRAPHROW(g,lab[i],M),M) != inter)
ok = FALSE;
}
}
return ok;
}
/*****************************************************************************
* *
* component(g,v,c,m,n) determines the set of all vertices that can be *
* reached along directed paths starting at vertex v, including v itself. *
* This set is returned as c, unless c is null. The size of the set is *
* returned as the function value. *
* *
* GLOBALS ACCESSED: bit<r>,setinter(),nextelement() *
* *
*****************************************************************************/
int
component(graph *g, int v, set *cmpt, int m, int n)
{
int i,z;
set newverts[MAXM],*gx;
int head,tail,x;
#if !MAXN
DYNALLOC1(int,workperm,workperm_sz,n+2,"testcanlab");
#endif
EMPTYSET(workset,m);
ADDELEMENT(workset,v);
head = 0;
tail = 1;
workperm[head] = v;
while (head < tail && tail < n)
{
x = workperm[head++];
gx = GRAPHROW(g,x,m);
for (i = m; --i >= 0;)
{
newverts[i] = gx[i] & ~workset[i];
workset[i] |= gx[i];
}
for (z = -1; (z = nextelement(newverts,m,z)) >= 0; )
workperm[tail++] = z;
}
if (cmpt != NULL)
for (i = m; --i >= 0;) cmpt[i] = workset[i];
return tail;
}
/*****************************************************************************
* *
* nautaux_check() checks that this file is compiled compatibly with the *
* given parameters. If not, call exit(1). *
* *
*****************************************************************************/
void
nautaux_check(int wordsize, int m, int n, int version)
{
if (wordsize != WORDSIZE)
{
fprintf(ERRFILE,"Error: WORDSIZE mismatch in nautaux.c\n");
exit(1);
}
#if MAXN
if (m > MAXM)
{
fprintf(ERRFILE,"Error: MAXM inadequate in nautaux.c\n");
exit(1);
}
if (n > MAXN)
{
fprintf(ERRFILE,"Error: MAXN inadequate in nautaux.c\n");
exit(1);
}
#endif
if (version < NAUTYREQUIRED)
{
fprintf(ERRFILE,"Error: nautaux.c version mismatch\n");
exit(1);
}
}
/*****************************************************************************
* *
* nautaux_freedyn() - free the dynamic memory in this module *
* *
*****************************************************************************/
void
nautaux_freedyn(void)
{
#if !MAXN
DYNFREE(workset,workset_sz);
DYNFREE(workperm,workperm_sz);
#endif
}

File Metadata

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

Event Timeline