Package {dgraphs}

dgraphs: Data-Derived Graph Construction Utilities

Description

Construct and analyze graphs derived from numerical observations.

Author(s)

Maintainer: Peter Gajer pgajer@gmail.com

Authors:

• Peter Gajer pgajer@gmail.com

Other contributors:

• Sunil Arya (ANN library) [contributor]

• David M. Mount (ANN library) [contributor]

• University of Maryland (ANN library) [copyright holder]

• Yixuan Qiu (Spectra library) [contributor, copyright holder]

• Anna Araslanova (Spectra LOBPCG solver) [contributor, copyright holder]

• Gael Guennebaud (Spectra linear algebra routines) [contributor, copyright holder]

• Jitse Niesen (Spectra linear algebra routines) [contributor, copyright holder]

• Netherlands eScience Center (Spectra eigensolver routines) [contributor, copyright holder]

See Also

Useful links:

• https://github.com/pgajer/dgraphs

• Report bugs at https://github.com/pgajer/dgraphs/issues

Validate an adjacency list

Description

Validate an adjacency list

Usage

.dgraphs.validate.adj.list(adj.list, allow.empty = FALSE)

Arguments

Value

The normalized adjacency list with integer neighbor vectors.

Convert an Adjacency List to igraph

Description

Convert an Adjacency List to igraph

Usage

adjlist.to.igraph(adj.list)

Arguments

Value

An undirected igraph graph.

Convert a Basin Graph to igraph

Description

Convert a Basin Graph to igraph

Usage

as_igraph(gflow.graph, include.vertex.attrs = TRUE, include.edge.attrs = TRUE)

Arguments

Value

An igraph object.

Build iKNN Graphs and Select a Neighborhood Size

Description

Builds an iKNN graph sequence and selects k from structural edit-distance stability, label-mixing stability, or both.

Usage

build.iknn.graphs.and.selectk(
  X,
  kmin,
  kmax,
  method = c("both", "edit", "mixing", "none"),
  pca.dim = 100,
  variance.explained = 0.99,
  trim.disconnected = TRUE,
  edit.min.lcc.frac = 1,
  edit.eps = 0.05,
  labels = NULL,
  perm.blocks = NULL,
  mixing.metric = c("homophily.effect", "homophily.z", "homophily.adjusted",
    "assortativity.effect", "assortativity.z", "homophily", "assortativity",
    "conductance.median", "conductance.wmean"),
  mixing.min.lcc.frac = 0.98,
  mixing.eps = 0.05,
  mixing.require.local.extremum = TRUE,
  mixing.window = 1L,
  n.perm = 200L,
  use.edge.weights = TRUE,
  weights.are.edge.lengths = FALSE,
  affinity.method = c("exp", "inv"),
  affinity.sigma = NULL,
  affinity.sigma.from = c("k.cc.mixing", "k.max.lcc", "k.trim"),
  affinity.eps = 1e-08,
  simplify.multiple = TRUE,
  seed = 1L,
  n.cores = 1L,
  verbose = TRUE,
  ...
)

Arguments

Value

An object of class "build_iknn_graphs_and_selectk" containing the graph sequence, connectivity diagnostics, selection curves, selected neighborhood sizes, trimming metadata, and call parameters.

Calculate Edit Distances Between Sequential Graphs

Description

Calculates edit distances between pairs of graphs separated by a specified offset in the sequence of k values.

Usage

calculate.edit.distances(
  k.values,
  graph.data,
  offset = 1,
  edge.cost = 1,
  weight.cost.factor = 0.1,
  verbose = FALSE
)

Arguments

Details

For a sequence of k values and an offset of 1, this function compares:

• Graph at k[1] with graph at k[2]

• Graph at k[2] with graph at k[3]

• And so on...

Value

A list containing:

Examples

graph.data <- list(
  adj.list = list(
    `5` = list(c(2), c(1, 3), c(2)),
    `10` = list(c(2, 3), c(1, 3), c(1, 2)),
    `15` = list(c(2, 3), c(1), c(1))
  ),
  dist.list = list(
    `5` = list(1, c(1, 2), 2),
    `10` = list(c(1, 2), c(1, 3), c(2, 3)),
    `15` = list(c(1, 1.5), 1, 1.5)
  )
)
k.vals <- c(5, 10, 15)
distances <- calculate.edit.distances(k.vals, graph.data, offset = 1)
distances$distances

Compare Two Adjacency Lists

Description

Compare Two Adjacency Lists

Usage

compare.adj.lists(adj.list1, adj.list2)

Arguments

Value

TRUE when each vertex has the same neighbor set in both lists, ignoring order; otherwise FALSE.

Compare Paths Across Hop Limits

Description

Compare Paths Across Hop Limits

Usage

compare.paths(x, from, to)

Arguments

Value

Data frame describing path availability and length by hop limit.

Compute Geodesic Statistics for Grid Vertices

Description

Analyzes how the number of geodesics scales with radius for each grid vertex. This function helps determine if collapsing/clustering geodesics is necessary and provides insights into the graph structure around grid vertices.

Usage

compute.geodesic.stats(
  adj.list,
  weight.list,
  min.radius = 0.2,
  max.radius = 0.5,
  n.steps = 5,
  n.packing.vertices = length(adj.list),
  max.packing.iterations = 20,
  packing.precision = 1e-04,
  verbose = FALSE
)

Arguments

Value

A list of class "geodesic_stats" containing:

radii

Numeric vector. Actual radii used in the analysis.

geodesic_rays

Matrix. Number of geodesic rays for each vertex at each radius.

composite_geodesics

Matrix. Number of composite geodesics for each vertex at each radius.

path_overlap

List of matrices. Overlap statistics for each vertex at each radius.

grid_vertices

Integer vector. The vertices selected as grid vertices.

summary

Data frame. Summary statistics for each radius.

Compute a Weighted Graph Diameter

Description

Compute a Weighted Graph Diameter

Usage

compute.graph.diameter(adj.list, weight.list)

Arguments

Value

A list containing the diameter and the farthest path details.

Compute a Weighted Shortest-Path Distance

Description

Compute a Weighted Shortest-Path Distance

Usage

compute.graph.distance(
  star.obj = NULL,
  i,
  j,
  adj.list = NULL,
  edge.lengths = NULL
)

Arguments

Value

Numeric shortest-path distance.

Compute Graph Endpoint Scores from a 3D Embedding

Description

Computes endpointness diagnostics for graph vertices by selecting graph-geodesic neighborhoods and evaluating how concentrated the corresponding 3D embedding directions are. This targets terminal arm tips in an embedding rather than graph-theoretic degree-1 vertices.

For each vertex x, let u_1, \dots, u_m be unit vectors in the embedding from x to graph-geodesic neighbors of x. The function computes:

s_{\min}(x) = \min_{i < j} u_i^\top u_j

s_q(x) = \mathrm{quantile}\{u_i^\top u_j : i < j\}

m(x) = \left\| \frac{1}{\sum_i w_i} \sum_i w_i u_i \right\|

\mathrm{score}(x) = m(x)\, \frac{1 + s_q(x)}{2}

Neighborhoods are selected in graph-geodesic space while directions are taken from the supplied 3D embedding.

Usage

compute.graph.endpoint.scores(
  adj.list,
  weight.list,
  layout.3d,
  neighborhood = c("geodesic_k", "geodesic_radius"),
  k = c(10L, 20L, 30L),
  radius = NULL,
  q = 0.1,
  neighbor.weighting = c("uniform", "inverse_distance", "gaussian"),
  gaussian.sigma = NULL,
  min.neighborhood.size = 3L,
  scale.aggregate = c("mean", "median", "min", "max"),
  verbose = FALSE
)

Arguments

Value

A list with aggregated per-vertex scores, per-scale score matrices, and neighborhood diagnostics.

Compute a graph summary as a probability mass function

Description

Converts a graph-like object into a named probability mass function (PMF) describing one selected graph summary. This provides a standardized bridge between graph objects and divergence functions such as jensen.shannon.divergence().

Supported v1 summaries are:

• "degree_distribution"

• "edge_weight_distribution"

• "component_size_distribution"

• "neighborhood_label_distribution"

"component_size_distribution" is included primarily as a diagnostic for disconnectedness / fragmentation, not as a general-purpose default stability summary.

Usage

compute.graph.summary.pmf(
  graph,
  summary = c("degree_distribution", "edge_weight_distribution",
    "component_size_distribution", "neighborhood_label_distribution"),
  labels = NULL,
  weight.list = NULL,
  bins = NULL,
  n.bins = 20L,
  bin.method = c("auto", "fixed_width", "fixed_quantile", "explicit"),
  normalize = TRUE,
  support = NULL,
  zero.pad = TRUE,
  simplify.multiple = TRUE,
  directed = FALSE,
  return.details = TRUE
)

Arguments

Value

If return.details = TRUE, a list with fields:

• summary: summary type used.

• pmf: named probability mass function.

• support: support of the PMF.

• counts: named raw-count vector before normalization.

• metadata: list of summary-specific metadata.

Otherwise, returns the named PMF vector.

Compute graph-summary stability across a graph sequence

Description

Computes a divergence-based stability curve across consecutive graphs in a sequence. This function provides a generalized sequence-level analogue of the degree-profile Jensen-Shannon calculation currently used in compute.stability.metrics().

Usage

compute.graph.summary.stability(
  graphs,
  summary = c("degree_distribution", "edge_weight_distribution",
    "component_size_distribution", "neighborhood_label_distribution"),
  divergence = c("js"),
  labels = NULL,
  summary.args = list(),
  k.values = NULL,
  graph.type = c("geom", "isize"),
  return.details = TRUE
)

Arguments

Value

If return.details = TRUE, a list with fields:

• summary: summary type used.

• divergence: divergence type used.

• k.values: full k sequence.

• k.transition.values: k values corresponding to consecutive-graph transitions.

• values: vector of divergence values of length length(k.values) - 1.

• details: optional pairwise details for each transition.

Otherwise, returns only the divergence vector.

Compute Stability Metrics Across a Sequence of IkNN Graphs

Description

Computes stability diagnostics across the pruned IkNN graphs produced by create.iknn.graphs(). Metrics include edit distances between consecutive graphs, graph-summary Jensen-Shannon divergence, edge-count diagnostics, local minima, and smoothed trend fits for plotting.

Usage

compute.stability.metrics(
  graphs,
  graph.type = c("geom", "isize"),
  summary = c("degree_distribution", "edge_weight_distribution",
    "component_size_distribution", "neighborhood_label_distribution"),
  divergence = c("js"),
  labels = NULL,
  summary.args = list()
)

Arguments

Value

An object of class "iknn_stability_metrics".

