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; unsigned int firstsingcode; unsigned int pathsingcode; unsigned int 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; 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;
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; unsigned long keptcounter; unsigned long levelcounter;
Partition *part; unsigned int 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 */
/* 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) return0;
}
}
} 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) { case1:
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;
void traces_refine_notrace(Candidate *Cand,
int n,
Partition *Part, struct TracesVars* tv, struct TracesInfo *ti) {
int i, j, k, jk, sc, ind0, ind1, ind2, ind3, labi, auxcells;
int value, iend, newcell;
int HitClsInd, SplInd, SplCntInd, CStackInd;
int iend1int, j1int; unsigned int longcode;
int Split = 0;
int Sparse = TRUE;
int *lab, *cls, *InvLab, *SplitCell, *LabCell;
int BigCell, BigCellPos, BigCellSize;
int *nghb; const int variation = 1;
int currentweight, weightstart, weightend, currentcell, currentsize;
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) { case1:
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) */
void traces_refine_maketrie(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; unsigned int longcode;
int Split = 0;
int Sparse = TRUE;
int *lab, *cls, *InvLab, *SplitCell, *LabCell;
int BigCell, BigCellPos, BigCellSize;
int *nghb; const int 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_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) { case1:
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; unsigned int longcode;
int Split = 0;
int Sparse = TRUE;
int *lab, *cls, *InvLab, *SplitCell, *LabCell;
int BigCell, BigCellPos, BigCellSize;
int *nghb; const int 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_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) { case1:
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) return0;
}
}
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) return0;
}
}
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) return0;
}
/* 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 */
if (cls[ind1] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[ind1]);
}
if (cls[newcell] == 1) {
Cand->singcode = MASHCOMM(Cand->singcode, Cand->lab[newcell]);
}
}
} else {
if (TraceCell) { return0;
}
}
} 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) { case1:
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) { return0;
}
}
} 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) { return0;
}
}
} 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) { return0;
}
}
}
}
}
} 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_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) { case1:
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;
}
} return FALSE;
}
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 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) { case0: /* Interrupted refinement: do not add to the list */
tv->stats->interrupted++;
SpineTL->levelcounter++; break; case1 : /* 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; case2 : /* 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) { return FALSE;
}
rn = pn; do {
if (!memcmp(rn->p, p, n*sizeof(int))) { returnTRUE;
}
rn = rn->next;
} while (rn != pn); return FALSE;
}
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) { return0;
}
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) { case0: break;
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) { return FALSE;
}
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) return FALSE;
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) { return FALSE;
}
}
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]);
}
}
}
}
} return1;
} else { return0;
}
}
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;
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)
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);
/* 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) { return0;
}
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.