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

The nine tails problem is to find the minimum number of the moves that lead to all coins
facing down. Each move flips a head coin and its neighbors. The weighted nine tails problem
assigns the number of flips as a weight on each move. For example, you can change the coins
in Figure 29.22a to those in Figure 29.22b by flipping the first coin in the first row and its two
neighbors. Thus, the weight for this move is 3 . You can change the coins in Figure 29.22c to
Figure 29.22d by flipping the center coin and its four neighbors. So the weight for this move is 5 .

H HH T TH T TH T HH

TTT HTT HHT TTH

HHH HHH HHH HTH

(a) (b) (c) (d)

F IGURE 29.22

The weight for each move is the number of flips for the move.

The weighted nine tails problem can be reduced to finding a shortest path from a starting
node to the target node in an edge-weighted graph. The graph has 512 nodes. Create an edge
from node v to u if there is a move from node u to node v . Assign the number of flips to be
the weight of the edge.
Recall that in Section 28.10 we defined a class NineTailModel for modeling the nine
tails problem. We now define a new class named WeightedNineTailModel that extends
NineTailModel , as shown in Figure 29.23.

NineTailModel

#tree: AbstractGraph<Integer>.Tree

A tree rooted at node 511.

+NineTailModel() Constructs a model for the nine tails problem and obtains the

tree.

+getShortestPath(nodeIndex: int):
List<Integer>

Returns a path from the specified node to the root. The path
returned consists of the node labels in a list.
Returns a list of Edge objects for the graph.

-getEdges():
List<AbstractGraph.Edge>
+getNode(index: int): char[]
+getIndex(node: char[]): int
+getFlippedNode(node: char[],
position: int): int
+flipACell(node: char[], row: int,
column: int): void
+printNode(node: char[]): void

Returns a node consisting of nine characters of H's and T's.
Returns the index of the specified node.

Flips the node at the specified position and returns the index
of the flipped node.

Flips the node at the specified row and column.

Displays the node to the console.

WeightedNineTailModel

+WeightedNineTailModel()

Constructs a model for the weighted nine tails problem
and obtains a ShortestPathTree rooted from the target
node.

+getNumberOfFlips(u: int): int Returns the number of flips from node u to the target

node 511.

-getNumberOfFlips(u: int, v: int): int

Returns the number of different cells between the two
nodes.

-getEdges(): List<WeightedEdge>

Gets the weighted edges for the weighted nine tail
problem.

F IGURE 29.23

The WeightedNineTailModel class extends NineTailModel .