Created
August 6, 2016 17:40
-
-
Save tareq-si-salem/f64aa8bbaaca9849243ff9cfa84691fe to your computer and use it in GitHub Desktop.
Prim-Jarnik and Kruksal to find a Minimal Spanning Tree of a connected graph GUI version
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.HBox; | |
import javafx.scene.layout.Pane; | |
import javafx.scene.paint.Color; | |
import javafx.scene.shape.Circle; | |
import javafx.scene.shape.Line; | |
import javafx.scene.text.Font; | |
import javafx.scene.text.Text; | |
import javafx.stage.Stage; | |
public class MSTGui extends Application { | |
ArrayList<Circle> nodes = new ArrayList<>(); | |
Circle circles[]; | |
@Override | |
public void start(Stage stage) throws Exception { | |
Pane graphContainer = new Pane(); | |
Pane primsTreeContainer = new Pane(); | |
Pane container = new Pane(); | |
HBox hBox = new HBox(container, primsTreeContainer, graphContainer); | |
Scene scene = new Scene(hBox, 900, 400); | |
stage.setScene(scene); | |
Graph G = new Graph(); | |
System.out.println("Cost matrix: "); | |
for (int i = 0; i < G.V.size(); i++) { | |
for (int j = 0; j < G.V.size(); j++) { | |
if (G.getWeight(i, j) == Graph.INF) { | |
System.out.print(Graph.INF_SYMBOL + "\t"); | |
} else { | |
System.out.printf("%.0f\t", G.getWeight(i, j)); | |
} | |
} | |
System.out.println(""); | |
} | |
for (int i = 0; i < G.V.size(); i++) { | |
Text text = new Text("" + i); | |
Circle node = createNode(text); | |
nodes.add(node); | |
container.getChildren().addAll(node, text); | |
} | |
int i = 0; | |
for (Circle node : nodes) { | |
node.setCenterX(200 + 150 * Math.cos(i * 2 * Math.PI / G.V.size())); | |
node.setCenterY(200 + 150 * (Math.sin(i * 2 * Math.PI / G.V.size()))); | |
i++; | |
} | |
G.E.stream().forEach((edge) -> { | |
addEdge(container, edge, false); | |
}); | |
stage.show(); | |
hBox.setOnMouseClicked(e -> { | |
prim(G, primsTreeContainer); | |
}); | |
} | |
private void prim(Graph G, Pane primsContainer) { | |
int n = G.V.size(); | |
boolean node_placed[] = new boolean[n]; | |
circles = new Circle[n]; | |
System.out.println("--------------------- Prim's Algorithm ---------------------"); | |
int closest[] = new int[n]; | |
double smallestCosts[] = new double[n]; | |
closest[0] = 0; | |
for (int i = 1; i < closest.length; i++) { | |
smallestCosts[i] = G.getWeight(i, 0); | |
closest[i] = 0; | |
} | |
double min; | |
System.out.println("Iteration\t\t\t\tClosest\t\t\t\tSmallestCosts"); | |
System.out.println("#Initial\t\t\t" + Arrays.toString(closest) + "\t\t" + Arrays.toString(smallestCosts)); | |
int k = 0; | |
for (int i = 1; i < n; i++) { | |
min = Graph.INF; | |
for (int j = 1; j < n; j++) { | |
if (smallestCosts[j] != 0 && min > smallestCosts[j]) { | |
k = j; | |
min = smallestCosts[j]; | |
} | |
} | |
// At this stage we have min{ smallesCosts } is smallesCosts[k] | |
smallestCosts[k] = 0; | |
for (int j = 1; j < n; j++) { | |
if (smallestCosts[j] > G.getWeight(k, j)) { | |
closest[j] = k; | |
smallestCosts[j] = G.getWeight(k, j); | |
} | |
} | |
System.out.println("#" + i + "\t\t\t\t" + Arrays.toString(closest) + "\t\t" + Arrays.toString(smallestCosts)); | |
} | |
double totalCost = 0; | |
for (int i = 0; i < closest.length; i++) { | |
totalCost += G.getWeight(i, closest[i]); | |
} | |
createAndAddNode(primsContainer, circles, 200, 30, 0); | |
node_placed[0] = true; | |
for (int u = 0; u < n; u++) { | |
ArrayList<Integer> childrenOfU = new ArrayList<>(); | |
if (node_placed[u] == true) { | |
for (int j = 1; j < n; j++) { | |
if (closest[j] == u) { | |
childrenOfU.add(j); | |
} | |
} | |
} | |
int s = 0; | |
boolean placed = false; | |
for (int child : childrenOfU) { | |
if (!node_placed[child]) { | |
createAndAddNode(primsContainer, circles, | |
circles[u].getCenterX() + 50 * Math.cos(-Math.PI / 2.0 + Math.PI / 6.0 * ((s) - (childrenOfU.size()) / 2)), | |
circles[u].getCenterY() + 50 * Math.sin(+Math.PI / 2.0 + Math.PI / 6.0 * ((s) - (childrenOfU.size()) / 2)), | |
child); | |
s += 2; | |
node_placed[child] = true; | |
placed = true; | |
} | |
} | |
if (placed) { | |
u = -1; | |
} | |
} | |
for (int i = 1; i < n; i++) { | |
addEdge(primsContainer, new Edge(i, closest[i], G.getWeight(i, closest[i])), true); | |
} | |
System.out.println("Minimal cost is: " + totalCost); | |
} | |
void addEdge(Pane root, Edge edge, boolean tree) { | |
Line line = new Line(); | |
Circle u, v; | |
if (!tree) { | |
u = nodes.get(edge.u); | |
v = nodes.get(edge.v); | |
} else { | |
u = circles[edge.u]; | |
v = circles[edge.v]; | |
} | |
line.setStartX(u.getCenterX()); | |
line.setStartY(u.getCenterY()); | |
line.setEndX(v.getCenterX()); | |
line.setEndY(v.getCenterY()); | |
line.setStrokeWidth(1); | |
Text t = new Text(String.format("%.1f", edge.weight)); | |
t.setFont(Font.font(13)); | |
t.setFill(Color.RED); | |
t.setLayoutX((line.getEndX() - line.getStartX()) * 0.25 + line.getStartX()); | |
t.setLayoutY((line.getEndY() - line.getStartY()) * 0.25 + line.getStartY()); | |
root.getChildren().add(0, t); | |
root.getChildren().add(0, line); | |
} | |
public static void main(String[] args) { | |
launch(args); | |
} | |
private Circle createNode(Text text) { | |
Circle circle = new Circle(10); | |
text.setFont(Font.font(15)); | |
text.setFill(Color.BLACK); | |
circle.setFill(Color.CORNFLOWERBLUE); | |
text.layoutXProperty().bind(circle.centerXProperty().add(-text.getLayoutBounds().getWidth() / 2)); | |
text.layoutYProperty().bind(circle.centerYProperty().add(5)); | |
return circle; | |
} | |
private void createAndAddNode(Pane primsContainer, Circle[] nodes, double w, double h, int i) { | |
Text text = new Text("" + i); | |
nodes[i] = createNode(text); | |
nodes[i].setCenterX(w); | |
nodes[i].setCenterY(h); | |
primsContainer.getChildren().addAll(nodes[i], text); | |
} | |
} |
You should install Java 8
include this class https://gist.github.com/Tareq-SiSalem/1d4da0676462888823025f14bc1e7d88, because it has the Graph and Edge classes.
and you can check this blog post, to see how to use it https://tareqthecomputerguy.wordpress.com/2016/08/06/prim-jarnik-and-kruksal-algorithm-to-find-a-mst-of-a-connected-graph/
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I got erros while compiling the above file.
Errors are listed BELOW 👎
MSTGui.java:54: error: illegal start of expression
G.E.stream().forEach((edge) -> {
^
MSTGui.java:54: error: illegal start of expression
G.E.stream().forEach((edge) -> {
^
MSTGui.java:54: error: ';' expected
G.E.stream().forEach((edge) -> {
^
MSTGui.java:55: error: ')' expected
addEdge(container, edge, false);
^
MSTGui.java:55: error: not a statement
addEdge(container, edge, false);
^
MSTGui.java:55: error: not a statement
addEdge(container, edge, false);
^
MSTGui.java:55: error: ';' expected
addEdge(container, edge, false);
^
MSTGui.java:56: error: illegal start of type
});
^
MSTGui.java:57: error: expected
stage.show();
^
MSTGui.java:58: error: expected
hBox.setOnMouseClicked(e -> {
^
MSTGui.java:58: error: expected
hBox.setOnMouseClicked(e -> {
^
MSTGui.java:58: error: ';' expected
hBox.setOnMouseClicked(e -> {
^
MSTGui.java:61: error: illegal start of type
});
^
MSTGui.java:64: error: class, interface, or enum expected
private void prim(Graph G, Pane primsContainer) {
^
MSTGui.java:66: error: class, interface, or enum expected
boolean node_placed[] = new boolean[n];
^
MSTGui.java:68: error: class, interface, or enum expected
circles = new Circle[n];
^
MSTGui.java:69: error: class, interface, or enum expected
System.out.println("--------------------- Prim's Algorithm ---------------------");
^
MSTGui.java:70: error: class, interface, or enum expected
int closest[] = new int[n];
^
MSTGui.java:71: error: class, interface, or enum expected
double smallestCosts[] = new double[n];
^
MSTGui.java:72: error: class, interface, or enum expected
closest[0] = 0;
^
MSTGui.java:74: error: class, interface, or enum expected
for (int i = 1; i < closest.length; i++) {
^
MSTGui.java:74: error: class, interface, or enum expected
for (int i = 1; i < closest.length; i++) {
^
MSTGui.java:74: error: class, interface, or enum expected
for (int i = 1; i < closest.length; i++) {
^
MSTGui.java:76: error: class, interface, or enum expected
closest[i] = 0;
^
MSTGui.java:77: error: class, interface, or enum expected
}
^
MSTGui.java:79: error: class, interface, or enum expected
System.out.println("Iteration\t\t\t\tClosest\t\t\t\tSmallestCosts");
^
MSTGui.java:80: error: class, interface, or enum expected
System.out.println("#Initial\t\t\t" + Arrays.toString(closest) + "\t\t" + Arrays.toString(smallestCosts));
^
MSTGui.java:81: error: class, interface, or enum expected
int k = 0;
^
MSTGui.java:83: error: class, interface, or enum expected
for (int i = 1; i < n; i++) {
^
MSTGui.java:83: error: class, interface, or enum expected
for (int i = 1; i < n; i++) {
^
MSTGui.java:83: error: class, interface, or enum expected
for (int i = 1; i < n; i++) {
^
MSTGui.java:85: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:85: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:85: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:88: error: class, interface, or enum expected
min = smallestCosts[j];
^
MSTGui.java:89: error: class, interface, or enum expected
}
^
MSTGui.java:94: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:94: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:94: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:97: error: class, interface, or enum expected
smallestCosts[j] = G.getWeight(k, j);
^
MSTGui.java:98: error: class, interface, or enum expected
}
^
MSTGui.java:101: error: class, interface, or enum expected
}
^
MSTGui.java:103: error: class, interface, or enum expected
for (int i = 0; i < closest.length; i++) {
^
MSTGui.java:103: error: class, interface, or enum expected
for (int i = 0; i < closest.length; i++) {
^
MSTGui.java:103: error: class, interface, or enum expected
for (int i = 0; i < closest.length; i++) {
^
MSTGui.java:105: error: class, interface, or enum expected
}
^
MSTGui.java:107: error: class, interface, or enum expected
node_placed[0] = true;
^
MSTGui.java:108: error: class, interface, or enum expected
for (int u = 0; u < n; u++) {
^
MSTGui.java:108: error: class, interface, or enum expected
for (int u = 0; u < n; u++) {
^
MSTGui.java:108: error: class, interface, or enum expected
for (int u = 0; u < n; u++) {
^
MSTGui.java:110: error: class, interface, or enum expected
if (node_placed[u] == true) {
^
MSTGui.java:111: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:111: error: class, interface, or enum expected
for (int j = 1; j < n; j++) {
^
MSTGui.java:114: error: class, interface, or enum expected
}
^
MSTGui.java:118: error: class, interface, or enum expected
boolean placed = false;
^
MSTGui.java:119: error: class, interface, or enum expected
for (int child : childrenOfU) {
^
MSTGui.java:125: error: class, interface, or enum expected
s += 2;
^
MSTGui.java:126: error: class, interface, or enum expected
node_placed[child] = true;
^
MSTGui.java:127: error: class, interface, or enum expected
placed = true;
^
MSTGui.java:128: error: class, interface, or enum expected
}
^
MSTGui.java:133: error: class, interface, or enum expected
}
^
MSTGui.java:135: error: class, interface, or enum expected
for (int i = 1; i < n; i++) {
^
MSTGui.java:135: error: class, interface, or enum expected
for (int i = 1; i < n; i++) {
^
MSTGui.java:137: error: class, interface, or enum expected
}
^
MSTGui.java:139: error: class, interface, or enum expected
}
^
MSTGui.java:143: error: class, interface, or enum expected
Circle u, v;
^
MSTGui.java:144: error: class, interface, or enum expected
if (!tree) {
^
MSTGui.java:146: error: class, interface, or enum expected
v = nodes.get(edge.v);
^
MSTGui.java:147: error: class, interface, or enum expected
} else {
^
MSTGui.java:149: error: class, interface, or enum expected
v = circles[edge.v];
^
MSTGui.java:150: error: class, interface, or enum expected
}
^
MSTGui.java:152: error: class, interface, or enum expected
line.setStartY(u.getCenterY());
^
MSTGui.java:153: error: class, interface, or enum expected
line.setEndX(v.getCenterX());
^
MSTGui.java:154: error: class, interface, or enum expected
line.setEndY(v.getCenterY());
^
MSTGui.java:155: error: class, interface, or enum expected
line.setStrokeWidth(1);
^
MSTGui.java:156: error: class, interface, or enum expected
Text t = new Text(String.format("%.1f", edge.weight));
^
MSTGui.java:157: error: class, interface, or enum expected
t.setFont(Font.font(13));
^
MSTGui.java:158: error: class, interface, or enum expected
t.setFill(Color.RED);
^
MSTGui.java:159: error: class, interface, or enum expected
t.setLayoutX((line.getEndX() - line.getStartX()) * 0.25 + line.getStartX());
^
MSTGui.java:160: error: class, interface, or enum expected
t.setLayoutY((line.getEndY() - line.getStartY()) * 0.25 + line.getStartY());
^
MSTGui.java:161: error: class, interface, or enum expected
root.getChildren().add(0, t);
^
MSTGui.java:162: error: class, interface, or enum expected
root.getChildren().add(0, line);
^
MSTGui.java:164: error: class, interface, or enum expected
}
^
MSTGui.java:166: error: class, interface, or enum expected
public static void main(String[] args) {
^
MSTGui.java:168: error: class, interface, or enum expected
}
^
MSTGui.java:172: error: class, interface, or enum expected
text.setFont(Font.font(15));
^
MSTGui.java:173: error: class, interface, or enum expected
text.setFill(Color.BLACK);
^
MSTGui.java:174: error: class, interface, or enum expected
circle.setFill(Color.CORNFLOWERBLUE);
^
MSTGui.java:175: error: class, interface, or enum expected
text.layoutXProperty().bind(circle.centerXProperty().add(-text.getLayoutBounds().getWidth() / 2));
^
MSTGui.java:176: error: class, interface, or enum expected
text.layoutYProperty().bind(circle.centerYProperty().add(5));
^
MSTGui.java:177: error: class, interface, or enum expected
return circle;
^
MSTGui.java:178: error: class, interface, or enum expected
}
^
MSTGui.java:182: error: class, interface, or enum expected
nodes[i] = createNode(text);
^
MSTGui.java:183: error: class, interface, or enum expected
nodes[i].setCenterX(w);
^
MSTGui.java:184: error: class, interface, or enum expected
nodes[i].setCenterY(h);
^
MSTGui.java:185: error: class, interface, or enum expected
primsContainer.getChildren().addAll(nodes[i], text);
^
MSTGui.java:186: error: class, interface, or enum expected
}
^
97 errors