Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/scipy/sparse/

1"""List of Lists sparse matrix class

2"""

4__docformat__ = "restructuredtext en"

6__all__ = ['lil_array', 'lil_matrix', 'isspmatrix_lil']

8from bisect import bisect_left

10import numpy as np

12from ._matrix import spmatrix

13from ._base import _spbase, sparray, issparse

14from ._index import IndexMixin, INT_TYPES, _broadcast_arrays

15from ._sputils import (getdtype, isshape, isscalarlike, upcast_scalar,

16 check_shape, check_reshape_kwargs)

17from . import _csparsetools

20class _lil_base(_spbase, IndexMixin):

21 _format = 'lil'

23 def __init__(self, arg1, shape=None, dtype=None, copy=False):

24 _spbase.__init__(self)

25 self.dtype = getdtype(dtype, arg1, default=float)

27 # First get the shape

28 if issparse(arg1):

29 if arg1.format == "lil" and copy:

30 A = arg1.copy()

31 else:

32 A = arg1.tolil()

34 if dtype is not None:

35 A = A.astype(dtype, copy=False)

37 self._shape = check_shape(A.shape)

38 self.dtype = A.dtype

39 self.rows = A.rows

40 self.data = A.data

41 elif isinstance(arg1,tuple):

42 if isshape(arg1):

43 if shape is not None:

44 raise ValueError('invalid use of shape parameter')

45 M, N = arg1

46 self._shape = check_shape((M, N))

47 self.rows = np.empty((M,), dtype=object)

48 self.data = np.empty((M,), dtype=object)

49 for i in range(M):

50 self.rows[i] = []

51 self.data[i] = []

52 else:

53 raise TypeError('unrecognized lil_array constructor usage')

54 else:

55 # assume A is dense

56 try:

57 A = self._ascontainer(arg1)

58 except TypeError as e:

59 raise TypeError('unsupported matrix type') from e

60 else:

61 A = self._csr_container(A, dtype=dtype).tolil()

63 self._shape = check_shape(A.shape)

64 self.dtype = A.dtype

65 self.rows = A.rows

66 self.data = A.data

68 def __iadd__(self,other):

69 self[:,:] = self + other

70 return self

72 def __isub__(self,other):

73 self[:,:] = self - other

74 return self

76 def __imul__(self,other):

77 if isscalarlike(other):

78 self[:,:] = self * other

79 return self

80 else:

81 return NotImplemented

83 def __itruediv__(self,other):

84 if isscalarlike(other):

85 self[:,:] = self / other

86 return self

87 else:

88 return NotImplemented

90 # Whenever the dimensions change, empty lists should be created for each

91 # row

93 def _getnnz(self, axis=None):

94 if axis is None:

95 return sum([len(rowvals) for rowvals in self.data])

96 if axis < 0:

97 axis += 2

98 if axis == 0:

99 out = np.zeros(self.shape[1], dtype=np.intp)

100 for row in self.rows:

101 out[row] += 1

102 return out

103 elif axis == 1:

104 return np.array([len(rowvals) for rowvals in self.data], dtype=np.intp)

105 else:

106 raise ValueError('axis out of bounds')

107

108 def count_nonzero(self):

109 return sum(np.count_nonzero(rowvals) for rowvals in self.data)

110

111 _getnnz.__doc__ = _spbase._getnnz.__doc__

112 count_nonzero.__doc__ = _spbase.count_nonzero.__doc__

113

114 def __str__(self):

115 val = ''

116 for i, row in enumerate(self.rows):

117 for pos, j in enumerate(row):

118 val += f" {str((i, j))}\t{str(self.data[i][pos])}\n"

119 return val[:-1]

120

121 def getrowview(self, i):

122 """Returns a view of the 'i'th row (without copying).

123 """

124 new = self._lil_container((1, self.shape[1]), dtype=self.dtype)

125 new.rows[0] = self.rows[i]

126 new.data[0] = self.data[i]

127 return new

128

129 def getrow(self, i):

130 """Returns a copy of the 'i'th row.

131 """

132 M, N = self.shape

133 if i < 0:

134 i += M

135 if i < 0 or i >= M:

136 raise IndexError('row index out of bounds')

