3D Array Traversal in Different Order

Question

I've a 3D array of nodes and I want to traverse it by starting from the middle node of array, and moving towards corners ... Like this

and So on ... but for visualization purposes I've shown in 2D but actually it is 3D, so when we move away we will creating a Cube on every even iteration and creating a sphere on every odd iteration. but

It will look like in 3D as

Hopefully I've stated my question in a best possible way... please help me to build an algorithm, I've tried a lot but didn't get the right path ... I'm familiar with C,C++, C#, JAVA so I'll be grateful if I can get the answer in these languages, otherwise just share the algorithm I'll implement it ...

EDITED:

Next Iteration

Answer 1

The way this works is by creating a graph, where each cell is a node. Since the graph have the shape of a cube, therefore each node must have a link to its X, Y and Z neighbour. The first proceeder to do is creating the graph by feeding the program the relation between neighbour nodes. For instance, we should give the program an input saying that node zero is connected to node one, etc ... After telling the program about how the nodes are connected to form the cube, it's easy to start thinking about traversing this graph. A popular algorithm for traversing graphs is called Breadth First Traversal (BFT), this algorithm allows nodes to be traversed in a distributed way. For example, if you have a tree, which is a type of graphs, traversing it using BFT will print the root first, then prints each level at a time, so it's kind of traversing the tree from the starting point by propagating fairly in all branches. In your example of traversing a cube starting from the middle to the corners is exactly what BFT can do for you. In this case, BFT will start from the middle and start traversing the nodes surface by surface, and since we are starting from the middle point, the propagation will take a sphere shape.

What is BFT
BFT needs to use a data structure called Queue which is a First In First Out list. First we offer to the queue the starting point and we mark it as visited, meaning that it has entered the queue and is not allowed to enter any time later in the traversal. Then we will apply a proceeder that will poll the head node, mark it as visited, and offer its unvisited neighbours. The same process is done again and again until all nodes are visited and therefore the queue is empty. The reason we use a queue here is to allow nodes to be traversed in balanced way. In this cube traversal program, offering the middle node will follow by polling it out from the queue and offering its 6 neighbours (in case of >= 3x3x3 cube). Then each of those neighbours node will be polled by order of entrance and their neighbours will be offered at the end of the queue. The proceeder keep running until no unvisited neighbour is left.

Code explanation:
First we need to know the size of the cube. A cube of 3x3x3 mean we should create 27 nodes. I created a method called generateCubeGraph() which will generate input string to inform the program about the relation between neighbour nodes. An example of return output by this method:

27 54
0 1
0 3
0 9
1 2
1 4
1 10
etc..

The first two values are respectively, the number of nodes, and the number of links/edges between neighbour nodes. The rest of the lines are the connection between nodes. For example the first line tells that node zero is connected to node 1, etc... Note that this is an undirected graph, so when the program store the link between nodes, it store from node x to node y and from node y to node x.
After generating the input, build() method will store the links between nodes in an adjacency list. Another array is created to count how many edge have been created for every node.
After storing the links, all we need to do is traverse the cube graph using BFT algorithm. Check above description on how it works and read the implementation for more understanding of how it works.
The printing methods are optional, they help in the implementation and in the description of how the code is working.

This picture below shows how I numbered the nodes in a cube of 3x3x3 nodes. Moreover, I have added an example to show how a node is linked to its X, Y and Z neighbour (At the bottom of the picture).

Here's the code for a Cube of 3 x 3 x 3 nodes in JAVA: (You can change the number of nodes per side by modifying sideNode variable)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Driver class: Build, traverse, print linkage
 */
public class CubeDriver {
    public static void main(String[] args) {

        // How many nodes per side
        int sideNodes = 3;

        Cube cube = new Cube();
        cube.build(cube.generateCubeGraph(sideNodes));

        System.out.println("Node execution order: ");
        cube.BFT();

        System.out.println("Nodes links:");
        dcube.printAL();

        System.out.println("Nodes on Layers:");
        cube.printLayers(sideNodes);
    }
}

/**
 * Cube creator
 */
class Cube{

    // Adjacency list (Hold node's neighbors)
    int al[][];

    // Degree array (Count how many neighbor per node)
    int dl[];

    int NODES;
    int EDGES;
    int MAX_LINKS = 6; // No node can have more than 6 links in all case

    /**
     * Create the links between nodes based on the input generated by generateCubeGraph() mehtod
     */
    public void build(String input){
        Scanner scan = new Scanner(input);

        // Get #Nodes and #Edges
        NODES = scan.nextInt();
        EDGES = scan.nextInt();

        // Initialize 2D Array and Degree array
        al = new int[NODES][MAX_LINKS];
        dl = new int[NODES];

        // Store the link between nodes
        for(int i=0; i<EDGES; i++){
            int node1, node2;

            node1  = scan.nextInt();
            node2 = scan.nextInt();

            int node1Neighbors = dl[node1]++;
            int node2Neighbors = dl[node2]++;

            al[node1][node1Neighbors] = node2;
            al[node2][node2Neighbors] = node1;
        }

    }

