Operations on connectivity and adjacency graphs#

The package pysdic provides functions to handle connectivity and adjacency graphs commonly used in SDIC analyses. This allows users to perform operations such as computing adjacency matrices, finding neighboring vertices or elements, and manipulating connectivity information for meshes.

A graph is a mathematical structure used to model pairwise relations between objects constructed from a set of vertices and edges (connections between vertices). The distance between two vertices in a graph is defined as the length of the shortest path connecting them, where the length is measured in terms of the number of edges traversed. The neighbors of a vertex are the vertices that are directly connected to it by an edge, while the neighborhood of a vertex includes all vertices that can be reached from it within a certain distance.

In this section:

  • graph is a List[List[int]] containing for each vertex the list of its neighbors.

  • adjacency_matrix is a Numpy or Scipy sparse square matrix of integers storing the distance between vertices in the graph.

  • neighborhood is a List[List[int]] containing for each vertex the list of its neighbors within a certain distance.

Core algorithms (BFS)#

The core algorithms for handling connectivity and adjacency graphs in pysdic are based on Breadth-First Search (BFS) techniques. BFS is a graph traversal algorithm that explores the vertices of a graph in layers, starting from a given source vertex and visiting all its neighbors before moving on to the neighbors’ neighbors. This approach is efficient for finding neighboring vertices or elements in a mesh, as well as for constructing adjacency matrices.

bfs_distance(graph, start[, max_distance, ...])

Perform a breadth-first search (BFS) to compute the shortest path distances from a starting vertex to all other vertices in the graph.

bfs_neighborhood(graph, start, max_distance)

Perform a breadth-first search (BFS) to compute the neighborhood of a starting vertex in the graph, where the neighborhood of a vertex is defined as the set of vertices that are within a specified distance from the vertex in the connectivity of the mesh.

compute_adjacency_matrix(graph[, max_distance])

Compute the adjacency matrix from the adjacency graph of the vertices, where the distance between two vertices is defined as the minimum number of elements that must be traversed to go from one vertex to another.

compute_neighborhood(graph[, max_distance, ...])

Compute the neighborhood of each vertex in the graph, where the neighborhood of a vertex is defined as the set of vertices that are within a specified distance from the vertex in the connectivity of the mesh.

Convenience functions for adjacency and neighborhood in a mesh#

Some functions in pysdic allow users to compute adjacency matrices and neighborhood from the connectivity of a mesh, which is a common representation in SDIC analyses.To

create_vertices_adjacency_graph(connectivity)

Create the vertices adjacency graph from the connectivity of the mesh, where two vertices are neighbors if there is an element in the mesh containing both vertices.

create_elements_adjacency_graph(connectivity)

Create the elements adjacency graph from the connectivity of the mesh, where two elements are neighbors if they share at least one vertex in the mesh.

compute_vertices_adjacency_matrix(connectivity)

Compute the vertices path distance matrix (adjacency matrix) from the connectivity of the mesh, where the distance between two vertices is defined as the minimum number of elements that must be traversed to go from one vertex to another.

compute_elements_adjacency_matrix(connectivity)

Compute the elements path distance matrix (adjacency matrix) from the connectivity of the mesh, where the distance between two elements is defined as the minimum number of elements that must be traversed to go from one element to another.

compute_vertices_neighborhood(connectivity)

Compute the neighborhood of each vertex in the mesh, where the neighborhood of a vertex is defined as the set of vertices that are within a specified distance from the vertex in the connectivity of the mesh.

compute_elements_neighborhood(connectivity)

Compute the neighborhood of each element in the mesh, where the neighborhood of an element is defined as the set of elements that are within a specified distance from the element in the connectivity of the mesh.

Compute the statistics of a property according to the adjacency (mean, median, std, …)#

The property can be defined :

  • at the vertices/elements of the mesh (ie the graph) and the statistics are computed according to the neighborhood of each vertex/element in the graph.

  • at integration points inside the elements of the mesh and the statistics are computed according to the neighborhood of each element in the graph.

compute_neighborhood_statistics(...[, ...])

Compute the specified statistics for the given property array defined at the vertices of a graph (or integration points) based on the neighborhood information for each vertex.