Question: Implement a topological sort method for the following two classes: //Vertex.java import java.util.TreeMap; public class Vertex implements Comparable { public String vertex; public TreeMap adjacent;//vertex
Implement a topological sort method for the following two classes:
//Vertex.java
import java.util.TreeMap;
public class Vertex implements Comparable
public String vertex;
public TreeMap
public Integer dist;
public Vertex path;
public boolean known;
public Vertex(String name) {
this.vertex = name;
adjacent = new TreeMap<>();
}
public void addEdge(String v, Integer weight)
{
adjacent.put(v, weight);
}
public void addEdge(String v)
{
adjacent.put(v, 1);
}
public String toString()
{
String temp = "Vertex:" + vertex + " | Distance:" + dist;
if(adjacent.size() > 0)
temp += " | Adjacent List:" + adjacent;
return temp;
}
public int compareTo(Vertex v)
{
return dist.compareTo(v.dist);
}
}
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
//Graph.java
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Graph {
public TreeMap
public Graph()
{
graph = new TreeMap<>();
}
public void addEdge(String v1, String v2, int weight)
{
//make sure both vertex exist in graph
addVertex(v1);
addVertex(v2);
graph.get(v1).addEdge(v2, weight);
}
public void addEdge(String v1, String v2)
{
addEdge(v1, v2, 0);
}
public void addBidirectionalEdges(String v1, String v2, int weight)
{
//make sure both vertex exist in graph
addVertex(v1);
addVertex(v2);
graph.get(v1).addEdge(v2, weight);
graph.get(v2).addEdge(v1, weight);
}
public void addBidirectionalEdges(String v1, String v2)
{
addBidirectionalEdges(v1, v2, 0);
}
private void addVertex(String v)
{
if(!graph.containsKey(v))
{
graph.put(v, new Vertex(v));
}
}
public void printMaxDistance()
{
int maxDist = 0;
String vert = "";
for(Map.Entry
if(vertex.getValue().dist != Integer.MAX_VALUE && vertex.getValue().dist > maxDist)
{
maxDist = vertex.getValue().dist;
vert = vertex.getKey();
}
System.out.println("MAX:"+vert+":"+maxDist);
}
public String toString()
{
if(graph.size() > 0)
{
String temp = "";
for(Map.Entry
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 s = graph.get(vs);
if(type.toLowerCase().equals("unweighted"))
{
unweighted(s);
}
else if(type.toLowerCase().equals("weighted"))
{
weighted(s);
}
else if(type.toLowerCase().equals("negative"))
{
negative(s);
}
Vertex e = 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(e.dist != Integer.MAX_VALUE)
{
Vertex curr = e;
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:" + e.dist);
}else{
System.out.println("can not reach end");
}
}
}
public void unweighted(Vertex s)
{
/*
* Pseudocode from textbook PG 372
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
for(Map.Entry
{
vertex.getValue().dist = Integer.MAX_VALUE;//v.dist = INFINITY;
vertex.getValue().path = null;
}
s.dist = 0;
q.addLast(s);
while(!q.isEmpty())
{
Vertex v = q.removeFirst();
for(Map.Entry
{
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
//implement Comparable
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
for(Map.Entry
{
vertex.getValue().dist = Integer.MAX_VALUE;//v.dist = INFINITY;
vertex.getValue().path = null;
vertex.getValue().known = false;
}
s.dist = 0;
q.add(s);
while(!q.isEmpty())
{
Vertex v = q.remove();//smallest distance in queue
v.known = true;
for(Map.Entry
{
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
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
for(Map.Entry
{
vertex.getValue().dist = Integer.MAX_VALUE;//v.dist = INFINITY;
vertex.getValue().path = null;
}
s.dist = 0;
q.addLast(s);
while(!q.isEmpty())
{
Vertex v = q.removeFirst();
for(Map.Entry
{
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(!q.contains(w)){
q.addLast(w);
}
}
}
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help