-
-
Save tejasri-v/50a9326e11d642b1eba03b5f8363a7bc to your computer and use it in GitHub Desktop.
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
In this problem you will implement Dijkstra’s algorithm to find shortest paths between pairs of cities on a map. We are providing a GUI that lets you visualize the map and the path your algorithm finds between two cities. | |
Before you start: | |
Examine the Codio directory. You will find the file cityxy.txt which contains a list of cities and their (X,Y) coordinates on the map. These are the vertices in the graph. The file citypairs.txt lists direct, connections between pairs of cities. These links are bidirectional, if you can go from NewYork to Boston, you can go from Boston to NewYork. These are the edges of the graph. | |
Compile all Java sources and run the program Display. At this point, click on the “Box URL” button along the Codio tool bar at the top of your screen. This should bring up a view of the computer’s actual desktop screen. Inside, a window will have appeared with your running program that displays the map. You will notice that clicking on “Compute All Euclidean Distances” does nothing and that “Draw Dijkstra’s Path” will throw a null pointer exception on the terminal tab. You will have to implement these methods yourself. | |
You can switch between this Virtual Desktop tab and any of your other tabs freely. Make sure you quit the Java program before running it again. You can do this by either clicking the small x at the top of the java application in the virtual desktop window or by ctrl^c’ing the program from terminal. | |
Carefully read through the classes Vertex.java and Edge.java, which represent the vertices and edges of a graph. You will not have to modify these classes for the assignment, but you need to understand how the graph is represented and what information is associated with each vertex and edge. | |
You will only have to modify Dijkstra.java, which represents a graph and will contain your implementation of Dijkstra’s algorithm. You will need to use the instance variable vertexNames, which contains a mapping from city names to Vertex objects after the graph is read from the data files. The main method of Dijkstra illustrates how the class is used by the GUI and might be useful for testing your implementation on the command line. | |
Implement the method computeAllEuclideanDistances() which should compute the euclidean distance between all cities that have a direct link and set the weights for the corresponding edges in the graph. Once this works correctly, the correct distances should be displayed in the GUI when clicking on "Compute All Euclidean Distances". | |
In the method doDijkstra(String s), implement Dijkstra’s algorithm starting at the city with name s. Use the distances associated with the edges. The method should update the distance and prev instance variables of the Vertex objects. You should not use a priority queue to store vertices that still need to be visited. Instead, keep these vertices on a List and scan through the entire list to find the minimum. We are making this simplification (at the expense of runtime) because java.util.PriorityQueue does not support the decreaseKey operation. | |
Implement the method getDijkstraPath(String s, String t), which uses the distance and prev instance variables of the Vertex objects to find the shortest path between s and t. This method should be called only after doDijkstra(String s) has been called with the start city. The resulting path should be returned as a list of Edge objects. Once this works correctly, you should be able to compute and display paths in the GUI. | |
Note: Your program must work for repeated runs of dijkstra’s algorithms on different city pairs. To make sure that your program does this, be sure that you reinitialize the bookkeeping fields (known, prev, and distance) in the vertices stored in vertexNames at the beginning of each run of doDijkstra. |
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
Vancouver,Calgary,100 | |
Vancouver,Seattle,100 | |
Calgary,Winnipeg,100 | |
Calgary,Helena,100 | |
Calgary,Seattle,100 | |
Winnipeg,Helena,100 | |
Winnipeg,Duluth,100 | |
Winnipeg,SaultSaintMarie,100 | |
SaultSaintMarie,Duluth,100 | |
SaultSaintMarie,Toronto,100 | |
SaultSaintMarie,Montreal,100 | |
Toronto,Montreal,100 | |
Toronto,Pittsburgh,100 | |
Montreal,Boston,100 | |
Montreal,NewYork,100 | |
Seattle,Helena,100 | |
Seattle,Portland,100 | |
Helena,Duluth,100 | |
Helena,SaltLakeCity,100 | |
Helena,Denver,100 | |
Helena,Omaha,100 | |
Duluth,Omaha,100 | |
Duluth,Chicago,100 | |
Chicago,Pittsburgh,100 | |
Chicago,SaintLouis,100 | |
Chicago,Omaha,100 | |
Pittsburgh,NewYork,100 | |
Pittsburgh,Washington,100 | |
NewYork,Washington,100 | |
NewYork,Boston,100 | |
Portland,SanFrancisco,100 | |
Portland,SaltLakeCity,100 | |
SanFrancisco,SaltLakeCity,100 | |
SanFrancisco,LosAngeles,100 | |
LosAngeles,LasVegas,100 | |
LosAngeles,Phoenix,100 | |
SaltLakeCity,Denver,100 | |
SaltLakeCity,LasVegas,100 | |
Denver,SantaFe,100 | |
Denver,Phoenix,100 | |
Denver,Omaha,100 | |
Denver,KansasCity,100 | |
KansasCity,SaintLouis,100 | |
KansasCity,OklahomaCity,100 | |
SaintLouis,Nashville,100 | |
Nashville,Raleigh,100 | |
Nashville,Atlanta,100 | |
Washington,Raleigh,100 | |
Raleigh,Atlanta,100 | |
Raleigh,Charleston,100 | |
Atlanta,Miami,100 | |
Atlanta,NewOrleans,100 | |
Charleston,Miami,100 | |
Miami,NewOrleans,100 | |
NewOrleans,LittleRock,100 | |
NewOrleans,Houston,100 | |
Houston,Dallas,100 | |
Dallas,LittleRock,100 | |
Dallas,ElPaso,100 | |
ElPaso,LosAngeles,100 | |
ElPaso,SantaFe,100 | |
Atlanta,Charleston,100 | |
SantaFe,OklahomaCity,100 | |
SantaFe,Phoenix,100 | |
LittleRock,Nashville,100 | |
LittleRock,OklahomaCity,100 | |
LittleRock,SaintLouis,100 |
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
Vancouver,80,78 | |
Calgary,180,67 | |
Winnipeg,360,75 | |
Montreal,696,66 | |
SaultSaintMarie,550,120 | |
Seattle,76,123 | |
Toronto,630,130 | |
Boston,750,110 | |
Portland,60,164 | |
Helena,260,170 | |
Duluth,440,166 | |
NewYork,700,165 | |
SaltLakeCity,200,270 | |
Denver,300,290 | |
Omaha,420,240 | |
Chicago,540,215 | |
Pittsburgh,640,200 | |
Washington,716,240 | |
SanFrancisco,50,315 | |
KansasCity,435,280 | |
SaintLouis,500,300 | |
Raleigh,700,285 | |
OklahomaCity,420,340 | |
LittleRock,490,360 | |
Nashville,580,330 | |
LasVegas,160,350 | |
SantaFe,300,360 | |
Atlanta,640,360 | |
Charleston,700,380 | |
LosAngeles,111,395 | |
Phoenix,220,390 | |
ElPaso,300,425 | |
Dallas,440,415 | |
Houston,470,450 | |
NewOrleans,550,440 | |
Miami,700,460 |
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.Collection; | |
import java.util.HashMap; | |
import java.util.LinkedList; | |
import java.util.List; | |
import java.util.Map; | |
import java.io.IOException; | |
import java.io.FileReader; | |
import java.io.BufferedReader; | |
import java.lang.Math; | |
public class Dijkstra { | |
// Keep a fast index to nodes in the map | |
private Map<String, Vertex> vertexNames; | |
/** | |
* Construct an empty Dijkstra with a map. The map's key is the name of a vertex | |
* and the map's value is the vertex object. | |
*/ | |
public Dijkstra() { | |
vertexNames = new HashMap<String, Vertex>(); | |
} | |
public Map<String, Vertex> getVertexMap(){ | |
return vertexNames; | |
} | |
public void setVertexMap(Map<String, Vertex> vertexNames){ | |
this.vertexNames = vertexNames; | |
} | |
/** | |
* Adds a vertex to the dijkstra. Throws IllegalArgumentException if two vertices | |
* with the same name are added. | |
* | |
* @param v | |
* (Vertex) vertex to be added to the dijkstra | |
*/ | |
public void addVertex(Vertex v) { | |
if (vertexNames.containsKey(v.name)) | |
throw new IllegalArgumentException("Cannot create new vertex with existing name."); | |
vertexNames.put(v.name, v); | |
} | |
/** | |
* Gets a collection of all the vertices in the dijkstra | |
* | |
* @return (Collection<Vertex>) collection of all the vertices in the dijkstra | |
*/ | |
public Collection<Vertex> getVertices() { | |
return vertexNames.values(); | |
} | |
/** | |
* Gets the vertex object with the given name | |
* | |
* @param name | |
* (String) name of the vertex object requested | |
* @return (Vertex) vertex object associated with the name | |
*/ | |
public Vertex getVertex(String name) { | |
return vertexNames.get(name); | |
} | |
/** | |
* Adds a directed edge from vertex u to vertex v | |
* | |
* @param nameU | |
* (String) name of vertex u | |
* @param nameV | |
* (String) name of vertex v | |
* @param cost | |
* (double) cost of the edge between vertex u and v | |
*/ | |
public void addEdge(String nameU, String nameV, Double cost) { | |
if (!vertexNames.containsKey(nameU)) | |
throw new IllegalArgumentException(nameU + " does not exist. Cannot create edge."); | |
if (!vertexNames.containsKey(nameV)) | |
throw new IllegalArgumentException(nameV + " does not exist. Cannot create edge."); | |
Vertex sourceVertex = vertexNames.get(nameU); | |
Vertex targetVertex = vertexNames.get(nameV); | |
Edge newEdge = new Edge(sourceVertex, targetVertex, cost); | |
sourceVertex.addEdge(newEdge); | |
} | |
/** | |
* Adds an undirected edge between vertex u and vertex v by adding a directed | |
* edge from u to v, then a directed edge from v to u | |
* | |
* @param nameU | |
* (String) name of vertex u | |
* @param nameV | |
* (String) name of vertex v | |
* @param cost | |
* (double) cost of the edge between vertex u and v | |
*/ | |
public void addUndirectedEdge(String nameU, String nameV, double cost) { | |
addEdge(nameU, nameV, cost); | |
addEdge(nameV, nameU, cost); | |
} | |
// STUDENT CODE STARTS HERE | |
/** | |
* Computes the euclidean distance between two points as described by their | |
* coordinates | |
* | |
* @param ux | |
* (double) x coordinate of point u | |
* @param uy | |
* (double) y coordinate of point u | |
* @param vx | |
* (double) x coordinate of point v | |
* @param vy | |
* (double) y coordinate of point v | |
* @return (double) distance between the two points | |
*/ | |
public double computeEuclideanDistance(double ux, double uy, double vx, double vy) { | |
// TODO | |
return Math.sqrt(Math.pow(uy - vy, 2) + Math.pow(ux - vx, 2)); // Replace this | |
} | |
/** | |
* Calculates the euclidean distance for all edges in the map using the | |
* computeEuclideanCost method. | |
*/ | |
public void computeAllEuclideanDistances() { | |
// TODO | |
for(Map.Entry vertex : vertexNames.entrySet()){ | |
Vertex v = (Vertex)vertex.getValue(); | |
for(Edge edge : v.adjacentEdges){ | |
edge.distance = computeEuclideanDistance(edge.source.x, edge.source.y, edge.target.x, edge.target.y); | |
} | |
} | |
} | |
/** | |
* Dijkstra's Algorithm. | |
* | |
* @param s | |
* (String) starting city name | |
*/ | |
public void doDijkstra(String s) { | |
// TODO | |
LinkedList<Vertex> vertices = new LinkedList<>(); | |
for(Vertex vertex : getVertices()){ | |
vertex.known = false; | |
vertex.prev = null; | |
vertex.distance = Double.POSITIVE_INFINITY; | |
} | |
Vertex source = vertexNames.get(s); | |
source.known = true; | |
source.distance = 0.0; | |
vertices.add(source); | |
Vertex target; | |
while(!vertices.isEmpty()){ | |
Vertex low = vertices.getFirst(); | |
for(Vertex vertex : vertices){ | |
if(vertex.distance < low.distance){ | |
low = vertex; | |
} | |
} | |
vertices.remove(low); | |
source = low; | |
source.known = true; | |
for(Edge x : source.adjacentEdges){ | |
target = x.target; | |
if((source.distance + x.distance < target.distance) && !target.known){ | |
target.distance = x.distance + source.distance; | |
target.prev = source; | |
vertices.add(target); | |
} | |
} | |
} | |
} | |
/** | |
* Returns a list of edges for a path from city s to city t. This will be the | |
* shortest path from s to t as prescribed by Dijkstra's algorithm | |
* | |
* @param s | |
* (String) starting city name | |
* @param t | |
* (String) ending city name | |
* @return (List<Edge>) list of edges from s to t | |
*/ | |
public List<Edge> getDijkstraPath(String s, String t) { | |
doDijkstra(s); | |
Vertex target = vertexNames.get(t); | |
LinkedList<Edge> ans = new LinkedList<>(); | |
while(target.prev != null){ | |
ans.addFirst(new Edge(target.prev, target, computeEuclideanDistance(target.prev.x, target.prev.y, target.x, target.y))); | |
target = target.prev; | |
} | |
double dist = ans.stream().mapToDouble(x -> x.distance).sum(); | |
//System.out.println(ans); | |
System.out.println("Total distance is " + dist); | |
// TODO | |
return ans; // Replace this | |
} | |
// STUDENT CODE ENDS HERE | |
/** | |
* Prints out the adjacency list of the dijkstra for debugging | |
*/ | |
public void printAdjacencyList() { | |
for (String u : vertexNames.keySet()) { | |
StringBuilder sb = new StringBuilder(); | |
sb.append(u); | |
sb.append(" -> [ "); | |
for (Edge e : vertexNames.get(u).adjacentEdges) { | |
sb.append(e.target.name); | |
sb.append("("); | |
sb.append(e.distance); | |
sb.append(") "); | |
} | |
sb.append("]"); | |
System.out.println(sb.toString()); | |
} | |
} | |
/** | |
* A main method that illustrates how the GUI uses Dijkstra.java to | |
* read a map and represent it as a graph. | |
* You can modify this method to test your code on the command line. | |
*/ | |
public static void main(String[] argv) throws IOException { | |
String vertexFile = "cityxy.txt"; | |
String edgeFile = "citypairs.txt"; | |
Dijkstra dijkstra = new Dijkstra(); | |
String line; | |
// Read in the vertices | |
BufferedReader vertexFileBr = new BufferedReader(new FileReader(vertexFile)); | |
while ((line = vertexFileBr.readLine()) != null) { | |
String[] parts = line.split(","); | |
if (parts.length != 3) { | |
vertexFileBr.close(); | |
throw new IOException("Invalid line in vertex file " + line); | |
} | |
String cityname = parts[0]; | |
int x = Integer.valueOf(parts[1]); | |
int y = Integer.valueOf(parts[2]); | |
Vertex vertex = new Vertex(cityname, x, y); | |
dijkstra.addVertex(vertex); | |
} | |
vertexFileBr.close(); | |
BufferedReader edgeFileBr = new BufferedReader(new FileReader(edgeFile)); | |
while ((line = edgeFileBr.readLine()) != null) { | |
String[] parts = line.split(","); | |
if (parts.length != 3) { | |
edgeFileBr.close(); | |
throw new IOException("Invalid line in edge file " + line); | |
} | |
dijkstra.addUndirectedEdge(parts[0], parts[1], Double.parseDouble(parts[2])); | |
} | |
edgeFileBr.close(); | |
// Compute distances. | |
// This is what happens when you click on the "Compute All Euclidean Distances" button. | |
dijkstra.computeAllEuclideanDistances(); | |
// print out an adjacency list representation of the graph | |
dijkstra.printAdjacencyList(); | |
// This is what happens when you click on the "Draw Dijkstra's Path" button. | |
// In the GUI, these are set through the drop-down menus. | |
String startCity = "SanFrancisco"; | |
String endCity = "Boston"; | |
dijkstra.doDijkstra(startCity); | |
// Get weighted shortest path between start and end city. | |
List<Edge> path = dijkstra.getDijkstraPath(startCity, endCity); | |
System.out.print("Shortest path between "+startCity+" and "+endCity+": "); | |
System.out.println(path); | |
} | |
} |
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.awt.BasicStroke; | |
import java.awt.Color; | |
import java.awt.Desktop; | |
import java.awt.Dimension; | |
import java.awt.EventQueue; | |
import java.awt.Font; | |
import java.awt.Graphics; | |
import java.awt.Graphics2D; | |
import java.awt.GridBagConstraints; | |
import java.awt.GridBagLayout; | |
import java.awt.Insets; | |
import java.awt.RenderingHints; | |
import java.awt.Stroke; | |
import java.awt.event.ItemEvent; | |
import java.awt.event.ItemListener; | |
import java.awt.event.MouseAdapter; | |
import java.awt.event.MouseEvent; | |
import java.io.BufferedReader; | |
import java.io.FileReader; | |
import java.io.IOException; | |
import java.net.URI; | |
import java.net.URISyntaxException; | |
import java.util.HashMap; | |
import java.util.LinkedList; | |
import java.util.ArrayList; | |
import java.util.List; | |
import java.util.Collections; | |
import javax.swing.DefaultComboBoxModel; | |
import javax.swing.JButton; | |
import javax.swing.JCheckBox; | |
import javax.swing.JComboBox; | |
import javax.swing.JFrame; | |
import javax.swing.JLabel; | |
import javax.swing.JPanel; | |
import javax.swing.JSeparator; | |
import javax.swing.JTextField; | |
import javax.swing.UIManager; | |
import javax.swing.border.EmptyBorder; | |
@SuppressWarnings("serial") | |
public class Display extends JFrame { | |
private JPanel contentPane; | |
private JTextField txtCityxytxt; | |
private JTextField txtCitypairstxt; | |
private GraphPanel panel; | |
private JComboBox<String> weightedStartCityComboBox; | |
private JComboBox<String> weightedEndCityComboBox; | |
private Dijkstra dijkstra; | |
private JCheckBox chckbxShowEdgeWeights; | |
/** | |
* Launch the application. | |
*/ | |
public static void main(String[] args) { | |
EventQueue.invokeLater(new Runnable() { | |
public void run() { | |
try { | |
Display frame = new Display(); | |
frame.setVisible(true); | |
} catch (Exception e) { | |
e.printStackTrace(); | |
} | |
} | |
}); | |
} | |
public static Dijkstra readGraph(String vertexFile, String edgeFile) { | |
Dijkstra dijkstra = new Dijkstra(); | |
try { | |
String line; | |
// Read in the vertices | |
BufferedReader vertexFileBr = new BufferedReader(new FileReader(vertexFile)); | |
while ((line = vertexFileBr.readLine()) != null) { | |
String[] parts = line.split(","); | |
if (parts.length != 3) { | |
vertexFileBr.close(); | |
throw new IOException("Invalid line in vertex file " + line); | |
} | |
String cityname = parts[0]; | |
int x = Integer.valueOf(parts[1]); | |
int y = Integer.valueOf(parts[2]); | |
Vertex vertex = new Vertex(cityname, x, y); | |
dijkstra.addVertex(vertex); | |
} | |
vertexFileBr.close(); | |
// Now read in the edges | |
BufferedReader edgeFileBr = new BufferedReader(new FileReader(edgeFile)); | |
while ((line = edgeFileBr.readLine()) != null) { | |
String[] parts = line.split(","); | |
if (parts.length != 3) { | |
edgeFileBr.close(); | |
throw new IOException("Invalid line in edge file " + line); | |
} | |
dijkstra.addUndirectedEdge(parts[0], parts[1], Double.parseDouble(parts[2])); | |
} | |
edgeFileBr.close(); | |
} catch (IOException e) { | |
System.err.println("Could not read the dijkstra: " + e); | |
return null; | |
} | |
return dijkstra; | |
} | |
/** | |
* Create the frame. | |
*/ | |
public Display() { | |
setTitle("Data Structures Dijkstra Visualizer"); | |
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); | |
setBounds(50, 50, 900, 700); | |
setMinimumSize(new Dimension(800, 600)); | |
contentPane = new JPanel(); | |
contentPane.setBorder(new EmptyBorder(5, 5, 5, 5)); | |
setContentPane(contentPane); | |
GridBagLayout gbl_contentPane = new GridBagLayout(); | |
gbl_contentPane.columnWidths = new int[] { 0, 0, 0, 0, 0, 0, 0 }; | |
gbl_contentPane.rowHeights = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0 }; | |
gbl_contentPane.columnWeights = new double[] { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, Double.MIN_VALUE }; | |
gbl_contentPane.rowWeights = new double[] { 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, Double.MIN_VALUE }; | |
contentPane.setLayout(gbl_contentPane); | |
dijkstra = readGraph("cityxy.txt", "citypairs.txt"); | |
panel = new GraphPanel(dijkstra); | |
GridBagConstraints gbc_panel = new GridBagConstraints(); | |
gbc_panel.gridwidth = 7; | |
gbc_panel.insets = new Insets(0, 0, 7, 0); | |
gbc_panel.fill = GridBagConstraints.BOTH; | |
gbc_panel.gridx = 0; | |
gbc_panel.gridy = 0; | |
contentPane.add(panel, gbc_panel); | |
JSeparator separator = new JSeparator(); | |
separator.setBackground(Color.WHITE); | |
separator.setForeground(Color.GRAY); | |
GridBagConstraints gbc_separator = new GridBagConstraints(); | |
gbc_separator.fill = GridBagConstraints.BOTH; | |
gbc_separator.gridwidth = 6; | |
gbc_separator.insets = new Insets(0, 0, 5, 0); | |
gbc_separator.gridx = 0; | |
gbc_separator.gridy = 2; | |
contentPane.add(separator, gbc_separator); | |
chckbxShowEdgeWeights = new JCheckBox("Show Edge Weights"); | |
chckbxShowEdgeWeights.addItemListener(new ItemListener() { | |
public void itemStateChanged(ItemEvent e) { | |
repaint(); | |
} | |
}); | |
JLabel lblReloadGraph = new JLabel("Load / Reload Dijkstra"); | |
GridBagConstraints gbc_lblReloadGraph = new GridBagConstraints(); | |
gbc_lblReloadGraph.anchor = GridBagConstraints.EAST; | |
gbc_lblReloadGraph.insets = new Insets(0, 0, 5, 5); | |
gbc_lblReloadGraph.gridx = 0; | |
gbc_lblReloadGraph.gridy = 3; | |
contentPane.add(lblReloadGraph, gbc_lblReloadGraph); | |
txtCityxytxt = new JTextField(); | |
txtCityxytxt.setText("cityxy.txt"); | |
GridBagConstraints gbc_txtCityxytxt = new GridBagConstraints(); | |
gbc_txtCityxytxt.gridwidth = 2; | |
gbc_txtCityxytxt.insets = new Insets(0, 0, 5, 5); | |
gbc_txtCityxytxt.fill = GridBagConstraints.HORIZONTAL; | |
gbc_txtCityxytxt.gridx = 1; | |
gbc_txtCityxytxt.gridy = 3; | |
contentPane.add(txtCityxytxt, gbc_txtCityxytxt); | |
txtCityxytxt.setColumns(10); | |
txtCitypairstxt = new JTextField(); | |
txtCitypairstxt.setText("citypairs.txt"); | |
GridBagConstraints gbc_txtCitypairstxt = new GridBagConstraints(); | |
gbc_txtCitypairstxt.gridwidth = 2; | |
gbc_txtCitypairstxt.insets = new Insets(0, 0, 5, 5); | |
gbc_txtCitypairstxt.fill = GridBagConstraints.HORIZONTAL; | |
gbc_txtCitypairstxt.gridx = 3; | |
gbc_txtCitypairstxt.gridy = 3; | |
contentPane.add(txtCitypairstxt, gbc_txtCitypairstxt); | |
txtCitypairstxt.setColumns(10); | |
JButton btnReloadGraph = new JButton("Load / Reset"); | |
GridBagConstraints gbc_btnReloadGraph = new GridBagConstraints(); | |
gbc_btnReloadGraph.fill = GridBagConstraints.HORIZONTAL; | |
gbc_btnReloadGraph.insets = new Insets(0, 0, 5, 0); | |
gbc_btnReloadGraph.gridx = 5; | |
gbc_btnReloadGraph.gridy = 3; | |
contentPane.add(btnReloadGraph, gbc_btnReloadGraph); | |
btnReloadGraph.addMouseListener(new MouseAdapter() { | |
@Override | |
public void mouseReleased(MouseEvent e) { | |
// update JPanel | |
updateGraphPanel(); | |
} | |
}); | |
JLabel lblEuclideanCosts = new JLabel("Euclidean Costs"); | |
GridBagConstraints gbc_lblEuclideanCosts = new GridBagConstraints(); | |
gbc_lblEuclideanCosts.anchor = GridBagConstraints.EAST; | |
gbc_lblEuclideanCosts.insets = new Insets(0, 0, 5, 5); | |
gbc_lblEuclideanCosts.gridx = 0; | |
gbc_lblEuclideanCosts.gridy = 4; | |
contentPane.add(lblEuclideanCosts, gbc_lblEuclideanCosts); | |
chckbxShowEdgeWeights.setSelected(true); | |
GridBagConstraints gbc_chckbxShowEdgeWeights = new GridBagConstraints(); | |
gbc_chckbxShowEdgeWeights.anchor = GridBagConstraints.EAST; | |
gbc_chckbxShowEdgeWeights.gridwidth = 4; | |
gbc_chckbxShowEdgeWeights.insets = new Insets(0, 0, 5, 5); | |
gbc_chckbxShowEdgeWeights.gridx = 1; | |
gbc_chckbxShowEdgeWeights.gridy = 4; | |
contentPane.add(chckbxShowEdgeWeights, gbc_chckbxShowEdgeWeights); | |
JButton btnComputeAllEuclidean = new JButton("Compute All Euclidean Distances"); | |
GridBagConstraints gbc_btnComputeAllEuclidean = new GridBagConstraints(); | |
gbc_btnComputeAllEuclidean.fill = GridBagConstraints.BOTH; | |
gbc_btnComputeAllEuclidean.insets = new Insets(0, 0, 5, 0); | |
gbc_btnComputeAllEuclidean.gridx = 5; | |
gbc_btnComputeAllEuclidean.gridy = 4; | |
contentPane.add(btnComputeAllEuclidean, gbc_btnComputeAllEuclidean); | |
btnComputeAllEuclidean.addMouseListener(new MouseAdapter() { | |
@Override | |
public void mouseReleased(MouseEvent e) { | |
panel.dijkstra.computeAllEuclideanDistances(); | |
repaint(); | |
} | |
}); | |
JLabel lblGetWeightedShortest_1 = new JLabel("Dijkstra's Algorithm"); | |
GridBagConstraints gbc_lblGetWeightedShortest_1 = new GridBagConstraints(); | |
gbc_lblGetWeightedShortest_1.anchor = GridBagConstraints.EAST; | |
gbc_lblGetWeightedShortest_1.insets = new Insets(0, 0, 5, 5); | |
gbc_lblGetWeightedShortest_1.gridx = 0; | |
gbc_lblGetWeightedShortest_1.gridy = 5; | |
contentPane.add(lblGetWeightedShortest_1, gbc_lblGetWeightedShortest_1); | |
JLabel lblStart_1 = new JLabel("Start"); | |
GridBagConstraints gbc_lblStart_1 = new GridBagConstraints(); | |
gbc_lblStart_1.insets = new Insets(0, 0, 5, 5); | |
gbc_lblStart_1.anchor = GridBagConstraints.EAST; | |
gbc_lblStart_1.gridx = 1; | |
gbc_lblStart_1.gridy = 5; | |
contentPane.add(lblStart_1, gbc_lblStart_1); | |
weightedStartCityComboBox = new JComboBox<>(); | |
weightedStartCityComboBox.setToolTipText(""); | |
GridBagConstraints gbc_weightedStartCityComboBox = new GridBagConstraints(); | |
gbc_weightedStartCityComboBox.insets = new Insets(0, 0, 5, 5); | |
gbc_weightedStartCityComboBox.fill = GridBagConstraints.HORIZONTAL; | |
gbc_weightedStartCityComboBox.gridx = 2; | |
gbc_weightedStartCityComboBox.gridy = 5; | |
contentPane.add(weightedStartCityComboBox, gbc_weightedStartCityComboBox); | |
JLabel lblEnd_1 = new JLabel("End"); | |
GridBagConstraints gbc_lblEnd_1 = new GridBagConstraints(); | |
gbc_lblEnd_1.insets = new Insets(0, 0, 5, 5); | |
gbc_lblEnd_1.anchor = GridBagConstraints.EAST; | |
gbc_lblEnd_1.gridx = 3; | |
gbc_lblEnd_1.gridy = 5; | |
contentPane.add(lblEnd_1, gbc_lblEnd_1); | |
weightedEndCityComboBox = new JComboBox<>(); | |
GridBagConstraints gbc_weightedEndCityComboBox = new GridBagConstraints(); | |
gbc_weightedEndCityComboBox.insets = new Insets(0, 0, 5, 5); | |
gbc_weightedEndCityComboBox.fill = GridBagConstraints.HORIZONTAL; | |
gbc_weightedEndCityComboBox.gridx = 4; | |
gbc_weightedEndCityComboBox.gridy = 5; | |
contentPane.add(weightedEndCityComboBox, gbc_weightedEndCityComboBox); | |
JButton btnDrawWeightedShortest = new JButton("Draw Dijkstra's Path"); | |
btnDrawWeightedShortest.setForeground(Color.GREEN); | |
GridBagConstraints gbc_btnDrawWeightedShortest = new GridBagConstraints(); | |
gbc_btnDrawWeightedShortest.fill = GridBagConstraints.HORIZONTAL; | |
gbc_btnDrawWeightedShortest.insets = new Insets(0, 0, 5, 0); | |
gbc_btnDrawWeightedShortest.gridx = 5; | |
gbc_btnDrawWeightedShortest.gridy = 5; | |
contentPane.add(btnDrawWeightedShortest, gbc_btnDrawWeightedShortest); | |
JLabel lblPanda = new JLabel("Panda 2016 <http://linanqiu.github.io/>"); | |
lblPanda.setForeground(UIManager.getColor("TextField.light")); | |
lblPanda.addMouseListener(new MouseAdapter() { | |
@Override | |
public void mouseReleased(MouseEvent e) { | |
try { | |
Desktop.getDesktop().browse(new URI("http://linanqiu.github.io/")); | |
} catch (IOException e1) { | |
// TODO Auto-generated catch block | |
e1.printStackTrace(); | |
} catch (URISyntaxException e1) { | |
// TODO Auto-generated catch block | |
e1.printStackTrace(); | |
} | |
} | |
}); | |
JSeparator separator_1 = new JSeparator(); | |
separator_1.setForeground(Color.GRAY); | |
separator_1.setBackground(Color.WHITE); | |
GridBagConstraints gbc_separator_1 = new GridBagConstraints(); | |
gbc_separator_1.fill = GridBagConstraints.BOTH; | |
gbc_separator_1.gridwidth = 6; | |
gbc_separator_1.insets = new Insets(0, 0, 5, 0); | |
gbc_separator_1.gridx = 0; | |
gbc_separator_1.gridy = 6; | |
contentPane.add(separator_1, gbc_separator_1); | |
GridBagConstraints gbc_lblPanda = new GridBagConstraints(); | |
gbc_lblPanda.gridwidth = 3; | |
gbc_lblPanda.anchor = GridBagConstraints.EAST; | |
gbc_lblPanda.gridx = 3; | |
gbc_lblPanda.gridy = 7; | |
contentPane.add(lblPanda, gbc_lblPanda); | |
btnDrawWeightedShortest.addMouseListener(new MouseAdapter() { | |
@Override | |
public void mouseReleased(MouseEvent e) { | |
String startCity = weightedStartCityComboBox.getItemAt(weightedStartCityComboBox.getSelectedIndex()); | |
String endCity = weightedEndCityComboBox.getItemAt(weightedEndCityComboBox.getSelectedIndex()); | |
System.out.println("Calculating shortest weighted path for " + startCity + " to " + endCity); | |
dijkstra.doDijkstra(startCity); | |
List<Edge> weightedPath = dijkstra.getDijkstraPath(startCity, endCity); | |
panel.overlayEdges.put("weighted", weightedPath); | |
repaint(); | |
} | |
}); | |
updateGraphPanel(); | |
} | |
private void updateGraphPanel() { | |
String vertexFile = txtCityxytxt.getText(); | |
String edgeFile = txtCitypairstxt.getText(); | |
dijkstra = readGraph(vertexFile, edgeFile); | |
panel.dijkstra = dijkstra; | |
System.out.println("Constructing new file from " + vertexFile + " and " + edgeFile); | |
System.out.println("Data read: " + panel.dijkstra.getVertices()); | |
List<String> cityNameList = new ArrayList<>(); | |
for (Vertex v : dijkstra.getVertices()) | |
cityNameList.add(v.name); | |
Collections.sort(cityNameList); | |
String[] cityNames = cityNameList.toArray(new String[cityNameList.size()]); | |
weightedStartCityComboBox.setModel(new DefaultComboBoxModel<>(cityNames)); | |
weightedEndCityComboBox.setModel(new DefaultComboBoxModel<>(cityNames)); | |
panel.overlayEdges.put("weighted", new LinkedList<Edge>()); | |
panel.overlayEdges.put("unweighted", new LinkedList<Edge>()); | |
panel.overlayEdges.put("mst", new LinkedList<Edge>()); | |
repaint(); | |
} | |
public class GraphPanel extends JPanel { | |
// dijkstra layout parameters | |
public static final int VERTEX_RADIUS = 10; | |
public static final int SPACE = 3; | |
public static final int MARGIN_X = 50; | |
public static final int MARGIN_Y = 50; | |
public static final int DEFAULT_THICKNESS = 1; | |
// scale factors | |
public float xFactor, yFactor; | |
public Dijkstra dijkstra; | |
public HashMap<String, List<Edge>> overlayEdges; | |
public GraphPanel(Dijkstra dijkstra) { | |
this.dijkstra = dijkstra; | |
overlayEdges = new HashMap<>(); | |
overlayEdges.put("weighted", new LinkedList<Edge>()); | |
overlayEdges.put("unweighted", new LinkedList<Edge>()); | |
overlayEdges.put("mst", new LinkedList<Edge>()); | |
} | |
public void paintComponent(Graphics g) { | |
// make everything smooth like butter | |
Graphics2D g2 = (Graphics2D) g; | |
g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); | |
g2.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_ON); | |
g2.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE); | |
g2.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY); | |
g2.setRenderingHint(RenderingHints.KEY_FRACTIONALMETRICS, RenderingHints.VALUE_FRACTIONALMETRICS_ON); | |
g2.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_QUALITY); | |
g2.setRenderingHint(RenderingHints.KEY_COLOR_RENDERING, RenderingHints.VALUE_COLOR_RENDER_QUALITY); | |
g2.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL, RenderingHints.VALUE_STROKE_PURE); | |
// scale the dijkstra | |
int minX = 0; | |
int maxX = 1; | |
int minY = 0; | |
int maxY = 1; | |
for (Vertex v : dijkstra.getVertices()) { | |
if (v.x < minX) | |
minX = v.x; | |
if (v.x > maxX) | |
maxX = v.x; | |
if (v.y < minY) | |
minY = v.y; | |
if (v.y > maxY) | |
maxY = v.y; | |
} | |
xFactor = (this.getBounds().width - 2 * MARGIN_X) / (float) (maxX - minX); | |
yFactor = (this.getBounds().height - 2 * MARGIN_Y) / (float) (maxY - minY); | |
super.paintComponent(g2); // paint the panel | |
try { | |
paintGraph(g2); // paint the dijkstra | |
} catch (NullPointerException e) { | |
e.printStackTrace(); | |
} | |
} | |
public void paintGraph(Graphics g) { | |
for (Vertex v : dijkstra.getVertices()) { | |
for (Edge edge : v.adjacentEdges) { | |
paintEdge(g, edge.source, edge.target, edge.distance, Color.LIGHT_GRAY, DEFAULT_THICKNESS, 255); | |
} | |
} | |
for (Vertex v : dijkstra.getVertices()) { | |
paintVertex(g, v); | |
} | |
for (String overlayType : overlayEdges.keySet()) { | |
if (overlayType.equals("unweighted")) { | |
for (Edge edge : overlayEdges.get(overlayType)) { | |
paintEdge(g, edge.source, edge.target, edge.distance, Color.RED, 8, 50); | |
} | |
} | |
if (overlayType.equals("weighted")) { | |
for (Edge edge : overlayEdges.get(overlayType)) { | |
paintEdge(g, edge.source, edge.target, edge.distance, Color.GREEN, 8, 50); | |
} | |
} | |
if (overlayType.equals("mst")) { | |
for (Edge edge : overlayEdges.get(overlayType)) { | |
paintEdge(g, edge.source, edge.target, edge.distance, Color.BLUE, 8, 50); | |
} | |
} | |
} | |
} | |
public void paintVertex(Graphics g, Vertex v) { | |
Graphics2D g2 = (Graphics2D) g; | |
int x = Math.round(xFactor * (float) v.x + (float) MARGIN_X); | |
int y = Math.round(yFactor * (float) v.y + (float) MARGIN_Y); | |
g2.setColor(Color.LIGHT_GRAY); | |
Stroke oldStroke = g2.getStroke(); | |
g2.setStroke(new BasicStroke(4)); | |
g2.drawOval(x - VERTEX_RADIUS / 2, y - VERTEX_RADIUS / 2, VERTEX_RADIUS, VERTEX_RADIUS); | |
g2.setStroke(oldStroke); | |
g2.setColor(Color.LIGHT_GRAY); | |
g2.fillOval(x - VERTEX_RADIUS / 2, y - VERTEX_RADIUS / 2, VERTEX_RADIUS, VERTEX_RADIUS); | |
g2.setColor(Color.DARK_GRAY); | |
g2.drawString(v.name, x - v.name.length() * 8 / 2, y + VERTEX_RADIUS / 2); | |
} | |
public void paintEdge(Graphics g, Vertex u, Vertex v, double weight, Color color, int thickness, int alpha) { | |
Graphics2D g2 = (Graphics2D) g; | |
int x1 = Math.round(xFactor * (float) u.x + (float) MARGIN_X); | |
int y1 = Math.round(yFactor * (float) u.y + (float) MARGIN_Y); | |
int x2 = Math.round(xFactor * (float) v.x + (float) MARGIN_X); | |
int y2 = Math.round(yFactor * (float) v.y + (float) MARGIN_Y); | |
g2.setColor(new Color(color.getRed(), color.getGreen(), color.getBlue(), alpha)); | |
Stroke oldStroke = g2.getStroke(); | |
g2.setStroke(new BasicStroke(thickness)); | |
g2.drawLine(x1, y1, x2, y2); | |
g2.setStroke(oldStroke); | |
if (chckbxShowEdgeWeights.isSelected()) { | |
Font oldFont = g2.getFont(); | |
g2.setFont(new Font("Helvetica", Font.PLAIN, 8)); | |
g2.setColor(Color.GRAY); | |
g2.drawString(String.format("%.1f", weight), (x1 + x2) / 2, (y1 + y2) / 2); | |
g2.setFont(oldFont); | |
} | |
} | |
} | |
} |
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
public class Edge { | |
public double distance; | |
public Vertex source; | |
public Vertex target; | |
public Edge(Vertex vertex1, Vertex vertex2, double weight) { | |
source = vertex1; | |
target = vertex2; | |
this.distance = weight; | |
} | |
public String toString() { | |
return source + " - " + target; | |
} | |
@Override | |
public boolean equals(Object o) { | |
if (this == o) { | |
return true; | |
} | |
if (o == null) { | |
return false; | |
} | |
if (!(o instanceof Edge)) { | |
return false; | |
} | |
Edge oEdge = (Edge) o; | |
return (source.equals(oEdge.source) && target.equals(oEdge.target) | |
&& distance == oEdge.distance) | |
|| (source.equals(oEdge.target) && target.equals(oEdge.source) | |
&& distance == oEdge.distance); | |
} | |
} |
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.LinkedList; | |
import java.util.List; | |
public class Vertex { | |
public String name; | |
public int x; | |
public int y; | |
public boolean known; | |
public double distance; // total distance from origin point | |
public Vertex prev; | |
public List<Edge> adjacentEdges; | |
public Vertex(String name, int x, int y) { | |
this.name = name; | |
this.x = x; | |
this.y = y; | |
// by default java sets uninitialized boolean to false and double to 0 | |
// hence known == false and dist == 0.0 | |
adjacentEdges = new LinkedList<Edge>(); | |
prev = null; | |
} | |
@Override | |
public int hashCode() { | |
// we assume that each vertex has a unique name | |
return name.hashCode(); | |
} | |
@Override | |
public boolean equals(Object o) { | |
if (this == o) { | |
return true; | |
} | |
if (o == null) { | |
return false; | |
} | |
if (!(o instanceof Vertex)) { | |
return false; | |
} | |
Vertex oVertex = (Vertex) o; | |
return name.equals(oVertex.name) && x == oVertex.x && y == oVertex.y; | |
} | |
public void addEdge(Edge edge) { | |
adjacentEdges.add(edge); | |
} | |
public String toString() { | |
return name + " (" + x + ", " + y + ")"; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment