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

49 public int getNumberOfFlips( int u) {
50 return ( int )((WeightedGraph<Integer>.ShortestPathTree)tree)
51 .getCost(u);
52 }
53 }

total number of flips

WeightedNineTailModel extends NineTailModel to build a WeightedGraph to model
the weighted nine tails problem (lines 10-11). For each node u , the getEdges() method
finds a flipped node v and assigns the number of flips as the weight for edge ( v , u ) (line 30).
The getNumberOfFlips(int u, int v) method returns the number of flips from node u
to node v (lines 38-47). The number of flips is the number of the different cells between the
two nodes (line 44).
The WeightedNineTailModel obtains a ShortestPathTree rooted at the target
node 511 (line 14). Note that tree is a protected data field defined in NineTailModel and
ShortestPathTree is a subclass of Tree . The methods defined in NineTailModel use
the tree property.
The getNumberOfFlips(int u) method (lines 49-52) returns the number of flips from
node u to the target node, which is the cost of the path from node u to the target node. This cost
can be obtained by invoking the getCost(u) method defined in the ShortestPathTree
class (line 51).
Listing 29.10 gives a program that prompts the user to enter an initial node and displays the
minimum number of flips to reach the target node.

L ISTING 29.10

WeightedNineTail.java
1 import java.util.Scanner;
2
3 public class WeightedNineTail {
4 public static void main(String[] args) {
5 // Prompt the user to enter the nine coins' Hs and Ts
6 System.out.print( "Enter an initial nine coins' Hs and Ts: " );
7 Scanner input = new Scanner(System.in);
8 String s = input.nextLine();
9

char [] initialNode = s.toCharArray();

initial node

10
11 WeightedNineTailModel model = new WeightedNineTailModel();
12 java.util.List<Integer> path =
13

create model

model.getShortestPath(NineTailModel.getIndex(initialNode)); get shortest path

14
15 System.out.println( "The steps to flip the coins are " );
16 for ( int i = 0 ; i < path.size(); i++)
17 NineTailModel.printNode(NineTailModel.getNode(path.get(i)));
18
19 System.out.println( "The number of flips is " +
20

print node

model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));

number of flips

21 }
22 }

Enter an initial nine coins Hs and Ts: HHHTTTHHH

The steps to flip the coins are
HHH
TTT
HHH