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