Package 'dgraphs'

Description

Construct and analyze graphs derived from numerical observations.

Start here

• Finding your way around dgraphs: a task-oriented catalog of public functions and object methods.

• Synthetic geometry and point sampling: reproducible curves, surfaces, embeddings and graph examples.

• Constructing and Diagnosing Data-Derived Graphs: graph-family comparisons, connectivity repair and diagnostics.

These links open installed HTML guides. From the console, use vignette("function-guide", package = "dgraphs") or vignette("synthetic-geometry", package = "dgraphs").

Author(s)

Maintainer: Pawel Gajer [email protected]

Authors:

• Pawel Gajer [email protected]

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]

• Danil Kirsanov (Polyhedral geodesic library) [contributor, copyright holder]

See Also

create.graph(), create.sknn.graph(), create.rknn.graph(), graph.geodesic.distances(), create.path.graph(), plot.dgraph(), sample.synthetic.geometry()

Examples

graph <- create.graph("chain", n = 5)
print(graph)
graph.geodesic.distances(graph, vertices = c(1, 5))
# The endpoint distance is four unit-length edges.

Description

Convert a dgraph to igraph

Usage

as_igraph(graph, stage = "final")

Arguments

Value

An undirected igraph. Edge lengths are named length; other attributes retain their names. No implicit weight or unit lengths are added. For metric paths pass weights = igraph::E(g)$length explicitly; for hop distance pass weights = NA.

Examples

graph <- dgraph(list(2L, 1L, integer()), list(0, 0, numeric()))
ig <- as_igraph(graph)
igraph::vcount(ig)
igraph::E(ig)$length

Description

Compile the pinned IAN and Clarabel sources installed with dgraphs in a new directory. The supported build target is macOS arm64. Setup requires Python 3, Apple's C++ compiler/SDK, and matching native Cargo/Rust tools (Rust >= 1.77). An initial build needs cached crates or network access. No tools are installed by this function. Compilation is explicit and never starts inside create.ian.graph() or ordinary package installation.

Usage

build.ian.backend(
  build.dir,
  python = "python3",
  cargo = "cargo",
  rustc = "rustc",
  cxx = "clang++",
  offline = FALSE
)

Arguments

Value

The absolute path to dgraphs_ian.so, invisibly. Save this path and pass it to create.ian.graph(..., backend = path). Reuse the built module with the same R installation; rebuild when changing R runtime or backend sources. Build errors retain available logs and raise an R error. No shared package library is modified. Build records identify source files and tool commands.

See Also

create.ian.graph()

Examples

## Not run: 
backend <- build.ian.backend("ian-build")
fit <- create.ian.graph(matrix(c(0, 1, 2), ncol = 1), backend = backend)
stopifnot(fit$complete)

## End(Not run)

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,
  k.values,
  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,
  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.

Examples

set.seed(1)
x <- matrix(rnorm(60), ncol = 2)
selected <- build.iknn.graphs.and.selectk(x, k.values = seq.int(2, 4),
    method = "edit",
    verbose = FALSE)
selected$k.opt.edit

Description

Compare Two Adjacency Lists

Usage

compare.adj.lists(adj.list1, adj.list2, verbose = FALSE)

Arguments

Value

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

Examples

graph <- list(c(2L, 3L), 1L, 1L)
compare.adj.lists(graph, list(c(3L, 2L), 1L, 1L))

Description

Compare Paths Across Hop Limits

Usage

compare.paths(path.result, from, to)

Arguments

Value

Data frame describing path availability and length by hop limit.

Examples

graph <- list(2L, c(1L, 3L), 2L)
lengths <- list(1, c(1, 2), 2)
series <- create.path.graph(dgraph(graph, lengths), h.values = 1:2)
compare.paths(series, from = 1, to = 3)

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

Examples

graph <- create.graph("circle", n = 8, sampling = "uniform")
stats <- compute.geodesic.stats(graph.adjacency(graph), graph.lengths(graph), min.radius = 0.3,
    max.radius = 0.5, n.steps = 2, n.packing.vertices = 4)
stats$summary

Description

