CSC 349: Design and Analysis of Algorithms

Assignment 4 — Directed Graphs

Credit: This is a lab by Christopher Siu.

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.

Deliverables:

GitHub Classroom: https://classroom.github.com/a/xR_lUIYN

Required Files: compile.sh, run.sh

Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh

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:

v0

v2

v3

v1

v4

v5

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.

· Finding a back edge during a depth-first search indicates the existence

of a cycle.

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

component.

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

connected component.

v0

0,11

v2

1,8

v3

2,7

v1

3,6

v5

4,5

v4

9,10

1 of 3

CSC 349: Design and Analysis of Algorithms

Fall 2019

Assignment 4 — Directed Graphs

Due: Wednesday, October 23rd

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, 2

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.

Part 2: Submission

The following items must be demonstrated in lab on the day of the deadline:

· Pseudocode for an efficient algorithm to find the strongly connected components of a directed graph.

· Drawings of three graphs that you consider interesting test cases for your algorithm.

The following files are required and must be pushed to your GitHub Classroom repository by 8pm of the due

date:

· compile.sh — A Bash script to compile your submission (even if it does nothing), as specified.

· run.sh — A Bash script to run your submission, as specified.

The following files are optional:

· *.py, *.java, *.clj, *.kt, *.js, *.sh — The Python, Java, Clojure, Kotlin, Node.js, or Bash source

code files of a working program to find strongly connected components, as specified.

Any files other than these will be ignored.

2 of 3

CSC 349: Design and Analysis of Algorithms

Fall 2019

Assignment 4 — Directed Graphs

Due: Wednesday, October 23rd

Additionally:

· On the date before the due date, the grader will be run after 8pm and provides feedback containing

only what your program scores. Only submissions made before 8pm are guaranteed to receive feedback.

What your program scores on the official run (the due date) is the final score.

· Late submissions made within 24 hours of the deadline receive a .7 multiplier. If you decide to make a

late submission, please notify me by sending an email to [email protected] both the subject

and the body in the format: ”CSC349,late,asgn<i>”, with i being the assignment number.

3 of 3