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 console for input / output.

2,3,4 4,5 6 6,7,3 4,7 (empty) 6

Explanation / Answer

import java.util.InputMismatchException;

import java.util.Scanner;

import java.util.Stack;

public class TopologicalSortTechnique

{

    private Stack<Integer> stack;

    public TopologicalSortTechnique()

    {

stack = new Stack<Integer>();

    }

    public int [] topological(int adjacency_matrix[][], int source) throws NullPointerException

    {

        int number_of_nodes_topology = adjacency_matrix[source].length - 1;

        int[] topological_sort_technique = new int [number_of_nodes_topology + 1];

        int pos = 1;

        int j ;

        int visited[] = new int[number_of_nodes + 1];

        int element = source;

        int i = source;

        visited[source] = 1;

        stack.push(source);

        while (!stack.isEmpty())

        {

            element_top = stack.peek();

            while (i <= number_of_nodes)

            {

                if (adjacency_matrix[element_top][i] == 1 && visited[i] == 1)

                {

                    if (stack.contains(i))

                    {

                        System.out.println("TOPOLOGICAL SORT NOT POSSIBLE");

                        return null;

                    }

                }

                if (adjacency_matrix[element_top][i] == 1 && visited[i] == 0)

                {

                    stack.push(i);

                    visited[i] = 1;

                    element = i;

                    i = 1;

                    continue;

                }

                i++;

            }

            j = stack.pop();

            topological_sort_technique[pos++] = j;

            i = ++j;

        }

        return topological_sort_technique;

    }      

    public static void main(String...arg)

    {

        int number_no_nodes, source;

        Scanner scanner = null;

        int topological_sort_technique[] = null;

        try

        {

            System.out.println("Enter the number of nodes in the graph");

            scanner = new Scanner(System.in);

            number_no_nodes_topology = scanner.nextInt();

            int adjacency_matrix[][] = new int[number_no_nodes + 1][number_no_nodes + 1];

            System.out.println("Enter the adjacency matrix");

                for (int i = 1; i <= number_no_nodes; i++)

                for (int j = 1; j <= number_no_nodes; j++)

                    adjacency_matrix[i][j] = scanner.nextInt();

            System.out.println("Enter the source for the graph");

            source = scanner.nextInt();

            System.out.println("The Topological sort for the graph is given by ");

            TopologicalSort toposort = new TopologicalSort();

            topological_sort_technique = toposort.topological(adjacency_matrix, source);

            System.out.println();

            for (int i = topological_sort.length - 1; i > 0; i-- )

            {

                if (topological_sort[i] != 0)

                    System.out.print(topological_sort[i]+" ");

            }          

        }catch(InputMismatchException inputMismatch)

         {

             System.out.println("Wrong Input format");

         }catch(NullPointerException nullPointer)

         {

         }

        scanner.close();

    }

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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