Compute a Weighted Graph Diameter

Usage

compute.graph.diameter(graph, stage = "final")

Arguments

Value

A list containing the diameter and the farthest path details.

Examples

graph <- list(2L, c(1L, 3L), 2L)
weights <- list(1, c(1, 2), 2)
compute.graph.diameter(dgraph(graph, weights))$diameter

Description

Compute a Weighted Shortest-Path Distance

Usage

compute.graph.distance(graph, i, j, stage = "final")

Arguments

Value

Numeric shortest-path distance.

Examples

graph <- list(2L, c(1L, 3L), 2L)
weights <- list(1, c(1, 2), 2)
compute.graph.distance(i = 1, j = 3, graph = dgraph(graph, weights))

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

Examples

chain <- create.graph("chain", n = 8)
layout <- cbind(seq_len(8), 0, 0)
scores <- compute.graph.endpoint.scores(graph.adjacency(chain), graph.lengths(chain), layout,
    k = c(2, 3), min.neighborhood.size = 2)
head(scores$summary)

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,
  edge.attribute = "length",
  stage = "final",
  bins = NULL,
  n.bins = 20L,
  bin.method = c("auto", "fixed_width", "fixed_quantile", "explicit"),
  normalize = TRUE,
  support = NULL,
  zero.pad = TRUE,
  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.

Examples

graph <- dgraph(list(c(2L, 3L), 1L, 1L))
compute.graph.summary.pmf(graph, summary = "degree_distribution")

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.

Examples

graphs <- list(
  dgraph(list(2L, c(1L, 3L), 2L)),
  dgraph(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))),
  create.graph("complete", 3)
)
compute.graph.summary.stability(
  graphs,
  summary = "degree_distribution"
)$values

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

Examples

set.seed(1)
x <- matrix(rnorm(60), ncol = 2)
graphs <- create.iknn.graphs(x, k.values = seq.int(2, 4), compute.full = TRUE,
    verbose = FALSE)
stability <- compute.stability.metrics(graphs)
stability$edit.distances

Description

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

Usage

compute.vertex.geodesic.stats(
  adj.list,
  length.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.

Examples

graph <- create.graph("circle", n = 8, sampling = "uniform")
compute.vertex.geodesic.stats(graph.adjacency(graph), graph.lengths(graph),
    grid.vertex = 1, min.radius = 0.3,
    max.radius = 0.5, n.steps = 2)

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.

Examples

graph <- list(c(2L, 3L), 1L, 1L)
weights <- list(c(1, 2), 1, 2)
convert.adjacency.list.to.adjacency.matrix(graph, weights)

Description

Convert an Adjacency List to an Edge Matrix

Usage

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

Arguments

Value

A list with edge.matrix and weights.

Examples

graph <- list(c(2L, 3L), 1L, 1L)
convert.adjacency.to.edge.matrix(graph)

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.

Examples

directed <- list(2L, integer(0), 1L)
convert.to.undirected(directed)

Description

Convert a Weighted Adjacency Matrix to Lists

Usage

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

Arguments

Value

A list with adj.list and weight.list.

Examples

A <- matrix(c(0, 1, 0, 1, 0, 2, 0, 2, 0), nrow = 3)
convert.weighted.adjacency.matrix.to.adjacency.list(A)

Description

Count Edges in an Undirected Adjacency List

Usage

count.edges(adj.list)

Arguments

Value

Number of undirected edges.

Examples

count.edges(list(c(2L, 3L), 1L, 1L))

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)
as.matrix(graph.edges(create.cknn.graph(X, k.scale = 1, delta = 1))[, c("from", "to")])

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

A dgraph with raw (MST) and final (completed) stages. Use graph accessors to inspect topology and lengths; construction details are in metadata.

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.order(graph)
nrow(graph.edges(graph))

Description

Each cover contains its source vertex plus its k nearest other vertices. Equal distances are resolved by ascending vertex index. Intersecting covers create edges whose lengths are shortest-path distances in the input graph.

Usage

create.geodesic.iknn.graph(graph, k, small.component = c("error", "truncate"))

Arguments

Value

