The number of nodes within k-hops in a n-D Torus

Torus is a widely used interconnection in high-performance computing systems. Torus can be built as 1D, 2D, 3D, 4D, 5D, 6D, and even higher dimensional topology, and they can be both server-centric and switch-centric.

For a n-D Torus with the same number of nodes in each dimension, starting from a certain node A how many nodes it can be reached within k hops?  Our research shows that it can be formulated mathematically as follows:

• 1-D (n=1):  N = 2*(k+1);
• 2-D or 3-D (n=2 or n=3):  N = f(n-1, k) + 2*[f(n-1, k-1) + 1] + ... + 2*[f(n-1, 0) +1] +2;
• 4-D or higher D (n >= 4) :  N = f(n-1, k) + 2[f(n-1, k-1) + 1]

,where n indicates the dimension of Torus, k denotes the number of hops starting from 0, N gives the total number of nodes that can be reached within k-hops, and the function f(n,k) computes the N for the case of k-hops in a n-D Torus.

This can be easily implemented in a recursive way. The codes are attached as follows for your reference:

#include <iostream>

using namespace std;

int nodes_num (int dimension, int hops)
{
	int nodes;

//	if (dimension <= 0 || hops < 0)
//	{
//		cerr << "Wrong parameter! Please try again!" << endl;
//		return -1;
//	}

	if(dimension == 1)
	{
		return 2 * (hops + 1);
	}

	if(dimension == 2 || dimension == 3)
	{
		nodes = nodes_num(dimension - 1, hops);
		for (int k = hops - 1; k >= 0; k--)
		{
			nodes += 2 * (nodes_num(dimension - 1, k) + 1);
		}
		return nodes + 2;
	}

	if(dimension >= 4)
	{
		if (hops == 0)
		{
			return nodes_num(dimension - 1, hops) + 2;
		}
		else
		{
			return nodes_num(dimension - 1, hops) + 2 * (nodes_num(dimension - 1, hops - 1) + 1);
		}
	}
}

int main()
{	
	while(!cin.fail() && !cin.bad())
	{
		int dimension, hops, nodes;

		cout << "Please input the dimension and the hops: " << endl;

		cout << "Dimension = ";
		cin >> dimension;

		cout << "Hops = ";
		cin >> hops;
		
		if (dimension <= 0 || hops < 0)
		{
			cerr << "Wrong parameter! Please check it and try again!" << endl;
			return -1;
		}
		else
		{
			nodes = nodes_num(dimension, hops);
			
			cout << "The total number of nodes that can be reached within " << hops << " hops is: " << nodes << endl << endl;

			cout << "The total number of nodes that can be reached at the " << hops << " hop is: " 
				 << nodes_num(dimension, hops) - nodes_num(dimension, hops - 1) << endl << endl;
		}
	}
	
	return 0;
}