Add a topological sort to the Graph/Vertex classes provided. Calculate the Big-O

Question

Add a topological sort to the Graph/Vertex classes provided. Calculate the Big-O notation for this method.

import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.TreeMap;
public class Graph {
private TreeMap<String, Vertex> graph;
public Graph()
{
graph = new TreeMap<>();
}
public void addEdge(String v1, String v2, Integer w)
{
//ensure vertex exist in graph
addVertex(v1);
addVertex(v2);
//get vertex object from graph for v1, add an adjacent edge to v2
graph.get(v1).addEdge(v2, w);
}
public void addEdge(String v1, String v2)
{
addEdge(v1, v2, 1);
}
public void addEdgeUndirected(String v1, String v2, Integer w)
{
//ensure vertex exist in graph
addVertex(v1);
addVertex(v2);
//get vertex object from graph for v1, add an adjacent edge to v2
graph.get(v1).addEdge(v2, w);
graph.get(v2).addEdge(v1, w);
}
public void addEdgeUndirected(String v1, String v2)
{
addEdgeUndirected(v1, v2, 1);
}
private void addVertex(String v)
{
if(!graph.containsKey(v))
{
graph.put(v, new Vertex(v));
}
}
public String toString()
{
String output = "";
for(Map.Entry<String,Vertex> e : graph.entrySet())
{
output += e.getValue()+" ";
}
return output;
}
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)
{
String path = "";
Vertex curr = e;
while(curr.path != null){
path = curr.getName()+", " + path;
curr = curr.path;
}
path = s.getName()+", " + path;
System.out.println(path);
System.out.println(e.dist);
}
else
{
System.out.println("can not reach end");
}
}
}
public void unweighted(Vertex s)
{
/*
* Pseudocode from textbook PG 372
Queue<Vertex> q = new Queue<Vertex>();
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);
}
}
}
*/
Queue<Vertex> q = new LinkedList<>();
for(Map.Entry<String,Vertex> e : graph.entrySet())
{
Vertex v = e.getValue();
v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity
v.path = null;
}
s.dist = 0;
q.offer(s);
while(!q.isEmpty())
{
Vertex v = q.poll();
for(Map.Entry<String, Integer> temp : v.adjacent.entrySet())
{
Vertex w = graph.get(temp.getKey());
if(w.dist == Integer.MAX_VALUE){
w.dist = v.dist + 1;
w.path = v;
q.offer(w);
}
}
}
}
public void weighted(Vertex s)
{
/*
* Pseudocode
PriorityQueue<Vertex> q = new PriorityQueue<Vertex>();
//implement Comparable<Vertex> 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<Vertex> q = new PriorityQueue<>();
for(Map.Entry<String,Vertex> e : graph.entrySet())
{
Vertex v = e.getValue();
v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity
v.path = null;
v.known = false;
}
s.dist = 0;
q.offer(s);
while(!q.isEmpty())
{
Vertex v = q.poll();
v.known = true;
for(Map.Entry<String, Integer> temp : v.adjacent.entrySet())
{
Vertex w = graph.get(temp.getKey());
Integer weight = temp.getValue();
if(w.dist > v.dist + weight){
w.dist = v.dist + weight;
w.path = v;
}
if(!w.known){
q.offer(w);
}
}
}
}
public void negative(Vertex s)
{
/*
* Pseudocode
Queue<Vertex> q = new Queue<Vertex>();
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);
}
}
}
}
*/
Queue<Vertex> q = new LinkedList<>();
for(Map.Entry<String,Vertex> e : graph.entrySet())
{
Vertex v = e.getValue();
v.dist = Integer.MAX_VALUE;//max int is around 2 billion, basically Infinity
v.path = null;
}
s.dist = 0;
q.offer(s);
while(!q.isEmpty())
{
Vertex v = q.poll();
for(Map.Entry<String, Integer> temp : v.adjacent.entrySet())
{
Vertex w = graph.get(temp.getKey());
Integer weight = temp.getValue();
if(w.dist > v.dist + weight){
w.dist = v.dist + weight;
w.path = v;
if(!q.contains(w)){
q.offer(w);
}
}
}
}
}

public void printMaxDistance()
{
int maxDist = 0;
String vert = "";
for(Map.Entry<String, Vertex> vertex : graph.entrySet())
if(vertex.getValue().dist != Integer.MAX_VALUE && vertex.getValue().dist > maxDist)
{
maxDist = vertex.getValue().dist;
vert = vertex.getKey();
}
System.out.println("MAX:"+vert+":"+maxDist);
}

}

___________________________________________________________

import java.util.Map;
import java.util.TreeMap;
public class Vertex implements Comparable<Vertex> {
private String name;
public TreeMap<String, Integer> adjacent;
public Integer dist;
public Vertex path;
public boolean known;
public Vertex(String n)
{
name = n;
adjacent = new TreeMap<>();
}
public void addEdge(String e, Integer i)
{
adjacent.put(e, i);//will overwrite existing edge with same name
}
public void addEdge(String e)
{
addEdge(e, 1);//use weight of 1 for unweighted
}

public String getName() {
return name;
}
public TreeMap<String, Integer> getAdjacent() {
return adjacent;
}
public String toString()
{
String output = "Name:"+name+" Dist:"+dist;
output += " Adjacent List:";
for(Map.Entry<String,Integer> e :adjacent.entrySet())
{
output += ","+e.getKey()+":"+e.getValue();
}
return output;
}
@Override
public int compareTo(Vertex arg0) {
return dist.compareTo(arg0.dist);
}
}

Explanation / Answer

Please find the implementation of Topological Sort below.

// A recursive function used by topologicalSort

public void topologicalSortUtil(String v, TreeMap<String, Boolean> visited,

   Stack<String> stack)

{

// Mark the current node as visited.

visited.put(v, true);

// Recur for all the vertices adjacent to this

// vertex

TreeMap< String, Integer> adj = graph.get(v).getAdjacent();

       while (String key : adj.keySet()) {

if (visited.containsKey(key) && !visited.get(key))

topologicalSortUtil(key, visited, stack);

}

// Push current vertex to stack which stores result

stack.push(v);

}

// The function to do Topological Sort. It uses

// recursive topologicalSortUtil()

public void topologicalSort()

{

Stack<String> stack = new Stack<>();

// Mark all the vertices as not visited

TreeMap<String, Boolean> visited = new TreeMap<>();

for (String v : graph.keySet())

visited.put(v, false);

// Call the recursive helper function to store

// Topological Sort starting from all vertices

// one by one

for (String v : graph.keySet())

if (visited.containsKey(v) && !visited.get(v))

topologicalSortUtil(v, visited, stack);

// Print contents of stack

while (stack.empty() == false)

System.out.print(stack.pop() + " ");

}

}

Time Complexity: O(V + E)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.