A dgraph with a final stage, lengths and an overlap edge attribute. metadata$neighborhood records requested and effective sizes and the tie rule.

Examples

graph <- create.graph("chain", 3)
create.geodesic.iknn.graph(graph, k = 1)

Description

Construct a standard topology or a simple geometric graph. All types return a dgraph() and use compact, 1-based adjacency indices. type is required; type names and names in ... must match exactly.

Usage

create.graph(type, n = NULL, ..., labels = NULL)

Arguments

Value

A dgraph with one final stage and construction information in metadata, including type. Inspect it with graph.adjacency(), graph.lengths(), graph.edges() and graph.order().

Types and arguments

empty, complete, cycle

Only n and labels. These return topology without stored lengths. A cycle closes a chain with one edge.

chain

span = 1 connects up to span positions on each side, giving at most 2 * span neighbors. It must be an integer from 1 to n - 1; it does not use the nearest-neighbor meaning of k. Optional finite numeric x orders vertices by coordinate (ties by input position) and supplies absolute coordinate differences as lengths. Without x, lengths are one. Optional vector y requires x and is reordered with it. Metadata contains order (sorted-to-input indices), x.sorted and y.sorted.

complete_bipartite

Required sizes, two positive integers. All pairs across the two parts are connected; there are no within-part edges or stored lengths. Vertices in the first part come first.

star

Required arms, at least two positive integer edge counts. Chains of those lengths share vertex 1 as their center. Thus n = 1 + sum(arms); all-one arms give an ordinary star. Vertices are numbered along successive arms. No lengths are stored.

circle

sampling = "uniform" or "random" (default), edge.length = "arc" (default) or "chord", and optional seed. Vertices are ordered by angle on the unit circle and consecutive vertices, including last-to-first, are connected. Arc lengths measure the shorter unit-circle arc between endpoints, even when the gap in the sampling order exceeds pi. Chords are Euclidean distances. Metadata contains angles (radians) and coordinates (x/y columns).

random

Required finite mean.degree, connected = TRUE, and optional seed. The edge count is floor(n * mean.degree / 2); ⁠0 <= mean.degree <= n - 1⁠. If connected, this count must be at least n - 1. A randomly ordered growing tree is built first, then a uniform subset of remaining pairs is added. This is not uniform sampling over connected graphs or spanning trees. If disconnected graphs are allowed, a uniform subset of all pairs is sampled. Each undirected edge receives one independent length uniform between 0.5 and 1.5. Candidate-pair storage is quadratic in n; this constructor is intended for small examples. Metadata records requested and realized mean degrees and connectivity.

Random numbers

For random and circle, seed = NULL uses and advances the caller's current random stream. An explicit nonnegative integer seed makes the call reproducible under the current RNG kind and restores the caller's RNG state afterwards, including an initially absent state. Uniform circle sampling consumes no random numbers. The richer geometry sampling API has its own seed/state continuation contract; see sample.synthetic.geometry().

Examples

graph.order(create.graph("empty", n = 4))
graph.edges(create.graph("complete", n = 3))
chain <- create.graph("chain", x = c(3, 1, 2), span = 1,
                      labels = c("third", "first", "second"))
graph.adjacency(chain)
graph.lengths(chain)
graph.edges(create.graph("cycle", n = 4))
graph.order(create.graph("complete_bipartite", sizes = c(2, 3)))
graph.order(create.graph("star", arms = c(2, 3, 1)))
graph.edges(create.graph("random", n = 6, mean.degree = 2, seed = 10))
circle <- create.graph("circle", n = 8, sampling = "uniform",
                       edge.length = "chord")
circle$metadata$coordinates

Description

Create a Refined Graph with Approximately Uniform Edge Spacing

Usage

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

Arguments

Value

A dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

Examples

chain <- create.graph("chain", n = 3)
grid <- create.grid.graph(graph.adjacency(chain), graph.lengths(chain), grid.size = 5)
grid$metadata$grid_vertices

Description

Construct the initial Gabriel graph, adapt local scales and prune edges, returning graphs, affinities and diagnostics. By default, proposed bridge edges are protected so that pruning retains connectivity, and the audited retry-power numerical policy permits one checked retry after an eligible solver rejection. These are explicit variants of reference IAN.

