COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/src/glpios04.c @ 10:5545663ca997

subpack-glpk
Last change on this file since 10:5545663ca997 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 7.4 KB
Line 
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
46IOSVEC *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
78void 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
109double 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
132void 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
175void 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
199void 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
234void 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
265void 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
294void 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 */
Note: See TracBrowser for help on using the repository browser.