create.maximal.packing: Create a Maximal Packing of Vertices in a Graph

In dgraphs: Data-Derived Graph Construction Utilities

Create a Maximal Packing of Vertices in a Graph

Description

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

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.

Value

A list with class "maximal_packing" containing five components:

adj_list	A list of adjacency vectors for each vertex in the resulting grid graph
weight_list	A list of weight vectors corresponding to each adjacency
grid_vertices	An integer vector of vertex indices that form the maximal packing
graph_diameter	A numeric value representing the maximum shortest path distance between any two vertices in the graph
max_packing_radius	A numeric value representing the optimal radius used for the final packing, which is the minimum guaranteed distance between any two vertices in the packing

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))
weight.list <- list(c(1), c(1, 1), c(1, 1), c(1, 1), c(1))

result <- create.maximal.packing(adj.list, weight.list, grid.size = 2)
result$grid_vertices
result$max_packing_radius

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