Quelle traces.c-old
Sprache: unbekannt
|
|
Spracherkennung für: .c-old vermutete Sprache: Unknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]
/******************************************************************************
* *
* This is the main file for traces() version 2.2, which is included into *
* nauty() version 2.8.6. *
* *
* nauty is Copyright (1984-2018) Brendan McKay. All rights reserved. *
* Traces is Copyright Adolfo Piperno, 2008-2018. All rights reserved. *
* See the file COPYRIGHT for the details of the software license. *
* *
* CHANGE HISTORY *
* 28-Dec-12 : final changes for version 2.0 *
* 20-Jan-13 : add code for ^C catching in Traces *
* 29-Mar-13 : bug correction in automorphism mode *
* 02-Apr-13 : add preprocessing *
* 21-May-13 : bug correction (coloured lists) *
* 29-Jun-13 : bug correction (coloured lists and cycles) *
* 07-Dec-13 : bug correction in automorphism mode (wrong group size *
* due to randomness in Schreier-Sims orbit computation) *
* bug correction (discrete initial partition) *
* 15-Feb-14 : CPUDEFS removed (already declared in gtools.h) *
* 01-Sep-15 : add weighted edges (not active) *
* 28-Jan-16 : version ready for nauty and Traces v.2.6 distribution *
* 12-Jul-16 : bug correction (reaching degree 2 vertices) *
* 07-Jun-18 : bug correction (finalnumcells, thanks R.Kralovic) *
* 07-Jun-18 : bug correction (index computation when findperm) *
* 10-Nov-22 : bug correction (cycles in degree 2 subgraphs) *
*****************************************************************************/
#include "traces.h"
#ifdef NAUTY_IN_MAGMA
#include "cleanup.e"
#endif
#define SORT_OF_SORT 2
#define SORT_NAME sort2ints
#define SORT_TYPE1 int
#define SORT_TYPE2 int
#include "sorttemplates.c"
typedef struct weightwhere {
int weight;
int *ref;
} weightwhere;
#define SORT_OF_SORT 2
#define SORT_NAME sortweights
#undef SORT_TYPE2
#define SORT_TYPE1 int
#define SORT_TYPE2 weightwhere
#include "sorttemplates.c"
#define NAUTY_ABORTED (-11)
#define NAUTY_KILLED (-12)
typedef struct Candidate {
boolean sortedlab;
int *invlab;
int *lab;
int code;
int do_it;
int indnum;
int name;
int vertex;
struct Candidate *next;
struct searchtrie *stnode;
unsigned int firstsingcode;
unsigned int pathsingcode;
unsigned int singcode;
} Candidate;
typedef struct Partition {
int *cls;
int *inv;
int active;
int cells;
int code;
} Partition;
typedef struct trielist {
struct searchtrie *triearray;
struct trielist *prev;
struct trielist *next;
} trielist;
typedef struct TracesVars {
char digstring[25];
double autchk;
double expaths;
double schreier1;
double schreier2;
double schreier3;
int augmented_cells;
int build_autom;
int *currorbit;
int *orbits;
int answ;
int brkstpcount;
int compstage;
int cand_level;
int canlist;
int digits;
int expathlength;
int firstpathlength;
int fromlevel;
int group_level;
int indivend;
int indivstart;
int indiv_vtx;
int lastcell;
int lastlev;
int lev_of_lastauto;
int levelfromCS0;
int linelgth;
int mark;
int treemark;
int autmark;
int markcell1;
int markcell2;
int maxdeg;
int maxtreelevel;
int maxspineorblevel;
int mindeg;
int name;
struct searchtrie *gotonode;
struct searchtrie *newgotonode;
struct searchtrie *newst_stage1;
int newindex;
int nextlevel;
int nfix;
int finalnumcells;
int permInd;
int preprocessed;
int samepref;
int specialgens;
int stackmark;
int steps;
int strategy;
trielist *strielist;
int strienext;
int tcell_sz;
int tcell;
int tcellevel;
int tcellexpath_sz;
int tcellexpath;
int tolevel_tl;
int tolevel;
int treedepth;
int trienext;
int triepos;
TracesOptions *options;
TracesStats *stats;
unsigned int singlongcode;
sparsegraph *graph;
sparsegraph *cangraph;
sparsegraph *input_graph;
int conta0;
int conta1;
int conta2;
int conta3;
int conta4;
int conta5;
int conta6;
int conta7;
int contatc;
} TracesVars;
typedef struct TracesInfo {
boolean autofound;
boolean deg_one;
boolean first_matching;
boolean regular;
boolean exitfromref;
boolean identitygroup;
boolean minimalinorbits;
boolean thegraphisparse;
boolean thegrouphaschanged;
boolean thereisnextlevel;
boolean useTempOrbits1;
boolean useTempOrbits2;
} TracesInfo;
typedef struct TracesSpine {
boolean thetracexists;
Candidate *listend;
Candidate *liststart;
int ccend;
int ccstart;
int listcounter;
int stpend;
int stpstart;
int tgtcell;
int tgtend;
int tgtfrom;
int tgtpos;
int tgtsize;
int trcend;
int trcstart;
int singend;
int singstart;
int updates;
unsigned long keptcounter;
unsigned long levelcounter;
Partition *part;
unsigned int singcode;
} TracesSpine;
typedef struct trie {
int value;
struct trie *first_child;
struct trie *next_sibling;
} trie;
typedef struct searchtrie {
int index;
int name;
int vtx;
int level;
struct searchtrie *father;
struct searchtrie *first_child;
struct searchtrie *last_child;
struct searchtrie *next_sibling;
struct searchtrie *goes_to;
} searchtrie;
typedef struct pair {
int arg;
int val;
} pair;
typedef struct grph_strct {
int *e;
int *w;
int d;
boolean one;
} grph_strct;
typedef struct ExpPathInfo {
int code;
int cell;
int info;
} ExpPathInfo;
static boolean traces_degree_refine(sparsegraph*, Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*, int, int*);
static int traces_vertexclass_refine (int, int*, int*, Candidate*, Partition*, int*);
static int traces_refine(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*, int, boolean);
static void traces_refine_notrace(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static void traces_refine_maketrie(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static int traces_refine_comptrie(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static int traces_refine_sametrace(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static int traces_refine_refine(sparsegraph*, Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static void refine_tr_refine(Candidate*, int, Partition*,
struct TracesVars*, struct TracesInfo*);
static int given_gens(sparsegraph*, permnode*, int*, boolean);
static void quickSort(int*, int);
static struct Partition* NewPartition(int);
static struct Candidate* NewCandidate(int, Candidate**, int);
static void NewPartSpine(int, int);
static int FreeList(Candidate*, int);
static int FixBase(int*, struct TracesVars*, Candidate*, int, int);
static boolean FixedBase(int*, struct TracesVars*, Candidate*, int, int);
static void factorial(double*, int*, int);
static void factorial2(double*, int*, int);
static int CheckForAutomorphisms(Candidate*, Candidate*, struct TracesVars*, struct TracesInfo*, int, int, Partition*);
static int CheckForSingAutomorphisms(Candidate*, Partition*, Candidate*, struct TracesVars*, struct TracesInfo*, int, int);
static int CheckForMatching(Candidate*, Candidate*, Partition*, struct TracesVars*, struct TracesInfo*, int, int);
static void Individualize(Partition*, Candidate*, int, int, int, int);
static boolean TreeFyTwo(int, Candidate*, Candidate*, Partition*, int, struct TracesVars*, struct TracesInfo*);
static void ExperimentalStep(Partition*, Candidate*, struct TracesVars*, struct TracesInfo*, int, int);
static boolean TargetCell(Candidate*, Partition*, int, struct TracesVars*, int);
static boolean TargetCellFirstPath(Candidate*, Partition*, struct TracesVars*);
static int TargetCellExpPath(Candidate*, Partition*, struct TracesVars*);
static boolean TargetCellSmall(Candidate*, Partition*, int, struct TracesVars*, int);
static boolean TargetCellFirstPathSmall(Candidate*, Partition*, struct TracesVars*);
static int TargetCellExpPathSmall(Candidate*, Partition*, struct TracesVars*);
static boolean SelectNextLevel(int, struct TracesVars*, struct TracesInfo*);
static void CopyCand(Candidate*, Candidate*, int, int*, int*);
static struct trie* trie_new(int, struct TracesVars*);
static struct trie* trie_make(trie*, int, int, struct TracesVars*);
static struct trie* trie_comp(trie*, int);
static void trie_dump(trie*);
static void trie_class(trie*, int*);
static void RemoveFromLevel(int, int, int, boolean);
static int CompStage0(Partition*, Partition*, Candidate*, Candidate*, int, int, struct TracesVars*, struct TracesInfo*);
static int CompStage1(Partition*, Partition*, Candidate*, Candidate*, int, int, struct TracesVars*, struct TracesInfo*);
static int CompStage2(Partition*, Partition*, Candidate*, Candidate*, int, int, struct TracesVars*, struct TracesInfo*);
static void grouporderplus(sparsegraph*, Candidate*, Partition*, permnode**, double*, int*, int, struct TracesVars*, struct TracesInfo*);
static boolean Prefix(Candidate*, Candidate*, int);
static boolean findperm(permnode*, int*, int);
static int spinelementorbsize(int*, int*, int, int);
static trielist* searchtrie_new(int, struct TracesVars*);
static searchtrie* searchtrie_make(Candidate*, Candidate*, int, struct TracesVars*);
static boolean lookup(searchtrie*);
static int* findcurrorbits(schreier*, int);
static int Preprocess(sparsegraph*, permnode**, Candidate*, int, Partition*, struct TracesVars*);
static void MakeTree(int, int, sparsegraph*, int, struct TracesVars*, boolean);
static void MakeCanTree(int, sparsegraph*, int, Candidate*, Partition*, struct TracesVars*);
static int maxint(int, int);
static int minint(int, int);
static void orbjoin_sp_perm(int*, int*, int*, int, int*);
static void orbjoin_sp_pair(int*, int*, int, int, int, int*);
static boolean isautom_sg_pair(graph*, int*, boolean, int, int, struct TracesVars*);
static void SetAutom(int, int, struct TracesVars*);
static void ResetAutom(int, int, struct TracesVars*);
static void PrintVect(int*, int, int, int);
static void putgraphplus_sg(FILE*, sparsegraph*, int);
static boolean VerifyId(int *p, int n);
static void PrintPartition(int*, int*, int, int, int);
static void Place(int, Candidate*, Partition*);
static int NonSingDeg(int, Candidate*, Partition*);
static int NonSingDegPlus1(Candidate*, Partition*, int, TracesVars*);
static void NonSingDegPlus2(Candidate*, Partition*, int, TracesVars*);
static void Edge_Delete(int, int, Candidate*, TracesVars*);
static boolean VerifyPart(Partition*, int, int);
static int VerifyPerm(int*, int,int);
static boolean VerifyCand(Candidate*, int, int);
static int FirstNeighbour(int, Candidate*, Partition*, int*, int, int*, int);
static int NextNeighbour(int, Candidate*, Partition*, int*, int, int*, int);
static sparsegraph* copy_sg_structure(sparsegraph*, sparsegraph*);
static void WeightCodes (int);
static void PrintWeightedGraph1(sparsegraph*, int, char[30]);
static void PrintWeightedGraph2(int n, char msg[30]);
static void MakeDiscrete(Partition*, int);
static void Complete(sparsegraph*, Candidate*, Partition*, int, TracesVars*, double*, int*,permnode**, int);
static void Allocate_Traces_Structures(int);
static void Allocate_refine_Structures(int);
static void Initialize_Traces_Variables(TracesVars*, TracesOptions*, TracesStats*, int*, sparsegraph*, sparsegraph*, int);
static void Initialize_Traces_Statistics (TracesStats*, int);
static void Initialize_Traces_Time_Variables (TracesVars*);
static int trie_classify(int, TracesVars*);
static int Check_degree_one(sparsegraph*, Candidate*, Partition*, int);
static void sort_Split_Array(int*, int);
static const unsigned int fuzz1[] = {037541, 061532, 005257, 026416};
static const unsigned int fuzz2[] = {006532, 070236, 035523, 062437};
static int Select_from_CStack(int*, int);
static void PrintBlissGraph(int);
static void CodeClassify(int, int, int);
static void Adjust_Cycles(Candidate*, Partition*, int, TracesVars*);
#define FUZZ1(x) ((x) ^ fuzz1[(x)&3])
#define FUZZ2(x) ((x) ^ fuzz2[(x)&3])
#define MASHCOMM(l, i) ((l) + FUZZ1(i))
#define MASHNONCOMM(l, i) (FUZZ2(l) + (i))
#define MASH(l, i) ((((l) ^ 065435) + (i)) & 077777)
#define MASH1(l, i) ((l + (i*i)) & 077777)
#define CLEANUP(l) ((int)((l) % 0x7FFF))
#define SS(n, sing, plur) (n), ((n) == 1?(sing):(plur))
#define SETMARK(Arr, Mrk) if (Mrk > (NAUTY_INFINITY-2)) { memset(Arr, 0, n*sizeof(int)); Mrk = 0; } Mrk++;
#define COPYNODE(W, V) { \
memcpy(W->lab, V->lab, n*sizeof(int)); \
memcpy(W->invlab, V->invlab, n*sizeof(int)); \
W->code = V->code; \
W->singcode = V->singcode; \
W->do_it = V->do_it; }
#define NEXTLINE fprintf(outfile, "\n");
#define PRINTCHAR(c) fprintf(outfile, "%s", c);
#define PRINTCAND(V, Lev) PRINTCHAR(" ") for (tmp=1; tmp<=Lev; tmp++) {fprintf(outfile, tv->digstring, V->lab[Spine[tmp].tgtpos]+labelorg);}
#define PRINTCANDF(V, Lev) { NEXTLINE for (tmp=1; tmp<=Lev; tmp++) {fprintf(outfile, "F%di", V->lab[Spine[tmp].tgtpos]+labelorg);} NEXTLINE }
#define PRINTCANDBIG(V, Lev) { PRINTCHAR(" ") \
for (tmp=1; tmp<=5; tmp++) {fprintf(outfile, tv->digstring, V->lab[Spine[tmp].tgtpos]+labelorg);} \
fprintf(outfile, "... "); \
for (tmp=Lev-4; tmp<=Lev; tmp++) {fprintf(outfile, tv->digstring, V->lab[Spine[tmp].tgtpos]+labelorg);} }
#define LINE(K, c) { PRINTCHAR(c) for (tmp=1; tmp<=K; tmp++) {fprintf(outfile, c);} }
#define TRACE_CHECK(Tr, Ind, Arg, End) { TracePos = Tr+Ind; \
if (newtrace) { \
*TracePos = Arg; \
} \
else { \
if (Ind < *End) { \
if (*TracePos != Arg) { \
if (*TracePos > Arg) { \
return FALSE; \
} \
else { \
*TracePos = Arg; \
newtrace = TRUE; \
} \
} \
} \
else { \
*TracePos = Arg; \
newtrace = TRUE; \
} \
} \
Ind++; }
#define SAMETRACE_CHECK(Tr, Ind, Arg, End) { TracePos = Tr+Ind; \
if (Ind < *End) { \
if (*TracePos != Arg) { \
return FALSE; \
} \
} \
else { \
return FALSE; \
} \
Ind++; }
#define NEWPARTSPINE(Lev) { if (Lev > 3) { \
Spine[Lev].part = malloc(sizeof(*(Spine[Lev].part))); \
if (Spine[Lev].part == NULL) { \
fprintf(ERRFILE, "\nError, memory not allocated.\n"); \
exit(1); \
} \
Spine[Lev].part->cls = Spine[Lev-3].part->cls; \
Spine[Lev].part->inv = Spine[Lev-3].part->inv; \
Spine[Lev-3].part->cls = Spine[Lev-3].part->inv = NULL; \
Spine[Lev].part->code = -1; \
Spine[Lev].part->cells = 0; \
} \
else { \
Spine[Lev].part = NewPartition(n); \
} }
#define FIND_SPLIT_CELLS SplInd = 0; \
for (j = 0; j < HitClsInd; j++) { \
ind1 = HitCls[j]; \
ElmHitCll[ind1] -= ind1; \
if ((ElmHitCll[ind1] > 0) && (ElmHitCll[ind1] < cls[ind1])) { \
SplCls[SplInd++] = ind1; \
} \
}
#define FREEPART(Part) { if (Part) { \
if (Part->cls) free(Part->cls); \
if (Part->inv) free(Part->inv); \
free(Part); } \
}
#define FREECAND(Cand) { if (Cand) { \
if (Cand->lab) free(Cand->lab); \
if (Cand->invlab) free(Cand->invlab); \
free(Cand); \
} }
#define COPYPART(P, Q) { memcpy(P->cls, Q->cls, n*sizeof(int)); \
memcpy(P->inv, Q->inv, n*sizeof(int)); \
P->cells = Q->cells; \
P->code = Q->code; } \
#define ADDTONEXTLEVEL { if (SpineTL->listend) { \
(SpineTL->listend)->next = NewCandidate(n, &GarbList, TRUE); \
if ((tv->compstage < 2) && (SpineTL->listcounter <= (NAUTY_INFINITY-2))) SpineTL->listcounter++; \
SpineTL->listend = (SpineTL->listend)->next; \
CopyCand(SpineTL->listend, NextCand, n, NULL, NULL); \
} \
else { \
SpineTL->liststart = NewCandidate(n, &GarbList, TRUE); \
if (tv->compstage < 2) SpineTL->listcounter = 1; \
SpineTL->listend = SpineTL->liststart; \
CopyCand(SpineTL->liststart, NextCand, n, NULL, NULL); \
} }
#define ORBITSIZES { memset(OrbSize, 0, n*sizeof(int)); \
for (i=0; i<n; i++) { \
OrbSize[tv->orbits[i]]++; \
} }
#define CURRORBITSIZES { memset(CurrOrbSize, 0, n*sizeof(int)); \
for (i=SpineTL->tgtcell; i<SpineTL->tgtend; i++) { \
CurrOrbSize[tv->currorbit[CurrCand->lab[i]]]++; \
} }
#define EXITFROMSTAGE0REFINE { PRINT_LINE_PLUS(tv->tolevel) \
if (tv->options->verbosity >= 2) fprintf(outfile, "-=="); \
CurrCand->indnum--; \
RemoveFromLevel(tv->tolevel, tv->treedepth, tv->strategy, FALSE); \
tv->compstage = 1; \
TempOrbits = NULL; \
trieroot = trie_new(n, tv); \
trieref = trieroot; \
tv->nextlevel = tv->maxtreelevel = tv->fromlevel; \
ti->thereisnextlevel = TRUE; \
ti->exitfromref = TRUE; \
return 0; }
#define EXITFROMSTAGE0EXPATH2 { PRINT_LINE_PLUS(tv->tolevel) \
if (tv->options->verbosity >= 2) fprintf(outfile, "=-="); \
tv->compstage = 1; \
TempOrbits = NULL; \
trieroot = trie_new(n, tv); \
trieref = trieroot; \
tv->nextlevel = tv->maxtreelevel = tv->tolevel; \
ti->thereisnextlevel = TRUE; \
ti->exitfromref = FALSE; \
return 0; }
#define EXITFROMSTAGE0EXPATH1 { PRINT_RETURN PRINT_LINE_PLUS(tv->tolevel) \
if (tv->options->verbosity >= 2) fprintf(outfile, "==-"); \
if (SpineTL->liststart) { \
AuxCand = SpineTL->liststart; \
SpineTL->liststart = NewCandidate(n, &GarbList, TRUE); \
CopyCand(SpineTL->liststart, NextCand, n, NULL, NULL); \
SpineTL->liststart->next = AuxCand; \
} \
else { \
SpineTL->liststart = NewCandidate(n, &GarbList, TRUE); \
SpineTL->listend = SpineTL->liststart; \
SpineTL->liststart->next = NULL; \
CopyCand(SpineTL->liststart, NextCand, n, NULL, NULL); \
} \
tv->compstage = 1; \
TempOrbits = NULL; \
trieroot = trie_new(n, tv); \
trieref = trieroot; \
tv->nextlevel = tv->maxtreelevel = tv->tolevel; \
ti->thereisnextlevel = TRUE; \
ti->exitfromref = FALSE; \
return 0; }
#define UPDATE_LINELGTH { if (tv->options->verbosity >= 2) { \
if (tv->tolevel < 12) { \
tv->linelgth = (tv->digits+1)*tv->tolevel+16; \
} \
else { \
tv->linelgth = (tv->digits+1)*10+20; \
} \
} }
#define PRINT_LINE { if ((tv->options->verbosity >= 1) && (tv->strategy == 0)) { \
if (tv->options->verbosity >= 2) { LINE(tv->linelgth, "-"); \
NEXTLINE} \
} \
}
#define PRINT_LINE_PLUS(Lev) { if ((tv->options->verbosity >= 1) && (tv->strategy == 0)) { \
if (tv->options->verbosity >= 2) { LINE(16+tv->digits+1, "-");} \
fprintf(outfile, " Level %d: %d cell%s; %d singleton%s; target cell: %d; %d orbit%s; %lu node%s (%lu kept); %d update%s;", \
Lev, SS(Spine[Lev].part->cells, "", "s"), SS((Spine[Lev].part->cells == n) ? n : Spine[Lev].singend, "", "s"), Spine[Lev].tgtsize, SS(tv->stats->numorbits, "", "s"), \
SS(Spine[Lev].levelcounter, "", "s"), Spine[Lev].keptcounter, SS(Spine[Lev].updates, "", "s")); \
if (Lev <= tv->group_level) fprintf(outfile, " group_level: %d", tv->group_level); \
NEXTLINE \
} \
}
#define PRINT_CANDIDATE(Cand, Lev) { \
for (tmp = Cand->name, cu = 0; tmp > 0; tmp /= 10, ++cu) {} \
for (tmp = Lev, cu1 = 0; tmp > 0; tmp /= 10, ++cu1) {} \
cu = 14-cu-cu1; \
LINE(cu, "-") \
fprintf(outfile, " %d, %d) ", Lev % 10000, Cand->name % 10000000); \
if (Lev < 12) { \
PRINTCAND(Cand, Lev) \
} \
else { \
PRINTCANDBIG(Cand, Lev) \
} \
PRINTCHAR("| ") \
fprintf(outfile, "{%x, %x} ", Cand->code, Cand->singcode); \
}
#define PRINT_CANDIDATEPLUS(PrevCand, Cand, Lev) { \
for (tmp = Cand->name, cu = 0; tmp > 0; tmp /= 10, ++cu) {} \
for (tmp = Lev, cu1 = 0; tmp > 0; tmp /= 10, ++cu1) {} \
cu = 14-cu-cu1; \
LINE(cu, "-") \
fprintf(outfile, " %d, %d, %d) ", Lev % 10000, Cand->name % 10000000, PrevCand->name); \
if (Lev < 12) { \
PRINTCAND(Cand, Lev) \
} \
else { \
PRINTCANDBIG(Cand, Lev) \
} \
PRINTCHAR("| ") \
fprintf(outfile, "{%x, %x} ", Cand->code, Cand->singcode); \
}
#define PRINT_EXPPATHSTEP(Cand, Boo) { \
if (tv->options->verbosity >= 2) { \
if ((tv->tolevel_tl-tv->tolevel < 6) || !has_nexttcell) { \
fprintf(outfile, "%d ", tv->indiv_vtx+labelorg); \
if (Boo) { \
if (tv->options->verbosity >= 2) fprintf(outfile, "{%d:%x} ", tv->tcellexpath, Cand->code); \
} \
else fprintf(outfile, "{interr.(%d)} ", NextPart->cells); \
if ((!has_nexttcell) && (tv->compstage == 0)) { \
fprintf(outfile, "(%d) ", tv->tolevel_tl); \
} \
} \
else { \
if (tv->tolevel_tl-tv->tolevel == 6) { \
fprintf(outfile, "... "); \
} \
} \
} \
}
#define PRINT_RETURN { if (tv->options->verbosity >= 2) { \
fprintf(outfile, "\n"); \
} }
#define PRINT_FROM_VERB(Verb,Lev) { if (tv->options->verbosity >= Verb) { \
fprintf(outfile, "FROM: "); \
if (Lev < 12) { \
PRINTCAND(CurrCand, tv->fromlevel) \
} \
else { \
PRINTCANDBIG(CurrCand, tv->fromlevel) \
} \
fprintf(outfile, " do_it: %d, indnum: %d, stnode->index: %d tcell @ %d: %d", CurrCand->do_it, CurrCand->indnum, CurrCand->stnode->index,tv->tcellevel,Spine[tv->tcellevel].tgtcell); \
PRINT_RETURN \
} }
#define PRINT_NOTMIN_VERB(Verb) { if (tv->options->verbosity >= Verb) { \
fprintf(outfile, " is NOT minimal in orbits (1, %d) [%d]; ", gom_level, CurrCand->lab[Spine[gom_level+1].tgtpos]+labelorg); \
fprintf(outfile, "at lev %d, orb[%d] = %d.\n", gom_level+1, CurrCand->lab[Spine[gom_level+1].tgtpos]+labelorg, tv->currorbit[CurrCand->lab[Spine[gom_level+1].tgtpos]]+labelorg); } }
#define PRINT_SKIPPED_VERB(Verb) { if (tv->options->verbosity >= Verb) \
fprintf(outfile, " skipped (0) (orbit[%d] = %d)\n", \
NextCand->vertex+labelorg, tv->currorbit[NextCand->vertex]+labelorg); }
#define PRINT_REFINE_VERB(Verb,where) { if (tv->options->verbosity >= Verb) \
fprintf(outfile, " REFINE(%c) (orbit[%d] = %d)\n",where, NextCand->vertex+labelorg, tv->currorbit[NextCand->vertex]+labelorg); }
#define PRINT_INDIV_VERB(Verb,Lev) { if (tv->options->verbosity >= Verb) { \
if (Lev < 12) { \
PRINTCAND(CurrCand, tv->fromlevel) \
} \
else { \
PRINTCANDBIG(CurrCand, tv->fromlevel) \
} \
fprintf(outfile, "| "); \
fprintf(outfile, tv->digstring, NextCand->vertex+labelorg); \
} }
#define PRINT_INDEX(V,Verb,where) if (tv->options->verbosity >= Verb) \
fprintf(outfile,"Set index @ %d: Name %d, index %d\n",where,V->name,V->index);
#define SPECIALGENERATORS { if (tv->options->generators) addpermutation(ring, AUTPERM, n); \
tv->stats->numgenerators++; \
tv->specialgens++; \
if (tv->options->writeautoms) { \
fprintf(outfile, "Gen #%d: ", tv->stats->numgenerators); \
writeperm(outfile, AUTPERM, tv->options->cartesian, tv->options->linelength, n); \
} \
if (tv->options->userautomproc) { \
(*tv->options->userautomproc)(tv->stats->numgenerators, AUTPERM, n); \
} }
#define UPDATEMIN(A, B) if (B < A) A = B;
#define PAIRORBJOIN(A, V) { if (A != V) { \
PrmPairs[tv->permInd].arg = A; \
PrmPairs[tv->permInd].val = V; \
tv->permInd++; \
orbjoin_sp_pair(tv->orbits, OrbList, n, A, V, &tv->stats->numorbits); \
MakeTree(A, V, sg, n, tv, FALSE); \
} }
#define SETPAIRS(A, V) { if (A != V) { \
PrmPairs[tv->permInd].arg = A; \
PrmPairs[tv->permInd].val = V; \
tv->permInd++; \
} }
#define SETPAIRSAUT(A, V) { if ((A != V) && (AUTPERM[A] != V)) { \
AUTPERM[A] = V; \
PrmPairs[tv->permInd].arg = A; \
PrmPairs[tv->permInd].val = V; \
tv->permInd++; \
} }
#define SETPAIRSAUTANDTREE(arg, val) { if (tv->build_autom) { SETPAIRSAUT(arg, val) } \
if (arg != val) orbjoin_sp_pair(tv->orbits, OrbList, n, arg, val, &tv->stats->numorbits); \
MakeTree(arg, val, sg_orig, n, tv, FALSE); }
#define PRINTF2(A, B) if (tv->options->verbosity > 3) printf(A, B)
#define PRINTF2_2(A, B, C) if (tv->options->verbosity > 3) printf(A, B, C)
#define PRINTF2_3(A, B, C, D) if (tv->options->verbosity > 3) printf(A, B, C, D)
#define PRINTF2_4(A, B, C, D, E) if (tv->options->verbosity > 3) printf(A, B, C, D, E)
#define VERB_PRINT(V,Verb,R) if (tv->options->verbosity >= Verb) { \
fprintf(outfile,"\033[0;32m%s\033[0m ",V); \
if (R) fprintf(outfile,"\n"); }
/* data decls. for CPUTIME */
#ifdef CPUDEFS
CPUDEFS
#endif
#if !MAXN
DYNALLSTAT(int, AUTPERM, AUTPERM_sz);
DYNALLSTAT(int, BreakSteps, BreakSteps_sz);
DYNALLSTAT(int, CStack, CStack_sz);
DYNALLSTAT(int, CurrOrbSize, CurrOrbSize_sz);
DYNALLSTAT(int, CurrRefCells, CurrRefCells_sz);
DYNALLSTAT(boolean, Diff, Diff_sz);
DYNALLSTAT(boolean, Factorials, Factorials_sz);
DYNALLSTAT(int, fix, fix_sz);
DYNALLSTAT(int, IDENTITY_PERM, IDENTITY_PERM_sz);
DYNALLSTAT(int, Markers, Markers_sz);
DYNALLSTAT(int, TreeMarkers, TreeMarkers_sz);
DYNALLSTAT(int, AutMarkers, AutMarkers_sz);
DYNALLSTAT(int, MarkHitVtx, MarkHitVtx_sz);
DYNALLSTAT(int, MultRefCells, MultRefCells_sz);
DYNALLSTAT(int, NghCounts, NghCounts_sz);
DYNALLSTAT(int, OrbSize, OrbSize_sz);
DYNALLSTAT(int, OrbList, OrbList_sz);
DYNALLSTAT(pair, PrmPairs, PrmPairs_sz);
DYNALLSTAT(int, TempOrbList, TempOrbList_sz);
DYNALLSTAT(int, RefCells, RefCells_sz);
DYNALLSTAT(searchtrie*, RefPath, RefPath_sz);
DYNALLSTAT(int, Singletons, Singletons_sz);
DYNALLSTAT(int, SplCls, SplCls_sz);
DYNALLSTAT(int, SplCnt, SplCnt_sz);
DYNALLSTAT(int, SplPos, SplPos_sz);
DYNALLSTAT(int, StackMarkers, StackMarkers_sz);
DYNALLSTAT(int, TheTrace, TheTrace_sz);
DYNALLSTAT(int, TheTraceCC, TheTraceCC_sz);
DYNALLSTAT(int, TheTraceSplNum, TheTraceSplNum_sz);
DYNALLSTAT(int, TheTraceSteps, TheTraceSteps_sz);
DYNALLSTAT(int, TEMPLAB, TEMPLAB_sz);
DYNALLSTAT(int, TEMPINVLAB, TEMPINVLAB_sz);
DYNALLSTAT(int, WeightsSeq, WeightsSeq_sz);
DYNALLSTAT(int, WorkArray, WorkArray_sz);
DYNALLSTAT(int, WorkArray0, WorkArray0_sz);
DYNALLSTAT(int, WorkArray1, WorkArray1_sz);
DYNALLSTAT(int, WorkArray2, WorkArray2_sz);
DYNALLSTAT(int, WorkArray3, WorkArray3_sz);
DYNALLSTAT(int, WorkArray4, WorkArray4_sz);
DYNALLSTAT(int, WorkArray5, WorkArray5_sz);
DYNALLSTAT(int, WorkArray6, WorkArray6_sz);
DYNALLSTAT(int, WorkArray7, WorkArray7_sz);
DYNALLSTAT(int, Neighbs1, Neighbs1_sz);
DYNALLSTAT(int, Neighbs2, Neighbs2_sz);
DYNALLSTAT(int, TreeStack, TreeStack_sz);
DYNALLSTAT(TracesSpine, Spine, Spine_sz);
DYNALLSTAT(trie*, TrieArray, TrieArray_sz);
DYNALLSTAT(grph_strct, TheGraph, TheGraph_sz);
DYNALLSTAT(ExpPathInfo, EPCodes, EPCodes_sz);
DYNALLSTAT(int, CyclesPart, CyclesPart_sz);
DYNALLSTAT(int, CyclesLength, CyclesLength_sz);
#else
static TLS_ATTR int CStack[MAXN];
static TLS_ATTR int AUTPERM[MAXN];
static TLS_ATTR int BreakSteps[MAXN];
static TLS_ATTR int CurrOrbSize[MAXN];
static TLS_ATTR int CurrRefCells[MAXN];
static TLS_ATTR boolean Diff[MAXN];
static TLS_ATTR boolean Factorials[MAXN];
static TLS_ATTR int fix[MAXN];
static TLS_ATTR int IDENTITY_PERM[MAXN];
static TLS_ATTR int Markers[MAXN];
static TLS_ATTR int TreeMarkers[MAXN];
static TLS_ATTR int AutMarkers[MAXN];
static TLS_ATTR int MarkHitVtx[MAXN];
static TLS_ATTR int MultRefCells[MAXN];
static TLS_ATTR int NghCounts[MAXN];
static TLS_ATTR int OrbSize[MAXN];
static TLS_ATTR int OrbList[MAXN];
static TLS_ATTR pair PrmPairs[MAXN];
static TLS_ATTR int TempOrbList[MAXN];
static TLS_ATTR int RefCells[MAXN];
static TLS_ATTR searchtrie* RefPath[MAXN];
static TLS_ATTR int Singletons[MAXN];
static TLS_ATTR int SplCls[MAXN];
static TLS_ATTR int SplCnt[MAXN];
static TLS_ATTR int SplPos[MAXN];
static TLS_ATTR int StackMarkers[MAXN];
static TLS_ATTR int TheTrace[MAXN];
static TLS_ATTR int TheTraceCC[MAXN];
static TLS_ATTR int TheTraceSplNum[MAXN];
static TLS_ATTR int TheTraceSteps[MAXN];
static TLS_ATTR int TEMPLAB[MAXN];
static TLS_ATTR int TEMPINVLAB[MAXN];
static TLS_ATTR int WeightsSeq[MAXN];
static TLS_ATTR int WorkArray[MAXN];
static TLS_ATTR int WorkArray0[MAXN];
static TLS_ATTR int WorkArray1[MAXN];
static TLS_ATTR int WorkArray2[MAXN];
static TLS_ATTR int WorkArray3[MAXN];
static TLS_ATTR int WorkArray4[MAXN];
static TLS_ATTR int WorkArray5[MAXN];
static TLS_ATTR int WorkArray6[MAXN];
static TLS_ATTR int WorkArray7[MAXN];
static TLS_ATTR int TreeStack[MAXN];
static TLS_ATTR TracesSpine Spine[MAXN];
static TLS_ATTR trie* TrieArray[MAXN];
static TLS_ATTR grph_strct TheGraph[MAXN];
static TLS_ATTR int Neighbs1[MAXN];
static TLS_ATTR int Neighbs2[MAXN];
static TLS_ATTR ExpPathInfo EPCodes[MAXN];
static TLS_ATTR int CyclesPart[MAXN];
static TLS_ATTR int CyclesLength[MAXN];
#endif
#define PERMSTACK WorkArray1
#define CYCLES WorkArray1
#define HitCls WorkArray2
#define CYCOLR WorkArray2
#define HitVtx WorkArray3
#define CYLGTH WorkArray3
#define CYMULT WorkArray4
#define HitCount WorkArray5
#define ElmHitCll WorkArray5
#define CYCPOS WorkArray5
#define CYCHIT TempOrbList
#define LGHATTR RefCells
#define CYCREP MultRefCells
#define TempOrbSize TEMPLAB
#define AutomCount TEMPINVLAB
#define CanonIndices MarkHitVtx
#define NSFCells NghCounts
#define TreeNodes AutMarkers
#define CellMarkers1 WorkArray6
#define CellMarkers2 WorkArray7
#define SingNonSing Singletons
static TLS_ATTR FILE *outfile;
/* Brendan's SCHREIER */
static TLS_ATTR schreier *gpB; /* This will point to the Schreier structure */
static TLS_ATTR permnode *gensB; /* This will point to the stored generators */
static TLS_ATTR Candidate *GarbList, *SpOrd, *SpCyc, *SpSwp;
static TLS_ATTR Partition *SpPart1, *SpPart2;
static TLS_ATTR TracesSpine *SpineTL, *SpineFL, *SpineTL_tl;
static TLS_ATTR trie *trieroot, *trieref;
static TLS_ATTR int *TempOrbits = NULL;
static TLS_ATTR sparsegraph redgraph;
void
Traces(sparsegraph *g_arg, int *lab, int *ptn,
int *orbits_arg, TracesOptions *options_arg, TracesStats *stats_arg,
sparsegraph *canong_arg) {
int i, j;
int tmp;
int deg, vtx1, vtx2, *ngh1, *ngh2, *wgh1, *wgh2, ord;
size_t j1;
trielist *STStart, *STAux;
searchtrie *TrieNode;
int retval;
Partition *CurrPart, *NextPart;
Candidate *CurrCand, *NextCand, *BestCand, *AuxCand;
const int n = g_arg->nv;
const int m = SETWORDSNEEDED(n);
if (g_arg->nv > (NAUTY_INFINITY-2))
{
fprintf(ERRFILE, "Traces: need n <= %d, but n=%d\n\n",
NAUTY_INFINITY-2, g_arg->nv);
return;
}
Allocate_Traces_Structures(n);
struct TracesVars *tv = malloc(sizeof(struct TracesVars));
if (tv == NULL) {
fprintf(ERRFILE, "\nError, memory not allocated.\n");
exit(1);
}
struct TracesInfo *ti = malloc(sizeof(struct TracesInfo));
if (ti == NULL) {
fprintf(ERRFILE, "\nError, memory not allocated.\n");
exit(1);
}
trieroot = NULL;
NextCand = GarbList = NULL;
DYNFREE(g_arg->w,g_arg->wlen); /* to be removed in presence of weightd edges */
Initialize_Traces_Variables(tv, options_arg, stats_arg, orbits_arg, g_arg, canong_arg, n);
outfile = (tv->options->outfile == NULL ? stdout : tv->options->outfile);
SpOrd = SpCyc = SpSwp = NULL;
SpPart1 = SpPart2 = NULL;
if (tv->options->verbosity >= 2) {
for (i = n, tv->digits = 0; i > 0; i /= 10, ++tv->digits) {}
snprintf(tv->digstring, 25, "%s%dd ", "%", tv->digits);
}
/* Initialize group and statistics */
Initialize_Traces_Statistics(stats_arg,n);
if (tv->options->verbosity >= 2) {
Initialize_Traces_Time_Variables(tv);
}
/* Initialize lab and ptn when in the unit partition case */
if (tv->options->defaultptn) {
for (i = 0; i < n; i++) {
IDENTITY_PERM[i] = i;
ptn[i] = NAUTY_INFINITY;
}
ptn[n-1] = 0;
memcpy(lab, IDENTITY_PERM, n*sizeof(int));
} else {
for (i = 0; i < n; i++) {
IDENTITY_PERM[i] = i;
}
}
memcpy(orbits_arg, IDENTITY_PERM, n*sizeof(int));
if (tv->options->generators) {
tv->stats->numorbits = given_gens(g_arg, *tv->options->generators,
orbits_arg, tv->options->digraph);
newgroup(&gpB, NULL, n);
gensB = *tv->options->generators;
expandschreier(gpB, &gensB, n);
ti->thegrouphaschanged = TRUE;
ti->identitygroup = FALSE;
memcpy(OrbList, gpB->orbits, n*sizeof(int));
}
else {
newgroup(&gpB, &gensB, n);
memcpy(OrbList, IDENTITY_PERM, n*sizeof(int));
tv->stats->numorbits = n;
ti->thegrouphaschanged = FALSE;
ti->identitygroup = TRUE;
}
copy_sg_structure(&redgraph, g_arg);
tv->graph = &redgraph;
if (g_arg->w) memcpy(tv->graph->w, g_arg->w, tv->graph->wlen*sizeof(int));
if (g_arg->e) memcpy(tv->graph->e, g_arg->e, tv->graph->elen*sizeof(int));
for (i=0; i<n; i++) {
EPCodes[i].info = 0;
TheGraph[i].d = g_arg->d[i];
if (TheGraph[i].d > tv->maxdeg) {
tv->maxdeg = TheGraph[i].d;
}
if (TheGraph[i].d < tv->mindeg) {
tv->mindeg = TheGraph[i].d;
}
if (g_arg->e) {
TheGraph[i].e = tv->graph->e + g_arg->v[i];
}
else {
TheGraph[i].e = NULL;
}
if (g_arg->w) {
TheGraph[i].w = tv->graph->w + g_arg->v[i];
}
else {
TheGraph[i].w = NULL;
}
TheGraph[i].one = FALSE;
}
ord = 0;
/*----------- WEIGHTS --------------*/
if (tv->options->weighted) {
WeightCodes(n);
ord = trie_classify(n,tv);
}
/*----------------------------------*/
if ((tv->maxdeg == tv->mindeg) && (ord == 0)) ti->regular = TRUE; else ti->regular = FALSE;
tv->currorbit = gpB->orbits;
memcpy(AUTPERM, IDENTITY_PERM, n*sizeof(int));
tv->permInd = 0;
memset(fix, 0, n*sizeof(int));
memset(TheTraceCC, 0, n*sizeof(int));
memset(Factorials, 0, n*sizeof(int));
/* ran_init(1234); any long int as an argument */
/* The graph is sparse? */
if (g_arg->nde < n || g_arg->nde / n < n / (g_arg->nde / n)) {
ti->thegraphisparse = TRUE;
}
else {
ti->thegraphisparse = FALSE;
}
tv->preprocessed = 0;
ti->deg_one = FALSE;
ti->first_matching = FALSE;
retval = 0;
/* Initialize candidate, partition, cells, orbits */
Spine[0].part = NewPartition(n);
CurrPart = Spine[0].part;
memset(CurrPart->inv, 0, n*sizeof(int));
NextPart = NewPartition(n);
CurrCand = NewCandidate(n, &GarbList, TRUE);
CurrCand->singcode = 0;
TempOrbits = NULL;
STStart = NULL;
if (ti->regular) {
if (tv->options->defaultptn) {
memcpy(CurrCand->lab, IDENTITY_PERM, n*sizeof(int));
memcpy(CurrCand->invlab, IDENTITY_PERM, n*sizeof(int));
CurrPart->cells = 1;
CurrPart->cls[0] = n;
TheTrace[0] = 0;
}
else {
memcpy(CurrCand->lab, lab, n*sizeof(int));
CurrPart->cells = 0;
j = 0;
for (i = 0; i < n; i++) {
if (j) CurrPart->inv[i] = j;
CurrCand->invlab[CurrCand->lab[i]] = i;
if (!ptn[i]) {
CurrPart->cls[j] = i-j+1;
if (CurrPart->cls[j] == 1) {
CurrCand->singcode = MASHCOMM(CurrCand->singcode, CurrCand->lab[j]);
}
TheTrace[CurrPart->cells++] = j;
j = i+1;
}
}
}
} else {
if (tv->options->weighted) {
CurrPart->cells = traces_vertexclass_refine(n, lab, ptn,
CurrCand, CurrPart, WeightsSeq);
}
else {
CurrPart->cells = traces_vertexclass_refine (n, lab, ptn,
CurrCand, CurrPart, g_arg->d);
}
}
memset(NghCounts,0,n*sizeof(int));
if (tv->options->verbosity == 7) PrintPartition(CurrCand->lab,CurrPart->cls,n,labelorg,1323);
/* Check for deg 1 vertices */
ti->deg_one = Check_degree_one(g_arg, CurrCand, CurrPart, n);
#if !MAXN
DYNALLOC1(int, Neighbs1, Neighbs1_sz, tv->maxdeg, "Traces");
DYNALLOC1(int, Neighbs2, Neighbs2_sz, tv->maxdeg, "Traces");
#endif
if (ti->deg_one) {
tv->preprocessed = Preprocess(g_arg, &gensB, CurrCand, n, CurrPart, tv);
}
if (tv->preprocessed) {
memset(Diff,0,n*sizeof(boolean));
for (i=0; i<n; i++) {
if ((TheGraph[i].d > 1) && (tv->input_graph->d[i] != TheGraph[i].d))
Diff[i] = TRUE;
}
}
/* Initialization of Spine structure */
SpineFL = Spine;
SpineFL->tgtcell = SpineFL->tgtpos = 0;
SpineFL->tgtend = n;
SpineFL->tgtfrom = -1;
SpineFL->trcstart = 0;
SpineFL->trcend = CurrPart->active = CurrPart->cells;
SpineFL->ccstart = SpineFL->ccend = 0;
SpineFL->stpstart = SpineFL->stpend = 0;
SpineFL->singstart = SpineFL->singend = 0;
SpineFL->thetracexists = FALSE;
SpineFL->liststart = SpineFL->listend = CurrCand;
SpineFL->levelcounter = 1;
SpineFL->keptcounter = 1;
SpineFL->updates = 1;
/* Further initializations */
tv->maxtreelevel = 0;
tv->tolevel = 0;
tv->tcell = 0;
UPDATE_LINELGTH
/* First refinement */
if (tv->preprocessed < 2)
traces_refine(CurrCand, n, CurrPart, tv, ti, 0, FALSE);
CurrCand->name = 0;
if (CurrPart->cells == n) {
tv->stats->canupdates++;
/* CANONICAL FORM ? */
if (tv->options->getcanon) {
memcpy(lab, CurrCand->lab, n*sizeof(int));
if (canong_arg) memcpy(CurrPart->inv, CurrCand->invlab, n*sizeof(int));
if (tv->options->usercanonproc != NULL)
{
(*tv->options->usercanonproc)((graph*)g_arg, lab, (graph*)canong_arg, tv->stats->canupdates, CurrCand->code, m, n);
}
}
}
else {
STStart = searchtrie_new(n, tv);
CurrCand->stnode = tv->strielist->triearray;
NextCand = NewCandidate(n, &GarbList, TRUE);
SpineFL->listcounter = 1;
tv->tcellevel = 0;
ti->exitfromref = FALSE;
Spine[1].levelcounter = 0;
Spine[1].updates = 0;
Spine[1].tgtfrom = 0;
memset(WorkArray, 0, n*sizeof(int));
do {
tv->fromlevel = tv->tolevel;
SpineFL = Spine+tv->fromlevel;
if (CurrCand) {
switch (tv->compstage) {
case 0: retval = CompStage0(CurrPart, NextPart, CurrCand, NextCand, m, n, tv, ti);
break;
case 1:
if (!TempOrbits) {
memcpy(WorkArray1, tv->currorbit, n*sizeof(int));
TempOrbits = WorkArray1;
}
memset(TempOrbSize, 0, n*sizeof(int));
for (i=SpineTL->tgtcell; i<SpineTL->tgtend; i++) {
TempOrbSize[TempOrbits[CurrCand->lab[i]]]++;
}
retval = CompStage1(CurrPart, NextPart, CurrCand, NextCand, m, n, tv, ti);
break;
case 2:
retval = CompStage2(CurrPart, NextPart, CurrCand, NextCand, m, n, tv, ti);
break;
default:
break;
}
if (retval == NAUTY_ABORTED)
tv->stats->errstatus = NAUABORTED;
else if (retval == NAUTY_KILLED) {
tv->stats->errstatus = NAUKILLED;
return;
}
}
/* NEXT CANDIDATE */
if (ti->thereisnextlevel) {
if (tv->nextlevel != tv->fromlevel) {
UPDATE_LINELGTH
}
tv->tolevel = tv->nextlevel;
CurrCand = Spine[tv->nextlevel].liststart;
CurrPart = Spine[tv->nextlevel].part;
}
}
while (ti->thereisnextlevel);
if (!retval) {
if (tv->compstage) {
memset(CurrOrbSize, 0, n*sizeof(int));
for (i=0; i<n; i++) {
CurrOrbSize[TempOrbits[i]]++;
}
}
if (!tv->options->getcanon) {
if (tv->compstage) {
tv->maxtreelevel++;
TrieNode = Spine[tv->maxtreelevel].liststart->stnode;
if (TrieNode->father) {
TrieNode = TrieNode->father;
}
if (!ti->exitfromref) {
TrieNode->index = 0;
for (i=1; i<AutomCount[0]; i++) {
TrieNode->index += CurrOrbSize[AutomCount[i]];
PRINT_INDEX(TrieNode,4,30)
}
}
}
}
if (tv->maxtreelevel) PRINT_LINE_PLUS(tv->maxtreelevel);
AuxCand = Spine[tv->maxtreelevel].liststart;
while (!AuxCand->do_it) {
AuxCand = AuxCand->next;
}
/* CANONICAL FORM ? */
if (tv->options->getcanon) {
BestCand = AuxCand;
AuxCand = AuxCand->next;
while (AuxCand) {
if (AuxCand->do_it) {
if (comparelab_tr(g_arg, BestCand->lab, BestCand->invlab, AuxCand->lab, AuxCand->invlab, Spine[tv->maxtreelevel].part->cls, Spine[tv->maxtreelevel].part->inv) == 1) {
BestCand = AuxCand;
tv->stats->canupdates++;
if (tv->options->usercanonproc != NULL)
{
(*tv->options->usercanonproc)((graph*)g_arg, lab, (graph*)canong_arg, tv->stats->canupdates, CurrCand->code, m, n);
}
}
}
AuxCand = AuxCand->next;
}
grouporderplus(g_arg, BestCand, Spine[tv->maxtreelevel].part, &gensB, &(tv->stats->grpsize1), &(tv->stats->grpsize2), n, tv, ti);
if (tv->options->verbosity >= 2) {
LINE(32, "-")
NEXTLINE
fprintf(outfile, "Canonical:");
PRINTCAND(BestCand, tv->maxtreelevel)
PRINT_RETURN
}
memcpy(lab, BestCand->lab, n*sizeof(int));
if (canong_arg) memcpy(CurrPart->inv, BestCand->invlab, n*sizeof(int));
}
else {
grouporderplus(g_arg, AuxCand, Spine[tv->maxtreelevel].part, &gensB, &(tv->stats->grpsize1), &(tv->stats->grpsize2), n, tv, ti);
}
if (tv->options->verbosity >= 2) {
if (tv->linelgth < 40) {
tv->linelgth = 40;
}
LINE(32, "-")
NEXTLINE
}
}
}
tv->stats->treedepth = tv->treedepth;
if (Spine[tv->treedepth].part->code == -1) {
tv->stats->treedepth--;
}
if (tv->options->verbosity >= 2) {
fprintf(outfile, "group time: %.2f, %.2f, %.2f; total: %.2f; exp_paths time: %.2f; aut_check time: %.2f\n%lu refinement%s interrupted by trace comparison (%s); special cells: %d\n------", tv->schreier1, tv->schreier2, tv->schreier3, tv->schreier1+tv->schreier2+tv->schreier3,
tv->expaths, tv->autchk, SS(tv->stats->interrupted, "", "s"), (tv->options->strategy == 0 ? "breadth-first" : "depth-first"), tv->specialgens);
PRINT_RETURN
}
if (tv->options->verbosity >= 3) fprintf(outfile, "CPYCAND(0): %d, ID<-TMPORB(1): %d, LAB(2): %d, PART(3): %d, TEMP(4)->: %d, TEMP(5)<-: %d, CHKFORAUT(6): %d, ISAUT(7): %d, ContaTC: %d\n", tv->conta0, tv->conta1, tv->conta2, tv->conta3, tv->conta4, tv->conta5, tv->conta6, tv->conta7, tv->contatc);
if (tv->options->getcanon && canong_arg) {
canong_arg->nv = g_arg->nv;
canong_arg->nde = g_arg->nde;
SG_ALLOC(*canong_arg, g_arg->nv, g_arg->nde, "traces canong");
updatecan_tr(g_arg, canong_arg, lab, CurrPart->inv, 0);
}
if (tv->options->generators) {
deleteunmarked(&gensB);
*tv->options->generators = gensB;
freeschreier(&gpB, NULL);
}
else {
freeschreier(&gpB, &gensB);
schreier_freedyn();
}
while (STStart) {
STAux = STStart;
free(STAux->triearray);
STStart = STStart->next;
free(STAux);
}
tv->canlist = 0;
for (i=0; i<=tv->treedepth; i++) {
if (Spine[i].liststart) {
tv->canlist += FreeList(Spine[i].liststart, TRUE);
Spine[i].liststart = Spine[i].listend = NULL;
}
}
if (GarbList) {
tv->stats->peaknodes = FreeList(GarbList, FALSE);
}
FREECAND(NextCand)
FREECAND(SpOrd)
FREECAND(SpCyc)
FREECAND(SpSwp)
FREEPART(NextPart)
FREEPART(SpPart1)
FREEPART(SpPart2)
if (!tv->options->getcanon && trieroot) {
for (i=0; i<=tv->triepos; i++) {
free(TrieArray[i]);
}
}
for (i=0; i <= tv->treedepth; i++) {
FREEPART(Spine[i].part)
}
CurrCand = GarbList = NULL;
tv->stats->peaknodes += tv->canlist;
if (tv->graph != g_arg) {
SG_FREE(redgraph);
}
free(tv);
free(ti);
traces_freedyn();
return;
}
int traces_vertexclass_refine (int n, int *lab, int *ptn, Candidate *Cand, Partition *Part, int *RefArray) {
int i, j, k, aux, cells, end;
memcpy(Cand->lab, lab, n*sizeof(int));
cells = 0;
j = 0;
for (i = 0; i < n; i++) {
WorkArray1[i] = RefArray[Cand->lab[i]];
if (!ptn[i]) {
TheTrace[cells++] = j;
sort2ints(WorkArray1+j,Cand->lab+j,i-j+1);
aux = WorkArray1[j];
Part->cls[j] = 1;
Part->inv[j] = j;
Cand->invlab[Cand->lab[j]] = j;
if (i == j) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[j]);
j++;
} else {
end = i+1;
for (k=j+1; k<end; k++) {
if (WorkArray1[k] == aux) {
(Part->cls[j])++;
Part->inv[k] = j;
Cand->invlab[Cand->lab[k]] = k;
} else {
if (Part->cls[j] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[j]);
}
TheTrace[cells++] = k;
j = k;
aux = WorkArray1[j];
Part->cls[j] = 1;
Part->inv[j] = j;
Cand->invlab[Cand->lab[j]] = j;
}
}
j = end;
}
}
}
return cells;
}
int traces_refine(Candidate *Cand,
int n,
Partition *Part,
struct TracesVars* tv,
struct TracesInfo *ti,
int num_indv,
boolean make_code) {
int i, j, k, jk, sc, ind0, ind1, ind2, ind3, ind4, tlp1, labi;
int value, iend, newcell;
int HitClsInd, SplInd, SplCntInd, CStackInd, TraceInd, TraceCCInd, TraceStepsInd, SingInd;
int j1int, iend1int;
unsigned int longcode;
int newtrace = FALSE;
int Sparse = TRUE;
int *lab, *cls, *InvLab, *TracePos, *SplitCell, *LabCell, *TraceEnd, Traceccend, *Tracestpend;
int BigCell, BigCellPos, BigCellSize;
boolean TraceCell = FALSE;
int *nghb;
int conta;
const int variation = 0;
int currentweight, weightstart, weightend, currentcell, currentsize;
VERB_PRINT("RFLT",3,FALSE)
HitClsInd = 0;
if (tv->stackmark > (NAUTY_INFINITY-2)) {
memset(StackMarkers, 0, n*sizeof(int));
tv->stackmark = 0;
}
tv->stackmark++;
tv->augmented_cells = Part->cells;
SpineTL = Spine+tv->tolevel;
TraceEnd = &(SpineTL->trcend);
Traceccend = SpineTL->ccend;
Tracestpend = &(SpineTL->stpend);
TraceCCInd = SpineTL->ccstart;
TraceStepsInd = SpineTL->stpstart;
SingInd = SpineTL->singstart + num_indv;
lab = Cand->lab;
InvLab = Cand->invlab;
cls = Part->cls;
UPDATEMIN(Part->active, n-1);
memcpy(CStack+1, TheTrace+SpineTL->trcstart, (Part->active)*sizeof(int));
CStackInd = Part->active;
for (i = 1; i <= CStackInd; i++) {
StackMarkers[CStack[i]] = tv->stackmark;
}
longcode = Part->cells;
TraceInd = SpineTL->trcstart+Part->active;
if (!SpineTL->thetracexists) {
newtrace = TRUE;
}
conta=0;
while (CStackInd > 0) {
weightend = 0;
if (tv->mark > (NAUTY_INFINITY-2)) {
memset(Markers, 0, n*sizeof(int));
memset(MarkHitVtx, 0, n*sizeof(int));
tv->mark = 0;
}
tv->mark++;
if (Part->cells == n) break;
k = Select_from_CStack(cls, CStackInd);
currentcell = CStack[k];
currentsize = currentcell+cls[currentcell];
CStack[k] = CStack[CStackInd--];
StackMarkers[currentcell] = 0;
labi = lab[currentcell];
iend1int = TheGraph[labi].d;
nghb = TheGraph[labi].e;
do {
ind0 = currentcell;
ind2 = currentsize;
weightstart = weightend;
if (tv->options->weighted) {
currentweight = (TheGraph[labi].w)[weightstart];
while ((iend1int > weightend) && ((TheGraph[labi].w)[weightend] == currentweight)) {
weightend++;
}
} else {
weightend = TheGraph[labi].d;
}
if (!newtrace) {
TraceCell = ((ind0 == TheTraceCC[TraceCCInd]) && (TraceCCInd < Traceccend));
}
/* Analysis of occurrences of neighbors of the current cell */
/* The list of cells with neighbors in the current cell is built */
if (cls[ind0] == 1) { /* SINGLETON CURRENT CELL CASE */
/* NEIGHCOUNT_SING_MULT */
HitClsInd = 0;
for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
value = Part->inv[InvLab[k]];
if (cls[value] > 1) {
if (Markers[value] != tv->mark) {
HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
ElmHitCll[value] = value;
}
HitVtx[ElmHitCll[value]++] = k;
} else {
switch (variation) {
case 1:
longcode = MASHCOMM(longcode, value);
break;
default:
break;
}
}
}
/* end NEIGHCOUNT_SING_MULT */
tv->mark++;
FIND_SPLIT_CELLS;
/* SINGLETON CC CASE */
if (SplInd) {
if (newtrace) {
TheTraceCC[TraceCCInd] = ind0;
}
if (!TraceCell) {
TheTraceCC[TraceCCInd] = ind0;
newtrace = TRUE;
}
TRACE_CHECK(TheTraceSplNum, TraceCCInd, SplInd, &Traceccend)
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) {
ind1 = SplCls[j];
i = ind1+cls[ind1]-ElmHitCll[ind1];
TRACE_CHECK(TheTrace, TraceInd, i, TraceEnd)
}
for (j = 0; j < SplInd; j++) {
/* REARRANGE_CELLS */
ind1 = SplCls[j];
cls[ind1] = cls[ind1]-ElmHitCll[ind1];
newcell = ind1+cls[ind1];
cls[newcell] = ElmHitCll[ind1];
Part->cells++;
if (StackMarkers[ind1] != tv->stackmark) {
if (cls[newcell] < cls[ind1]) {
CStack[++CStackInd] = newcell;
StackMarkers[newcell] = tv->stackmark;
}
else {
CStack[++CStackInd] = ind1;
StackMarkers[ind1] = tv->stackmark;
}
}
else {
CStack[++CStackInd] = newcell;
StackMarkers[newcell] = tv->stackmark;
}
SplitCell = HitVtx+ind1;
ind3 = cls[newcell];
LabCell = lab+newcell;
for (jk = 0; jk < ind3; jk++) {
k = SplitCell[jk];
i = LabCell[jk];
Part->inv[newcell+jk] = newcell;
lab[InvLab[k]] = i;
InvLab[i] = InvLab[k];
LabCell[jk] = k;
InvLab[k] = newcell+jk;
}
/* END REARRANGE_CELLS */
if (cls[ind1] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[ind1]);
if (newtrace) Singletons[SingInd] = ind1;
SingInd++;
}
if (cls[newcell] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[newcell]);
if (newtrace) Singletons[SingInd] = newcell;
SingInd++;
}
}
}
else {
if ((!newtrace) && TraceCell) {
if (!tv->options->weighted) return 0;
}
}
}
else {
if (ti->thegraphisparse) {
/* NEIGHCOUNT_SPARSE_MULT */
HitClsInd = 0;
if (cls[ind0] != n) {
for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e;
for (j = weightstart; j < weightend; j++) {
k = nghb[j];
if (MarkHitVtx[k] == tv->mark) {
NghCounts[k]++;
}
else {
value = Part->inv[InvLab[k]];
if (cls[value] > 1) {
MarkHitVtx[k] = tv->mark;
NghCounts[k] = 1;
if (Markers[value] != tv->mark) {
HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
HitVtx[value] = k;
ElmHitCll[value] = 1;
}
else {
HitVtx[value+ElmHitCll[value]++] = k;
}
}
else {
switch (variation) {
case 1:
longcode = MASHCOMM(longcode, value);
break;
default:
break;
}
}
}
}
}
}
/* End NEIGHCOUNT_SPARSE_MULT */
tv->mark++;
SplInd = 0;
SplCls[0] = n;
for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
if ((ElmHitCll[ind1] > 0) && (ElmHitCll[ind1] < cls[ind1])) {
SplCls[SplInd++] = ind1;
}
else {
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]];
for (i = ind1; i < ind2; i++)
{
if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j];
break;
}
}
}
}
/* SPARSE CASE */
if (SplInd) {
if (newtrace) {
TheTraceCC[TraceCCInd] = ind0;
}
if (!TraceCell) {
TheTraceCC[TraceCCInd] = ind0;
newtrace = TRUE;
}
TRACE_CHECK(TheTraceSplNum, TraceCCInd, SplInd+n, &Traceccend)
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (sc = 0; sc < SplInd; sc++) { /* For each cell C to be split */
ind0 = SplCls[sc];
ind1 = ind0 + cls[ind0];
SplCntInd = 0;
if (ElmHitCll[ind0] < cls[ind0]) {
SplCnt[SplCntInd++] = 0;
SplPos[0] = cls[ind0] - ElmHitCll[ind0];
}
/* According to the numbers of neighbors of C into the current cell */
/* compute how many vertices in C will be placed into the same new cell */
iend = ind0 + ElmHitCll[ind0];
for (i = ind0; i < iend; i++) {
value = NghCounts[HitVtx[i]];
if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
}
else {
SplPos[value]++;
}
}
tv->mark++;
if (SplCntInd) {
TRACE_CHECK(TheTraceSteps, TraceStepsInd, SplCntInd+n, Tracestpend)
}
/* Sort the values deriving from the previous step */
sort_Split_Array(SplCnt,SplCntInd);
Part->cells += SplCntInd-1;
/* Split the cell C and update the information for sizes of new cells */
/* Put the new cells into the stack */
i = ind0;
if (StackMarkers[i] != tv->stackmark) {
BigCellSize = 0;
}
for (k = 0; k < SplCntInd; k++) {
value = SplPos[SplCnt[k]];
cls[i] = value;
if ((StackMarkers[ind0] != tv->stackmark) && (value > BigCellSize)) {
BigCell = i;
BigCellPos = CStackInd;
BigCellSize = cls[i];
}
SplPos[SplCnt[k]] = i;
i += value;
if (i < ind1) {
CStack[++CStackInd] = i;
StackMarkers[i] = tv->stackmark;
TRACE_CHECK(TheTrace, TraceInd, i, TraceEnd)
}
}
if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
}
/* Permute elements of the cell C */
iend = ind0 + ElmHitCll[ind0];
for (i = ind0; i < iend; i++) {
value = HitVtx[i];
j = SplPos[NghCounts[value]]++; /* where HitVtx[i] goes */
k = InvLab[value]; /* where HitVtx[i] is in lab */
lab[k] = lab[j];
lab[j] = value;
InvLab[value] = j;
InvLab[lab[k]] = k;
NghCounts[value] = 0;
}
/* Reconstruct the cell C and update the inverse partition */
newcell = ind1 - ElmHitCll[ind0];
i = newcell;
ind2 = newcell+cls[newcell]-1;
do {
Part->inv[i] = newcell;
if (i == ind2) {
newcell = i+1;
if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
}
while (++i < ind1);
for (i = ind0, k = 0; k < SplCntInd; i+=cls[i], k++) {
if (cls[i] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[i]);
if (newtrace) Singletons[SingInd] = i;
SingInd++;
}
}
}
}
else {
if ((!newtrace) && TraceCell) {
return 0;
}
}
}
else {
if (TheGraph[lab[ind0]].d > n/cls[ind0]) {
Sparse = FALSE;
}
else {
Sparse = TRUE;
}
Sparse = TRUE;
if (Sparse) {
/* Counting occurrences of neighbors of the current cell */
/* The list of cells with neighbors in the current cell is also built */
if (cls[ind0] == n) {
for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
HitCls[0] = 0;
HitClsInd = 1;
}
else {
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.224 Sekunden
]
|
2026-03-28
|
