Problem Statement

Definition of a Graph

A graph G is a pair of sets consisting of a set V of vertices and a set E of edges that connect the vertices. Each edge is an ordered pair of vertices, and two vertices are adjacent if they are joined by an edge. A path between two vertices is a sequence of edges.

In a connected graph, there is a path from every vertex to every other vertex. There are no vertices that are not connected to at least one other vertex. In an undirected graph, every edge is bidirectional. So an undirected graph G with two vertices V₀ and V₁ would have one edge and be the set:

G = ( { V₀ , V₁ } , { ( V₀ , V₁ ) } )

If no vertex has a path back to itself, the graph is acyclic. A simple path passes through a vertex only once and has no cycles. The degree of a vertex is the number of edges that connect to it. If no edge has a value or cost, the graph is unweighted. The path length in an unweighted graph is the number of edges in the path.

The diameter of a graph is the longest shortest path of a connected graph. It is computed by determining the shortest path length between each set of vertices in the graph and then determining the longest of these. If two vertices are disconnected and the graph is disconnected, the path length between the two is infinity and the diameter of the graph is infinity.

The following are complete, undirected graphs with diameters of 2:

Purpose

The purpose of this exercise is to find the diameter of an undirected, unweighted graph which has no multiple or self connections.

The program will read input from cin to determine the number of vertices N and M number of edge specifications for an undirected graph. The program will then calculate the diameter of the graph and output it to cout.

The program will have no preset limits on the number of vertices N or edges M, but must not use more than O (N+M) memory. It will use an adjacency list ADT with a dynamically allocated array. The vertices in the adjacency list will be identified by numbers from 0 to N - 1. The program must check that memory has been properly allocated and gracefully handle out of memory situations.

In order to determine the diameter of the graph, the program must first determine if each vertex is connected to at least one other vertex. This can be done by first checking that the number of edges M is not less than the number of vertices minus 1 ( M >= N - 1 ). If there are any empty items in the adjacency list or M < N - 1, then the graph is unconnected and the diameter is infinity.

If the graph is connected, the program must find the shortest path between each set of vertices. The diameter will either be infinity if the graph is disconnected, or the greatest value of the shortest paths.

The following are incomplete, undirected graphs with diameters of infinity:

The following are complete, undirected graphs where M = N - 1 and the diameters are 4 and 3 respectively.

Input Data

The program reads input from a user from cin. It is assumed that the user will supply the input in the correct format. Without being prompted, the user will first enter N, the number of vertices in the graph.

The user will then enter M number of edges in the format ( i , j ) where i and j are two unequal integers separated by a comma, which represent two different vertices in the graph. No set of vertices will have more than one edge between them. The end of input will be indicated by the input -1 (negative one).

The input will be in the format:

Number of vertices, N // integer

Edge specification 1 // ( i₀ , j₀ )

Edge specification M // ( i_M-1, j_M-1)

-1 input complete

Output Data

The program result is output to cout. Once the program has determined the diameter of the graph, it will output the result in the format:

"Graph diameter = D"

where D is an integer if the graph is connected or the string "infinity" if the graph is not connected.

Error Handling

The program must handle errors and display appropriate messages for each error.

The program must verify that memory is correctly allocated for each vertex.
The program must verify that the number of vertices N is greater than or equal to 1.
The program must verify that for each edge indicated in the form ( i , j ), i does not equal j.

Test Plan

Several tests will be run in order to verify that the program meets the program requirements.

Input	Precondition	Postcondition	Rationale
N I,j … M -1	empty graph exists and memory is not full	cout “Graph diameter = D”	Check that a graph with N vertices and M edges is connected and has a diameter of D where D is an integer or the string “infinity”
0 -1	empty graph exists and memory is not full	cout “Input Exception - Program will now terminate” program termination	Check that the number of vertices is greater than or equal to 1.
1 0,0 -1	empty graph exists and memory is not full	cout “Input Exception - Program will now terminate” program termination	Check that the input values for the edge (i , j) are not equal to each other.
1 -1	empty graph exists and memory is not full	cout “Graph diameter = infinity”	Check that a graph with only one vertex is unconnected and has a diameter of infinity
1 0,1 -1	empty graph exists and memory is not full	cout “Input Exception - Program will now terminate” program termination	Check that the input values for the edge are not greater than N – 1.
2 0,1 1,0 -1	empty graph exists and memory is not full	cout “Input Exception - Program will now terminate” program termination	Check that the input values for the edge do not indicate a duplicate edge.
2 0,1 0,1 -1	empty graph exists and memory is not full	cout “Input Exception - Program will now terminate” program termination	Check that the input values for the edge do not indicate a duplicate edge.
2 0,1 -1	empty graph exists and memory is not full	cout “Graph diameter = 1”	Check that a graph with two vertices that are connected has a diameter that is not infinity.
3 0,1 1,2 2,0 -1	empty graph exists and memory is not full	cout “Graph diameter = 2”	Check that a graph with three vertices that are connected has a diameter that is not infinity.
3 0,1 0,2 -1	empty graph exists and memory is not full	cout “Graph diameter = 2”	Check that a graph with three vertices that are connected by 3 – 1 edges has a diameter that is not infinity.

Input	Precondition	Postcondition	Rationale
5 0,1 0,3 0,4 3,2 4,2 1,2 -1	empty graph exists and memory is not full	cout “Graph diameter = 2”	Check that a graph with 5 vertices that are connected has a diameter that is not infinity.
5 0,1 0,2 0,3 0,4 -1	empty graph exists and memory is not full	cout “Graph diameter = 2”	Check that a graph with 5 vertices that are connected by 5 – 1 edges has a diameter that is not infinity.
5 0,1 0,3 3,2 1,2 -1	none	cout “Graph diameter = infinity”	Check that a graph with 5 vertices and 5 – 1 edges may be unconnected with a diameter of infinity.
2 0,1 -1	memory is full	cout “Memory Exception – Program will now terminate” program termination	Check that program correctly checks for memory allocation.
	graph of size 1 has not been created	cout “Graph Exception – Program will now terminate” program termination	Check that program correctly checks that graph is created before allowing input.
	graph is not empty	cout “Graph Exception – Program will now terminate” program termination	Check that program correctly checks that graph is empty before allowing input.