For this assignment you will perform a topological sort of a directed graph, wit

Question

For this assignment you will perform a topological sort of a directed graph, with vertices labeled using strings. The graph layout will be read via System.in as described below. You will store this graph in an adjacency list, and print output to System.out according to the directions below.

The input consists of a sequence of directed edges, designated by the source and destination vertices. Stop reading edges when a blank line is read. For example, input like this:

Would correspond to a graph like this:

You do not need to implement a Graph class. I would build an adjacency list out of classes from the standard Java library. Map > graph= ... Remember, this is a map from vertices to sets of vertices (those reachable via an edge).

This algorithm proceeds by calculating the indegree of each vertex. I would use a Map to keep track of this. (Think of this as a map from String vertex labels to Integer indegree counts). The indegree of a vertex is the number of incoming edges – this corresponds to the number of times each vertex appears in the value sets from the adjacency list. As your algorithm proceeds, take care not to modify the adjacency list.

The algorithm is as follows:

Notice how this algorithm builds a list of vertices in the appropriate order. You should not print anything out until you confirm that no cycle is present.

Your program must either print out a valid topological sort of the graph, or print “This graph is cyclic”. With the input specified above, several outputs are valid. Two examples:

Explanation / Answer

import java.util.InputMismatchException;

import java.util.Scanner;

import java.util.Stack;

public class CheckCycle

{

    private Stack<Integer> stack;

    private int adjacencyMatrix[][];

    public CheckCycle()

    {

        stack = new Stack<Integer>();

  }

// this is for finding the adjacency matrix in graph

    public void dfs(int adjacency_matrix[][], int source)

    {

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

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

        for (int sourcevertex = 1; sourcevertex <= number_of_nodes; sourcevertex++)

        {

            for (int destinationvertex = 1; destinationvertex <= number_of_nodes; destinationvertex++)

            {

                adjacencyMatrix[sourcevertex][destinationvertex] =

                   adjacency_matrix[sourcevertex][destinationvertex];

            }

        }

// number of times visited a graph for cyclic

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

        int element = source;                               

        int destination = source;                                         

        visited[source] = 1;                    

        stack.push(source);

        while (!stack.isEmpty())

        {

            element = stack.peek();

            destination = element;        

       while (destination <= number_of_nodes)

       {

                if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 1)

                {

                    if (stack.contains(destination))

                    {             

                        System.out.println("The Graph contains cycle");

                        return;            

                    }

                }

                   if (adjacencyMatrix[element][destination] == 1 && visited[destination] == 0)

           {

                    stack.push(destination);

                    visited[destination] = 1;

                    adjacencyMatrix[element][destination] = 0;

                    element = destination;

                    destination = 1;

               continue;

                }

                destination++;

       }

            stack.pop();              

        }         

    }

    public static void main(String...arg)

    {

        int number_of_nodes, source;

        Scanner scanner = null;

   try

        {

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

            scanner = new Scanner(System.in);

            number_of_nodes = scanner.nextInt();

// getting proper answer, is this a proper cyclic

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

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

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

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

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

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

            source = scanner.nextInt();

            CheckCycle checkCycle = new CheckCycle();

            checkCycle.dfs(adjacency_matrix, source);

        }catch(InputMismatchException inputMismatch)

        {

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

        }         

        scanner.close();          

    }

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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