8. connectivity — A class and functions for handling nodal connectivity.

This module defines a specialized array class for representing nodal connectivity. This is e.g. used in mesh models, where geometry is represented by a set of numbered points (nodes) and the geometric elements are described by refering to the node numbers. In a mesh model, points common to adjacent elements are unique, and adjacency of elements can easily be detected from common node numbers.

Classes defined in module connectivity

class connectivity.Connectivity

A class for handling element/node connectivity.

A connectivity object is a 2-dimensional integer array with all non-negative values. Each row of the array defines an element by listing the numbers of its lower entity types. A typical use is a Mesh object, where each element is defined in function of its nodes. While in a Mesh the word ‘node’ will normally refer to a geometrical point, here we will use ‘node’ for the lower entity whatever its nature is. It doesn’t even have to be a geometrical entity.

The current implementation limits a Connectivity object to numbers that are smaller than 2**31.

In a row (element), the same node number may occur more than once, though usually all numbers in a row are different. Rows containing duplicate numbers are called degenerate elements. Rows containing the same node sets, albeit different permutations thereof, are called duplicates.

A new Connectivity object is created with the following syntax

Connectivity(data=[],dtyp=None,copy=False,nplex=0)

Parameters:

• data: should be compatible with an integer array with shape (nelems,nplex), where nelems is the number of elements and nplex is the plexitude of the elements.
• dtype: can be specified to force an integer type but is set by default from the passed data.
• copy: can be set True to force copying the data. By default, the specified data will be used without copying, if possible.
• nplex: can be specified to force a check on the plexitude of the data, or to set the plexitude for an empty Connectivity. An error will be raised if the specified data do not match the specified plexitude. If an eltype is specified, the plexitude of the element type will override this value.
• eltype: an Element type (a subclass of Element) or the name of an Element type, or None (default). If the Connectivity will be used to create a Mesh, the proper element type or name should be set: either here or at Mesh creation time. If the Connectivity will be used for other purposes, the element type may be not important.

Example:

>>> print(Connectivity([[0,1,2],[0,1,3],[0,3,2],[0,5,3]]))
[[0 1 2]
 [0 1 3]
 [0 3 2]
 [0 5 3]]

nelems()

Return the number of elements in the Connectivity table.

Example:

>>> Connectivity([[0,1,2],[0,1,3],[0,3,2],[0,5,3]]).nelems()
4

maxnodes()

Return an upper limit for number of nodes in the connectivity.

This returns the highest node number plus one.

nnodes()

Return the actual number of nodes in the connectivity.

This returns the count of the unique node numbers.

nplex()

Return the plexitude of the elements in the Connectivity table.

Example:

>>> Connectivity([[0,1,2],[0,1,3],[0,3,2],[0,5,3]]).nplex()
3

report()

Format a Connectivity table

testDegenerate()

Flag the degenerate elements (rows).

A degenerate element is a row which contains at least two equal values.

Returns a boolean array with shape (self.nelems(),). The True values flag the degenerate rows.

Example:

>>> Connectivity([[0,1,2],[0,1,1],[0,3,2]]).testDegenerate()
array([False,  True, False], dtype=bool)

listDegenerate()

Return a list with the numbers of the degenerate elements.

Example:

>>> Connectivity([[0,1,2],[0,1,1],[0,3,2]]).listDegenerate()
array([1])

listNonDegenerate()

Return a list with the numbers of the non-degenerate elements.

Example:

>>> Connectivity([[0,1,2],[0,1,1],[0,3,2]]).listNonDegenerate()
array([0, 2])

removeDegenerate()

Remove the degenerate elements from a Connectivity table.

Degenerate elements are rows with repeating values.

Returns a Connectivity with the degenerate elements removed.

Example:

>>> Connectivity([[0,1,2],[0,1,1],[0,3,2]]).removeDegenerate()
Connectivity([[0, 1, 2],
       [0, 3, 2]])

