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 # Divide every element by this scalar

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

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

293 return new

294 else:

295 return self.tocsr() / other

296

297 def copy(self):

298 M, N = self.shape

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

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

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

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

303 0, N, 1, N)

304 return new

305

306 copy.__doc__ = _spbase.copy.__doc__

307

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

309 shape = check_shape(args, self.shape)

310 order, copy = check_reshape_kwargs(kwargs)

311

312 # Return early if reshape is not required

313 if shape == self.shape:

314 if copy:

315 return self.copy()

316 else:

317 return self

318

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

320

321 if order == 'C':

322 ncols = self.shape[1]

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

324 for col, j in enumerate(row):

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

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

327 elif order == 'F':

328 nrows = self.shape[0]

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

330 for col, j in enumerate(row):

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

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

333 else:

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

335

336 return new

337

338 reshape.__doc__ = _spbase.reshape.__doc__

339

340 def resize(self, *shape):

341 shape = check_shape(shape)

342 new_M, new_N = shape

343 M, N = self.shape

344

345 if new_M < M:

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

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

348 elif new_M > M:

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

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

351 for i in range(M, new_M):

352 self.rows[i] = []

353 self.data[i] = []

354

355 if new_N < N:

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

357 trunc = bisect_left(row, new_N)

358 del row[trunc:]

359 del data[trunc:]

360

361 self._shape = shape

362

363 resize.__doc__ = _spbase.resize.__doc__

364

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

366 d = self._process_toarray_args(order, out)

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

368 for pos, j in enumerate(row):

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

370 return d

371

372 toarray.__doc__ = _spbase.toarray.__doc__

373

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

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

376

377 transpose.__doc__ = _spbase.transpose.__doc__

378

379 def tolil(self, copy=False):

380 if copy:

381 return self.copy()

382 else:

383 return self

384

385 tolil.__doc__ = _spbase.tolil.__doc__

386

387 def tocsr(self, copy=False):

388 M, N = self.shape

389 if M == 0 or N == 0:

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

391

392 # construct indptr array

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

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

395 idx_dtype = np.int32

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

397 indptr[0] = 0

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

399 np.cumsum(indptr, out=indptr)

400 nnz = indptr[-1]

401 else:

402 idx_dtype = self._get_index_dtype(maxval=N)

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

404 _csparsetools.lil_get_lengths(self.rows, lengths)

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

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

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

408 indptr[0] = 0

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

410

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

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

413 _csparsetools.lil_flatten_to_array(self.rows, indices)

414 _csparsetools.lil_flatten_to_array(self.data, data)

415

416 # init csr matrix

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

418

419 tocsr.__doc__ = _spbase.tocsr.__doc__

420

421

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

423 """

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

425 Cython fancy getset routines.

426

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

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

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

430 choke on them.

431

432 Parameters

433 ----------

434 i, j

435 Index arrays

436 x : optional

437 Data arrays

438

439 Returns

440 -------

441 i, j, x

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

443

444 """

445 if i.dtype > j.dtype:

446 j = j.astype(i.dtype)

447 elif i.dtype < j.dtype:

448 i = i.astype(j.dtype)

449

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

451 i = i.astype(np.intp)

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

453 j = j.astype(np.intp)

454

455 if x is not None:

456 if not x.flags.writeable:

457 x = x.copy()

458 return i, j, x

459 else:

460 return i, j

461

462

463def isspmatrix_lil(x):

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

465

466 Parameters

467 ----------

468 x

469 object to check for being a lil matrix

470

471 Returns

472 -------

473 bool

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

475

476 Examples

477 --------

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

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

480 True

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

482 False

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

484 False

485 """

486 return isinstance(x, lil_matrix)

487

488

489# This namespace class separates array from matrix with isinstance

490class lil_array(_lil_base, sparray):

491 """

492 Row-based LIst of Lists sparse array.

493

494 This is a structure for constructing sparse arrays incrementally.

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

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

497 index, per row.

498

499 This can be instantiated in several ways:

500 lil_array(D)

501 where D is a 2-D ndarray

502

503 lil_array(S)

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

505

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

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

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

509

510 Attributes

511 ----------

512 dtype : dtype

513 Data type of the array

514 shape : 2-tuple

515 Shape of the array

516 ndim : int

517 Number of dimensions (this is always 2)

518 nnz

519 size

520 data

521 LIL format data array of the array

522 rows

523 LIL format row index array of the array

524 T

525

526 Notes

527 -----

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

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

530

531 Advantages of the LIL format

532 - supports flexible slicing

533 - changes to the array sparsity structure are efficient

534

535 Disadvantages of the LIL format

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

537 - slow column slicing (consider CSC)

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

539

540 Intended Usage

541 - LIL is a convenient format for constructing sparse arrays

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

543 CSC format for fast arithmetic and matrix vector operations

544 - consider using the COO format when constructing large arrays

545

546 Data Structure

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

548 list of column indices of non-zero elements.

549 - The corresponding nonzero values are stored in similar

550 fashion in ``self.data``.

551

552 """

553

554

555class lil_matrix(spmatrix, _lil_base):

556 """

557 Row-based LIst of Lists sparse matrix.

558

559 This is a structure for constructing sparse matrices incrementally.

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

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

562 index, per row.

563

564 This can be instantiated in several ways:

565 lil_matrix(D)

566 where D is a 2-D ndarray

567

568 lil_matrix(S)

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

570

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

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

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

574

575 Attributes

576 ----------

577 dtype : dtype

578 Data type of the matrix

579 shape : 2-tuple

580 Shape of the matrix

581 ndim : int

582 Number of dimensions (this is always 2)

583 nnz

584 size

585 data

586 LIL format data array of the matrix

587 rows

588 LIL format row index array of the matrix

589 T

590

591 Notes

592 -----

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

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

595

596 Advantages of the LIL format

597 - supports flexible slicing

598 - changes to the matrix sparsity structure are efficient

599

600 Disadvantages of the LIL format

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

602 - slow column slicing (consider CSC)

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

604

605 Intended Usage

606 - LIL is a convenient format for constructing sparse matrices

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

608 CSC format for fast arithmetic and matrix vector operations

609 - consider using the COO format when constructing large matrices

610

611 Data Structure

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

613 list of column indices of non-zero elements.

614 - The corresponding nonzero values are stored in similar

615 fashion in ``self.data``.

616

617 """

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

294 statements