Compute Geodesic Statistics for a Single Grid Vertex

Description

Analyzes how the number of geodesics scales with radius for a specific grid vertex.

Usage

compute.vertex.geodesic.stats(
  adj.list,
  weight.list,
  grid.vertex,
  min.radius = 0.2,
  max.radius = 0.5,
  n.steps = 5,
  n.packing.vertices = length(adj.list),
  packing.precision = 1e-04
)

Arguments

Value

A data frame of class "vertex_geodesic_stats" with columns:

radius

Actual radius used.

rays

Number of geodesic rays within radius.

composite_geodesics

Number of composite geodesics.

overlap_min

Minimum overlap ratio.

overlap_p05

5th percentile overlap ratio.

overlap_p25

25th percentile overlap ratio.

overlap_median

Median overlap ratio.

overlap_p75

75th percentile overlap ratio.

overlap_p95

95th percentile overlap ratio.

overlap_max

Maximum overlap ratio.

Convert an Adjacency List to an Adjacency Matrix

Description

Convert an Adjacency List to an Adjacency Matrix

Usage

convert.adjacency.list.to.adjacency.matrix(
  adj.list,
  weight.list = NULL,
  mode = "undirected",
  remove.self.loops = TRUE
)

Arguments

Value

Numeric adjacency matrix.

Convert an Adjacency List to an Edge Matrix

Description

Convert an Adjacency List to an Edge Matrix

Usage

convert.adjacency.to.edge.matrix(adj.list, weights.list = NULL)

Arguments

Value

A list with edge.matrix and weights.

Convert a Directed Adjacency List to an Undirected Adjacency List

Description

Convert a Directed Adjacency List to an Undirected Adjacency List

Usage

convert.to.undirected(adj.list)

Arguments

Value

An adjacency list with reciprocal edges added and duplicate neighbors removed.

Convert a Weighted Adjacency Matrix to Lists

Description

Convert a Weighted Adjacency Matrix to Lists

Usage

convert.weighted.adjacency.matrix.to.adjacency.list(A)

Arguments

Value

A list with adjacency.list and weights.list.

Count Edges in an Undirected Adjacency List

Description

Count Edges in an Undirected Adjacency List

Usage

count.edges(adj.list)

Arguments

Value

Number of undirected edges.

Compute Adaptive Radius-kNN Graphs With Batched ANN Search

Description

Tentative C++-backed counterpart to create.rknn.graphs(). It builds one ANN kd-tree, computes nearest-neighbor distances through the maximal requested k value once, derives each requested k.scale from that shared result, and materializes adaptive-radius edge tables for all k values in C++. The existing R finalization path is then used for pruning, lifecycle branches, and optional component repair.

This function is exported as a diagnostic helper while the native backend is being benchmarked and validated. Ordinary callers should use create.rknn.graphs() with the default backend = "auto" or with backend = "cpp" to request this native backend explicitly.

Usage

cpp.create.rknn.graphs(X, kmin = NULL, kmax = NULL, ..., k.values = NULL)

Arguments

Value

A "rknn_graphs" object with the same default structure as create.rknn.graphs(). When return.timing = TRUE, timing is attached at the graph-sequence level because the ANN setup and max-k scale search are shared across k values.

See Also

create.rknn.graphs()

Examples

X <- matrix(c(0, 1, 3, 4), ncol = 1)
result <- cpp.create.rknn.graphs(
  X,
  k.values = c(1, 2),
  graph.detail = "minimal",
  prune.method = "none"
)
names(result$graphs)

Create a Bi-kNN Chain Graph

Description

Create a Bi-kNN Chain Graph

Usage

create.bi.kNN.chain.graph(n.vertices = 5, k = 1, x = NULL, y = NULL)

Arguments

Value

A list with adj.list, edge.lengths, x.sorted, and y.sorted.

Create a Bipartite Graph

Description

Create a Bipartite Graph

Usage

create.bipartite.graph(n1, n2)

Arguments

Value

An adjacency list for the complete bipartite graph.

Create a Chain Graph

Description

Create a Chain Graph

Usage

create.chain.graph(n.vertices = NULL, x = NULL, y = NULL)

Arguments

Value

A list with adj.list, edge.lengths, x.sorted, and y.sorted.

Create a Chain Graph with Offset Vertex Labels

Description

Create a Chain Graph with Offset Vertex Labels

Usage

create.chain.graph.with.offset(n, offset = 0)

Arguments

Value

A chain graph adjacency list.

Create a Circular Graph

Description

Create a Circular Graph

Usage

create.circular.graph(n)

Arguments

Value

An undirected cycle graph adjacency list.

Compute a Continuous-kNN Graph

Description

Creates an undirected continuous-kNN graph using local scale distances. Let \sigma_i be the distance from observation i to its k.scale-th non-self nearest neighbor. Vertices are adjacent when

\|x_i - x_j\|_2 \le \delta \sqrt{\sigma_i\sigma_j}.

This is a convenience wrapper around create.rknn.graph() with type = "adaptive.radius" and radius.rule = "geomean". It is useful as a named data-derived graph construction in geodesic reconstruction benchmarks.

Usage

create.cknn.graph(
  X,
  k.scale,
  delta = 1,
  radius.search = c("ann", "all.pairs"),
  return.timing = FALSE,
  graph.detail = c("full", "minimal"),
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

Value

A list inheriting from "cknn_graph" and "adaptive_radius_graph". It contains the same lifecycle fields as create.rknn.graph() with type = "adaptive.radius", radius_rule = "geomean", radius_factor = delta, and graph_rule = "continuous.knn".

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
create.cknn.graph(X, k.scale = 1, delta = 1)$edge_matrix

Construct a Minimal Spanning Tree (MST) Completion Graph

Description

Constructs a completion of the Minimal Spanning Tree (MST) graph from a numeric data matrix. The graph is constructed in two steps: first, a MST is built connecting all data points using minimal total edge length; then, additional edges are added between any pair of points whose Euclidean distance is less than or equal to a quantile threshold based on the MST edge length distribution.

Usage

create.cmst.graph(
  X,
  q.thld = 0.9,
  pca.dim = 100,
  variance.explained = 0.99,
  verbose = TRUE
)

Arguments

Details

The MST completion process enhances connectivity in the original MST by adding edges between vertices that are "close" according to the distance distribution in the MST. This can be useful for creating more robust graph representations of data that maintain local structure while avoiding long-range connections.

When PCA is applied (either through pca.dim or variance.explained), the data is first centered and projected onto the leading principal components before graph construction. This can significantly reduce computation time for high-dimensional data while preserving the most important variation.

Value

An object of class mst_completion_graph, which is a list containing:

mst_adj_list

A list of length n, where element i contains the indices of vertices adjacent to vertex i in the MST.

mst_weight_list

A list of length n, where element i contains the edge weights corresponding to the adjacent vertices in mst_adj_list[[i]].

cmst_adj_list

A list of length n containing adjacency information for the completed MST graph.

cmst_weight_list

A list of length n containing edge weights for the completed MST graph.

mst_edge_weights

Numeric vector containing all unique MST edge weights.

cmst_distance_threshold

Numeric scalar containing the actual Euclidean distance threshold used for completion.

The returned object also has the following attributes:

q_thld

The quantile threshold used for MST completion.

pca

If PCA was applied, a list containing:

• original_dim: The original number of dimensions

• n_components: The number of PCA components used

• variance_explained: The proportion of variance explained

• cumulative_variance: Cumulative variance by component (if applicable)

call

The matched function call.

References

Gower, J. C., & Ross, G. J. S. (1969). Minimum spanning trees and single linkage cluster analysis. Applied Statistics, 18(1), 54-64.

See Also

stats::prcomp() for principal component analysis.

Examples

set.seed(123)
X <- matrix(rnorm(60), nrow = 20, ncol = 3)
graph <- create.cmst.graph(X, verbose = FALSE)
graph$n_vertices
graph$n_edges

Create a Complete Graph

Description

Create a Complete Graph

Usage

create.complete.graph(n)

Arguments

Value

An adjacency list for the complete graph on n vertices.

Create Distance Plot

Description

Creates a plot of edit distances with optional smoothing or regression results.

Usage

create.distance.plot(
  x,
  y,
  smooth = TRUE,
  smooth.method = "loess",
  mark.x = NULL,
  xlab = "Number of Nearest Neighbors (k)",
  ylab = "Edit Distance",
  main = NULL,
  width = 6,
  height = 6,
  ...
)

Arguments

Details

The function creates a scatter plot with optional smoothing line. If mark.x is provided, vertical dashed lines are added at those x-values.

Value

Returns NULL invisibly after drawing the plot.

Examples

k.vals <- c(5, 10, 15, 20)
distances <- c(2.2, 1.4, 1.1, 1.3)
create.distance.plot(k.vals, distances, smooth = FALSE)

min.k <- k.vals[which.min(distances)]
create.distance.plot(k.vals, distances, mark.x = min.k,
                     smooth = FALSE,
                     main = "Edit Distance vs k")

Create an Empty Graph

Description

Create an Empty Graph

Usage

create.empty.graph(n)

Arguments

Value

An adjacency list for the empty graph on n vertices.

Create a graph-geodesic iKNN graph

Description

Rebuilds an iKNN graph from an existing weighted graph by using graph geodesic distances in place of Euclidean distances. For every vertex i, the graph-metric neighbor set contains the first k finite graph-geodesic nearest vertices under the same convention used by create.iknn.graphs(). Because self-distance is zero, this includes i whenever i is finite from itself. Vertices i and j are connected in the returned graph when those two neighbor sets intersect.

Usage

create.geodesic.iknn.graph(graph, k)

Arguments

Value

A list with entries:

adj_list

1-based adjacency list for the final graph.

weight_list

Final graph-geodesic edge lengths from the input graph.

raw_adj_list, raw_weight_list

The native geodesic iKNN graph.

pruned_adj_list, pruned_weight_list

Identical to raw_* because geodesic iKNN graphs do not currently have a pruning stage.

raw_repaired_adj_list, raw_repaired_weight_list, pruned_repaired_adj_list, pruned_repaired_weight_list, repaired_pruned_adj_list, repaired_pruned_weight_list

Lifecycle aliases identical to the final graph because this constructor has no MST repair or pruning stage.

isize_list

Intersection sizes for each edge.

n_edges

Number of undirected edges.

Examples

graph <- list(
  adj_list = list(2L, c(1L, 3L), 2L),
  weight_list = list(1, c(1, 1), 1)
)
create.geodesic.iknn.graph(graph, k = 1)

Create a Refined Graph with Approximately Uniform Edge Spacing

Description

Create a Refined Graph with Approximately Uniform Edge Spacing

Usage

create.grid.graph(
  adj.list,
  weight.list,
  grid.size,
  start.vertex = 1L,
  snap.tolerance = 0.1
)

Arguments

Value

A list with adj_list, weight_list, and grid_vertices.

Create intersection k-nearest neighbor graphs with dual pruning

Description

For each k \in [k_{\mathrm{min}},\,k_{\mathrm{max}}], builds an intersection-weighted k-NN graph and applies two pruning schemes: (1) geometric (path-to-edge ratio) and (2) intersection-size. Optionally performs PCA before graph construction.

Usage

create.iknn.graphs(
  X,
  kmin,
  kmax,
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  compute.full = TRUE,
  with.isize.pruning = FALSE,
  with.edge.pruning.stats = FALSE,
  pca.dim = 100,
  variance.explained = 0.99,
  knn.metric = c("euclidean", "linf.simplex"),
  linf.tol = sqrt(.Machine$double.eps),
  n.cores = 1L,
  parallel.mode = c("auto", "k", "bucket", "hybrid", "bucket.prune"),
  hybrid.batch.size = 2L,
  verbose = TRUE,
  knn.cache.path = NULL,
  knn.cache.mode = c("none", "read", "write", "readwrite")
)

Arguments

Details

Geometric pruning uses the deviation threshold max.path.edge.ratio.deviation.thld and the filtering percentile path.edge.ratio.percentile. Intersection-size pruning currently uses a maximum alternative path length of 2.

Output behavior by flags:

• compute.full = FALSE: both geom_pruned_graphs and isize_pruned_graphs are NULL.

• compute.full = TRUE and with.isize.pruning = FALSE: geom_pruned_graphs is returned and isize_pruned_graphs is NULL.

Value

A list of class "iknn_graphs" with entries:

k_statistics

Matrix of per-k edge counts and reductions. (If the C++ side supplies column names, they’re preserved. Otherwise we add names consistent with what the C++ returns.)

geom_pruned_graphs

If compute.full=TRUE, list of geometrically pruned graphs (adjacency + weights); otherwise NULL.

isize_pruned_graphs

If compute.full=TRUE and with.isize.pruning=TRUE, list of intersection-size pruned graphs; otherwise NULL.

edge_pruning_stats

If with.edge.pruning.stats=TRUE, list (per k) of edge-level statistics; otherwise NULL.

Examples

# Generate sample data
X <- matrix(rnorm(100 * 5), 100, 5)

# Basic usage
res1 <- create.iknn.graphs(
  X, kmin = 3, kmax = 10, n.cores = 1,
  compute.full = FALSE
)

# With custom pruning parameters
res2 <- create.iknn.graphs(
  X, kmin = 3, kmax = 10,
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  compute.full = TRUE,
  n.cores = 1,
  verbose = TRUE
)

# View statistics for each k
print(res2$k_statistics)

Create iterated graph-geodesic iKNN graphs

Description

Constructs G0 with create.iknn.graphs(), then constructs G1, G2, ..., Gm by repeatedly applying create.geodesic.iknn.graph() to each graph in the kmin:kmax sequence. This implements the iterated nerve rule

\{i,j\} \in E(G_{t+1}) \iff kNN_{G_t}(i) \cap kNN_{G_t}(j) \ne \emptyset,

with edge length

\ell_{t+1}(i,j) = d_{G_t}(i,j).

Usage

create.iterated.iknn.graphs(
  X,
  kmin,
  kmax,
  n.iterations = 3L,
  max.path.edge.ratio.deviation.thld = 0,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  pca.dim = 100,
  variance.explained = 0.99,
  n.cores = 1L,
  parallel.mode = c("auto", "k", "bucket", "hybrid", "bucket.prune"),
  hybrid.batch.size = 2L,
  verbose = TRUE,
  knn.cache.path = NULL,
  knn.cache.mode = c("none", "read", "write", "readwrite")
)

Arguments

Value

A list of class "iterated_iknn_graphs" with entries:

k_values

Integer vector of requested k values.

n_iterations

Number of geodesic rebuilds after G0.

initial_graphs

The "iknn_graphs" object returned by create.iknn.graphs() for G0.

graphs

Nested list named G0, G1, ...; each entry is a named list of graph objects for kmin:kmax.

summary

Data frame with one row per iteration and k.

Examples

set.seed(1)
X <- matrix(rnorm(30), ncol = 2)
out <- create.iterated.iknn.graphs(X, kmin = 2, kmax = 3, n.iterations = 1,
                                   verbose = FALSE)
out$summary

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

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:

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

Compute a Mutual k-Nearest Neighbor Graph with Weights

Description

Creates an undirected graph where two points are connected by an edge if and only if they are present in each other's k-nearest neighbor (kNN) lists. The weight of each edge represents the distance between the connected vertices.

Usage

create.mknn.graph(
  X,
  k,
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

Details

The mutual k-nearest neighbor graph is a symmetric graph where an edge between vertices i and j exists if and only if:

• j is among the k nearest neighbors of i, AND

• i is among the k nearest neighbors of j

This mutual relationship ensures that the resulting graph is undirected and typically sparser than a standard k-nearest neighbor graph.

The final graph is always stored in adj_list/weight_list. Lifecycle diagnostic fields follow the same convention as the other graph constructors: raw_* is before pruning and MST repair, and pruned_* is after pruning but before MST repair. The raw_repaired_*, pruned_repaired_*, and repaired_pruned_* branches allow one constructor call to compare native, prune-first, and repair-first graph geodesic geometries.

Value

A list with class "mknn_graph" containing:

adj_list

A list where element i contains the indices of vertices connected to vertex i by an edge in the final graph after optional MST component repair.

weight_list

A list where element i contains the distances between vertex i and its connected neighbors in the final graph (in the same order as adj_list[[i]]).

raw_adj_list, raw_weight_list

The native mutual-kNN graph before pruning and before optional MST component repair.

pruned_adj_list, pruned_weight_list

The graph after optional local geometric pruning and before optional MST component repair. If pruning is disabled, these fields are identical to the raw graph.

raw_repaired_adj_list, raw_repaired_weight_list

The native mutual kNN graph after MST component repair.

pruned_repaired_adj_list, pruned_repaired_weight_list

The prune-first branch after MST component repair.

repaired_pruned_adj_list, repaired_pruned_weight_list

The repair-first branch after applying local geometric pruning to the repaired raw graph.

n_vertices

The number of vertices in the graph.

n_edges

The total number of edges in the graph.

k

The k value used to construct the graph.

See Also

create.mknn.graphs for creating multiple graphs with different k values, summary.mknn_graphs for summarizing graph properties

Examples

set.seed(123)
X <- matrix(rnorm(60), ncol = 2)
graph <- create.mknn.graph(X, k = 4)
graph$n_vertices
graph$n_edges
graph$adj_list[[1]]

Create Multiple Mutual kNN Graphs with Geometric Pruning

Description

Constructs a series of mutual k-nearest neighbor (MkNN) graphs across a range of k values, with optional geometric pruning to remove redundant edges based on alternative path analysis.

Usage

create.mknn.graphs(
  X,
  kmin,
  kmax,
  max.path.edge.ratio.thld = 1.2,
  path.edge.ratio.percentile = 0.5,
  compute.full = FALSE,
  pca.dim = 100,
  variance.explained = 0.99,
  verbose = FALSE
)

Arguments

Details

This function performs the following steps for each k value:

1. Mutual kNN Graph Construction: Creates a graph where edges exist only between mutually nearest neighbors.

2. Geometric Pruning (optional): Removes edges where alternative paths exist with acceptable length ratios. An edge (i,j) is pruned if there exists a path i->k->j such that (d(i,k) + d(k,j)) / d(i,j) <= threshold.

3. Dimensionality Reduction (optional): If the data has more than pca.dim dimensions, PCA is applied before graph construction to improve computational efficiency and reduce noise.

The geometric pruning step helps create sparser graphs by removing edges that can be well-approximated by two-hop paths, which can improve graph quality for clustering and visualization tasks.

Value

An object of class "mknn_graphs" containing:

k_statistics

A data frame with columns: k (k value), n_edges (edges before pruning), n_edges_pruned (edges after pruning), n_removed (number of removed edges), reduction_ratio (proportion of edges removed).

pruned_graphs

If compute.full=TRUE, a named list of pruned graphs for each k value. NULL otherwise.

edge_pruning_stats

A list of pruning statistics for each k value, containing edge lengths and path ratios.

The returned object also has the following attributes:

• kmin, kmax: The k range used

• max.path.edge.ratio.thld: The pruning threshold used

• path.edge.ratio.percentile: The percentile threshold used

• pca: If PCA was performed, contains dimensionality reduction details

See Also

create.mknn.graph for creating a single MkNN graph, summary.mknn_graphs for summarizing the results

Examples

set.seed(123)
X <- matrix(rnorm(80), ncol = 2)
result <- create.mknn.graphs(
  X, kmin = 3, kmax = 4, compute.full = TRUE, verbose = FALSE
)
result$k_statistics

X.high <- matrix(rnorm(120), nrow = 20, ncol = 6)
result.pca <- create.mknn.graphs(
  X.high, kmin = 2, kmax = 3, pca.dim = 3, verbose = FALSE
)
attr(result.pca, "pca")$n_components

Create a Path Graph with Limited Hop Distance

Description

Create a Path Graph with Limited Hop Distance

Usage

create.path.graph(graph, edge.lengths, h)

Arguments

Value

An object of class "path.graph".

Create a Series of Path Graphs

Description

Create a Series of Path Graphs

Usage

create.path.graph.series(graph, edge.lengths, h.values)

Arguments

Value

A list of "path.graph" objects.

Create a Path Length Matrix Graph Structure

Description

Create a Path Length Matrix Graph Structure

Usage

create.plm.graph(graph, edge.lengths, h)

Arguments

Value

An object of class path.graph.plm.

Create a Random Undirected Graph

Description

Create a Random Undirected Graph

Usage

create.random.graph(n_vertices, avg_degree, connected = TRUE)

Arguments

Value

A list with adj.list and weight.list.

Compute a Radius-kNN Graph

Description

Creates an undirected Euclidean radius graph from a numeric data matrix. Use type = "fixed" for a fixed-radius graph, where vertices i and j are adjacent exactly when their Euclidean distance is at most radius. Use type = "adaptive.radius" for an adaptive-radius graph based on observation-specific local scale distances.

Usage

create.rknn.graph(
  X,
  type = c("fixed", "adaptive.radius"),
  radius = NULL,
  k.scale = NULL,
  radius.factor = 1,
  radius.rule = c("max", "min", "geomean"),
  radius.search = c("ann", "all.pairs"),
  return.timing = FALSE,
  graph.detail = c("full", "minimal"),
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

Value

For type = "fixed", a list of class "radius_graph". For type = "adaptive.radius", a list of class "adaptive_radius_graph". Both contain adjacency lists, edge weights, edge matrix, and component diagnostics. The final graph is stored in adj_list/weight_list; raw and pruned lifecycle graph stages are stored in corresponding ⁠raw_*⁠/⁠pruned_*⁠ fields when graph.detail = "full".

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
create.rknn.graph(X, type = "fixed", radius = 1.1)$edge_matrix
create.rknn.graph(X, type = "adaptive.radius", k.scale = 1)$edge_matrix

Compute Adaptive Radius-kNN Graphs Across k Values

Description

Creates a sequence of adaptive-radius graphs by varying the k.scale parameter passed to create.rknn.graph(type = "adaptive.radius"). By default, ANN-backed construction uses the batched C++ backend while the direct all-pairs reference path uses the scalar R loop. Set backend = "r" to force the scalar loop for ANN parity checks.

Usage

create.rknn.graphs(
  X,
  kmin = NULL,
  kmax = NULL,
  ...,
  k.values = NULL,
  backend = c("auto", "cpp", "r")
)

Arguments

Value

A list of class "rknn_graphs" with components:

graphs

A named list of adaptive-radius graph objects, one per k.

k_statistics

A data frame with one row per k containing edge, component, and MST-repair counts.

timing

Present only when forwarded options request graph timing; contains backend-specific construction timing rows.

Attributes include kmin, kmax, k.values, and n_vertices.

See Also

create.rknn.graph()

Examples

X <- matrix(c(0, 1, 3, 4), ncol = 1)
result <- create.rknn.graphs(
  X,
  kmin = 1,
  kmax = 2,
  radius.search = "all.pairs",
  graph.detail = "minimal",
  prune.method = "none"
)
names(result$graphs)
result$k_statistics

Create a Single Intersection-weighted k-Nearest Neighbors Graph

Description

Creates and prunes an intersection-weighted k-nearest neighbors (IWD-kNN) graph from input data. The graph is constructed based on feature space distances and intersection sizes between neighbor sets.

Usage

create.single.iknn.graph(
  X,
  k,
  max.path.edge.ratio.deviation.thld = 0.1,
  prune.method = c("global.geodesic", "none", "local.geodesic", "global.geodesic.ratio"),
  prune.tau = NULL,
  prune.local.k = NULL,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  compute.full = FALSE,
  with.isize.pruning = FALSE,
  with.edge.pruning.stats = FALSE,
  pca.dim = 100,
  variance.explained = 0.99,
  knn.metric = c("euclidean", "linf.simplex"),
  linf.tol = sqrt(.Machine$double.eps),
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2,
  with.lifecycle.branches = FALSE,
  verbose = TRUE,
  knn.cache.path = NULL,
  knn.cache.mode = c("none", "read", "write", "readwrite")
)

Arguments

Details

adj_list and weight_list always contain the final graph used by downstream algorithms. ⁠raw_*⁠ fields contain the native graph before pruning, and ⁠pruned_*⁠ fields contain the graph after pruning but before optional MST component repair. If pruning is disabled, ⁠pruned_*⁠ is identical to ⁠raw_*⁠. The repaired lifecycle branches allow direct comparison of raw, prune-first, and repair-first graph geodesic distances from a single constructor call.

Value

An object of class "IkNN" (inheriting from "list") containing:

adj_list

Adjacency lists for the final graph after optional MST repair

weight_list

Edge weights for the final graph

raw_adj_list

Adjacency lists for the native graph before pruning

raw_weight_list

Edge weights for the native graph before pruning

pruned_adj_list

Adjacency lists after pruning and before MST repair

pruned_weight_list

Edge weights after pruning and before MST repair

raw_repaired_adj_list, raw_repaired_weight_list

The native graph after MST component repair.

pruned_repaired_adj_list, pruned_repaired_weight_list

The prune-first branch after MST component repair.

repaired_pruned_adj_list, repaired_pruned_weight_list

The repair-first branch after applying the selected pruning method to the repaired raw graph.

n_edges

Total number of edges in original graph

n_edges_in_pruned_graph

Number of edges after pruning

n_removed_edges

Number of edges removed by pruning

edge_reduction_ratio

Proportion of edges removed

call

The matched function call

k

Number of nearest neighbors used

n

Number of data points

d

Number of features

If compute.full = TRUE, additional components include:

isize_list

Intersection sizes for original edges

conn_comps

Connected components identification

connected_components

Alternative format of connected components

Examples

# Create sample data
set.seed(123)
X <- matrix(rnorm(100), ncol = 2)
result <- create.single.iknn.graph(X, k = 3)
summary(result)

Compute a Symmetric k-Nearest Neighbor Graph

Description

Creates an undirected symmetric k-nearest neighbor (sKNN) graph from a numeric data matrix. An edge between vertices i and j is present when either j is among the k nearest neighbors of i, or i is among the k nearest neighbors of j.

Usage

create.sknn.graph(
  X,
  k,
  prune.edges = FALSE,
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  edge.weight = c("distance"),
  neighbor.method = c("exact", "ann"),
  ann.eps = 0,
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

Details

With no nearest-neighbor ties, the sKNN edge rule is equivalent to

d_{ij} \le \max(\sigma_i, \sigma_j),

where \sigma_i is the distance from point i to its k-th non-self nearest neighbor.

If connect.components = TRUE, the graph is augmented with MST edges. The default connect.method = "component.mst" first collapses each connected component of the sKNN graph to one component vertex, weights each component pair by the shortest data-space edge between them, and adds the minimum spanning tree of this component graph. This adds exactly m - 1 bridge edges when the original sKNN graph has m connected components. connect.method = "component.mst.ann" uses ANN nearest-neighbor bridge candidates first and automatically falls back to exact component MST when the sparse candidate graph does not connect all components. The alternative connect.method = "global.mst" unions the sKNN graph with the full Euclidean MST on the data points.

neighbor.method = "exact" computes all pairwise distances and is the deterministic reference implementation. neighbor.method = "ann" uses the bundled ANN kd-tree for the Euclidean kNN search step; exact parity can differ only in nearest-neighbor tie cases. Edge weights are always returned as ordinary Euclidean distances. Exact component.mst repair uses exact pairwise bridge distances; component.mst.ann uses ANN bridge candidates before guaranteed exact fallback.

If prune.method = "local.geodesic" or prune.edges = TRUE, an experimental local-geodesic pruning stage is applied after the sKNN support is built and before optional MST connectivity repair. Candidate edges are processed longest-first. For an edge ⁠(i, j)⁠, the edge is removed only when the currently retained graph contains an alternative path from i to j, restricted to the union of their local neighborhoods, whose length is at most prune.tau times the direct edge length. prune.method = "global.geodesic.ratio" instead uses the whole graph as the alternative-path search domain and removes long edges whose shortest alternative path is within the configured geodesic-ratio threshold.

Value

A list of class "sknn_graph" with adjacency lists, weights, edge matrix, kNN index matrix, component diagnostics, and any MST edges added. The graph lifecycle fields are:

raw_adj_list, raw_weight_list

The native sKNN graph before pruning and before optional MST component repair.

pruned_adj_list, pruned_weight_list

The graph after optional local geometric pruning and before optional MST component repair. If pruning is disabled, these fields are identical to the raw graph.

raw_repaired_adj_list, raw_repaired_weight_list

The native sKNN graph after MST component repair.

pruned_repaired_adj_list, pruned_repaired_weight_list

The prune-first branch after MST component repair.

repaired_pruned_adj_list, repaired_pruned_weight_list

The repair-first branch after applying local geometric pruning to the repaired raw graph.

adj_list, weight_list

The final graph after optional MST component repair. Downstream algorithms should use these fields unless they explicitly need a lifecycle diagnostic stage.

Examples

X <- rbind(c(0, 0), c(1, 0), c(10, 0), c(11, 0))
g <- create.sknn.graph(X, k = 1, connect.components = TRUE)
g$n_components_before
g$n_components_after
g$mst_edge_matrix

Create a Star Graph by Joining Chains

Description

Create a Star Graph by Joining Chains

Usage

create.star.graph(sizes)

Arguments

Value

An adjacency list for the star graph.

Create a Subgraph from a Graph Object

Description

Create a Subgraph from a Graph Object

Usage

create.subgraph(
  S.graph,
  id.indices = NULL,
  ids = NULL,
  S = NULL,
  use.sequential.indices = FALSE
)

Arguments

Value

A list with subgraph adj_list and dist_list.

Create a Threshold Distance Graph

Description

Create a Threshold Distance Graph

Usage

create.threshold.distance.graph(dist.matrix, threshold, include.names = TRUE)

Arguments

Value

A list with adj_list and weight_list.

Deprecated Radius Graph Constructors

Description

create.radius.graph() and create.adaptive.radius.graph() are deprecated compatibility wrappers. Use create.rknn.graph() with type = "fixed" or type = "adaptive.radius" instead.

Usage

create.radius.graph(
  X,
  radius,
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

create.adaptive.radius.graph(
  X,
  k.scale,
  radius.factor = 1,
  radius.rule = c("max", "min", "geomean"),
  radius.search = c("ann", "all.pairs"),
  return.timing = FALSE,
  graph.detail = c("full", "minimal"),
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

Value

A graph list produced by create.rknn.graph(). The fixed-radius wrapper returns an object of class "radius_graph"; the adaptive-radius wrapper returns an object of class "adaptive_radius_graph". Each object contains the final adjacency and weight lists, an edge matrix and edge weights, graph-construction parameters, and component, pruning, and repair diagnostics.

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
create.rknn.graph(X, type = "fixed", radius = 1.1)$edge_matrix
create.rknn.graph(X, type = "adaptive.radius", k.scale = 1)$edge_matrix

Detect Graph Endpoints from a 3D Embedding

Description

Detects terminal arm tips in a graph by:

1. computing graph endpoint scores from the 3D embedding,

2. optionally smoothing those scores on the graph using fit.rdgraph.regression() and refit.rdgraph.regression(),

3. finding graph-local maxima with detect.local.extrema(),

4. retaining only maxima that persist across neighborhood scales.

The function works with terminal regions in an embedding; returned endpoints need not be degree-1 vertices.

Usage

detect.graph.endpoints(
  adj.list,
  weight.list,
  layout.3d,
  neighborhood = c("geodesic_k", "geodesic_radius"),
  k = c(10L, 20L, 30L),
  radius = NULL,
  q = 0.1,
  neighbor.weighting = c("uniform", "inverse_distance", "gaussian"),
  gaussian.sigma = NULL,
  min.neighborhood.size = 3L,
  scale.aggregate = c("mean", "median", "min", "max"),
  score.metric = c("score", "m", "s.q", "s.min"),
  smooth = FALSE,
  fitted.model = NULL,
  smooth.fit.args = NULL,
  smooth.refit.args = NULL,
  detect.max.radius = 2,
  detect.min.neighborhood.size = 2L,
  scale.stability.radius = NULL,
  min.scale.stability = 0.5,
  min.score.quantile = 0.8,
  max.endpoints = NULL,
  verbose = FALSE
)

Arguments

Value

A list with endpoint vertices, score diagnostics, optional smoothed scores, scale stability summaries, and the local-extrema fit used for endpoint calling.

Detect Local Extrema in a Graph

Description

Detect Local Extrema in a Graph

Usage

detect.local.extrema(
  adj.list,
  weight.list,
  y,
  max.radius,
  min.neighborhood.size,
  detect.maxima = TRUE,
  custom.prefix = NULL
)

Arguments

Value

A local_extrema object.

Produce k-NN Distance and Index Matrices from a Distance Matrix

Description

Produce k-NN Distance and Index Matrices from a Distance Matrix

Usage

dist.to.knn(d, k)

Arguments

Value

A list with nn.i and nn.d matrices.

Compute Edge Difference Between Two Graphs

Description

Compute Edge Difference Between Two Graphs

Usage

edge.diff(graph1, graph2)

Arguments

Value

A list containing neighbors present in graph1 but not graph2 for each vertex.

Estimate Pairwise Geodesic Distances

Description

Estimate Pairwise Geodesic Distances

Usage

estimate.geodesic.distances(points, k = 5, graph = NULL, method = "knn.graph")

Arguments

Value

Numeric matrix of graph shortest-path distances.

Euclidean Distance Between Two Points

Description

Euclidean Distance Between Two Points

Usage

euclidean.distance(p1, p2)

Arguments

Value

Euclidean distance between p1 and p2.

Extract Unique Edge Lengths from an Undirected Graph

Description

Extract Unique Edge Lengths from an Undirected Graph

Usage

extract.edge.lengths(
  adj.list,
  edge.length.list,
  method = c("vectorized", "preallocate", "parallel"),
  mc.cores = 2
)

Arguments

Value

Numeric vector of unique undirected edge lengths.

Extract Edge Lengths Along a Graph Path

Description

Extract Edge Lengths Along a Graph Path

Usage

extract.trajectory.edge.lengths(
  traj,
  adj.list,
  edge.length.list,
  add.quantiles = FALSE
)

Arguments

Value

Data frame with consecutive vertex pairs and their edge lengths.

Generate a Weighted Circle Graph

Description

Generate a Weighted Circle Graph

Usage

generate.circle.graph(n, type = "random", seed = NULL)

Arguments

Value

A list with adj.list and weight.list.

Select Graph Endpoints by Core-Eccentricity Geometry

Description

Select Graph Endpoints by Core-Eccentricity Geometry

Usage

geodesic.core.endpoints(
  adj.list,
  weight.list,
  core.quantile = 0.1,
  endpoint.quantile = 0.9,
  use.approx.eccentricity = TRUE,
  n.landmarks = 64L,
  max.endpoints = NULL,
  seed = 1L,
  verbose = FALSE
)

Arguments

Value

A geodesic_core_endpoints list of endpoints and diagnostics.

Geodesic Disk in a Weighted Graph

Description

Geodesic Disk in a Weighted Graph

Usage

geodesic.disk(adj.list, weight.list, center.vertex, radius = NULL, n = NULL)

Arguments

Value

List with vertices, effective radius, and aligned dists.

Estimate Geodesic Nearest Neighbors Within a Point Cloud

Description

Estimate Geodesic Nearest Neighbors Within a Point Cloud

Usage

geodesic.knn(X, k, K = 5, G = NULL)

Arguments

Value

A list with nn.index and nn.dist matrices.

Estimate Geodesic Nearest Neighbors from Grid Points to Data Points

Description

Estimate Geodesic Nearest Neighbors from Grid Points to Data Points

Usage

geodesic.knnx(X, X.grid, k, method = "knn.graph", K = 5)

Arguments

Value

A list with graph vertices, graph edges, nn.index, and nn.dist.

Get Unique Edge Weights from a Weighted Graph

Description

Get Unique Edge Weights from a Weighted Graph

Usage

get.edge.weights(adj.list, weight.list, n.cores = 1L)

Arguments

Value

Numeric vector of unique undirected edge weights.

Get Shortest Path Between Two Vertices

Description

Get Shortest Path Between Two Vertices

Usage

get.shortest.path(pg, from, to)

Arguments

Value

Path information, or NULL when no stored path exists.

Convert Coordinates and Edges to a Weighted Adjacency Matrix

Description

Convert Coordinates and Edges to a Weighted Adjacency Matrix

Usage

graph.adj.mat(X, E)

Arguments

Value

Symmetric weighted adjacency matrix with Euclidean edge lengths.

Assign Vertices to Connected Components

Description

Assign Vertices to Connected Components

Usage

graph.connected.components(adj.list)

Arguments

Value

Integer vector of component IDs, one per vertex.

Calculate Graph Edit Distance (Pure R Implementation)

Description

Computes the graph edit distance between two weighted graphs with identical vertex sets using a pure R implementation. This function considers edge insertions, deletions, and weight modifications.

Usage

graph.edit.distance(
  graph1.adj.list,
  graph1.weights,
  graph2.adj.list,
  graph2.weights,
  edge.cost = 1,
  weight.cost.factor = 0.1
)

Arguments

Details

The graph edit distance is calculated as:

• For edges present in one graph but not the other: edge.cost

• For edges present in both graphs with different weights: abs(weight1 - weight2) * weight.cost.factor

Both graphs must have the same number of vertices. The function assumes undirected graphs.

Value

A non-negative numeric value representing the graph edit distance between the two input graphs.

Examples

# Create two simple graphs
graph1.adj <- list(c(2, 3), c(1, 3), c(1, 2))
graph1.wts <- list(c(1, 2), c(1, 3), c(2, 3))

graph2.adj <- list(c(2, 3), c(1, 3), c(1, 2))
graph2.wts <- list(c(1.5, 2), c(1.5, 2.5), c(2, 2.5))

# Calculate distance
dist <- graph.edit.distance(graph1.adj, graph1.wts,
                           graph2.adj, graph2.wts)
print(dist)  # Weight differences only

Embed Graph in 2D or 3D Space

Description

Embed Graph in 2D or 3D Space

Usage

graph.embedding(
  adj.list,
  weights.list = NULL,
  invert.weights = TRUE,
  dim = 2,
  method = c("fr", "kk"),
  verbose = FALSE
)

Arguments

Value

Numeric layout matrix with one row per embedded vertex.

Compute Graph Geodesic Distances from a Graph Object

Description

Compute Graph Geodesic Distances from a Graph Object

Usage

graph.geodesic.distances(graph, vertices = NULL, stage = "final")

Arguments

Value

A numeric matrix of shortest-path distances.

Generate Spectral Embedding of a Graph

Description

Generate Spectral Embedding of a Graph

Usage

graph.spectral.embedding(evectors, dim, evalues = NULL)

Arguments

Value

Numeric spectral embedding matrix.

Compute Graph Spectrum

Description

Compute Graph Spectrum

Usage

graph.spectrum(
  graph,
  nev = NULL,
  use.R = FALSE,
  return.Laplacian = FALSE,
  return.dense = FALSE
)

Arguments

Value

A list with evalues, evectors, and optionally laplacian.

Compute divergence between two graphs using a selected graph summary

Description

Extracts one selected graph summary from two graph-like objects and computes a divergence between the resulting probability mass functions.

Currently the supported divergence is Jensen-Shannon divergence, implemented via jensen.shannon.divergence().

Usage

graph.summary.divergence(
  g1,
  g2,
  summary = c("degree_distribution", "edge_weight_distribution",
    "component_size_distribution", "neighborhood_label_distribution"),
  divergence = c("js"),
  labels = NULL,
  summary.args = list(),
  support = NULL,
  return.details = TRUE
)

Arguments

Value

If return.details = TRUE, a list with fields:

• summary: summary type used.

• divergence: divergence type used.

• value: scalar divergence value.

• pmf1: aligned PMF for g1.

• pmf2: aligned PMF for g2.

• support: aligned support.

• metadata: summary-specific metadata for both graphs.

Otherwise, returns the scalar divergence value.

Weighted Graph Distance Between Graphs with Identical Vertex Sets

Description

Weighted Graph Distance Between Graphs with Identical Vertex Sets

Usage

identical.vertex.set.weighted.graph.similarity(
  graph1.adj.list,
  graph1.weights,
  graph2.adj.list,
  graph2.weights,
  calculate.normalized.deviation = FALSE
)

Arguments

Value

Numeric distance-matrix deviation.

Compute Distance Preservation Correlations

Description

Computes Pearson and Spearman correlations between estimated and true pairwise distances over the upper-triangular distance entries.

Usage

isometry.distance.correlations(
  D.estimated,
  D.true,
  true.tol = sqrt(.Machine$double.eps)
)

Arguments

Value

Named numeric vector with entries pearson_cor and spearman_cor.

Examples

D <- as.matrix(dist(1:4))
isometry.distance.correlations(2 * D, D)

Compute Multiplicative Distortion Quantiles

Description

Computes quantiles of the calibrated pairwise distortion

\rho_{ij}=\alpha\hat D_{ij}/D_{ij}.

Values near 1 indicate approximately isometric distance preservation.

Usage

isometry.distortion.quantiles(
  D.estimated,
  D.true,
  probs = c(0.05, 0.5, 0.95),
  scale = TRUE,
  true.tol = sqrt(.Machine$double.eps)
)

Arguments

Value

Named numeric vector of distortion quantiles.

Examples

D <- as.matrix(dist(1:4))
isometry.distortion.quantiles(1.1 * D, D)

Compute Geodesic-Isometry Diagnostics

Description

Computes signed and scale-regime diagnostics for comparing estimated graph geodesic distances with reference geodesic distances. Distances are first optionally calibrated by the least-squares scale from isometry.scale().

Usage

isometry.geodesic.diagnostics(
  D.estimated,
  D.true,
  scale = TRUE,
  true.tol = sqrt(.Machine$double.eps),
  band.probs = c(1/3, 2/3)
)

Arguments

Value

Named numeric vector with relative geodesic stress, signed residual bias, shortcut fraction, relative absolute residual quantiles, and median signed relative residuals in short/mid/long reference-distance bands.

Examples

D <- as.matrix(dist(1:4))
isometry.geodesic.diagnostics(1.1 * D, D)

Compute Relative Absolute Isometry Errors

Description

Computes quantiles of pairwise relative absolute errors

\left|\alpha\hat D_{ij}-D_{ij}\right|/D_{ij}.

Usage

isometry.rel.abs.error(
  D.estimated,
  D.true,
  probs = c(0.5, 0.95),
  scale = TRUE,
  true.tol = sqrt(.Machine$double.eps)
)

Arguments

Value

Named numeric vector of relative absolute error quantiles.

Examples

D <- as.matrix(dist(1:4))
isometry.rel.abs.error(1.1 * D, D)

Compute Relative RMS Isometry Error

Description

Computes the relative root-mean-square distance-matrix error after optional scalar calibration:

\left[ \frac{\sum_{i<j}(\alpha\hat D_{ij}-D_{ij})^2} {\sum_{i<j}D_{ij}^2} \right]^{1/2}.

Usage

isometry.rel.rms.error(
  D.estimated,
  D.true,
  scale = TRUE,
  true.tol = sqrt(.Machine$double.eps)
)

Arguments

Value

Numeric scalar relative RMS error.

Examples

D <- as.matrix(dist(1:4))
isometry.rel.rms.error(2 * D, D)

Compute the Optimal Isometry Calibration Scale

Description

Computes the least-squares scalar \alpha that aligns estimated distances to true distances:

\alpha^* = \frac{\sum_{i<j} \hat D_{ij}D_{ij}} {\sum_{i<j} \hat D_{ij}^2}.

Usage

isometry.scale(D.estimated, D.true, true.tol = sqrt(.Machine$double.eps))

Arguments

Value

Numeric scalar calibration scale.

Examples

D <- as.matrix(dist(1:4))
isometry.scale(2 * D, D)

Jensen-Shannon Divergence

Description

Jensen-Shannon Divergence

Usage

jensen.shannon.divergence(p, q)

Arguments

Value

Jensen-Shannon divergence using log base 2.

Join Two Adjacency-List Graphs

Description

Join Two Adjacency-List Graphs

Usage

join.graphs(graph1, graph2, i1, i2)

Arguments

Value

A joined adjacency list using 1-based vertex indices.

Load Graph Data from RDA Files

Description

Loads pruned graph data from a series of RDA files for different k values and combines them into a list structure containing adjacency and distance lists.

Usage

load.graph.data(
  k.values,
  prefix,
  suffix = "_NN_graph.rda",
  graph.object.name = "S.graph",
  verbose = TRUE
)

Arguments

Details

The function expects RDA files to be named according to the pattern: paste0(prefix, k, suffix) for each k value.

Each RDA file should contain an object with the name specified in graph.object.name, which must have components pruned_adj_list and pruned_dist_list.

Value

A list containing two components:

Examples

prefix <- file.path(tempdir(), "dgraphs-k")
S.graph <- list(
  pruned_adj_list = list(c(2L), c(1L)),
  pruned_dist_list = list(1, 1)
)
save(S.graph, file = paste0(prefix, 2, ".rda"))
graph.data <- load.graph.data(
  2, prefix = prefix, suffix = ".rda", verbose = FALSE
)
unlink(paste0(prefix, 2, ".rda"))
names(graph.data$adj.list)

Find the Minimum Hop Limit for Path Existence

Description

Find the Minimum Hop Limit for Path Existence

Usage

minh.limit(x, from, to)

Arguments

Value

Minimum hop limit where the path exists, or NULL.

Construct the Nerve Graph of a Cover

Description

Construct the Nerve Graph of a Cover

Usage

nerve.graph(covering.list, n.cores = 1)

Arguments

Value

A list with adjacency.list, weights.list, and adjacency.matrix.

Construct a path.graph object

Description

Construct a path.graph object

Usage

new.path.graph(adj.list, edge.length.list, hop.list, shortest.paths)

Value

A list of class "path.graph" containing aligned adjacency, edge-length, and hop-count lists together with the stored shortest paths.

Plot the distribution of overlap values

Description

Plot the distribution of overlap values

Usage

overlap.distribution.plot(x, radius_idx = NULL)

Arguments

Value

Invisibly returns NULL

Normalized Cumulative Distance Along a Vertex Path

Description

Normalized Cumulative Distance Along a Vertex Path

Usage

path.dist(s, V, edge.col = "gray")

Arguments

Value

Numeric vector of cumulative path distances normalized to end at 1.

Compute Euclidean Path Length

Description

Compute Euclidean Path Length

Usage

path.length(X)

Arguments

Value

Total Euclidean length of the path.

Plot Diagnostics for Intersection k-NN Graph Analysis

Description

Plot Diagnostics for Intersection k-NN Graph Analysis

Usage

## S3 method for class 'IkNNgraphs'
plot(
  x,
  type = "diag",
  diags = c("edist", "edge", "deg"),
  with.pwlm = TRUE,
  with.lmin = FALSE,
  breakpoint.col = "blue",
  lmin.col = "gray",
  k = NA,
  mar = c(2.5, 2.5, 0.5, 0.5),
  mgp = c(2.5, 0.5, 0),
  tcl = -0.3,
  xline = 2.4,
  yline = 3.15,
  ...
)

Arguments

Value

Invisibly returns TRUE.

Plot method for build_iknn_graphs_and_selectk

Description

Plot method for build_iknn_graphs_and_selectk

Usage

## S3 method for class 'build_iknn_graphs_and_selectk'
plot(
  x,
  which = c("connect", "edit", "mixing"),
  connect.args = list(),
  edit.args = list(),
  mixing.args = list(),
  par.args = list(),
  ...
)

Arguments

Value

Invisibly returns x, unchanged, after producing the requested panels. If which is empty, invisibly returns NULL without plotting.

Plot method for cst_graph_mixing_stats

Description

Plot method for cst_graph_mixing_stats

Usage

## S3 method for class 'cst_graph_mixing_stats'
plot(
  x,
  which = c("null.homophily", "null.assortativity", "mixing.matrix", "conductance"),
  ...
)

Arguments

Value

Invisibly returns NULL after producing the requested diagnostic panels.

Plot Geodesic Statistics

Description

Creates visualizations of geodesic statistics to help understand the relationship between radius and number of geodesics.

Usage

## S3 method for class 'geodesic_stats'
plot(
  x,
  plot.type = c("summary", "heatmap", "vertex", "all"),
  selected.vertices = NULL,
  max.vertices = 10,
  ...
)

Arguments

Value

Invisibly returns NULL.

Examples

stats <- list(
  radii = c(0.2, 0.4),
  geodesic_rays = matrix(c(2, 3, 3, 4), nrow = 2, byrow = TRUE),
  composite_geodesics = matrix(c(1, 1, 1, 2), nrow = 2, byrow = TRUE),
  grid_vertices = c(5L, 9L),
  summary = data.frame(
    radius = c(0.2, 0.4),
    avg_rays = c(2.5, 3.5),
    max_rays = c(3, 4),
    composite_ratio = c(0.4, 0.5),
    avg_overlap_median = c(0.35, 0.45)
  )
)
class(stats) <- c("geodesic_stats", "list")

plot(stats, plot.type = "summary")
plot(stats, plot.type = "vertex", selected.vertices = 5)

Plot Method for IkNN Stability Metrics

Description

Plot Method for IkNN Stability Metrics

Usage

## S3 method for class 'iknn_stability_metrics'
plot(x, ...)

Arguments

Value

Invisibly returns TRUE after producing the stability diagnostic plot.

Plot method for vertex_geodesic_stats objects

Description

Plot method for vertex_geodesic_stats objects

Usage

## S3 method for class 'vertex_geodesic_stats'
plot(x, ...)

Arguments

Value

Invisibly returns NULL

Examples

x <- data.frame(
  radius = c(0.2, 0.4, 0.6),
  rays = c(3, 5, 6),
  composite_geodesics = c(1, 2, 3),
  overlap_min = c(0.10, 0.15, 0.20),
  overlap_p05 = c(0.15, 0.20, 0.25),
  overlap_p25 = c(0.20, 0.25, 0.30),
  overlap_median = c(0.30, 0.40, 0.50),
  overlap_p75 = c(0.40, 0.50, 0.60),
  overlap_p95 = c(0.55, 0.65, 0.75),
  overlap_max = c(0.60, 0.70, 0.80),
  potential_pairs = c(3, 10, 15),
  composite_ratio = c(1/3, 0.2, 0.2),
  overlap_ratio = c(0.30, 0.40, 0.50)
)
class(x) <- c("vertex_geodesic_stats", "data.frame")
attr(x, "vertex") <- 7L

plot(x)

Plot a Graph with Colored Vertices

Description

Plot a Graph with Colored Vertices

Usage

plot2D.colored.graph(
  embedding,
  adj.list,
  vertex.colors,
  vertex.size = 1,
  edge.alpha = 0.2,
  color.palette = NULL,
  main = "",
  add.legend = TRUE
)

Arguments

Value

Invisibly returns NULL; produces a plot as a side effect.

Print method for build_iknn_graphs_and_selectk

Description

Print method for build_iknn_graphs_and_selectk

Usage

## S3 method for class 'build_iknn_graphs_and_selectk'
print(x, ...)

Arguments

Value

Invisibly returns x, unchanged, after printing its selected neighborhood sizes and trimming status.

Print method for geodesic_stats objects

Description

Prints a brief overview of the geodesic statistics.

Usage

## S3 method for class 'geodesic_stats'
print(x, ...)

Arguments

Value

The object invisibly.

Print Method for knn.outliers Objects

Description

Prints a summary of the outlier detection results from remove.knn.outliers.

Usage

## S3 method for class 'knn.outliers'
print(x, ...)

Arguments

Value

Invisibly returns the input object.

Examples

knn.res <- list(
  S.q = matrix(c(0, 0,
                 1, 1,
                 2, 2), ncol = 2, byrow = TRUE),
  y.q = c(1.0, 1.5, 2.0),
  nn.d = matrix(c(0.2, 0.4,
                  0.3, 0.5,
                  1.4, 1.8,
                  0.25, 0.45),
                ncol = 2, byrow = TRUE),
  d.thld = 1,
  idx = c(TRUE, TRUE, FALSE, TRUE),
  n.outliers = 1L,
  method = "qf"
)
class(knn.res) <- "knn.outliers"

knn.res

Print Method for Maximal Packing Results

Description

Print Method for Maximal Packing Results

Usage

## S3 method for class 'maximal_packing'
print(x, ...)

Arguments

Value

Invisible copy of x

Examples

x <- list(
  adj_list = list(c(2L), c(1L, 3L), c(2L, 4L), c(3L)),
  graph_diameter = 3,
  max_packing_radius = 1.5,
  grid_vertices = c(1L, 4L)
)
class(x) <- "maximal_packing"

x

Print Method for mknn_graph Objects

Description

Prints a concise summary of a mutual k-nearest neighbor graph object.

Usage

## S3 method for class 'mknn_graph'
print(x, ...)

Arguments

Value

Invisibly returns the input object.

Examples

graph <- list(
  n_vertices = 3L,
  n_edges = 2L,
  k = 2L,
  adj_list = list(c(2L), c(1L, 3L), c(2L))
)
class(graph) <- c("mknn_graph", "list")

print(graph)

Print Method for mknn_graphs Objects

Description

Prints a concise summary of a collection of mutual k-nearest neighbor graphs.

Usage

## S3 method for class 'mknn_graphs'
print(x, ...)

Arguments

Value

Invisibly returns the input object.

Examples

graphs <- list(
  k_statistics = data.frame(
    k = 2:4,
    n_edges_pruned = c(2L, 3L, 3L)
  )
)
attr(graphs, "kmin") <- 2L
attr(graphs, "kmax") <- 4L
attr(graphs, "n_vertices") <- 3L
class(graphs) <- "mknn_graphs"

print(graphs)

Print Method for MST Completion Graph Objects

Description

Displays a concise summary of an MST completion graph object, including basic graph statistics and parameter information.

Usage

## S3 method for class 'mst_completion_graph'
print(x, ...)

Arguments

Details

This method provides a human-readable overview of the graph structure without displaying the full adjacency lists. For detailed inspection of graph components, use direct indexing (e.g., x$mst_adj_list) or the summary method.

Value

Invisibly returns the input object x.

See Also

summary.mst_completion_graph for more detailed summaries, create.cmst.graph for creating MST completion graphs

Examples

graph <- list(
  mst_adj_list = list(c(2L), c(1L, 3L), c(2L)),
  mst_weight_list = list(1.1, c(1.1, 0.9), 0.9),
  cmst_adj_list = list(c(2L, 3L), c(1L, 3L), c(1L, 2L)),
  cmst_weight_list = list(c(1.1, 1.4), c(1.1, 0.9), c(1.4, 0.9)),
  mst_edge_weights = c(1.1, 0.9),
  cmst_distance_threshold = 1.08
)
attr(graph, "q_thld") <- 0.8
attr(graph, "cmst_distance_threshold") <- graph$cmst_distance_threshold
class(graph) <- c("mst_completion_graph", "list")

print(graph)

Print Method for Packing Validation Results

Description

Print Method for Packing Validation Results

Usage

## S3 method for class 'packing_validation'
print(x, ...)

Arguments

Value

Invisible copy of x

Examples

x <- list(
  valid = TRUE,
  is.maximal = TRUE,
  min.packing.distance = 2,
  max.coverage.distance = 1,
  violations = NULL,
  potential.additions = NULL
)
class(x) <- "packing_validation"

x

Print Method for summary.knn.outliers Objects

Description

Prints the summary of outlier detection results.

Usage

## S3 method for class 'summary.knn.outliers'
print(x, ...)

Arguments

Value

Invisibly returns the input object.

Examples

knn.res <- list(
  S.q = matrix(c(0, 0,
                 1, 1,
                 2, 2), ncol = 2, byrow = TRUE),
  y.q = c(1.0, 1.5, 2.0),
  nn.d = matrix(c(0.2, 0.4,
                  0.3, 0.5,
                  1.4, 1.8,
                  0.25, 0.45),
                ncol = 2, byrow = TRUE),
  d.thld = 1,
  idx = c(TRUE, TRUE, FALSE, TRUE),
  n.outliers = 1L,
  method = "qf"
)
class(knn.res) <- "knn.outliers"

summary(knn.res)

Print Summary of MST Completion Graph

Description

Formats and displays the summary information for an MST completion graph in a readable format.

Usage

## S3 method for class 'summary.mst_completion_graph'
print(x, digits = 3L, ...)

Arguments

Value

Invisibly returns the input summary object.

Examples

graph <- list(
  mst_adj_list = list(c(2L), c(1L, 3L), c(2L)),
  mst_weight_list = list(1.1, c(1.1, 0.9), 0.9),
  cmst_adj_list = list(c(2L, 3L), c(1L, 3L), c(1L, 2L)),
  cmst_weight_list = list(c(1.1, 1.4), c(1.1, 0.9), c(1.4, 0.9)),
  mst_edge_weights = c(1.1, 0.9),
  cmst_distance_threshold = 1.08
)
attr(graph, "q_thld") <- 0.8
attr(graph, "cmst_distance_threshold") <- graph$cmst_distance_threshold
class(graph) <- c("mst_completion_graph", "list")

graph_summary <- summary(graph)
print(graph_summary, digits = 4)

Remove Outliers from a State Space Using k-Nearest Neighbors

Description

Identifies and removes outliers from a multivariate state space based on k-nearest neighbor distances. This function implements several strategies for outlier detection, all based on the principle that outliers tend to be isolated from the main data clusters and thus have larger distances to their nearest neighbors.

Usage

remove.knn.outliers(
  S,
  y = NULL,
  p = 0.98,
  dist.factor = 100,
  K = 30,
  method = "diff.dist.factor"
)

Arguments

Details

The function determines outliers by analyzing the distances between points and their K nearest neighbors. Several detection methods are available:

When K = 1:

Points are flagged as outliers if their distance to the nearest neighbor exceeds the p-th percentile threshold of all nearest neighbor distances.

"dist.factor":

Points are considered outliers if the ratio of the K-th nearest neighbor distance to the 1st nearest neighbor distance exceeds dist.factor.

"diff.dist.factor" (default):

For each point, finds the maximum jump in distance between consecutive neighbors, normalizes by the median jump across all points, and flags points as outliers if their relative jump exceeds dist.factor. This method is particularly robust as it adapts to the overall distribution of distances.

Default unnamed method:

Iteratively checks if the first nearest neighbor distance exceeds the threshold or if any consecutive difference between neighbor distances exceeds the threshold.

Value

A list of class "knn.outliers" containing the following components:

S.q

The filtered state space matrix with outliers removed.

y.q

The filtered dependent variable (if y was provided), otherwise NULL.

nn.d

A matrix of dimensions nrow(S) x K containing distances to the K nearest neighbors for each point.

d.thld

The distance threshold used for outlier detection.

idx

A logical vector indicating which points were kept (TRUE) and which were identified as outliers (FALSE).

n.outliers

The number of outliers detected.

method

The outlier detection method used.

See Also

get.knn for the k-nearest neighbor calculation, quantile for percentile calculations

Examples

# Create a sample dataset with outliers
set.seed(123)
n_normal <- 120
n_outliers <- 6

# Generate normal data
normal_data <- matrix(rnorm(n_normal * 2), ncol = 2)

# Generate outliers far from the main cluster
outliers <- cbind(rnorm(n_outliers, mean = 10, sd = 0.5),
                  rnorm(n_outliers, mean = 10, sd = 0.5))

# Combine data
S <- rbind(normal_data, outliers)
y <- c(rnorm(n_normal), rnorm(n_outliers, mean = 5))

# Remove outliers using the default method
result <- remove.knn.outliers(S, y, K = 10)

# Print summary
cat("Number of outliers detected:", result$n.outliers, "\n")
cat("Percentage of data retained:",
    round(100 * nrow(result$S.q) / nrow(S), 2), "%\n")

# Use a different method with more conservative threshold
result2 <- remove.knn.outliers(S, y, p = 0.95, method = "dist.factor",
                               dist.factor = 5, K = 10)

# Plot the original and filtered state space
oldpar <- par(mfrow = c(1, 2))
plot(S, col = "gray", main = "Original State Space",
     xlab = "Dimension 1", ylab = "Dimension 2")
points(S[!result$idx, ], col = "red", pch = 16, cex = 1.2)

plot(result$S.q, col = "blue", pch = 16,
     main = "Filtered State Space",
     xlab = "Dimension 1", ylab = "Dimension 2")
legend("topright", legend = c("Retained", "Removed"),
       col = c("blue", "red"), pch = 16)
par(oldpar)

Remove Self-Loops from an Adjacency List

Description

Remove Self-Loops from an Adjacency List

Usage

rm.self.loops(adj.list)

Arguments

Value

The adjacency list with entries equal to their vertex index removed.

Computes Shortest Path Distances for Selected Vertices

Description

Computes Shortest Path Distances for Selected Vertices

Usage

shortest.path(graph, edge.lengths, vertices)

Arguments

Value

A numeric matrix of shortest-path distances.

Subdivide a Path into Arc-Length Spaced Points

Description

Subdivide a Path into Arc-Length Spaced Points

Usage

subdivide.path(path, n.subdivision.pts)

Arguments

Value

Matrix of subdivided path coordinates.

Summarize Deviation from Isometry

Description

Computes the standard benchmark summary used to compare graph geodesic distances with reference geodesic distances: optimal scalar calibration, relative RMS error, relative absolute error quantiles, multiplicative distortion quantiles, and distance correlations.

Usage

summarize.isometry.deviation(
  D.estimated,
  D.true,
  scale = TRUE,
  true.tol = sqrt(.Machine$double.eps)
)

Arguments

Value

A one-row data frame.

Examples

D <- as.matrix(dist(1:4))
summarize.isometry.deviation(1.1 * D, D)

Summarize overlap statistics from geodesic_stats object

Description

Summarize overlap statistics from geodesic_stats object

Usage

summarize_overlap_statistics(object)

Arguments

Value

A data frame with summary statistics for overlap at each radius

Summarize IkNN Graph Object

Description

Prints a summary of an IkNN graph object, including the number of vertices, edges, and pruning statistics.

Usage

## S3 method for class 'IkNN'
summary(object, ...)

Arguments

Value

Invisibly returns NULL while printing summary information to the console

Examples

graph <- list(
  pruned_adj_list = list(c(2L, 3L), c(1L, 3L), c(1L, 2L)),
  n_edges = 3L,
  n_pruned_edges = 2L,
  n_removed_edges = 1L,
  edge_reduction_ratio = 1 / 3
)
class(graph) <- c("IkNN", "list")

summary(graph)

Summary method for geodesic_stats objects

Description

Provides a summary table of geodesic statistics with percentages and counts for different metric types.

Usage

## S3 method for class 'geodesic_stats'
summary(object, type = c("rays", "composite", "overlap"), ...)

Arguments

Value

A matrix with row for each radius and columns for each unique count value. Each cell contains a string with "percent (count)" format.

Examples

stats <- list(
  radii = c(0.2, 0.4),
  geodesic_rays = matrix(c(2, 3, 3, 4), nrow = 2, byrow = TRUE),
  composite_geodesics = matrix(c(1, 1, 1, 2), nrow = 2, byrow = TRUE),
  path_overlap = list(
    min = matrix(c(0.1, 0.2, 0.2, 0.3), nrow = 2, byrow = TRUE),
    p05 = matrix(c(0.1, 0.2, 0.2, 0.3), nrow = 2, byrow = TRUE),
    p25 = matrix(c(0.2, 0.3, 0.3, 0.4), nrow = 2, byrow = TRUE),
    median = matrix(c(0.3, 0.4, 0.4, 0.5), nrow = 2, byrow = TRUE),
    p75 = matrix(c(0.4, 0.5, 0.5, 0.6), nrow = 2, byrow = TRUE),
    p95 = matrix(c(0.5, 0.6, 0.6, 0.7), nrow = 2, byrow = TRUE),
    max = matrix(c(0.6, 0.7, 0.7, 0.8), nrow = 2, byrow = TRUE)
  )
)
class(stats) <- c("geodesic_stats", "list")

summary(stats)
summary(stats, type = "composite")
summary(stats, type = "overlap")

Summarize an iknn_graphs Object

Description

Provides a detailed summary of an iknn_graphs object created by the create.iknn.graphs() function. The summary includes statistics for each intersection kNN graph in the sequence, displaying information about the connectivity and structure of the graphs for different k values.

Usage

## S3 method for class 'iknn_graphs'
summary(object, use.isize.pruned = FALSE, ...)

Arguments

Details

The summary function extracts and presents key statistics about the structure of each intersection kNN graph in the iknn_graphs object. All graphs share the same number of vertices (equal to the number of rows in the input data matrix), but they differ in the number of edges due to varying k values and the pruning methods applied during graph creation.

The function displays general information about the graph sequence, including the number of vertices, the range of k values, and the pruning parameters used. It then presents a tabular summary of statistics for each individual graph, showing how the graph structure changes as k increases.

For each intersection kNN graph, the following metrics are calculated:

• Number of edges: Total number of connections in the graph

• Mean degree: Average number of connections per vertex

• Min/Max degree: Range of vertex connectivity

• Density: Proportion of potential connections that are actually present

• Sparsity: 1 - density, measuring the proportion of missing connections

Value

Invisibly returns a data frame containing statistics for each graph. The data frame has the following columns:

See Also

create.iknn.graphs for creating intersection kNN graphs.

Examples

# Create sample data
set.seed(123)
x <- matrix(rnorm(1000), ncol = 5)

# Generate intersection kNN graphs
iknn.res <- create.iknn.graphs(
  x,
  kmin = 3,
  kmax = 10,
  n.cores = 1,
  with.isize.pruning = TRUE
)

# Summarize the geometrically pruned graphs
summary(iknn.res)

# Summarize the intersection-size pruned graphs
summary(iknn.res, use.isize.pruned = TRUE)

Summary Method for knn.outliers Objects

Description

Provides a detailed summary of the outlier detection results from remove.knn.outliers.

Usage

## S3 method for class 'knn.outliers'
summary(object, ...)

Arguments

Value

A list of class "summary.knn.outliers" containing summary statistics.

Examples

knn.res <- list(
  S.q = matrix(c(0, 0,
                 1, 1,
                 2, 2), ncol = 2, byrow = TRUE),
  y.q = c(1.0, 1.5, 2.0),
  nn.d = matrix(c(0.2, 0.4,
                  0.3, 0.5,
                  1.4, 1.8,
                  0.25, 0.45),
                ncol = 2, byrow = TRUE),
  d.thld = 1,
  idx = c(TRUE, TRUE, FALSE, TRUE),
  n.outliers = 1L,
  method = "qf"
)
class(knn.res) <- "knn.outliers"

summary(knn.res)

Summary Method for mknn_graphs Objects

Description

Provides a comprehensive summary of mutual k-nearest neighbor graphs created by create.mknn.graphs, including structural statistics and connectivity information for each k value.

Usage

## S3 method for class 'mknn_graphs'
summary(object, ...)

Arguments

Details

The summary provides insights into how graph structure changes with k:

• Connected Components: Indicates graph fragmentation. A value of 1 means the graph is fully connected.

• Degree Statistics: Shows the distribution of vertex connectivity. Large differences between min and max degree may indicate hub vertices.

• Density/Sparsity: Measures how many of the possible edges are present. MkNN graphs are typically very sparse.

For pruned graphs, the statistics reflect the structure after geometric pruning has been applied.

Value

Invisibly returns a data frame containing graph statistics with columns:

idx

Index of the k value (1 to number of graphs)

k

The k value used for the graph

n_components

Number of connected components

n_edges

Number of edges in the graph

mean_degree

Average vertex degree

min_degree

Minimum vertex degree

max_degree

Maximum vertex degree

density

Graph density (proportion of possible edges present)

sparsity

Graph sparsity (1 - density)

Examples

mknn_result <- list(
  pruned_graphs = list(
    list(adj_list = list(c(2L), c(1L, 3L), c(2L))),
    list(adj_list = list(c(2L, 3L), c(1L, 3L), c(1L, 2L)))
  ),
  k_statistics = data.frame(
    k = 2:3,
    n_edges = c(2L, 3L),
    n_edges_pruned = c(2L, 3L),
    n_removed = c(0L, 0L),
    reduction_ratio = c(0, 0)
  )
)
attr(mknn_result, "kmin") <- 2L
attr(mknn_result, "kmax") <- 3L
attr(mknn_result, "n_vertices") <- 3L
attr(mknn_result, "max.path.edge.ratio.thld") <- 1.2
class(mknn_result) <- "mknn_graphs"

stats <- summary(mknn_result)
plot(stats$k, stats$mean_degree, type = "b",
     xlab = "k", ylab = "Mean Degree")

Summary Method for MST Completion Graph Objects

Description

Computes and returns a comprehensive summary of an MST completion graph, including graph statistics, edge weight distributions, and PCA information if applicable.

Usage

## S3 method for class 'mst_completion_graph'
summary(object, ...)

Arguments

Value

An object of class summary.mst_completion_graph containing:

n_vertices

Number of vertices in the graph

n_mst_edges

Number of edges in the minimal spanning tree

n_cmst_edges

Number of edges in the completed graph

q_thld

Quantile threshold used for completion

edge_weight_summary

Five-number summary of MST edge weights

completion_threshold

The actual distance threshold used

pca_applied

Logical indicating if PCA was applied

pca_info

PCA details (if applicable)

See Also

print.summary.mst_completion_graph for printing summaries, create.cmst.graph for creating graphs

Examples

graph <- list(
  mst_adj_list = list(c(2L), c(1L, 3L), c(2L)),
  mst_weight_list = list(1.1, c(1.1, 0.9), 0.9),
  cmst_adj_list = list(c(2L, 3L), c(1L, 3L), c(1L, 2L)),
  cmst_weight_list = list(c(1.1, 1.4), c(1.1, 0.9), c(1.4, 0.9)),
  mst_edge_weights = c(1.1, 0.9),
  cmst_distance_threshold = 1.08
)
attr(graph, "q_thld") <- 0.8
attr(graph, "cmst_distance_threshold") <- graph$cmst_distance_threshold
class(graph) <- c("mst_completion_graph", "list")

summary(graph)

Summarize an rknn_graphs Object

Description

Provides a compact table of graph characteristics for an "rknn_graphs" object created by create.rknn.graphs() or cpp.create.rknn.graphs(). The table reports final edge counts, component-repair counts, degree summaries, and density/sparsity for each adaptive-radius k.scale value.

Usage

## S3 method for class 'rknn_graphs'
summary(object, ...)

Arguments

Value

Invisibly returns a data frame with one row per graph and columns:

See Also

create.rknn.graphs(), cpp.create.rknn.graphs()

Examples

X <- matrix(c(0, 1, 3, 4), ncol = 1)
graphs <- create.rknn.graphs(
  X,
  kmin = 1,
  kmax = 2,
  radius.search = "all.pairs",
  graph.detail = "minimal",
  prune.method = "none"
)
summary(graphs)

Summary method for vertex_geodesic_stats objects

Description

Summary method for vertex_geodesic_stats objects

Usage

## S3 method for class 'vertex_geodesic_stats'
summary(object, ...)

Arguments

Value

A summary of the vertex geodesic statistics

Examples

x <- data.frame(
  radius = c(0.2, 0.4, 0.6),
  rays = c(3, 5, 6),
  composite_geodesics = c(1, 2, 3),
  overlap_min = c(0.10, 0.15, 0.20),
  overlap_p05 = c(0.15, 0.20, 0.25),
  overlap_p25 = c(0.20, 0.25, 0.30),
  overlap_median = c(0.30, 0.40, 0.50),
  overlap_p75 = c(0.40, 0.50, 0.60),
  overlap_p95 = c(0.55, 0.65, 0.75),
  overlap_max = c(0.60, 0.70, 0.80),
  potential_pairs = c(3, 10, 15),
  composite_ratio = c(1/3, 0.2, 0.2),
  overlap_ratio = c(0.30, 0.40, 0.50)
)
class(x) <- c("vertex_geodesic_stats", "data.frame")
attr(x, "vertex") <- 7L

summary(x)

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

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:

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

Verify Maximal Packing Created by create.maximal.packing

Description

A convenience function to verify the correctness of a maximal packing created using the create.maximal.packing function. This function validates both the packing property (minimum separation distance) and maximality (no vertices can be added).

Usage

verify.maximal.packing(packing.result, verbose = TRUE)

Arguments

Details

This function takes the output of create.maximal.packing and verifies two key properties:

1. The packing vertices are all separated by at least max_packing_radius

2. The packing is maximal (no more vertices can be added without violating the distance constraint)

When \code{verbose = TRUE}, the function prints:
\itemize{
  \item Graph diameter
  \item Packing radius used
  \item Number of vertices in the packing
  \item Minimum distance between packing vertices
  \item Maximum coverage distance
  \item Validity and maximality status
  \item Any violations or potential additions (if applicable)
}

Value

A logical value: TRUE if the packing is both valid (satisfies the distance constraint) and maximal (no vertices can be added), FALSE otherwise.

See Also

create.maximal.packing, validate.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)

verify.maximal.packing(result, verbose = FALSE)

Extract Vertices from a Graph Result

Description

Extract Vertices from a Graph Result

Usage

vertices(object, ...)

Arguments

Value

Object-specific vertex indices.

Prune Long Edges in a Weighted Graph

Description

Prune Long Edges in a Weighted Graph

Usage

wgraph.prune.long.edges(
  graph,
  edge.lengths,
  alt.path.len.ratio.thld,
  use.total.length.constraint = TRUE,
  verbose = FALSE
)

Arguments

Value

A list with pruned adjacency and edge-length lists.