Usage

create.ian.graph(
  X,
  distances = NULL,
  specimen.ids = NULL,
  participant.ids = NULL,
  graph = NULL,
  diagnostics = c("summary", "full"),
  backend = NULL,
  max.solves = 10000L,
  numerical.policy = "IAN evaluated-LP retry-power 0.1",
  preserve.connectivity = TRUE
)

Arguments

Details

Build the optional module once with build.ian.backend() and pass its returned path as backend. The supported build target is macOS arm64. The function itself does not compile code, download dependencies or launch an external solver. See system.file("ian", "README.md", package = "dgraphs") for the numerical contract, setup requirements and bounded qualification.

Input rows are specimens; graph vertices are unique feature profiles in first-occurrence order. Always check complete before using final_graph. Invalid R arguments or an unavailable backend raise an R error. Numerical refusal and interruption during engine execution return an incomplete result with the available diagnostics. Memory exhaustion or process termination is not a recoverable-result guarantee.

The default numerical policy is ⁠IAN evaluated-LP retry-power 0.1⁠. A rejected original return remains rejected. Its single eligible retry must itself pass strict solver success and the unchanged original-unit checks. numerical.policy="IAN evaluated-LP 1.0" together with preserve.connectivity=FALSE selects the previous strict/reference behavior. This public default adoption changes neither policy's implementation.

The returned top-level fields are complete, error, initial_graph, final_graph, last_valid_graph, mapping, scales, affinity, diagnostics and backend. Graphs are dgraph() objects with metric edge lengths in input distance units; affinity values are separate similarities. Mapping contains one-based representatives and member_to_profile, plus specimen, profile and participant IDs. Repeated participant IDs do not merge specimens. Error information contains kind, code and message. diagnostics$solver_history retains both accepted and rejected attempts. Backend information identifies the selected policies, source and settings. Checkpoint/resume is not exposed through this R interface.

Value

A list with complete, structured error, initial Gabriel graph, final_graph only on full completion, last_valid_graph (possibly partial), profile mapping, local scales and an affinity matrix distinct from metric edge lengths. Graph indices and mappings are one-based. Full traces retain original zero-based core indices and declare this in diagnostics. Summary diagnostics include per-solve status, acceptance, settings, residuals and iteration counts. Refusal and interruption return incomplete structured results; invalid R arguments error before native execution. Interrupts are checked at engine events; they do not interrupt an active solver call. In connectivity mode, diagnostics$connectivity contains protected.edges (one-based profile rows and IDs, first/last encounter iteration, count and first statistic), per-iteration history, and stop.reason. Iterations in this summary are one-based. Protected edges are encountered proposals, not necessarily edges that would pass the pruning criteria. Full traces also include every edge proposal and whether eligibility was tested. A complete pass with no deletion stops, including when statistical candidates remain protected. Partial results retain available protection diagnostics; final_graph remains NULL if later optimization or affinity construction fails.

See Also

build.ian.backend()

Examples

# Set this variable to the path returned by build.ian.backend().
backend <- Sys.getenv("DGRAPHS_IAN_BACKEND")
if (nzchar(backend) && file.exists(backend)) {
  X <- rbind(c(0, 0), c(1, 0), c(2, 0), c(0, 0))
  fit <- create.ian.graph(X, backend = backend,
      specimen.ids = c("alpha", "beta", "gamma", "delta"))
  stopifnot(fit$complete)
  graph.edges(fit$initial_graph)
  graph.edges(fit$final_graph)
  fit$mapping$member_to_profile # Four specimens, three unique profiles.
  fit$diagnostics$connectivity$protected.edges
}

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,
  k.values,
  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),
  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, k.values = seq.int(3, 10), compute.full = FALSE)

# With custom pruning parameters
res2 <- create.iknn.graphs(X, k.values = seq.int(3, 10),
    max.path.edge.ratio.deviation.thld = 0.1,
    path.edge.ratio.percentile = 0.5, compute.full = TRUE, verbose = TRUE)

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

