46. varray — Working with variable width tables.

Mesh type geometries use tables of integer data to store the connectivity between different geometric entities. The basic connectivity table in a Mesh with elements of the same type is a table of constant width: the number of nodes connected to each element is constant. However, the inverse table (the elements connected to each node) does not have a constant width.

Tables of constant width can conveniently be stored as a 2D array, allowing fast indexing by row and/or column number. A variable width table can be stored (using arrays) in two ways:

• as a 2D array, with a width equal to the maximal row length. Unused positions in the row are then filled with an invalid value (-1).

• as a 1D array, storing a simple concatenation of the rows. An additional array then stores the position in that array of the first element of each row.

In pyFormex, variable width tables were initially stored as 2D arrays: a remnant of the author’s past FORTRAN experience. With a growing professional use of pyFormex involving ever larger models, it became clear that there was a large memory (and thus also speed) penalty related to the use of 2D arrays with lots of unused entries.

The Varray class can offer important memory and speed gains for large models. With many algorithms we even found that a 2D array result could be achieved faster by first constructing a Varray and then converting that to a 2D array. Not sorting the entries in the Varray provides a further gain. The Varray class defined below therefore does not sort the rows by default, but provides methods to sort them when needed.

46.1. Classes defined in module varray

class varray.Varray(data=[], ind=None)

A variable width 2D integer array.

This class provides an efficient way to store tables of nonnegative integers when the rows of the table may have different length.

For large tables this may allow an important memory saving compared to a rectangular array where the non-existent entries are filled by some special value. Data in the Varray are stored as a single 1D array, containing the concatenation of all rows. An index is kept with the start position of each row in the 1D array.

Parameters:

• data –

  Data to initialize to a new Varray object. This can either of:

  • another Varray instance: a shallow copy of the Varray is created.

  • a list of lists of integers. Each item in the list contains one row of the table.

  • a 2D ndarray of integer type. The nonnegative numbers on each row constitute the data for that row.

  • a 1D array or list of integers, containing the concatenation of the rows. The second argument ind specifies the indices of the first element of each row.

  • a 1D array or list of integers, containing the concatenation of the rows obtained by prepending each row with the row length. The caller should make sure these 1D data are consistent.

• ind (1-dim int array_like, optional) – This is only used when data is a pure concatenation of all rows. It holds the position in data of the first element of each row. Its length is equal to the number of rows (nrows) or nrows+1. It is a non-decreasing series of integer values, starting with 0. If it has nrows+1 entries, the last value is equal to the total number of elements in data. This last value may be omitted, and will then be added automatically. Note that two subsequent elements may be equal, corresponding with an empty row.

Examples

Create a Varray from a nested list:

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> Va
Varray([[0], [1, 2], [0, 2, 4], [0, 2]])

The Varray prints in a user-friendly format:

>>> print(Va)
Varray (nrows=4, width=1..3)
  [0]
  [1 2]
  [0 2 4]
  [0 2]

The internal data are 1-D arrays:

>>> print(Va.data)
[0 1 2 0 2 4 0 2]
>>> print(Va.ind)
[0 1 3 6 8]

Other initialization methods resulting in the same Varray:

>>> Vb = Varray(Va)
>>> print(str(Vb) == str(Va))
True
>>> Vb = Varray(np.array([[-1,-1,0],[-1,1,2],[0,2,4],[-1,0,2]]))
>>> print(str(Vb) == str(Va))
True
>>> Vc = Varray([0,1,2,0,2,4,0,2], at.cumsum0([1,2,3,2]))
>>> print(str(Vc) == str(Va))
True
>>> Vd = Varray([1,0, 2,1,2, 3,0,2,4, 2,0,2])
>>> print(str(Vd) == str(Va))
True

Show info about the Varray

>>> print(Va.nrows, Va.width, Va.shape)
4 (1, 3) (4, 3)
>>> print(Va.size, Va.lengths)
8 [1 2 3 2]

Indexing: The data for any row can be obtained by simple indexing:

>>> print(Va[1])
[1 2]

This is equivalent with

>>> print(Va.row(1))
[1 2]

>>> print(Va.row(-1))
[0 2]

Change elements:

>>> Va[1][0] = 3
>>> print(Va[1])
[3 2]

Full row can be changed with matching length:

>>> Va[1] = [1, 2]
>>> print(Va[1])
[1 2]

Negative indices are allowed:

Extracted columns are filled with -1 values where needed

>>> print(Va.col(1))
[-1  2  2  2]

Select takes multiple rows using indices or bool:

>>> print(Va.select([1,3]))
Varray (nrows=2, width=2..2)
  [1 2]
  [0 2]

>>> print(Va.select(Va.lengths==2))
Varray (nrows=2, width=2..2)
  [1 2]
  [0 2]

Iterator: A Varray provides its own iterator:

