CS515-Assignment 7 Solved

1           Overview
Let G = (V,E) be an undirected graph. Some vertices of G are red, and the others are blue. Let VR denote the set of red vertices of G, and VB the set of blue vertices of G. The vertex set V of G is the union of the two disjoint sets VR and VB. Likewise, the edge set E of G is the union of three mutually disjoint subsets: the set ERR of edges with both endpoints red, the set EBB of edges with both endpoints blue, and the set ERB of edges with endpoints of two different colors. We have the two induced subgraphs: the red subgraph GR = (VR,ERR), and the blue subgraph GB = (VB,EBB).

A cycle in the red subgraph GR is called a red cycle. Likewise, a cycle in the blue subgraph GB is called a blue cycle. A red or a blue cycle is called monochromatic, since such a cycle consists of vertices of the same color. On the other hand, a cycle in G with vertices of both the colors is called nonmonochromatic. In this assignment, you need to write a program to identify the existence of monochromatic and nonmonochromatic cycles, and print some of them.

In the following figure, a graph is shown. A red cycle in the graph is (0,2,3,0). A blue cycle in the graph is (1,4,8,7,1). These cycles are monochromatic. Two nonmonochromatic cycles in the graph are (0,1,7,6,3,0) and (5,6,7,8,9,5). We assume that a cycle does not contain repeated vertices (except the first and the last ones).

 

2           Task to be carried out
Perform the following tasks.

2.1         Storing the Graph
You need to store the following information about an undirected graph.

•    The number of vertices in the graph (an integer)

•    The colors of the vertices (an array of characters r and b)

•    The vertex numbers (an array of integers): Let G has n vertices. These vertices are naturally numbered as 0,1,2,3,...,n − 1. The red subgraph in the above example has the vertex set 0,2,3,5,6 and blue subgraph has vertex set 1,4,7,8,9.

•    The edges of the graph: Use the adjacency-list (not matrix) representation to store the edges. Since we are dealing with undirected graphs, for every undirected edge (u,v), v must appear in the adjacency list of u, and u in the adjacency list of v. .

2.2         Read and Print a Graph
Write a function readgraph to return a graph G constructed from user inputs. The user first enters the number n of vertices of G, followed by the colors of the vertices, and finally by the list of edges. Each edge is specified by a pair (u,v). It is the responsibility of the user to avoid entering the same edge multiple times. When the user is done with entering the edges, −1 is entered as u in order to indicate the end of the input session.

2.3         Get the Red and Blue Subgraph
Write a function getcolgraph(G, color) that, given the graph G and a color (r or b), generates GR or GB as color suggests, and returns this subgraph.

2.4         DFS traversal in a graph, and detection of cycles
Write a recursive DFS function, and a multi-DFS function for an input graph. During the traversal, look for a back edge and if a back edge is detected, then the cycle causing this back edge is printed along with the colors of the vertices on the cycle. All cycles in a graph are not required to print by the multi-DFS traversal. It suffices to print atmost two cycles corresponding to the back edges.

3           Sample Input Output
10 //no of vertices r b r r b r r b b b //color code of the vertices

//edge list terminated by -1

0 1, 0 2, 0 3, 1 3, 1 4, 1 7, 2 3, 2 5, 3 6, 4 7, 4 8, 5 6, 5 9, 6 7, 7 8, 8 9, -1

Original Graph 0-> 1, 2, 3

1-> 0, 3, 4, 7 2-> 0, 3, 5

3-> 0, 1, 2, 6

4-> 1, 7, 8

5-> 2, 6, 9

6-> 3, 5, 7

7-> 1, 4, 6, 8

8-> 4, 7, 9

9-> 5, 8

Red SubGraph

0-> 2, 3

2-> 0, 3, 5

3-> 0, 2, 6

5-> 2, 6

6-> 5

Blue SubGraph

1-> 4, 7

4-> 1, 7, 8

7-> 1, 4, 8

8-> 4, 7, 9 9-> 8

Red Cycles

0-2-3-0 color (r-r-r-r)

0-2-5-6-3-0 color (r-r-r-r-r-r)

Blue Cycles

1-4-8-7-1 color (b-b-b-b-b)

4-7-8 color (r-r-r)

Multi Color Cycles

0-1-7-6-3-0 color (r-b-b-r-r-r)

5-6-7-8-9-5 color (r-r-b-b-b-r)