1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/glpios04.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,303 @@
1.4 +/* glpios04.c (operations on sparse vectors) */
1.5 +
1.6 +/***********************************************************************
1.7 +* This code is part of GLPK (GNU Linear Programming Kit).
1.8 +*
1.9 +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
1.10 +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics,
1.11 +* Moscow Aviation Institute, Moscow, Russia. All rights reserved.
1.12 +* E-mail: <mao@gnu.org>.
1.13 +*
1.14 +* GLPK is free software: you can redistribute it and/or modify it
1.15 +* under the terms of the GNU General Public License as published by
1.16 +* the Free Software Foundation, either version 3 of the License, or
1.17 +* (at your option) any later version.
1.18 +*
1.19 +* GLPK is distributed in the hope that it will be useful, but WITHOUT
1.20 +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.21 +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
1.22 +* License for more details.
1.23 +*
1.24 +* You should have received a copy of the GNU General Public License
1.25 +* along with GLPK. If not, see <http://www.gnu.org/licenses/>.
1.26 +***********************************************************************/
1.27 +
1.28 +#include "glpios.h"
1.29 +
1.30 +/***********************************************************************
1.31 +* NAME
1.32 +*
1.33 +* ios_create_vec - create sparse vector
1.34 +*
1.35 +* SYNOPSIS
1.36 +*
1.37 +* #include "glpios.h"
1.38 +* IOSVEC *ios_create_vec(int n);
1.39 +*
1.40 +* DESCRIPTION
1.41 +*
1.42 +* The routine ios_create_vec creates a sparse vector of dimension n,
1.43 +* which initially is a null vector.
1.44 +*
1.45 +* RETURNS
1.46 +*
1.47 +* The routine returns a pointer to the vector created. */
1.48 +
1.49 +IOSVEC *ios_create_vec(int n)
1.50 +{ IOSVEC *v;
1.51 + xassert(n >= 0);
1.52 + v = xmalloc(sizeof(IOSVEC));
1.53 + v->n = n;
1.54 + v->nnz = 0;
1.55 + v->pos = xcalloc(1+n, sizeof(int));
1.56 + memset(&v->pos[1], 0, n * sizeof(int));
1.57 + v->ind = xcalloc(1+n, sizeof(int));
1.58 + v->val = xcalloc(1+n, sizeof(double));
1.59 + return v;
1.60 +}
1.61 +
1.62 +/***********************************************************************
1.63 +* NAME
1.64 +*
1.65 +* ios_check_vec - check that sparse vector has correct representation
1.66 +*
1.67 +* SYNOPSIS
1.68 +*
1.69 +* #include "glpios.h"
1.70 +* void ios_check_vec(IOSVEC *v);
1.71 +*
1.72 +* DESCRIPTION
1.73 +*
1.74 +* The routine ios_check_vec checks that a sparse vector specified by
1.75 +* the parameter v has correct representation.
1.76 +*
1.77 +* NOTE
1.78 +*
1.79 +* Complexity of this operation is O(n). */
1.80 +
1.81 +void ios_check_vec(IOSVEC *v)
1.82 +{ int j, k, nnz;
1.83 + xassert(v->n >= 0);
1.84 + nnz = 0;
1.85 + for (j = v->n; j >= 1; j--)
1.86 + { k = v->pos[j];
1.87 + xassert(0 <= k && k <= v->nnz);
1.88 + if (k != 0)
1.89 + { xassert(v->ind[k] == j);
1.90 + nnz++;
1.91 + }
1.92 + }
1.93 + xassert(v->nnz == nnz);
1.94 + return;
1.95 +}
1.96 +
1.97 +/***********************************************************************
1.98 +* NAME
1.99 +*
1.100 +* ios_get_vj - retrieve component of sparse vector
1.101 +*
1.102 +* SYNOPSIS
1.103 +*
1.104 +* #include "glpios.h"
1.105 +* double ios_get_vj(IOSVEC *v, int j);
1.106 +*
1.107 +* RETURNS
1.108 +*
1.109 +* The routine ios_get_vj returns j-th component of a sparse vector
1.110 +* specified by the parameter v. */
1.111 +
1.112 +double ios_get_vj(IOSVEC *v, int j)
1.113 +{ int k;
1.114 + xassert(1 <= j && j <= v->n);
1.115 + k = v->pos[j];
1.116 + xassert(0 <= k && k <= v->nnz);
1.117 + return (k == 0 ? 0.0 : v->val[k]);
1.118 +}
1.119 +
1.120 +/***********************************************************************
1.121 +* NAME
1.122 +*
1.123 +* ios_set_vj - set/change component of sparse vector
1.124 +*
1.125 +* SYNOPSIS
1.126 +*
1.127 +* #include "glpios.h"
1.128 +* void ios_set_vj(IOSVEC *v, int j, double val);
1.129 +*
1.130 +* DESCRIPTION
1.131 +*
1.132 +* The routine ios_set_vj assigns val to j-th component of a sparse
1.133 +* vector specified by the parameter v. */
1.134 +
1.135 +void ios_set_vj(IOSVEC *v, int j, double val)
1.136 +{ int k;
1.137 + xassert(1 <= j && j <= v->n);
1.138 + k = v->pos[j];
1.139 + if (val == 0.0)
1.140 + { if (k != 0)
1.141 + { /* remove j-th component */
1.142 + v->pos[j] = 0;
1.143 + if (k < v->nnz)
1.144 + { v->pos[v->ind[v->nnz]] = k;
1.145 + v->ind[k] = v->ind[v->nnz];
1.146 + v->val[k] = v->val[v->nnz];
1.147 + }
1.148 + v->nnz--;
1.149 + }
1.150 + }
1.151 + else
1.152 + { if (k == 0)
1.153 + { /* create j-th component */
1.154 + k = ++(v->nnz);
1.155 + v->pos[j] = k;
1.156 + v->ind[k] = j;
1.157 + }
1.158 + v->val[k] = val;
1.159 + }
1.160 + return;
1.161 +}
1.162 +
1.163 +/***********************************************************************
1.164 +* NAME
1.165 +*
1.166 +* ios_clear_vec - set all components of sparse vector to zero
1.167 +*
1.168 +* SYNOPSIS
1.169 +*
1.170 +* #include "glpios.h"
1.171 +* void ios_clear_vec(IOSVEC *v);
1.172 +*
1.173 +* DESCRIPTION
1.174 +*
1.175 +* The routine ios_clear_vec sets all components of a sparse vector
1.176 +* specified by the parameter v to zero. */
1.177 +
1.178 +void ios_clear_vec(IOSVEC *v)
1.179 +{ int k;
1.180 + for (k = 1; k <= v->nnz; k++)
1.181 + v->pos[v->ind[k]] = 0;
1.182 + v->nnz = 0;
1.183 + return;
1.184 +}
1.185 +
1.186 +/***********************************************************************
1.187 +* NAME
1.188 +*
1.189 +* ios_clean_vec - remove zero or small components from sparse vector
1.190 +*
1.191 +* SYNOPSIS
1.192 +*
1.193 +* #include "glpios.h"
1.194 +* void ios_clean_vec(IOSVEC *v, double eps);
1.195 +*
1.196 +* DESCRIPTION
1.197 +*
1.198 +* The routine ios_clean_vec removes zero components and components
1.199 +* whose magnitude is less than eps from a sparse vector specified by
1.200 +* the parameter v. If eps is 0.0, only zero components are removed. */
1.201 +
1.202 +void ios_clean_vec(IOSVEC *v, double eps)
1.203 +{ int k, nnz;
1.204 + nnz = 0;
1.205 + for (k = 1; k <= v->nnz; k++)
1.206 + { if (fabs(v->val[k]) == 0.0 || fabs(v->val[k]) < eps)
1.207 + { /* remove component */
1.208 + v->pos[v->ind[k]] = 0;
1.209 + }
1.210 + else
1.211 + { /* keep component */
1.212 + nnz++;
1.213 + v->pos[v->ind[k]] = nnz;
1.214 + v->ind[nnz] = v->ind[k];
1.215 + v->val[nnz] = v->val[k];
1.216 + }
1.217 + }
1.218 + v->nnz = nnz;
1.219 + return;
1.220 +}
1.221 +
1.222 +/***********************************************************************
1.223 +* NAME
1.224 +*
1.225 +* ios_copy_vec - copy sparse vector (x := y)
1.226 +*
1.227 +* SYNOPSIS
1.228 +*
1.229 +* #include "glpios.h"
1.230 +* void ios_copy_vec(IOSVEC *x, IOSVEC *y);
1.231 +*
1.232 +* DESCRIPTION
1.233 +*
1.234 +* The routine ios_copy_vec copies a sparse vector specified by the
1.235 +* parameter y to a sparse vector specified by the parameter x. */
1.236 +
1.237 +void ios_copy_vec(IOSVEC *x, IOSVEC *y)
1.238 +{ int j;
1.239 + xassert(x != y);
1.240 + xassert(x->n == y->n);
1.241 + ios_clear_vec(x);
1.242 + x->nnz = y->nnz;
1.243 + memcpy(&x->ind[1], &y->ind[1], x->nnz * sizeof(int));
1.244 + memcpy(&x->val[1], &y->val[1], x->nnz * sizeof(double));
1.245 + for (j = 1; j <= x->nnz; j++)
1.246 + x->pos[x->ind[j]] = j;
1.247 + return;
1.248 +}
1.249 +
1.250 +/***********************************************************************
1.251 +* NAME
1.252 +*
1.253 +* ios_linear_comb - compute linear combination (x := x + a * y)
1.254 +*
1.255 +* SYNOPSIS
1.256 +*
1.257 +* #include "glpios.h"
1.258 +* void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y);
1.259 +*
1.260 +* DESCRIPTION
1.261 +*
1.262 +* The routine ios_linear_comb computes the linear combination
1.263 +*
1.264 +* x := x + a * y,
1.265 +*
1.266 +* where x and y are sparse vectors, a is a scalar. */
1.267 +
1.268 +void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y)
1.269 +{ int j, k;
1.270 + double xj, yj;
1.271 + xassert(x != y);
1.272 + xassert(x->n == y->n);
1.273 + for (k = 1; k <= y->nnz; k++)
1.274 + { j = y->ind[k];
1.275 + xj = ios_get_vj(x, j);
1.276 + yj = y->val[k];
1.277 + ios_set_vj(x, j, xj + a * yj);
1.278 + }
1.279 + return;
1.280 +}
1.281 +
1.282 +/***********************************************************************
1.283 +* NAME
1.284 +*
1.285 +* ios_delete_vec - delete sparse vector
1.286 +*
1.287 +* SYNOPSIS
1.288 +*
1.289 +* #include "glpios.h"
1.290 +* void ios_delete_vec(IOSVEC *v);
1.291 +*
1.292 +* DESCRIPTION
1.293 +*
1.294 +* The routine ios_delete_vec deletes a sparse vector specified by the
1.295 +* parameter v freeing all the memory allocated to this object. */
1.296 +
1.297 +void ios_delete_vec(IOSVEC *v)
1.298 +{ /* delete sparse vector */
1.299 + xfree(v->pos);
1.300 + xfree(v->ind);
1.301 + xfree(v->val);
1.302 + xfree(v);
1.303 + return;
1.304 +}
1.305 +
1.306 +/* eof */