In this project, we will process an undirected graph. More specifically, we require that the given graph must be an undirected, connected, acyclic graph, which is a tree. If it is a tree, we will find its diameter. The diameter of a tree is the length of a longest simple path of the tree.
1.(Input) The input comes from a text file that stores the adjacency matrix of a graph. Your program will take the file name of an input as a command-line argument. Then your program will read the content of the file line by line, in which each row corresponds to one row of the adjacency matrix of a graph.
2.(Validation) Before we process the graph, we need to validate the data to make sure that the given data corresponds to the adjacency matrix of a graph. Basically we need to check the following items:
(Square Matrix)
Each row of the data file has a sequence of integers separated by a space character. Make sure that the number of rows equals the number of columns. Otherwise display an error message.
(Bit Value Entries)
Check if each entry of the matrix takes the bit value: 0 or 1. If not, display an error message.
(No Self-Loops)
Since an undirected graph cannot have any self-loop, we need to check that all the diagonal entries must be 0. Otherwise display an error message.
(Valid Undirected Graph)
In order to make sure that this matrix corresponds to the adjacency matrix of an undirected graph, you need to check if it is symmetric. If not, display an error message.
3.(Valid Tree) We still need to make sure that the given graph is a tree: undirected, connected, and acyclic (see definition of acyclic below). Although some of the steps can be integrated into your main algorithm if you like. That means you do not have to do them separately.
(Connected Graph)
Make sure that the graph is connected. Otherwise display an error message.
(Acyclic Graph)
Make sure that the graph does not contain any cycle. If yes, display an error message.
4.(Find a Diameter ) After you get a valid tree, you can design an algorithm to calculate its diameter. In this project, the performance of your algorithm is not very important, if only you get a correct answer.
5.(Output) After you get the answer, you need to output the length of the longest simple path as the diameter. Other than that, you also need to print out this longest simple path as a sequence of vertex numbers.
6.(Testing) You need to prepare your own testing files for your project development.