make_lattice vertex ordering/naming

[otoomet]

I want to create a (2D) lattice graph where nodes are names something
like "a11", "a12", "a21", etc where the number correspond to rows and
columns.

I can see that a command

make_lattice(c(3,4))

orders the vertices first according to the first dimension (3) and
thereafter according to the second dimension. This makes it
relatively straightforward to create such names. However:

• this behavior is not documented. Is it part of API? May I rely on
  it?

• For >2 dimensions such approach is more complex. Would it be
  possible to add such a naming scheme to the lattice graphs? I
  imagine igraph uses the row/col/... indices internally when creating
  the lattice, and so it is just a question of attaching the
  corresponding names, or maybe even better, the vertex attributes. In this
  case computing the indices from the vertex order seems just
  unnecessary.

[gaborcsardi]

I don't mind attaching some names, if requested. Do you want to work on a PR for this?

[otoomet]

Hmm... Interesting idea. I cannot commit before I have finished a few other things I promised to do but then I will take a look at the code.

Now I think that attaching numeric vertex attributes might be more useful. In 2D case you could query those by something like V(g)$i, V(g)$j, etc. I don't have an idea how to generalize it to n-dimensional case though.

[szhorvat]

Now igraph_lattice() in the C core guarantees a specific vertex ordering, making this feasible: igraph/igraph#1174

However, IMO, to make this feature truly useful, it should use structured tuples of integers as vertex "names" (or any attribute), so that the position of each vertex in the grid could be immediately determined. The string "a34" has only limited usefulness (basically it's just for plotting / visualization), but the tuple c(3,4) can actually be used for computation. It can also be used for plotting (as vertex coordinates).

The same applies not only to grid/lattice graphs, but a number of other graphs as well, such as De Bruijn graphs, Kautz graphs, and line graphs. Maple does use meaningful vertex names for such graphs, and I plan to do the same in some future version of igraph's Mathematica interface.

Something important to consider is performance: we need to consider if the extra storage required by these attributes will hinder performance when working with very large graphs. Think e.g. a 100 x 100 x 100 x 100 four-dimensional grid graph.

[schochastics]

Implementing this is easy, question is, are we ok with the added runtime and mem space

library(igraph)
vec <- c(100, 100, 100)
bench::mark(
  add_names = {
    grid <- do.call(expand.grid, lapply(vec, seq_len))
    row_strings <- paste0("(", do.call(paste, c(grid, sep = ",")), ")")
  },
  make_lattice = make_lattice(vec), check = FALSE
)
#> Warning: Some expressions had a GC in every iteration; so filtering is
#> disabled.
#> # A tibble: 2 × 6
#>   expression        min   median `itr/sec` mem_alloc `gc/sec`
#>   <bch:expr>   <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl>
#> 1 add_names       451ms    464ms      2.15    80.1MB     2.15
#> 2 make_lattice    512ms    512ms      1.95     272MB     7.82

g <- make_lattice(c(100, 100))
grid <- do.call(expand.grid, lapply(c(100, 100), seq_len))
row_strings <- paste0("(", do.call(paste, c(grid, sep = ",")), ")")
object.size(g)
#> 318992 bytes
V(g)$name <- row_strings
object.size(g)
#> 960560 bytes

^{Created on 2025-07-15 with reprex v2.1.1}

cc @szhorvat

[szhorvat]

There could be an option to disable it, in case people are generating very large graphs? But as I understanding, this just doubles runtime, which is not that bad?

[schochastics]

That's what I would suggested to, add an argument to the function if names should be added or not. I also think that the runtime increase is neglible

[maelle]

With a default set to an option to be documented in igraph_options()?

[schochastics]

I will tackle this in a bigger PR to rework lattices together with #994 probably also #1404 and #1405