12 char help2[]=
"\nA positive semidefinite relaxation of the\n\ 13 graph k coloring problem can be rewritten as\n\n\ 15 such that X_ij <= 1 - 1/(k-1) for all edges (i,j).\n\ 18 char help[]=
"DSDP Usage: color <graph filename> ";
20 static int ReadGraph(
char*,
int *,
int *,
int**,
int **,
double **);
21 static int ParseGraphline(
char*,
int*,
int*,
double*,
int*);
22 static int RandomizedColor(
DSDP,
SDPCone,
int,
int[],
int[],
int);
26 int main(
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; }
57 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);
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++){
78 if (info) printf(
"ERROR 1: %d \n",i);
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];
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);
96 if (info) printf(
"ERROR 3: %d %d \n",i,vari);
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){
109 }
else if (strncmp(argv[kk],
"-help",7)==0){
115 if (info){ printf(
"Out of memory\n");
return 1; }
119 if (info){ printf(
"Out of memory\n");
return 1; }
122 if (info){ printf(
"Numerical error\n");
return 1; }
126 info=RandomizedColor(dsdp, sdpcone, nnodes, node1, node2, nedges);
131 free(node1);free(node2);free(weight);
140 static 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;
151 static 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);
158 static 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--;
172 static 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;}
182 static 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];} }
192 static int First(
int coloring[],
int nnodes){
194 for (i=0;i<nnodes;i++){
202 static 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;}
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);
257 #define BUFFERSIZ 100 260 #define __FUNCT__ "ParseGraphline" 261 static 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" 280 int 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;
int DSDPCreate(int m, DSDP *dsdpnew)
Create a DSDP solver. FIRST DSDP routine!
int DSDPDestroy(DSDP dsdp)
Free the internal data structures of the solver and the cones associated with it.
int DSDPReadOptions(DSDP dsdp, char filename[])
Read DSDP parameters from a file.
int DSDPCreateBCone(DSDP dsdp, BCone *dspcone)
Create a new cone that represents bounds on the y variables.
int DSDPSetOptions(DSDP dsdp, char *runargs[], int nargs)
Read command line arguments to set options in DSDP.
int DSDPSetDualObjective(DSDP dsdp, int i, double bi)
Set the objective vector b in (D).
Internal structures for the DSDP solver.
DSDPTerminationReason
There are many reasons to terminate the solver.
int SDPConeGetXArray(SDPCone sdpcone, int blockj, double *xx[], int *nn)
After applying the solver, set a pointer to the array in the object with the solution X.
The API to DSDP for those applications using DSDP as a subroutine library.
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
int BConeAllocateBounds(BCone bcone, int nnz)
Set a surplus variable in constraint in (P).
int BConeSetPSlackVariable(BCone bcone, int vari)
Set a slack variable to a constraint in (P).
int DSDPSetPotentialParameter(DSDP dsdp, double rho)
Set the potential parameter.
int DSDPStopReason(DSDP dsdp, DSDPTerminationReason *reason)
Copy the reason why the solver terminated.
int MinColoring(int argc, char *argv[])
SDP relaxation of k-coloring problem.
int DSDPSolve(DSDP dsdp)
Apply DSDP to the problem.
int SDPConeSetBlockSize(SDPCone sdpcone, int blockj, int n)
Set the dimension of one block in the semidefinite cone.
Internal structure for semidefinite cone.
int SDPConeSetSparsity(SDPCone sdpcone, int blockj, int nnz)
Set the number of nonzero matrices in a block of the semidefinite cone.
int DSDPComputeX(DSDP dsdp)
Compute the X variables.
int SDPConeSetASparseVecMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Set data matrix in a sparse format.
struct BCone_C * BCone
The BCone object points to lower and upper bounds on the variable y in (D).
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.