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 dis- tinct 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.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-
01001000 00011000 10001000 00000010 01000110 00100001 00000000 00000010
The maximum size of the input matrix will be 26 × 26. Once the input file is read, then perform the followings-
- Check whether the input matrix represents a valid graph
- If the input matrix represents a valid graph then gen- erate the linked list for the given graph
- Provide an option to print the input matrix.
- Provide an option to print the linked list info.
4 Submission
Submit the assignment using the submission link provided in the following course page only.
https://www.iitp.ac.in/~samrat/CompSysLab2_CS515/
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 dis- tinct 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 de- scribed 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:
abcdefgh a01001000 b00011000 c10001000 d00000010 e01000110 f00100001 g00000000 h00000010