Description

Constructs G0 with create.iknn.graphs(), then constructs G1, G2, ..., Gm by repeatedly applying create.geodesic.iknn.graph() to each graph in the k.values 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,
  k.values,
  n.iterations = 3L,
  small.component = c("error", "truncate"),
  max.path.edge.ratio.deviation.thld = 0,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  pca.dim = 100,
  variance.explained = 0.99,
  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 k.values.

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, k.values = seq.int(2, 3), n.iterations = 1,
    verbose = FALSE)
out$summary

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,
  length.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 maximal_packing result containing its graph (a dgraph), grid_vertices (packing indices), graph_diameter, and max_packing_radius (the guaranteed separation of packing vertices).

See Also

validate.maximal.packing, verify.maximal.packing

Examples

adj.list <- list(c(2), c(1, 3), c(2, 4), c(3, 5), c(4))
length.list <- list(c(1), c(1, 1), c(1, 1), c(1, 1), c(1))

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

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.

Use graph accessors for the final graph and graph.stages() to list stored raw, pruned and repaired stages. Construction details are in metadata.

Value

A dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

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.order(graph)
nrow(graph.edges(graph))
graph.adjacency(graph)[[1]]

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,
  k.values,
  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:

• k.values: The requested neighborhood sizes

• 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, k.values = seq.int(3, 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, k.values = seq.int(2, 3), pca.dim = 3, verbose = FALSE)
attr(result.pca, "pca")$n_components

Description

Find minimum-length routes using at most each requested number of edges. Equal-length routes prefer fewer hops. One route is stored per unordered pair and can be retrieved in either direction with get.shortest.path().

Usage

create.path.graph(graph, h.values, stage = "final")

Arguments

Details

Hop-constrained search retains a separate distance for each hop count, then selects the best route for each pair. With nonnegative lengths, limits above n - 1 need no additional search. For each source, auxiliary storage is proportional to n * min(h, n - 1); storing routes for all reachable pairs can require cubic space. Use small hop limits when possible.

Value

A named path.graph.series collection, even for one limit. Names are h_2, h_4, etc. Each member is a path.graph with a graph of reachable pairs, stored shortest.paths, and an h attribute recording the requested limit. Its graph stores route lengths and a hops edge attribute. Routes use the input graph's vertex indices. Empty graphs and isolated vertices are preserved.

Examples

graph <- create.graph("chain", n = 5)
paths <- create.path.graph(graph, h.values = c(2, 4))
get.shortest.path(paths[["h_4"]], from = 1, to = 5)
get.shortest.path(paths[["h_4"]], from = 5, to = 1)
compare.paths(paths, from = 1, to = 5)

Description

Create a Path Length Matrix Graph Structure

Usage

create.plm.graph(adj.list, length.list, h)

Arguments

Value

An object of class path.graph.plm.

Examples

graph <- list(2L, c(1L, 3L), 2L)
lengths <- list(1, c(1, 2), 2)
create.plm.graph(graph, lengths, h = 3)

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

A dgraph, with constructor class radius_graph for fixed radii or adaptive_radius_graph for adaptive radii. Use graph accessors for topology, lengths and retained stages; construction diagnostics are in metadata.

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
as.matrix(graph.edges(create.rknn.graph(X, type = "fixed", radius = 1.1))[, c("from", "to")])
as.matrix(graph.edges(create.rknn.graph(X, type = "adaptive.radius", k.scale = 1))[, c("from",
"to")])

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, k.values, ..., 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 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, k.values = seq.int(1, 2), radius.search = "all.pairs",
    graph.detail = "minimal",
    prune.method = "none")
names(result$graphs)
result$k_statistics

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

The default accessors inspect the final graph. Use stage = "raw" or stage = "pruned" to inspect earlier stages. graph.stages() reports which repaired branches are retained; a missing stage is an error.

Value

A dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

Examples

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

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,
  knn.index = NULL,
  graph.detail = c("full", "minimal"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2,
  input.type = c("observations", "distances")
)

Arguments

Details

