lemon-project-template-glpk

comparison deps/glpk/src/glpios04.c @ 9:33de93886c88

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