    /**
     * Traverse using Breadth first traversal method
     * Plug the middle node in a queue, then poll it and put it's neighbor, then poll each neighbor and put their neighbors if not visited already
     */
    public void BFT(){
        int visited[] = new int[NODES];
        Queue<Integer> q = new LinkedList<Integer>();
        int VISITED = 1;

        // Plug the center node
        int middle = NODES/2;
        q.offer(middle);
        visited[middle] = VISITED;

        while(!q.isEmpty()){
            int polledNode = q.poll();
            System.out.print(polledNode + " ");

            for(int i=0; i < dl[polledNode]; i++){
                int neighbor = al[polledNode][i];

                if(visited[neighbor] != VISITED){
                    q.offer(neighbor);
                    visited[neighbor] = VISITED;
                }
            }
        }
        System.out.println("\n");
    }

    /**
     * Input generator for a cube
     */
    public String generateCubeGraph(int n){
        int SIDE = n; // Number of nodes in one side of the cube
        String links = ""; // Holds the final output
        int link = 0; // Counts the number of links

        for(int row=0; row<SIDE; row++){
            for(int col=0; col<SIDE; col++){
                for(int depth=0; depth<SIDE; depth++){
                    int current = depth + (col * SIDE) + (row * SIDE * SIDE);

                    // If not last depth
                    if(depth != SIDE-1){
                        links += String.format("%d %d\n", current, current+1);
                        link++;
                    }

                    // If not last col
                    if(col != SIDE-1){
                        links += String.format("%d %d\n", current, current+SIDE);
                        link++;
                    }

                    // If not last row
                    if(row != SIDE-1){
                        links += String.format("%d %d\n", current, current+(SIDE*SIDE));
                        link++;
                    }
                }
            }
        }

        // return #Nodes, #Edges, links ...
        return String.format("%d %d\n%s", SIDE*SIDE*SIDE, link, links);
    }

    /**
     * Prints the links between each nodes. Used for debugging only
     */
    public void printAL(){
        for(int node = 0; node < NODES; node++){
            System.out.print(String.format("Node %3d linked to nodes: ", node));
            for(int neighbor = 0; neighbor < dl[node]; neighbor++){
                System.out.print(String.format("%3d ", al[node][neighbor]));
            }
            System.out.println();
        }
        System.out.println();
    }

    /**
     * Print 3D layers nodes number
     * */
    public void printLayers(int sideNode){
        for(int layer=0; layer<sideNode; layer++){
            System.out.println("Layer: " + layer);
            for(int row = 0; row < sideNode; row++){
                for(int col = 0; col < sideNode; col++){
                    int current = layer + (col * sideNode) + (row * sideNode * sideNode);
                    System.out.print(String.format("%3d ", current));
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

Output

Node execution order: 
13 4 10 12 14 16 22 1 3 5 7 9 11 19 15 21 17 23 25 0 2 6 8 18 20 24 26 

Nodes links:
Node   0 linked to nodes:   1   3   9 
Node   1 linked to nodes:   0   2   4  10 
Node   2 linked to nodes:   1   5  11 
Node   3 linked to nodes:   0   4   6  12 
Node   4 linked to nodes:   1   3   5   7  13 
Node   5 linked to nodes:   2   4   8  14 
Node   6 linked to nodes:   3   7  15 
Node   7 linked to nodes:   4   6   8  16 
Node   8 linked to nodes:   5   7  17 
Node   9 linked to nodes:   0  10  12  18 
Node  10 linked to nodes:   1   9  11  13  19 
Node  11 linked to nodes:   2  10  14  20 
Node  12 linked to nodes:   3   9  13  15  21 
Node  13 linked to nodes:   4  10  12  14  16  22 
Node  14 linked to nodes:   5  11  13  17  23 
Node  15 linked to nodes:   6  12  16  24 
Node  16 linked to nodes:   7  13  15  17  25 
Node  17 linked to nodes:   8  14  16  26 
Node  18 linked to nodes:   9  19  21 
Node  19 linked to nodes:  10  18  20  22 
Node  20 linked to nodes:  11  19  23 
Node  21 linked to nodes:  12  18  22  24 
Node  22 linked to nodes:  13  19  21  23  25 
Node  23 linked to nodes:  14  20  22  26 
Node  24 linked to nodes:  15  21  25 
Node  25 linked to nodes:  16  22  24  26 
Node  26 linked to nodes:  17  23  25 

Nodes on Layers: // Check the picture above to know what the below layers are.
Layer: 0
  0   3   6 
  9  12  15 
 18  21  24 

Layer: 1
  1   4   7 
 10  13  16 
 19  22  25 

Layer: 2
  2   5   8 
 11  14  17 
 20  23  26 

Link to verify how it works in 3D (You have to colour the nodes in the node processed order, and you can get the node number by looking at the layer output for each node number position):

3D Model for a 5 x 5 x 5 Cube

Answer 2

I'd be tempted to do the most obvious thing: a connectivity graph (that can be implicit by array position) and a bucket sort.

At each iteration, take any cell from the highest numbered bucket. For each of its neighbours that isn't marked as already processed, remove them from their current bucket and insert into the next one up. Then mark that cell as processed and remove it from its bucket.

If you want strict inside-to-outside ordering, pick from the highest numbered bucket whichever cell is closest to the centre. If you're going to apply this test, it's probably smartest to keep bucket contents roughly in order; it feels like keeping an ordered list in each bucket plus a list of cells not yet inserted into the ordered list and doing a just-in-time merge sort with the known in-order list jumping in only at the final merge step would be smartest.

Have I correctly understood the problem?