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: https://github.com/igraph/igraph/issues/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.