1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
/* sva.h (sparse vector area) */
/***********************************************************************
* This code is part of GLPK (GNU Linear Programming Kit).
*
* Copyright (C) 2012-2013 Andrew Makhorin, Department for Applied
* Informatics, Moscow Aviation Institute, Moscow, Russia. All rights
* reserved. E-mail: <mao@gnu.org>.
*
* 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 <http://www.gnu.org/licenses/>.
***********************************************************************/
#ifndef SVA_H
#define SVA_H
/***********************************************************************
* Sparse Vector Area (SVA) is a container for sparse vectors. This
* program object is used mainly on computing factorization, where the
* sparse vectors are rows and columns of sparse matrices.
*
* The SVA storage is a set of locations numbered 1, 2, ..., size,
* where size is the size of SVA, which is the total number of
* locations currently allocated. Each location is identified by its
* pointer p, 1 <= p <= size, and is the pair (ind[p], val[p]), where
* ind[p] and val[p] are, respectively, the index and value fields used
* to store the index and numeric value of a particular vector element.
*
* Each sparse vector is identified by its reference number k,
* 1 <= k <= n, where n is the total number of vectors currently stored
* in SVA, and defined by the triplet (ptr[k], len[k], cap[k]), where:
* ptr[k] is a pointer to the first location of the vector; len[k] is
* the vector length, which is the number of its non-zero elements,
* len[k] >= 0; and cap[k] is the capacity of the vector, which is the
* total number of adjacent locations allocated to that vector,
* cap[k] >= len[k]. Thus, non-zero elements of k-th vector are stored
* in locations ptr[k], ptr[k]+1, ..., ptr[k]+len[k]-1, and locations
* ptr[k]+len[k], ptr[k]+len[k]+1, ..., ptr[k]+cap[k]-1 are reserved.
*
* The SVA storage is divided into three parts as follows:
*
* Locations 1, 2, ..., m_ptr-1 constitute the left (dynamic) part of
* SVA. This part is used to store vectors, whose capacity may change.
* Note that all vectors stored in the left part are also included in
* a doubly linked list, where they are ordered by increasing their
* pointers ptr[k] (this list is needed for efficient implementation
* of the garbage collector used to defragment the left part of SVA);
*
* Locations m_ptr, m_ptr+1, ..., r_ptr-1 are free and constitute the
* middle (free) part of SVA.
*
* Locations r_ptr, r_ptr+1, ..., size constitute the right (static)
* part of SVA. This part is used to store vectors, whose capacity is
* not changed. */
typedef struct SVA SVA;
struct SVA
{ /* sparse vector area */
int n_max;
/* maximal value of n (enlarged automatically) */
int n;
/* number of currently allocated vectors, 0 <= n <= n_max */
int *ptr; /* int ptr[1+n_max]; */
/* ptr[0] is not used;
* ptr[k], 1 <= i <= n, is pointer to first location of k-th
* vector in the arrays ind and val */
int *len; /* int len[1+n_max]; */
/* len[0] is not used;
* len[k], 1 <= k <= n, is length of k-th vector, len[k] >= 0 */
int *cap; /* int cap[1+n_max]; */
/* cap[0] is not used;
* cap[k], 1 <= k <= n, is capacity of k-th vector (the number
* of adjacent locations allocated to it), cap[k] >= len[k] */
/* NOTE: if cap[k] = 0, then ptr[k] = 0 and len[k] = 0 */
int size;
/* total number of locations in SVA */
int m_ptr, r_ptr;
/* partitioning pointers that define the left, middle, and right
* parts of SVA (see above); 1 <= m_ptr <= r_ptr <= size+1 */
int head;
/* number of first (leftmost) vector in the linked list */
int tail;
/* number of last (rightmost) vector in the linked list */
int *prev; /* int prev[1+n_max]; */
/* prev[0] is not used;
* prev[k] is number of vector which precedes k-th vector in the
* linked list;
* prev[k] < 0 means that k-th vector is not in the list */
int *next; /* int next[1+n_max]; */
/* next[0] is not used;
* next[k] is number of vector which succedes k-th vector in the
* linked list;
* next[k] < 0 means that k-th vector is not in the list */
/* NOTE: only vectors having non-zero capacity and stored in the
* left part of SVA are included in this linked list */
int *ind; /* int ind[1+size]; */
/* ind[0] is not used;
* ind[p], 1 <= p <= size, is index field of location p */
double *val; /* double val[1+size]; */
/* val[0] is not used;
* val[p], 1 <= p <= size, is value field of location p */
#if 1
int talky;
/* option to enable talky mode */
#endif
};
#define sva_create_area _glp_sva_create_area
SVA *sva_create_area(int n_max, int size);
/* create sparse vector area (SVA) */
#define sva_alloc_vecs _glp_sva_alloc_vecs
int sva_alloc_vecs(SVA *sva, int nnn);
/* allocate new vectors in SVA */
#define sva_resize_area _glp_sva_resize_area
void sva_resize_area(SVA *sva, int delta);
/* change size of SVA storage */
#define sva_defrag_area _glp_sva_defrag_area
void sva_defrag_area(SVA *sva);
/* defragment left part of SVA */
#define sva_more_space _glp_sva_more_space
void sva_more_space(SVA *sva, int m_size);
/* increase size of middle (free) part of SVA */
#define sva_enlarge_cap _glp_sva_enlarge_cap
void sva_enlarge_cap(SVA *sva, int k, int new_cap, int skip);
/* enlarge capacity of specified vector */
#define sva_reserve_cap _glp_sva_reserve_cap
void sva_reserve_cap(SVA *sva, int k, int new_cap);
/* reserve locations for specified vector */
#define sva_make_static _glp_sva_make_static
void sva_make_static(SVA *sva, int k);
/* relocate specified vector to right part of SVA */
#define sva_check_area _glp_sva_check_area
void sva_check_area(SVA *sva);
/* check sparse vector area (SVA) */
#define sva_delete_area _glp_sva_delete_area
void sva_delete_area(SVA *sva);
/* delete sparse vector area (SVA) */
#endif
/* eof */
|
