GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1051

Listing 28.13 shows the source code for NineTailModel.java.

L ISTING 28.13

NineTailModel.java
1 import java.util.*;
2
3 public class NineTailModel {
4

public final static int NUMBER_OF_NODES = 512 ;

5 protected AbstractGraph<Integer>.Tree tree; // Define a tree declare a tree

6
7 /** Construct a model */
8 public NineTailModel() {
9 // Create edges
10 List<AbstractGraph.Edge> edges = getEdges();
11
12 // Create a graph
13 UnweightedGraph<Integer> graph = new UnweightedGraph<>(
14 edges, NUMBER_OF_NODES);
15
16 // Obtain a BSF tree rooted at the target node
17 tree = graph.bfs( 511 );
18 }
19
20 /** Create all edges for the graph */
21 private List<AbstractGraph.Edge> getEdges() {
22 List<AbstractGraph.Edge> edges =
23

create edges

create graph

create tree

get edges

new ArrayList<>(); // Store edges

24
25 for ( int u = 0 ; u < NUMBER_OF_NODES; u++) {
26 for ( int k = 0 ; k < 9 ; k++) {
27 char [] node = getNode(u); // Get the node for vertex u
28 if (node[k] == 'H' ) {
29 int v = getFlippedNode(node, k);
30 // Add edge (v, u) for a legal move from node u to node v
31 edges.add( new AbstractGraph.Edge(v, u));
32 }
33 }
34 }
35
36

add an edge

return edges;

37 }
38
39

public static int getFlippedNode( char [] node, int position) { flip cells

40 int row = position / 3 ;

41 int column = position % 3 ;

42
43 flipACell(node, row, column);
44 flipACell(node, row - 1 , column);
45 flipACell(node, row + 1 , column);
46 flipACell(node, row, column - 1 );
47 flipACell(node, row, column + 1 );
48
49

column

Flip

row

return getIndex(node);

50 }
51
52 public static void flipACell( char [] node, int row, int column) {
53 if (row >= 0 && row <= 2 && column >= 0 && column <= 2 ) {
54 // Within the boundary
55 if (node[row * 3 + column] == 'H' )
56 node[row * 3 + column] = 'T' ; // Flip from H to T

flip a cell