write a program which will take the description of a single graph from standard

Question

write a program which will take the description of a single graph from standard input and write to standard output a topological ordering of the nodes of that graph.

1 Description For this assignment, you are to write a program which will take the description of a single graph from standard input and write to standard output a topological ordering of the nodes of that graph. You may write your program in either Java, Python, C, or C++. Other languages need to be approved by the GTF. You may store the graph with either an adjacency list or an adjacency matrix. Your program should implement a linear time depth-first search algorithm and may be tested on very large graphs. Linear time here means O(n m) if using an adjacency list, and O(n2) if using adjacency matrix. 2 Sample Input The first line of input contains two integers, N and M. N is the number of nodes the nodes are 1, 2, 3, N and M is the number of edges. In addition, the nodes have names, so the next N lines of the input are the names of the nodes as strings (these represent tasks). There follow M lines describing each edge. An edge description is a line containing three integers I J W: 1 S I, J SN and W 0. This represents a directed edge from node I to node J with weight W 6 7 paint cleanup bill purchase prepare 1 2 6 1 4 3 4 2 8 6 1 1 5 6 1 5 3 1 2 3 4 Note: All the edges are presented with weights. You may ignore these weights in this assignment,

Explanation / Answer

Code is written in 2 classes in java. copy to 2 different files and execute

Sample Input:

6 7
v1
v2
v3
v4
v5
v6
1 2 6
1 4 3
4 2 8
6 1 1
5 6 1
5 3 1
2 3 4

Sample output:

5 v5
6 v6
1 v1
4 v4
2 v2
3 v3

//Node.java

import java.util.LinkedList;

public class Node {
   private LinkedList<Node> list;
   private String name;
   private int id;
   public Node(int id, String name) {
       this.id = id;
       this.name = name;
       list = new LinkedList<Node>();
   }
   public int getId() {
       return id;
   }
  
   public String getName() {
       return name;
   }
  
   public LinkedList<Node> getList() {
       return list;
   }
  
   public void addAdjacentNode(Node node)
   {
       list.add(node);
   }
  
   public String toString() {
       return id + " " + name;
   }
}

//Graph.java

import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

public class Graph {
   private int verticesCount; // No. of vertices
private Node adj[]; // Nodes List
  
Graph(int v)
{
   this.verticesCount = v;
   adj = new Node[verticesCount+1];
}
  
public int getVerticesCount() {
       return verticesCount;
   }

public void addNode(int index, Node node)
{
   adj[index] = node;
}
  
   public void addEdge(int v, int w)
{
   adj[v].addAdjacentNode(adj[w]);
}
  
void sortUtil(int v, boolean visited[],
Stack<Node> stack)
{
// Mark the current node as visited.
visited[v] = true;
Node node;

// Recur for all the vertices adjacent to this
// vertex
Iterator<Node> it = adj[v].getList().iterator();
while (it.hasNext())
{
node = it.next();
if (!visited[node.getId()])
   sortUtil(node.getId(), visited, stack);
}

// Push current vertex to stack which stores result
stack.push(adj[v]);
}
  
void topologicalSort()
{
Stack<Node> stack = new Stack<Node>();

// Mark all the vertices as not visited
boolean visited[] = new boolean[verticesCount+1];
for (int i = 1; i <= verticesCount; i++)
visited[i] = false;

// Call the recursive helper function to store
// Topological Sort starting from all vertices
// one by one
for (int i = 1; i <= verticesCount; i++)
if (visited[i] == false)
   sortUtil(i, visited, stack);

  
while (stack.empty()==false)
System.out.println(stack.pop());
}
  
public static void main(String args[])
{
       Scanner scan = new Scanner(System.in);
       Graph graph = new Graph(scan.nextInt());
       int edges = scan.nextInt();
       scan.nextLine();
       for(int i =1; i<= graph.getVerticesCount(); i++)
       {
           Node node = new Node(i, scan.nextLine());
           graph.addNode(i,node);
       }
      
       for(int i =0; i<edges;i++)
       {
           int v = scan.nextInt();
           int w = scan.nextInt();
           int weight = scan.nextInt(); // we are parsing weights but ignoring it now
           scan.nextLine();
           graph.addEdge(v, w);
       }
      
       graph.topologicalSort();
}
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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