Quelle traces.c Sprache: C

/******************************************************************************
*                                                                            *
* 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

--> --------------------

quality92%

¤ Dauer der Verarbeitung: 0.41 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.