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: sameComponent(String u, String v) Returns true if u and v belong to the same SCC; otherwise returns false.

Explanation / Answer

If two nodes u and v belong to the same strongly connected component, then there exists paths both from u to v and v to u.

Boolean sameComponent(String u, String v){
   // call the below function twice and
   // if it returns true both the times
   // then both vertices belong to same SCC
  
   Boolean firstCall = isReachable(u,v);
   Boolean secondCall = isReachable(v,u);
  
   if(firstCall && secondCall)
       return true;
   else
       return false;
}

//prints BFS traversal from a given source s
Boolean isReachable(String s, String d)
{
LinkedList<String>temp;

// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];

// Create a queue for BFS
LinkedList<String> queue = new LinkedList<String>();

// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);

// 'i' will be used to get all adjacent vertices of a vertex
Iterator<String> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();

int n;
i = adj[s].listIterator();

// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();

// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;

// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}

// If BFS is complete without visited d
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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