Implement Topological Sort and check cycle import java.util.ArrayList; /** * Gra

Question

Implement Topological Sort and check cycle

import java.util.ArrayList;

/**
* Graph_Cities.java
*
* This class represents a graph of roads
* between cities.
*
* Complete the addRoads, getRoadDuration,
* getTopologicalOrdering, and hasCycle methods.
*
* You must use an adjacency matrix representation
* of a graph.
*/
public class Graph_Cities
{
   // 0.0f = no road
   // So if roads[a][b] = 0.0f then there is no edge
   private float[][] roads;
   private int vertexCount;
   // do not add additional instance variables
  
   public Graph_Cities(int vertexCount)
   {
       this.vertexCount = vertexCount;
       this.roads = new float[vertexCount][vertexCount];
   }
  
   /**
   * Add a road (weight) between two cities.
   *
   * @param a the start city (index)
   * @param b the end city (index)
   * @param duration the weight of the road
   */
   public void addRoad(int a, int b, float duration)
   {
      
       // YOUR CODE HERE
   }
  
   /**
   * Return the duration (weight) of a road.
   *
   * @param a start city (index)
   * @param b end city (index)
   * @return the weight between the two cities
   */
   public float getRoadDuration(int a, int b)
   {
       // YOUR CODE HERE
   }
  
   /**
   * getTopologicalOrdering.
   *
   * Return a topological ordering of the graph.
   *
   * You can assume that the graph doesn't have
   * any cycles.
   *
   * The returned arraylist should contain a
   * list of indexes in topoligical order.
   *
   * TIP: Do this method last. It is the most
   * difficult, but it is only worth a fraction
   * of the total points.
   *
   * @return a topological ordering of the graph
   */
   public ArrayList getTopologicalOrdering()
   {
       // YOUR CODE HERE
   }
  
   /**
   * hasCycle.
   *
   * Return true if the graph contains a cycle.
   *
   * Use Depth-First Search to check for cycles.
   *
   * This will require a recursive helper method
   * that you can define however you like.
   *
   * @return true if the graph contains a cycle, or false otherwise
   */
   public boolean hasCycle()
   {
       // YOUR CODE HERE
   }
}

public class Tester
{
   public static void main(String[] args)
   {
       Graph_Cities g = new Graph_Cities(5);
       g.addRoad(0, 1, 1.0f);
       g.addRoad(1, 2, 2.0f);
       g.addRoad(1, 4, 1.0f);
       g.addRoad(2, 3, 1.0f);
       g.addRoad(3, 4, 2.0f);
      
       System.out.printf("Actual: %.2f%n", g.getRoadDuration(1, 2));
       System.out.printf("Expected: 2.00%n");
      
       System.out.printf("Actual: %.2f%n", g.getRoadDuration(2, 3));
       System.out.printf("Expected: 1.00%n");
      
       System.out.println("Actual: " + g.getTopologicalOrdering());
       System.out.println("Expected: [0, 1, 2, 3, 4]");

       System.out.println("Actual: " + g.hasCycle());
       System.out.println("Expected: false");
      
       g.addRoad(4, 0, 1.0f);
       System.out.println("Actual: " + g.hasCycle());
       System.out.println("Expected: true");
      
       g = new Graph_Cities(5);
       g.addRoad(0, 3, 1.0f);
       g.addRoad(3, 1, 2.0f);
       g.addRoad(1, 2, 1.0f);
       g.addRoad(2, 4, 1.0f);
      
       System.out.println("Actual: " + g.getTopologicalOrdering());
       System.out.println("Expected: [0, 3, 1, 2, 4]");
   }
}

Explanation / Answer

import java.util.InputMismatchException;
import java.util.Scanner;
import java.util.Stack;

public class TopoCycle
{
private Stack<Integer> stack;

public TopoCycle()
{
stack = new Stack<Integer>();
}

public boolean checkCycle(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] topological_sort = new int [number_of_nodes + 1];
int pos = 1;
int j;
boolean cycle = false;


int visited[] = new int[number_of_nodes + 1];
int element = source;
int i = source;
visited[source] = 1;
stack.push(source);


while (!stack.isEmpty())
{
element = stack.peek();
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 1)
{
if (stack.contains(i))
{
System.out.println("The Graph Contains a cycle");
cycle = true;
return cycle;
}
}
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
continue;
}
i++;
}
j = stack.pop();  
topological_sort[pos++] = j;
i = ++j;
}
System.out.println("The Graph does not Contain cycle");
return cycle;
}  

public static void main(String...arg)
{
int number_no_nodes, source;
Scanner scanner = null;
try
{
System.out.println("Enter the number of nodes in the graph");
scanner = new Scanner(System.in);
number_no_nodes = 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();

   TopoCycle topoCycle = new TopoCycle();
topoCycle.checkCycle(adjacency_matrix, source);

}catch(InputMismatchException inputMismatch)
{
System.out.println("Wrong Input format");
}
scanner.close();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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