Node

Let $~g_{i^1i^2~\cdots~i^{D}} = (s_{i^1}, s_{i^2}, ..., s_{i^{D}})$ be a $D$-node or simply a node or vertex of a $D$-grid. It can be described as a tuple where :

$$g_{i^1i^2~\cdots~i^{D}} = (s_{i^1}, s_{i^2}, ..., s_{i^{D}} ) ~~|~~ s_{i^j} \in S_j ~~,~~ i^j \in [1,N_j]$$

Here we use the notation $s_{i^j}$ instead of $s_i^j$ because it is more convenient. The total number of nodes in the grid, which is also the cardinality of $G$, is given by :

$$N = card(G) = N_2 \times N_2 \times \cdots \times N_{D}$$

Labeling

As suggested by the employed notation, nodes can simply be identified by stacking together the indexes of the values taken by each parameter. Thus, a node has a unique tuple "address" in the grid : $${i^1i^2~\cdots~i^{D}} \Leftrightarrow (i^1,i^2,\cdots,i^{D})$$

Numbering

However, there is exactly $N!$ different ways to order a finite set of $N$ nodes : $$i^j \in [1,N^j] \longrightarrow \sigma_k^j(i) \in [1,N^j] ~~,~~ j \in [1,D]$$

Where $\sigma_k^j$ is the $k^{th}$ permutation function (in a total of $N^j!$) over the set $S_j$.

Fore sure, not all ways of numbering this nodes are made equals in terms of convenience, especially when it comes to construct grid's cells from their corner nodes. The proposed numbering is the following :

$$\begin{array}{c|ccccc} Index & i^1 & i^1 & i^2 & \cdots & i^{D} \\ \hline 1 & 1 & 1 & 1 & \cdots & 1 \\ 2 & 2 & 1 & 1 & \cdots & 1 \\ 3 & 3 & 1 & 1 & \cdots & 1 \\ & \vdots & \vdots & \vdots & & \vdots \\ N_1 & N_1 & 1 & 1 & \cdots & 1 \\ \hline +1 & 1 & 2 & 1 & \cdots & 1 \\ +2 & 1 & 2 & 1 & \cdots & 1 \\ +3 & 1 & 2 & 1 & \cdots & 1 \\ & \vdots & \vdots & \vdots & & \vdots \\ 2 N_1 & N_1 & 2 & 1 & \cdots & 1 \\ \hline & \vdots & \vdots & \vdots & & \vdots \\ (N_2-1) N_1 & N_1 & N_2-1 & 1 & \cdots & 1 \\ \hline +1 & 1 & N_2 & 1 & \cdots & 1 \\ +2 & 2 & N_2 & 1 & \cdots & 1 \\ +3 & 3 & N_2 & 1 & \cdots & 1 \\ & \vdots & \vdots & \vdots & & \vdots \\ N_2 N_1 & N_1 & N_2 & 1 & \cdots & 1 \\ \hline +1 & 1 & 1 & 2 & \cdots & 1 \\ +2 & 2 & 1 & 2 & \cdots & 1 \\ +3 & 3 & 1 & 2 & \cdots & 1 \\ & \vdots & \vdots & \vdots & & \vdots \\ 2 N_2 N_1 & N_1 & 1 & 2 & \cdots & 1 \\ \hline & \vdots & \vdots & \vdots & & \vdots \\ N_3 N_2 N_1 & N_1 & N_2 & N_3 & \cdots & 1 \\ \hline & \vdots & \vdots & \vdots & & \vdots \\ N-N_1 & N_1 & N_2 & N_3 & \cdots & N_D \\ \hline +1 & 1 & N_2 & N_3 & \cdots & N_D \\ +2 & 2 & N_2 & N_3 & \cdots & N_D \\ +3 & 3 & N_2 & N_3 & \cdots & N_D \\ & \vdots & \vdots & \vdots & & \vdots \\ N & N_1 & N_2 & N_3 & \cdots & N_D \end{array}$$

Indexing

Nodes can be indexed :

$$\begin{array}{rl} i^1i^2~\cdots~i^{D} & \Leftrightarrow (i^1,i^2,\cdots,i^{D}) \\ & \Leftrightarrow g_{i^1i^2~\cdots~i^{D}} \end{array}$$

From Address to Index

Nodes can be indexed from their tuple address :

$$\begin{array}{rrl} n_{i^1i^2~\cdots~i^{D}} & = & 0 \\ & += & i^1 \\ & += & i^2 \cdot N_1 \\ & += & i^3 \cdot ( N_2 \times N_1) \\ & & \cdots \\ & += & i^{D} \cdot ( N_{D-1} \times \cdots \times N_1 ) \end{array}$$

From Index to Address

Recursive euclidean division leads back to the address :

$$n_{i^1i^2~\cdots~i^{D}} = i^1 + N_1 \cdot (i_2 + N_2 \cdot (i_3 + \cdots + N_{D-2} \cdot (i_{D-1} + N_{D-1} \cdot i_D)))$$

$$\left \{ \begin{aligned} i^0 &= 0 \\ q^0 &= n \\ \\ i^1 &= q^0\;mod(N1) \\ q^1 &= q^0 : N1 \\ \\ i^{j} &= q^{j-1} \;mod(N_j) \\ q^j &= q^{j-1} : N_j \end{aligned} \right.$$

The recursive factors should be precomputed for a given grid to achieve fast index to tuple conversion.