Java Programming Write a program to perform a topological sort on a graph. Creat

Question

Java Programming

Write a program to perform a topological sort on a graph.

Create a representation of a directed graph.

Create a Vertex class that has the value of the vertex, the indegree and a list of adjacent nodes.

Create a DirectedGraph class that is a list of Vertex objects. This is your graph.

Write a TopologicalSort class that has methods that take in a Directed graph and does a topological sort.

Your test case should use the graph representation of the following

Use the console for input / output.

Explanation / Answer

Vertext.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {

   private int inDegree;
   private int val;
   private List<Vertex> adjecent;
   private boolean visited;
  
   public Vertex(){}
   public Vertex(int val)
   {
       this.val=val;
       inDegree=0;
       adjecent=new ArrayList<Vertex>();
       visited=false;
   }
   public boolean isVisited() {
       return visited;
   }
   public void setVisited(boolean visited) {
       this.visited = visited;
   }
   public int getInDegree() {
       return inDegree;
   }
   public void setInDegree(int inDegree) {
       this.inDegree = inDegree;
   }
   public int getVal() {
       return val;
   }
   public void setVal(int val) {
       this.val = val;
   }
   public List<Vertex> getAdjecent() {
       return adjecent;
   }
   public void setAdjecent(List<Vertex> adjecent) {
       this.adjecent = adjecent;
   }
}

DirectedGraph.java

import java.util.ArrayList;
import java.util.List;

public class DirectedGraph {

   private List<Vertex> graph;
  
   public DirectedGraph(){
       graph=new ArrayList<Vertex>();
   }

   public List<Vertex> getGraph() {
       return graph;
   }
  
  
}

TopologicalSort.java

import java.util.Iterator;
import java.util.List;
import java.util.Stack;

public class TopologicalSort {
  
   public void topologicalSortUtil(Vertex v,Stack<Vertex> stack){
       v.setVisited(true);
       Vertex i;
      
       Iterator<Vertex> it=v.getAdjecent().iterator();
       while(it.hasNext())
       {
           i=it.next();
           if(!i.isVisited()){
               topologicalSortUtil(i, stack);
           }
          
       }
       stack.push(v);
   }
  
   public void topologicalSort(List<Vertex> dag){
       Stack stack=new Stack();
      
       for(int i=0;i<dag.size();i++)
       {
           if(!dag.get(i).isVisited()){
               topologicalSortUtil(dag.get(i), stack);
           }
       }
      
       while(stack.empty()==false)
       {
           Vertex v=(Vertex)stack.pop();
           System.out.println(v.getVal()+" ");
       }
   }
  
   public static void main(String a[])
   {
       Vertex v2=new Vertex(2);
       Vertex v3=new Vertex(3);
       Vertex v4=new Vertex(4);
       Vertex v5=new Vertex(5);
       Vertex v6=new Vertex(6);
       Vertex v7=new Vertex(7);
      
       List<Vertex> vl2=v2.getAdjecent();
       vl2.add(v3);
       vl2.add(v4);
      
       List<Vertex> vl4=v4.getAdjecent();
       vl4.add(v5);
       vl4.add(v7);
      
       List<Vertex> vl6=v6.getAdjecent();
       vl6.add(v7);
       vl6.add(v3);
      
      
       DirectedGraph dg=new DirectedGraph();
       List<Vertex> dag=dg.getGraph();
       dag.add(v2);
       dag.add(v3);
       dag.add(v4);
       dag.add(v5);
       dag.add(v6);
       dag.add(v7);
      
       TopologicalSort ts=new TopologicalSort();
       ts.topologicalSort(dag);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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