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;
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 SetStableSetData(DSDP, SDPCone, int, int, EdgeMat[])
Given a graph, formulate maximum Stable Set problem and place data into solver.
int DSDPSetOptions(DSDP dsdp, char *runargs[], int nargs)
Read command line arguments to set options in DSDP.
int DSDPSetZBar(DSDP dsdp, double ppobj)
Set an upper bound on the objective value at the solution.
int DSDPSetDualObjective(DSDP dsdp, int i, double bi)
Set the objective vector b in (D).
int SDPConeCheckData(SDPCone sdpcone)
Check the matrix operations on a data matrix;.
Internal structures for the DSDP solver.
int DSDPSetGapTolerance(DSDP dsdp, double gaptol)
Terminate the solver when the relative duality gap is less than this tolerance.
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 SDPConeAddXVAV(SDPCone sdpcone, int blockj, double vin[], int n, double sum[], int mm)
Compute for i = 0 through m.
int SDPConeViewDataMatrix(SDPCone sdpcone, int blockj, int vari)
Print a data matrix to the screen.
int DSDPSetup(DSDP dsdp)
Set up data structures in the solver and the cones associated with it.
int DSDPReuseMatrix(DSDP dsdp, int rm)
Reuse the Hessian of the barrier function multiple times at each DSDP iteration.
int SDPConeAddARankOneMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Add data matrix where v is a sparse vector.
int SDPConeAddASparseVecMat(SDPCone sdpcone, int blockj, int vari, int n, double alpha, int ishift, const int ind[], const double val[], int nnz)
Add data matrix in a sparse format.
int StableRandomized(SDPCone, int, int, EdgeMat[])
Apply a randomized procedure to find feasible stable sets.
int SDPConeComputeXV(SDPCone sdpcone, int blockj, int *derror)
Compute a factor V such that .
int DSDPSetY0(DSDP dsdp, int i, double yi0)
Set the initial values of variables y in (D).
int SDPConeUsePackedFormat(SDPCone sdpcone, int blockj)
Use packed symmetric format for the dense array.
int SDPConeXVMultiply(SDPCone sdpcone, int blockj, double vin[], double vout[], int n)
Multiply an array by a factor V such that .
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.
int StableSet(int argc, char *argv[])
Formulate and solve the maximum Stable Set problem.
int DSDPSetStandardMonitor(DSDP dsdp, int k)
Print at every kth iteration.