Question: In JAVA, Add a topological sort method to the Graph/Vertex classes. Then calculate the Big-Oh notation for this method. Graph Class: import java.util.LinkedList; import java.util.Map;
In JAVA, Add a topological sort method to the Graph/Vertex classes. Then calculate the Big-Oh notation for this method.
Graph Class:
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Graph {
public TreeMap graph;
public Graph()
{
graph = new TreeMap<>();
}
public void addEdge(String v1, String v2, Integer w)
{
addVertex(v1);
addVertex(v2);
if(graph.get(v1).addEdge(v2, w))
graph.get(v2).indegree++;
}
public void addEdge(String v1, String v2)
{
addEdge(v1, v2, 0);
}
public void addBidirectionalEdges(String v1, String v2, Integer w1, Integer w2)
{
addEdge(v1, v2, w1);
addEdge(v2, v1, w2);
}
public void addBidirectionalEdges(String v1, String v2, Integer w)
{
addBidirectionalEdges(v1, v2, w, w);
}
public void addBidirectionalEdges(String v1, String v2)
{
addBidirectionalEdges(v1, v2, 0, 0);
}
public void addVertex(String v)
{
if(!graph.containsKey(v))
{
graph.put(v, new Vertex(v));
}
}
public String toString()
{
if(graph.size() > 0)
{
String temp = "";
for(Map.Entry vertex : graph.entrySet())
temp += vertex.getValue() + " ";
return temp;
}
return "No Verticies";
}
/***************************************************************************/
public void printPath(String vs, String ve, String type)
{
if(graph.containsKey(vs) && graph.containsKey(ve))
{
System.out.println(type.toUpperCase());
Vertex start = graph.get(vs);
if(type.toLowerCase().equals("unweighted"))
{
unweighted(start);
}
else if(type.toLowerCase().equals("weighted"))
{
weighted(start);
}
else if(type.toLowerCase().equals("negative"))
{
negative(start);
}
Vertex end = graph.get(ve);
/*
* Pseudocode
if(e.dist != INFINITY){
String path = "";
Vertex curr = e;
while(curr.path != null){
path += curr;
curr = curr.path;
}
path = s + path;
print(path)
print(dist)
}else{
print("can not reach end");
}
*/
if(end.dist != Integer.MAX_VALUE)
{
Vertex curr = end;
String path = curr.vertex;
curr = curr.path;
while(curr.path != null)
{
path = curr.vertex + "->" + path ;
curr = curr.path;
}
path = vs + "->" + path;
System.out.println(path);
System.out.println("Distance:" + end.dist);
}
else
{
System.out.println("Can not reach end vertex from start");
}
}
}
public void unweighted(Vertex s)
{
/*
* Pseudocode from textbook PG 372
Queue q = new Queue();
for each Vertex v{
v.dist = INFINITY;
v.path = null;//added to make sure we clear the path between runs of pathing methods
}
s.dist = 0;
q.enqueue(s);
while(!q.isEmpty()){
Vertex v = q.dequeue();
for each Vertex w adjacent to v{
if(w.dist == INFINITY){
w.dist = v.dist + 1;
w.path = v;
q.enqueue(w);
}
}
}
*/
LinkedList q = new LinkedList<>();
for(Map.Entry vertex : graph.entrySet())
{
vertex.getValue().dist = Integer.MAX_VALUE;
vertex.getValue().path = null;
}
s.dist = 0;
q.addLast(s);
while(!q.isEmpty())
{
Vertex v = q.removeFirst();
for(Map.Entry vertex : v.adjacent.entrySet())
{
Vertex w = graph.get(vertex.getKey());
if(w.dist == Integer.MAX_VALUE)
{
w.dist = v.dist+1;
w.path = v;
q.addLast(w);
}
}
}
}
public void weighted(Vertex s)
{
/*
* Pseudocode
PriorityQueue q = new PriorityQueue();
//implement Comparable based on distance for PriorityQueue
for each Vertex v{
v.dist = INFINITY;
v.path = null;//added to make sure we clear the path between runs of pathing methods
v.known = false;
}
s.dist = 0;
q.enqueue(s);
while(!q.isEmpty()){
Vertex v = q.dequeue();//smallest distance in queue
v.known = true;
for each Vertex w adjacent to v{
if(w.dist > v.dist + w.weight){
w.dist = v.dist + w.weight;
w.path = v;
}
if(!w.known){
q.enqueue(w);
}
}
}
*/
PriorityQueue q = new PriorityQueue<>();
for(Map.Entry vertex : graph.entrySet())
{
vertex.getValue().dist = Integer.MAX_VALUE;
vertex.getValue().path = null;
vertex.getValue().known = false;
}
s.dist = 0;
q.add(s);
while(!q.isEmpty())
{
Vertex v = q.remove();
v.known = true;
for(Map.Entry vertex : v.adjacent.entrySet())
{
Vertex w = graph.get(vertex.getKey());
int weight = vertex.getValue();
if(w.dist > v.dist + weight){
w.dist = v.dist + weight;
w.path = v;
}
if(!w.known){
q.add(w);
}
}
}
}
public void negative(Vertex s)
{
/*
* Pseudocode
Queue q = new Queue();
for each Vertex v{
v.dist = INFINITY;
v.path = null;//added to make sure we clear the path between runs of pathing methods
}
s.dist = 0;
q.enqueue(s);
while(!q.isEmpty()){
Vertex v = q.dequeue();
for each Vertex w adjacent to v{
if(w.dist > v.dist + w.weight){
w.dist = v.dist + w.weight;
w.path = v;
if(!q.contains(w)){
q.enqueue(w);
}
}
}
}
*/
LinkedList q = new LinkedList<>();
for(Map.Entry vertex : graph.entrySet())
{
vertex.getValue().dist = Integer.MAX_VALUE;
vertex.getValue().path = null;
}
s.dist = 0;
q.addLast(s);
while(!q.isEmpty())
{
Vertex v = q.removeLast();
for(Map.Entry vertex : v.adjacent.entrySet())
{
Vertex w = graph.get(vertex.getKey());
int weight = vertex.getValue();
if(w.dist > v.dist + weight){
w.dist = v.dist + weight;
/* possible fix for infinite recursion
if(w.dist < 0)
w.dist = 0;
*/
w.path = v;
if(!q.contains(w)){
q.addLast(w);
}
}
}
}
}
}
********************************************************************************************************************************************************************************************************************
********************************************************************************************************************************************************************************************************************
********************************************************************************************************************************************************************************************************************
Vertex Class:
import java.util.TreeMap;
public class Vertex implements Comparable {
public String vertex;
public TreeMap adjacent;//vertex connected name and weight to that vertex
public int indegree;
public Integer dist;
public Vertex path;
public boolean known;
public Vertex(String v)
{
vertex = v;
adjacent = new TreeMap<>();
indegree = 0;
dist = Integer.MAX_VALUE;
path = null;
known = false;
}
public boolean addEdge(String v, int w)
{
if(!adjacent.containsKey(v))
{
adjacent.put(v, w);
return true;//does not exist in adjacent list
}
else if(adjacent.get(v) > w)
{
adjacent.put(v, w);//exists, but new weight is better
}
return false;
}
public void addEdge(String v)
{
addEdge(v, 0);//unweighted
}
public String toString()
{
String temp = "Vertex:" + vertex + " | In Degree:" + indegree + " | Distance:" + dist ;
if(adjacent.size() > 0)
temp += " | Adjacent List:" + adjacent;
return temp;
}
public int compareTo(Vertex v)
{
return dist.compareTo(v.dist);
}
}
Step by Step Solution
There are 3 Steps involved in it
To add a topological sort method to the Graph and Vertex classes in Java we need to follow these steps and then calculate the BigO notation for this m... View full answer
Get step-by-step solutions from verified subject matter experts
Study Help