137 new = self._lil_container((1, N), dtype=self.dtype)

138 new.rows[0] = self.rows[i][:]

139 new.data[0] = self.data[i][:]

140 return new

141

142 def __getitem__(self, key):

143 # Fast path for simple (int, int) indexing.

144 if (isinstance(key, tuple) and len(key) == 2 and

145 isinstance(key[0], INT_TYPES) and

146 isinstance(key[1], INT_TYPES)):

147 # lil_get1 handles validation for us.

148 return self._get_intXint(*key)

149 # Everything else takes the normal path.

150 return IndexMixin.__getitem__(self, key)

151

152 def _asindices(self, idx, N):

153 # LIL routines handle bounds-checking for us, so don't do it here.

154 try:

155 x = np.asarray(idx)

156 except (ValueError, TypeError, MemoryError) as e:

157 raise IndexError('invalid index') from e

158 if x.ndim not in (1, 2):

159 raise IndexError('Index dimension must be <= 2')

160 return x

161

162 def _get_intXint(self, row, col):

163 v = _csparsetools.lil_get1(self.shape[0], self.shape[1], self.rows,

164 self.data, row, col)

165 return self.dtype.type(v)

166

167 def _get_sliceXint(self, row, col):

168 row = range(*row.indices(self.shape[0]))

169 return self._get_row_ranges(row, slice(col, col+1))

170

171 def _get_arrayXint(self, row, col):

172 row = row.squeeze()

173 return self._get_row_ranges(row, slice(col, col+1))

174

175 def _get_intXslice(self, row, col):

176 return self._get_row_ranges((row,), col)

177

178 def _get_sliceXslice(self, row, col):

179 row = range(*row.indices(self.shape[0]))

180 return self._get_row_ranges(row, col)

181

182 def _get_arrayXslice(self, row, col):

183 return self._get_row_ranges(row, col)

184

185 def _get_intXarray(self, row, col):

186 row = np.array(row, dtype=col.dtype, ndmin=1)

187 return self._get_columnXarray(row, col)

188

189 def _get_sliceXarray(self, row, col):

190 row = np.arange(*row.indices(self.shape[0]))

191 return self._get_columnXarray(row, col)

192

193 def _get_columnXarray(self, row, col):

194 # outer indexing

195 row, col = _broadcast_arrays(row[:,None], col)

196 return self._get_arrayXarray(row, col)

197

198 def _get_arrayXarray(self, row, col):

199 # inner indexing

200 i, j = map(np.atleast_2d, _prepare_index_for_memoryview(row, col))

201 new = self._lil_container(i.shape, dtype=self.dtype)

202 _csparsetools.lil_fancy_get(self.shape[0], self.shape[1],

203 self.rows, self.data,

204 new.rows, new.data,

205 i, j)

206 return new

207

208 def _get_row_ranges(self, rows, col_slice):

209 """

210 Fast path for indexing in the case where column index is slice.

211

212 This gains performance improvement over brute force by more

213 efficient skipping of zeros, by accessing the elements

214 column-wise in order.

215

216 Parameters

217 ----------

218 rows : sequence or range

219 Rows indexed. If range, must be within valid bounds.

220 col_slice : slice

221 Columns indexed

222

223 """

224 j_start, j_stop, j_stride = col_slice.indices(self.shape[1])

225 col_range = range(j_start, j_stop, j_stride)

226 nj = len(col_range)

227 new = self._lil_container((len(rows), nj), dtype=self.dtype)

228

229 _csparsetools.lil_get_row_ranges(self.shape[0], self.shape[1],

230 self.rows, self.data,

231 new.rows, new.data,

232 rows,

233 j_start, j_stop, j_stride, nj)

234

235 return new

236

237 def _set_intXint(self, row, col, x):

238 _csparsetools.lil_insert(self.shape[0], self.shape[1], self.rows,

239 self.data, row, col, x)

240

241 def _set_arrayXarray(self, row, col, x):

242 i, j, x = map(np.atleast_2d, _prepare_index_for_memoryview(row, col, x))

243 _csparsetools.lil_fancy_set(self.shape[0], self.shape[1],

244 self.rows, self.data,

245 i, j, x)

246

247 def _set_arrayXarray_sparse(self, row, col, x):

248 # Fall back to densifying x

249 x = np.asarray(x.toarray(), dtype=self.dtype)

250 x, _ = _broadcast_arrays(x, row)

251 self._set_arrayXarray(row, col, x)

252

253 def __setitem__(self, key, x):

254 if isinstance(key, tuple) and len(key) == 2:

255 row, col = key

256 # Fast path for simple (int, int) indexing.

257 if isinstance(row, INT_TYPES) and isinstance(col, INT_TYPES):

258 x = self.dtype.type(x)

259 if x.size > 1:

260 raise ValueError("Trying to assign a sequence to an item")

261 return self._set_intXint(row, col, x)

262 # Fast path for full-matrix sparse assignment.

263 if (isinstance(row, slice) and isinstance(col, slice) and

264 row == slice(None) and col == slice(None) and

265 issparse(x) and x.shape == self.shape):

266 x = self._lil_container(x, dtype=self.dtype)

267 self.rows = x.rows

268 self.data = x.data

269 return

270 # Everything else takes the normal path.

271 IndexMixin.__setitem__(self, key, x)

272

273 def _mul_scalar(self, other):

274 if other == 0:

275 # Multiply by zero: return the zero matrix

276 new = self._lil_container(self.shape, dtype=self.dtype)

277 else:

278 res_dtype = upcast_scalar(self.dtype, other)

279

280 new = self.copy()

281 new = new.astype(res_dtype)

282 # Multiply this scalar by every element.

283 for j, rowvals in enumerate(new.data):

284 new.data[j] = [val*other for val in rowvals]

285 return new

286

287 def __truediv__(self, other): # self / other

288 if isscalarlike(other):

289 new = self.copy()

290 new.dtype = np.result_type(self, other)

291 # Divide every element by this scalar

292 for j, rowvals in enumerate(new.data):

293 new.data[j] = [val/other for val in rowvals]

294 return new

295 else:

296 return self.tocsr() / other

297

298 def copy(self):

299 M, N = self.shape

300 new = self._lil_container(self.shape, dtype=self.dtype)

301 # This is ~14x faster than calling deepcopy() on rows and data.

302 _csparsetools.lil_get_row_ranges(M, N, self.rows, self.data,

303 new.rows, new.data, range(M),

304 0, N, 1, N)

305 return new

306

307 copy.__doc__ = _spbase.copy.__doc__

308

309 def reshape(self, *args, **kwargs):

310 shape = check_shape(args, self.shape)

311 order, copy = check_reshape_kwargs(kwargs)

312

313 # Return early if reshape is not required

314 if shape == self.shape:

315 if copy:

316 return self.copy()

317 else:

318 return self

319

320 new = self._lil_container(shape, dtype=self.dtype)

321

322 if order == 'C':

323 ncols = self.shape[1]

324 for i, row in enumerate(self.rows):

325 for col, j in enumerate(row):

326 new_r, new_c = np.unravel_index(i * ncols + j, shape)

327 new[new_r, new_c] = self[i, j]

328 elif order == 'F':

329 nrows = self.shape[0]

330 for i, row in enumerate(self.rows):

331 for col, j in enumerate(row):

332 new_r, new_c = np.unravel_index(i + j * nrows, shape, order)

333 new[new_r, new_c] = self[i, j]

334 else:

335 raise ValueError("'order' must be 'C' or 'F'")

336

337 return new

338

339 reshape.__doc__ = _spbase.reshape.__doc__

340

341 def resize(self, *shape):

342 shape = check_shape(shape)

343 new_M, new_N = shape

344 M, N = self.shape

345

346 if new_M < M:

347 self.rows = self.rows[:new_M]

348 self.data = self.data[:new_M]

349 elif new_M > M:

350 self.rows = np.resize(self.rows, new_M)

351 self.data = np.resize(self.data, new_M)

352 for i in range(M, new_M):

353 self.rows[i] = []

354 self.data[i] = []

355

356 if new_N < N:

357 for row, data in zip(self.rows, self.data):

358 trunc = bisect_left(row, new_N)

359 del row[trunc:]

360 del data[trunc:]

361

362 self._shape = shape

363

