Compute a GRIP layout

This is the primary layout API. It uses the quality-first multiscale GRIP engine with extra coarse-level global repulsion to reduce foldovers while preserving the usual GRIP refinement structure. With preset = NULL, the default profile is tuned for higher-quality layouts and automatically tapers final_rounds on larger graphs.

Usage

grip(
  edges = NULL,
  n = NULL,
  adj_list = NULL,
  weight_list = NULL,
  edge_weights = NULL,
  dim = 3,
  placement = c("barycenter", "circle"),
  preset = NULL,
  rounds = 160,
  final_rounds = 384,
  num_init = 24,
  num_nbrs = 20,
  r = 0.03,
  s = 7.5,
  repulsion_factor = 2.5,
  coarse_repulsion_factor = 1.5,
  coarse_repulsion_sample = 16,
  coarse_repulsion_exact_below = 64,
  final_anchor_factor = 0,
  final_move_scale_after_first = 1,
  final_mode = c("fr", "kk_repulse"),
  insertion_anchor_count = 3,
  insertion_anchor_scope = c("any_higher", "prev_misf"),
  insertion_anchor_strategy = c("first", "distance_band", "balanced_band", "spread_prev"),
  level0_insertion_mode = c("inherit", "barycenter", "least_squares"),
  level0_anchor_count = insertion_anchor_count,
  level0_local_kk_steps = 3,
  lgkk_polish_rounds = 0L,
  lgkk_multiscale_rounds = 0L,
  lgkk_rounds_coarse = NULL,
  lgkk_rounds_pre_final = NULL,
  lgkk_rounds_final = NULL,
  lgkk_local_nbrs = 20L,
  lgkk_landmark_count = 8L,
  lgkk_multiscale_scope = c("all", "coarse"),
  lgkk_active_limit = 4096L,
  tinit_factor = 6,
  seed = 6,
  disconnected = c("components", "error"),
  metric = c("hop", "edge_length"),
  metric_neighbor_cap = NULL,
  length_normalization = c("median", "mean", "none")
)

Arguments

edges

Two-column integer matrix of edges (1-based vertex ids). Supply either edges/edge_weights or adj_list/weight_list, not both. Fractional, nonfinite, and out-of-range vertex ids are rejected before integer conversion.

n

Number of vertices, a finite positive integer.

adj_list

Adjacency list (1-based) for undirected graphs.

weight_list

Parallel list of edge lengths for adj_list. The edge-length-metric engine requires it; in the hop-metric engine, NULL treats all edges as length 1. All supplied lengths must be finite and strictly positive.

edge_weights

Vector of edge lengths for edges, in the same order as its rows. The edge-length-metric engine requires it; in the hop-metric engine, NULL treats all edges as length 1. All supplied lengths must be finite and strictly positive. The selected engine determines whether lengths also define graph distances.

dim

Layout dimension (2 or 3). Default is 3.

placement

Initial placement strategy. "circle" is only used for 2D.

preset

Optional tuning preset. NULL uses the quality-first defaults. "carpet" applies a preset tuned for Sierpinski-carpet-like graphs and validated on carpet levels 3 and 4. "mesh" applies a preset tuned for rectangular lattice graphs and validated on 8x8 and 12x12 mesh layouts. "torus" applies a preset tuned for 3D torus layouts and validated on torus sizes from 8x8 through 20x20. "tree" applies a preset tuned for symmetric force-directed layouts of tree-like graphs and validated on binary trees of depths 5 and 6. Presets only fill in tuning arguments that you did not supply explicitly.

rounds

Initial rounds for refinement.

final_rounds

Final rounds for refinement.

num_init

Number of initial vertices in the coarsest level.

num_nbrs

Maximum number of graph-distance neighbors retained for local refinement at each filtration level.

r

Main local temperature adaptation rate in [0, 1].

s

Non-negative boost factor applied when successive displacements have a consistent direction.

repulsion_factor

Non-negative multiplier applied to GRIP's finest-level repulsive force scale.

coarse_repulsion_factor

Non-negative multiplier applied to the extra coarse-level active-set repulsion term. 0 disables that extra term.

coarse_repulsion_sample

Positive integer sample size used to approximate active-set-wide repulsion on larger coarse levels.

coarse_repulsion_exact_below

Positive integer threshold. When the active set size is at most this value, the coarse repulsion is computed exactly against all currently active vertices instead of being sampled.

