pyxfem.core.graph module

Graph and mesh topology utilities for finite element computations.

This module provides data structures and algorithms for handling: - 2D simplex mesh connectivity (triangles to unique edges and orientations). - Compressed index data representations for ragged/jagged arrays (CSR-like indexing). - Upward mesh adjacencies (vertex-to-element reverse mappings). - Directed and undirected graph connectivity checks and connected component coloring. - Coordinate extraction for triangle elements (with optional Numba acceleration).

class pyxfem.core.graph.CompressedDataIndex(index: NDArray[int64], data: NDArray, check=False)

Bases: object

Compressed Sparse Row (CSR) style storage for ragged 1D arrays.

Stores a list of variable-length sub-arrays within a single contiguous data array, indexed by offset pointers.

Parameters:

• index (NDArray) – Array of starting offsets of length N + 1, where index[k] to index[k + 1] defines the slice for entry k.

• data (NDArray) – Contiguous 1D buffer containing the concatenated elements.

• check (bool, optional) – If True, validates that all index bounds fall within data (default is False).

Raises:

ValueError – If check=True and any index value is negative or exceeds the data length.

ndata_perentry()

Compute the number of items stored in each entry.

Returns:

1D array of length N containing the count of elements for each entry.

Return type:

NDArray

class pyxfem.core.graph.Connections(compressed_connections_data: CompressedDataIndex, check=True)

Bases: object

Directed graph connectivity representation using CSR-style indexing.

Parameters:

• compressed_connections_data (CompressedDataIndex) – Underlying compressed data representing the adjacency list.

• check (bool, optional) – If True, validates graph integrity on initialization (default is True).

Raises:

ValueError – If check=True and the provided structure fails connectivity validation.

static check(compressed_connections_data: CompressedDataIndex) → bool

Validate if a CompressedDataIndex conforms to a valid directed graph.

Checks dtype consistency, absence of negative vertex indices, and ensures edge targets do not exceed the vertex count.

Parameters:

compressed_connections_data (CompressedDataIndex) – Graph adjacency representation to check.

Returns:

True if the data forms a valid directed graph, False otherwise.

Return type:

bool

isconnected(a: int, b: int, check=False) → bool

Check if a directed edge exists from node a to node b (a -> b).

Parameters:

• a (int) – Source node index.

• b (int) – Target node index.

• check (bool, optional) – Whether to verify node existence bounds first (default is False).

Returns:

True if a directed edge from a to b exists, False otherwise.

Return type:

bool

Raises:

ValueError – If check=True and either node a or b is out of bounds.

isin(a: int) → bool

Check whether vertex index a exists in the graph.

Parameters:

a (int) – Node index to check.

Returns:

True if node a is within graph bounds, False otherwise.

Return type:

bool

class pyxfem.core.graph.UndirectedConnections(connect: Connections, check=True)

Bases: object

Undirected graph connectivity representation using CSR-style indexing.

Enforces symmetry: if an edge exists from a -> b, the reverse edge b -> a must also be present.

Parameters:

• connect (Connections) – Directed connection instance to interpret as undirected.

• check (bool, optional) – If True, validates reciprocity of edges (default is True).

Raises:

ValueError – If check=True and reciprocity check fails.

static check(connect: Connections) → bool

Verify that every edge in the graph is reciprocal (if a->b then b->a).

Parameters:

connect (Connections) – Directed graph connection to inspect.

Returns:

True if all connections are strictly undirected, False otherwise.

Return type:

bool

isconnected(a: int, b: int, check=False) → bool

Check whether nodes a and b are connected.

Parameters:

• a (int) – First node index.

• b (int) – Second node index.

• check (bool, optional) – Whether to check bounds prior to lookup (default is False).

Returns:

True if a and b share an edge, False otherwise.

Return type:

bool

Raises:

ValueError – If check=True and either node is out of bounds.

isin(a: int) → bool

Check whether vertex index a exists in the graph.

Parameters:

a (int) – Node index.

Returns:

True if node a is within graph bounds, False otherwise.

Return type:

bool

pyxfem.core.graph.UpwardAdjacencies

alias of CompressedDataIndex

pyxfem.core.graph.build_compressed_data_index_from_list_of_list(lofl, check=False) → CompressedDataIndex

Construct a CompressedDataIndex instance from a nested Python list.

Parameters:

• lofl (list of list of int) – List of variable-length integer sequences.

• check (bool, optional) – Whether to validate bounds on creation (default is False).

Returns:

Initialized compressed sparse index structure.

Return type:

CompressedDataIndex