With input.type = "distances", supplied distances determine exact neighbor rankings, every edge length, and component/global MST repair. Distance input must be finite, nonnegative, square and symmetric, with a zero diagonal. Symmetry and diagonal tolerance is 1e-12 * max(1, max(X)); accepted asymmetry is averaged and the diagonal set to zero. Row and column names, if present, must be identical and unique. Off-diagonal zeros are allowed. Triangle inequality is not tested, so symmetric dissimilarities are accepted. Ties are resolved by increasing vertex index, excluding self explicitly. ANN search/repair and pruning are unsupported for distance input and error. The series constructor validates distances and ranks neighbors once, through its largest requested k. Full lifecycle stages use these same distances.

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 dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

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$metadata$n_components_before
g$metadata$n_components_after
g$metadata$mst_edge_matrix

Description

Constructs symmetric k-nearest neighbor graphs for several values of k while performing one bundled ANN search for observations, or one exact ranking of supplied distances, at the largest requested value. The ordered non-self neighbor matrix is sliced for each graph, so lower-k graphs use exactly the same neighbor ranking as the largest graph.

Usage

create.sknn.graphs(
  X,
  k.values,
  ...,
  input.type = c("observations", "distances")
)

Arguments

Value

A list of class "sknn_graphs" with components graphs, a named list of "sknn_graph" objects, and k_statistics, a data frame of edge and component counts. Attributes record the requested values and number of vertices.

See Also

create.sknn.graph()

Examples

set.seed(1)
X <- matrix(rnorm(60), ncol = 3)
graphs <- create.sknn.graphs(
  X,
  k.values = c(2, 4),
  graph.detail = "minimal"
)
graphs$k_statistics

Description

Extract an Induced Subgraph

Usage

create.subgraph(graph, vertices, stage = "final")

Arguments

Value

A dgraph with compact indices and aligned lengths and attributes. metadata$original.vertices maps its vertices back to the original graph.

Examples

graph <- create.graph("chain", 4)
sub <- create.subgraph(graph, vertices = c(4, 3))
graph.edges(sub)
sub$metadata$original.vertices

Description

Create a Threshold Distance Graph

Usage

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

Arguments

Value

A dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

Examples

distances <- as.matrix(dist(matrix(c(0, 1, 3), ncol = 1)))
create.threshold.distance.graph(distances, threshold = 1.5)

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

Examples

chain <- create.graph("chain", n = 8)
layout <- cbind(seq_len(8), 0, 0)
endpoints <- detect.graph.endpoints(graph.adjacency(chain), graph.lengths(chain),
    layout, k = c(2,
    3), min.neighborhood.size = 2, detect.max.radius = 2, detect.min.neighborhood.size = 2,
    min.score.quantile = 0.5)
endpoints$endpoints

Description

Detect Local Extrema in a Graph

Usage

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

Arguments

Details

Summaries use the recorded detection setting for empty results. Empty objects saved by older versions lack this setting; their summaries report NA for the extrema type because it cannot be recovered from empty vectors.

Value

A local_extrema object. Its scalar logical detect.maxima component records whether maxima or minima were requested, even when no extrema are found. The per-extremum is_maxima and type vectors are empty in that case.

Examples

chain <- create.graph("chain", n = 5)
extrema <- detect.local.extrema(graph.adjacency(chain), graph.lengths(chain), y = c(1, 3, 1, 2,
    0), max.radius = 1, min.neighborhood.size = 2)
extrema$vertices

Description

A dgraph stores an undirected simple graph, including isolated vertices. Adjacency, lengths and scalar edge attributes are validated together and sorted together. Zero lengths are edges; absent lengths remain NULL.

Usage

dgraph(adj.list, length.list = NULL, edge.attributes = list())

graph.adjacency(graph, stage = "final")

graph.lengths(graph, stage = "final")

graph.order(graph)

graph.stages(graph)

graph.edge.attribute(graph, name, stage = "final")

graph.edges(graph, stage = "final")

Arguments

Value

dgraph() returns a graph. The accessors return adjacency lists, length lists (or NULL), an ordered edge data frame, the vertex count, stage names, or the requested attribute list, respectively. Edge tables contain integer from < to, optional numeric length, and attributes.

