lemon-project-template-glpk

annotate deps/glpk/src/glpios04.c @ 11:4fc6ad2fb8a6

find changesets by author, revision, files, or words in the commit message
Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
rev   line source
alpar@9 1 /* glpios04.c (operations on sparse vectors) */
alpar@9 2
alpar@9 3 /***********************************************************************
alpar@9 4 * This code is part of GLPK (GNU Linear Programming Kit).
alpar@9 5 *
alpar@9 6 * Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
alpar@9 7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,
alpar@9 8 * Moscow Aviation Institute, Moscow, Russia. All rights reserved.
alpar@9 9 * E-mail: <mao@gnu.org>.
alpar@9 10 *
alpar@9 11 * GLPK is free software: you can redistribute it and/or modify it
alpar@9 12 * under the terms of the GNU General Public License as published by
alpar@9 13 * the Free Software Foundation, either version 3 of the License, or
alpar@9 14 * (at your option) any later version.
alpar@9 15 *
alpar@9 16 * GLPK is distributed in the hope that it will be useful, but WITHOUT
alpar@9 17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
alpar@9 18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
alpar@9 19 * License for more details.
alpar@9 20 *
alpar@9 21 * You should have received a copy of the GNU General Public License
alpar@9 22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
alpar@9 23 ***********************************************************************/
alpar@9 24
alpar@9 25 #include "glpios.h"
alpar@9 26
alpar@9 27 /***********************************************************************
alpar@9 28 * NAME
alpar@9 29 *
alpar@9 30 * ios_create_vec - create sparse vector
alpar@9 31 *
alpar@9 32 * SYNOPSIS
alpar@9 33 *
alpar@9 34 * #include "glpios.h"
alpar@9 35 * IOSVEC *ios_create_vec(int n);
alpar@9 36 *
alpar@9 37 * DESCRIPTION
alpar@9 38 *
alpar@9 39 * The routine ios_create_vec creates a sparse vector of dimension n,
alpar@9 40 * which initially is a null vector.
alpar@9 41 *
alpar@9 42 * RETURNS
alpar@9 43 *
alpar@9 44 * The routine returns a pointer to the vector created. */
alpar@9 45
alpar@9 46 IOSVEC *ios_create_vec(int n)
alpar@9 47 { IOSVEC *v;
alpar@9 48 xassert(n >= 0);
alpar@9 49 v = xmalloc(sizeof(IOSVEC));
alpar@9 50 v->n = n;
alpar@9 51 v->nnz = 0;
alpar@9 52 v->pos = xcalloc(1+n, sizeof(int));
alpar@9 53 memset(&v->pos[1], 0, n * sizeof(int));
alpar@9 54 v->ind = xcalloc(1+n, sizeof(int));
alpar@9 55 v->val = xcalloc(1+n, sizeof(double));
alpar@9 56 return v;
alpar@9 57 }
alpar@9 58
alpar@9 59 /***********************************************************************
alpar@9 60 * NAME
alpar@9 61 *
alpar@9 62 * ios_check_vec - check that sparse vector has correct representation
alpar@9 63 *
alpar@9 64 * SYNOPSIS
alpar@9 65 *
alpar@9 66 * #include "glpios.h"
alpar@9 67 * void ios_check_vec(IOSVEC *v);
alpar@9 68 *
alpar@9 69 * DESCRIPTION
alpar@9 70 *
alpar@9 71 * The routine ios_check_vec checks that a sparse vector specified by
alpar@9 72 * the parameter v has correct representation.
alpar@9 73 *
alpar@9 74 * NOTE
alpar@9 75 *
alpar@9 76 * Complexity of this operation is O(n). */
alpar@9 77
alpar@9 78 void ios_check_vec(IOSVEC *v)
alpar@9 79 { int j, k, nnz;
alpar@9 80 xassert(v->n >= 0);
alpar@9 81 nnz = 0;
alpar@9 82 for (j = v->n; j >= 1; j--)
alpar@9 83 { k = v->pos[j];
alpar@9 84 xassert(0 <= k && k <= v->nnz);
alpar@9 85 if (k != 0)
alpar@9 86 { xassert(v->ind[k] == j);
alpar@9 87 nnz++;
alpar@9 88 }
alpar@9 89 }
alpar@9 90 xassert(v->nnz == nnz);
alpar@9 91 return;
alpar@9 92 }
alpar@9 93
alpar@9 94 /***********************************************************************
alpar@9 95 * NAME
alpar@9 96 *
alpar@9 97 * ios_get_vj - retrieve component of sparse vector
alpar@9 98 *
alpar@9 99 * SYNOPSIS
alpar@9 100 *
alpar@9 101 * #include "glpios.h"
alpar@9 102 * double ios_get_vj(IOSVEC *v, int j);
alpar@9 103 *
alpar@9 104 * RETURNS
alpar@9 105 *
alpar@9 106 * The routine ios_get_vj returns j-th component of a sparse vector
alpar@9 107 * specified by the parameter v. */
alpar@9 108
alpar@9 109 double ios_get_vj(IOSVEC *v, int j)
alpar@9 110 { int k;
alpar@9 111 xassert(1 <= j && j <= v->n);
alpar@9 112 k = v->pos[j];
alpar@9 113 xassert(0 <= k && k <= v->nnz);
alpar@9 114 return (k == 0 ? 0.0 : v->val[k]);
alpar@9 115 }
alpar@9 116
alpar@9 117 /***********************************************************************
alpar@9 118 * NAME
alpar@9 119 *
alpar@9 120 * ios_set_vj - set/change component of sparse vector
alpar@9 121 *
alpar@9 122 * SYNOPSIS
alpar@9 123 *
alpar@9 124 * #include "glpios.h"
alpar@9 125 * void ios_set_vj(IOSVEC *v, int j, double val);
alpar@9 126 *
alpar@9 127 * DESCRIPTION
alpar@9 128 *
alpar@9 129 * The routine ios_set_vj assigns val to j-th component of a sparse
alpar@9 130 * vector specified by the parameter v. */
alpar@9 131
alpar@9 132 void ios_set_vj(IOSVEC *v, int j, double val)
alpar@9 133 { int k;
alpar@9 134 xassert(1 <= j && j <= v->n);
alpar@9 135 k = v->pos[j];
alpar@9 136 if (val == 0.0)
alpar@9 137 { if (k != 0)
alpar@9 138 { /* remove j-th component */
alpar@9 139 v->pos[j] = 0;
alpar@9 140 if (k < v->nnz)
alpar@9 141 { v->pos[v->ind[v->nnz]] = k;
alpar@9 142 v->ind[k] = v->ind[v->nnz];
alpar@9 143 v->val[k] = v->val[v->nnz];
alpar@9 144 }
alpar@9 145 v->nnz--;
alpar@9 146 }
alpar@9 147 }
alpar@9 148 else
alpar@9 149 { if (k == 0)
alpar@9 150 { /* create j-th component */
alpar@9 151 k = ++(v->nnz);
alpar@9 152 v->pos[j] = k;
alpar@9 153 v->ind[k] = j;
alpar@9 154 }
alpar@9 155 v->val[k] = val;
alpar@9 156 }
alpar@9 157 return;
alpar@9 158 }
alpar@9 159
alpar@9 160 /***********************************************************************
alpar@9 161 * NAME
alpar@9 162 *
alpar@9 163 * ios_clear_vec - set all components of sparse vector to zero
alpar@9 164 *
alpar@9 165 * SYNOPSIS
alpar@9 166 *
alpar@9 167 * #include "glpios.h"
alpar@9 168 * void ios_clear_vec(IOSVEC *v);
alpar@9 169 *
alpar@9 170 * DESCRIPTION
alpar@9 171 *
alpar@9 172 * The routine ios_clear_vec sets all components of a sparse vector
alpar@9 173 * specified by the parameter v to zero. */
alpar@9 174
alpar@9 175 void ios_clear_vec(IOSVEC *v)
alpar@9 176 { int k;
alpar@9 177 for (k = 1; k <= v->nnz; k++)
alpar@9 178 v->pos[v->ind[k]] = 0;
alpar@9 179 v->nnz = 0;
alpar@9 180 return;
alpar@9 181 }
alpar@9 182
alpar@9 183 /***********************************************************************
alpar@9 184 * NAME
alpar@9 185 *
alpar@9 186 * ios_clean_vec - remove zero or small components from sparse vector
alpar@9 187 *
alpar@9 188 * SYNOPSIS
alpar@9 189 *
alpar@9 190 * #include "glpios.h"
alpar@9 191 * void ios_clean_vec(IOSVEC *v, double eps);
alpar@9 192 *
alpar@9 193 * DESCRIPTION
alpar@9 194 *
alpar@9 195 * The routine ios_clean_vec removes zero components and components
alpar@9 196 * whose magnitude is less than eps from a sparse vector specified by
alpar@9 197 * the parameter v. If eps is 0.0, only zero components are removed. */
alpar@9 198
alpar@9 199 void ios_clean_vec(IOSVEC *v, double eps)
alpar@9 200 { int k, nnz;
alpar@9 201 nnz = 0;
alpar@9 202 for (k = 1; k <= v->nnz; k++)
alpar@9 203 { if (fabs(v->val[k]) == 0.0 || fabs(v->val[k]) < eps)
alpar@9 204 { /* remove component */
alpar@9 205 v->pos[v->ind[k]] = 0;
alpar@9 206 }
alpar@9 207 else
alpar@9 208 { /* keep component */
alpar@9 209 nnz++;
alpar@9 210 v->pos[v->ind[k]] = nnz;
alpar@9 211 v->ind[nnz] = v->ind[k];
alpar@9 212 v->val[nnz] = v->val[k];
alpar@9 213 }
alpar@9 214 }
alpar@9 215 v->nnz = nnz;
alpar@9 216 return;
alpar@9 217 }
alpar@9 218
alpar@9 219 /***********************************************************************
alpar@9 220 * NAME
alpar@9 221 *
alpar@9 222 * ios_copy_vec - copy sparse vector (x := y)
alpar@9 223 *
alpar@9 224 * SYNOPSIS
alpar@9 225 *
alpar@9 226 * #include "glpios.h"
alpar@9 227 * void ios_copy_vec(IOSVEC *x, IOSVEC *y);
alpar@9 228 *
alpar@9 229 * DESCRIPTION
alpar@9 230 *
alpar@9 231 * The routine ios_copy_vec copies a sparse vector specified by the
alpar@9 232 * parameter y to a sparse vector specified by the parameter x. */
alpar@9 233
alpar@9 234 void ios_copy_vec(IOSVEC *x, IOSVEC *y)
alpar@9 235 { int j;
alpar@9 236 xassert(x != y);
alpar@9 237 xassert(x->n == y->n);
alpar@9 238 ios_clear_vec(x);
alpar@9 239 x->nnz = y->nnz;
alpar@9 240 memcpy(&x->ind[1], &y->ind[1], x->nnz * sizeof(int));
alpar@9 241 memcpy(&x->val[1], &y->val[1], x->nnz * sizeof(double));
alpar@9 242 for (j = 1; j <= x->nnz; j++)
alpar@9 243 x->pos[x->ind[j]] = j;
alpar@9 244 return;
alpar@9 245 }
alpar@9 246
alpar@9 247 /***********************************************************************
alpar@9 248 * NAME
alpar@9 249 *
alpar@9 250 * ios_linear_comb - compute linear combination (x := x + a * y)
alpar@9 251 *
alpar@9 252 * SYNOPSIS
alpar@9 253 *
alpar@9 254 * #include "glpios.h"
alpar@9 255 * void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);
alpar@9 256 *
alpar@9 257 * DESCRIPTION
alpar@9 258 *
alpar@9 259 * The routine ios_linear_comb computes the linear combination
alpar@9 260 *
alpar@9 261 * x := x + a * y,
alpar@9 262 *
alpar@9 263 * where x and y are sparse vectors, a is a scalar. */
alpar@9 264
alpar@9 265 void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y)
alpar@9 266 { int j, k;
alpar@9 267 double xj, yj;
alpar@9 268 xassert(x != y);
alpar@9 269 xassert(x->n == y->n);
alpar@9 270 for (k = 1; k <= y->nnz; k++)
alpar@9 271 { j = y->ind[k];
alpar@9 272 xj = ios_get_vj(x, j);
alpar@9 273 yj = y->val[k];
alpar@9 274 ios_set_vj(x, j, xj + a * yj);
alpar@9 275 }
alpar@9 276 return;
alpar@9 277 }
alpar@9 278
alpar@9 279 /***********************************************************************
alpar@9 280 * NAME
alpar@9 281 *
alpar@9 282 * ios_delete_vec - delete sparse vector
alpar@9 283 *
alpar@9 284 * SYNOPSIS
alpar@9 285 *
alpar@9 286 * #include "glpios.h"
alpar@9 287 * void ios_delete_vec(IOSVEC *v);
alpar@9 288 *
alpar@9 289 * DESCRIPTION
alpar@9 290 *
alpar@9 291 * The routine ios_delete_vec deletes a sparse vector specified by the
alpar@9 292 * parameter v freeing all the memory allocated to this object. */
alpar@9 293
alpar@9 294 void ios_delete_vec(IOSVEC *v)
alpar@9 295 { /* delete sparse vector */
alpar@9 296 xfree(v->pos);
alpar@9 297 xfree(v->ind);
alpar@9 298 xfree(v->val);
alpar@9 299 xfree(v);
alpar@9 300 return;
alpar@9 301 }
alpar@9 302
alpar@9 303 /* eof */