typedefstruct Candidate {
boolean sortedlab; int *invlab; int *lab; int code; int do_it; int indnum; int name; int vertex; struct Candidate *next; struct searchtrie *stnode; unsignedint firstsingcode; unsignedint pathsingcode; unsignedint singcode;
} Candidate;
typedefstruct Partition { int *cls; int *inv; int active; int cells; int code;
} Partition;
typedefstruct 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; unsignedint 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;
typedefstruct 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; unsignedlong keptcounter; unsignedlong levelcounter;
Partition *part; unsignedint singcode;
} TracesSpine;
/* 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 */
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;
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;
}
}
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;
}
/* 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;
}
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 (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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* DENSE-SPARSE CASE */ if (SplInd) { if (newtrace) {
TheTraceCC[TraceCCInd] = ind0;
} if (!TraceCell) {
TheTraceCC[TraceCCInd] = ind0;
newtrace = TRUE;
}
TRACE_CHECK(TheTraceSplNum, TraceCCInd, SplInd+2*n, &Traceccend)
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[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+2*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)
}
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
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 (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
SplInd = 0;
ind4 = 0; while (ind4 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind4+cls[ind4]; if (cls[ind4] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind4]]; for (i = ind4+1; i < ind1; i++) { if (NghCounts[lab[i]] != value)
{
SplInd++;
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind4; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
tv->mark++;
if (SplInd && !TraceCell) newtrace = TRUE;
if (SplCntInd) {
TRACE_CHECK(TheTraceSteps, TraceStepsInd, SplCntInd+3*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 = ind4; if (StackMarkers[i] != tv->stackmark) {
BigCellSize = 0;
} for (k = 0; k < SplCntInd; k++) {
value = SplPos[SplCnt[k]];
cls[i] = value;
if (cls[ind1] == 1) {
Cand->pathsingcode = MASHCOMM(Cand->pathsingcode, lab[ind1]);
} if (cls[newcell] == 1) {
Cand->pathsingcode = MASHCOMM(Cand->pathsingcode, lab[newcell]);
}
}
} 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];
Split = FALSE;
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j];
Split = TRUE; break;
}
} if (!Split) {
longcode = MASHCOMM(longcode, ind1);
}
}
}
/* 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++;
/* 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;
}
}
/* 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->pathsingcode = MASHCOMM(Cand->pathsingcode, lab[i]);
}
}
}
} 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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[i]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
}
tv->mark++;
/* 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;
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
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->pathsingcode = MASHCOMM(Cand->pathsingcode, lab[i]);
}
}
}
} else { if (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
ind0 = 0; while (ind0 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind0+cls[ind0]; if (cls[ind0] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind0]]; for (i = ind0+1; i < ind1; i++)
{ if (NghCounts[lab[i]] != value)
{
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind0; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
if (SplCntInd) {
tv->mark++;
/* 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;
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
for (i = ind0; i < ind1; i+=cls[i]) { if (cls[i] == 1) {
Cand->pathsingcode = MASHCOMM(Cand->pathsingcode, lab[i]);
}
}
}
}
ind0 = ind1;
}
}
}
}
} while (weightend < iend1int);
} /* end while (CStackInd > 0) */
/* 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;
/* 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];
trieref = trie_make(trieref, i, n, tv);
}
/* 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];
Split = FALSE;
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j];
Split = TRUE; break;
}
} if (!Split) {
longcode = MASHCOMM(longcode, ind1);
}
}
}
/* 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++;
/* 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;
trieref = trie_make(trieref, i, n, tv);
}
}
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);
}
} 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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[i]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
}
tv->mark++;
/* 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;
trieref = trie_make(trieref, i, n, tv);
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
}
} else { if (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
ind0 = 0; while (ind0 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind0+cls[ind0]; if (cls[ind0] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind0]]; for (i = ind0+1; i < ind1; i++)
{ if (NghCounts[lab[i]] != value)
{
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind0; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
if (SplCntInd) {
tv->mark++;
/* 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;
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
trieref = trie_make(trieref, i, n, tv);
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
}
}
ind0 = ind1;
}
}
}
}
} while (weightend < iend1int);
} /* end while (CStackInd > 0) */
int traces_refine_comptrie(Candidate *Cand, int n,
Partition *Part, struct TracesVars* tv, struct TracesInfo *ti) { int i, j, k, jk, sc, ind0, ind1, ind2, ind3, labi; int value, iend, newcell; int HitClsInd, SplInd, SplCntInd, CStackInd; int j1int, iend1int; unsignedint longcode; int Split = 0; int Sparse = TRUE; int *lab, *cls, *InvLab, *SplitCell, *LabCell; int BigCell, BigCellPos, BigCellSize; int *nghb; constint variation = 1; int currentweight, weightstart, weightend, currentcell, currentsize;
/* 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;
/* 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];
trieref = trie_comp(trieref, i); if (trieref == NULL) return 0;
}
/* 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];
Split = FALSE;
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j];
Split = TRUE; break;
}
} if (!Split) {
longcode = MASHCOMM(longcode, ind1);
}
}
}
/* 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++;
/* 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;
trieref = trie_comp(trieref, i); if (trieref == NULL) return 0;
}
}
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);
}
} 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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
;
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[i]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
}
tv->mark++;
/* 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;
trieref = trie_comp(trieref, i); if (trieref == NULL) return 0;
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell;
if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
}
} else { if (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
ind0 = 0; while (ind0 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind0+cls[ind0]; if (cls[ind0] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind0]]; for (i = ind0+1; i < ind1; i++)
{ if (NghCounts[lab[i]] != value)
{
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind0; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
if (SplCntInd) {
tv->mark++;
/* 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;
}
} if ((StackMarkers[ind0] != tv->stackmark) && (BigCell != ind0)) {
CStack[BigCellPos] = ind0;
StackMarkers[BigCell] = 0;
StackMarkers[ind0] = tv->stackmark;
trieref = trie_comp(trieref, i); if (trieref == NULL) return 0;
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
}
}
ind0 = ind1;
}
}
}
}
} while (weightend < iend1int);
} /* end while (CStackInd > 0) */
/* 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) {
SAMETRACE_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];
SAMETRACE_CHECK(TheTrace, TraceInd, i, TraceEnd)
}
/* 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) {
SAMETRACE_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) {
SAMETRACE_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;
SAMETRACE_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]);
}
}
}
} else { if (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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* DENSE-SPARSE CASE */ if (SplInd) {
SAMETRACE_CHECK(TheTraceSplNum, TraceCCInd, SplInd+2*n, &Traceccend)
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[i]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
}
tv->mark++;
if (SplCntInd) {
SAMETRACE_CHECK(TheTraceSteps, TraceStepsInd, SplCntInd+2*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;
SAMETRACE_CHECK(TheTrace, TraceInd, i, TraceEnd)
}
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
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]);
}
}
}
} else { if (TraceCell) { return 0;
}
}
} else { if (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
SplInd = 0;
ind4 = 0; while (ind4 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind4+cls[ind4]; if (cls[ind4] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind4]]; for (i = ind4+1; i < ind1; i++) { if (NghCounts[lab[i]] != value)
{
SplInd++;
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind4; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
tv->mark++;
if (SplCntInd) {
SAMETRACE_CHECK(TheTraceSteps, TraceStepsInd, SplCntInd+3*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 = ind4; if (StackMarkers[i] != tv->stackmark) {
BigCellSize = 0;
} for (k = 0; k < SplCntInd; k++) {
value = SplPos[SplCnt[k]];
cls[i] = value; if ((StackMarkers[ind4] != 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;
SAMETRACE_CHECK(TheTrace, TraceInd, i, TraceEnd)
}
} if ((StackMarkers[ind4] != tv->stackmark) && (BigCell != ind4)) {
CStack[BigCellPos] = ind4;
StackMarkers[BigCell] = 0;
StackMarkers[ind4] = tv->stackmark;
}
/* Permute elements of the cell C */
i = ind4; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind4;
i = ind4;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
for (i = ind4, k = 0; k < SplCntInd; i+=cls[i], k++) { if (cls[i] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[i]);
}
}
}
}
ind4 = ind1;
}
/* DENSE-DENSE CASE */ if (SplInd) {
SAMETRACE_CHECK(TheTraceSplNum, TraceCCInd, SplInd+3*n, &Traceccend)
} else { if (TraceCell) { return 0;
}
}
}
}
}
} while (weightend < iend1int);
} /* end while (CStackInd > 0) */
for (i=SpineTL->trcstart; i < TraceInd; i++) {
ind0 = TheTrace[i];
longcode = MASHNONCOMM(longcode, Part->inv[ind0]);
labi = lab[ind0];
iend1int = TheGraph[labi].d;
nghb = TheGraph[labi].e; for (j1int = 0; j1int < iend1int; ++j1int) {
k = nghb[j1int];
value = Part->inv[InvLab[k]];
longcode = MASHCOMM(longcode, value);
}
}
/* 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) {
/* 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];
}
/* 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) {
/* 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++;
/* 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;
}
}
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);
}
}
} 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 {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_SPARSE_MULT */
HitClsInd = 0; for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
value = Part->inv[InvLab[k]]; if (Markers[value] != tv->mark) { if (cls[value] > 1) HitCls[HitClsInd++] = value;
Markers[value] = tv->mark;
}
}
} /* End NEIGHCOUNT_DENSE_SPARSE_MULT */
}
tv->mark++;
SplInd = 0; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j];
ind2 = ind1+cls[ind1];
value = NghCounts[lab[ind1++]]; for (i = ind1; i < ind2; i++)
{ if (NghCounts[lab[i]] != value)
{
SplCls[SplInd++] = HitCls[j]; break;
}
}
}
/* DENSE-SPARSE CASE */ if (SplInd) {
/* Sorting the cells to be split */
sort_Split_Array(SplCls, SplInd);
for (j = 0; j < SplInd; j++) { /* For each cell C to be split */
ind0 = SplCls[j];
ind1 = ind0+cls[ind0];
SplCntInd = 0;
/* 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 */ for (i = ind0; i < ind1; i++) {
value = NghCounts[lab[i]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
}
tv->mark++;
/* 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;
}
}
/* Permute elements of the cell C */
i = ind0; do {
SplCnt[SplPos[NghCounts[lab[i]]]++] = lab[i];
} while(++i < ind1);
/* Reconstruct the cell C and update the inverse partition */
newcell = ind0;
i = ind0;
ind2 = newcell+cls[newcell]-1; do {
lab[i] = SplCnt[i];
InvLab[lab[i]] = i;
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+cls[newcell]-1;
}
} while (++i < ind1);
}
}
} else { if (cls[ind0] == n) { for (i = 0; i < n; i++) {
NghCounts[i] = TheGraph[i].d;
}
} else {
memset(NghCounts, 0, n*sizeof(int));
/* NEIGHCOUNT_DENSE_DENSE_MULT */ for (i = ind0; i < ind2; i++) {
labi = lab[i];
nghb = TheGraph[labi].e; for (j1int = weightstart; j1int < weightend; ++j1int) {
k = nghb[j1int];
(NghCounts[k])++;
}
} /* End NEIGHCOUNT_DENSE_DENSE_MULT */
}
SplInd = 0;
ind4 = 0; while (ind4 < n) { /* For each cell C with size(C) > 1 */
ind1 = ind4+cls[ind4]; if (cls[ind4] > 1) {
/* Determine whether C must be split */
SplCntInd = 0;
value = NghCounts[lab[ind4]]; for (i = ind4+1; i < ind1; i++) { if (NghCounts[lab[i]] != value)
{
SplInd++;
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = i-ind4; do {
value = NghCounts[lab[i++]]; if (Markers[value] != tv->mark) {
Markers[value] = tv->mark;
SplCnt[SplCntInd++] = value;
SplPos[value] = 1;
} else {
SplPos[value]++;
}
} while(i != ind1); break;
}
}
tv->mark++;
if (SplCntInd) {
/* 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 = ind4; if (StackMarkers[i] != tv->stackmark) {
BigCellSize = 0;
} for (k = 0; k < SplCntInd; k++) {
value = SplPos[SplCnt[k]];
cls[i] = value;
int Check_degree_one(sparsegraph *sg, Candidate *Cand, Partition *Part, int n) {
int i;
for (i=0; i<n; i += Part->cls[i]) { if (sg->d[Cand->lab[i]] == 1) { returnTRUE;
}
} returnFALSE;
}
int CheckForAutomorphisms(Candidate *CurrCand, Candidate *NextCand, struct TracesVars* tv, struct TracesInfo* ti, int m, int n, Partition* Part) {
Candidate *CheckAutList; int i, j, k, tgt_level, numtemporbits; int CheckLevel, CheckLevelEnd; int temp, tmp, tmp1, arg, arg1, val, val1;
searchtrie *TrieCandFrom, *TrieCheckFrom;
if (CheckAutList->lab[Spine[temp].tgtpos] == AutomCount[1]) { for (i=1; i<AutomCount[0]; i++) if (AutomCount[i] == tmp1) break; if (i == AutomCount[0]) {
AutomCount[AutomCount[0]++] = TempOrbits[NextCand->lab[Spine[temp].tgtpos]];
}
}
void CodeClassify(int Level, int code, int cell) { switch (EPCodes[Level].info) { case 0:
EPCodes[Level].code = code;
EPCodes[Level].cell = cell;
EPCodes[Level].info = 1; break; case 1: if (EPCodes[Level].cell != cell) {
EPCodes[Level].info = 3;
} else { if (EPCodes[Level].code != code) {
EPCodes[Level].info = 2;
}
} break; case 2: if (EPCodes[Level].cell != cell) {
EPCodes[Level].info = 3;
} break; default: break;
}
}
void Complete(sparsegraph *sg_orig, Candidate *Cand, Partition *Part, int cell, TracesVars *tv, double *grpsize1, int *grpsize2, permnode **ring, int n) { int i, j, k; int arg, val; int numtemporbits;
k = cell + Part->cls[cell];
if (tv->permInd) ResetAutom(tv->permInd, n, tv); for (i = cell; i < k; i++) {
tv->currorbit[Cand->lab[i]] = Cand->lab[k];
arg = Cand->lab[i];
val = Cand->lab[i+1];
SETPAIRSAUTANDTREE(arg, val)
}
arg = Cand->lab[i];
val = Cand->lab[cell];
SETPAIRSAUTANDTREE(arg, val)
SPECIALGENERATORS
if (Part->cls[cell] > 1) { if (tv->permInd) ResetAutom(tv->permInd, n, tv);
arg = Cand->lab[cell];
val = Cand->lab[cell+1];
SETPAIRSAUTANDTREE(arg, val)
arg = Cand->lab[cell+1];
val = Cand->lab[cell];
SETPAIRSAUTANDTREE(arg, val)
SPECIALGENERATORS
}
}
int CompStage0(Partition *CurrPart, Partition *NextPart, Candidate *CurrCand, Candidate *NextCand, int m, int n, struct TracesVars* tv, struct TracesInfo *ti) { int i, j, i1, j2, k, cu, cu1, num_indv; int temp, tmp, auxcode, search_vtx, gom_level;
boolean closeloop, firstsing, has_nexttcell;
Candidate *SpTLliststart, *AuxCand;
searchtrie *TreeNode, *TreeNode1, *TreeNode2;
#ifdef NAUTY_IN_MAGMA if (main_seen_interrupt) return NAUTY_KILLED; #else if (nauty_kill_request) return NAUTY_KILLED; #endif
Individualize(NextPart, NextCand, NextCand->vertex, tv->tcell, CurrPart->cells, SpineTL->tgtpos);
tv->stats->numnodes++;
tv->answ = traces_refine(NextCand,
n,
NextPart, tv, ti, num_indv, TRUE); switch (tv->answ) { case 0: /* Interrupted refinement: do not add to the list */
tv->stats->interrupted++;
SpineTL->levelcounter++; break; case 1 : /* The same trace has been found once more : add to the list */
SpineTL->levelcounter++;
NextCand->do_it = TRUE; if (tv->options->verbosity >= 2) PRINT_CANDIDATE(NextCand, tv->tolevel);
/* ANY AUTOMORPHISM? */ if (tv->options->verbosity >= 2) tv->autchk -= CPUTIME;
tv->newindex = 0; if (NextCand->do_it) {
closeloop = CheckForAutomorphisms(CurrCand, NextCand, tv, ti, m, n, NextPart); if (!NextCand->do_it && closeloop < tv->tolevel) k = SpineTL->tgtend;
} if (tv->options->verbosity >= 2) tv->autchk += CPUTIME;
if (NextCand->do_it) {
ADDTONEXTLEVEL;
SpineTL->keptcounter++;
searchtrie_make(CurrCand, SpineTL->listend, n, tv);
}
} else { if (BreakSteps[tv->tolevel]) {
NextCand->firstsingcode = NextCand->pathsingcode; if (CheckForSingAutomorphisms(CurrCand, NextPart, NextCand, tv, ti, m, n)) if (!NextCand->do_it) {
PRINT_RETURN break;
}
}
/* ANY AUTOMORPHISM? */ if (tv->options->verbosity >= 2) tv->autchk -= CPUTIME;
tv->newindex = 0; if (NextCand->do_it) {
closeloop = CheckForAutomorphisms(CurrCand, NextCand, tv, ti, m, n, NextPart); if (!NextCand->do_it && closeloop < tv->tolevel) k = SpineTL->tgtend;
} if (tv->options->verbosity >= 2) tv->autchk += CPUTIME;
if (NextCand->do_it) {
ADDTONEXTLEVEL;
SpineTL->keptcounter++;
searchtrie_make(CurrCand, SpineTL->listend, n, tv);
}
}
PRINT_RETURN break; case 2 : /* Delete the old list and start a new one: a better trace has been found */
if (NextPart->cells > tv->finalnumcells) {
tv->finalnumcells = NextPart->cells;
}
tv->tolevel_tl = tv->tolevel;
has_nexttcell = FALSE; if (NextPart->cells == n) {
tv->stats->canupdates++; if (tv->options->usercanonproc != NULL)
{
(*tv->options->usercanonproc)((graph*)tv->input_graph, NextCand->lab, (graph*)tv->cangraph, tv->stats->canupdates, NextCand->code, m, n);
}
}
if (tv->tolevel > tv->treedepth) {
tv->treedepth = tv->tolevel; if (tv->strategy) {
SpineTL->part = NewPartition(n);
} else {
NewPartSpine(tv->tolevel,n);
}
}
if (!tv->strategy && (tv->tolevel > 1) && !SpineTL->liststart) { /* First Candidate at current level */
tv->maxtreelevel = tv->tolevel;
int CompStage1(Partition *CurrPart, Partition *NextPart, Candidate *CurrCand, Candidate *NextCand, int m, int n, struct TracesVars* tv, struct TracesInfo *ti) { int i, k, cu, cu1, tmp, gom_level, search_vtx, temp;
searchtrie *TreeNode, *TrieNode;
#ifdef NAUTY_IN_MAGMA if (main_seen_interrupt) return NAUTY_KILLED; #else if (nauty_kill_request) return NAUTY_KILLED; #endif
/* ANY AUTOMORPHISM? */ if (tv->options->verbosity >= 2) tv->autchk -= CPUTIME;
PRINTF2("CS1 2?: finalnumcells: %d\n", tv->finalnumcells);
CheckForAutomorphisms(CurrCand, NextCand, tv, ti, m, n, NextPart); if (tv->options->verbosity >= 2) tv->autchk += CPUTIME;
PRINT_RETURN
/* ADD TO NEXT LEVEL */
SpineTL->keptcounter++; if (!Spine[tv->tolevel].listend) COPYPART(Spine[tv->tolevel].part, NextPart);
ADDTONEXTLEVEL;
searchtrie_make(CurrCand, SpineTL->listend, n, tv);
}
} /* end for */
PRINTF2("CS1 3: finalnumcells: %d\n", tv->finalnumcells); for (k = tv->indivstart; k < tv->indivend; k++) {
MultRefCells[RefCells[tv->currorbit[CurrCand->lab[k]]] % n]++;
}
if (tv->options->verbosity >= 2) { if (MultRefCells[0]) {
fprintf(outfile, tv->digstring, n);
fprintf(outfile, "cells: %d; ", MultRefCells[0]);
} for (k=1; k<n; k++) { if (MultRefCells[k]) {
fprintf(outfile, tv->digstring, k);
fprintf(outfile, "cells: %d; ", MultRefCells[k]);
}
}
NEXTLINE
void factorial2(double *size1, int *size2, int k) { int i;
for(i = k; i > 0; i -= 2) {
MULTIPLY(*size1, *size2, i);
}
}
boolean findperm(permnode *pn, int *p, int n) {
permnode *rn;
if (!pn) { returnFALSE;
}
rn = pn; do { if (!memcmp(rn->p, p, n*sizeof(int))) { returnTRUE;
}
rn = rn->next;
} while (rn != pn); returnFALSE;
}
int *findcurrorbits(schreier *gp, int k) { int i;
schreier *sh;
sh = gp; for (i = 0; i < k; i++) {
sh = sh->next;
} return sh->orbits;
}
int FirstNeighbour(int vtx, Candidate *Cand, Partition *Part, int* Markers, int mark, int *ngh, int n) { int *e_vtx; int i, k, deg; int ngh1, ngh2, cell1, cell2;
k = 0;
deg = TheGraph[vtx].d;
e_vtx = TheGraph[vtx].e;
if (deg == n-1) { return 0;
}
for (i=0; i<deg; i++) { if (Markers[e_vtx[i]] != mark) {
cell1 = Part->inv[Cand->invlab[e_vtx[i]]]; if (Part->cls[cell1] > 1) {
ngh1 = e_vtx[i++];
k++; break;
}
}
} for (; i<deg; i++) { if (Markers[e_vtx[i]] != mark) {
cell2 = Part->inv[Cand->invlab[e_vtx[i]]]; if (Part->cls[cell2] > 1) {
ngh2 = e_vtx[i];
k++; break;
}
}
} switch (k) { case 0: break;
case 1:
*ngh = ngh1; break;
case 2: if (cell1 < cell2) {
*ngh = ngh1;
} else {
*ngh = ngh2;
} break;
default: break;
} return k;
}
int FixBase(int *fix, struct TracesVars *tv, Candidate *Cand, int from, int to) { int i, j, k, go, nfix;
nfix = j = 0;
go = TRUE; for (i = from; i < to; i++) {
k = Cand->lab[Spine[i+1].tgtpos]; if (go && (nfix < tv->nfix) && (fix[nfix] == k)) {
j++;
} else {
fix[nfix] = k; if (go) go = FALSE;
}
nfix++;
}
tv->nfix = nfix; return j;
}
boolean FixedBase(int *fix, struct TracesVars *tv, Candidate *Cand, int from, int to) { int i, k, nfix;
nfix = 0; for (i = from; i < to; i++) {
k = Cand->lab[Spine[i+1].tgtpos]; if (fix[nfix] != k) { returnFALSE;
}
nfix++;
} returnTRUE;
}
int FreeList(Candidate *List, int cond) {
Candidate *Temp; int conta = 0; int conta1 = 0;
while (List) { if (List->do_it == cond) {
conta1++;
}
conta++;
Temp = List; if (List->lab) free(List->lab); if (List->invlab) free(List->invlab);
List = List->next;
free(Temp);
}
/* Check if the permutations in the list gens are automorphisms,
* also set mark and refcount fields and initialise orbits. */ int given_gens(sparsegraph *g, permnode *gens, int *orbits, boolean digraph) { int i, m, n, norbs;
permnode *pn;
n = g->nv; for (i = 0; i < n; ++i) orbits[i] = i;
memcpy(IDENTITY_PERM, orbits, n*sizeof(int));
norbs = n;
if (!gens) return norbs;
m = SETWORDSNEEDED(n);
pn = gens; do { if (!isautom_sg((graph*)g, pn->p, digraph, m, n)) {
fprintf(ERRFILE, "Input permutation is not an automorphism\n"); exit(1);
}
norbs = orbjoin(orbits, pn->p, n);
pn->mark = 1;
pn->refcount = 0;
pn = pn->next;
} while (pn != gens);
return norbs;
}
void grouporderplus(sparsegraph *sg_orig, Candidate *Cand, Partition *Part, permnode **ring, double *grpsize1, int *grpsize2, int n, TracesVars *tv, TracesInfo *ti) {
int i, i1, j, j0, j2, k, k1, k2, w, w1, w2, c, c1, c2, n1, n2; int prev, step, start, counts, StInd, CyInd, cycnum; int tmp, temp, halfsize, nghcell, numvertices; int arg, val;
searchtrie *TrieNode; int NSFCInd, ind;
boolean do_ngh = FALSE;
if (Part->cells < n) { if (!ti->deg_one) { if (sg_orig->e) {
memcpy(tv->graph->e, sg_orig->e, tv->graph->elen*sizeof(int)); for (i=0; i<n; i++) {
TheGraph[i].e = tv->graph->e + sg_orig->v[i];
}
}
}
NSFCInd = 0;
/* Trees */ if (tv->options->getcanon && tv->preprocessed) { for (i = 0; i < n; i += Part->cls[i]) { if (Part->cls[i] == 1) {
tmp = Cand->lab[i]; if ((TheGraph[tmp].d >= 0) && (TheGraph[tmp].d < sg_orig->d[tmp])) { for (j=i; j<i+Part->cls[i]; j++) {
MakeCanTree(Cand->lab[j], sg_orig, n, Cand, Part, tv);
}
}
}
}
}
memset(SingNonSing, 0, n*sizeof(int));
for (i = 0; i < n; i += Part->cls[i]) { if (Part->cls[i] > 1) { if (TheGraph[Cand->lab[i]].d > 2) { for (j=i; j<i+Part->cls[i]; j++) {
SingNonSing[Cand->lab[j]] = 2;
}
}
} else {
SingNonSing[Cand->lab[i]] = 1;
}
}
for (i = 0; i < n; i += Part->cls[i]) { if (Part->cls[i] > 1) { if (TheGraph[Cand->lab[i]].d > 2) NonSingDegPlus1(Cand, Part, i, tv);
NSFCells[NSFCInd++] = i;
} else {
NonSingDegPlus2(Cand, Part, i, tv);
numvertices--;
}
}
/* Degree 2 and at least one nghb with deg > 2 */
SETMARK(StackMarkers, tv->stackmark) for (ind = 0; ind < NSFCInd; ind++) {
i = NSFCells[ind];
SETMARK(Markers, tv->mark) if (Part->cls[i] > 1) {
tmp = Cand->lab[i]; if ((TheGraph[tmp].d == 2) && ((TheGraph[TheGraph[tmp].e[0]].d > 2) || ((TheGraph[TheGraph[tmp].e[1]].d > 2)))) {
n1 = TheGraph[tmp].e[0];
n2 = TheGraph[tmp].e[1]; if (TheGraph[n1].d > 2) { if (TheGraph[n2].d > 2) { if (Cand->invlab[n1] < Cand->invlab[n2]) {
start = n1;
} else {
start = n2;
}
} else {
start = n1;
}
} else {
start = n2;
}
counts = 0;
StInd = 0; for (j=i; j<i+Part->cls[i]; j++) {
step = Cand->lab[j]; if (Markers[step] != tv->mark) {
prev = start;
counts++; do {
Markers[step] = tv->mark;
PERMSTACK[StInd++] = step; if (TheGraph[step].e[0] != prev) {
prev = step;
step = TheGraph[step].e[0];
} else {
prev = step;
step = TheGraph[step].e[1];
}
} while (TheGraph[step].d == 2);
boolean isautom_sg_pair(graph *g, int *p, boolean digraph, int m, int n, struct TracesVars *tv) { int *d, *e;
size_t *v; int i, k, pi, di;
size_t vi, vpi, j;
SG_VDE(g, v, d, e);
for (k = 0; k < tv->permInd; ++k)
{
i = PrmPairs[k].arg;
pi = p[i];
di = d[i]; if (d[pi] != di) returnFALSE;
vi = v[i];
vpi = v[pi];
SETMARK(AutMarkers, tv->autmark) for (j = 0; j < di; ++j) AutMarkers[p[e[vi+j]]] = tv->autmark; for (j = 0; j < di; ++j) if (AutMarkers[e[vpi+j]] != tv->autmark) { returnFALSE;
}
}
int maxint(int u, int v) { if (u > v) { return u;
} else { return v;
}
}
int minint(int u, int v) { if (u < v) { return u;
} else { return v;
}
}
int NextNeighbour(int vtx, Candidate *Cand, Partition *Part, int* Markers, int mark, int *ngh, int n) { int *e_vtx; int i, j, deg, cell1, nghi; int cell[2]; int vert[2];
sort_Split_Array(HitCls,HitClsInd);
SplInd = 0;
SplCls[0] = n; for (j = 0; j < HitClsInd; j++) {
ind1 = HitCls[j]; if ((ElmHitCll[ind1] > 0) && (ElmHitCll[ind1] < Part->cls[ind1])) {
SplCls[SplInd++] = ind1;
} else {
ind2 = ind1+Part->cls[ind1];
value = NghCounts[Cand->lab[ind1++]]; for (i = ind1; i < ind2; i++) { if (NghCounts[Cand->lab[i]] != value) {
SplCls[SplInd++] = HitCls[j]; break;
}
} if (i == ind2) {
ind1 = HitCls[j]; if (TheGraph[Cand->lab[ind1]].d != 1) { for (i = ind1; i < ind2; i++) {
value = Cand->lab[i];
Edge_Delete(value, NghCounts[value], Cand, tv);
sge = TheGraph[value].e+TheGraph[value].d; if (NghCounts[value]>1) {
factorial(&(tv->stats->grpsize1), &(tv->stats->grpsize2), NghCounts[value]); if (tv->permInd) ResetAutom(tv->permInd, n, tv); for (j0=0; j0<NghCounts[value]-1; j0++) {
SETPAIRSAUTANDTREE_PREPROC(sge[j0], sge[j0+1])
}
SETPAIRSAUTANDTREE_PREPROC(sge[j0], sge[0])
SPECIALGENERATORS if (NghCounts[value] > 2) { if (tv->permInd) ResetAutom(tv->permInd, n, tv);
SETPAIRSAUTANDTREE_PREPROC(sge[0], sge[1]) if (tv->build_autom) {
SETPAIRSAUT(sge[1], sge[0])
}
MakeTree(sge[1], sge[0], sg, n, tv, FALSE);
SPECIALGENERATORS
}
}
} if (TheGraph[Cand->lab[ind1]].d == 1) {
CStack[CStackInd++] = ind1;
}
}
}
}
}
if (SplInd) {
for (sc = 0; sc < SplInd; sc++) { /* For each cell C to be split */
ind0 = SplCls[sc];
ind1 = ind0 + Part->cls[ind0];
SplCntInd = 0; if (ElmHitCll[ind0] < Part->cls[ind0]) {
SplCnt[SplCntInd++] = 0;
SplPos[0] = Part->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++;
/* 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; for (k = 0; k < SplCntInd; k++) {
value = SplPos[SplCnt[k]];
Part->cls[i] = value;
SplPos[SplCnt[k]] = i;
i += value; if (i < ind1) {
TheTrace[TraceInd++] = i;
}
}
/* Permute elements of the cell C */
iend = ind0 + ElmHitCll[ind0];
for (i = ind0; i < iend; i++) {
value = HitVtx[i];
Edge_Delete(value, NghCounts[value], Cand, tv);
sge = TheGraph[value].e+TheGraph[value].d; if (NghCounts[value] > 1) {
factorial(&(tv->stats->grpsize1), &(tv->stats->grpsize2), NghCounts[value]);
if (tv->permInd) ResetAutom(tv->permInd, n, tv); for (j0=0; j0<NghCounts[value]-1; j0++) {
SETPAIRSAUTANDTREE_PREPROC(sge[j0], sge[j0+1])
}
SETPAIRSAUTANDTREE_PREPROC(sge[j0], sge[0])
SPECIALGENERATORS if (NghCounts[value] > 2) { if (tv->permInd) ResetAutom(tv->permInd, n, tv);
SETPAIRSAUTANDTREE_PREPROC(sge[0], sge[1]) if (tv->build_autom) {
SETPAIRSAUT(sge[1], sge[0])
}
MakeTree(sge[1], sge[0], sg, n, tv, FALSE);
SPECIALGENERATORS
}
}
j = SplPos[NghCounts[value]]++; /* where HitVtx[i] goes */
k = Cand->invlab[value]; /* where HitVtx[i] is in lab */
Cand->lab[k] = Cand->lab[j];
Cand->lab[j] = value;
Cand->invlab[value] = j;
Cand->invlab[Cand->lab[k]] = k;
NghCounts[value] = 0;
}
/* Reconstruct the cell C and update the inverse partition */
newcell = ind1 - ElmHitCll[ind0];
i = newcell;
ind2 = newcell+Part->cls[newcell]-1; do {
Part->inv[i] = newcell; if (i == ind2) {
newcell = i+1; if (newcell < n) ind2 = newcell+Part->cls[newcell]-1;
}
} while (++i < ind1);
for (i = ind0, k = 0; k < SplCntInd; i+=Part->cls[i], k++) { if ((k > 0) || (SplCnt[0] > 0)) { if (TheGraph[Cand->lab[i]].d == 1) {
CStack[CStackInd++] = i;
}
} if (Part->cls[i] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[i]);
}
}
}
}
} return 1;
} else { return 0;
}
}
void PrintPartition(int *v, int *cls, int n, int l, int line) { int i, j, k;
k=0;
fprintf(outfile, "[ "); for (i=0; i<n; i+=cls[i]) { if ((cls[i]<=0) || i>=n) {
printf("WRONG"); break;
} for (j=i; j<i+cls[i]; j++) {
fprintf(outfile, "%d ", v[j]+l); if (k++ > 50) {
fprintf(outfile,"\n");
k=0;
}
} if ((i+cls[i])<n) fprintf(outfile, "| ");
}
fprintf(outfile, "] at line %d\n", line); return;
}
void PrintVect(int *v, int z, int n, int l) { int i;
printf("["); for (i = z; i<n; i++)
printf(" %2d", v[i]+l);
printf(" ]\n"); return;
}
void PrintWeightedGraph1(sparsegraph *g_arg, int n, char msg[30]) { int i, j; int *ngh1, *wgh1;
void sort_Split_Array(int *Array, int Ind){ int i, k, value;
switch (Ind) { case 0: case 1: break; case 2: if (Array[0] > Array[1]) {
value = Array[0];
Array[0] = Array[1];
Array[1] = value;
} break; case 3: case 4: case 5: case 6: case 7: case 8: for (k = 1; k < Ind; ++k) {
value = Array[k];
i = k - 1; while ((i >= 0) && (value < Array[i])) {
Array[i + 1] = Array[i];
--i;
}
Array[i + 1] = value;
} break; default:
quickSort(Array, Ind); break;
}
}
int spinelementorbsize(int *orbits, int *lab, int size, int elem) { int i, j, val;
j = 0;
val = orbits[elem]; for (i = 0; i < size; ++i) { if (orbits[lab[i]] == val) ++j;
} return j;
}
boolean TargetCell(Candidate *TargCand, Partition *Part, int n, struct TracesVars* tv, intLv) { int TCell = -1, TCSize = 1; int i;
VERB_PRINT("TCELL",3,FALSE) if (Part->cells == n) {
tv->finalnumcells = n; returnFALSE;
} if (tv->maxdeg <=2) { returnFALSE;
}
if (Lv < tv->tcellevel) {
tv->tcell = Spine[Lv+1].tgtcell; returnTRUE;
} else { if (Part->cls[0] == n) {
tv->tcell = 0; returnTRUE;
} while (TCell < 0) { for (i = Spine[Lv].tgtcell; i < Spine[Lv].tgtend; i += Part->cls[i]) { if (Part->cls[i] > TCSize) { if (NonSingDeg(TargCand->lab[i], TargCand, Part) > 2) {
TCSize = Part->cls[i];
TCell = i;
}
}
}
Lv--; if ((Lv < 0) && (TCell < 0)) returnFALSE;
}
tv->tcell = TCell; returnTRUE;
}
}
int TargetCellExpPath(Candidate *TargCand, Partition *Part, struct TracesVars* tv) { int Lv, n;
VERB_PRINT("TCEP",3,FALSE)
n = tv->input_graph->nv; if (Part->cells == n) { return 0;
}
boolean TargetCellFirstPath(Candidate *TargCand, Partition *Part, struct TracesVars* tv) { int n, TCell, TCSize, TCell1, TCSize1; int Lv, i, Lev, vtx, vtx_d; int loopstart, loopend;
boolean divided;
VERB_PRINT("TCFP",3,FALSE)
k = tv->permInd; if (j1 == j2) {
quickSort(Neighbs1, j1);
quickSort(Neighbs2, j2); for (i=0; i<j1; i++) {
arg = Cand1->lab[Neighbs1[i]];
val = Cand2->lab[Neighbs2[i]]; if ((Markers[arg] != tv->mark) && (Markers[val] != tv->mark)) {
SETPAIRSAUT(arg, val)
SETPAIRSAUT(val, arg)
Markers[arg] = tv->mark;
Markers[val] = tv->mark;
}
}
}
} returnTRUE;
}
/***************************************************************************** * * * trie_class(t,c) classifies vertices according to weights of their edges * * *
*****************************************************************************/
void trie_class(trie *t, int *count) {
if (t->first_child == NULL) {
WeightsSeq[t->value] = *count; if (t->next_sibling == NULL) (*count)++; return;
} else {
t = t->first_child; while (t) {
trie_class(t,count);
t = t->next_sibling;
}
}
}
trieref = trieroot; for (j=0; j<TheGraph[i].d; j++) {
trieref = trie_make(trieref, wgh1[j], n, tv);
}
trieref = trie_make(trieref, n, n, tv);
trie_make(trieref, i, n, tv);
}
trie_class(trieroot,&ord);
if (t->first_child) {
t = t->first_child; while (t) { if (value != t->value) {
t = t->next_sibling;
} else { break;
}
} return t;
} else { return NULL;
}
}
void trie_dump(trie *t) { if (t->first_child == NULL) return; else {
printf("( ");
t = t->first_child; while (t) {
printf("%d ",t->value);
trie_dump(t);
t = t->next_sibling;
}
printf(") ");
}
}
/***************************************************************************** * * * trie_make(t,v,n,tv) places the value v into the trie t * * *
*****************************************************************************/
struct trie *trie_make(trie *t, int value, int n, struct TracesVars* tv) {
trie *t1;
t1 = t; if (tv->trienext == n) {
tv->trienext = 0;
tv->triepos++;
TrieArray[tv->triepos] = malloc(n*sizeof(trie)); if (TrieArray[tv->triepos] == NULL) {
fprintf(ERRFILE, "\nError, memory not allocated.\n"); exit(1);
}
} if (t->first_child) {
t = t->first_child; if (value < t->value) {
t1->first_child = &TrieArray[tv->triepos][tv->trienext++];
t1->first_child->next_sibling = t;
t1->first_child->first_child = NULL;
t = t1->first_child;
t->value = value; return t;
} while (value > t->value) {
t1 = t; if (t->next_sibling) {
t = t->next_sibling;
} elsebreak;
} if (value == t->value) { return t;
}
t1->next_sibling = &TrieArray[tv->triepos][tv->trienext++];
t1->next_sibling->first_child = t1->next_sibling->next_sibling = NULL; if (t != t1) {
t1->next_sibling->next_sibling = t;
}
t = t1->next_sibling;
} else {
t->first_child = &TrieArray[tv->triepos][tv->trienext++];
t = t->first_child;
t->first_child = t->next_sibling = NULL;
}
t->value = value; return t;
}
struct trie *trie_new(int n, struct TracesVars* tv) {
boolean VerifyCand(Candidate *Cand, int n, int line) { int i, k;
for (i=0; i<n; i++) {
k=Cand->lab[i]; if (Cand->invlab[k] != i) {
printf("Cand->invlab wrong at %d (vtx: %d), line %d\n", i, k, line);
PrintVect(Cand->lab, 0, n, 0);
PrintVect(Cand->invlab, 0, n, 0); returnFALSE;
}
} returnTRUE;
}
boolean VerifyId(int *p, int n) { int i, r;
r = TRUE; for (i=0; i<n; i++) { if (p[i] != i) {
printf("p[%d] = %d\n", i, p[i]);
r = FALSE;
}
} return r;
}
boolean VerifyPart(Partition *Part, int start, int end) { int i,j;
for (i=start; i<end; i+=Part->cls[i]) { if (Part->cls[i] == 0 || i>=end) {
printf("WRONG cls\n"); returnFALSE;
} for (j=0; j<Part->cls[i]; j++) { if (Part->inv[i+j] != i) {
printf("WRONG inv\n"); returnFALSE;
}
}
}
printf("OK\n"); returnTRUE;
}
int VerifyPerm(int *perm, int n,int where) { int i;
/***************************************************************************** * * * WeightCodes(n) transforms the weight w(u,v) of an edge into a new weight * * W(u,v) such that W(a,b) = W(c,d) iff w(a,b) = w(c,d) and w(b,a) = w(d,c). * * *
*****************************************************************************/
void WeightCodes(int n) { int i,j,aux; int sumdegs; int deg, vtx1, vtx2, *ngh1, *ngh2, *wgh1, *wgh2, ord;
/* swap VArray and WArray.weight */ for (i=0; i<sumdegs; i++) {
aux = VArray[i];
VArray[i] = WArray[i].weight;
WArray[i].weight = aux;
}
i = j = 0; do { if (WArray[i].weight == WArray[j].weight) {
j++;
} else {
sortweights(VArray+i,WArray+i,j-i);
i = j;
}
} while (j<sumdegs);
sortweights(VArray+i,WArray+i,j-i);
/* weight class */
ord = 0;
*(WArray[0].ref) = 0; for (i=1; i<sumdegs; i++) { if ((WArray[i].weight != WArray[i-1].weight) || (VArray[i] != VArray[i-1])) {
ord++;
}
*(WArray[i].ref) = ord;
}
boolean TargetCellFirstPathSmall(Candidate *TargCand, Partition *Part, struct TracesVars* tv) { int n, TCell, TCSize, TCell1, TCSize1; int Lv, i, Lev, vtx, vtx_d; int loopstart, loopend;
boolean divided;
n = tv->input_graph->nv; if (Part->cells == n) { return 0;
}
Lev = tv->tolevel_tl;
Lv = tv->tolevel_tl;
TCell = TCell1 = -1;
TCSize = TCSize1 = n;
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 und die Messung sind noch experimentell.