Description
Functional Requirements
Write a Java program (based on a graph traversal algorithm you’ve learned in this class) that, for a given undirected graph, outputs: (i) vertices of each connected component; (ii) a cycle or a message that the graph is acyclic (if there are more than one cycles in a graph, you are required to output just one of them).
Your programs should take inputs from a file via the command line with the following structure in the input file. Each line of the input file represents a graph. The first number in a line species the number of vertices in the graph. Then pairs of vertices define the edges.
An example of an input file is as follows:
5 (1,2) (3,4) (3,5) (4,5)
4 (1,2) (2,3) (1,4)
It specifies two graphs. The first graph has five vertices (1,2,3,4,5) and four edges. The second graph has four vertices (1,2,3,4) and three edges.
Proper output should look (something) like:
-
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Graph1:
Two connected components: {1 2} {3 4 5}
Cycle detected: 3 – 4 – 5 – 3
Graph2:
One connected component: {1 2 3 4}
The graph is acyclic.
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
You must test your programs on a nontrivial input file (with at least 3 graphs and each graph having 7-10 nodes). For the second problem, your test graphs should cover both cyclic and acyclic graphs. Your output should be formatted nicely so that it is easy to read.
Your program should use “good style”. See the separate handout on style requirements for CS-203 programs. In particular, note that you should describe the algorithms you implement
1
in sufficient detail to demonstrate your deep understanding of the algorithms in question.
Additional Requirements
Additionally, you should create the following ordinary text file:
README: Information on how to compile and run your program.
Submitting Your Program
Before 11:59:59 p.m., Tuesday, 23 October 2018 (4th Tuesday), you must upload a zip archive to the course Blackboard assignment for Programming Assignment 1. This zip archive must contain all source code files for your program, including a class named PROG1 with a MAIN method.
No code printouts are required.
Explain Your Program
You must explain your program to the instructor before 5:00 p.m., Thursday, 25 October 2018 (4th Thursday), either in the lab or in the office hour. Highly encourage you to explain your program before the submission deadline, which is 11:59:59 p.m., Tuesday, 23 October 2018 (4th Tuesday). Then, you can modify your program if the instructor finds problems.
Hints
Connected component: in graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
Acyclic: A graph without a cycle.
2
