Reference Manual#

bounded_domains.graph module#

Graph structure and auxiliary constructs for representation of polygonal domains.

class bounded_domains.graph.Graph(domain: bounded_domains.domains.PolygonalDomain)#

Bases: object

A graph modeling the relationship of vertices in a polygonal domain.

The graph is stored in form of an adjacency matrix (using SparseMatrix).

Parameters: domain – The PolygonalDomain whose vertices should be modeled by the graph.

property order: int#: The order of the graph, i.e., the number of vertices.

plot(filename: str | Path | None = None, **kwargs) → None#

A plot of the graph.

Note

For the sake of visual clarity, the reflexive edges are not plotted. For the other edges, their color corresponds to their weight.

This is the sample output for a domain generated via rectangle_domain_data():

Parameters

filename – The name of the file the plot is saved to.
kwargs – Further keyword arguments are passed to matplotlib.

property size: int#: The size of the graph, i.e., the number of edges.

class bounded_domains.graph.SparseMatrix(array: list[list[float]])#

Bases: object

A sparse matrix implementing the CRS format.

Parameters: array – A two-dimensional (rectangular) array of floats. Only non-zero entries will be stored.

cell_iterator() → Iterator[tuple[tuple[int, int], float]]#: An iterator over all non-zero entries with their matrix coordinates.

property columns#: The number of columns in the matrix.

static from_CRS(values: list[float], column_indices: list[int], row_pointers: list[int], columns: int) → SparseMatrix#

Initialization of a SparseMatrix from the raw CRS data.

Parameters

values – The list of non-zero entries.
column_indices – The list of column indices of the non-zero entries.
row_pointers – The list containing the (cumulative) number of non-zero entries.
columns – The number of columns of the matrix.

plot(filename: str | Path | None = None) → None#

A plot of this matrix.

For the weighted adjacency matrix from a domain generated via rectangle_domain_data(), the generated plot looks like this:

Parameters: filename – The name of the file the plot is written to. If None (the default), matplotlib just shows the plot.

static read(filename: str | Path) → None#

Read a sparse matrix from a file.

The file can either be an ASCII file (with rows separated by newlines, and space-separated entries), or a binary file created with SparseMatrix.save().

Parameters: filename – The name of the file to be read.

property rows#: The number of rows in the matrix.

save(filename: str | Path, binary: bool = False) → None#

Save the matrix to a file.

Parameters

filename – The name of the file the matrix will be stored in.
binary – If False (the default), the matrix will be written to a plain text ASCII file (rows are newline-separated, entries are tab-separated). Otherwise the matrix is written to a compressed (via gzip) binary file.

class bounded_domains.graph.WeightedGraph(domain: bounded_domains.domains.PolygonalDomain)#

Bases: bounded_domains.graph.Graph

A weighted graph modeling the relationship of vertices in a polygonal domain.

The weight of an edge between distinct vertices \(u\) and \(v\) is the inverse of the squared node distance. The weight of reflexive edges \((v, v)\) is the negative sum of the weights of all non-reflexive edges incident to \(v\).

Parameters: domain – The PolygonalDomain whose vertices should be modeled by the graph.

bounded_domains.domains module#

Data structures and classes for polygonal domains.

class bounded_domains.domains.Element(id: int, vertices: Iterable[int])#

Bases: object

Representation of a (triangular) element.

Parameters

id – The index of the element.
vertices – A list of indices of the vertices of this (triangular) element.

class bounded_domains.domains.Node(x, y)#

Bases: tuple

property x#: Alias for field number 0

property y#: Alias for field number 1

class bounded_domains.domains.PolygonalDomain(elements: list[Element], vertices: list[Node])#

Bases: object

A polygonal domain consisting of (triangular) elements.

Parameters

elements – The list of elements the domain consists of.
coordinates – The list of Nodes specifying the coordinates of the elements of the domain.

adjacent_elements(element: Element | int, shared_edge: bool = False) → list[Element]#

The adjacent elements of the specified element.

Parameters

element – The element whose neighbors are determined. If an int is passed, it is assumed to be the index of an element of the domain.
shared_edge – If True, only elements that share an edge with the specified element are returned. Otherwise (the default behavior) all elements that share at least one vertex are returned.

adjacent_vertices(vertex_index: int) → list[int]#

All vertices (by their indices) that are adjacent to this vertex.

Parameters: vertex_index – The index of the vertex whose neighboring vertices are returned.

build_mappings() → None#: Iterate through domain elements and build auxiliary relation dictionaries.