pyxfem.core.graph.build_undirected_connection(lofl, check=True) → UndirectedConnections

Build an UndirectedConnections instance directly from a list of adjacency lists.

Parameters:

• lofl (list of list of int) – Adjacency list representation where entry i contains neighbors of node i.

• check (bool, optional) – Whether to enforce connection validity and symmetry checks (default is True).

Returns:

The resulting undirected graph connectivity structure.

Return type:

UndirectedConnections

Raises:

ValueError – If check=True and the graph is invalid or asymmetric.

pyxfem.core.graph.coloring_connection(conn: Connections) → NDArray

Label weakly connected components in a directed graph.

Performs graph traversal to assign a unique 1-based component identifier to all reachable vertices.

Parameters:

conn (Connections) – Directed graph connectivity structure.

Returns:

Array of length num_nodes containing 1-based component color indices.

Return type:

NDArray of int

pyxfem.core.graph.coloring_undirected_connection(conn: UndirectedConnections) → NDArray

Label connected components of an undirected graph with 0-based group IDs.

Parameters:

conn (UndirectedConnections) – Undirected graph connectivity structure.

Returns:

Array of component color IDs spanning [0, num_components - 1].

Return type:

NDArray of int

pyxfem.core.graph.create_edges_from_tris(t2v: Annotated[NDArray[int64], 'Shape(N, 3)']) → Tuple[Annotated[NDArray[int64], 'Shape(N, 2)'], Annotated[NDArray[int64], 'Shape(N, 3)'], Annotated[NDArray[int64], 'Shape(N, 3)']]

Extract unique edges and their local orientations from triangle connectivities.

Parameters:

t2v (NDArray of shape (nt, 3)) – Triangle-to-vertex connectivity matrix, where each row contains the indices of the three vertices defining a triangle.

Returns:

• e2v (NDArray of shape (ne, 2)) – Array of unique edges bounding the triangles. Each row [vid0, vid1] contains vertex IDs ordered such that vid0 < vid1.

• t2e (NDArray of shape (nt, 3)) – Triangle-to-edge connectivity table. For each triangle, lists the global IDs of its 3 unique bounding edges.

• t2eflip (NDArray of shape (nt, 3)) – Edge orientation flag matrix containing binary values (0 or 1). A value of 1 indicates that the local triangle edge directed as v_i -> v_{i+1} is reversed relative to the canonical global edge in e2v.

pyxfem.core.graph.extract_txy(xy: NDArray[float64], t2v: Annotated[NDArray[int64], 'Shape(N, 3)'], out: NDArray[float64] | None = None) → NDArray[float64]

Extract spatial coordinates for all nodes in each triangle element.

Parameters:

• xy (NDArray of shape (num_nodes, dim)) – Global vertex coordinate table.

• t2v (NDArray of shape (num_elements, 3)) – Triangle-to-vertex connectivity table.

• out (NDArray of shape (num_elements, 3, dim), optional) – Preallocated output buffer. If None, an array is allocated.

Returns:

Coordinates of the 3 vertices for each triangle element.

Return type:

NDArray of shape (num_elements, 3, dim)

pyxfem.core.graph.extract_txy_numba(xy, t2v, out_txy)

Accelerated parallel kernel for triangle vertex coordinate extraction.

Parameters:

• xy (NDArray of shape (N, dim)) – Node coordinate table.

• t2v (NDArray of shape (num_elements, 3)) – Triangle-to-vertex connectivity table.

• out_txy (NDArray of shape (num_elements, 3, dim)) – Preallocated array written in place.

pyxfem.core.graph.upward_adjacencies(t: NDArray) → CompressedDataIndex

Invert downward element-to-vertex adjacencies into vertex-to-element adjacencies.

Given an element connectivity array (e.g., triangle-to-vertex), constructs the reverse mapping indicating which elements share each vertex.

Parameters:

t (NDArray of shape (num_elements, num_nodes_per_element)) – Element connectivity table.

Returns:

Compressed index structure where entry i yields the array of elements sharing vertex i.

Return type:

UpwardAdjacencies

pyxfem.core.graph.which_in_upward(upward: CompressedDataIndex, downward: Annotated[NDArray[int64], 'Shape(N, K)']) → NDArray

Locate the local node index of each vertex within its upward connected elements.

Parameters:

• upward (UpwardAdjacencies) – Upward vertex-to-element adjacencies.

• downward (DownwardAdjacencies) – Downward element-to-vertex connectivity table.

Returns:

Local column index (0, 1, …, K-1) of vertex vid inside each element referencing it in the upward adjacency structure.

Return type:

NDArray of shape matching upward.data