Create a Maximal Packing of Vertices in a Graph

Creates a maximal packing of vertices based on a specified grid size. The algorithm places vertices in the graph using a separation distance that produces a vertex set packing of size approximately equal to the given grid size. A vertex packing is a set of vertices where each pair is separated by at least a specified distance.

Usage

create.maximal.packing(
  adj.list,
  length.list,
  grid.size,
  max.iterations = 20,
  precision = 0.1
)

Arguments

adj.list

A list where each element is a vector of adjacent vertex indices (1-based) for the corresponding vertex. Must represent an undirected graph.

length.list

A list where each element is a vector of edge weights corresponding to the adjacencies in adj.list. All weights must be positive.

grid.size

A positive integer (>= 2) specifying the approximate separation distance between vertices in the packing.

max.iterations

Maximum number of iterations for the algorithm to converge. Default is 20.

precision

Precision threshold for convergence of the algorithm. Must be between 0 and 0.5. Default is 0.1.

Value

A maximal_packing result containing its graph (a dgraph), grid_vertices (packing indices), graph_diameter, and max_packing_radius (the guaranteed separation of packing vertices).

Details

The function computes a maximal packing by iteratively selecting vertices that are approximately grid.size apart from each other. The process starts from one of the graph's diameter endpoints (determined automatically) and continues until no more vertices can be added to the packing without violating the distance constraint.

The returned \code{graph_diameter} represents the longest shortest path
in the graph, which provides insight into the graph's overall structure
and extent.

The \code{max_packing_radius} value indicates the minimum distance that
separates any two vertices in the packing. This value is determined
through binary search to achieve a packing of approximately the
requested size.

The function validates input parameters and ensures that the graph
structure is properly specified before computing the packing. The graph
must be undirected (symmetric adjacency) and connected.

See also

validate.maximal.packing, verify.maximal.packing

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))

result <- create.maximal.packing(adj.list, length.list, grid.size = 2)
result$grid_vertices
#> [1] 4 1
result$max_packing_radius
#> [1] 2