Created
August 6, 2016 17:16
-
-
Save tareq-si-salem/70ed46f44940581a065c4d0573163c15 to your computer and use it in GitHub Desktop.
Implementation of the Dijkstra’s and Floyd-Warshall’s Algorithms GUI JavaFX
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Arrays; | |
import javafx.application.Application; | |
import javafx.scene.Scene; | |
import javafx.scene.layout.Pane; | |
import javafx.scene.paint.Color; | |
import javafx.scene.shape.Circle; | |
import javafx.scene.shape.Line; | |
import javafx.scene.shape.Polygon; | |
import javafx.scene.text.Font; | |
import javafx.scene.text.Text; | |
import javafx.stage.Stage; | |
public class ShortestPathGUI extends Application { | |
ArrayList<Circle> nodes = new ArrayList<>(); | |
int clickcount = 0; | |
int pathfromto[] = new int[2]; | |
DiGraph g; | |
Line[][] line; | |
public static void main(String[] args) { | |
launch(args); | |
} | |
@Override | |
public void start(Stage stage) { | |
System.out.println("creating graph"); | |
g = new DiGraph(); | |
floydWarshallAlgorithm(); | |
Pane root = new Pane(); | |
Scene scene = new Scene(root, 800, 600); | |
stage.setScene(scene); | |
stage.show(); | |
for (int i = 0; i < g.vertices.size(); i++) { | |
Circle circle = new Circle(15); | |
circle.setFill(Color.GRAY); | |
Text text = new Text("" + i); | |
text.setFont(Font.font(17)); | |
text.setFill(Color.DARKORANGE); | |
circle.setStroke(Color.DARKORANGE); | |
text.layoutXProperty().bind(circle.centerXProperty().add(-text.getLayoutBounds().getWidth() / 2)); | |
text.layoutYProperty().bind(circle.centerYProperty().add(5)); | |
nodes.add(circle); | |
root.getChildren().addAll(circle, text); | |
} | |
int i = 0; | |
for (Circle circle : nodes) { | |
circle.setCenterX(400 + 250 * Math.cos(i * 2 * Math.PI / g.vertices.size() - Math.PI * 2/3.0)); | |
circle.setCenterY(300 + 250 * (Math.sin(i * 2 * Math.PI / g.vertices.size() - Math.PI * 2/3.0))); | |
circle.setOnMouseClicked(e -> { | |
Circle c = (Circle) e.getSource(); | |
pathfromto[clickcount] = nodes.indexOf(c); | |
if (clickcount == 1) { | |
ArrayList<Integer> path = floydPath(pathfromto[0], pathfromto[1]); | |
new Thread(() -> { | |
for (int j = 0; j < path.size() - 1; j++) { | |
try { | |
Line l = line[path.get(j)][path.get(j + 1)]; | |
l.setStroke(Color.BLUE); | |
l.setStrokeWidth(7); | |
Thread.sleep(500); | |
} catch (Exception ex) { | |
} | |
} | |
try { | |
Thread.sleep(1000); | |
} catch (Exception ex) { | |
} | |
for (int j = 0; j < path.size() - 1; j++) { | |
Line l = line[path.get(j)][path.get(j + 1)]; | |
l.setStroke(Color.BLACK); | |
l.setStrokeWidth(3); | |
} | |
}).start(); | |
} | |
clickcount = (clickcount + 1) % 2; | |
}); | |
i++; | |
} | |
line = new Line[g.vertices.size()][g.vertices.size()]; | |
for (int j = 0; j < g.vertices.size(); j++) { | |
for (int k = 0; k < g.vertices.size(); k++) { | |
double w = g.getWeight(j, k); | |
if (w != 0 && w != Double.MAX_VALUE) { | |
addEdge(root, j, k, w); | |
} | |
} | |
} | |
} | |
void addEdge(Pane root, int u, int v, double weight) { | |
line[u][v] = new Line(); | |
Circle circleU, circleV; | |
circleU = nodes.get(u); | |
circleV = nodes.get(v); | |
line[u][v].setStartX(circleU.getCenterX()); | |
line[u][v].setStartY(circleU.getCenterY()); | |
line[u][v].setEndX(circleV.getCenterX()); | |
line[u][v].setEndY(circleV.getCenterY()); | |
line[u][v].setStrokeWidth(3); | |
Text t = new Text(String.valueOf(weight)); | |
double arrowAngle = (Math.atan2(line[u][v].getEndY() - line[u][v].getStartY(), line[u][v].getEndX() - line[u][v].getStartX())); | |
t.setLayoutX((line[u][v].getEndX() - line[u][v].getStartX()) / 2 + line[u][v].getStartX()); | |
t.setLayoutY((line[u][v].getEndY() - line[u][v].getStartY()) / 2 + line[u][v].getStartY()); | |
double scale = 2.5; | |
Polygon arrowHead = new Polygon(-4.33 * scale, 2.5 * scale, 5.0 * scale, 0, -4.33 * scale, -2.5 * scale, -4.33 * scale, 2.5 * scale); | |
arrowHead.setRotate(Math.toDegrees(arrowAngle)); | |
arrowHead.setLayoutX(line[u][v].getEndX() - 20 * Math.cos(arrowAngle)); | |
arrowHead.setLayoutY(line[u][v].getEndY() - 20 * Math.sin(arrowAngle)); | |
arrowHead.setFill(line[u][v].getStroke()); | |
root.getChildren().add(0, arrowHead); | |
root.getChildren().add(0, line[u][v]); | |
root.getChildren().add(0, t); | |
} | |
double[][] D; | |
int[][] floydWarshallPaths; | |
private void floydWarshallAlgorithm() { | |
D = new double[g.vertices.size()][g.vertices.size()]; | |
floydWarshallPaths = new int[D.length][D.length]; | |
for (int[] path : floydWarshallPaths) { | |
Arrays.fill(path, -1); | |
} | |
for (int i = 0; i < D.length; i++) { | |
for (int j = 0; j < D.length; j++) { | |
D[i][j] = g.getWeight(i, j); | |
if (D[i][j] == Double.MAX_VALUE) { | |
System.out.print("+INF "); | |
} else { | |
if (D[i][j] != 0) { | |
floydWarshallPaths[i][j] = j; | |
} | |
System.out.printf("%.1f ", D[i][j]); | |
} | |
} | |
System.out.println(""); | |
} | |
System.out.println("---------------------"); | |
for (int k = 0; k < D.length; k++) { | |
for (int i = 0; i < D.length; i++) { | |
for (int j = 0; j < D.length; j++) { | |
if (D[i][j] == Double.MAX_VALUE) { | |
System.out.printf("%-2c ", '\u221e'); | |
} else { | |
System.out.printf("%-2.0f ", D[i][j]); | |
} | |
} | |
System.out.println(); | |
} | |
System.out.println("---------------------"); | |
for (int i = 0; i < D.length; i++) { | |
for (int j = 0; j < D.length; j++) { | |
if (D[i][j] > D[i][k] + D[k][j]) { | |
D[i][j] = D[i][k] + D[k][j]; | |
floydWarshallPaths[i][j] = floydWarshallPaths[i][k]; | |
} | |
} | |
} | |
} | |
for (int path[] : floydWarshallPaths) { | |
for (int p : path) { | |
System.out.printf("%d ", p); | |
} | |
System.out.println(""); | |
} | |
for (int i = 0; i < D.length; i++) { | |
for (int j = 0; j < D.length; j++) { | |
System.out.println("Path from " + i + " to " + j + ": " + floydPath(i, j)); | |
} | |
} | |
} | |
ArrayList<Integer> floydPath(int u, int v) { | |
ArrayList<Integer> path = new ArrayList<>(); | |
if (floydWarshallPaths[u][v] == -1) { | |
return path; | |
} | |
path.add(u); | |
while (u != v) { | |
u = floydWarshallPaths[u][v]; | |
path.add(u); | |
} | |
return path; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
getWeight() was not declared in DiGraph (