You will design and implement a class named GraphProcessor that will read a grap

Question

You will design and implement a class named GraphProcessor that will read a graph stored in a file, implements Strongly Connected Components (SCC) algorithm discussed in lectures, build appropriate data structures to answer following queries efficiently: • Out degree of a vertex • Whether two vertices are in the same SCC • Number of SCC’s of the graph • Size of the largest component • Given a vertex v, find all vertices that belong to the same SCC as v 4 • Find shortest (BFS) path from a vertex v to u.

Question: Write a method: largestComponent() Returns the size of the largest component.

Explanation / Answer

public List<List<Integer>> getSCComponents(List<Integer>[] graph)
{
int V = graph.length;
boolean[] visited = new boolean[V];
List<Integer> order = fillOrder(graph, visited);   
List<Integer>[] reverseGraph = getTranspose(graph);
visited = new boolean[V];
Collections.reverse(order);
List<List<Integer>> SCComp = new ArrayList<>();
for (int i = 0; i < order.size(); i++)
{
int v = order.get(i);
if (!visited[v])
{
List<Integer> comp = new ArrayList<>();
DFS(reverseGraph, v, visited, comp);
SCComp.add(comp);
}
}
return SCComp;
}
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Kosaraju algorithm Test ");
Kosaraju k = new Kosaraju();
System.out.println("Enter number of Vertices");
int V = scan.nextInt();
List<Integer>[] g = new List[V];
for (int i = 0; i < V; i++)
g[i] = new ArrayList<Integer>();
System.out.println(" Enter number of edges");
int E = scan.nextInt();
System.out.println("Enter "+ E +" x, y coordinates");
for (int i = 0; i < E; i++)
{
int x = scan.nextInt();
int y = scan.nextInt();
/** add edge **/
g[x].add(y);
}
System.out.println(" SCC : ");
List<List<Integer>> scComponents = k.getSCComponents(g);
System.out.println(scComponents);
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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