12char help2[]=
"\nA positive semidefinite relaxation of the\n\
13graph k coloring problem can be rewritten as\n\n\
15 such that X_ij <= 1 - 1/(k-1) for all edges (i,j).\n\
18char help[]=
"DSDP Usage: color <graph filename> ";
20static int ReadGraph(
char*,
int *,
int *,
int**,
int **,
double **);
21static int ParseGraphline(
char*,
int*,
int*,
double*,
int*);
22static int RandomizedColor(
DSDP,
SDPCone,
int,
int[],
int[],
int);
23int MinColoring(
int argc,
char *argv[]);
26int main(
int argc,
char *argv[]){
28 info=MinColoring(argc,argv);
39int MinColoring(
int argc,
char *argv[]){
42 int *node1,*node2,nedges,nnodes;
44 double *weight,*yy1,*yy2,bb;
50 if (argc<2){ printf(
"%s\n%s",help2,help);
return(1); }
52 info = ReadGraph(argv[1],&nnodes,&nedges,&node1,&node2,&weight);
53 if (info){ printf(
"Problem reading file\n");
return 1; }
55 info = DSDPCreate(nnodes+nedges,&dsdp);
57 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);
58 info = SDPConeSetBlockSize(sdpcone,0,nnodes);
59 info = SDPConeSetSparsity(sdpcone,0,nnodes+nedges+1);
61 info = DSDPCreateBCone(dsdp,&bcone);
63 if (info){ printf(
"Out of memory\n");
return 1; }
70 iptr1=(
int*)malloc(nnodes*
sizeof(
int));
71 yy1=(
double*)malloc(nnodes*
sizeof(
double));
72 for (i=0;i<nnodes;i++){
73 iptr1[i]=(i+2)*(i+1)/2-1;
76 for (i=0;i<nnodes;i++){
77 info=SDPConeSetASparseVecMat(sdpcone,0,i+1,nnodes,1.0,0,iptr1+i,yy1+i,1);
78 if (info) printf(
"ERROR 1: %d \n",i);
79 info=DSDPSetDualObjective(dsdp,i+1,1.0);
84 iptr2=(
int*)malloc(nedges*
sizeof(
int));
85 yy2=(
double*)malloc(nedges*
sizeof(
double));
86 for (i=0;i<nedges;i++){
87 iptr2[i]=(node1[i])*(node1[i]+1)/2+node2[i];
90 info = BConeAllocateBounds(bcone,nedges);
91 for (i=0; i<nedges; i++){
93 info = SDPConeSetSparseVecMat(sdpcone,0,vari,nnodes,0,iptr2+i,yy2+i,1);
94 if (info) printf(
"ERROR 2: %d %d \n",i,vari);
95 info = BConeSetPSlackVariable(bcone,vari);
96 if (info) printf(
"ERROR 3: %d %d \n",i,vari);
97 info = DSDPSetDualObjective(dsdp,vari,bb);
102 info=DSDPSetPotentialParameter(dsdp,5);
104 for (kk=1; kk<argc-1; kk++){
105 if (strncmp(argv[kk],
"-dloginfo",8)==0){
107 }
else if (strncmp(argv[kk],
"-params",7)==0){
108 info=DSDPReadOptions(dsdp,argv[kk+1]);
109 }
else if (strncmp(argv[kk],
"-help",7)==0){
113 info=DSDPSetOptions(dsdp,argv,argc);
115 if (info){ printf(
"Out of memory\n");
return 1; }
116 info = DSDPSetStandardMonitor(dsdp,1);
118 info = DSDPSetup(dsdp);
119 if (info){ printf(
"Out of memory\n");
return 1; }
121 info = DSDPSolve(dsdp);
122 if (info){ printf(
"Numerical error\n");
return 1; }
123 info = DSDPStopReason(dsdp,&reason);
126 info=RandomizedColor(dsdp, sdpcone, nnodes, node1, node2, nedges);
129 info = DSDPDestroy(dsdp);
131 free(node1);free(node2);free(weight);
140static int GetXRow(
double xmat[],
double xrow[],
int row,
int n){
141 int i,i1=row*(row+1)/2;
142 for (i=0;i<row;i++){xrow[i]=xmat[i1+i];}
143 for (i=row;i<n;i++){xrow[i]=xmat[i1+row];i1+=i+1;}
148 int index;
double val;
151static int cut_comp(
const void *e1,
const void *e2){
152 double d1=((orderVec*)e1)->val, d2=((orderVec*)e2)->val;
153 if (d1<d2)
return (1);
154 else if (d1>d2)
return (-1);
158static int RemoveNode(
int node,
int node1[],
int node2[],
int *nedges){
159 int i,nnedges=*nedges;
160 for (i=0;i<nnedges;i++){
161 if (node1[i]==node || node2[i]==node){
162 node1[i]=node1[nnedges-1];
163 node2[i]=node2[nnedges-1];
165 if (i < nnedges) i--;
172static int Connected(
int n1,
int n2,
int node1[],
int node2[],
int nedges){
174 if (n1==n2)
return 1;
175 for (i=0;i<nedges;i++){
176 if (node1[i]==n1 && node2[i]==n2){
return 1;}
177 if (node1[i]==n2 && node2[i]==n1){
return 1;}
182static int HighDegree(
int node1[],
int node2[],
int nedges,
int iwork[],
int nnodes){
183 int i,nmax=0,maxdegree=-1;
184 for (i=0;i<nnodes;i++) iwork[i]=0;
185 for (i=0;i<nedges;i++){
186 iwork[node1[i]]++; iwork[node2[i]]++;
188 for (i=0;i<nnodes;i++){
if (iwork[i]>maxdegree){nmax=i; maxdegree=iwork[i];} }
192static int First(
int coloring[],
int nnodes){
194 for (i=0;i<nnodes;i++){
202static int RandomizedColor(
DSDP dsdp,
SDPCone sdpcone,
int nnodes,
int node1[],
int node2[],
int nedges){
203 int i,j,nodek,nn,info,flag,coloring=0,maxvertex;
204 int *degree,*color,*cgroup,ngsize,uncolored=nnodes;
209 xrow=(
double*)malloc(nnodes*
sizeof(
double));
210 color=(
int*)malloc(nnodes*
sizeof(
int));
211 cgroup=(
int*)malloc(nnodes*
sizeof(
int));
212 degree=(
int*)malloc(nnodes*
sizeof(
int));
213 vorder=(orderVec*)malloc(nnodes*
sizeof(orderVec));
215 for (i=0;i<nnodes;i++){ color[i]=0;}
216 info=DSDPComputeX(dsdp);
217 info=SDPConeGetXArray(sdpcone,0,&xptr,&nn);
223 maxvertex=First(color,nnodes);
224 maxvertex=HighDegree(node1,node2,tnedges,degree,nnodes);
226 cgroup[0]=maxvertex;ngsize=1;
228 info=GetXRow(xptr,xrow,maxvertex,nnodes);
230 for (i=0;i<nnodes;i++){vorder[i].index=i; vorder[i].val = xrow[i];}
231 qsort( (
void*)vorder, nnodes,
sizeof(orderVec), cut_comp);
233 for (i=0;i<nnodes;i++){
234 nodek=vorder[i].index;
235 if (color[nodek]==0){
236 for (flag=0,j=0;j<ngsize;j++){
237 if (Connected(nodek,cgroup[j],node1,node2,tnedges) ){flag=1;}
239 if (flag==0){ cgroup[ngsize]=nodek; ngsize++; }
242 for (i=0;i<ngsize;i++){
243 color[cgroup[i]]=coloring; uncolored--;
244 RemoveNode(cgroup[i],node1,node2,&tnedges);
247 printf(
"\nCOLORS: %d\n",coloring);
260#define __FUNCT__ "ParseGraphline"
261static int ParseGraphline(
char * thisline,
int *row,
int *col,
double *value,
267 rtmp=-1, coltmp=-1, *value=0.0;
268 temp=sscanf(thisline,
"%d %d %lf",&rtmp,&coltmp,value);
269 if (temp==3 && rtmp>0 && coltmp>0) *gotem=3;
270 else if (temp==2 && rtmp>0 && coltmp>0){ *value = 1.0; *gotem=3;}
272 *row=rtmp-1; *col=coltmp-1;
279#define __FUNCT__ "ReadGraph"
280int ReadGraph(
char* filename,
int *nnodes,
int *nedges,
281 int**n1,
int ** n2,
double **wght){
284 char thisline[BUFFERSIZ]=
"*";
285 int i,k=0,line=0,nodes,edges,gotone=3;
291 fp=fopen(filename,
"r");
292 if (!fp){printf(
"Cannot open file %s !",filename);
return(1);}
294 while(!feof(fp) && (thisline[0] ==
'*' || thisline[0] ==
'"') ){
295 fgets(thisline,BUFFERSIZ,fp); line++;
298 if (sscanf(thisline,
"%d %d",&nodes, &edges)!=2){
299 printf(
"First line must contain the number of nodes and number of edges\n");
303 node1=(
int*)malloc(edges*
sizeof(
int));
304 node2=(
int*)malloc(edges*
sizeof(
int));
305 weight=(
double*)malloc(edges*
sizeof(
double));
307 for (i=0; i<edges; i++){ node1[i]=0;node2[i]=0;weight[i]=0.0;}
309 while(!feof(fp) && gotone){
311 fgets(thisline,BUFFERSIZ,fp); line++;
312 info = ParseGraphline(thisline,&row,&col,&value,&gotone);
313 if (gotone && value!=0.0 && k<edges &&
314 col < nodes && row < nodes && col >= 0 && row >= 0){
315 if (row<col){info=row;row=col;col=info;}
318 node1[k]=row; node2[k]=col;
319 weight[k]=value; k++;
321 }
else if (gotone && k>=edges) {
322 printf(
"To many edges in file.\nLine %d, %s\n",line,thisline);
324 }
else if (gotone&&(col >= nodes || row >= nodes || col < 0 || row < 0)){
325 printf(
"Invalid node number.\nLine %d, %s\n",line,thisline);
329 *nnodes=nodes; *nedges=edges;
330 *n1=node1; *n2=node2; *wght=weight;
The API to DSDP for those applications using DSDP as a subroutine library.
struct BCone_C * BCone
The BCone object points to lower and upper bounds on the variable y in (D).
DSDPTerminationReason
There are many reasons to terminate the solver.
Internal structures for the DSDP solver.
Internal structure for semidefinite cone.