CIS 3223 Lab10 – Using Depth-First Graph (DFG) to find
Strongly Connected Components of a Directed Graph
DUE: (before the next lab, 10:30am Friday, April 10, 2008)
Depth-First Approach for
Discovery of Connected Graph Regions
In Labs 8 and 9 you
implemented the DFS algorithm and used it to analyze undirected graphs. In this
lab, you will use DFS function to write a Matlab code
that finds all strongly connected components of a directed graph. The idea of
the algorithm is based on applying DFS on the original graph G and its reverse
graph GR, and is described in Chapter 3 of the Dasgupta
textbook.
TASKS
1. Your goal is to implement in Matlab
a DFS_SCC algorithm that, given a graph, finds all strongly connected components
of a directed graph. The function definition is:
function regions = dfs_scc(G)
You should assume:
G to be the
adjacency matrix of dimension N*N, where N is the number of graph nodes.
regions to be an array of size N*1
with integer values that indicate to which strongly connected component each of
the N nodes belongs. For example, if all nodes are connected,
regions will be an array of ones.
Observe that dsf function from Lab 8 should be used as a subroutine. You should implement an efficient DSF_SCC Matlab algorithm that uses graph representation with
adjacency lists, as you did in Lab 9.
2. Evaluate the correctness of DFS_SCC
function. Use graph from the textbook we used as a working example in the
class.
3. Generate graphs G of size N
= {10, 50, 100, 500} and with alpha = {0.01, 0.1} using the following code:
G = sprand(N,N,alpha);
Observe
that the resulting graph is directed. Run DFS_SCC 10 times for each possible
combination of N and alpha. For each run, save the number of strongly connected components, size of the largest component,
average size of the component, and time needed to run the algorithm. Is the
runtime consistent with the theoretical result O(|V|+|E|)?
If the ansewer is no, try to figure out what is the
problem. Explain in your report.