Dijkstra’s algorithm

 

Dijkstra’s algorithm 

In this project you will implement Dijkstra’s algorithm to find paths through a graph representing a network routing problem.

Provided Framework 1. A graphical user interface that generates a graph/network with a specified number of points, for a provided random seed 2. A display for the graph vertices and for the subsequently computed shortest paths

When you hit “Generate” the framework for this project generates a random set of nodes, V, each with 3 randomly selected edges to other nodes. The edges are directed and the edge cost is the Euclidean distance between the nodes. Thus, all nodes will have an out-degree of 3, but no predictable value for in-degree. You will be passed a graph structure which is comprised of |V| nodes, each with 3 edges, thus |E| = 3 |V| = O(|V|). The nodes have an (x,y) location and the edges include the start/end nodes and the edge length. The nodes are drawn on the display in

the provided framework. You can hit “Generate” again to build a new graph (if you change the random seed). After generating, clicking on a node (or entering its index in the appropriate box) will highlight the source in green, and clicking another (or, again entering its index in the box) will highlight the destination in red. Each click alternates between the two. After these nodes are selected you can hit “Compute”, and your code should draw the shortest path starting from the source node and following all intermediate nodes until the destination node. Next to each edge between two nodes, display the cost of that segment of the route. Also, in the "Total Path Cost" box, display the total path cost. If the destination cannot be reached from the source then put “unreachable” in the total cost box. Clicking on the screen again will clear the current path while allowing you to set another source/destination pair. To make sure everything is working correctly, first try some smaller problems that you can solve by hand. Also, at the bottom of this page, we have included a screen shot for a particular 2000 vertex problem, which you can use as a debug check to help ensure your code is working correctly. Note that here, since each node has a predefined maximum out-degree, O(|E|) = O(|V|), so in your analysis you can use O(|V|) in place of O(|E|). Note that in a stable network, a node could just run Dijkstra’s once for every node in the network and set up a routing table which it could then use for any message. However, for unstable networks (new nodes, outages, etc.) such a table would not necessarily be correct for very long.

:the solve problem 

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

 

///////////////////////////////////////////////////////////////////////////////////

 

  

 

  ///////////   Clase Edge////////////////////////

 

public class Edge {

private Node adjacent;

private int cost;

public Edge(Node adjacent, int cost) {

this.adjacent = adjacent;

this.cost = cost;

}

public Node getAdjacent() {

return adjacent;

}

public void setAdjacent(Node adjacent) {

this.adjacent = adjacent;

}

public int getCost() {

return cost;

}

public void setCost(int cost) {

this.cost = cost;

}

@Override

public String toString() {

return "Edge [adjacent=" + adjacent + ", cost=" + cost + "]";

}

}

 

//////////class Graph////////////////////

 import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.PriorityQueue;

import java.util.Random;

import javafx.application.Application;

import javafx.geometry.Pos;

import javafx.scene.layout.AnchorPane;

import javafx.scene.paint.Color;

import javafx.scene.shape.*;

import javafx.scene.Scene;

import javafx.scene.control.*;

import javafx.scene.layout.*;

import javafx.stage.Stage;