final_anchor_factor

Non-negative multiplier for an anchor term that pulls the final FR stage back toward the pre-final full-graph layout. 0 disables the anchor and preserves the current behavior.

final_move_scale_after_first

Scalar in [0, 1] applied to the final FR displacement after the first finest-level round. Values below 1 damp later full-graph movement while keeping the first FR round unchanged.

final_mode

Final full-graph refinement mode. "fr" keeps the current Fruchterman-Reingold-style final stage. "kk_repulse" uses a KK-style local distance-matching update with explicit active-set repulsion instead of the final FR phase.

insertion_anchor_count

Positive integer number of anchor vertices used during multiscale insertion on non-initial MISF refinement levels. This is the closest current implementation to a global K_mish parameter.

insertion_anchor_scope

Anchor-eligibility rule used during multiscale insertion. "any_higher" matches the historical GRIP behavior and allows anchors from any already placed higher MISF level. "prev_misf" restricts anchors to the immediately previous MISF level only.

insertion_anchor_strategy

Anchor-selection rule used during multiscale insertion. "first" keeps the historical first-anchors-found BFS behavior. "distance_band" keeps exploring until the K_mish-th anchor distance band is exhausted, then places the new vertex from that less order-sensitive anchor pool. "balanced_band" uses the same band expansion, then explicitly selects a subset whose centroid stays centered in the candidate cloud while remaining geometrically spread out. "spread_prev" is a symmetry-oriented band strategy intended to be paired with insertion_anchor_scope = "prev_misf"; it selects anchors with broad angular and geometric coverage before placement.

level0_insertion_mode

Level-0 insertion placement override used only when the finest filtration level is first populated. "inherit" keeps the current GRIP behavior. "barycenter" disables the 2D circle heuristic at level 0 and uses barycentric anchor placement. "least_squares" uses a multi-anchor least-squares distance fit at level 0 before any local micro-polish.

level0_anchor_count

Positive integer number of already placed anchors to collect for level-0 insertion experiments. By default this inherits insertion_anchor_count. The legacy behavior uses 3.

level0_local_kk_steps

Non-negative integer number of tiny local KK micro-polish steps applied immediately after each level-0 insertion. The legacy behavior uses 3.

lgkk_polish_rounds

Non-negative integer number of experimental landmark-geodesic KK polish iterations applied after the main GRIP solve. 0 disables the polish.

lgkk_multiscale_rounds

Non-negative integer number of compiled landmark-geodesic KK refinement rounds applied inside the multiscale solver after each eligible MISF level completes its standard GRIP rounds. This legacy shared budget is used as a fallback when any of the more specific per-stage budgets below are left NULL.

lgkk_rounds_coarse

Optional non-negative integer number of compiled LGKK rounds applied on coarse MISF levels with misf_level > 1. When NULL, this falls back to lgkk_multiscale_rounds.

lgkk_rounds_pre_final

Optional non-negative integer number of compiled LGKK rounds applied on the last coarse level just before the full graph is opened (misf_level == 1). When NULL, this falls back to lgkk_multiscale_rounds.

lgkk_rounds_final

Optional non-negative integer number of compiled LGKK rounds applied after the full graph level completes its standard GRIP rounds (misf_level == 0). When NULL, this falls back to lgkk_multiscale_rounds.

lgkk_local_nbrs

Number of nearest graph-metric neighbors retained per vertex in the LGKK sparse local set when either LGKK stage is enabled.

lgkk_landmark_count

Number of farthest-point landmarks retained per vertex in the LGKK sparse long-range set when either LGKK stage is enabled.

lgkk_multiscale_scope

Scope for the compiled multiscale LGKK stage. "all" applies it after every eligible MISF level, including the final full-graph level. "coarse" applies it only on coarse levels.

lgkk_active_limit

Positive integer upper bound on the active-set size for compiled multiscale LGKK cache construction. Levels larger than this skip the multiscale LGKK stage.

tinit_factor

Initial temperature factor.

seed

Optional RNG seed for reproducibility. If NULL, uses current time.

disconnected

How to handle disconnected graphs: "components" (default) lays out each connected component separately and packs them into one coordinate matrix; "error" stops with an error.

metric

Graph metric used by the multiscale GRIP engine. "hop" (default) uses unweighted shortest-path hop counts to build the MISF hierarchy and graph neighborhoods. "edge_length" uses shortest-path distances obtained by summing the supplied positive edge lengths. See Edge-length semantics for the exact role of edge lengths in each mode.

