Validate a Maximal Packing — validate.maximal.packing • dgraphs

Validates whether a given vertex packing is maximal and correctly satisfies the distance constraints. A packing is valid if all vertices are separated by at least the specified radius, and is maximal if no additional vertices can be added without violating this constraint.

Usage

validate.maximal.packing(
  adj.list,
  length.list,
  packing.vertices,
  max.packing.radius
)

Arguments

adj.list: A list where each element is a vector of adjacent vertex indices (1-based) for the corresponding vertex.
length.list: A list where each element is a vector of edge weights corresponding to the adjacencies in adj.list.
packing.vertices: An integer vector of vertex indices (1-based) that form the packing to be validated.
max.packing.radius: A numeric value representing the minimum distance that should separate any two vertices in the packing.

Value

A list with class "packing_validation" containing validation results:

valid: Logical indicating whether the packing satisfies the distance constraint
min.packing.distance: The minimum distance found between any two packing vertices
max.coverage.distance: The maximum distance from any non-packing vertex to its nearest packing vertex
violations: A data frame containing details of any violations found, or NULL if none. Contains columns: type, vertex1, vertex2, distance
is.maximal: Logical indicating whether the packing is maximal (no vertices can be added)
potential.additions: Integer vector of vertex indices that could potentially be added to the packing if it's not maximal, or NULL if maximal

Details

This function performs two key validations:

Packing Property: Verifies that all vertices in the packing are separated by at least max.packing.radius.
Maximality: Verifies that no additional vertex can be added to the packing without violating the packing property.

The function uses the igraph package to compute shortest path distances between vertices using Dijkstra's algorithm.

Examples

adj.list <- list(c(2), c(1, 3), c(2, 4), c(3, 5), c(4))
length.list <- list(c(1), c(1, 1), c(1, 1), c(1, 1), c(1))
packing <- c(1, 3, 5)
radius <- 2

result <- validate.maximal.packing(adj.list, length.list, packing, radius)
result$valid
#> [1] TRUE
result$is.maximal
#> [1] TRUE