>>> for row in Va:
...     print(row)
[0]
[1 2]
[0 2 4]
[0 2]

>>> print(Varray())
Varray (nrows=0, width=0..0)

property nrows

The number of rows in the Varray

property lengths

An array with the row lengths

property minwidth

The length of the shortest row

property maxwidth

The length of the longest row

property width

A tuple with the minimum and maximum width

property strwidth

A string with the mainimum and maximum row length

property size

The total number of elements in the Varray

property shape

A tuple with the number of rows and the maximum row length

property dtype

Return the data type of the elements in the Varray

copy()

Return a deep copy of the Varray

length(i)

Return the length of row i

row(i)

Return the data for the row i.

Parameters:

i (int) – The index of the row to return.

Returns:

1-dim int array – An array with the values of row i

Notes

The same is obtained by simple indexing. See the examples.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> print(Va.row(1))
[1 2]
>>> print(Va[1])
[1 2]

rowslice(i)

Return a slice object for the row i.

Parameters:

i (int) – The index of the row to return.

Returns:

slice – A slice object representing the set of indices for row i

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> print(Va.rowslice(2))
slice(3, 6, None)
>>> print(Va.data[Va.rowslice(2)])
[0 2 4]

rowlimits()

Generator for row slice limits

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> for row in Va.rowlimits():
...     print(row)
(0, 1)
(1, 3)
(3, 6)
(6, 8)

index1d(i, j)

Return the sequential index for the element with 2D index i,j

Parameters:

• i (int) – The row index

• j (int) – The column index

Returns:

int – The sequential index corresponding with position (i,j).

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> print(Va.index1d(2,2))
5

index2d(k)

Return the 2D index for the element with sequential index k

Parameters:

k (int) – The sequential index in the flat array

Returns:

• i (int) – The row index of the element with sequential index k

• j (int) – The column index of the element with sequential index k

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> print(Va.index2d(5))
(2, 2)

setRow(i, data)

Replace the data of row i

This is equivalent to self[i] = data.

col(i)

Return the data for column i

This always returns a list of length nrows. For rows where the column index i is missing, a value -1 is returned.

select(sel)

Select some rows from the Varray.

Parameters:

sel (iterable of ints or bools) – Specifies the row(s) to be selected. If type is int, the values are the row numbers. If type is bool, the length of the iterable should be exactly self.nrows; the positions where the value is True are the rows to be returned.

Returns:

Varray object – A Varray with only the selected rows.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> Va.select((1,3))
Varray([[1, 2], [0, 2]])
>>> Va.select((False,True,False,True))
Varray([[1, 2], [0, 2]])

rowindex(sel)

Return the rowindex for the elements flagged by selector sel.

sel is either a list of element numbers or a bool array with length self.size

colindex(sel)

Return the column index for the elements flagged by selector sel.

sel is either a list of element numbers or a bool array with length self.size

index(sel)

Convert a selector to an index.

Parameters:

sel (iterable of ints or bools) – Specifies the elements of the Varray to be selected. If type is int, the values are the index numbers in the flat array. If type is bool, the length of the iterable should be exactly self.size; the positions where the value is True will be returned.

Returns:

int array – The selected element numbers.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> Va.index((1,3,5,7))
array([1, 3, 5, 7])
>>> Va.index((False,True,False,True,False,True,False,True))
array([1, 3, 5, 7])

where(sel)

Return row and column index of the selected elements

sel is either a list of element numbers or a bool array with length self.size

Returns a 2D array where the first column is the row index and the second column the corresponding column index of an element selected by sel

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> Va.where([1,3,5,7])
array([[1, 0],
       [2, 0],
       [2, 2],
       [3, 1]])

sorted()

Returns a sorted Varray.

Returns a Varray with the same entries but where each row is sorted.

This returns a copy of the data, and leaves the original unchanged.

See also sort() for sorting the rows inplace.

roll(shift)

Roll the elements row by row.

Parameters:

shift (int) – The number of places by which elements are shifted. Positive values shift to the right.

Returns:

Varray – A Varray containing on each row the entries from the input Varray shifted ofter the specified number of places.

Examples

>>> Varray([[0], [0, 1, 2, 3], [0, 2, 4]]).roll(1)
Varray([[0], [3, 0, 1, 2], [4, 0, 2]])

removeFlat(ind)

Remove the element with flat index i

Parameters:

ind (int or int array_like) – Index in the flat data of the element(s) to remove.

Returns:

Varray – A Varray with the element(s) ind removed.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> Va.removeFlat(3)
Varray([[0], [1, 2], [2, 4], [0, 2]])
>>> Va.removeFlat([0,2,7])
Varray([[], [1], [0, 2, 4], [0]])

sort()

Sort the Varray inplace.

Sorting a Varray sorts the elements in each row. The sorting is done inplace.

See also sorted() for sorting the rows without changing the original.

Examples

