12 Compute the stable set for a graph. \n\n\
13 DSDP Usage: stable <graph filename> \n";
20 static int ReadGraphFromFile(
char*,
int*,
int*, EdgeMat*[]);
24 #define CHKERR(a) { if (a){printf("DSDP Numerical Error or Memory Problem"); return 2;} }
26 int main(
int argc,
char *argv[]){
42 int info,kk,nedges,nnodes;
47 if (argc<2){ printf(
"%s",help);
return(1); }
49 info = ReadGraphFromFile(argv[1],&nnodes,&nedges,&Edges);
50 if (info){ printf(
"Problem reading file\n");
return 1; }
52 info =
DSDPCreate(nedges+nnodes+1,&dsdp);CHKERR(info);
53 info = DSDPCreateSDPCone(dsdp,1,&sdpcone);CHKERR(info);
58 if (info){ printf(
"Problem setting data\n");
return 1; }
61 info =
DSDPSetZBar(dsdp,1e10*nnodes+1);CHKERR(info);
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){
69 }
else if (strncmp(argv[kk],
"-help",5)==0){
109 int i,ii,info,nnodes=nodes+1;
114 diag=(
double*)malloc(nnodes*
sizeof(
double));
115 iptr=(
int*)malloc(nnodes*
sizeof(
int));
116 iptr2=(
int*)malloc(nnodes*
sizeof(
int));
118 ii=nodes*(nodes+1)/2;
119 for (i=0;i<nnodes;i++){
128 for (i=0;i<nnodes;i++){
130 info =
DSDPSetY0(dsdp,i+1,0.0);CHKERR(info);
139 for (i=0; i<edges; i++){
143 info =
DSDPSetY0(dsdp,i+nnodes+1,0.0);CHKERR(info);
165 int i,j,derror,info,nnodes=nodes+1;
166 double dd,scal=RAND_MAX,*vv,*tt,*cc,ymin=0;
169 vv=(
double*)malloc(nnodes*
sizeof(
double));
170 tt=(
double*)malloc(nnodes*
sizeof(
double));
171 cc=(
double*)malloc((edges+nnodes+2)*
sizeof(double));
173 for (i=0;i<nnodes;i++){
174 for (j=0;j<nnodes;j++){dd = (( rand())/scal - .5); vv[j] = tan(3.1415926*dd);}
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]) ){
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;}
189 if (cc[0]<ymin) ymin=cc[0];
191 printf(
"Stable Set Size: %4.0f\n",-ymin);
192 free(vv); free(tt); free(cc);
198 #define BUFFERSIZ 100
201 #define __FUNCT__ "ParseGraphline"
202 static int ParseGraphline(
char * thisline,
int *row,
int *col,
double *value,
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;}
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);
221 #define __FUNCT__ "ReadGraphFromFile"
222 static int ReadGraphFromFile(
char* filename,
int *nnodes,
int *nedges, EdgeMat**EE){
225 char thisline[BUFFERSIZ]=
"*";
226 int i,k=0,line=0,nodes,edges,gotone=3;
231 fp=fopen(filename,
"r");
232 if (!fp){ printf(
"Cannot open file %s !",filename);
return(1); }
234 while(!feof(fp) && (thisline[0] ==
'*' || thisline[0] ==
'"') ){
235 fgets(thisline,BUFFERSIZ,fp); line++; }
237 if (sscanf(thisline,
"%d %d",&nodes, &edges)!=2){
238 printf(
"First line must contain the number of nodes and number of edges\n");
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;
248 while(!feof(fp) && gotone){
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;}
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;
261 }
else if (gotone && k>=edges) {
262 printf(
"To many edges in file.\nLine %d, %s\n",line,thisline);
264 }
else if (gotone&&(col >= nodes || row >= nodes || col < 0 || row < 0)){
265 printf(
"Invalid node number.\nLine %d, %s\n",line,thisline);
270 *nnodes=nodes; *nedges=k;