import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import javafx.application.Application;
import javafx.geometry.Point2D;
import javafx.geometry.Pos;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.image.ImageView;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.scene.layout.Pane;
import javafx.scene.shape.Line;
import javafx.stage.Stage;
/** Use the old Graph.java, AbstractGraph.java, UnweightedGraph.java. Need to replace it in the future.*/
public class Exercise28_18 extends Application {
private Model model = new Model();
private static final int SIZE = 8;
private int startX = 0;
private int startY = 0;
private ArrayList<Point2D> moveHistory = null;
@Override // Override the start method in the Application class
public void start(Stage primaryStage) {
BorderPane pane = new BorderPane();
ChessBoard board = new ChessBoard();
pane.setCenter(board);
Button btPath = new Button("Path");
Button btCycle = new Button("Cycle");
HBox hBox = new HBox(5);
hBox.getChildren().addAll(btPath, btCycle);
hBox.setAlignment(Pos.CENTER);
pane.setBottom(hBox);
// Create a scene and place it in the stage
Scene scene = new Scene(pane, 250, 250);
primaryStage.setTitle("Exercise28_18"); // Set the stage title
primaryStage.setScene(scene); // Place the scene in the stage
primaryStage.show(); // Display the stage
board.repaint();
btPath.setOnAction(e -> {
resetMoveHistory();
List<Integer> list = model.findHamiltonianPath(startX, startY);
for (int i = 0; i < list.size(); i++) {
addMoveHistory(list.get(i) / 8, list.get(i) % 8);
}
board.repaint();
});
btCycle.setOnAction(e -> {
resetMoveHistory();
List<Integer> list = model.findHamiltonianCycle(startX, startY);
for (int i = 0; i < list.size(); i++) {
addMoveHistory(list.get(i) / 8, list.get(i) % 8);
}
board.repaint();
});
scene.widthProperty().addListener(ov -> board.repaint());
scene.heightProperty().addListener(ov -> board.repaint());
}
public void resetMoveHistory() {
moveHistory = new ArrayList(63);
}
public void addMoveHistory(int x, int y) {
moveHistory.add(new Point2D(x, y));
}
public void removeLastMoveHistory() {
moveHistory.remove(moveHistory.size() - 1);
}
private class ChessBoard extends Pane {
ImageView knightImageView = new ImageView("image/knight.jpg");
ChessBoard() {
this.setOnMouseClicked(e -> {
startX = (int) (e.getX() / (getWidth() / SIZE));
startY = (int) (e.getY() / (getHeight() / SIZE));
resetMoveHistory();
repaint();
});
}
protected void repaint() {
// Clear previous drawing
this.getChildren().clear();
// Add the Knight image
this.getChildren().add(knightImageView);
knightImageView.setX(startX * getWidth() / SIZE);
knightImageView.setY(startY * getHeight() / SIZE);
knightImageView.setFitWidth(getWidth() / SIZE);
knightImageView.setFitHeight(getHeight() / SIZE);
// Draw the lines
for (int i = 1; i <= SIZE; i++) {
this.getChildren().add(
new Line(0, i * getHeight() / SIZE, getWidth(), i * getHeight() / SIZE));
this.getChildren().add(
new Line(i * getWidth() / SIZE, 0, i * getWidth() / SIZE, getHeight()));
}
// Draw the moves
if (moveHistory != null) {
for (int i = 1; i < moveHistory.size(); i++) {
Point2D p1 = moveHistory.get(i - 1);
Point2D p2 = moveHistory.get(i);
this.getChildren().add(
new Line(p1.getX() * (getWidth() / SIZE) + getWidth() / SIZE / 2,
p1.getY() * (getHeight() / SIZE) + (getHeight() / SIZE / 2),
p2.getX() * (getWidth() / SIZE) + getWidth() / SIZE / 2,
p2.getY() * (getHeight() / SIZE) + getHeight() / SIZE / 2));
}
}
}
}
/**
* The main method is only needed for the IDE with limited
* JavaFX support. Not needed for running from the command line.
*/
public static void main(String[] args) {
launch(args);
}
/**
* Edge inner class inside the AbstractGraph class
*/
public static class Edge {
public int u; // Starting vertex of the edge
public int v; // Ending vertex of the edge
/**
* Construct an edge for (u, v)
*/
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
}
public interface Graph {
/**
* Return the number of vertices in the graph
*/
public int getSize();
/**
* Return the vertices in the graph
*/
public Object[] getVertices();
/**
* Return the object for the specified vertex index
*/
public Object getVertex(int index);
/**
* Return the index for the specified vertex object
*/
public int getIndex(Object v);
/**
* Return the neighbors of vertex v
*/
public java.util.List getNeighbors(int v);
/**
* Return the degree for a specified vertex
*/
public int getDegree(int v);
/**
* Return the adjacency matrix
*/
public int[][] getAdjacencyMatrix();
/**
* Print the adjacency matrix
*/
public void printAdjacencyMatrix();
/**
* Print the edges
*/
public void printEdges();
/**
* Obtain a depth-first search tree
*/
public AbstractGraph.Tree dfs(int v);
/**
* Obtain a breadth-first search tree
*/
public AbstractGraph.Tree bfs(int v);
/**
* Obtain a depth-first search tree
*/
public List<Integer> getHamiltonianPath(int v);
/**
* Obtain a depth-first search tree
*/
public List<Integer> getHamiltonianCycle(int v);
/** Return a Hamiltonian cycle
* Return null if the graph does not contain a Hamiltonian cycle */
public List<Integer> getHamiltonianCycle();
}
public abstract class AbstractGraph implements Graph {
protected Object[] vertices; // Store vertices
protected LinkedList<Integer>[] neighbors; // Adjacency lists
/**
* Construct a graph from edges and vertices stored in arrays
*/
protected AbstractGraph(int[][] edges, Object[] vertices) {
this.vertices = vertices;
createAdjacencyLists(edges, vertices.length);
}
/**
* Construct a graph from edges and vertices stored in ArrayList
*/
protected AbstractGraph(List<Edge> edges, List<Object> vertices) {
this.vertices = vertices.toArray();
createAdjacencyLists(edges, vertices.size());
}
/**
* Construct a graph from edges and vertices in ArrayList
*/
protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
vertices = new Integer[numberOfVertices]; // Create vertices
for (int i = 0; i < numberOfVertices; i++) {
vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}
/**
* Construct a graph from edges in array
*/
protected AbstractGraph(int[][] edges, int numberOfVertices) {
vertices = new Integer[numberOfVertices]; // Create vertices
for (int i = 0; i < numberOfVertices; i++) {
vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...}
}
createAdjacencyLists(edges, numberOfVertices);
}
/**
* Create adjacency lists for each vertex
*/
@SuppressWarnings("unchecked")
private void createAdjacencyLists(