Java Reference
In-Depth Information
The
NineTailModel
class creates a
Graph
and obtains a
Tree
rooted at the target node
511
.
WeightedNineTailModel
is the same as
NineTailModel
except that it creates a
WeightedGraph
and obtains a
ShortestPathTree
rooted at the target node
511
.
Weight-
edNineTailModel
extends
NineTailModel
. The method
getEdges()
finds all edges in
the graph. The
getNumberOfFlips(int u, int v)
method returns the number of flips
from node
u
to node
v
. The
getNumberOfFlips(int u)
method returns the number of flips
from node
u
to the target node.
Listing 29.9 implements
WeightedNineTailModel
.
L
ISTING
29.9
WeightedNineTailModel.java
1
import
java.util.*;
2
3
public class
WeightedNineTailModel
extends
NineTailModel {
4
extends
NineTailModel
/** Construct a model */
5
public
WeightedNineTailModel() {
constructor
6
// Create edges
7
List<WeightedEdge> edges = getEdges();
get edges
8
9
// Create a graph
10
WeightedGraph<Integer> graph =
new
WeightedGraph<>(
create a graph
11
edges, NUMBER_OF_NODES);
12
13
// Obtain a shortest path tree rooted at the target node
14
tree = graph.getShortestPath(
511
);
get a tree
15 }
16
17
/** Create all edges for the graph */
18
private
List<WeightedEdge> getEdges() {
19
// Store edges
20 List<WeightedEdge> edges =
new
ArrayList<>();
21
22
get weighted edges
for
(
int
u =
0
; u < NUMBER_OF_NODES; u++) {
23
for
(
int
k =
0
; k <
9
; k++) {
24
char
[] node = getNode(u);
// Get the node for vertex u
25
if
(node[k] ==
'H'
) {
26
int
v = getFlippedNode(node, k);
get adjacent node
weight
27
int
numberOfFlips = getNumberOfFlips(u, v);
28
29
// Add edge (v, u) for a legal move from node u to node v
30 edges.add(
new
WeightedEdge(v, u, numberOfFlips));
31 }
32 }
33 }
34
35
add an edge
return
edges;
36 }
37
38
private static int
getNumberOfFlips(
int
u,
int
v) {
number of flips
39
char
[] node1 = getNode(u);
40
char
[] node2 = getNode(v);
41
42
int
count =
0
;
// Count the number of different cells
43
for
(
int
i =
0
; i < node1.length; i++)
44
if
(node1[i] != node2[i]) count++;
45
46
return
count;
47 }
48
Search WWH ::
Custom Search