Coverage for /usr/lib/python3/dist-packages/scipy/sparse/_dok.py: 24%
281 statements
« prev ^ index » next coverage.py v7.4.4, created at 2025-06-14 15:25 +0200
1"""Dictionary Of Keys based matrix"""
3__docformat__ = "restructuredtext en"
5__all__ = ['dok_array', 'dok_matrix', 'isspmatrix_dok']
7import itertools
8import numpy as np
10from ._matrix import spmatrix, _array_doc_to_matrix
11from ._base import _spbase, sparray, issparse
12from ._index import IndexMixin
13from ._sputils import (isdense, getdtype, isshape, isintlike, isscalarlike,
14 upcast, upcast_scalar, check_shape)
16try:
17 from operator import isSequenceType as _is_sequence
18except ImportError:
19 def _is_sequence(x):
20 return (hasattr(x, '__len__') or hasattr(x, '__next__')
21 or hasattr(x, 'next'))
24class _dok_base(_spbase, IndexMixin, dict):
25 """
26 Dictionary Of Keys based sparse matrix.
28 This is an efficient structure for constructing sparse
29 matrices incrementally.
31 This can be instantiated in several ways:
32 dok_array(D)
33 with a dense matrix, D
35 dok_array(S)
36 with a sparse matrix, S
38 dok_array((M,N), [dtype])
39 create the matrix with initial shape (M,N)
40 dtype is optional, defaulting to dtype='d'
42 Attributes
43 ----------
44 dtype : dtype
45 Data type of the matrix
46 shape : 2-tuple
47 Shape of the matrix
48 ndim : int
49 Number of dimensions (this is always 2)
50 nnz
51 Number of nonzero elements
53 Notes
54 -----
56 Sparse matrices can be used in arithmetic operations: they support
57 addition, subtraction, multiplication, division, and matrix power.
59 Allows for efficient O(1) access of individual elements.
60 Duplicates are not allowed.
61 Can be efficiently converted to a coo_matrix once constructed.
63 Examples
64 --------
65 >>> import numpy as np
66 >>> from scipy.sparse import dok_array
67 >>> S = dok_array((5, 5), dtype=np.float32)
68 >>> for i in range(5):
69 ... for j in range(5):
70 ... S[i, j] = i + j # Update element
72 """
73 _format = 'dok'
75 def __init__(self, arg1, shape=None, dtype=None, copy=False):
76 dict.__init__(self)
77 _spbase.__init__(self)
79 self.dtype = getdtype(dtype, default=float)
80 if isinstance(arg1, tuple) and isshape(arg1): # (M,N)
81 M, N = arg1
82 self._shape = check_shape((M, N))
83 elif issparse(arg1): # Sparse ctor
84 if arg1.format == self.format and copy:
85 arg1 = arg1.copy()
86 else:
87 arg1 = arg1.todok()
89 if dtype is not None:
90 arg1 = arg1.astype(dtype, copy=False)
92 dict.update(self, arg1)
93 self._shape = check_shape(arg1.shape)
94 self.dtype = arg1.dtype
95 else: # Dense ctor
96 try:
97 arg1 = np.asarray(arg1)
98 except Exception as e:
99 raise TypeError('Invalid input format.') from e
101 if len(arg1.shape) != 2:
102 raise TypeError('Expected rank <=2 dense array or matrix.')
104 d = self._coo_container(arg1, dtype=dtype).todok()
105 dict.update(self, d)
106 self._shape = check_shape(arg1.shape)
107 self.dtype = d.dtype
109 def update(self, val):
110 # Prevent direct usage of update
111 raise NotImplementedError("Direct modification to dok_array element "
112 "is not allowed.")
114 def _update(self, data):
115 """An update method for dict data defined for direct access to
116 `dok_array` data. Main purpose is to be used for effcient conversion
117 from other _spbase classes. Has no checking if `data` is valid."""
118 return dict.update(self, data)
120 def _getnnz(self, axis=None):
121 if axis is not None:
122 raise NotImplementedError("_getnnz over an axis is not implemented "
123 "for DOK format.")
124 return dict.__len__(self)
126 def count_nonzero(self):
127 return sum(x != 0 for x in self.values())
129 _getnnz.__doc__ = _spbase._getnnz.__doc__
130 count_nonzero.__doc__ = _spbase.count_nonzero.__doc__
132 def __len__(self):
133 return dict.__len__(self)
135 def get(self, key, default=0.):
136 """This overrides the dict.get method, providing type checking
137 but otherwise equivalent functionality.
138 """
139 try:
140 i, j = key
141 assert isintlike(i) and isintlike(j)
142 except (AssertionError, TypeError, ValueError) as e:
143 raise IndexError('Index must be a pair of integers.') from e
144 if (i < 0 or i >= self.shape[0] or j < 0 or j >= self.shape[1]):
145 raise IndexError('Index out of bounds.')
146 return dict.get(self, key, default)
148 def _get_intXint(self, row, col):
149 return dict.get(self, (row, col), self.dtype.type(0))
151 def _get_intXslice(self, row, col):
152 return self._get_sliceXslice(slice(row, row+1), col)
154 def _get_sliceXint(self, row, col):
155 return self._get_sliceXslice(row, slice(col, col+1))
157 def _get_sliceXslice(self, row, col):
158 row_start, row_stop, row_step = row.indices(self.shape[0])
159 col_start, col_stop, col_step = col.indices(self.shape[1])
160 row_range = range(row_start, row_stop, row_step)
161 col_range = range(col_start, col_stop, col_step)
162 shape = (len(row_range), len(col_range))
163 # Switch paths only when advantageous
164 # (count the iterations in the loops, adjust for complexity)
165 if len(self) >= 2 * shape[0] * shape[1]:
166 # O(nr*nc) path: loop over <row x col>
167 return self._get_columnXarray(row_range, col_range)
168 # O(nnz) path: loop over entries of self
169 newdok = self._dok_container(shape, dtype=self.dtype)
170 for key in self.keys():
171 i, ri = divmod(int(key[0]) - row_start, row_step)
172 if ri != 0 or i < 0 or i >= shape[0]:
173 continue
174 j, rj = divmod(int(key[1]) - col_start, col_step)
175 if rj != 0 or j < 0 or j >= shape[1]:
176 continue
177 x = dict.__getitem__(self, key)
178 dict.__setitem__(newdok, (i, j), x)
179 return newdok
181 def _get_intXarray(self, row, col):
182 col = col.squeeze()
183 return self._get_columnXarray([row], col)
185 def _get_arrayXint(self, row, col):
186 row = row.squeeze()
187 return self._get_columnXarray(row, [col])
189 def _get_sliceXarray(self, row, col):
190 row = list(range(*row.indices(self.shape[0])))
191 return self._get_columnXarray(row, col)
193 def _get_arrayXslice(self, row, col):
194 col = list(range(*col.indices(self.shape[1])))
195 return self._get_columnXarray(row, col)
197 def _get_columnXarray(self, row, col):
198 # outer indexing
199 newdok = self._dok_container((len(row), len(col)), dtype=self.dtype)
201 for i, r in enumerate(row):
202 for j, c in enumerate(col):
203 v = dict.get(self, (r, c), 0)
204 if v:
205 dict.__setitem__(newdok, (i, j), v)
206 return newdok
208 def _get_arrayXarray(self, row, col):
209 # inner indexing
210 i, j = map(np.atleast_2d, np.broadcast_arrays(row, col))
211 newdok = self._dok_container(i.shape, dtype=self.dtype)
213 for key in itertools.product(range(i.shape[0]), range(i.shape[1])):
214 v = dict.get(self, (i[key], j[key]), 0)
215 if v:
216 dict.__setitem__(newdok, key, v)
217 return newdok
219 def _set_intXint(self, row, col, x):
220 key = (row, col)
221 if x:
222 dict.__setitem__(self, key, x)
223 elif dict.__contains__(self, key):
224 del self[key]
226 def _set_arrayXarray(self, row, col, x):
227 row = list(map(int, row.ravel()))
228 col = list(map(int, col.ravel()))
229 x = x.ravel()
230 dict.update(self, zip(zip(row, col), x))
232 for i in np.nonzero(x == 0)[0]:
233 key = (row[i], col[i])
234 if dict.__getitem__(self, key) == 0:
235 # may have been superseded by later update
236 del self[key]
238 def __add__(self, other):
239 if isscalarlike(other):
240 res_dtype = upcast_scalar(self.dtype, other)
241 new = self._dok_container(self.shape, dtype=res_dtype)
242 # Add this scalar to every element.
243 M, N = self.shape
244 for key in itertools.product(range(M), range(N)):
245 aij = dict.get(self, (key), 0) + other
246 if aij:
247 new[key] = aij
248 # new.dtype.char = self.dtype.char
249 elif issparse(other):
250 if other.format == "dok":
251 if other.shape != self.shape:
252 raise ValueError("Matrix dimensions are not equal.")
253 # We could alternatively set the dimensions to the largest of
254 # the two matrices to be summed. Would this be a good idea?
255 res_dtype = upcast(self.dtype, other.dtype)
256 new = self._dok_container(self.shape, dtype=res_dtype)
257 dict.update(new, self)
258 with np.errstate(over='ignore'):
259 dict.update(new,
260 ((k, new[k] + other[k]) for k in other.keys()))
261 else:
262 csc = self.tocsc()
263 new = csc + other
264 elif isdense(other):
265 new = self.todense() + other
266 else:
267 return NotImplemented
268 return new
270 def __radd__(self, other):
271 if isscalarlike(other):
272 new = self._dok_container(self.shape, dtype=self.dtype)
273 M, N = self.shape
274 for key in itertools.product(range(M), range(N)):
275 aij = dict.get(self, (key), 0) + other
276 if aij:
277 new[key] = aij
278 elif issparse(other):
279 if other.format == "dok":
280 if other.shape != self.shape:
281 raise ValueError("Matrix dimensions are not equal.")
282 new = self._dok_container(self.shape, dtype=self.dtype)
283 dict.update(new, self)
284 dict.update(new,
285 ((k, self[k] + other[k]) for k in other.keys()))
286 else:
287 csc = self.tocsc()
288 new = csc + other
289 elif isdense(other):
290 new = other + self.todense()
291 else:
292 return NotImplemented
293 return new
295 def __neg__(self):
296 if self.dtype.kind == 'b':
297 raise NotImplementedError('Negating a sparse boolean matrix is not'
298 ' supported.')
299 new = self._dok_container(self.shape, dtype=self.dtype)
300 dict.update(new, ((k, -self[k]) for k in self.keys()))
301 return new
303 def _mul_scalar(self, other):
304 res_dtype = upcast_scalar(self.dtype, other)
305 # Multiply this scalar by every element.
306 new = self._dok_container(self.shape, dtype=res_dtype)
307 dict.update(new, ((k, v * other) for k, v in self.items()))
308 return new
310 def _mul_vector(self, other):
311 # matrix * vector
312 result = np.zeros(self.shape[0], dtype=upcast(self.dtype, other.dtype))
313 for (i, j), v in self.items():
314 result[i] += v * other[j]
315 return result
317 def _mul_multivector(self, other):
318 # matrix * multivector
319 result_shape = (self.shape[0], other.shape[1])
320 result_dtype = upcast(self.dtype, other.dtype)
321 result = np.zeros(result_shape, dtype=result_dtype)
322 for (i, j), v in self.items():
323 result[i,:] += v * other[j,:]
324 return result
326 def __imul__(self, other):
327 if isscalarlike(other):
328 dict.update(self, ((k, v * other) for k, v in self.items()))
329 return self
330 return NotImplemented
332 def __truediv__(self, other):
333 if isscalarlike(other):
334 res_dtype = upcast_scalar(self.dtype, other)
335 new = self._dok_container(self.shape, dtype=res_dtype)
336 dict.update(new, ((k, v / other) for k, v in self.items()))
337 return new
338 return self.tocsr() / other
340 def __itruediv__(self, other):
341 if isscalarlike(other):
342 dict.update(self, ((k, v / other) for k, v in self.items()))
343 return self
344 return NotImplemented
346 def __reduce__(self):
347 # this approach is necessary because __setstate__ is called after
348 # __setitem__ upon unpickling and since __init__ is not called there
349 # is no shape attribute hence it is not possible to unpickle it.
350 return dict.__reduce__(self)
352 # What should len(sparse) return? For consistency with dense matrices,
353 # perhaps it should be the number of rows? For now it returns the number
354 # of non-zeros.
356 def transpose(self, axes=None, copy=False):
357 if axes is not None:
358 raise ValueError("Sparse matrices do not support "
359 "an 'axes' parameter because swapping "
360 "dimensions is the only logical permutation.")
362 M, N = self.shape
363 new = self._dok_container((N, M), dtype=self.dtype, copy=copy)
364 dict.update(new, (((right, left), val)
365 for (left, right), val in self.items()))
366 return new
368 transpose.__doc__ = _spbase.transpose.__doc__
370 def conjtransp(self):
371 """Return the conjugate transpose."""
372 M, N = self.shape
373 new = self._dok_container((N, M), dtype=self.dtype)
374 dict.update(new, (((right, left), np.conj(val))
375 for (left, right), val in self.items()))
376 return new
378 def copy(self):
379 new = self._dok_container(self.shape, dtype=self.dtype)
380 dict.update(new, self)
381 return new
383 copy.__doc__ = _spbase.copy.__doc__
385 def tocoo(self, copy=False):
386 if self.nnz == 0:
387 return self._coo_container(self.shape, dtype=self.dtype)
389 idx_dtype = self._get_index_dtype(maxval=max(self.shape))
390 data = np.fromiter(self.values(), dtype=self.dtype, count=self.nnz)
391 row = np.fromiter((i for i, _ in self.keys()), dtype=idx_dtype, count=self.nnz)
392 col = np.fromiter((j for _, j in self.keys()), dtype=idx_dtype, count=self.nnz)
393 A = self._coo_container(
394 (data, (row, col)), shape=self.shape, dtype=self.dtype
395 )
396 A.has_canonical_format = True
397 return A
399 tocoo.__doc__ = _spbase.tocoo.__doc__
401 def todok(self, copy=False):
402 if copy:
403 return self.copy()
404 return self
406 todok.__doc__ = _spbase.todok.__doc__
408 def tocsc(self, copy=False):
409 return self.tocoo(copy=False).tocsc(copy=copy)
411 tocsc.__doc__ = _spbase.tocsc.__doc__
413 def resize(self, *shape):
414 shape = check_shape(shape)
415 newM, newN = shape
416 M, N = self.shape
417 if newM < M or newN < N:
418 # Remove all elements outside new dimensions
419 for (i, j) in list(self.keys()):
420 if i >= newM or j >= newN:
421 del self[i, j]
422 self._shape = shape
424 resize.__doc__ = _spbase.resize.__doc__
427def isspmatrix_dok(x):
428 """Is `x` of dok_array type?
430 Parameters
431 ----------
432 x
433 object to check for being a dok matrix
435 Returns
436 -------
437 bool
438 True if `x` is a dok matrix, False otherwise
440 Examples
441 --------
442 >>> from scipy.sparse import dok_array, dok_matrix, coo_matrix, isspmatrix_dok
443 >>> isspmatrix_dok(dok_matrix([[5]]))
444 True
445 >>> isspmatrix_dok(dok_array([[5]]))
446 False
447 >>> isspmatrix_dok(coo_matrix([[5]]))
448 False
449 """
450 return isinstance(x, dok_matrix)
453# This namespace class separates array from matrix with isinstance
454class dok_array(_dok_base, sparray):
455 pass
457dok_array.__doc__ = _dok_base.__doc__
459class dok_matrix(spmatrix, _dok_base):
460 def set_shape(self, shape):
461 new_matrix = self.reshape(shape, copy=False).asformat(self.format)
462 self.__dict__ = new_matrix.__dict__
463 dict.clear(self)
464 dict.update(self, new_matrix)
466 def get_shape(self):
467 """Get shape of a sparse array."""
468 return self._shape
470 shape = property(fget=get_shape, fset=set_shape)
472dok_matrix.__doc__ = _array_doc_to_matrix(_dok_base.__doc__)