We are going to implement Topological Sort algorithm with the following requirem
ID: 3569872 • Letter: W
Question
We are going to implement Topological Sort algorithm with the following requirements:
The program reads a graph info represented by adjacency list from an input file called "input.txt".
The structure of the adjacency list looks like what you saw in the class and also you can find it in the page #14 of session #26 lecture note.
The first integer number is the id of the vertex and the rest integers are the id of the adjacent vertices.
All integers are delimited by a space.
Example: the adjacency list in the "input.txt" file
1 2 3 4
2 4 5
3 6
4 3 6 7
5 4 7
6
7 6
<end of file>
Then, implement the modified version of the topological sort and print the sorted vertices' IDs using space separated integers.
Output on the Console
1 2 5 4 3 7 6
Notes
The whole program should be in one java file named TopoSort.java in the default package.
It should read the input.txt file from the current folder, where the jar file is located.
There is no blank line in the input file except (probably) at the end of the file. So, your program should ignore the blank lines at the end of the file and also it should ignore any extra white spaces after the last integer numbers.
There should NOT be any extra character in the output.
The output should be in one line.
I'll test your program with the big graphs. So, this is not the case that the provided example is my only test case.
Explanation / Answer
public class TopoSort{ private int vertices; private Set nodes = new HashSet(); private Set edges = new HashSet(); public Graph (int vertices) { this.vertices = vertices; } public void addVertex(Node node){ this.nodes.add(node); } public void addNodes (Set nodeList) { this.nodes = nodeList; } public void addEdge(Edge eg ){ this.edges.add(eg); } public Set topologicalSort() { Queue q = new LinkedList(); Set topoSort = new LinkedHashSet(); int vertexProcessesCtr = 0; for(Node m : this.nodes){ addToQueueToposort(m,topoSort,vertexProcessesCtr,q); } while(!q.isEmpty()) { Node m = q.poll(); for(Node child : m.adjacenctNode){ int indeq = child.getInDegree()-1; child.setInDegree(indeq); addToQueueToposort(child,topoSort,vertexProcessesCtr,q); } } if(vertexProcessesCtr > this.vertices) { System.out.println(); } return topoSort; } private void addToQueueToposort(Node node, Set topoSort, int vertexProcessesCtr, Queue q) { if(node.getInDegree()==0){ q.add(node); ++vertexProcessesCtr; topoSort.add(node); } } }Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.