Examples

graph <- dgraph(list(c(3L, 2L), 1L, 1L, integer()),
                list(c(0, 2), 2, 0, numeric()))
graph.order(graph)
graph.edges(graph)
graph.stages(graph)
graph.adjacency(graph)
graph.lengths(graph)

Description

Compute Edge Difference Between Two Graphs

Usage

edge.diff(adj.list1, adj.list2)

Arguments

Value

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

Examples

graph1 <- list(c(2L, 3L), 1L, 1L)
graph2 <- list(2L, 1L, integer(0))
edge.diff(graph1, graph2)

Description

For quadforms this integrates the induced metric along each straight latent segment. Flat quadforms reduce exactly to Euclidean distance.

Usage

edge.lengths.synthetic.geometry(geometry, from, to, tolerance = 1e-10)

Arguments

Value

A numeric vector of segment lengths.

Examples

geometry <- synthetic.quadform(1L, 1L)
edge.lengths.synthetic.geometry(geometry, matrix(0), matrix(2))

Description

Lift coordinates onto a quadratic surface using Geometry Lab arithmetic

Usage

embed.quadform.surface(latent, coefficients)

Arguments

Value

A three-column matrix. Version-1 arithmetic preserves existing Geometry Lab cloud identities and reference meshes.

Examples

embed.quadform.surface(matrix(c(0, 1, 0, 1), ncol = 2), c(1, 0, -1))

Description

This deterministic operator performs no random draws. A realized frame.matrix is required for random-frame geometries.

Usage

embed.synthetic.geometry(geometry, latent, frame.matrix = NULL)

Arguments

Value

A numeric matrix of observed coordinates.

Examples

geometry <- synthetic.circle()
embed.synthetic.geometry(geometry, matrix(c(0, pi / 2), ncol = 1))

Description

Explore saved data-geodesic graph reconstruction benchmarks using manual graph selection, metric-based selection, saved layouts and parameter scans. This is the maintained replacement for the dggraphui application.

Usage

explore.graphs(
  project = NULL,
  launch = TRUE,
  host = "127.0.0.1",
  port = getOption("shiny.port"),
  launch.browser = interactive(),
  ...
)

Arguments

Details

The optional packages shiny, bslib, plotly and digest are required only for the explorer. The optional grip package is needed only when explicitly generating a missing weighted layout. Opening a project reads saved results; it does not reconstruct graphs, fit layouts or overwrite benchmark assets. Newly generated layouts are stored in a separate dgraphs user cache.

Project registration stores locations in the user's dgraphs data directory, outside the installed package. Set options(dgraphs.projects_dir = ...) to choose another catalog directory. Set options(dgraphs.graph_explorer_cache_dir = ...) to choose the layout cache.

The default display preserves original coordinates and equal x/y/z units. Optional centering with a single scale factor preserves proportions. Per-axis normalization is labeled as distorting proportions. The displayed edge count discloses thinning above 4000 edges; saved metrics always use the complete graph and are never recomputed by display controls.

Choose Open circle demo in the app, or use the installed project below. Its two chord-weighted graphs use 12 equally spaced unit-circle points. Increasing k from 2 to 4 introduces shortcuts relative to exact shorter circle arcs. Layouts and metrics are already saved; no fitting is needed.

Value

When launch = FALSE, a shiny.appobj; otherwise the result of shiny::runApp(), invisibly.

See Also

read.graph.benchmark(), register.graph.project()

Examples

if (interactive() && all(vapply(c("shiny", "bslib", "plotly", "digest"),
                               requireNamespace, logical(1), quietly = TRUE))) {
    demo <- system.file("extdata", "graph-explorer-demo", package = "dgraphs")
    explore.graphs(demo)
}

Description

Extract Edge Lengths Along a Graph Path

Usage

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

Arguments

Value

Data frame with consecutive vertex pairs and their edge lengths.

Examples

graph <- list(2L, c(1L, 3L), 2L)
lengths <- list(1, c(1, 2), 2)
extract.trajectory.edge.lengths(c(1, 2, 3), graph, lengths)

