-
Notifications
You must be signed in to change notification settings - Fork 5
/
Prim.java
executable file
·120 lines (108 loc) · 2.98 KB
/
Prim.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
package com.vee.algorithms.graph;
import java.io.File;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import com.vee.algorithms.datastructures.Edge;
public class Prim {
private Map<Integer,List<Edge>> adjList;
int startVertex;
private static class HeapVertex {
double score;
int id;
HeapVertex(int id, double score) {
this.id = id;
this.score = score;
}
@Override
public boolean equals(Object h) {
return ((HeapVertex) h).id == id;
}
}
private void initAddVertex(int from, int to, double weight) {
if (adjList.get(from) == null) {
List<Edge> adj = new ArrayList<Edge>();
adj.add(new Edge(to, weight));
adjList.put(from, adj);
} else {
adjList.get(from).add(new Edge(to, weight));
}
}
private void init(String pathName) {
adjList = new HashMap<Integer, List<Edge>>();
try {
Scanner scanner = new Scanner(new File(pathName));
scanner.nextLine();
while (scanner.hasNextLine()) {
String s = scanner.nextLine();
String num[] = s.split("\\s");
int from = Integer.parseInt(num[0]);
int to = Integer.parseInt(num[1]);
double weight = Double.parseDouble(num[2]);
initAddVertex(from, to, weight);
initAddVertex(to, from, weight);
}
} catch (Exception e) {
e.printStackTrace();
}
}
public long calculate() {
PriorityQueue<HeapVertex> heap = new PriorityQueue<HeapVertex>(
adjList.size(),
new Comparator<HeapVertex>() {
public int compare(HeapVertex o1, HeapVertex o2) {
return Double.compare(o1.score, o2.score);
}
});
Map<Integer, Double> weights= new HashMap<Integer, Double>();
for (Integer v : adjList.keySet()) {
heap.add(new HeapVertex(v, Double.MAX_VALUE));
weights.put(v, Double.MAX_VALUE);
}
HeapVertex s = heap.poll();
startVertex = s.id;
s.score = Integer.MIN_VALUE;
heap.offer(s);
weights.put(startVertex, Double.MIN_VALUE);
Set<Integer> traversed = new HashSet<Integer>();
while (!heap.isEmpty()) {
HeapVertex u = heap.poll();
System.out.println(u.id + " " + weights.get(u.id));
traversed.add(u.id); //add to MST
for (Edge e : adjList.get(u.id)) { //update scores/weights
if (traversed.contains(e.getTo())) {
continue;
}
if (weights.get(e.getTo()).compareTo(e.getWeight()) > 0) {
weights.put(e.getTo(), e.getWeight());
HeapVertex v = new HeapVertex(e.getTo(), e.getWeight());
heap.remove(v);
heap.offer(v);
}
}
}
long sumOfWeights = 0;
weights.remove(startVertex);
for (Double w : weights.values()) {
sumOfWeights += w;
}
return sumOfWeights;
}
public static Prim build(String fileName) {
Prim p = new Prim();
p.init(fileName);
return p;
}
public static void main(String[] args) {
long sum = Prim
.build("/home/vee/workspace/data/coursera/prim-edges.txt")
.calculate();
System.out.println(sum);
}
}