validate.maximal.packing: Validate a Maximal Packing

In dgraphs: Data-Derived Graph Construction Utilities

Validate a Maximal Packing

Description

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,
  weight.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.
weight.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.

Details

This function performs two key validations:

1. Packing Property: Verifies that all vertices in the packing are separated by at least max.packing.radius.

2. 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.

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

Examples

adj.list <- list(c(2), c(1, 3), c(2, 4), c(3, 5), c(4))
weight.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, weight.list, packing, radius)
result$valid
result$is.maximal

dgraphs documentation built on Aug. 21, 2026, 1:08 a.m.