-
Notifications
You must be signed in to change notification settings - Fork 0
/
Kruskals.java
177 lines (155 loc) · 4.91 KB
/
Kruskals.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package com.dsa.project5;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
/**
* Kruskal algorithm implementation to get a minimum spanning tree among the cities of Texas
* @author Anshul Pardhi
*
*/
public class Kruskals {
private static final String DELIMITER = ",";
private static HashMap<String, Integer> cityMap = new HashMap<>(); //Stores every city name and maps it to a unique integral value
//because union and find of DisjSets require an integer argument
private static List<List<Edge>> edges = new LinkedList<List<Edge>>(); //Stores all the edges of the graph from the adjacency list
private static List<Edge> mstEdges = new ArrayList<>(); //Stores all the MST edges
private static int NUM_VERTICES; //Total vertices of the graph
/**
* Inner class to represent an edge of the graph
* @author Anshul Pardhi
*
*/
private static class Edge {
String startCity;
String endCity;
int distance;
Edge(String startCity, String endCity, int distance) {
this.startCity = startCity;
this.endCity = endCity;
this.distance = distance;
}
}
/**
* Reads a file to get dictionary words
* @param filePath the file path
* @return a BufferedReader object
* @throws FileNotFoundException
*/
public static BufferedReader readFile(String filePath) throws FileNotFoundException {
InputStream fis = new FileInputStream(filePath);
InputStreamReader isr = new InputStreamReader(fis, Charset.forName("UTF-8"));
return new BufferedReader(isr);
}
/**
* Parses CSV to create a list of edges and a map
* @param br Input buffered reader object
* @throws IOException
*/
public void insert(BufferedReader br) throws IOException {
String line;
int count = 0;
while ((line = br.readLine()) != null) {
String[] currLineArr = line.split(DELIMITER);
int len = currLineArr.length;
if(len <= 0) {
break;
}
List<Edge> list = new LinkedList<>();
String initCity = currLineArr[0];
cityMap.put(initCity, count);
for(int i = 1; i < len; i += 2) {
Edge edge = new Edge(initCity, currLineArr[i], Integer.parseInt(currLineArr[i + 1])); //Create a new edge
list.add(edge);
}
edges.add(list);
count++;
}
NUM_VERTICES = cityMap.size();
}
/**
* Kruskal algorithm implementation using Priority Queue and Disjoint Set
*/
public void kruskal() {
int edgesAccepted = 0;
DisjSets ds = new DisjSets(NUM_VERTICES);
//Create a priority queue and sort it on the basis of distances
PriorityQueue<Edge> pq = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge e1, Edge e2) {
return e1.distance - e2.distance;
}
});
getEdges(pq); //Populate the priority queue
Edge e;
while(edgesAccepted < NUM_VERTICES - 1) {
e = pq.poll(); //Get the edge with minimum distance
int startParent = ds.find(cityMap.get(e.startCity));
int endParent = ds.find(cityMap.get(e.endCity));
if(startParent != endParent) {
//New edge for spanning tree found!
edgesAccepted++;
ds.union(startParent, endParent);
mstEdges.add(e); //Add the edge to MST
}
}
}
/**
* Prints the generated Minimum Spanning Tree
*/
private void printMST() {
int totalDistance = 0;
int len = mstEdges.size();
for(int i=0; i<len; i++) {
totalDistance += mstEdges.get(i).distance;
System.out.println(mstEdges.get(i).startCity + " -> " + mstEdges.get(i).endCity + " " + mstEdges.get(i).distance);
}
System.out.println("Total Distance: " + totalDistance);
}
/**
* Populate the priority queue with unique edges
* @param pq priority queue to populate
*/
private void getEdges(PriorityQueue<Edge> pq) {
int rows = edges.size();
for(int i=0; i<rows; i++) {
int cols = edges.get(i).size();
for(int j=0; j<cols; j++) {
Edge edge = edges.get(i).get(j);
Edge reverseEdge = new Edge(edge.endCity, edge.startCity, edge.distance);
if(!pq.contains(reverseEdge)) {
//Only add unique edges
pq.offer(edge);
}
}
}
}
public static void main(String[] args) {
Kruskals k = new Kruskals();
try {
//Change the file path to your file location
String filePath = "texas_cities.csv";
BufferedReader br = readFile(filePath);
k.insert(br); //Parse CSV, create edges and form a graph
br.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
//Kruskal algorithm to find the minimum spanning tree
k.kruskal();
k.printMST(); //Print the generated Minimum Spanning Tree
}
}