364 resize.__doc__ = _spbase.resize.__doc__

365

366 def toarray(self, order=None, out=None):

367 d = self._process_toarray_args(order, out)

368 for i, row in enumerate(self.rows):

369 for pos, j in enumerate(row):

370 d[i, j] = self.data[i][pos]

371 return d

372

373 toarray.__doc__ = _spbase.toarray.__doc__

374

375 def transpose(self, axes=None, copy=False):

376 return self.tocsr(copy=copy).transpose(axes=axes, copy=False).tolil(copy=False)

377

378 transpose.__doc__ = _spbase.transpose.__doc__

379

380 def tolil(self, copy=False):

381 if copy:

382 return self.copy()

383 else:

384 return self

385

386 tolil.__doc__ = _spbase.tolil.__doc__

387

388 def tocsr(self, copy=False):

389 M, N = self.shape

390 if M == 0 or N == 0:

391 return self._csr_container((M, N), dtype=self.dtype)

392

393 # construct indptr array

394 if M*N <= np.iinfo(np.int32).max:

395 # fast path: it is known that 64-bit indexing will not be needed.

396 idx_dtype = np.int32

397 indptr = np.empty(M + 1, dtype=idx_dtype)

398 indptr[0] = 0

399 _csparsetools.lil_get_lengths(self.rows, indptr[1:])

400 np.cumsum(indptr, out=indptr)

401 nnz = indptr[-1]

402 else:

403 idx_dtype = self._get_index_dtype(maxval=N)

404 lengths = np.empty(M, dtype=idx_dtype)

405 _csparsetools.lil_get_lengths(self.rows, lengths)

406 nnz = lengths.sum(dtype=np.int64)

407 idx_dtype = self._get_index_dtype(maxval=max(N, nnz))

408 indptr = np.empty(M + 1, dtype=idx_dtype)

409 indptr[0] = 0

410 np.cumsum(lengths, dtype=idx_dtype, out=indptr[1:])

411

412 indices = np.empty(nnz, dtype=idx_dtype)

413 data = np.empty(nnz, dtype=self.dtype)

414 _csparsetools.lil_flatten_to_array(self.rows, indices)

415 _csparsetools.lil_flatten_to_array(self.data, data)

416

417 # init csr matrix

418 return self._csr_container((data, indices, indptr), shape=self.shape)

419

420 tocsr.__doc__ = _spbase.tocsr.__doc__

421

422

423def _prepare_index_for_memoryview(i, j, x=None):

424 """

425 Convert index and data arrays to form suitable for passing to the

426 Cython fancy getset routines.

427

428 The conversions are necessary since to (i) ensure the integer

429 index arrays are in one of the accepted types, and (ii) to ensure

430 the arrays are writable so that Cython memoryview support doesn't

431 choke on them.

432

433 Parameters

434 ----------

435 i, j

436 Index arrays

437 x : optional

438 Data arrays

439

440 Returns

441 -------

442 i, j, x

443 Re-formatted arrays (x is omitted, if input was None)

444

445 """

446 if i.dtype > j.dtype:

447 j = j.astype(i.dtype)

448 elif i.dtype < j.dtype:

449 i = i.astype(j.dtype)

450

451 if not i.flags.writeable or i.dtype not in (np.int32, np.int64):

452 i = i.astype(np.intp)

453 if not j.flags.writeable or j.dtype not in (np.int32, np.int64):

454 j = j.astype(np.intp)

455

456 if x is not None:

457 if not x.flags.writeable:

458 x = x.copy()

459 return i, j, x

460 else:

461 return i, j

462

463

464def isspmatrix_lil(x):

465 """Is `x` of lil_matrix type?

466

467 Parameters

468 ----------

469 x

470 object to check for being a lil matrix

471

472 Returns

473 -------

474 bool

475 True if `x` is a lil matrix, False otherwise

476

477 Examples

478 --------

479 >>> from scipy.sparse import lil_array, lil_matrix, coo_matrix, isspmatrix_lil

480 >>> isspmatrix_lil(lil_matrix([[5]]))

481 True

482 >>> isspmatrix_lil(lil_array([[5]]))

483 False

484 >>> isspmatrix_lil(coo_matrix([[5]]))

485 False

486 """

487 return isinstance(x, lil_matrix)

488

489

490# This namespace class separates array from matrix with isinstance

491class lil_array(_lil_base, sparray):

492 """

493 Row-based LIst of Lists sparse array.

494

495 This is a structure for constructing sparse arrays incrementally.

496 Note that inserting a single item can take linear time in the worst case;

497 to construct the array efficiently, make sure the items are pre-sorted by

498 index, per row.

499

500 This can be instantiated in several ways:

501 lil_array(D)

502 where D is a 2-D ndarray

503

504 lil_array(S)

505 with another sparse array or matrix S (equivalent to S.tolil())

506

507 lil_array((M, N), [dtype])

508 to construct an empty array with shape (M, N)

509 dtype is optional, defaulting to dtype='d'.

510

511 Attributes

512 ----------

513 dtype : dtype

514 Data type of the array

515 shape : 2-tuple

516 Shape of the array

517 ndim : int

518 Number of dimensions (this is always 2)

519 nnz

520 size

521 data

522 LIL format data array of the array

523 rows

524 LIL format row index array of the array

525 T

526

527 Notes

528 -----

529 Sparse arrays can be used in arithmetic operations: they support

530 addition, subtraction, multiplication, division, and matrix power.

531

532 Advantages of the LIL format

533 - supports flexible slicing

534 - changes to the array sparsity structure are efficient

535

536 Disadvantages of the LIL format

537 - arithmetic operations LIL + LIL are slow (consider CSR or CSC)

538 - slow column slicing (consider CSC)

539 - slow matrix vector products (consider CSR or CSC)

540

541 Intended Usage

542 - LIL is a convenient format for constructing sparse arrays

543 - once an array has been constructed, convert to CSR or

544 CSC format for fast arithmetic and matrix vector operations

545 - consider using the COO format when constructing large arrays

546

547 Data Structure

548 - An array (``self.rows``) of rows, each of which is a sorted

549 list of column indices of non-zero elements.

550 - The corresponding nonzero values are stored in similar

551 fashion in ``self.data``.

552

553 """

554

555

556class lil_matrix(spmatrix, _lil_base):

557 """

558 Row-based LIst of Lists sparse matrix.

559

560 This is a structure for constructing sparse matrices incrementally.

561 Note that inserting a single item can take linear time in the worst case;

562 to construct the matrix efficiently, make sure the items are pre-sorted by

563 index, per row.

564

565 This can be instantiated in several ways:

566 lil_matrix(D)

567 where D is a 2-D ndarray

568

569 lil_matrix(S)

570 with another sparse array or matrix S (equivalent to S.tolil())

571

572 lil_matrix((M, N), [dtype])

573 to construct an empty matrix with shape (M, N)

574 dtype is optional, defaulting to dtype='d'.

575

576 Attributes

577 ----------

578 dtype : dtype

579 Data type of the matrix

580 shape : 2-tuple

581 Shape of the matrix

582 ndim : int

583 Number of dimensions (this is always 2)

584 nnz

585 size

586 data

587 LIL format data array of the matrix

588 rows

589 LIL format row index array of the matrix

590 T

591

592 Notes

593 -----

594 Sparse matrices can be used in arithmetic operations: they support

595 addition, subtraction, multiplication, division, and matrix power.

596

597 Advantages of the LIL format

598 - supports flexible slicing

599 - changes to the matrix sparsity structure are efficient

600

601 Disadvantages of the LIL format

602 - arithmetic operations LIL + LIL are slow (consider CSR or CSC)

603 - slow column slicing (consider CSC)

604 - slow matrix vector products (consider CSR or CSC)

605

606 Intended Usage

607 - LIL is a convenient format for constructing sparse matrices

608 - once a matrix has been constructed, convert to CSR or

609 CSC format for fast arithmetic and matrix vector operations

610 - consider using the COO format when constructing large matrices

611

612 Data Structure

613 - An array (``self.rows``) of rows, each of which is a sorted

614 list of column indices of non-zero elements.

615 - The corresponding nonzero values are stored in similar

616 fashion in ``self.data``.

617

618 """

Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/scipy/sparse/_lil.py: 20%

295 statements