>>> va = Varray([[0],[2,1],[4,0,2],[0,2]])
>>> va.sort()
>>> print(va)
Varray (nrows=4, width=1..3)
  [0]
  [1 2]
  [0 2 4]
  [0 2]

toArray()

Convert the Varray to a 2D array.

Returns a 2D array with shape (self.nrows,self.maxwidth), containing the row data of the Varray. Rows which are shorter than width are padded at the start with values -1.

Examples

>>> Varray([[0],[2,1],[4,0,2],[0,2]]).toArray()
array([[-1, -1,  0],
       [-1,  2,  1],
       [ 4,  0,  2],
       [-1,  0,  2]])
>>> Varray([[0,3],[2,1],[4,0],[0,2]]).toArray()
array([[0, 3],
       [2, 1],
       [4, 0],
       [0, 2]])

sameLength()

Groups the rows according to their length.

Returns:

• lengths (list) – the sorted unique row lengths

• rows (list) – the indices of the rows having the corresponding length.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> L,R = Va.sameLength()
>>> print(L)
[1 2 3]
>>> print(R)
[array([0]), array([1, 3]), array([2])]

split()

Split the Varray into 2D arrays.

Returns:

• list – A list of 2D arrays where all the rows of VA with the same number

• of columns are collected. The list is sorted in order of increasing

• number of columns.

Examples

>>> Va = Varray([[0],[1,2],[0,2,4],[0,2]])
>>> for a in Va.split():
...     print(a)
[[0]]
[[1 2]
 [0 2]]
[[0 2 4]]

toList()

Convert the Varray to a nested list.

Returns a list of lists of integers.

inverse(sort=True, expand=False)

Return the inverse of a Varray.

The inverse of a Varray is again a Varray. Values k on a row i will become values i on row k. The number of data in both Varrays is thus the same.

The inverse of the inverse is equal to the original. Two Varrays are equal if they have the same number of rows and all rows contain the same numbers, independent of their order.

Parameters:

sort (bool) – If True (default), the values on each row of the returned index are sorted. The default (False) will leave the values in the order obtained by the algorithm, which depends on Python/numpy sorting, and usually turns out to be sorted as well.

Returns:

• Varray

• The inverse index, as a Varray (default).

• Each row i of the inverse contains the numbers of the rows of the

• input in which a value i appeared. The rows are sorted by default.

Examples

>>> a = Varray([[0,1],[2,0],[1,2],[4]])
>>> b = a.inverse()
>>> c = b.inverse()
>>> print(a,b,c)
Varray (nrows=4, width=1..2)
  [0 1]
  [2 0]
  [1 2]
  [4]
 Varray (nrows=5, width=0..2)
  [0 1]
  [0 2]
  [1 2]
  []
  [3]
 Varray (nrows=4, width=1..2)
  [0 1]
  [0 2]
  [1 2]
  [4]

>>> a = Varray([[-1,0,1],[0,2,-1],[2,1,1],[3,-2,0]])
>>> print(a.inverse())
Varray (nrows=4, width=1..3)
  [0 1 3]
  [0 2 2]
  [1 2]
  [3]

classmethod concatenate(varrays)

Concatenate a list of Varrays to a single Varray.

Parameters:

varrays (list of Varray) – The list of Varrays to concatenate.

Returns:

Varray – The concatenated Varrays.

Examples

>>> VA0 = Varray([[0,1],[2,3,4]])
>>> VA1 = Varray([[5,6]])
>>> VA2 = Varray([[7,8],[9]])
>>> VA = Varray.concatenate([VA0,VA1,VA2])
>>> print(VA)
Varray (nrows=5, width=1..3)
  [0 1]
  [2 3 4]
  [5 6]
  [7 8]
  [9]

classmethod fromArrays(arrays)

Concatenate a list of 2D int arrays into a Varray

Examples

>>> VA = Varray.fromArrays([
...     [[1,1], [2,2]],
...     [[3,3,3], [4,4,4]],
...     [[5,5], [6,6], [7,7]],
... ])
>>> print(VA)
Varray (nrows=7, width=2..3)
  [1 1]
  [2 2]
  [3 3 3]
  [4 4 4]
  [5 5]
  [6 6]
  [7 7]

46.2. Functions defined in module varray

varray.graphColors(adj)

Colorizes all nodes of a graph using Welsh-Powell algorithm.

The algorithm determines a color scheme thus that no two connected nodes of a graph have the same color. While not guaranteeing to be the optimal solution, it usually is a very close. This function can for example be used to determine a color scheme for different areas on a planar map, such that no two touching regions will have the same color.

Parameters:

adj (varray_like) – An adjacency array where each row i lists the nodes connected to node i. It can be a Varray or a regular 2d array padded with -1 entries to have constant row length.

Returns:

int array – An 1-d int array with the color palette numbers for the nodes.

Examples