Answer To: 2/26/2021 Project 2 https://canvas.pitt.edu/courses/81202/assignments/508595?module_item_id=...
Vaishnavi R answered on Mar 05 2021
ass2/Assignment/.classpath
ass2/Assignment/.project
Assignment
org.eclipse.jdt.core.javabuilder
org.eclipse.jdt.core.javanature
ass2/Assignment/.settings/org.eclipse.jdt.core.prefs
eclipse.preferences.version=1
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
org.eclipse.jdt.core.compiler.codegen.targetPlatform=15
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
org.eclipse.jdt.core.compiler.compliance=15
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
org.eclipse.jdt.core.compiler.debug.localVariable=generate
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
org.eclipse.jdt.core.compiler.problem.enablePreviewFeatures=disabled
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
org.eclipse.jdt.core.compiler.problem.reportPreviewFeatures=warning
org.eclipse.jdt.core.compiler.release=enabled
org.eclipse.jdt.core.compiler.source=15
ass2/Assignment/bin/analysis.class
ass2/Assignment/bin/Dijkstra.class
ass2/Assignment/bin/MinDist.class
ass2/Assignment/bin/PerformanceTest.class
ass2/Assignment/bin/Vertex.class
ass2/Assignment/src/analysis.java
ass2/Assignment/src/analysis.java
public class analysis {
private static final long MEGABYTE = 1024L * 1024L;
public static long bytesToMegabytes(long bytes) {
return bytes / MEGABYTE;
}
}
ass2/Assignment/src/Dijkstra.java
ass2/Assignment/src/Dijkstra.java
// THIS PROGRAM IS FOR DIJKSTRA ALGORITHM USING 2d array
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
//import jdk.javadoc.internal.doclets.toolkit.util.Utils.Pair;
public class Dijkstra
{
private PriorityQueue pq;
private Vertex vertices[];
// parent of node/vertex
private int path[];
// stores distance of src to all vertex
private int dist[];
// this method is for extracting the info from excel file
public static ArrayList file()
{
ArrayList myList = new ArrayList();
try
{
FileReader fr = null;
BufferedReader br = null;
String inputPath;
fr = new FileReader("E:\\vaishnavi\\greynodes\\assignments\\project2inputfile3-vocie1vd.csv");
br = new BufferedReader(fr);
String line = null;
line = br.readLine();
while(line!=null)
{
myList.add(line);
line = br.readLine();
}
} //try end
catch(IOException ioex)
{
System.out.print(ioex);
}
return myList;
}
// this method will take src and dest and run dijkstra algorithm
public void dijkstraAlgo(int sourceNode, int destinatioNode)
{
try {
// first add src to pq,
// pass (distance, vertex)
pq.add(new MinDist(0,sourceNode));
dist[sourceNode]=0;
while(!pq.isEmpty())
{
int p = pq.peek().getVertex();
dist[p] = pq.peek().getDist();
pq.remove();
if(p == destinatioNode)
{
break;
}
// search for adjacent elements
for(int i=0; i<427; i++)
{
if(vertices[p].matrix[i]!=Integer.MAX_VALUE)
{
if(dist[i]>dist[p]+vertices[p].matrix[i])
{
path[i] = p;
dist[i] = dist[p]+vertices[p].matrix[i];
pq.add(new MinDist(dist[i],i));
}
}
}
}
}
catch(ClassCastException c)
{
System.out.print(c);
}
}
// recursive funtion to print the path
public static void printPath(int path[], int i,Vertex ver[]) {
if(path[i] == -1) {
System.out.println(ver[i].nodeId + " "+ ver[i].name);
return;
}
printPath(path,path[i],ver);
System.out.println(ver[i].nodeId + " "+ ver[i].name);
}
public static void main(String[] args)
{
long startTime = System.nanoTime();
System.out.println("DIJKSTRA ALGORITHM USING 2D ARRAY");
ArrayList myList = file();
Dijkstra d = new Dijkstra();
d.dist = new int[427];
d.vertices = new Vertex[427];
d.path = new int[427];
for(int i=0; i<427; i++)
{
d.vertices[i]=null;
}
for(int i=0; i<427; i++)
{
d.path[i]=-1;
}
for(int i=0; i<427; i++)
{
d.dist[i]=Integer.MAX_VALUE;
}
int op=0;
for(int i=1; i {
String name="";
double x=0;
double y=0;
int nodeId = 0;
int distance=0;
int destination=0;
String line = myList.get(i);
String[] tokens = line.split(",");
int count=0;
for (String token : tokens)
{
count++;
if(count==1)
{
nodeId = Integer.parseInt(token);
}
else if(count==2)
{
destination = Integer.parseInt(token);
}
else if(count==3)
{
distance = Integer.parseInt(token);
}
else if(count==4)
{
x = Double.parseDouble(token.substring(2, token.length()));
}
else if(count==5)
{
y = Double.parseDouble(token.substring(0, token.length()-2));
}
else if(count==6)
{
name =token.substring(1,token.length());
name.concat(",");
}
else if(count==7)
{
name+=(token.substring(0, token.length()-1));
}
}
if(d.vertices[nodeId]==null)
{
Vertex v = new Vertex(name,x,y,nodeId);
v.addEdge(destination, distance);
d.vertices[nodeId]=v;
}
else
{
d.vertices[nodeId].addEdge(destination, distance);
}
}
// take input
int sourceNode;
int destinatioNode;
Scanner s = new Scanner(System.in);
sourceNode = s.nextInt();
destinatioNode = s.nextInt();
d.pq = new PriorityQueue(427, new MinDist());
d.dijkstraAlgo(sourceNode,destinatioNode);
// total distance from source to destination
System.out.println(d.dist[destinatioNode]);
// print path
printPath(d.path,destinatioNode,d.vertices);
long endTime = System.nanoTime();
System.out.println("Took "+(endTime - startTime) + " ns");
}
}
ass2/Assignment/src/MinDist.java
ass2/Assignment/src/MinDist.java
import java.util.*;
public class MinDist implements Comparator {
private int dist;
private int ver;
MinDist(){
dist = 0;
ver = 0;
}
// parameterised constructor
MinDist(int dist,int ver){
this.dist = dist;
this.ver = ver;
}
// method to give distance of vertex to src node
public int getDist() {
return dist;
}
// method to give current vertex
public int getVertex() {
return ver;
}
@Override
public int compare(MinDist o1, MinDist o2) {
if(o1.dist < o2.dist) return -1;
if(o1.dist > o2.dist) return 1;
return 0;
}
}
ass2/Assignment/src/PerformanceTest.java
ass2/Assignment/src/PerformanceTest.java
public class PerformanceTest
{
private static final long MEGABYTE = 1024L * 1024L;
public static long bytesToMegabytes(long bytes) {
return bytes / MEGABYTE;
}
}
ass2/Assignment/src/Vertex.java
ass2/Assignment/src/Vertex.java
public class Vertex {
String name;
double x;
double y;
int nodeId;
// every node has 1d array to store connections of a graph
int matrix[];
public Vertex(String name,double x,double y,int nodeId)
{
this.name = name;
this.x = x;
this.y = y;
this.nodeId = nodeId;
this.matrix = new int[427];
for (int i = 0; i < 427; i++)
matrix[i] = Integer.MAX_VALUE;
}
// creating adjaceny list
public void addEdge(int nodeId2,int weight)
{
matrix[nodeId2]= weight;
}
public void display()
{
System.out.println(this.nodeId);
System.out.println(this.name);
}
}
ass2/dijkstra2D.png
ass2/dijkstraLinkedList.png
ass2/DijkstraLL/.classpath
ass2/DijkstraLL/.project
DijkstraLL
org.eclipse.jdt.core.javabuilder
...