CSC349-Assignment 4 Directed Graphs Solved

In a directed graph, the existence of a path from a vertex u to a vertex v does not imply the existence of a path from v back to u. As a result, finding a path from u to v does not necessarily mean that they are in the same component. Finding the components of a directed graph requires a more sophisticated approach than a pure depth-first search.

Part 1: Strongly Connected Components
Recall that a strongly connected component of a directed graph is a set of vertices within which there exists a

directed path between every pair of vertices. For example, consider the following directed graph:

 

 This graph contains three strongly connected components: {v1,v2,v3}, {v0,v4}, and {v5}. Further recall that such components are maximal, in that no more vertices may be added to a component without breaking its strong connectedness. Thus, v0 alone does not form a component, because v4 can still be added. In your programming language of choice per Assignment 1, implement an algorithm to find the strongly connected components of a directed graph. To help you get started, note the following observations:

· No strongly connected component can span multiple trees in a forest generated by a depth-first search.

· Assigning pre- and postvisit numbers to vertices during a depth-first

            search allows identification of back edges.                                                                 2,7

· Finding a back edge during a depth-first search indicates the existence     v3 of a cycle.

                · All vertices along a cycle must be in the same strongly connected                    3,6

           component.                                                                                                                         v1

· If two cycles share any vertices, then they are both in the same strongly

           connected component.                                                                                                  4,5

v5

 

 

Each input graph will be provided as an edge list: each edge in the graph will be represented by a commaseparated pair of vertex identifiers, indicating an edge from the first vertex to the second.

You may assume that vertex identifiers are contiguous natural numbers — they begin at 0, and there will be no “gaps” in the identifiers used. You may also assume that the graph will be simple and will not contain any isolated vertices.

For example, the above graph could be represented as:

0, [1]0, 3 2, 3 0, 4 1, 5 4, 3

3, 1

1, 2

4, 0

Your program must accept as a command line argument the name of a file containing an edge list as described above, then print to stdout the strongly connected components according to the following format:

· Vertices within the same component appear on a single comma-separated line. Vertices in different components appear on different lines.

· Each line’s vertices must be sorted in ascending order. Note that vertex identifiers are integers, not strings. The lines themselves must be sorted in ascending order using their smallest vertex identifiers. For example:

$ ./compile.sh

$ ./run.sh in1.txt

3 Strongly Connected Component(s):

0, 4

1, 2, 3

5

Your program will be tested using diff, so its printed output must match exactly.


 
[1] of 3