diff -r d59bea55db9b -r c445c931472f src/glpios04.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/glpios04.c Mon Dec 06 13:09:21 2010 +0100 @@ -0,0 +1,303 @@ +/* glpios04.c (operations on sparse vectors) */ + +/*********************************************************************** +* This code is part of GLPK (GNU Linear Programming Kit). +* +* Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, +* 2009, 2010 Andrew Makhorin, Department for Applied Informatics, +* Moscow Aviation Institute, Moscow, Russia. All rights reserved. +* E-mail: . +* +* GLPK is free software: you can redistribute it and/or modify it +* under the terms of the GNU General Public License as published by +* the Free Software Foundation, either version 3 of the License, or +* (at your option) any later version. +* +* GLPK is distributed in the hope that it will be useful, but WITHOUT +* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public +* License for more details. +* +* You should have received a copy of the GNU General Public License +* along with GLPK. If not, see . +***********************************************************************/ + +#include "glpios.h" + +/*********************************************************************** +* NAME +* +* ios_create_vec - create sparse vector +* +* SYNOPSIS +* +* #include "glpios.h" +* IOSVEC *ios_create_vec(int n); +* +* DESCRIPTION +* +* The routine ios_create_vec creates a sparse vector of dimension n, +* which initially is a null vector. +* +* RETURNS +* +* The routine returns a pointer to the vector created. */ + +IOSVEC *ios_create_vec(int n) +{ IOSVEC *v; + xassert(n >= 0); + v = xmalloc(sizeof(IOSVEC)); + v->n = n; + v->nnz = 0; + v->pos = xcalloc(1+n, sizeof(int)); + memset(&v->pos[1], 0, n * sizeof(int)); + v->ind = xcalloc(1+n, sizeof(int)); + v->val = xcalloc(1+n, sizeof(double)); + return v; +} + +/*********************************************************************** +* NAME +* +* ios_check_vec - check that sparse vector has correct representation +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_check_vec(IOSVEC *v); +* +* DESCRIPTION +* +* The routine ios_check_vec checks that a sparse vector specified by +* the parameter v has correct representation. +* +* NOTE +* +* Complexity of this operation is O(n). */ + +void ios_check_vec(IOSVEC *v) +{ int j, k, nnz; + xassert(v->n >= 0); + nnz = 0; + for (j = v->n; j >= 1; j--) + { k = v->pos[j]; + xassert(0 <= k && k <= v->nnz); + if (k != 0) + { xassert(v->ind[k] == j); + nnz++; + } + } + xassert(v->nnz == nnz); + return; +} + +/*********************************************************************** +* NAME +* +* ios_get_vj - retrieve component of sparse vector +* +* SYNOPSIS +* +* #include "glpios.h" +* double ios_get_vj(IOSVEC *v, int j); +* +* RETURNS +* +* The routine ios_get_vj returns j-th component of a sparse vector +* specified by the parameter v. */ + +double ios_get_vj(IOSVEC *v, int j) +{ int k; + xassert(1 <= j && j <= v->n); + k = v->pos[j]; + xassert(0 <= k && k <= v->nnz); + return (k == 0 ? 0.0 : v->val[k]); +} + +/*********************************************************************** +* NAME +* +* ios_set_vj - set/change component of sparse vector +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_set_vj(IOSVEC *v, int j, double val); +* +* DESCRIPTION +* +* The routine ios_set_vj assigns val to j-th component of a sparse +* vector specified by the parameter v. */ + +void ios_set_vj(IOSVEC *v, int j, double val) +{ int k; + xassert(1 <= j && j <= v->n); + k = v->pos[j]; + if (val == 0.0) + { if (k != 0) + { /* remove j-th component */ + v->pos[j] = 0; + if (k < v->nnz) + { v->pos[v->ind[v->nnz]] = k; + v->ind[k] = v->ind[v->nnz]; + v->val[k] = v->val[v->nnz]; + } + v->nnz--; + } + } + else + { if (k == 0) + { /* create j-th component */ + k = ++(v->nnz); + v->pos[j] = k; + v->ind[k] = j; + } + v->val[k] = val; + } + return; +} + +/*********************************************************************** +* NAME +* +* ios_clear_vec - set all components of sparse vector to zero +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_clear_vec(IOSVEC *v); +* +* DESCRIPTION +* +* The routine ios_clear_vec sets all components of a sparse vector +* specified by the parameter v to zero. */ + +void ios_clear_vec(IOSVEC *v) +{ int k; + for (k = 1; k <= v->nnz; k++) + v->pos[v->ind[k]] = 0; + v->nnz = 0; + return; +} + +/*********************************************************************** +* NAME +* +* ios_clean_vec - remove zero or small components from sparse vector +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_clean_vec(IOSVEC *v, double eps); +* +* DESCRIPTION +* +* The routine ios_clean_vec removes zero components and components +* whose magnitude is less than eps from a sparse vector specified by +* the parameter v. If eps is 0.0, only zero components are removed. */ + +void ios_clean_vec(IOSVEC *v, double eps) +{ int k, nnz; + nnz = 0; + for (k = 1; k <= v->nnz; k++) + { if (fabs(v->val[k]) == 0.0 || fabs(v->val[k]) < eps) + { /* remove component */ + v->pos[v->ind[k]] = 0; + } + else + { /* keep component */ + nnz++; + v->pos[v->ind[k]] = nnz; + v->ind[nnz] = v->ind[k]; + v->val[nnz] = v->val[k]; + } + } + v->nnz = nnz; + return; +} + +/*********************************************************************** +* NAME +* +* ios_copy_vec - copy sparse vector (x := y) +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_copy_vec(IOSVEC *x, IOSVEC *y); +* +* DESCRIPTION +* +* The routine ios_copy_vec copies a sparse vector specified by the +* parameter y to a sparse vector specified by the parameter x. */ + +void ios_copy_vec(IOSVEC *x, IOSVEC *y) +{ int j; + xassert(x != y); + xassert(x->n == y->n); + ios_clear_vec(x); + x->nnz = y->nnz; + memcpy(&x->ind[1], &y->ind[1], x->nnz * sizeof(int)); + memcpy(&x->val[1], &y->val[1], x->nnz * sizeof(double)); + for (j = 1; j <= x->nnz; j++) + x->pos[x->ind[j]] = j; + return; +} + +/*********************************************************************** +* NAME +* +* ios_linear_comb - compute linear combination (x := x + a * y) +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y); +* +* DESCRIPTION +* +* The routine ios_linear_comb computes the linear combination +* +* x := x + a * y, +* +* where x and y are sparse vectors, a is a scalar. */ + +void ios_linear_comb(IOSVEC *x, double a, IOSVEC *y) +{ int j, k; + double xj, yj; + xassert(x != y); + xassert(x->n == y->n); + for (k = 1; k <= y->nnz; k++) + { j = y->ind[k]; + xj = ios_get_vj(x, j); + yj = y->val[k]; + ios_set_vj(x, j, xj + a * yj); + } + return; +} + +/*********************************************************************** +* NAME +* +* ios_delete_vec - delete sparse vector +* +* SYNOPSIS +* +* #include "glpios.h" +* void ios_delete_vec(IOSVEC *v); +* +* DESCRIPTION +* +* The routine ios_delete_vec deletes a sparse vector specified by the +* parameter v freeing all the memory allocated to this object. */ + +void ios_delete_vec(IOSVEC *v) +{ /* delete sparse vector */ + xfree(v->pos); + xfree(v->ind); + xfree(v->val); + xfree(v); + return; +} + +/* eof */