fp20_dstruct.c

Go to the documentation of this file.
00001 /****************************************************************************/
00002 /*                                                                          */
00003 /*  This file is part of QSopt_ex.                                          */
00004 /*                                                                          */
00005 /*  (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash,      */
00006 /*  and Daniel Espinoza                                                     */
00007 /*                                                                          */
00008 /*  Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his     */
00009 /*  copyright in QSopt.                                                     */
00010 /*                                                                          */
00011 /*  This code may be used under the terms of the GNU General Public License */
00012 /*  (Version 2.1 or later) as published by the Free Software Foundation.    */
00013 /*                                                                          */
00014 /*  Alternatively, use is granted for research purposes only.               */
00015 /*                                                                          */
00016 /*  It is your choice of which of these two licenses you are operating      */
00017 /*  under.                                                                  */
00018 /*                                                                          */
00019 /*  We make no guarantees about the correctness or usefulness of this code. */
00020 /*                                                                          */
00021 /****************************************************************************/
00022 
00023 /* RCS_INFO = "$RCSfile: fp20_dstruct.c,v $ $Revision: 1.2 $ $Date: 2003/11/05 16:49:52 $"; */
00024 static int TRACE = 0;
00025 
00026 #include "config.h"
00027 #include "fp20_iqsutil.h"
00028 #include "fp20_dstruct.h"
00029 #include "fp20_qsopt.h"
00030 #include "fp20_lpdefs.h"
00031 #ifdef USEDMALLOC
00032 #include "dmalloc.h"
00033 #endif
00034 
00035 /****************************************************************************/
00036 /*                                                                          */
00037 /*                            fp20_svector                                       */
00038 /*                                                                          */
00039 /*  Written by:  Applegate, Cook, Dash                                      */
00040 /*  Date:                                                                   */
00041 /*                                                                          */
00042 /*    EXPORTED FUNCTIONS:                                                   */
00043 /*                                                                          */
00044 /****************************************************************************/
00045 
00046 void fp20_ILLsvector_init (
00047   fp20_svector * s)
00048 {
00049   s->nzcnt = 0;
00050   s->indx = 0;
00051   s->coef = 0;
00052 }
00053 
00054 void fp20_ILLsvector_free (
00055   fp20_svector * s)
00056 {
00057   ILL_IFFREE (s->indx, int);
00058 
00059   fp20_EGlpNumFreeArray (s->coef);
00060   s->nzcnt = 0;
00061 }
00062 
00063 int fp20_ILLsvector_alloc (
00064   fp20_svector * s,
00065   int nzcnt)
00066 {
00067   int rval = 0;
00068 
00069   s->nzcnt = nzcnt;
00070   if (nzcnt == 0)
00071   {
00072     s->indx = 0;
00073     s->coef = 0;
00074   }
00075   else
00076   {
00077     ILL_SAFE_MALLOC (s->indx, nzcnt, int);
00078 
00079     s->coef = fp20_EGlpNumAllocArray (nzcnt);
00080   }
00081   return 0;
00082 CLEANUP:
00083   ILL_IFFREE (s->indx, int);
00084   fp20_EGlpNumFreeArray (s->coef);
00085   ILL_RETURN (rval, "fp20_ILLsvector_alloc");
00086 }
00087 
00088 int fp20_ILLsvector_copy (
00089   const fp20_svector * s_in,
00090   fp20_svector * s_out)
00091 {
00092   int i;
00093   int nzcnt = s_in->nzcnt;
00094   int rval = 0;
00095 
00096   rval = fp20_ILLsvector_alloc (s_out, nzcnt);
00097   ILL_CLEANUP_IF (rval);
00098   for (i = 0; i < nzcnt; i++)
00099   {
00100     s_out->indx[i] = s_in->indx[i];
00101     fp20_EGlpNumCopy (s_out->coef[i], s_in->coef[i]);
00102   }
00103 
00104 CLEANUP:
00105   ILL_RETURN (rval, "fp20_ILLsvector_copy");
00106 }
00107 
00108 /****************************************************************************/
00109 /*                                                                          */
00110 /*                            fp20_heap                                          */
00111 /*                                                                          */
00112 /*  Written by:  Applegate, Cook, Dash                                      */
00113 /*  Date:                                                                   */
00114 /*                                                                          */
00115 /*    EXPORTED FUNCTIONS:                                                   */
00116 /*                                                                          */
00117 /****************************************************************************/
00118 
00119 #define fp20_DEBUG_HEAP 0
00120 
00121 #define fp20_HEAP_D 3
00122 #define fp20_HEAP_UP(x) (((x)-1)/fp20_HEAP_D)
00123 #define fp20_HEAP_DOWN(x) (((x)*fp20_HEAP_D)+1)
00124 
00125 static int fp20_siftup (
00126   fp20_heap * h,
00127   int hloc,
00128   int ix),
00129   fp20_siftdown (
00130   fp20_heap * h,
00131   int hloc,
00132   int ix),
00133   fp20_maxchild (
00134   fp20_heap * h,
00135   int hloc);
00136 
00137 static int fp20_siftup (
00138   fp20_heap * h,
00139   int hloc,
00140   int ix)
00141 {
00142   int i = hloc;
00143   int p = fp20_HEAP_UP (i);
00144   EGfp20_t val;
00145 
00146   fp20_EGlpNumInitVar (val);
00147   fp20_EGlpNumCopy (val, h->key[ix]);
00148 
00149   while (i > 0 && fp20_EGlpNumIsLess (h->key[h->entry[p]], val))
00150   {
00151     h->entry[i] = h->entry[p];
00152     h->loc[h->entry[i]] = i;
00153     i = p;
00154     p = fp20_HEAP_UP (p);
00155   }
00156   h->entry[i] = ix;
00157   h->loc[ix] = i;
00158   ILL_IFTRACE2 ("%s:%la:%d:%d:%d\n", __func__, fp20_EGlpNumToLf (val), hloc, ix, i);
00159   fp20_EGlpNumClearVar (val);
00160   return i;
00161 }
00162 
00163 static int fp20_siftdown (
00164   fp20_heap * h,
00165   int hloc,
00166   int ix)
00167 {
00168   int i = hloc;
00169   int c = fp20_maxchild (h, i);
00170   EGfp20_t val;
00171 
00172   fp20_EGlpNumInitVar (val);
00173   fp20_EGlpNumCopy (val, h->key[ix]);
00174   ILL_IFTRACE2 ("%s:%d:%d:%d:%la", __func__, hloc, ix, c, fp20_EGlpNumToLf (val));
00175 
00176   while (c != -1 && fp20_EGlpNumIsLess (val, h->key[h->entry[c]]))
00177   {
00178     h->entry[i] = h->entry[c];
00179     h->loc[h->entry[i]] = i;
00180     i = c;
00181     c = fp20_maxchild (h, c);
00182   }
00183   h->entry[i] = ix;
00184   h->loc[ix] = i;
00185   fp20_EGlpNumClearVar (val);
00186   ILL_IFTRACE2 ("%s:%d:%d\n", __func__, ix, i);
00187   return i;
00188 }
00189 
00190 //extern EGfp20_t fp20_ILL_MINDOUBLE;
00191 static int fp20_maxchild (
00192   fp20_heap * h,
00193   int hloc)
00194 {
00195   int i;
00196   int mc = -1;
00197   int hmin = fp20_HEAP_D * hloc + 1;
00198   int hmax = fp20_HEAP_D * hloc + fp20_HEAP_D;
00199   EGfp20_t val;
00200 
00201   fp20_EGlpNumInitVar (val);
00202   fp20_EGlpNumCopy (val, fp20_ILL_MINDOUBLE);
00203   ILL_IFTRACE2 (" %s:%d", __func__, hloc);
00204 
00205   for (i = hmin; i <= hmax && i < h->size; i++)
00206     if (fp20_EGlpNumIsLess (val, h->key[h->entry[i]]))
00207     {
00208       fp20_EGlpNumCopy (val, h->key[h->entry[i]]);
00209       mc = i;
00210       ILL_IFTRACE2 (":%d:%la", mc, fp20_EGlpNumToLf (val));
00211     }
00212   fp20_EGlpNumClearVar (val);
00213   ILL_IFTRACE2 ("\n");
00214   return mc;
00215 }
00216 
00217 #if fp20_DEBUG_HEAP > 0
00218 
00219 static void fp20_printheap (
00220   fp20_heap * h)
00221 {
00222   int i;
00223 
00224   printf ("entry (%d): ", h->size);
00225   for (i = 0; i < h->size; i++)
00226     printf ("%d ", h->entry[i]);
00227   printf ("\n loc: ");
00228   for (i = 0; i < h->maxsize; i++)
00229     printf ("%d ", h->loc[i]);
00230   printf ("\n key: ");
00231   for (i = 0; i < h->maxsize; i++)
00232     printf ("%la ", fp20_EGlpNumToLf (h->key[i]));
00233   printf ("\n key(sorted): ");
00234   for (i = 0; i < h->size; i++)
00235     printf ("%la ", fp20_EGlpNumToLf (h->key[h->entry[i]]));
00236   printf ("\n");
00237 }
00238 
00239 static void fp20_heapcheck (
00240   fp20_heap * h)
00241 {
00242   int i, tcnt = 0;
00243 
00244   for (i = 0; i < h->maxsize; i++)
00245   {
00246     if (h->loc[i] < -1)
00247       printf ("error in fp20_heap\n");
00248     else if (h->loc[i] > -1)
00249       tcnt++;
00250   }
00251   if (tcnt != h->size)
00252     printf ("error 3 in fp20_heap\n");
00253 
00254   for (i = 0; i < h->size; i++)
00255   {
00256     if (h->loc[h->entry[i]] != i)
00257       printf ("error 1 in fp20_heap\n");
00258     if (!fp20_EGlpNumIsNeqqZero (h->key[h->entry[i]]))
00259       printf ("error 2 in fp20_heap\n");
00260     if (fp20_EGlpNumIsLess (h->key[h->entry[fp20_HEAP_UP (i)]], h->key[h->entry[i]]))
00261       printf ("error 4 in fp20_heap\n");
00262   }
00263 }
00264 
00265 #endif
00266 
00267 void fp20_ILLheap_insert (
00268   fp20_heap * const h,
00269   int const ix)
00270 {
00271   int i = h->size;
00272 
00273   ILL_IFTRACE ("%s:%d:%la\n", __func__, ix, fp20_EGlpNumToLf (h->key[ix]));
00274 
00275   i = fp20_siftup (h, i, ix);
00276   h->size++;
00277 
00278 #if fp20_DEBUG_HEAP > 0
00279   fp20_heapcheck (h);
00280 #endif
00281 #if fp20_DEBUG_HEAP > 1
00282   fp20_printheap (h);
00283 #endif
00284 }
00285 
00286 void fp20_ILLheap_modify (
00287   fp20_heap * const h,
00288   int const ix)
00289 {
00290   int i = h->loc[ix];
00291   int pi = i;
00292 
00293   ILL_IFTRACE ("%s:%d\n", __func__, ix);
00294 
00295   if (h->loc[ix] == -1)
00296     return;
00297   i = fp20_siftup (h, i, ix);
00298   if (pi == i)
00299     i = fp20_siftdown (h, i, ix);
00300 
00301 #if fp20_DEBUG_HEAP > 0
00302   fp20_heapcheck (h);
00303 #endif
00304 #if fp20_DEBUG_HEAP > 1
00305   fp20_printheap (h);
00306 #endif
00307 }
00308 
00309 void fp20_ILLheap_delete (
00310   fp20_heap * const h,
00311   int const ix)
00312 {
00313   int i = h->loc[ix];
00314   int pi = i;
00315   int nix = h->entry[h->size - 1];
00316 
00317   ILL_IFTRACE ("%s:%d:%d:%d\n", __func__, ix, nix, pi);
00318 
00319   h->loc[ix] = -1;
00320   h->size--;
00321   if (nix == ix)
00322   {
00323 #if fp20_DEBUG_HEAP > 0
00324     fp20_heapcheck (h);
00325 #endif
00326 #if fp20_DEBUG_HEAP > 1
00327     fp20_printheap (h);
00328 #endif
00329     return;
00330   }
00331 
00332   h->entry[i] = nix;
00333   h->loc[nix] = i;
00334 
00335   i = fp20_siftup (h, i, nix);
00336   ILL_IFTRACE ("%s:%d:%d:%d:%d\n", __func__, ix, nix, pi, i);
00337   if (pi == i)
00338     fp20_siftdown (h, i, nix);
00339 
00340 #if fp20_DEBUG_HEAP > 0
00341   fp20_heapcheck (h);
00342 #endif
00343 #if fp20_DEBUG_HEAP > 1
00344   fp20_printheap (h);
00345 #endif
00346 }
00347 
00348 int fp20_ILLheap_findmin (
00349   fp20_heap * const h)
00350 {
00351   if (h->hexist == 0 || h->size <= 0)
00352     return -1;
00353   return h->entry[0];
00354 }
00355 
00356 void fp20_ILLheap_init (
00357   fp20_heap * const h)
00358 {
00359   h->entry = NULL;
00360   h->loc = NULL;
00361   h->key = NULL;
00362   h->hexist = 0;
00363 }
00364 
00365 int fp20_ILLheap_build (
00366   fp20_heap * const h,
00367   int const nelems,
00368   EGfp20_t * key)
00369 {
00370   int rval = 0;
00371   int i, n = 0;
00372 
00373   ILL_IFTRACE ("%s:%d\n", __func__, nelems);
00374 
00375   h->hexist = 1;
00376   h->size = 0;
00377   h->maxsize = nelems;
00378   h->key = key;
00379   ILL_SAFE_MALLOC (h->entry, nelems, int);
00380   ILL_SAFE_MALLOC (h->loc, nelems, int);
00381 
00382   for (i = 0; i < nelems; i++)
00383   {
00384     if (fp20_EGlpNumIsGreatZero (key[i]))
00385     {
00386       h->entry[n] = i;
00387       h->loc[i] = n;
00388       n++;
00389     }
00390     else
00391       h->loc[i] = -1;
00392   }
00393   h->size = n;
00394   for (i = n - 1; i >= 0; i--)
00395   {
00396     ILL_IFTRACE2 ("insert %la\n", fp20_EGlpNumToLf (h->key[h->entry[i]]));
00397     fp20_siftdown (h, i, h->entry[i]);
00398   }
00399 
00400 #if fp20_DEBUG_HEAP > 0
00401   fp20_heapcheck (h);
00402 #endif
00403 #if fp20_DEBUG_HEAP > 1
00404   fp20_printheap (h);
00405 #endif
00406 
00407 CLEANUP:
00408   if (rval)
00409     fp20_ILLheap_free (h);
00410   ILL_RETURN (rval, "fp20_ILLheap_init");
00411 }
00412 
00413 void fp20_ILLheap_free (
00414   fp20_heap * const h)
00415 {
00416   if (h->hexist)
00417   {
00418     ILL_IFFREE (h->entry, int);
00419     ILL_IFFREE (h->loc, int);
00420 
00421     h->hexist = 0;
00422     h->maxsize = 0;
00423     h->size = 0;
00424   }
00425 }
00426 
00427 
00428 /****************************************************************************/
00429 /*                                                                          */
00430 /*                          matrix                                          */
00431 /*                                                                          */
00432 /*  Written by:  Applegate, Cook, Dash                                      */
00433 /*  Date:                                                                   */
00434 /*                                                                          */
00435 /*    EXPORTED FUNCTIONS:                                                   */
00436 /*                                                                          */
00437 /****************************************************************************/
00438 
00439 void fp20_ILLmatrix_init (
00440   fp20_ILLmatrix * A)
00441 {
00442   if (A)
00443   {
00444     A->matval = 0;
00445     A->matcnt = 0;
00446     A->matbeg = 0;
00447     A->matind = 0;
00448     A->matcols = 0;
00449     A->matcolsize = 0;
00450     A->matrows = 0;
00451     A->matsize = 0;
00452     A->matfree = 0;
00453   }
00454 }
00455 
00456 void fp20_ILLmatrix_free (
00457   fp20_ILLmatrix * A)
00458 {
00459   if (A)
00460   {
00461     fp20_EGlpNumFreeArray (A->matval);
00462     ILL_IFFREE (A->matcnt, int);
00463     ILL_IFFREE (A->matbeg, int);
00464     ILL_IFFREE (A->matind, int);
00465 
00466     fp20_ILLmatrix_init (A);
00467   }
00468 }
00469 
00470 void fp20_ILLmatrix_prt (
00471   EGioFile_t * fd,
00472   fp20_ILLmatrix * A)
00473 {
00474   int j, k;
00475 
00476   if (A == NULL)
00477   {
00478     EGioPrintf (fd, "Matrix %p: empty\n", (void *) A);
00479   }
00480   else
00481   {
00482     EGioPrintf (fd, "Matrix %p: nrows = %d ncols = %d\n",
00483              (void *) A, A->matrows, A->matcols);
00484     for (j = 0; j < A->matcols; j++)
00485     {
00486       EGioPrintf (fd, "col %d: ", j);
00487       for (k = A->matbeg[j]; k < A->matbeg[j] + A->matcnt[j]; k++)
00488       {
00489         EGioPrintf (fd, "row %d=%.3f ", A->matind[k], fp20_EGlpNumToLf (A->matval[k]));
00490       }
00491       EGioPrintf (fd, "\n");
00492     }
00493   }
00494 }

Generated on Thu Mar 29 09:32:30 2012 for QSopt_ex by  doxygen 1.4.7