Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/scipy/sparse/_dok.py: 20%
373 statements
« prev ^ index » next coverage.py v7.4.4, created at 2024-03-22 06:44 +0000
1"""Dictionary Of Keys based matrix"""
3__docformat__ = "restructuredtext en"
5__all__ = ['dok_array', 'dok_matrix', 'isspmatrix_dok']
7import itertools
8from warnings import warn
9import numpy as np
11from ._matrix import spmatrix
12from ._base import _spbase, sparray, issparse
13from ._index import IndexMixin
14from ._sputils import (isdense, getdtype, isshape, isintlike, isscalarlike,
15 upcast, upcast_scalar, check_shape)
18class _dok_base(_spbase, IndexMixin, dict):
19 _format = 'dok'
21 def __init__(self, arg1, shape=None, dtype=None, copy=False):
22 _spbase.__init__(self)
24 is_array = isinstance(self, sparray)
25 if isinstance(arg1, tuple) and isshape(arg1, allow_1d=is_array):
26 self._shape = check_shape(arg1, allow_1d=is_array)
27 self._dict = {}
28 self.dtype = getdtype(dtype, default=float)
29 elif issparse(arg1): # Sparse ctor
30 if arg1.format == self.format:
31 arg1 = arg1.copy() if copy else arg1
32 else:
33 arg1 = arg1.todok()
35 if dtype is not None:
36 arg1 = arg1.astype(dtype, copy=False)
38 self._dict = arg1._dict
39 self._shape = check_shape(arg1.shape, allow_1d=is_array)
40 self.dtype = arg1.dtype
41 else: # Dense ctor
42 try:
43 arg1 = np.asarray(arg1)
44 except Exception as e:
45 raise TypeError('Invalid input format.') from e
47 if arg1.ndim > 2:
48 raise TypeError('Expected rank <=2 dense array or matrix.')
50 if arg1.ndim == 1:
51 if dtype is not None:
52 arg1 = arg1.astype(dtype)
53 self._dict = {i: v for i, v in enumerate(arg1) if v != 0}
54 self.dtype = arg1.dtype
55 else:
56 d = self._coo_container(arg1, dtype=dtype).todok()
57 self._dict = d._dict
58 self.dtype = d.dtype
59 self._shape = check_shape(arg1.shape, allow_1d=is_array)
61 def update(self, val):
62 # Prevent direct usage of update
63 raise NotImplementedError("Direct update to DOK sparse format is not allowed.")
65 def _getnnz(self, axis=None):
66 if axis is not None:
67 raise NotImplementedError(
68 "_getnnz over an axis is not implemented for DOK format."
69 )
70 return len(self._dict)
72 def count_nonzero(self):
73 return sum(x != 0 for x in self.values())
75 _getnnz.__doc__ = _spbase._getnnz.__doc__
76 count_nonzero.__doc__ = _spbase.count_nonzero.__doc__
78 def __len__(self):
79 return len(self._dict)
81 def __contains__(self, key):
82 return key in self._dict
84 def setdefault(self, key, default=None, /):
85 return self._dict.setdefault(key, default)
87 def __delitem__(self, key, /):
88 del self._dict[key]
90 def clear(self):
91 return self._dict.clear()
93 def popitem(self):
94 return self._dict.popitem()
96 def items(self):
97 return self._dict.items()
99 def keys(self):
100 return self._dict.keys()
102 def values(self):
103 return self._dict.values()
105 def get(self, key, default=0.0):
106 """This provides dict.get method functionality with type checking"""
107 if key in self._dict:
108 return self._dict[key]
109 if isintlike(key) and self.ndim == 1:
110 key = (key,)
111 if self.ndim != len(key):
112 raise IndexError(f'Index {key} length needs to match self.shape')
113 try:
114 for i in key:
115 assert isintlike(i)
116 except (AssertionError, TypeError, ValueError) as e:
117 raise IndexError('Index must be or consist of integers.') from e
118 key = tuple(i + M if i < 0 else i for i, M in zip(key, self.shape))
119 if any(i < 0 or i >= M for i, M in zip(key, self.shape)):
120 raise IndexError('Index out of bounds.')
121 if self.ndim == 1:
122 key = key[0]
123 return self._dict.get(key, default)
125 # override IndexMixin.__getitem__ for 1d case until fully implemented
126 def __getitem__(self, key):
127 if self.ndim == 2:
128 return super().__getitem__(key)
130 if isinstance(key, tuple) and len(key) == 1:
131 key = key[0]
132 INT_TYPES = (int, np.integer)
133 if isinstance(key, INT_TYPES):
134 if key < 0:
135 key += self.shape[-1]
136 if key < 0 or key >= self.shape[-1]:
137 raise IndexError('index value out of bounds')
138 return self._get_int(key)
139 else:
140 raise IndexError('array/slice index for 1d dok_array not yet supported')
142 # 1D get methods
143 def _get_int(self, idx):
144 return self._dict.get(idx, self.dtype.type(0))
146 # 2D get methods
147 def _get_intXint(self, row, col):
148 return self._dict.get((row, col), self.dtype.type(0))
150 def _get_intXslice(self, row, col):
151 return self._get_sliceXslice(slice(row, row + 1), col)
153 def _get_sliceXint(self, row, col):
154 return self._get_sliceXslice(row, slice(col, col + 1))
156 def _get_sliceXslice(self, row, col):
157 row_start, row_stop, row_step = row.indices(self.shape[0])
158 col_start, col_stop, col_step = col.indices(self.shape[1])
159 row_range = range(row_start, row_stop, row_step)
160 col_range = range(col_start, col_stop, col_step)
161 shape = (len(row_range), len(col_range))
162 # Switch paths only when advantageous
163 # (count the iterations in the loops, adjust for complexity)
164 if len(self) >= 2 * shape[0] * shape[1]:
165 # O(nr*nc) path: loop over <row x col>
166 return self._get_columnXarray(row_range, col_range)
167 # O(nnz) path: loop over entries of self
168 newdok = self._dok_container(shape, dtype=self.dtype)
169 for key in self.keys():
170 i, ri = divmod(int(key[0]) - row_start, row_step)
171 if ri != 0 or i < 0 or i >= shape[0]:
172 continue
173 j, rj = divmod(int(key[1]) - col_start, col_step)
174 if rj != 0 or j < 0 or j >= shape[1]:
175 continue
176 newdok._dict[i, j] = self._dict[key]
177 return newdok
179 def _get_intXarray(self, row, col):
180 col = col.squeeze()
181 return self._get_columnXarray([row], col)
183 def _get_arrayXint(self, row, col):
184 row = row.squeeze()
185 return self._get_columnXarray(row, [col])
187 def _get_sliceXarray(self, row, col):
188 row = list(range(*row.indices(self.shape[0])))
189 return self._get_columnXarray(row, col)
191 def _get_arrayXslice(self, row, col):
192 col = list(range(*col.indices(self.shape[1])))
193 return self._get_columnXarray(row, col)
195 def _get_columnXarray(self, row, col):
196 # outer indexing
197 newdok = self._dok_container((len(row), len(col)), dtype=self.dtype)
199 for i, r in enumerate(row):
200 for j, c in enumerate(col):
201 v = self._dict.get((r, c), 0)
202 if v:
203 newdok._dict[i, j] = v
204 return newdok
206 def _get_arrayXarray(self, row, col):
207 # inner indexing
208 i, j = map(np.atleast_2d, np.broadcast_arrays(row, col))
209 newdok = self._dok_container(i.shape, dtype=self.dtype)
211 for key in itertools.product(range(i.shape[0]), range(i.shape[1])):
212 v = self._dict.get((i[key], j[key]), 0)
213 if v:
214 newdok._dict[key] = v
215 return newdok
217 # override IndexMixin.__setitem__ for 1d case until fully implemented
218 def __setitem__(self, key, value):
219 if self.ndim == 2:
220 return super().__setitem__(key, value)
222 if isinstance(key, tuple) and len(key) == 1:
223 key = key[0]
224 INT_TYPES = (int, np.integer)
225 if isinstance(key, INT_TYPES):
226 if key < 0:
227 key += self.shape[-1]
228 if key < 0 or key >= self.shape[-1]:
229 raise IndexError('index value out of bounds')
230 return self._set_int(key, value)
231 else:
232 raise IndexError('array index for 1d dok_array not yet provided')
234 # 1D set methods
235 def _set_int(self, idx, x):
236 if x:
237 self._dict[idx] = x
238 elif idx in self._dict:
239 del self._dict[idx]
241 # 2D set methods
242 def _set_intXint(self, row, col, x):
243 key = (row, col)
244 if x:
245 self._dict[key] = x
246 elif key in self._dict:
247 del self._dict[key]
249 def _set_arrayXarray(self, row, col, x):
250 row = list(map(int, row.ravel()))
251 col = list(map(int, col.ravel()))
252 x = x.ravel()
253 self._dict.update(zip(zip(row, col), x))
255 for i in np.nonzero(x == 0)[0]:
256 key = (row[i], col[i])
257 if self._dict[key] == 0:
258 # may have been superseded by later update
259 del self._dict[key]
261 def __add__(self, other):
262 if isscalarlike(other):
263 res_dtype = upcast_scalar(self.dtype, other)
264 new = self._dok_container(self.shape, dtype=res_dtype)
265 # Add this scalar to each element.
266 for key in itertools.product(*[range(d) for d in self.shape]):
267 aij = self._dict.get(key, 0) + other
268 if aij:
269 new[key] = aij
270 elif issparse(other):
271 if other.shape != self.shape:
272 raise ValueError("Matrix dimensions are not equal.")
273 res_dtype = upcast(self.dtype, other.dtype)
274 new = self._dok_container(self.shape, dtype=res_dtype)
275 new._dict = self._dict.copy()
276 if other.format == "dok":
277 o_items = other.items()
278 else:
279 other = other.tocoo()
280 if self.ndim == 1:
281 o_items = zip(other.coords[0], other.data)
282 else:
283 o_items = zip(zip(*other.coords), other.data)
284 with np.errstate(over='ignore'):
285 new._dict.update((k, new[k] + v) for k, v in o_items)
286 elif isdense(other):
287 new = self.todense() + other
288 else:
289 return NotImplemented
290 return new
292 def __radd__(self, other):
293 return self + other # addition is comutative
295 def __neg__(self):
296 if self.dtype.kind == 'b':
297 raise NotImplementedError(
298 'Negating a sparse boolean matrix is not supported.'
299 )
300 new = self._dok_container(self.shape, dtype=self.dtype)
301 new._dict.update((k, -v) for k, v in self.items())
302 return new
304 def _mul_scalar(self, other):
305 res_dtype = upcast_scalar(self.dtype, other)
306 # Multiply this scalar by every element.
307 new = self._dok_container(self.shape, dtype=res_dtype)
308 new._dict.update(((k, v * other) for k, v in self.items()))
309 return new
311 def _matmul_vector(self, other):
312 res_dtype = upcast(self.dtype, other.dtype)
314 # vector @ vector
315 if self.ndim == 1:
316 if issparse(other):
317 if other.format == "dok":
318 keys = self.keys() & other.keys()
319 else:
320 keys = self.keys() & other.tocoo().coords[0]
321 return res_dtype(sum(self._dict[k] * other._dict[k] for k in keys))
322 elif isdense(other):
323 return res_dtype(sum(other[k] * v for k, v in self.items()))
324 else:
325 return NotImplemented
327 # matrix @ vector
328 result = np.zeros(self.shape[0], dtype=res_dtype)
329 for (i, j), v in self.items():
330 result[i] += v * other[j]
331 return result
333 def _matmul_multivector(self, other):
334 result_dtype = upcast(self.dtype, other.dtype)
335 # vector @ multivector
336 if self.ndim == 1:
337 # works for other 1d or 2d
338 return sum(v * other[j] for j, v in self._dict.items())
340 # matrix @ multivector
341 M = self.shape[0]
342 new_shape = (M,) if other.ndim == 1 else (M, other.shape[1])
343 result = np.zeros(new_shape, dtype=result_dtype)
344 for (i, j), v in self.items():
345 result[i] += v * other[j]
346 return result
348 def __imul__(self, other):
349 if isscalarlike(other):
350 self._dict.update((k, v * other) for k, v in self.items())
351 return self
352 return NotImplemented
354 def __truediv__(self, other):
355 if isscalarlike(other):
356 res_dtype = upcast_scalar(self.dtype, other)
357 new = self._dok_container(self.shape, dtype=res_dtype)
358 new._dict.update(((k, v / other) for k, v in self.items()))
359 return new
360 return self.tocsr() / other
362 def __itruediv__(self, other):
363 if isscalarlike(other):
364 self._dict.update((k, v / other) for k, v in self.items())
365 return self
366 return NotImplemented
368 def __reduce__(self):
369 # this approach is necessary because __setstate__ is called after
370 # __setitem__ upon unpickling and since __init__ is not called there
371 # is no shape attribute hence it is not possible to unpickle it.
372 return dict.__reduce__(self)
374 def diagonal(self, k=0):
375 if self.ndim == 2:
376 return super().diagonal(k)
377 raise ValueError("diagonal requires two dimensions")
379 def transpose(self, axes=None, copy=False):
380 if self.ndim == 1:
381 return self.copy()
383 if axes is not None and axes != (1, 0):
384 raise ValueError(
385 "Sparse arrays/matrices do not support "
386 "an 'axes' parameter because swapping "
387 "dimensions is the only logical permutation."
388 )
390 M, N = self.shape
391 new = self._dok_container((N, M), dtype=self.dtype, copy=copy)
392 new._dict.update((((right, left), val) for (left, right), val in self.items()))
393 return new
395 transpose.__doc__ = _spbase.transpose.__doc__
397 def conjtransp(self):
398 """DEPRECATED: Return the conjugate transpose.
400 .. deprecated:: 1.14.0
402 `conjtransp` is deprecated and will be removed in v1.16.0.
403 Use `.T.conj()` instead.
404 """
405 msg = ("`conjtransp` is deprecated and will be removed in v1.16.0. "
406 "Use `.T.conj()` instead.")
407 warn(msg, DeprecationWarning, stacklevel=2)
409 if self.ndim == 1:
410 new = self.tocoo()
411 new.data = new.data.conjugate()
412 return new
414 M, N = self.shape
415 new = self._dok_container((N, M), dtype=self.dtype)
416 new._dict = {(right, left): np.conj(val) for (left, right), val in self.items()}
417 return new
419 def copy(self):
420 new = self._dok_container(self.shape, dtype=self.dtype)
421 new._dict.update(self._dict)
422 return new
424 copy.__doc__ = _spbase.copy.__doc__
426 @classmethod
427 def fromkeys(cls, iterable, value=1, /):
428 tmp = dict.fromkeys(iterable, value)
429 keys = tmp.keys()
430 if isinstance(next(iter(keys)), tuple):
431 shape = tuple(max(idx) + 1 for idx in zip(*keys))
432 else:
433 shape = (max(keys) + 1,)
434 result = cls(shape, dtype=type(value))
435 result._dict = tmp
436 return result
438 def tocoo(self, copy=False):
439 nnz = self.nnz
440 if nnz == 0:
441 return self._coo_container(self.shape, dtype=self.dtype)
443 idx_dtype = self._get_index_dtype(maxval=max(self.shape))
444 data = np.fromiter(self.values(), dtype=self.dtype, count=nnz)
445 # handle 1d keys specially b/c not a tuple
446 inds = zip(*self.keys()) if self.ndim > 1 else (self.keys(),)
447 coords = tuple(np.fromiter(ix, dtype=idx_dtype, count=nnz) for ix in inds)
448 A = self._coo_container((data, coords), shape=self.shape, dtype=self.dtype)
449 A.has_canonical_format = True
450 return A
452 tocoo.__doc__ = _spbase.tocoo.__doc__
454 def todok(self, copy=False):
455 if copy:
456 return self.copy()
457 return self
459 todok.__doc__ = _spbase.todok.__doc__
461 def tocsc(self, copy=False):
462 if self.ndim == 1:
463 raise NotImplementedError("tocsr() not valid for 1d sparse array")
464 return self.tocoo(copy=False).tocsc(copy=copy)
466 tocsc.__doc__ = _spbase.tocsc.__doc__
468 def resize(self, *shape):
469 is_array = isinstance(self, sparray)
470 shape = check_shape(shape, allow_1d=is_array)
471 if len(shape) != len(self.shape):
472 # TODO implement resize across dimensions
473 raise NotImplementedError
475 if self.ndim == 1:
476 newN = shape[-1]
477 for i in list(self._dict):
478 if i >= newN:
479 del self._dict[i]
480 self._shape = shape
481 return
483 newM, newN = shape
484 M, N = self.shape
485 if newM < M or newN < N:
486 # Remove all elements outside new dimensions
487 for i, j in list(self.keys()):
488 if i >= newM or j >= newN:
489 del self._dict[i, j]
490 self._shape = shape
492 resize.__doc__ = _spbase.resize.__doc__
494 # Added for 1d to avoid `tocsr` from _base.py
495 def astype(self, dtype, casting='unsafe', copy=True):
496 dtype = np.dtype(dtype)
497 if self.dtype != dtype:
498 result = self._dok_container(self.shape, dtype=dtype)
499 data = np.array(list(self._dict.values()), dtype=dtype)
500 result._dict = dict(zip(self._dict, data))
501 return result
502 elif copy:
503 return self.copy()
504 return self
507def isspmatrix_dok(x):
508 """Is `x` of dok_array type?
510 Parameters
511 ----------
512 x
513 object to check for being a dok matrix
515 Returns
516 -------
517 bool
518 True if `x` is a dok matrix, False otherwise
520 Examples
521 --------
522 >>> from scipy.sparse import dok_array, dok_matrix, coo_matrix, isspmatrix_dok
523 >>> isspmatrix_dok(dok_matrix([[5]]))
524 True
525 >>> isspmatrix_dok(dok_array([[5]]))
526 False
527 >>> isspmatrix_dok(coo_matrix([[5]]))
528 False
529 """
530 return isinstance(x, dok_matrix)
533# This namespace class separates array from matrix with isinstance
534class dok_array(_dok_base, sparray):
535 """
536 Dictionary Of Keys based sparse array.
538 This is an efficient structure for constructing sparse
539 arrays incrementally.
541 This can be instantiated in several ways:
542 dok_array(D)
543 where D is a 2-D ndarray
545 dok_array(S)
546 with another sparse array or matrix S (equivalent to S.todok())
548 dok_array((M,N), [dtype])
549 create the array with initial shape (M,N)
550 dtype is optional, defaulting to dtype='d'
552 Attributes
553 ----------
554 dtype : dtype
555 Data type of the array
556 shape : 2-tuple
557 Shape of the array
558 ndim : int
559 Number of dimensions (this is always 2)
560 nnz
561 Number of nonzero elements
562 size
563 T
565 Notes
566 -----
568 Sparse arrays can be used in arithmetic operations: they support
569 addition, subtraction, multiplication, division, and matrix power.
571 - Allows for efficient O(1) access of individual elements.
572 - Duplicates are not allowed.
573 - Can be efficiently converted to a coo_array once constructed.
575 Examples
576 --------
577 >>> import numpy as np
578 >>> from scipy.sparse import dok_array
579 >>> S = dok_array((5, 5), dtype=np.float32)
580 >>> for i in range(5):
581 ... for j in range(5):
582 ... S[i, j] = i + j # Update element
584 """
587class dok_matrix(spmatrix, _dok_base):
588 """
589 Dictionary Of Keys based sparse matrix.
591 This is an efficient structure for constructing sparse
592 matrices incrementally.
594 This can be instantiated in several ways:
595 dok_matrix(D)
596 where D is a 2-D ndarray
598 dok_matrix(S)
599 with another sparse array or matrix S (equivalent to S.todok())
601 dok_matrix((M,N), [dtype])
602 create the matrix with initial shape (M,N)
603 dtype is optional, defaulting to dtype='d'
605 Attributes
606 ----------
607 dtype : dtype
608 Data type of the matrix
609 shape : 2-tuple
610 Shape of the matrix
611 ndim : int
612 Number of dimensions (this is always 2)
613 nnz
614 Number of nonzero elements
615 size
616 T
618 Notes
619 -----
621 Sparse matrices can be used in arithmetic operations: they support
622 addition, subtraction, multiplication, division, and matrix power.
624 - Allows for efficient O(1) access of individual elements.
625 - Duplicates are not allowed.
626 - Can be efficiently converted to a coo_matrix once constructed.
628 Examples
629 --------
630 >>> import numpy as np
631 >>> from scipy.sparse import dok_matrix
632 >>> S = dok_matrix((5, 5), dtype=np.float32)
633 >>> for i in range(5):
634 ... for j in range(5):
635 ... S[i, j] = i + j # Update element
637 """
639 def set_shape(self, shape):
640 new_matrix = self.reshape(shape, copy=False).asformat(self.format)
641 self.__dict__ = new_matrix.__dict__
643 def get_shape(self):
644 """Get shape of a sparse matrix."""
645 return self._shape
647 shape = property(fget=get_shape, fset=set_shape)