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); | |
} | |
} |
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
You should install Java 8