metric_neighbor_cap

Weighted-metric search limit used only when metric = "edge_length". NULL performs the exact weighted neighborhood search and stops once the required neighbors and anchors are filled. A positive integer enables an approximate search by limiting the number of settled vertices per search. It is an error to supply this argument with metric = "hop".

length_normalization

Global normalization applied only when metric = "edge_length": "median" (default) divides every edge length by their median, "mean" divides by their mean, and "none" preserves the supplied numerical scale. It is an error to supply this argument with metric = "hop".

Value

A numeric matrix with n rows and dim columns.

Details

Edge-length semantics

The arguments edge_weights and weight_list are historically named but represent positive edge lengths or traversal costs, not connection strengths, capacities, or similarities. A larger value requests a longer geometric edge. If the available values are strengths for which a larger value means a closer connection, convert them to positive lengths before calling grip(), for example with a scientifically appropriate reciprocal or other monotone decreasing transformation.

With metric = "hop", the standard GRIP hierarchy, insertion anchors, and retained local neighborhoods use combinatorial shortest-path distance: every traversed edge contributes one hop. When edge lengths are supplied, they are nevertheless used as the desired lengths of adjacent vertex pairs in the attractive force calculation. Thus this mode is useful when topology should determine the multiscale organization but adjacent edges should have unequal target lengths. No global length normalization is performed in this mode. If no lengths are supplied, every edge has desired length one. Optional LGKK stages use the supplied edge lengths for their geodesic distances even though the standard GRIP stages remain hop based.

With metric = "edge_length", positive edge lengths are required. The same lengths determine desired adjacent-edge lengths and the shortest-path metric used for the MISF hierarchy, insertion anchors, retained graph neighborhoods, and LGKK stages. Dijkstra-style weighted shortest paths are used instead of hop-count breadth-first searches. By default, all lengths are divided by their median before layout; this preserves relative geometry while placing the numerical scale near the solver's unit scale. Use length_normalization = "mean" for mean scaling or "none" when the absolute supplied scale is intentional. Multiplying all input lengths by the same positive constant therefore leaves the default normalized solve unchanged.

For edges input, provide one value per row through edge_weights. For adj_list input, provide a parallel weight_list: weight_list[[i]][j] is the length of the edge from vertex i to adj_list[[i]][j]. For an undirected graph, the adjacency and length entries should be symmetric.

Workflow guides

Start with vignette("function-guide", package = "grip") to choose a layout, diagnostic, or reference comparison. List installed guides with vignette(package = "grip").

References

Gajer, P. and Kobourov, S.G. (2002). GRIP: Graph dRawing with Intelligent Placement. Journal of Graph Algorithms and Applications, 6(3), 203–224. doi:10.7155/jgaa.00052.

Gajer, P., Goodrich, M.T. and Kobourov, S.G. (2004). A multi-dimensional approach to force-directed layouts of large graphs. Computational Geometry, 29(1), 3–18. doi:10.1016/j.comgeo.2004.03.014.

Examples

edges <- edges.mesh(4, 4)
coords <- grip(edges, n = max(edges), dim = 2,
                      coarse_repulsion_factor = 0.2,
                      coarse_repulsion_sample = 8,
                      coarse_repulsion_exact_below = 32,
                      seed = 1)
round(coords, 3)
#>          [,1]    [,2]
#>  [1,] -10.713  78.890
#>  [2,]  13.068  65.728
#>  [3,]  38.326  50.285
#>  [4,]  60.879  35.116
#>  [5,] -25.881  56.336
#>  [6,]  -1.844  42.112
#>  [7,]  24.101  26.248
#>  [8,]  47.718  11.335
#>  [9,] -41.324  31.079
#> [10,] -17.708  16.166
#> [11,]   8.238   0.302
#> [12,]  32.275 -13.922
#> [13,] -54.486   7.298
#> [14,] -31.932  -7.871
#> [15,]  -6.675 -23.315
#> [16,]  17.106 -36.476

# Use edge lengths throughout the multiscale graph metric.
path <- cbind(1:5, 2:6)
lengths <- c(1, 1, 2, 1, 1)
weighted.coords <- grip(
  path, n = 6, edge_weights = lengths,
  metric = "edge_length", dim = 2,
  rounds = 4, final_rounds = 4, num_init = 3, seed = 1
)