reduceDegenerate(target=None)

Reduce degenerate elements to lower plexitude elements.

This will try to reduce the degenerate elements of the Connectivity to a lower plexitude. This is only possible if an element type was set in the Connectivity. This function uses the data of the Element database in elements.

If a target element type is given, only the reductions to that element type are performed. Else, all the target element types for which a reduction scheme is available, will be tried.

Returns:

A list of Connectivities of which the first one contains the originally non-degenerate elements and the last one contains the elements that could not be reduced and may be empty. If the original Connectivity does not have an element type set, or the element type does not have any reduction schemes defined, a list with only the original is returned.

Note

If the Connectivity is part of a Mesh, you should use the Mesh.reduceDegenerate method instead, as that one will preserve the property numbers into the resulting Meshes.

Example:

>>> C = Connectivity([[0,1,2],[0,1,1],[0,3,2]],eltype='line3')
>>> print(C.reduceDegenerate())
[Connectivity([[0, 1]]), Connectivity([[0, 1, 2],
       [0, 3, 2]])]

testDuplicate(permutations=True, return_multiplicity=False)

Test the Connectivity list for duplicates.

By default, duplicates are elements that consist of the same set of nodes, in any particular order. Setting permutations to False will only find the duplicate rows that have matching values at every position.

Returns a tuple of two arrays and optionally a dictionary:

• an index used to sort the elements
• a flags array with the value True for indices of the unique elements and False for those of the duplicates.
• if return_multiplicity is True, returns also an extra dict with multiplicities as keys and a list of elements as value.

Example:

>>> conn = Connectivity([[0,1,3],[2,3,0],[0,2,3],[0,1,2],[0,2,1],[0,3,2]])
>>> print(conn)
[[0 1 3]
 [2 3 0]
 [0 2 3]
 [0 1 2]
 [0 2 1]
 [0 3 2]]
>>> ind,ok,D = conn.testDuplicate(return_multiplicity=True)
>>> print(ind,ok)
[3 4 0 1 2 5] [ True False  True  True False False]
>>> print(ok.cumsum())
[1 1 2 3 3 3]
>>> print(D)
{1: array([0]), 2: array([3, 4]), 3: array([1, 2, 5])}

listUnique(permutations=True)

Return a list with the numbers of the unique elements.

Example:

>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).listUnique()
array([0, 2])

listDuplicate(permutations=True)

Return a list with the numbers of the duplicate elements.

Example:

>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).listDuplicate()
array([1])

removeDuplicate(permutations=True)

Remove duplicate elements from a Connectivity list.

By default, duplicates are elements that consist of the same set of nodes, in any particular order. Setting permutations to False will only remove the duplicate rows that have matching values at matching positions.

Returns a new Connectivity with the duplicate elements removed.

Example:

>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).removeDuplicate()
Connectivity([[0, 1, 2],
       [0, 3, 2]])

reorder(order='nodes')

Reorder the elements of a Connectivity in a specified order.

This does not actually reorder the elements itself, but returns an index with the order of the rows (elements) in the connectivity table that meets the specified requirements.

Parameters:

• order: specifies how to reorder the elements. It is either one of the special string values defined below, or else it is an index with length equal to the number of elements. The index should be a permutation of the numbers in range(self.nelems(). Each value gives of the number of the old element that should be placed at this position. Thus, the order values are the old element numbers on the position of the new element number.

  order can also take one of the following predefined values, resulting in the corresponding renumbering scheme being generated:

  • ‘nodes’: the elements are renumbered in order of their appearance in the inverse index, i.e. first are the elements connected to node 0, then the as yet unlisted elements connected to node 1, etc.
  • ‘random’: the elements are randomly renumbered.
  • ‘reverse’: the elements are renumbered in reverse order.

Returns:

A 1-D integer array which is a permutation of arange(self.nelems(), such that taking the elements in this order will produce a Connectivity reordered as requested. In case an explicit order was specified as input, this order is returned after checking that it is indeed a permutation of range(self.nelems().

Example:

>>> A = Connectivity([[1,2],[2,3],[3,0],[0,1]])
>>> A[A.reorder('reverse')]
Connectivity([[0, 1],
       [3, 0],
       [2, 3],
       [1, 2]])
>>> A.reorder('nodes')
array([3, 2, 0, 1])
>>> A[A.reorder([2,3,0,1])]
Connectivity([[3, 0],
       [0, 1],
       [1, 2],
       [2, 3]])

renumber(start=0)

Renumber the nodes to a consecutive integer range.

The node numbers in the table are changed thus that they form a consecutive integer range starting from the specified value.

Returns a tuple:

• elems: the renumbered connectivity
• oldnrs: The sorted list of unique (old) node numbers. The new node numbers are assigned in order of increasing old node numbers, thus the old node number for new node number i can be found at position i - start.

Example:

>>> e,n = Connectivity([[0,2],[1,4],[4,2]]).renumber(7)
>>> print(e,n)
[[ 7  9]
 [ 8 10]
 [10  9]] [0 1 2 4]

inverse()

Return the inverse index of a Connectivity table.

Returns the inverse index of the Connectivity, as computed by arraytools.inverseIndex().

Example:

>>> Connectivity([[0,1,2],[0,1,4],[0,4,2]]).inverse()
array([[ 0,  1,  2],
       [-1,  0,  1],
       [-1,  0,  2],
       [-1, -1, -1],
       [-1,  1,  2]])

nParents()

Return the number of elements connected to each node.

Returns a 1-D int array with the number of elements connected to each node. The length of the array is equal to the highest node number + 1. Unused node numbers will have a count of zero.

Example:

>>> Connectivity([[0,1,2],[0,1,4],[0,4,2]]).nParents()
array([3, 2, 2, 0, 2])

connectedTo(nodes, return_ncon=False)

Check if the elements are connected to the specified nodes.

• nodes: a single node number or a list/array thereof,
• return_ncon: if True, also return the number of connections for each element.

Returns an int array with the numbers of the elements that contain at least one of the specified nodes. If return_ncon is True, also returns an int array giving the number of connections for each connected element.

Example:

>>> A = Connectivity([[0,1,2],[0,1,3],[0,3,2],[1,2,3]])
>>> A.connectedTo(2)
array([0, 2, 3])
>>> A.connectedTo([0,1,3],True)
(array([0, 1, 2, 3]), array([2, 3, 2, 2]))

hits(nodes)

Count the nodes from a list connected to the elements.

nodes: a single node number or a list/array thereof

Returns an (nelems,) shaped int array with the number of nodes from the list that are contained in each of the elements.

Note that this information can also be got from meth:connectedTo. This method however exapnds the results to the full element set, making it apt for use in selector expressions like:

self[self.hits(nodes) >= 2]

Example:

>>> A = Connectivity([[0,1,2],[0,1,3],[0,3,2],[1,2,3]])
>>> A.hits(2)
array([1, 0, 1, 1])
>>> A.hits([0,1,3])
array([2, 3, 2, 2])

adjacency(kind='e', mask=None)

Return a table of adjacent items.

Create an element adjacency table (kind=’e’) or node adjacency table (kind=’n’).

An element i is said to be adjacent to element j, if the two elements have at least one common node.

A node i is said to be adjacent to node j, if there is at least one element containing both nodes.

Parameters:

• kind: ‘e’ or ‘n’, requesting resp. element or node adjacency.

• mask: Either None or a boolean array or index flagging the nodes which are to be considered connectors between elements. If None, all nodes are considered connections. This option is only useful in the case kind == ‘e’. If you want to use an element mask for the ‘n’ case, just apply the (element) mask beforehand:

  self[mask].adjacency('n')
  

Returns:

An Adjacency array with shape (nr,nc), where row i holds a sorted list of all the items that are adjacent to item i, padded with -1 values to create an equal list length for all items.

Example:

>>> Connectivity([[0,1],[0,2],[1,3],[0,5]]).adjacency('e')
Adjacency([[ 1,  2,  3],
       [-1,  0,  3],
       [-1, -1,  0],
       [-1,  0,  1]])
>>> Connectivity([[0,1],[0,2],[1,3],[0,5]]).adjacency('e',mask=[1,2,3,5])
Adjacency([[ 2],
       [-1],
       [ 0],
       [-1]])
>>> Connectivity([[0,1],[0,2],[1,3],[0,5]]).adjacency('n')
Adjacency([[ 1,  2,  5],
       [-1,  0,  3],
       [-1, -1,  0],
       [-1, -1,  1],
       [-1, -1, -1],
       [-1, -1,  0]])
>>> Connectivity([[0,1,2],[0,1,3],[2,4,5]]).adjacency('n')
Adjacency([[-1,  1,  2,  3],
       [-1,  0,  2,  3],
       [ 0,  1,  4,  5],
       [-1, -1,  0,  1],
       [-1, -1,  2,  5],
       [-1, -1,  2,  4]])
>>> Connectivity([[0,1,2],[0,1,3],[2,4,5]])[[0,2]].adjacency('n')
Adjacency([[-1, -1,  1,  2],
       [-1, -1,  0,  2],
       [ 0,  1,  4,  5],
       [-1, -1, -1, -1],
       [-1, -1,  2,  5],
       [-1, -1,  2,  4]])

selectNodes(selector)

Return a Connectivity containing subsets of the nodes.

Parameters:

• selector: an object that can be converted to a 1-dim or 2-dim int array. Examples are a tuple of local node numbers, or a list of such tuples all having the same length. Each row of selector holds a list of the local node numbers that should be retained in the new Connectivity table.

Returns:

A Connectivity object with shape (self.nelems*selector.nelems,selector.nplex). This function does not collapse the duplicate elements. The eltype of the result is equal to that of the selector, possibly None.

Example:

>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).selectNodes([[0,1],[0,2]])
Connectivity([[0, 1],
       [0, 2],
       [0, 2],
       [0, 1],
       [0, 3],
       [0, 2]])

insertLevel(selector, permutations=True)

Insert an extra hierarchical level in a Connectivity table.

A Connectivity table identifies higher hierarchical entities in function of lower ones. This method inserts an extra level in the hierarchy. For example, if you have volumes defined in function of points, you can insert an intermediate level of edges, or faces. Multiple intermediate level entities may be created from each element.

Parameters:

• selector: an object that can be converted to a 1-dim or 2-dim integer array. Examples are a tuple of local node numbers, or a list of such tuples all having the same length. Each row of selector holds a list of the local node numbers that should be retained in the new Connectivity table.

• permutations: bool . If True, rows which are permutations of the same data are considered equal.

  If the Connectivity has an element type, selector can also be a single integer specifying one of the hierarchical levels of element entities (See the Element class). In that case the selector is constructed automatically from self.eltype.getEntities(selector).

Returns:

• hi: a Connectivity defining the original elements in function of the intermediate level ones,
• lo: a Connectivity defining the intermediate level items in function of the lowest level ones (the original nodes). If the selector has an eltype attribute, then lo will inherit the same eltype value.

All intermediate level items that consist of the same set of nodes in any permutation order and with any multiplicity, are considered identical and are collapsed into single items if permutations is True. The resulting node numbering of the created intermediate entities (the lo return value) respects the numbering order of the original elements and applied the selector, but it is undefined which of the collapsed sequences is returned.

Because the precise order of the data in the collapsed rows is lost, it is in general not possible to restore the exact original table from the two result tables. See however Mesh.getBorder() for an application where an inverse operation is possible, because the border only contains unique rows. See also Mesh.combine(), which is an almost inverse operation for the general case, if the selector is complete. The resulting rows may however be permutations of the original.

Example:

>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).insertLevel([[0,1],[1,2],[2,0]])
(Connectivity([[0, 3, 1],
       [1, 3, 0],
       [2, 4, 1]]), Connectivity([[0, 1],
       [2, 0],
       [0, 3],
       [1, 2],
       [3, 2]]))
 >>> Connectivity([[0,1,2,3]]).insertLevel([[0,1,2],[1,2,3],[0,1,1],[0,0,1],[1,0,0]])
 (Connectivity([[1, 2, 0, 0, 0]]), Connectivity([[0, 1, 1],
        [0, 1, 2],
        [1, 2, 3]]))

combine(lo)

Combine two hierarchical Connectivity levels to a single one.

self and lo are two hierarchical Connectivity tables, representing higher and lower level respectively. This means that the elements of self hold numbers which point into lo to obtain the lowest level items.

In the current implementation, the plexitude of lo should be 2!

As an example, in a structure of triangles, hi could represent triangles defined by 3 edges and lo could represent edges defined by 2 vertices. This method will then result in a table with plexitude 3 defining the triangles in function of the vertices.

This is the inverse operation of insertLevel() with a selector which is complete. The algorithm only works if all vertex numbers of an element are unique.

Example:

>>> hi,lo = Connectivity([[0,1,2],[0,2,1],[0,3,2]]).          insertLevel([[0,1],[1,2],[2,0]])
>>> hi.combine(lo)
Connectivity([[0, 1, 2],
       [0, 2, 1],
       [0, 3, 2]])

resolve()

Resolve the connectivity into plex-2 connections.

Creates a Connectivity table with a plex-2 (edge) connection between any two nodes that are connected to a common element.

There is no point in resolving a plexitude 2 structure. Plexitudes lower than 2 can not be resolved.

Returns a plex-2 Connectivity with all connections between node pairs. In each element the nodes are sorted.

Example:

>>> print([ i for i in combinations(range(3),2) ])
[(0, 1), (0, 2), (1, 2)]
>>> Connectivity([[0,1,2],[0,2,1],[0,3,2]]).resolve()
Connectivity([[0, 1],
       [0, 2],
       [0, 3],
       [1, 2],
       [2, 3]])

sharedNodes(elist)

Return the list of nodes shared by all elements in elist

Parameters:

• elist: an integer list-like with element numbers.

Returns a 1-D integer array with the list of nodes that are common to all elements in the specified list. This array may be empty.

Functions defined in module connectivity

connectivity.findConnectedLineElems(elems)

Find a single path of connected line elems.

This function is intended as a helper function for connectedLineElems(). It should probably not be used directly, because, as a side-effect, it changes the data in the elems argument. connectedLineElems() does not have this inconvenience.

The function searches a Connectivity table for a chain of elements in which the first node of all but the first element is equal to the last node of the previous element. To create such a chain, elements may be reordered and the node sequence of an element may be reversed.

Parameters:

• elems: Connectivity-like. Any plexitude is allowed, but only the first and the last column are relevant.

Returns:

• con: a Connectivity with the same shape as the input Connectivity elems, holding a single chain extracted from the input and filled with -1 for the remainder (if any). The chain will not necessarily be the longest path. It will however at least contain the first element of the input table.
• inv: an int array with two columns and number of rows equal to that of con. The first column holds the row number in elems of the entries in con. The second column holds a value +1 or -1, flagging whether the element is traversed in original direction (+1) in the chain or in the reverse direction (-1).

Example:

>>> con,inv = findConnectedLineElems([[0,1],[1,2],[0,4],[4,2]])
>>> print(con)
[[0 1]
 [1 2]
 [2 4]
 [4 0]]
>>> print(inv)
[[ 0  1]
 [ 1  1]
 [ 3 -1]
 [ 2 -1]]

>>> con,inv = findConnectedLineElems([[0,1],[1,2],[0,4]])
>>> print(con)
[[2 1]
 [1 0]
 [0 4]]
>>> print(inv)
[[ 1 -1]
 [ 0 -1]
 [ 2  1]]

>>> C = Connectivity([[0,1],[0,2],[0,3],[4,5]])
>>> con,inv = findConnectedLineElems(C)
>>> print(con)
[[ 1  0]
 [ 0  2]
 [-1 -1]
 [-1 -1]]
>>> print(inv)
[[ 0 -1]
 [ 1  1]
 [-1  0]
 [-1  0]]
>>> print(C)
[[-1 -1]
 [-1 -1]
 [ 0  3]
 [ 4  5]]

connectivity.connectedLineElems(elems, return_indices=False)

Partition a collection of line segments into connected polylines.

The input argument is a (nelems,2) shaped array of integers. Each row holds the two vertex numbers of a single line segment.

The return value is a list of Connectivity tables of plexitude 2. The line elements of each Connectivity are ordered to form a continuous connected segment, i.e. the first vertex of each line element in a table is equal to the last vertex of the previous element. The connectivity tables are sorted in order of decreasing length.

If return_indices = True, a second list of tables is returned, with the same shape as those in the first list. The tables of the second list contain in the first column the original element number of the entries, and in the second column a value +1 or -1 depending on whether the element traversal in the connected segment is in the original direction (+1) or the reverse (-1).

Example:

>>> connectedLineElems([[0,1],[1,2],[0,4],[4,2]])
[Connectivity([[0, 1],
       [1, 2],
       [2, 4],
       [4, 0]])]

>>> connectedLineElems([[0,1],[1,2],[0,4]])
[Connectivity([[2, 1],
       [1, 0],
       [0, 4]])]

>>> connectedLineElems([[0,1],[0,2],[0,3],[4,5]])
[Connectivity([[1, 0],
       [0, 2]]), Connectivity([[4, 5]]), Connectivity([[0, 3]])]

>>> connectedLineElems([[0,1],[0,2],[0,3],[4,5]])
[Connectivity([[1, 0],
       [0, 2]]), Connectivity([[4, 5]]), Connectivity([[0, 3]])]

>>> connectedLineElems([[0,1],[0,2],[0,3],[4,5]],True)
([Connectivity([[1, 0],
       [0, 2]]), Connectivity([[4, 5]]), Connectivity([[0, 3]])], [array([[ 0, -1],
       [ 1,  1]], dtype=int32), array([[3, 1]], dtype=int32), array([[2, 1]], dtype=int32)])
>>> connectedLineElems([[0,1,2],[2,0,3],[0,3,1],[4,5,2]])
[Connectivity([[3, 0, 2],
       [2, 1, 0],
       [0, 3, 1]]), Connectivity([[4, 5, 2]])]

Obviously, from the input elems table and the second return value, the first return value could be reconstructed:

first = [
    where(i[:,-1:] > 0, elems[i[:,0]], elems[i[:,0],::-1])
    for i in second
]

But since the construction of the first list is required by the algorithm, it is returned anyway.

connectivity.adjacencyArrays(elems, nsteps=1)

Create adjacency arrays for 2-node elements.

elems is a (nr,2) shaped integer array. The result is a list of adjacency arrays, where row i of adjacency array j holds a sorted list of the nodes that are connected to node i via a shortest path of j elements, padded with -1 values to create an equal list length for all nodes. This is: [adj0, adj1, ..., adjj, ... , adjn] with n=nsteps.

Example:

>>> adjacencyArrays([[0,1],[1,2],[2,3],[3,4],[4,0]],3)
[array([[0],
       [1],
       [2],
       [3],
       [4]]), Adjacency([[1, 4],
       [0, 2],
       [1, 3],
       [2, 4],
       [0, 3]]), array([[2, 3],
       [3, 4],
       [0, 4],
       [0, 1],
       [1, 2]]), array([], shape=(5, 0), dtype=int64)]