3D Array Traversal in Different Order
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 540 10 30 91 21 41 10etc..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):
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?