/* graph to coloring problem translation and solving program */ /* Converts graph and number of colors into a set */ /* of propositional clauses that encode the coloring problem. */ /* Uses a variation of binary search to find the chromatic number. * numColors is not a required command-line input for this program. * Invokes (via system()) a program with this command-line format: * progpath file.cnf numColors cpuMins -encoding temp.outfile * where * progpath is the default or user-supplied filename to execute, * usually a csh script. It must produce correct exit codes. * Primarily, 0=unsat, 1=sat. See invokeSolver() comments. * numColors and -encoding are for progpath to use in making file names * for its solution, log, etc., that are descriptive. * See outoptTbl[]. * temp.outfile is for progpath to use for informational output * that will be read by this program and dumped to stdout. * This program then deletes temp.outfile. */ /* Like tocolor.c but uses array of adjacency lists, as well as matrix */ /* Input format is Dimacs graph c FILE: myciel3.col p edge 5 5 e 1 2 e 1 4 e 2 3 e 3 5 e 4 5 */ #include #include #include #include #include #include #include #include /* The above defines MAXSIG and SIGXCPU, but linux uses (_NSIG - 1) = 63 */ #ifndef MAXSIG # define MAXSIG 63 #endif #include "intlist.h" /* The default parameter to system() will begin with SATDIR/SATPROG. * Use the -S flag to set this path to the satsolver (csh script usually) * at runtime. * These strings may be set with * -DSATDIR='"."' -DSATPROG='"do-chaff-ncol.csh"' * * in the cc command line. Note the quoting carefully. * * The exit codes of SATPROG are returned by system() and interpreted * in this program, so they MUST be controlled in all cases, including * abnormal ends, especially when cpu time is exceeded. * For normal ends, 0 = unsat and 1 = sat. * See the code following the system() invokation for abnormal cases. */ #ifndef SATDIR #define SATDIR "." #endif #ifndef SATPROG #define SATPROG "run-satsolver.csh" #endif FILE* fin; FILE* fout; #define MINARGS 3 #define strEq(x,y) (!strcmp((x),(y))) /* Traditional encoding: node 1 => 1, ..., K; node 2 => K+1, ..., 2k; ... * colors are 0, ..., K-1. */ #define tradVar(node, color, nColors) (1 + (node-1) * nColors + color) /* xor encoding: colors are 0, ..., K-1. L = logColors. nVars = numNodes*L. * node 1 => 1, ..., L; node 2 => L+1, ..., 2L; ... * edge-xor 0 => nVars + 1, ..., nVars + L; * edge-xor 1 => nVars + L+1, ..., nVars + 2L; ... */ #define xNodeVar(node, bit) (1 + (node-1) * logColors + bit) #define xEdgeVar(edge, bit) (nVars + 1 + edge * logColors + bit) void initDisallow(long nColors, long logColors); void processHdr(FILE* fin); void writeHdr(FILE* fout, long totVars, long nClauses); void loadInputGraph(FILE* fin); long sortVertsTmp(long numNodes, intlist adjVertsTmp[], intlist adjVerts[]); long findChromaticNumber(int brkopt); long setupSpecial1(int brkopt); long setupSpecial2(int brkopt); long setupSpecial99(void); long prefixClique(long numSpecial); void processGraph(FILE* fout); void calcColors(long nColors); long searchUpSeqColors(long current, long upper, int brkopt); long searchSeqColors(long lower, long current, long upper, int brkopt); long searchColors(long lower, long upper, int brkopt); long subsearch1(long lower, long mid1, long upper, int ans1, int brkopt); long subsearch2(long lower, long mid2, long upper, int ans2, int brkopt); void greedyColor(long specialNode[], long numSpecial); long lowColor(long i, intlist adjColors[], char taken[]); void updateAdjColors(long i, long iColor, intlist adjColors[]); int testColorable(long nColors, int brkopt); int invokeSolver(char outName[]); void genEdgeConstr(FILE* fout, long i, long adjNode); void genNodeConstr(FILE* fout, long i); void disallow(FILE* fout, long u, long maxColor); long findDenseNode(long numNodes, long rowWidth); void fillSpecial(int brkopt, long startNode, long nColors); long findDenseNode2(long numNodes, long rowWidth); long fillSpecial2(int brkopt, long startNode); long setEffRow(long numNodes, long winnerRow[], long effRow[]); void insert(long base, long vacant, long cand, long candDegree); void insert2(long base, long vacant, long cand, long candScore); long cliqueScore(long k); long setRowScores(long thisRow[], long i, long nColors); long winnerMin(long thisRow[]); long pruneWinner(long thisRow[], long i, long k); long checkClique(long specialNode[], long low, long high); long checkClique4(long numNodes, long rowWidth); int checkItOut; /* 0 to suppress checkClique() and checkClique4 */ char* outoptTbl[7] = { "-cn", "-x", "-s", "-c", "-cn", "-tr", "" }; /* cpu is given in minutes */ #define CPU_LEVELS 3 #define CPU_LEVELS_DEF 5 char cpu[CPU_LEVELS_DEF+1][12]; char cpu5[12] = "5"; char cpu60[12] = "60"; char cpu300[12] = "300"; char cpu1440[12] = "1440"; char cpu7200[12] = "7200"; int cpuLevel; static void prUsage(char* argv[]) { printf("Usage: %s [-Spppp.csh] [-b1 | -b2] [-q] [-pCC | -j | -d | -g] [-tMMMM] " "[-x|-s|-c|-cn|-tr] infile outfile " "[-n nodes arcs] [-b v1 ...]\n", argv[0]); printf("\tFLAGS MUST BE IN ORDER SHOWN--sorry. [ ] denote optional flags.\n"); printf("\t-Spppp.csh means invoke pppp.csh to run your sat solver.\n"); printf("\t-b1 means break symmetry by heuristic 1.\n"); printf("\t-b2 means break symmetry by heuristic 2.\n"); printf("\t-b may not be specified together with -b1 or -b2.\n"); printf("\t-q means print some clique information.\n"); printf("\t-pCC means test CC colors only, at max cpu level, no search.\n"); printf("\t-j means jump (binary search) on numColors;\n"); printf("\t-d means seq. search down numColors; default is sequential up.\n"); printf("\t-g Only verify formula is sat with greedy coloring and -tr.\n"); printf("\t-tMMMM means allow MMMM minutes as max cpu level (default %s).\n", cpu[CPU_LEVELS]); printf("\t-x|-s|-c|-cn|-tr encoding choices. c: circuit, cn: circuit-new\n"); printf("\t tr: traditional, s,x: nonCNF. " "NOTE: c = xg and cn = xe in write-ups.\n"); printf("\tinfile is the graph (.col) file.\n"); printf("\toutfile is the encoded CNF (.cnf) file. Results are on stdout.\n"); printf("\tarcs is number of DIRECTED edges " "(usually double value on \"edge\" line\n"); printf("\t of infile, and input has undirected edges). Not really needed.\n"); printf("\t If arcs = value on \"edge\" line, input has directed edges\n"); printf("\t\"-b v1 ...\" node list upon which to limit colors: " "0, 0-1, 0-2, ...\n"); return; } long numColors, logColors, nVars, rndColors, multpl, chi; long singleNumColors; long clauseCnt, edgeNum; long* specialNode; long numSpecial, numSpecialIn; long effSpecial; /* min(numSpecial, numColors - 1) */ long* clsNeeded; /* clsNeeded[i] = clauses needed to enforce * color <= i in xg, xe encodings. i <= numColors-1. * This is the number of 0-bits in i. */ char (*bit)[32]; /* pointer to (i.e., array of) array of 32 chars. * bit[i][j] = j-th-bit of i <= numColors-1, lsb = 0. */ long forcedCnt, disallowCnt; long* degree; long* degree2; /* sum degrees of adjacent nodes */ long graphDegree; long* winnerRow; /* max over i of thisRow */ long* thisRow; /* (how many triangles with i,j) * 2 + 1 */ long* effRow; /* j's having nonzero score after pruning, heuristic 2 */ long effDegree; /* entries in effRow; they begin at [0] */ long bigClique; /* effDegree+1 if effRow[] + winner make clique, else 0 */ char* adjMat; intlist* adjVerts; long* color0; /* colors assigned (>= 1) by greedyColor(). */ long* colorStatus; /* Remember which ncolors were solved or abandoned. */ long greedyColorNum; /* number of colors used by greedyColor(). */ long rowWidth; long numNodes, numArcs, totalEdges, numArcsArg; int outopt; int brkopt; long searchType; /* 0 = seq.up, 1 = seq.down, 2 = binary. */ char argString[1000]; char inName[256], outName[256]; char dir[100] = SATDIR ; char prog[100] = SATPROG ; char progpath[204]; long finalRange[2]; int my_pid; char my_host[32]; int main(int argc, char* argv[]) { long i, j, k; long totVars, nClauses; int curArg; long numNodesArg; long clqSize; multpl = 1; outopt = 4; brkopt = 0; checkItOut = 0; singleNumColors = 0; searchType = 0; sprintf(progpath, "%s/%s", dir, prog); strcpy(cpu[1], cpu5); strcpy(cpu[2], cpu60); strcpy(cpu[3], cpu300); strcpy(cpu[4], cpu1440); strcpy(cpu[5], cpu7200); cpuLevel = 1; strcpy(cpu[0], cpu[1]); setbuf(stdout,NULL); curArg = 1; if ((argc-curArg) < MINARGS-1) { prUsage(argv); exit(argc-1); } if (argv[curArg][0] == '-' && argv[curArg][1] == 'S') { strcpy(progpath, argv[curArg]+2); curArg ++; } if (strEq(argv[curArg], "-b1")) { brkopt = 1; /* use heuristic 1 to break symmetry */ curArg ++; } else if (strEq(argv[curArg], "-b2")) { brkopt = 2; /* use heuristic 2 to break symmetry */ curArg ++; } if (strEq(argv[curArg], "-q")) { checkItOut = 1; /* print some clique info */ curArg ++; } if (argv[curArg][0] == '-' && argv[curArg][1] == 'p') { singleNumColors = atoi(argv[curArg]+2); curArg ++; } else if (strEq(argv[curArg], "-d")) { searchType = 1; curArg ++; } else if (strEq(argv[curArg], "-g")) { searchType = -1; curArg ++; } else if (strEq(argv[curArg], "-j")) { searchType = 2; curArg ++; } if (argv[curArg][0] == '-' && argv[curArg][1] == 't' && argv[curArg][2] != 'r') { sprintf(cpu[CPU_LEVELS], "%d", atoi(argv[curArg]+2)); curArg ++; } if (strEq(argv[curArg], "-x")) { outopt = 1; /* xors, tersest */ if (searchType == -1) { printf("CANNOT use %s with -g; %s cancelled.\n", argv[curArg], argv[curArg]); outopt = 5; } curArg ++; } else if (strEq(argv[curArg], "-s")) { outopt = 2; /* and-or, n*logColors vars */ if (searchType == -1) { printf("CANNOT use %s with -g; %s cancelled.\n", argv[curArg], argv[curArg]); outopt = 5; } curArg ++; } else if (strEq(argv[curArg], "-c")) { outopt = 3; /* cnf, n*logColors vars, e*2^(logColors) clauses */ if (searchType == -1) { printf("CANNOT use %s with -g; %s cancelled.\n", argv[curArg], argv[curArg]); outopt = 5; } curArg ++; } else if (strEq(argv[curArg], "-cn")) { outopt = 4; /* cnf, new vars to stand for or's, xor's */ if (searchType == -1) { printf("CANNOT use %s with -g; %s cancelled.\n", argv[curArg], argv[curArg]); outopt = 5; } curArg ++; } else if (strEq(argv[curArg], "-tr")) { outopt = 5; /* cnf, tradtional encoding */ curArg ++; } if ((argc-curArg) < MINARGS-1) { prUsage(argv); exit(argc-1); } strcpy(inName, argv[curArg]); curArg ++; strcpy(outName, argv[curArg]); curArg ++; /* make sure outName is writable */ fout = fopen(outName, "w"); if (fout == NULL) { printf("fopen failed for output %s\n", outName); exit(3); } strcpy(argString, "c"); for (i = 0; i < argc; i++) { strcat(argString, " "); strcat(argString, argv[i]); } fprintf(fout, argString); i = fprintf(fout, "\n"); if (i != 1) { printf("fprintf failed for output %s\n", outName); exit(3); } i = fclose(fout); if (i) { printf("fclose failed for output %s\n", outName); exit(3); } if (strEq(inName, "-")) fin = stdin; else fin = fopen(inName, "r"); if (fin == NULL) { printf("fopen failed for input %s\n", inName); exit(3); } my_pid = getpid(); gethostname(my_host, 32); my_host[16] = 0; /* just need a uniquifier for file names. */ if (strchr(my_host, '.') != NULL) *strchr(my_host, '.') = 0; processHdr(fin); specialNode = calloc(numNodes + 1, sizeof(long)); /* confirm sizeof(*bit)==32 printf("sizeof(*bit) = %d\n", sizeof(*bit));*/ bit = calloc(numNodes, sizeof(*bit)); clsNeeded = calloc(numNodes, sizeof(long)); if (curArg < argc) { if (strEq(argv[curArg], "-n")) { /* check nodes and arcs on command line with those in file. */ curArg ++; if ((argc-curArg) < 3) { prUsage(argv); exit(1); } /* Does next arg confirm numNodes? */ sscanf(argv[curArg], "%ld", &numNodesArg); if (numNodesArg != numNodes) { printf("numNodes on command line and in file disagree: "); printf("%ld vs. %ld\n", numNodesArg, numNodes); exit(2); } curArg ++; /* Does next arg confirm numArcs? If it's 2*numArcs, * assume input has directed edges. */ sscanf(argv[curArg], "%ld", &numArcsArg); if (numArcsArg == numArcs) { /* This is 2 * totalEdges */ } else if (numArcsArg == totalEdges) { totalEdges = numArcsArg / 2; numArcs = numArcsArg; } else { /* assume input has undirected edges */ printf("WARNING: "); printf("numArcs on command line and in file disagree: "); printf("%ld vs. %ld\n", numArcsArg, numArcs); numArcsArg = totalEdges; } curArg ++; } } if (curArg < argc) { if (strEq(argv[curArg], "-b")) { if (brkopt != 0) { printf("Cannot specify -b and -b%d\n", brkopt); prUsage(argv); exit(1); } curArg ++; brkopt = 99; /* argv[curArg .. argc-1] are nodes to receive distinct forced colors */ numSpecialIn = argc - curArg; if (numSpecialIn <= 0) { prUsage(argv); exit(1); } numSpecial = numSpecialIn; for (i = 0; i < numSpecialIn; i++) { specialNode[i] = atoi(argv[i + curArg]); } } } loadInputGraph(fin); fclose(fin); chi = findChromaticNumber(brkopt); if (chi > 0) { printf("Chromatic Number is %ld\n", chi); } else { printf("findChromaticNumber error code %ld\n", chi); printf(" finalRange = [%ld, %ld]\n", finalRange[0], finalRange[1]); } return 0; } void processHdr(FILE* fin) { char buf[1024]; char* retn; long pnodes, pedges; /* read next noncomment */ buf[0] = 0; retn = fgets(buf, 1024, fin); while (buf[0] == 'c') {buf[0] = 0; retn = fgets(buf, 1024, fin);} /* process p line */ if (buf[0] != 'p') exit(31); sscanf(buf, "%*s %*s %ld %ld", &pnodes, &pedges); numNodes = pnodes; totalEdges = pedges; numArcs = totalEdges * 2; return; } void writeHdr(FILE* fout, long totVars, long nClauses) { fprintf(fout, argString); fprintf(fout,"\n"); fprintf(fout,"c "); if (outopt == 1 || outopt == 2 || outopt == 3 || outopt == 4) fprintf(fout,"%ld bits ", logColors); fprintf(fout,"(%ld colors).\n", numColors); if (outopt == 1) { fprintf(fout,"p satx "); fprintf(fout,"%ld\n", totVars); fprintf(fout,"(*(\n"); } else if (outopt == 2) { fprintf(fout,"p sat "); fprintf(fout,"%ld\n", totVars); fprintf(fout,"(*(\n"); } else if (outopt == 3 || outopt == 4 || outopt == 5) { fprintf(fout,"p cnf "); fprintf(fout,"%ld %ld\n", totVars, nClauses); } return; } /* allocate and initialize degree[] and adjVerts[] and adjMat[]. * allocate degree2[] also. */ void loadInputGraph(FILE* fin) { long i, j, k, dups; long node, numAdj, adjNode; char buf[1024]; char* retn; intlist* adjVertsTmp; rowWidth = numNodes + 1; degree = calloc(rowWidth, sizeof(long)); degree2 = calloc(rowWidth, sizeof(long)); winnerRow = calloc(rowWidth, sizeof(long)); thisRow = calloc(rowWidth, sizeof(long)); effRow = calloc(rowWidth, sizeof(long)); adjVertsTmp = calloc(rowWidth, sizeof(intlist)); adjVerts = calloc(rowWidth, sizeof(intlist)); if (adjVerts == NULL) exit(33); /* read next noncomment */ buf[0] = 0; retn = fgets(buf, 1024, fin); while (buf[0] == 'c') {buf[0] = 0; retn = fgets(buf, 1024, fin);} while(retn) { long nf, u, v, loc; /* should be an e line */ nf = sscanf(buf, "e %ld %ld", &u, &v); if (nf != 2) exit(35); if (u < 1 || u > numNodes) exit(36); if (v < 1 || v > numNodes) exit(36); if (u != v) { /* from u to v */ adjVertsTmp[u] = IL_cons(v, adjVertsTmp[u]); degree[u] ++; if (numArcs != numArcsArg) { /* input gives undirected edges */ adjVertsTmp[v] = IL_cons(u, adjVertsTmp[v]); degree[v] ++; } } /* read next noncomment */ buf[0] = 0; retn = fgets(buf, 1024, fin); while (buf[0] == 'c') {buf[0] = 0; retn = fgets(buf, 1024, fin);} } /* If adjMat is built as edges are loaded, as well as adjVertsTmp, * then duplicates can be eliminated on the fly. * However, it might be better to find them with sortVertsTmp() * to help detect bad inputs. */ dups = sortVertsTmp(numNodes, adjVertsTmp, adjVerts); if (dups > 0) { long changeCntr; printf("WARNING: %ld duplicate (directed) edges eliminated.\n", dups); changeCntr = 0; for (i = 1; i <= numNodes; i++) { long len = IL_length(adjVerts[i]); if (len != degree[i]) { if (changeCntr < 20) printf("DEGREE CHANGED for %ld: %ld -> %ld\n", i, degree[i], len); else if (changeCntr == 20) printf("ADD'L DEGREE CHANGES SUPPRESSED\n"); changeCntr ++; degree[i] = len; } } printf("WARNING: %ld nodes changed degree..\n\n", changeCntr); } free(adjVertsTmp); /* Can build adjMat now and set graphDegree. */ adjMat = calloc(rowWidth*rowWidth, sizeof(char)); if (adjMat == NULL) exit(33); graphDegree = 0; for (i = 1; i <= numNodes; i++) { intlist rem; long offseti = rowWidth * i; long offsetj; if (graphDegree < degree[i]) graphDegree = degree[i]; ; for (rem = adjVerts[i]; rem != IL_EMPTYLIST; rem = IL_REST(rem)) { j = IL_FIRST(rem); offsetj = rowWidth * j; adjMat[offseti + j] = 1; adjMat[offsetj + i] = 1; } } return; } /* Destroy lists in adjVertsTmp while creating sorted lists in adjVerts. * Precondition: adjVerts[i] is empty for all i. * Eliminate any duplicate edges in the process. * This actually creates the transpose graph, but due to symmetry * it is the same graph. */ long sortVertsTmp(long numNodes, intlist adjVertsTmp[], intlist adjVerts[]) { long i, j, k, dups, trueArcs, trueEdges; intlist rem, lnode, jAdj; dups = 0; trueArcs = 0; trueEdges = 0; for (i = numNodes; i >= 1; i --) { rem = adjVertsTmp[i]; while (rem != IL_EMPTYLIST) { lnode = rem; /* lnode will be destructively modified. */ j = IL_FIRST(rem); rem = IL_REST(rem); jAdj = adjVerts[j]; if (jAdj != IL_EMPTYLIST) { k = IL_FIRST(jAdj); if (i == k) { /* discard lnode, dont bother with free */ dups ++; continue; } } /* Put i on j's list, recycling lnode; no cons(). */ IL_REST(lnode) = jAdj; IL_FIRST(lnode) = i; adjVerts[j] = lnode; trueArcs ++; if (i > j) { trueEdges ++; } } } if (trueEdges != totalEdges) { printf("WARNING: totalEdges %ld in p-line not equal trueEdges %ld. ", totalEdges, trueEdges); printf("Using trueEdges\n"); totalEdges = trueEdges; } if (trueArcs != 2 * trueEdges) { printf("ERROR: graph is not symmetric: %ld upward, %ld downward. ", trueEdges, trueArcs - trueEdges); printf("Using upward\n"); } return dups; } long findChromaticNumber(int brkopt) { long clqSize; long i, j, k; long lower, upper, lower0, upper0, upper1, chi; int clqAns; if (brkopt == 99) bigClique = setupSpecial99(); else if (brkopt == 1) bigClique = setupSpecial1(brkopt); else if (brkopt == 2) bigClique = setupSpecial2(brkopt); else bigClique = 1; greedyColor(specialNode, numSpecial); printf("greedyColorNum = %ld\n", greedyColorNum); if (searchType == -1) { singleNumColors = greedyColorNum; } if (brkopt > 0 && brkopt != 99) { long target = singleNumColors > numSpecial ? numSpecial : singleNumColors > 1 ? singleNumColors : greedyColorNum > numSpecial ? numSpecial : greedyColorNum; /* This returns 0 without doing any work unless "-q" flag was used. */ clqSize = checkClique(specialNode, 0, target); if (clqSize > 0) { printf("Selected special nodes plus %ld form %ld-clique\n", clqSize, target - 0 + 1); } else if (clqSize < 0) { printf("Selected special nodes form %ld-clique\n", -clqSize); } else if (target > 0 && checkItOut) { printf("Selected special nodes do not form a %ld-clique\n", target - 0); } } printf("\n"); /* Initialize to impossible values */ finalRange[0] = 0; finalRange[1] = numNodes + 1; lower0 = bigClique; upper0 = greedyColorNum; if (singleNumColors <= 1 && searchType == 2) { cpuLevel = 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); /* As an heuristic, see if bigClique is enough colors first. */ clqAns = testColorable(bigClique, brkopt); if (clqAns > 0) { chi = bigClique; return chi; } else if (clqAns == 0) { lower = lower0 + 1; } else if (clqAns == - SIGXCPU ) { printf("WARNING: " "test with cliquesize %ld exceeded %s cpu mins\n", bigClique, cpu[0]); lower = lower0; } else if (clqAns < 0) { /* failed -- do something better later. */ printf("WARNING: test with cliquesize %ld failed, continuing\n", bigClique); lower = lower0; } upper = upper0; cpuLevel = 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(lower, upper, brkopt); } else if (singleNumColors <= 1 && searchType == 0) { /* DEFAULT: Search upward from clique lower bound. */ cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); /* Expand the bounds so that the sat solver confirms the computed * bounds. The confirmations should be fairly inexpensive. * If the upper0 bound cannot be confirmed, continue upward 2 levels * until a value IS confirmed to be colorable or the program * fails for a reason other than exceeding CPU. */ lower = lower0 - 1; upper = upper0 + 2; chi = searchUpSeqColors(lower, upper, brkopt); if (finalRange[0] > upper0) { /* solver error or bad fmla or greedyNum wrong */ printf("ERROR: %ld >= greedyNum; fmla found unsat\n", finalRange[0] - 1); } } else if (singleNumColors <= 1 && searchType == 1) { cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); /* Expand the bounds so that the sat solver confirms the computed * bounds. The confirmations should be fairly inexpensive. * If the upper bound cannot be confirmed, continue upward * until a value IS confirmed to be colorable or the program * fails for a reason other than exceeding CPU. * We expect the while loop always to break, never to exit. */ upper1 = upper0; upper = finalRange[1]; while (upper1 < finalRange[1]) { int ans; printf("confirm upper bound %ld starting\n", upper1); ans = testColorable(upper1, brkopt); if (ans > 0) { upper = upper1; break; } else if (ans == 0) { /* solver error or bad fmla or greedyNum wrong */ printf("ERROR: %ld >= greedyNum; fmla found unsat\n", upper1); upper = finalRange[1]; break; } else if (ans != -SIGXCPU) { /* Give up on confirming any upper bound */ upper = finalRange[1]; break; } /* Weaken the upper bound and hope it gets easier. */ printf("confirm upper bound %ld exceeded CPU\n", upper1); upper1 ++; } lower = lower0 - 1; chi = searchSeqColors(lower, upper0, upper, brkopt); } else { int ans; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); /* Test singleNumColors only. */ if (searchType == -1) printf("Verify greedy coloring with %ld colors only\n", singleNumColors); else printf("Test %ld colors only\n", singleNumColors); ans = testColorable(singleNumColors, brkopt); if (ans > 0) { return singleNumColors; } else if (ans == 0) { printf("NOT COLORABLE with: %ld\n", singleNumColors); return finalRange[1]; } else if (ans == -SIGXCPU) { printf("EXCEEDED CPU with: %ld\n", singleNumColors); return ans; } else { printf("TERMINATED ON SIGNAL with: %ld\n", singleNumColors); return ans; } } return chi; } /* Precondition: graph can be colored with "upper" and cannot be colored * with "lower" - 1 colors. * Objective: Return the smallest number of colors that is sufficient, * if that value is found; * return negative number if that value was not found. * Use -j to select this routine. * * Earlier attempts to use varying time budgets are now overridden; * cpu[CPU_LEVELS] is always used. User may control that with -tMMMM. */ long searchColors(long lower, long upper, int brkopt) { long mid, mid1, mid2, chi; int ans, ans1, ans2; if (lower >= upper) { chi = upper; return chi; } mid = sqrt(lower * upper + 0.0) + 0.49; if (upper - lower == 1) { /* Last test, so use maximum cpu level. */ cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); mid = (upper + mid) / 2; } printf("searchColors lower mid upper = %ld %ld %ld\n", lower, mid, upper); ans = testColorable(mid, brkopt); if (ans > 0) { if (cpuLevel > 1) cpuLevel --; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(lower, mid, brkopt); } else if (ans == 0) { /* New range is probably easier. */ cpuLevel = 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(mid+1, upper, brkopt); } else if (ans == - SIGXCPU) { if (mid < upper -1) { mid1 = sqrt(mid * upper + 0.0) + 0.49; ans1 = testColorable(mid1, brkopt); chi = subsearch1(lower, mid1, upper, ans1, brkopt); } else if (mid > lower) { mid1 = sqrt(lower * mid + 0.0) + 0.49; ans1 = testColorable(mid1, brkopt); chi = subsearch1(lower, mid1, upper, ans1, brkopt); } else if (cpuLevel < CPU_LEVELS) { /* Try original range with bigger CPU budget */ cpuLevel ++; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(lower, upper, brkopt); } } else { /* ans < 0 && ans != - SIGXCPU */ /* Presumably ran out of memory, not time. Increasing * colors will probably make memory problem worse, and * increasing the time with same number of colors will not help. */ if (mid > lower) { cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); mid2 = sqrt(lower * mid + 0.0) + 0.49; ans2 = testColorable(mid2, brkopt); chi = subsearch2(lower, mid2, upper, ans2, brkopt); } else { /* failed -- nothing else to try. */ finalRange[0] = lower; finalRange[1] = upper; chi = ans; } } return chi; } long subsearch1(long lower, long mid1, long upper, int ans1, int brkopt) { long chi; if (ans1 == 1) { chi = searchColors(lower, mid1, brkopt); } else if (ans1 == 0) { /* New range is probably easier. */ cpuLevel = 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(mid1+1, upper, brkopt); } else if (ans1 == - SIGXCPU && cpuLevel < CPU_LEVELS) { /* Try original range with bigger CPU budget */ cpuLevel ++; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(lower, upper, brkopt); } else if (ans1 == - SIGXCPU) { /* give up */ chi = ans1; } else if (cpuLevel < CPU_LEVELS) { /* Try original range with bigger CPU budget */ cpuLevel ++; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(lower, upper, brkopt); } else { /* give up */ chi = ans1; } return chi; } long subsearch2(long lower, long mid2, long upper, int ans2, int brkopt) { long chi; if (ans2 == 1) { chi = searchColors(lower, mid2, brkopt); } else if (ans2 == 0) { /* New range is probably easier. */ cpuLevel = 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); chi = searchColors(mid2+1, upper, brkopt); } else if (ans2 == - SIGXCPU) { /* give up */ chi = ans2; } else { /* give up */ chi = ans2; } return chi; } /* Precondition: graph can be colored with "upper" and cannot be colored * or failed with fewer than "current" colors. * "current" - 1 is the last (largest) number of colors tested. * If "current" > "upper", the test with "current" - 1 failed. * * Objective: Return the smallest number of colors that is sufficient, * if that value is found; * return negative number if that value was not found. * The negative number is - (numNodes + 9999) if there is nothing left * to try; * otherwise, the negative number is the most recent negative return * from testColorable(), which is passed through from invokeSolver(). */ long searchUpSeqColors(long current, long upper, int brkopt) { long chi; int ans, ans2; if (current > upper) { /* failed -- nothing else to try. Return impossible value */ chi = - (numNodes + 9999); return chi; } cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); printf("searchUpSeqColors current upper = %ld %ld\n", current, upper); ans = testColorable(current, brkopt); if (ans > 0) { chi = current; } else if (ans == 0) { chi = searchUpSeqColors(current+1, upper, brkopt); } else if (ans != -SIGXCPU) { /* Give up on finding upper bound -- prob. out of memory. */ chi = ans; } else { /* ans == -SIGXCPU. Doesnt matter if later unsat is found. */ ans2 = searchUpSeqColors(current+1, upper, brkopt); if (ans2 < 0 || current < finalRange[0]) chi = ans2; else chi = ans; } return chi; } /* Precondition: graph can be colored with "upper" and cannot be colored * with "lower" - 1 colors. * "current" is the last (smallest) number of colors tested. * If "current" == "upper" that number is colorable; otherwise, * if "current" < "lower", "current" colors is NOT enough; otherwise, * the test with "current" failed. * * Objective: Return the smallest number of colors that is sufficient, * if that value is found, i.e., gap between lower and upper = 0; * return negative number if that value was not found. * The negative number is - (numNodes + 9999) if there is nothing left * to try but the gap between lower and upper did not shrink to 0; * otherwise the negative number is the most recent negative return * from testColorable(), which is passed through from invokeSolver(). * * This procedure goes from high numbers to low, but there are pure "bulk" * difficulties with high numbers, often, so searchUpSeqColors() is the * default. Use -d to select this routine. */ long searchSeqColors(long lower, long current, long upper, int brkopt) { long mid, chi; int ans; if (lower >= upper) { chi = upper; return chi; } if (lower > current) { /* failed -- nothing else to try. Return impossible value */ chi = - (numNodes + 9999); return chi; } mid = current - 1; cpuLevel = CPU_LEVELS; strcpy(cpu[0], cpu[cpuLevel]); printf("searchSeqColors lower mid upper = %ld %ld %ld\n", lower, mid, upper); ans = testColorable(mid, brkopt); if (ans > 0) { chi = searchSeqColors(lower, mid, mid, brkopt); } else if (ans == 0) { chi = searchSeqColors(mid+1, mid, upper, brkopt); } else if (mid <= lower) { chi = ans; } else { chi = searchSeqColors(lower, mid, upper, brkopt); } if (chi == - (numNodes + 9999) && ans < 0) chi = ans; return chi; } /* Objective: Return 1 if graph can be colored with "nColors"; * return 0 if graph cannot be colored with "nColors"; * return negative number if the test aborted or exceeded resources. * This negative number is whatever invokeSolver() returned. * * Also update finalRange[] if the result narrows this range. * * Also update colorStatus[nColors] if the result is 0 or 1. * * If colorStatus[nColors] >= 0 upon entry, simply return that value. * This permits positive codes > 1 to mark nColors values that are * considered hopeless to solve, but testColorable() doesn't decide this. */ int testColorable(long nColors, int brkopt) { int ans; long i, j, k; long totVars, nClauses; numColors = nColors; /* for subroutines where this is not a param. */ if (searchType == -1) effSpecial = 0; else if (numSpecial < numColors) effSpecial = numSpecial; else effSpecial = numColors - 1; if (colorStatus[nColors] >= 0) return colorStatus[nColors]; calcColors(nColors); initDisallow(nColors, logColors); clauseCnt = 0; nVars = logColors * multpl * numNodes; /* old forcedCnt = effSpecial*logColors; * old disallowCnt = (rndColors - numColors). */ forcedCnt = 0; for (i = 0; i < effSpecial; i ++) forcedCnt += clsNeeded[i]; disallowCnt = clsNeeded[nColors-1]; if (outopt == 1 || outopt == 2) { totVars = nVars; nClauses = rndColors * totalEdges + /* constraints */ forcedCnt + /* forced colors */ disallowCnt*(numNodes - effSpecial); /* forbidden clrs */ } else if (outopt == 3) { /* xg encoding */ totVars = nVars; nClauses = nColors * totalEdges + /* constraints */ forcedCnt + /* forced colors */ disallowCnt*(numNodes - effSpecial); /* forbidden clrs */ } else if (outopt == 4) { /* xe encoding */ totVars = nVars + logColors * totalEdges; nClauses = (1 + 4*logColors) * totalEdges + /* constraints */ forcedCnt + /* forced colors */ disallowCnt*(numNodes - effSpecial); /* forbidden clrs */ } else if (outopt == 5) { /* traditional */ totVars = nVars = numNodes * nColors; nClauses = numNodes + nColors * totalEdges + /* constraints */ effSpecial*0 + /* forced colors */ 0; /* forbidden clrs */ if (searchType == -1) nClauses += numNodes; /* forced greedy colors */ } else { /* traditional, but abort if debugging */ totVars = nVars = numNodes * nColors; nClauses = numNodes + nColors * totalEdges + /* constraints */ effSpecial*0 + /* forced colors */ 0; /* forbidden clrs */ assert(0); } fout = fopen(outName, "w"); writeHdr(fout, totVars, nClauses); if (searchType == -1) { /* Force the greedy colors to be used. effSpecial = 0 in this case. */ for (i = 1; i <= numNodes; i++) { long color = color0[i] - 1; if (outopt == 5) { long var = tradVar(i, color, nColors); fprintf(fout,"%ld ", var); fprintf(fout,"0\n"); clauseCnt ++; } } } for (i = 0; i < effSpecial; i++) { long color = i; long fnode = specialNode[i]; if (outopt == 1 || outopt == 2 || outopt == 3 || outopt == 4) { disallow(fout, fnode, color); } else if (outopt == 5) { for (k = 0; k <= color; k++) { long var = tradVar(fnode, k, nColors); fprintf(fout,"%ld ", var); } fprintf(fout,"0\n"); clauseCnt ++; } } processGraph(fout); if (outopt == 1 || outopt == 2) fprintf(fout,"))\n"); i = fclose(fout); if (i) { printf("fclose failed for output %s, errno = %d\n", outName, errno); perror("testColorable"); exit(3); } printf(" \n cnf done, edges = %ld, total vars = %ld, clauseCnt = %ld\n", edgeNum, totVars, clauseCnt); ans = invokeSolver(outName); if (ans == 1) { colorStatus[nColors] = ans; if (nColors < finalRange[1]) finalRange[1] = nColors; } else if (ans == 0) { colorStatus[nColors] = ans; if (nColors >= finalRange[0]) finalRange[0] = nColors + 1; } return ans; } /* these #defines are copied from sys/wait.h on solaris */ #define WIFEXITED(stat) ((int)((stat)&0xFF) == 0) #define WIFSIGNALED(stat) ((int)((stat)&0xFF) > 0 && \ (int)((stat)&0xFF00) == 0) #define WIFSTOPPED(stat) ((int)((stat)&0xFF) == 0177 && \ (int)((stat)&0xFF00) != 0) #define WEXITSTATUS(stat) ((int)(((stat)>>8)&0xFF)) #define WTERMSIG(stat) ((int)((stat)&0x7F)) #define WSTOPSIG(stat) ((int)(((stat)>>8)&0xFF)) /* shsig returns non-zero if the sh invoked by system() received a signal * and exited due to that signal (unsure about "-STOP" signal). */ int shsig(int stat) {return WTERMSIG(stat);} /* shstatus returns exit status of the sh invoked by system(), which * is the exit status of the command passed to system(), normally. * It is limited to 8 bits, so values 128-255 are ambiguous on sign. * However, if the command terminated due to a signal S sent to the command, * then sh returns (128+S). * It is unlikely the command will receive such a signal except by * explicit user action with "kill -signal pid" because the command is * usually a shell script itself. * It is unclear what happens if sh invokes csh, csh invokes pgm, and * pgm receives a signal such as cpu-time-exceeded or segv, etc. */ int shstatus(int stat) { int x = WEXITSTATUS(stat); return x <= 128+MAXSIG? x : x | 0xFFFFFF00; } int cmdsig(int stat) { int x = WEXITSTATUS(stat); return x < 128? 0 : x > 128+MAXSIG? 0 : x - 128; } /* Invoke the sat solver and interpret high-byte of the return code as follows: * 1 = sat return 1 * 0 = unsat return 0 * 128+SIG = cmd terminated on SIG return -SIG * 256-X = cmd exit status was -X return -X * To resolve ambiguity between -SIG and -X, assume the only value of X is 1, * as SIGHUP = 1 and is not expected to occur. * The normal nonzero value of SIG is SIGXCPU. */ int invokeSolver(char outName[]) { int ans, retn; char cmd[1000]; char invokeLog[100]; FILE* fpInvoke; int invokeCh; sprintf(invokeLog, "invoke%s-%s-%d.log", outoptTbl[outopt], my_host, my_pid); sprintf(cmd, "%s %s %ld %s %s> %s 2>&1", progpath, outName, numColors, cpu[0], outoptTbl[outopt], invokeLog); fprintf(stdout, "system(%s)\n", cmd); errno = 0; retn = system(cmd); fprintf(stdout, "return = 0x%04x\n", retn); /* Pass through output of system() and rm its file */ fprintf(stdout, "===== %s =====:\n", invokeLog); fpInvoke = fopen(invokeLog, "r"); invokeCh = fgetc(fpInvoke); while (invokeCh != EOF) { putc(invokeCh, stdout); invokeCh = fgetc(fpInvoke); } fprintf(stdout, "\n"); fflush(stdout); /* Try to ensure the output isn't lost */ fclose(fpInvoke); unlink(invokeLog); if (retn < 0) { fprintf(stdout, "return,errno = %d,%d\n", retn, errno); perror("invokeSolver"); ans = retn; } else if (errno > 0) { fprintf(stdout, "return,errno = %d,%d\n", retn, errno); perror("invokeSolver"); ans = -errno; } else if (errno < 0) { fprintf(stdout, "return,errno = %d,%d\n", retn, errno); perror("invokeSolver"); ans = errno; } else if (shsig(retn) != 0) { fprintf(stdout, "shstatus = 0x%02x\n", shstatus(retn)); fprintf(stdout, "shsig = 0x%02x\n", shsig(retn)); fprintf(stdout, "cmdsig = 0x%02x\n", cmdsig(retn)); ans = - shsig(retn); } else if (cmdsig(retn) != 0) { fprintf(stdout, "shstatus = 0x%02x\n", shstatus(retn)); fprintf(stdout, "shsig = 0x%02x\n", shsig(retn)); fprintf(stdout, "cmdsig = 0x%02x\n", cmdsig(retn)); ans = - cmdsig(retn); } else { ans = shstatus(retn); } return ans; } long setupSpecial99(void) { long clqSize; if (checkItOut) { /* Check whether all input special nodes form a clique, * possibly including one additional node. */ clqSize = checkClique(specialNode, 0, numSpecialIn); if (clqSize > 0) { printf("Input special nodes plus %ld form %ld-clique\n", clqSize, numSpecialIn - 0 + 1); } else if (clqSize < 0) { printf("Input special nodes form %ld-clique\n", -clqSize); } else { printf("Input special nodes do not form a %ld-clique\n", numSpecialIn - 0); } } /* Find prefix of input special nodes that does form a clique. */ clqSize = prefixClique(numSpecialIn); return clqSize; } long setupSpecial1(int brkopt) { long clqSize, i, j, k; long winner = findDenseNode(numNodes, rowWidth); numColors = degree[winner] + 2; printf("Adding specialNodes:"); numSpecial = 0; fillSpecial(brkopt, winner, degree[winner] + 2); printf("\nFinal numSpecial: %ld\n", numSpecial); /* now numSpecial might have increased, usually to degree[winner] + 1. * specialNode[0] = winner, specialNode[1 .. numSpecial-1] = * neighbors of winner, ranked by their degree, high to low. */ /* Find prefix of specialNode[] that does form a clique. */ clqSize = prefixClique(numSpecial); return clqSize; } long setupSpecial2(int brkopt) { long clqSize, i, j, k; long winner = findDenseNode2(numNodes, rowWidth); printf("Adding specialNodes:"); clqSize = fillSpecial2(brkopt, winner); printf("\nFinal numSpecial: %ld\n", numSpecial); /* now numSpecial might have increased, usually to degree[winner] + 1. * specialNode[0] = winner, specialNode[1 .. numSpecial-1] = * neighbors of winner, ranked by their score, high to low. */ return clqSize; } long prefixClique(long numSpecial) { long i = specialNode[0]; long offseti = rowWidth * i; long j, k, m, effDegree, effMax, preClique; intlist remi, remj; long thisColScore, iScore; /* Find prefix of specialNode[0 .. numSpecial-1] that forms a clique. */ iScore = 0; for (j = 1; j <= numNodes; j++) thisRow[j] = 0; for (m = 1; m < numSpecial; m++) { j = specialNode[m]; thisColScore = 0; if (adjMat[offseti + j]) thisColScore ++; /* for Adj[i][j] */ for (remj=adjVerts[j]; remj != IL_EMPTYLIST; remj = IL_REST(remj)) { k = IL_FIRST(remj); if (adjMat[offseti + k]) thisColScore += 2; } thisRow[j] = thisColScore; iScore += thisColScore; } effDegree = numSpecial-1; while (effDegree > 0) { effMax = cliqueScore(effDegree + 1); /* stop pruning if a clique has been found */ if (iScore == effMax) break; k = specialNode[effDegree]; iScore -= pruneWinner(thisRow, i, k); effDegree --; } if (iScore == cliqueScore(effDegree + 1)) { preClique = effDegree + 1; printf("Found %ld-clique: %ld (winner)", preClique, i); /* enumerate the rest of the clique */ for (j = 1; j <= effDegree; j++) printf("% ld", specialNode[j]); printf("\n"); } else preClique = 0; return preClique; } void processGraph(FILE* fout) { long i, j, k; intlist rem; edgeNum = 0; for (i = 1; i <= numNodes; i++) { genNodeConstr(fout, i); /* gen edge constraints */ for (rem = adjVerts[i]; rem != IL_EMPTYLIST; rem = IL_REST(rem)) { j = IL_FIRST(rem); genEdgeConstr(fout, i, j); } } return; } void genNodeConstr(FILE* fout, long i) { if (outopt == 1 || outopt == 2 || outopt == 3 || outopt == 4) { /* generate color constraints -- not needed for powers of 2 */ /* if special, its special clauses make stronger color restriction. */ long j, k; long isp, isSpecial; isSpecial = 0; for (isp = 0; isp < effSpecial; isp++) { if (specialNode[isp] == i) { isSpecial = 1; break; } } if (isSpecial == 0) { disallow(fout, i, numColors-1); } } if (outopt == 5) { /* Generate domain constraints, positive clauses */ long color; long isp, isSpecial; /* if special, its special clause subsumes the positive clause. */ isSpecial = 0; for (isp = 0; isp < effSpecial; isp++) { if (specialNode[isp] == i) { isSpecial = 1; break; } } if (isSpecial == 0) { for (color = 0; color < numColors; color++) { long var = tradVar(i, color, numColors); fprintf(fout,"%ld ", var); } fprintf(fout,"0\n"); clauseCnt ++; } } return; } void genEdgeConstr(FILE* fout, long i, long adjNode) { long k; long thisEdge; if (adjNode > i) { thisEdge = edgeNum; edgeNum ++; if (outopt == 1) { long i_bit, j_bit; fprintf(fout," +( "); for (k = 0; k < logColors; k++) { i_bit = xNodeVar(i, k); j_bit = xNodeVar(adjNode, k); fprintf(fout, "xor(%ld %ld) ", i_bit, j_bit ); } fprintf(fout,")\n"); } else if (outopt == 2) { long i_bit, j_bit; fprintf(fout," +( "); for (k = 0; k < logColors; k++) { i_bit = xNodeVar(i, k); j_bit = xNodeVar(adjNode, k); fprintf(fout, "*(%ld -%ld) *(-%ld %ld) ", i_bit, j_bit, i_bit, j_bit ); } fprintf(fout,")\n"); } else if (outopt == 3) { long i_bit, j_bit, clauseNum, flag; long edgeClauses = rndColors; edgeClauses = numColors; /* only gen for valid colors!!-AVG*/ for (clauseNum = 0; clauseNum < edgeClauses; clauseNum ++) { for (k = 0; k < logColors; k++) { flag = 1 << k; i_bit = xNodeVar(i, k); j_bit = xNodeVar(adjNode, k); if (flag & clauseNum) { i_bit = - i_bit; j_bit = - j_bit; } fprintf(fout, "%ld %ld ", i_bit, j_bit ); } fprintf(fout,"0\n"); clauseCnt ++; } } else if (outopt == 4) { long i_bit, j_bit; long xor_var; /* 1 cl. to enforce: some xor_var is true. */ for (k = 0; k < logColors; k++) { xor_var = xEdgeVar(thisEdge, k); fprintf(fout, "%ld ", xor_var ); } fprintf(fout,"0\n"); clauseCnt ++; for (k = 0; k < logColors; k++) { xor_var = xEdgeVar(thisEdge, k); i_bit = xNodeVar(i, k); j_bit = xNodeVar(adjNode, k); /* 4 cl.s to enforce: xor_var iff (i_bit xor j_bit) */ fprintf(fout, "%ld %ld %ld ", -xor_var, i_bit, j_bit ); fprintf(fout,"0\n"); clauseCnt ++; fprintf(fout, "%ld %ld %ld ", -xor_var, -i_bit, -j_bit ); fprintf(fout,"0\n"); clauseCnt ++; fprintf(fout, "%ld %ld %ld ", xor_var, -i_bit, j_bit ); fprintf(fout,"0\n"); clauseCnt ++; fprintf(fout, "%ld %ld %ld ", xor_var, i_bit, -j_bit ); fprintf(fout,"0\n"); clauseCnt ++; } } else if (outopt == 5) { long thisVar, adjVar; for (k = 0; k < numColors; k++) { thisVar = tradVar(i, k, numColors); adjVar = tradVar(adjNode, k, numColors); fprintf(fout, "%ld %ld 0\n", -thisVar, - adjVar); clauseCnt ++; } } } return; } long findDenseNode(long numNodes, long rowWidth) { long maxDegree, maxDegree2, winner, winnerCnt, i, j; maxDegree = maxDegree2 = 0; winner = 0; winnerCnt = 0; for (i = 1; i <= numNodes; i++) { if (degree[i] > maxDegree) { maxDegree = degree[i]; winner = i; winnerCnt = 1; } else if (degree[i] == maxDegree) { winnerCnt += 1; } } if (winnerCnt > 1) { printf("Found %ld nodes with degree %ld\n", winnerCnt, maxDegree); } for (i = 1; i <= numNodes; i++) { intlist rem; long degree2i; if (degree[i] < maxDegree) continue; degree2i = 0; for (rem = adjVerts[i]; rem != IL_EMPTYLIST; rem = IL_REST(rem)) { j = IL_FIRST(rem); degree2i += degree[j]; } degree2[i] = degree2i; if (degree2i > maxDegree2) { maxDegree2 = degree2i; winner = i; winnerCnt = 1; } else if (degree2i == maxDegree2) { winnerCnt += 1; } } printf("Dense node"); if (winnerCnt > 1) printf(" (%ld-way tie)", winnerCnt); printf(": %ld degree %ld degree2 %ld\n", winner, degree[winner], degree2[winner]); return winner; } /* expand numSpecial to nColors-1 (at most) by adding startNode * and the highest-degree neighbors of startNode as special nodes. * Assuming degree(startNode) >= nColors-1, we will not run out * of neighbors. If no node has degree >= nColors, the graph is * trivially colorable. */ void fillSpecial(int brkopt, long startNode, long nColors) { long i, j, base; intlist rem; long cand, candDegree; if (numSpecial >= nColors-1) return; printf(" %ld", startNode); specialNode[numSpecial] = startNode; numSpecial ++; if (numSpecial >= nColors-1) return; base = numSpecial; rem = adjVerts[startNode]; if (rem == IL_EMPTYLIST) return; /* very unexpected--startNode is isolated. */ cand = IL_FIRST(rem); rem = IL_REST(rem); specialNode[base] = cand; numSpecial ++; while (numSpecial < nColors-1) { if (rem == IL_EMPTYLIST) { for (i = base; i < numSpecial; i++) printf(" %ld", specialNode[i]); return; /* unexpected--startNode has low degree.*/ } cand = IL_FIRST(rem); rem = IL_REST(rem); candDegree = degree[cand]; insert(base, numSpecial, cand, candDegree); numSpecial ++; } /* specialNode[] is full. See if later candidates bump someone. */ while (rem != IL_EMPTYLIST) { cand = IL_FIRST(rem); rem = IL_REST(rem); candDegree = degree[cand]; if (candDegree > degree[specialNode[numSpecial-1]]) { /* bump specialNode[numSpecial-1] */ insert(base, numSpecial-1, cand, candDegree); } } for (i = base; i < numSpecial; i++) printf(" %ld", specialNode[i]); return; } void insert(long base, long vacant, long cand, long candDegree) { if (vacant == base) specialNode[vacant] = cand; else if (candDegree <= degree[specialNode[vacant-1]]) specialNode[vacant] = cand; else { specialNode[vacant] = specialNode[vacant-1]; insert(base, vacant-1, cand, candDegree); } return; } /** heuristic 2 considers the matrix limited to i and adj(i) with 0's * on the diagonal. The score for i is twice the number of 1's in * this matrix that are NOT in row i or column i plus * the number of 1's in row i (which is full except for [i][i]). * This means each triangle in the graph that involves i counts 4 and * each vertex adjacent to i counts 1 towards the total score for i. * A vertex in a clique of size k has a score >= (k - 1)*(2k - 3). * A completely filled square is a clique. * Many variations are possible in case there are no triangles. * Here, ties on total score are broken by degree[i] */ /* What is the iScore in an k-clique? */ long cliqueScore(long k) {return (k - 1) * (2 * k - 3);} long findDenseNode2(long numNodes, long rowWidth) { long maxScore, maxScore2, winner, winnerCnt, i, j, k; long iScore; maxScore = maxScore2 = 0; winner = 0; winnerCnt = 0; for (j = 1; j <= numNodes; j++) { winnerRow[j] = 0; } for (i = 1; i <= numNodes; i++) { iScore = setRowScores(thisRow, i, 1); /* boil it down to a clique by specifying 1 color */ if (iScore > maxScore) { maxScore = iScore; for (j = 1; j <= numNodes; j++) { winnerRow[j] = thisRow[j]; } winner = i; winnerCnt = 1; } else if (iScore == maxScore && degree[i] > degree[winner]) { maxScore = iScore; for (j = 1; j <= numNodes; j++) { winnerRow[j] = thisRow[j]; } winner = i; winnerCnt += 1; } else if (iScore == maxScore) { winnerCnt += 1; } } if (winnerCnt > 1) { printf("Found %ld nodes with score %ld\n", winnerCnt, maxScore); } /* Tie-break is based on larger vertex-degree. */ printf("winner is %ld with score %ld and degree %ld\n", winner, maxScore, degree[winner]); return winner; } /* expand numSpecial by degree[startNode]+1 by adding startNode * and the highest-score neighbors of startNode as special nodes. * However, prune out the weakest neighbors (lowest scores) and as * each is pruned, surviving nodes no longer get credit for being * adjacent to it; their scores are reduced. * Assuming numSpecial = 0 initially, specialNode[0] = winner, and * neighbors are ordered strongest to weakest in * specialNode[1 .. degree[startNode]]. * Return the largest prefix that constitutes a clique. * * Assuming degree(startNode) >= degree[startNode]+1, we will not run out * of neighbors. If no node has degree >= numColors, the graph is * trivially colorable. */ long fillSpecial2(int brkopt, long startNode) { long i, j, base, maxScore, preClique; long startDegree = degree[startNode]; specialNode[numSpecial] = startNode; numSpecial ++; base = numSpecial; /* boil it down to a clique by specifying 1 color again, to store * pruned nodes in higher part of effRow[]. * Is should be that maxScore = cliqueScore(effDegree + 1) in all * cases, for the test below. * setEffRow stores clique neighbors of startNode into effRow[0 ...]. */ maxScore = setRowScores(winnerRow, startNode, 1); effDegree = setEffRow(numNodes, winnerRow, effRow); for (j = 0; j < startDegree; j++) { specialNode[numSpecial] = effRow[j]; numSpecial++; } printf(" %ld", startNode); for (j = base; j < numSpecial; j++) printf(" %ld", specialNode[j]); printf("\n"); if (maxScore == cliqueScore(effDegree + 1)) { preClique = effDegree + 1; printf("Found %ld-clique: %ld (winner)", preClique, startNode); /* enumerate the rest of the clique */ for (j = 0; j < effDegree; j++) printf("% ld", effRow[j]); printf("\n"); } else preClique = 0; return preClique; } long setRowScores(long thisRow[], long i, long nColors) { long j, k, effDegree, effMax; intlist remi, remj; long thisColScore, iScore; long offseti = rowWidth * i; iScore = 0; for (j = 1; j <= numNodes; j++) thisRow[j] = 0; for (remi = adjVerts[i]; remi != IL_EMPTYLIST; remi = IL_REST(remi)) { j = IL_FIRST(remi); thisColScore = 0; thisColScore ++; /* for Adj[i][j] */ for (remj=adjVerts[j]; remj != IL_EMPTYLIST; remj = IL_REST(remj)) { k = IL_FIRST(remj); if (adjMat[offseti + k]) thisColScore += 2; } thisRow[j] = thisColScore; iScore += thisColScore; } effDegree = degree[i]; while (effDegree > nColors - 2) { effMax = cliqueScore(effDegree + 1); /* stop pruning if a clique has been found */ if (iScore == effMax) break; k = winnerMin(thisRow); effRow[effDegree-1] = k; iScore -= pruneWinner(thisRow, i, k); effDegree --; } return iScore; } long pruneWinner(long thisRow[], long i, long k) { long j, offsetj; long reduction; reduction = 0; for (j = 1; j <= numNodes; j++) { if (thisRow[j] == 0) continue; offsetj = rowWidth * j; if (adjMat[offsetj + k]) { thisRow[j] -= 2; reduction += 2; } } reduction += thisRow[k]; thisRow[k] = 0; return reduction; } long winnerMin(long thisRow[]) { long j, k; long curMin; k = 0; curMin = 4 * rowWidth * rowWidth; /* impossible value */ for (j = 1; j <= numNodes; j++) { if (thisRow[j] == 0) continue; if (thisRow[j] < curMin || (thisRow[j] == curMin && degree[j] < degree[k])) { curMin = thisRow[j]; k = j; } } return k; } long setEffRow(long numNodes, long winnerRow[], long effRow[]) { long effDegree, j; effDegree = 0; for (j = 1; j <= numNodes; j++) { if (winnerRow[j] > 0) { effRow[effDegree] = j; effDegree ++; } } return effDegree; } void insert2(long base, long vacant, long cand, long candScore) { if (vacant == base) specialNode[vacant] = cand; else if (candScore < winnerRow[specialNode[vacant-1]]) specialNode[vacant] = cand; else if (candScore == winnerRow[specialNode[vacant-1]] && degree[cand] <= degree[specialNode[vacant-1]]) specialNode[vacant] = cand; else { specialNode[vacant] = specialNode[vacant-1]; insert2(base, vacant-1, cand, candScore); } return; } void initDisallow(long nColors, long logColors) { long i, j, clneed, flag; for (i = 0; i < nColors; i ++) { clneed = 0; for (j = 0; j < logColors; j ++) { flag = (1< maxColor. */ void disallow(FILE* fout, long u, long maxColor) { long j, k, flag; for (j = 0; j < logColors; j ++) { if (bit[maxColor][j]) continue; if (outopt == 1 || outopt == 2) { long u_bit; fprintf(fout," +( "); for (k = j+1; k 4) break; } if (jfound > 16) break; } if (ifound > 64) break; } if (nCliques == 0) printf("no 4-clique found\n\n"); else printf("%ld 4-cliques found\n\n", nCliques); return nCliques; } long checkClique(long specialNode[], long low, long high) { /* Return i > 0 if there is a clique of size (high - low + 1) * consisting of i and all nodes in specialNode[] in * the range [low <= k < high], * or else return -(high - low) if there is a clique consisting of * all nodes in specialNode[] in the range [low <= k < high], * or else return 0. */ long i, j, k, m, offset, missing; intlist rem; /* checkClique() may be costly, so we provide a way to disable it */ if (checkItOut == 0) return 0; if (high <= low) return 0; for (k = low; k < high; k++) { i = specialNode[k]; offset = rowWidth * i; for (m = low; m < high; m++) { j = specialNode[m]; if (j != i && adjMat[offset + j] == 0) return 0; } } /* OK, we have a clique of size (high - low). Look for another node */ for (i = 1; i <= numNodes; i ++) { if (inSpecial(specialNode, low, high, i)) continue; offset = rowWidth * i; missing = 0; for (m = low; m < high; m++) { j = specialNode[m]; if (j != i && adjMat[offset + j] == 0) { missing = 1; break; } } if (missing) continue; return i; } return -(high - low); } void calcColors(long nColors) { long i; i = nColors-1; logColors = 0; rndColors = 1; while (i > 0) { logColors ++; rndColors = (rndColors << 1); i = i/2; } printf("num colors = %ld, rndColors = %ld\n", nColors, rndColors); } /* color graph in adjVerts with colors 1, ..., ncolors <= graphDegree+1. * Use simple greedy method, but process specialNode[] first. * Also allocate and initialize colorStatus[], although it's unrelated. */ void greedyColor(long specialNode[], long numSpecial) { long ncolors, i, j, k, iColor; intlist* adjColors; char* taken; long maxColor = graphDegree+1; color0 = calloc(rowWidth, sizeof(long)); colorStatus = calloc(rowWidth, sizeof(long)); adjColors = calloc(rowWidth, sizeof(intlist)); taken = calloc(maxColor+1, sizeof(char)); if (color0 == NULL || colorStatus == NULL || adjColors == NULL || taken == NULL) { printf("WARNING: no space for greedyColor(), continuing.\n"); if (color0) { for (i = 1; i <= maxColor; i++) color0[i] = i; } greedyColorNum = maxColor; return; } for (i = 1; i <= numNodes; i++) colorStatus[i] = -1; ncolors = 0; for (k = 0; k < numSpecial; k++) { i = specialNode[k]; iColor = lowColor(i, adjColors, taken); if (ncolors < iColor) ncolors = iColor; color0[i] = iColor; updateAdjColors(i, iColor, adjColors); } for (i = 1; i <= numNodes; i++) { if (color0[i] == 0) { iColor = lowColor(i, adjColors, taken); if (ncolors < iColor) ncolors = iColor; color0[i] = iColor; updateAdjColors(i, iColor, adjColors); } } greedyColorNum = ncolors; free(adjColors); /* all the lists are now garbage, though. */ free(taken); return; } void updateAdjColors(long i, long iColor, intlist adjColors[]) { intlist rem; long j; rem = adjVerts[i]; while (rem != IL_EMPTYLIST) { j = IL_FIRST(rem); rem = IL_REST(rem); adjColors[j] = IL_cons(iColor, adjColors[j]); } return; } long lowColor(long i, intlist adjColors[], char taken[]) { intlist rem; long j, clr; rem = adjColors[i]; while (rem != IL_EMPTYLIST) { j = IL_FIRST(rem); rem = IL_REST(rem); taken[j] = 1; } clr = 0; for (j = 1; j <= graphDegree + 1; j++) { if (taken[j] == 0) { clr = j; break; } } rem = adjColors[i]; while (rem != IL_EMPTYLIST) { j = IL_FIRST(rem); rem = IL_REST(rem); taken[j] = 0; } return clr; }