Skip to main content

Module triangular_lattice

rust_igraph::algorithms::constructors

Module triangular_lattice 

Source
Expand description

Triangular lattice constructor (ALGO-CN-023).

Counterpart of igraph_triangular_lattice() in references/igraph/src/constructors/lattices.c:290-319.

Builds a planar triangular lattice whose vertices have coordinates (i, j) for non-negative integers and where each (i, j) is connected to (i + 1, j), (i, j + 1), and (i - 1, j + 1) whenever those neighbours exist on the lattice. Every vertex thus has degree at most six, and the graph is the planar dual of the hexagonal lattice over the same dims.

The dims slice doubles as a shape selector with three modes:

  • [n] — triangle with side length n
  • [size_x, size_y] — quasi-rectangle, size_x rows of size_y vertices each
  • [size_x, size_y, size_z] — hexagon with side lengths size_x, size_y, size_z

Vertices are numbered lexicographically with the second coordinate more significant (the C lex_ordering = false path), matching the upstream library.

Modes:

  • directed = false: every undirected lattice edge is emitted once with the lower vertex id as the source.
  • directed = true, mutual = false: each lattice edge becomes a single arc oriented from the lower vertex id to the higher.
  • directed = true, mutual = true: every undirected lattice edge becomes a pair of opposite arcs (the canonical orientation plus its reverse), matching the C ADD_EDGE_IJ_KL_IF_EXISTS macro’s double push.

Special cases:

  • dims = [] and dims = [...] with any zero component both collapse to the empty graph (vcount = 0), matching the upstream “if vector_int_contains(dims, 0) return igraph_empty” guard.
  • dims.len() != 1, 2, 3 is rejected with IgraphError::InvalidArgument.

Algorithm: build per-row row_lengths and row_start arrays from the requested shape, then walk every lattice vertex and emit the three canonical “forward” neighbours that fall inside the lattice. Boundary checks reproduce the upstream ADD_EDGE_IJ_KL_IF_EXISTS macro byte-for-byte. The vertex index for (i, j) is prefix_sum[j] + (i - row_start[j]).

Time complexity: O(|V| + |E|).

Functions§

triangular_lattice
Build a triangular lattice with the requested shape.