DSDP
stable.c
Go to the documentation of this file.
1#include "dsdp5.h"
2#include <stdio.h>
3#include <string.h>
4#include <math.h>
5#include <stdlib.h>
6
11char help[]="\n\
12Compute the stable set for a graph. \n\n\
13DSDP Usage: stable <graph filename> \n";
14
15typedef struct {
16 double v[3];
17 int indd[3];
18} EdgeMat;
19
20static int ReadGraphFromFile(char*,int*, int*, EdgeMat*[]);
21int SetStableSetData(DSDP, SDPCone, int, int, EdgeMat[]);
22int StableSet(int argc,char *argv[]);
23int StableRandomized(SDPCone,int, int, EdgeMat[]);
24#define CHKERR(a) { if (a){printf("DSDP Numerical Error or Memory Problem"); return 2;} }
25
26int main(int argc,char *argv[]){
27 int info;
28 info=StableSet(argc,argv);
29 return 0;
30}
31
40int StableSet(int argc,char *argv[]){
41
42 int info,kk,nedges,nnodes;
43 EdgeMat *Edges;
44 DSDP dsdp;
45 SDPCone sdpcone;
46
47 if (argc<2){ printf("%s",help); return(1); }
48
49 info = ReadGraphFromFile(argv[1],&nnodes,&nedges,&Edges);
50 if (info){ printf("Problem reading file\n"); return 1; }
51
52 info = DSDPCreate(nedges+nnodes+1,&dsdp);CHKERR(info);
53 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);CHKERR(info);
54 info = SDPConeSetBlockSize(sdpcone,0,nnodes+1);CHKERR(info);
55 info = SDPConeUsePackedFormat(sdpcone,0);CHKERR(info);
56 info = SDPConeSetSparsity(sdpcone,0,nedges+nnodes+1);CHKERR(info);
57 info = SetStableSetData(dsdp, sdpcone, nnodes, nedges, Edges);
58 if (info){ printf("Problem setting data\n"); return 1; }
59
60 info = DSDPSetGapTolerance(dsdp,0.0001);CHKERR(info);
61 info = DSDPSetZBar(dsdp,1e10*nnodes+1);CHKERR(info);
62 info = DSDPReuseMatrix(dsdp,10);CHKERR(info);
63
64 for (kk=1; kk<argc-1; kk++){
65 if (strncmp(argv[kk],"-dloginfo",8)==0){
66 info=DSDPLogInfoAllow(DSDP_TRUE,0);CHKERR(info);
67 } else if (strncmp(argv[kk],"-params",7)==0){
68 info=DSDPReadOptions(dsdp,argv[kk+1]);CHKERR(info);
69 } else if (strncmp(argv[kk],"-help",5)==0){
70 printf("%s\n",help);
71 }
72 }
73 info=DSDPSetOptions(dsdp,argv,argc);CHKERR(info);
74
75 info = DSDPSetStandardMonitor(dsdp,1);CHKERR(info);
76
77 info = DSDPSetup(dsdp);CHKERR(info);
78 if (0==1){info=SDPConeCheckData(sdpcone);}
79
80 info=DSDPSolve(dsdp); CHKERR(info);
81 info=StableRandomized(sdpcone,nnodes,nedges,Edges);
82
83 info=DSDPComputeX(dsdp);CHKERR(info);
84
85 if (0==1){ /* Look at the solution */
86 int n; double *xx;
87 info=SDPConeGetXArray(sdpcone,0,&xx,&n);CHKERR(info);
88 }
89
90 info = DSDPDestroy(dsdp);CHKERR(info);
91 free(Edges);
92
93 return 0;
94} /* main */
95
107int SetStableSetData(DSDP dsdp, SDPCone sdpcone, int nodes, int edges, EdgeMat Edge[]){
108
109 int i,ii,info,nnodes=nodes+1;
110 int *iptr,*iptr2;
111 double *diag;
112
113 /* The c matrix has all elements equal to 1.0 */
114 diag=(double*)malloc(nnodes*sizeof(double));
115 iptr=(int*)malloc(nnodes*sizeof(int));
116 iptr2=(int*)malloc(nnodes*sizeof(int));
117
118 ii=nodes*(nodes+1)/2;
119 for (i=0;i<nnodes;i++){
120 diag[i]=1.0;
121 iptr[i]=i*(i+1)/2+i;
122 iptr2[i]=i;
123 }
124 info = SDPConeSetASparseVecMat(sdpcone,0,0,nnodes,-0.50,0,iptr,diag,nodes);CHKERR(info);
125 info = SDPConeAddASparseVecMat(sdpcone,0,0,nnodes,-0.25,-ii,iptr2,diag,nodes);CHKERR(info);
126 if (0){info=SDPConeViewDataMatrix(sdpcone,0,0);}
127 /* Diagonal elements must equal 1 */
128 for (i=0;i<nnodes;i++){
129 info = DSDPSetDualObjective(dsdp,i+1,1.0);CHKERR(info);
130 info = DSDPSetY0(dsdp,i+1,0.0);CHKERR(info);
131 info = SDPConeSetASparseVecMat(sdpcone,0,i+1,nnodes,1.0,0,iptr+i,diag+i,1);CHKERR(info);
132 }
133
134 /*
135 For each edge connecting nodes i and j,
136 X(i,i)+X(j,j)+X(i,j)+X(j,i)+X(i,n)+X(n,i)+X(j,n)+X(n,j)+X(n,n) = 1
137 where nodes i,j numbered 0 ... n-1.
138 */
139 for (i=0; i<edges; i++){
140 info = SDPConeAddARankOneMat(sdpcone,0,i+nnodes+1,nnodes,1.0,0,Edge[i].indd,Edge[i].v,3);
141 if (0==1){info = SDPConeViewDataMatrix(sdpcone,0,i+nnodes+1);CHKERR(info);}
142 info = DSDPSetDualObjective(dsdp,i+nnodes+1,1.0);CHKERR(info);
143 info = DSDPSetY0(dsdp,i+nnodes+1,0.0);CHKERR(info);
144 }
145
146 /* The initial point y is feasible and near the central path */
147 /*
148 info = DSDPSetR0(dsdp,0);
149 */
150 return(0);
151}
152
164int StableRandomized(SDPCone sdpcone,int nodes, int edges, EdgeMat Edge[]){
165 int i,j,derror,info,nnodes=nodes+1;
166 double dd,scal=RAND_MAX,*vv,*tt,*cc,ymin=0;
167 int e0,e1,e2;
168
169 vv=(double*)malloc(nnodes*sizeof(double));
170 tt=(double*)malloc(nnodes*sizeof(double));
171 cc=(double*)malloc((edges+nnodes+2)*sizeof(double));
172 info=SDPConeComputeXV(sdpcone,0,&derror);
173 for (i=0;i<nnodes;i++){
174 for (j=0;j<nnodes;j++){dd = (( rand())/scal - .5); vv[j] = tan(3.1415926*dd);}
175 info=SDPConeXVMultiply(sdpcone,0,vv,tt,nnodes);
176 for (j=0; j<edges; j++){
177 e0=Edge[j].indd[0];e1=Edge[j].indd[1];e2=Edge[j].indd[2];
178 if (tt[e0] * tt[e2] > 0 && tt[e1]*tt[e2] >0){
179 if ( fabs(tt[e0]-tt[e2]) > fabs(tt[e1]-tt[e2]) ){
180 tt[e0]*=-1;
181 } else {
182 tt[e1]*=-1;
183 }
184 }
185 }
186 for (j=0;j<nnodes;j++){if (tt[j]<0) tt[j]=-1; else tt[j]=1;}
187 for (j=0;j<edges+nodes+1;j++){cc[j]=0;}
188 info=SDPConeAddXVAV(sdpcone,0,tt,nnodes,cc,edges+nnodes+2);
189 if (cc[0]<ymin) ymin=cc[0];
190 }
191 printf("Stable Set Size: %4.0f\n",-ymin);
192 free(vv); free(tt); free(cc);
193
194 return(0);
195}
196
197
198#define BUFFERSIZ 100
199
200#undef __FUNCT__
201#define __FUNCT__ "ParseGraphline"
202static int ParseGraphline(char * thisline,int *row,int *col,double *value,
203 int *gotem){
204
205 int temp;
206 int rtmp,coltmp;
207
208 rtmp=-1, coltmp=-1, *value=0.0;
209 temp=sscanf(thisline,"%d %d %lf",&rtmp,&coltmp,value);
210 if (temp==3 && rtmp>0 && coltmp>0) *gotem=3;
211 else if (temp==2 && rtmp>0 && coltmp>0){ *value = 1.0; *gotem=3;}
212 else *gotem=0;
213 *row=rtmp-1; *col=coltmp-1;
214 if (*gotem && (*col < 0 || *row < 0)){
215 printf("Node Number must be positive.\n, %s\n",thisline);
216 }
217 return(0);
218}
219
220#undef __FUNCT__
221#define __FUNCT__ "ReadGraphFromFile"
222static int ReadGraphFromFile(char* filename,int *nnodes, int *nedges, EdgeMat**EE){
223
224 FILE*fp;
225 char thisline[BUFFERSIZ]="*";
226 int i,k=0,line=0,nodes,edges,gotone=3;
227 int info,row,col;
228 double value;
229 EdgeMat *E;
230
231 fp=fopen(filename,"r");
232 if (!fp){ printf("Cannot open file %s !",filename); return(1); }
233
234 while(!feof(fp) && (thisline[0] == '*' || thisline[0] == '"') ){
235 fgets(thisline,BUFFERSIZ,fp); line++; }
236
237 if (sscanf(thisline,"%d %d",&nodes, &edges)!=2){
238 printf("First line must contain the number of nodes and number of edges\n");
239 return 1;
240 }
241
242 E=(EdgeMat*)malloc(edges*sizeof(EdgeMat)); *EE=E;
243 for (i=0; i<edges; i++){
244 E[i].v[0]=0; E[i].v[1]=0; E[i].v[2]=0;
245 E[i].indd[0]=0; E[i].indd[1]=0; E[i].indd[2]=0;
246 }
247
248 while(!feof(fp) && gotone){
249 thisline[0]='\0';
250 fgets(thisline,BUFFERSIZ,fp); line++;
251 info = ParseGraphline(thisline,&row,&col,&value,&gotone);
252 if (gotone && k<edges &&
253 col < nodes && row < nodes && col >= 0 && row >= 0){
254 if (row > col){i=row;row=col;col=i;}
255 if (row == col){}
256 else {
257 E[k].indd[0]=row; E[k].indd[1]=col; E[k].indd[2]=nodes;
258 E[k].v[0]=1.0; E[k].v[1]=1.0; E[k].v[2]=1.0;
259 k++;
260 }
261 } else if (gotone && k>=edges) {
262 printf("To many edges in file.\nLine %d, %s\n",line,thisline);
263 return 1;
264 } else if (gotone&&(col >= nodes || row >= nodes || col < 0 || row < 0)){
265 printf("Invalid node number.\nLine %d, %s\n",line,thisline);
266 return 1;
267 }
268 }
269
270 *nnodes=nodes; *nedges=k;
271
272 return 0;
273}
274
The API to DSDP for those applications using DSDP as a subroutine library.
@ DSDP_TRUE
int StableRandomized(SDPCone, int, int, EdgeMat[])
Apply a randomized procedure to find feasible stable sets.
Definition stable.c:164
Internal structures for the DSDP solver.
Definition dsdp.h:65
Internal structure for semidefinite cone.
Definition dsdpsdp.h:80