build_node_tree(vertices: list[Node]) → None#

Build auxiliary kd-tree used for distance queries.

Parameters: vertices – A list of 2D coordinates.

closest_element(node: bounded_domains.domains.Node, compare_all_elements: bool = False) → bounded_domains.domains.Element#

Determines a element of the domain that is closest to the specified node.

The default, efficient strategy to find the closest element is as follows:

First, by calling closest_vertex(), the closest vertex of the polygonal domain is determined.
Second, elements_containing_vertex() is used to determine all elements which the closest vertex is contained in.
Third, the determined elements together with their adjacent ones (via adjacent_elements()) make up a set of candidate elements.
Finally, the distance to all elements in the candidate set is computed using distance_to_element(), and an Element with minimal distance is returned.

Note

In pathologic situations where the polygonal domain is not connected, the strategy that only considers elements adjacent to the ones containing a closest vertex can produce wrong results.

Parameters

node – The node to which an element with minimum distance is found.
compare_all_elements – If False (the default) only elements adjacent to the ones containing the closest vertex are queried. Otherwise the distance to all elements is computed.

closest_vertex(node: bounded_domains.domains.Node) → int#

Determines a closest vertex to the specified node.

This is done by querying the kd-tree storing coordinate data.

Parameters: node – The node to which a closest vertex is determined.
Returns: The index of a closest vertex.
Return type: int

distance_to_element(node: bounded_domains.domains.Node, element_id: int) → float#

The distance from a given input Node to the element with the specified id.

We use the following approach to determine the distance between the point \(P\) and the triangle \(\triangle ABC\). First, we solve the equation \(A + (B-A) t_1 + (C-A) t_2 = P\). Depending on the values of \(t_1\) and \(t_2\), we proceed as follows:

In case \(0\leq t_1, t_2 \leq 1\) the point is inside of \(\triangle ABC\) and the distance is thus 0,
if \(t_1 < 0\) we compute the closest point on the segment \(AC\),
if \(t_2 < 0\) we compute the closest point on the segment \(AB\),
and if \(t_1 + t_2 > 1\) we compute the closest point on the segment \(BC\).

Parameters

node – The node to which the distance is computed.
element_id – The index of the element to which the distance is computed.

elements_containing_vertex(vertex_index: int) → list[Element]#

A list of all elements containing the specified vertex.

Parameters: vertex_index – The index of the vertex contained in the returned elements.

static from_files(element_file_path: str | Path, vertex_file_path: str | Path) → PolygonalDomain#

Constructs a PolygonalDomain by reading entries from files.

Parameters

element_file_path – Path of the element file.
vertex_file_path – Path of the vertex file.

property num_vertices: int#: The number of vertices of the domain.

vertex(node_index: int) → bounded_domains.domains.Node#

The coordinates of a vertex given its index.

Parameters: node_index – The index of the vertex whose coordinates are returned.

bounded_domains.domains.distance_point_on_segment(P: bounded_domains.domains.Node, A: bounded_domains.domains.Node, B: bounded_domains.domains.Node) → float#

Determines the shortest distance from a point P to a line segment AB.

Parameters

P – The node from which the distance to the segment is determined.
A – An endpoint of the line segment.
B – An endpoint of the line segment.

bounded_domains.utils module#

Utility functions (in particular file operations).

bounded_domains.utils.read_element_file(file_path: Path | str) → list[Element]#

Read an element file and return its content in a list.

Also checks whether the specified file is formatted correctly.

An element file is a plain text file formatted like this:

number of Elements
vertex1     vertex2     vertex3
vertex1     vertex2     vertex3
...

The vertices are given in form of integer indices referring to the corresponding entry in the vertex file.

Parameters: file_path – The path to the element file.

bounded_domains.utils.read_vertex_file(file_path: Path | str) → list[Node]#

Read a vertex file and return its content in a list.

Also checks whether the specified file is formatted correctly.

A vertex file is a plain text file formatted like this:

number of coordinates
x   y
x   y
...

The x and y coordinates are given as floats.

Parameters: file_path – The path to the vertex file.

bounded_domains.utils.rectangle_domain_data(m: int, n: int) → tuple[list[Element], list[Node]]#

Generate data for a triangulation of the unit square.

Parameters

n – The number of intervals along the x-axis.
m – The number of intervals along the y-axis.

Returns

A tuple with the first entry being the list of elements and the second entry being the list of nodes required to instantiate a PolygonalDomain.

Return type

tuple[list[Element], list[Node]]