public class Graph extends Application {

// Vertecies

private Node[] nodes;

// for clear the path when click on the screen

private Integer i = 0;

// the circles that drew

private Circle[] dots = null;

public static void main(String[] args) {

launch(args);

}

@Override

public void start(Stage pStage) throws Exception {

VBox vb = new VBox(10);

vb.setAlignment(Pos.CENTER);

vb.setPrefSize(800, 400);

AnchorPane dotP = new AnchorPane();

dotP.setPrefSize(800, 300);

dotP.setStyle("-fx-background-color: #1D1D1D ");

HBox hb1 = new HBox(10);

hb1.setAlignment(Pos.CENTER);

TextField seedTf = new TextField();

TextField sizeTf = new TextField();

Button generateB = new Button("Generate");

hb1.getChildren().addAll(new Label("Seed:"), seedTf, new Label("Size:"), sizeTf, generateB);

HBox hb2 = new HBox(20);

hb2.setAlignment(Pos.CENTER);

TextField startTf = new TextField();

TextField endTf = new TextField();

TextField costTf = new TextField();

Button computeB = new Button("Compute Cost");

hb2.getChildren().addAll(new Label("Start:"), startTf, new Label("End:"), endTf, computeB,

new Label("Total Cost:"), costTf);

hb2.setDisable(true);

vb.getChildren().addAll(dotP, hb1, hb2);

// when seed TextField is clicked to make the program star another time

seedTf.setOnMouseClicked(e -> {

sizeTf.setDisable(false);

generateB.setDisable(false);

hb2.setDisable(true);

startTf.setText("");

endTf.setText("");

costTf.setText("");

});

startTf.setOnMouseClicked(e -> {

dots[Integer.parseInt(startTf.getText())] = null;

});

endTf.setOnKeyPressed(e -> {

});

// for AnchorPane to select the circle (source and distination ) and to

// clear the path

dotP.setOnMouseClicked(e -> {

// decide that the children is circle

if (e.getTarget() instanceof Circle) {

int id = Integer.parseInt(((Circle) e.getTarget()).getId());

// the circle is source

if (i == 0) {

startTf.setText(id + "");

dots[id].setFill(Color.BLUE);

dots[id].setRadius(5);

i++;

// circle is target

} else if (i == 1) {

endTf.setText(id + "");

dots[id].setFill(Color.GREEN);

dots[id].setRadius(5);

i++;

}

} else {

// when the source and distination and then clear the path to

// choose new one

if (i == 2 && !endTf.getText().isEmpty() && !startTf.getText().isEmpty()) {

int start = Integer.parseInt(startTf.getText());

int end = Integer.parseInt(endTf.getText());

int size = dotP.getChildren().size();

// delete the lines and the label for the cost and return

// the selected circles to the original stage

for (int i = dots.length; i < size; i++) {

String name = dotP.getChildren().get(i).getClass().getSimpleName();

if (name.equals("Label")) {

dotP.getChildren().remove(i);

i--;

size--;

} else if (name.equals("Line")) {

dotP.getChildren().remove(i);

i--;

size--;

}

}

dots[start].setFill(Color.WHITE);

dots[start].setRadius(2);

dots[end].setFill(Color.WHITE);

dots[end].setRadius(2);

startTf.setText("");

endTf.setText("");

costTf.setText("");

i = 0;

}

}

});

// make the circles randomly and also the paths between them

generateB.setOnAction(e -> {

try {

dotP.getChildren().clear();

Random r = new Random();

int seed = Integer.parseInt(seedTf.getText());

r.setSeed(seed);

int size = Integer.parseInt(sizeTf.getText());

// put limitation on number of nodes

if (size < 7) {

throw new NumberFormatException("The Number of nodes must be more than 7");

} else {

nodes = new Node[size];

dots = new Circle[size];

// generate the coordinates of the circles the function get

// size of the array and the boundary from & to

int[] xS = r.ints((size), 1, (int) dotP.getPrefWidth()).toArray();

int[] yS = r.ints((size), 1, (int) dotP.getPrefHeight()).toArray();

for (int i = 0; i < size; i++) {

dots[i] = new Circle(xS[i], yS[i], 2, Color.WHITE);

dots[i].setId(i + "");

dotP.getChildren().add(dots[i]);

// check if the node is set before

if (nodes[i] == null)

nodes[i] = new Node(i);

int[] cost = new Random().ints(3, 1, 20).toArray();

System.out.print("Node" + i + ": ");

int[] indecies = new Random().ints(3, 1, size - 1).toArray();

// check for condition to the adjacents that must be not

// equal to the vertex and not equal to another adjacent

while (indecies[0] == indecies[1] || indecies[0] == indecies[2] || indecies[1] == indecies[2]

|| indecies[0] == i || indecies[1] == i || indecies[2] == i) {

indecies = new Random().ints(3, 0, size - 1).toArray();

}

// add the adjacents to the vertex

for (int j = 0; j < 3; j++) {

System.out.print(indecies[j] + " " + cost[j] + "== ");

// for initialize the nodes that not initialized

if (nodes[indecies[j]] == null)

nodes[indecies[j]] = new Node(indecies[j]);

nodes[i].getAdjs().add(new Edge(nodes[indecies[j]], cost[j]));

}

System.out.println();

}

}

generateB.setDisable(true);

hb2.setDisable(false);

} catch (Exception e4) {

String st = "Please Enter Postive Integers In the fields and size more than 7";

Dialog<ButtonType> d = new Alert(Alert.AlertType.ERROR, st);

d.showAndWait();

}

});

// apply dijkstra and print the path on the screen

computeB.setOnAction(e -> {

try {

int initial = Integer.parseInt(startTf.getText());

int target = Integer.parseInt(endTf.getText());

int size = Integer.parseInt(sizeTf.getText());

// check for the values of start and end

if (initial == target || target > size || target < 0 || initial < 0 || initial > size) {

String st = "The initial and target must not be equal or more than size or negative";

Dialog<ButtonType> d = new Alert(Alert.AlertType.ERROR, st);

d.showAndWait();

dots[target].setRadius(2);

dots[target].setFill(Color.WHITE);

} else {

dots[initial].setFill(Color.BLUE);

dots[initial].setRadius(5);

dots[target].setFill(Color.GREEN);

dots[target].setRadius(5);

i = 2;

// make the values to original values inorder to make

// multiple routes many times

for (Node temp : nodes) {

temp.setDistance(Integer.MAX_VALUE);

temp.setVisited(false);

temp.setParent(null);

}

// dijkstra

computeShortestPaths(nodes[initial]);

// print path

List<Node> path = getShortestPathTo(nodes[target]);

// check if there is path from source to distenation

if (nodes[target].getDistance() == Integer.MAX_VALUE) {

dots[target].setRadius(2);

dots[target].setFill(Color.WHITE);

costTf.setText("Unreachable");

} else {

// print the lines and the costs

for (int i = 0; i < path.size() - 1; i++) {

int indexS = path.get(i).getName();

int indexE = path.get(i + 1).getName();

Line line = new Line(dots[indexS].getCenterX(), dots[indexS].getCenterY(),

dots[indexE].getCenterX(), dots[indexE].getCenterY());

line.setStroke(Color.WHITE);

// get cost

int cost = 0;

for (int j = 0; j < 3; j++) {

if (nodes[indexS].getAdjs().get(j).getAdjacent().getName() == indexE)

cost = nodes[indexS].getAdjs().get(j).getCost();

}

Label temp = new Label(cost + "");

temp.setStyle("-fx-text-fill:#ffffff");

temp.setLayoutX((line.getStartX() + line.getEndX()) / 2);

temp.setLayoutY((line.getStartY() + line.getEndY()) / 2);

temp.setTextFill(Color.DARKTURQUOISE);

costTf.setText(nodes[target].getDistance() + "");

dotP.getChildren().addAll(line, temp);

}

}

}

} catch (Exception err) {

String st = "Please enter positive integer values";

Dialog<ButtonType> d = new Alert(Alert.AlertType.ERROR, st);

d.showAndWait();

}

});

Scene scene = new Scene(vb);

pStage.setScene(scene);

pStage.setTitle("Galaxy Simulation");

pStage.show();

}

public void computeShortestPaths(Node sourceVertex) {

sourceVertex.setDistance(0);

PriorityQueue<Node> priorityQueue = new PriorityQueue<>();

priorityQueue.add(sourceVertex);

sourceVertex.setVisited(true);

while (!priorityQueue.isEmpty()) {

// Getting the minimum distance vertex from priority queue

// getting minimum unknon distance

Node actualVertex = priorityQueue.poll();

for (Edge edge : actualVertex.getAdjs()) {

// get the adjacents

Node v = edge.getAdjacent();

if (!v.isVisited()) {

int newDistance = actualVertex.getDistance() + edge.getCost();

if (newDistance < v.getDistance()) {

priorityQueue.remove(v);

v.setDistance(newDistance);

v.setParent(actualVertex);

priorityQueue.add(v);

}

}

}

actualVertex.setVisited(true);

}

}

public List<Node> getShortestPathTo(Node targetVertex) {

List<Node> path = new ArrayList<>();

for (Node vertex = targetVertex; vertex != null; vertex = vertex.getParent()) {

path.add(vertex);

}

Collections.reverse(path);

return path;

}

}

///////////class Node////////////////////////////////////

import java.util.ArrayList;

public class Node implements Comparable<Node> {

private int name;

private boolean visited;

private int distance = Integer.MAX_VALUE;

private ArrayList<Edge> adjs = new ArrayList<>();

private Node parent;

public Node() {

}

public Node(int name) {

this.name = name;

}

public ArrayList<Edge> getAdjs() {

return adjs;

}

public void setAdjs(ArrayList<Edge> adjs) {

this.adjs = adjs;

}

public Node getParent() {

return parent;

}

public void setParent(Node parent) {

this.parent = parent;

}

public int getName() {

return name;

}

public void setName(int name) {

this.name = name;

}

public boolean isVisited() {

return visited;

}

public void setVisited(boolean visited) {

this.visited = visited;

}

public int getDistance() {

return distance;

}

public void setDistance(int distance) {

this.distance = distance;

}

@Override

public String toString() {

return " [name=" + name + ", visited=" + visited + ", distance=" + distance + ", adjs=" + adjs + ", parent="

+ parent + "]->";

}

@Override

public int compareTo(Node o) {

return (int) (this.distance - o.getDistance());

}

}