Skip to contents

Expand Basins to Cover All Graph Vertices

Source: R/compute_gfc.R
expand.basins.to.cover.Rd

Assigns uncovered vertices to their nearest basin based on shortest path distance in the graph. This is useful after filtering spurious extrema, when some vertices may no longer belong to any retained basin.

Usage

expand.basins.to.cover(
  basins.vertices.list,
  adj.list,
  weight.list,
  n.vertices = NULL
)

Arguments

basins.vertices.list

A named list of integer vectors, where each element contains the vertex indices belonging to a basin. Names should correspond to basin labels (e.g., "M1", "M2", ... or "m1", "m2", ...).

adj.list

Adjacency list representation of the graph. Element i contains the indices of vertices adjacent to vertex i.

weight.list

List of edge weights (typically edge lengths) corresponding to the adjacency list. Element i contains the weights of edges incident to vertex i.

n.vertices

Integer specifying the total number of vertices in the graph. If NULL (default), inferred from the length of adj.list.

Value

A named list with the same structure as basins.vertices.list, where each basin has been expanded to include its nearest uncovered vertices. The union of all returned basins covers all graph vertices.

Details

After filtering spurious local extrema, the union of retained basins may not cover the entire graph. Vertices that belonged to removed basins are left unassigned. This function reassigns such vertices to the nearest retained basin based on shortest path distance in the weighted graph.

For each uncovered vertex, the function computes the shortest path distance to all covered vertices, identifies the closest covered vertex, and assigns the uncovered vertex to the basin containing that closest vertex. Ties are broken arbitrarily (by the order in which basins appear in the input list).

The function uses igraph::distances() for efficient shortest path computation, restricting the calculation to distances from uncovered vertices to covered vertices rather than computing the full distance matrix.

See also

compute.gfc for computing refined basins

Examples

if (FALSE) { # \dontrun{
# After computing refined basins
result <- compute.gfc(adj.list, edge.length.list, fitted.values,
                                 edge.length.quantile.thld = 0.9,
                                 min.basin.size = 10)

# Expand maximum basins to cover all vertices
expanded.max.basins <- expand.basins.to.cover(
    basins.vertices.list = result$max.vertices.list,
    adj.list = adj.list,
    weight.list = edge.length.list,
    n.vertices = length(adj.list)
)

# Verify full coverage
all.vertices <- unique(unlist(expanded.max.basins))
length(all.vertices) == length(adj.list)  # Should be TRUE
} # }