Instructions
Requirements and Specifications
Source Code
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Map;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
/**
* Your implementation of various different graph algorithms.
*
* @author YOUR NAME HERE
* @version 1.0
* @userid YOUR USER ID HERE (i.e. gburdell3)
* @GTID YOUR GT ID HERE (i.e. 900000000)
*
* Collaborators: LIST ALL COLLABORATORS YOU WORKED WITH HERE
*
* Resources: LIST ALL NON-COURSE RESOURCES YOU CONSULTED HERE
*/
public class GraphAlgorithms {
/**
* Performs a breadth first search (bfs) on the input graph, starting at
* the parameterized starting vertex.
*
* When exploring a vertex, explore in the order of neighbors returned by
* the adjacency list. Failure to do so may cause you to lose points.
*
* You may import/use java.util.Set, java.util.List, java.util.Queue, and
* any classes that implement the aforementioned interfaces, as long as they
* are efficient.
*
* The only instance of java.util.Map that you may use is the
* adjacency list from graph. DO NOT create new instances of Map
* for BFS (storing the adjacency list in a variable is fine).
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @param the generic typing of the data
* @param start the vertex to begin the bfs on
* @param graph the graph to search through
* @return list of vertices in visited order
* @throws IllegalArgumentException if any input is null, or if start
* doesn't exist in the graph
*/
public static List> bfs(Vertex start, Graph graph) {
if (graph == null || start == null || !graph.getVertices().contains(start)) {
throw new IllegalArgumentException();
}
Set> visited = new HashSet<>();
Queue> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
List> result = new ArrayList<>();
while (!queue.isEmpty()) {
Vertex curr = queue.poll();
result.add(curr);
for (VertexDistance edge : graph.getAdjList().get(curr)) {
Vertex vertex = edge.getVertex();
if (visited.contains(vertex)) {
continue;
}
visited.add(vertex);
queue.add(vertex);
}
}
return result;
}
/**
* Performs a depth first search (dfs) on the input graph, starting at
* the parameterized starting vertex.
*
* When exploring a vertex, explore in the order of neighbors returned by
* the adjacency list. Failure to do so may cause you to lose points.
*
* *NOTE* You MUST implement this method recursively, or else you will lose
* all points for this method.
*
* You may import/use java.util.Set, java.util.List, and
* any classes that implement the aforementioned interfaces, as long as they
* are efficient.
*
* The only instance of java.util.Map that you may use is the
* adjacency list from graph. DO NOT create new instances of Map
* for DFS (storing the adjacency list in a variable is fine).
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @param the generic typing of the data
* @param start the vertex to begin the dfs on
* @param graph the graph to search through
* @return list of vertices in visited order
* @throws IllegalArgumentException if any input is null, or if start
* doesn't exist in the graph
*/
public static List> dfs(Vertex start, Graph graph) {
if (graph == null || start == null || !graph.getVertices().contains(start)) {
throw new IllegalArgumentException();
}
List> result = new ArrayList<>();
dfsStep(start, graph, new HashSet<>(), result);
return result;
}
/**
* Helper method for performing step of DFS traverse
* @param curr current vertex to continue DFS on
* @param graph grsph structure
* @param visited set of visited vertices
* @param result list of vertices in visiting order
* @param type of vertex
*/
private static void dfsStep(Vertex curr, Graph graph, Set> visited, List> result) {
visited.add(curr);
result.add(curr);
for (VertexDistance edge : graph.getAdjList().get(curr)) {
Vertex vertex = edge.getVertex();
if (visited.contains(vertex)) {
continue;
}
dfsStep(vertex, graph, visited, result);
}
}
/**
* Finds the single-source shortest distance between the start vertex and
* all vertices given a weighted graph (you may assume non-negative edge
* weights).
*
* Return a map of the shortest distances such that the key of each entry
* is a node in the graph and the value for the key is the shortest distance
* to that node from start, or Integer.MAX_VALUE (representing
* infinity) if no path exists.
*
* You may import/use java.util.PriorityQueue,
* java.util.Map, and java.util.Set and any class that
* implements the aforementioned interfaces, as long as your use of it
* is efficient as possible.
*
* You should implement the version of Dijkstra's where you use two
* termination conditions in conjunction.
*
* 1) Check if all of the vertices have been visited.
* 2) Check if the PQ is empty yet.
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @param the generic typing of the data
* @param start the vertex to begin the Dijkstra's on (source)
* @param graph the graph we are applying Dijkstra's to
* @return a map of the shortest distances from start to every
* other node in the graph
* @throws IllegalArgumentException if any input is null, or if start
* doesn't exist in the graph.
*/
public static Map, Integer> dijkstras(Vertex start,
Graph graph) {
if (graph == null || start == null || !graph.getVertices().contains(start)) {
throw new IllegalArgumentException();
}
Map, Integer> distances = new HashMap<>();
for (Vertex v : graph.getVertices()) {
distances.put(v, Integer.MAX_VALUE);
}
distances.put(start, 0);
PriorityQueue> pq = new PriorityQueue<>(new Comparator>() {
@Override
public int compare(Vertex o1, Vertex o2) {
return Integer.compare(distances.getOrDefault(o1, Integer.MAX_VALUE),
distances.getOrDefault(o2, Integer.MAX_VALUE));
}
});
pq.addAll(graph.getVertices());
Set> visited = new HashSet<>();
while (!pq.isEmpty()) {
Vertex curr = pq.poll();
visited.add(curr);
int currDistance = distances.getOrDefault(curr, Integer.MAX_VALUE);
if (currDistance == Integer.MAX_VALUE) {
break;
}
for (VertexDistance edge : graph.getAdjList().get(curr)) {
Vertex vertex = edge.getVertex();
if (visited.contains(vertex)) {
continue;
}
int nextDistance = distances.getOrDefault(vertex, Integer.MAX_VALUE);
if (nextDistance > currDistance + edge.getDistance()) {
distances.put(vertex, edge.getDistance() + currDistance);
pq.remove(vertex);
pq.add(vertex);
}
}
}
return distances;
}
/**
* Runs Kruskal's algorithm on the given graph and returns the Minimal
* Spanning Tree (MST) in the form of a set of Edges. If the graph is
* disconnected and therefore no valid MST exists, return null.
*
* You may assume that the passed in graph is undirected. In this framework,
* this means that if (u, v, 3) is in the graph, then the opposite edge
* (v, u, 3) will also be in the graph, though as a separate Edge object.
*
* The returned set of edges should form an undirected graph. This means
* that every time you add an edge to your return set, you should add the
* reverse edge to the set as well. This is for testing purposes. This
* reverse edge does not need to be the one from the graph itself; you can
* just make a new edge object representing the reverse edge.
*
* You may assume that there will only be one valid MST that can be formed.
*
* Kruskal's will also require you to use a Disjoint Set which has been
* provided for you. A Disjoint Set will keep track of which vertices are
* connected given the edges in your current MST, allowing you to easily
* figure out whether adding an edge will create a cycle. Refer
* to the DisjointSet and DisjointSetNode classes that
* have been provided to you for more information.
*
* You should NOT allow self-loops or parallel edges into the MST.
*
* By using the Disjoint Set provided, you can avoid adding self-loops and
* parallel edges into the MST.
*
* You may import/use java.util.PriorityQueue,
* java.util.Set, and any class that implements the aforementioned
* interfaces.
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @param the generic typing of the data
* @param graph the graph we are applying Kruskals to
* @return the MST of the graph or null if there is no valid MST
* @throws IllegalArgumentException if any input is null
*/
public static Set> kruskals(Graph graph) {
if (graph == null) {
throw new IllegalArgumentException();
}
DisjointSet> ds = new DisjointSet<>();
PriorityQueue> pq = new PriorityQueue<>(new Comparator>() {
@Override
public int compare(Edge o1, Edge o2) {
return Integer.compare(o1.getWeight(), o2.getWeight());
}
});
pq.addAll(graph.getEdges());
for (Vertex v : graph.getVertices()) {
ds.find(v);
}
Set> result = new HashSet<>();
int added = 0;
while (added < graph.getVertices().size() - 1 && !pq.isEmpty()) {
Edge curr = pq.poll();
Vertex u = curr.getU();
Vertex v = curr.getV();
if (ds.find(u) != ds.find(v)) {
result.add(curr);
result.add(new Edge<>(v, u, curr.getWeight()));
ds.union(u, v);
added++;
}
}
if (added < graph.getVertices().size() - 1) {
return null;
}
return result;
}
}