Description

Minimize sums of powered edge lengths. Coordinate input defaults to the complete Euclidean graph, implementing the sample Fermat distance on the observed points. A symmetric kNN restriction or a supplied graph is an explicit alternative, with no automatic guarantee of the same distances.

Usage

fermat.distances(
  graph = NULL,
  p = 2,
  rooted = FALSE,
  vertices = NULL,
  stage = "final",
  points = NULL,
  graph.type = NULL,
  k = NULL,
  backend = "explicit",
  sources = NULL,
  targets = NULL,
  max.workspace.bytes = 512 * 1024^2,
  return.graph = FALSE
)

Arguments

Details

For base lengths $l_e$, the unrooted result is $\min_\pi \sum_{e\in\pi} l_e^p$. At p = 1, complete-graph coordinate distances are Euclidean; restricted distances are ordinary graph distances. Restricting edges cannot decrease the result when retained weights agree. Taking k = n - 1 recovers the complete graph.

Groisman, Jonckheere and Sapienza define the unrooted complete-graph estimator and prove consistency after sample-size normalization under their sampling assumptions. Their Proposition 2.12 establishes a high-probability equality for a sufficiently large nearest-neighbor restriction under its stated assumptions. It does not certify arbitrary fixed k, pruned graphs, or arbitrary supplied lengths. This function applies neither sample-size normalization nor an estimated limit constant.

Both coordinate constructions evaluate all Euclidean pairs. Explicit complete graphs store quadratic adjacency. The implicit backend uses dense Dijkstra searches with linear scratch and no graph restriction: with h sources, n observations and d coordinates its worst-case time is O(hn^2d). A global numeric-range check takes O(n^2d) time. Pivot-to-all output uses O(hn) storage; full all-pairs output is still quadratic. Select pivots outside this function; no automatic pivot sampling or distance approximation is performed. Distances are computed in floating-point arithmetic. Overflow, positive powered lengths underflowing to zero, and a conservative upper bound on simple-path cost exceeding the numeric range cause errors; rescale base lengths before retrying. Multiplying lengths by a > 0 multiplies unrooted distances by a^p (rooted distances by a).

With return.graph = TRUE, one deterministic shortest-path tree is selected per source (ties need not include every minimizing path). Only paths to the requested targets contribute edges. The returned graph retains all input vertices, including unused isolated vertices. Its edge lengths are powered base lengths even when the returned distances are rooted. Thus graph geodesics reproduce the unrooted requested distances. With all sources and targets it preserves every pair; a subset guarantees only the requested pairs. The union need not be sparse. The implicit workspace estimate includes a conservative allowance for the predecessor-edge union when requested.

Value

Numeric square distance matrix, or a source-by-target matrix when sources is supplied, in requested order. Unreachable pairs are Inf. Zero-length edges are retained; duplicate points have zero distance. Point row names or graph adjacency names label the matrix. With return.graph = TRUE, return a list containing distances (this matrix), graph (a dgraph with powered base edge lengths), and metadata. Metadata records sources, targets, coverage (all_pairs or requested_pairs), p, rooted, edge.weight.type, and the backend used. Graph distances are unrooted even when the returned matrix is rooted.

References

Groisman, P., Jonckheere, M. and Sapienza, F. (2022). Nonhomogeneous Euclidean first-passage percolation and distance learning. Bernoulli, 28(1), 255–276. doi:10.3150/21-BEJ1341. See Definitions 2.1 and 2.11 and Proposition 2.12 in https://arxiv.org/html/1810.09398v2.

See Also

graph.geodesic.distances(), create.sknn.graph()

Examples

X <- matrix(c(0, 1, 2), ncol = 1)
fermat.distances(points = X, p = 2) # 0 -> 1 -> 2 costs 2, not 4
fermat.distances(points = X, p = 2, rooted = TRUE)
fermat.distances(points = X, graph.type = "sknn", k = 1)
g <- dgraph(list(2L, c(1L, 3L), 2L), list(1, c(1, 1), 1))
fermat.distances(g, vertices = c(1, 3))