CS515-Assignment 1 Solved

1           Problem Description
A directed simple graph G=(V,E) is a set V of vertices (or nodes) and a set E of edges, where each edge is a pair of distinct vertices. It is customary to draw a graph with vertices indicated by circles and edges represented by directed line segments (or curves) between pairs of vertices. Let’s also assume that we do not allow an edge to start and end at the same vertex. Also, parallel edges between a pair of nodes is not allowed. A graph with eight vertices is shown in the following figure:

 

2           Representation of the Graph
We consider two ways to represent a graph. They are described in the following subsections.

2.1         Adjacency Matrix
Let G be a graph with n vertices. An adjacency matrix is an n×n matrix with rows and columns labeled by the vertex labels. The (i,j)-th entry in the matrix is 1, if there is an edge from vertex i to vertex j in G. It is 0, otherwise. For example, the adjacency matrix representation of the above graph is as follows:

 
a
b
c
d
e
f
g
h
a
0
1
0
0
1
0
0
0
b
0
0
0
1
1
0
0
0
c
1
0
0
0
1
0
0
0
d
0
0
0
0
0
0
1
0
e
0
1
0
0
0
1
1
0
f
0
0
1
0
0
0
0
1
g
0
0
0
0
0
0
0
0
h
0
0
0
0
0
0
1
0
2.2         Adjacency List
In this representation, one uses nodes (struct node), each consisting of a label and a pointer to a node of similar type. Let again G be a graph with n vertices. One first creates an array of n nodes to represent n vertices of the graph. The pointer at a node heads a linked list of nodes representing the edges from the head node. The linked list representation of the above graph is as shown in the following figure:

 

3           Tasks to be carried out
Read a graph from an input file. The input file name is ip.txt. The input file format will be as follows-

      0     1     0     0     1     0     0     0

0        0                0              1              1              0              0              0

1        0                0              0              1              0              0              0

      0     0     0     0     0     0     1     0

      0     1     0     0     0     1     1     0

      0     0     1     0     0     0     0     1

      0     0     0     0     0     0     0     0

      0     0     0     0     0     0     1     0

The maximum size of the input matrix will be 26 × 26. Once the input file is read, then perform the followings-

1.    Check whether the input matrix represents a valid graph

2.    If the input matrix represents a valid graph then generate the linked list for the given graph

3.    Provide an option to print the input matrix.

4.    Provide an option to print the linked list info.