Assignment No: 9 Graph Traversals and Their Applications Solution

Description

Let G = (V, E ) be an undirected graph. Some vertices of G are red, and the others are blue. Let V_R denote the set of red vertices of G, and V_B the set of blue vertices of G. The vertex set V of G is the union of the two disjoint sets V_R and V_B . Likewise, the edge set E of G is the union of three mutually disjoint subsets: the set E_RR of edges with both endpoints red, the set E_BB of edges with both endpoints blue, and the set E_RB of edges with endpoints of two different colors. We have the two induced subgraphs: the red subgraph G_R = (V_R , E_RR ), and the blue subgraph G_B = (V_B , E_BB ). We will define a subgraph G_RB of G later (in Part 5).

A cycle in the red subgraph G_R is called a red cycle. Likewise, a cycle in the blue subgraph G_B 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 write a program to identify the existence of monochromatic and nonmonochromatic cycles, and print some of them.

The following figure demonstrates such a graph. A red cycle in the graph is (5, 11, 13, 15). A blue cycle in the graph is (0, 3, 12, 9, 14, 7). These cycles are monochromatic. Two nonmonochromatic cycles in the graph are (5, 12, 4, 16, 11, 13, 15) and (13, 7, 10, 9, 12, 3, 15, 5). We assume that a cycle does not contain repeated vertices (except the first and the last ones). For a reason to be explained later, some of the edges of G are shown in bold. The two examples of nonmonochromatic cycles given above use only the bold edges.

GB

GR

7

• 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. There is no need to keep the adjacency lists sorted (with respect to the numbers of the neighboring vertices).

Part 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) (see the sample I/O section). 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.

Write another function prngraph to print a graph in a format illustrated in the sample I/O.

Part 3: Get the red and the blue subgraphs

Write a function getcolgraph(G, col or) that, given the graph G and a col or (r or b), generates G_R or G_B as col or suggests, and returns this subgraph.

Part 4: DFS traversal in a graph, and detection of cycles

Write a recursive DFS function, and a multi-DFS function for an input graph. The traversal carries out two additional tasks. First, whenever a back edge is detected, the cycle causing this back edge is printed along with the colors of the vertices on the cycle (see Sample I/O). All cycles in a graph are not printed by a multi-DFS traversal. It suffices to print only the cycles corresponding to the back edges. Second, all the edges of the DFS forest are stored in the parent representation in an array. You also need to maintain the levels of the nodes in the DFS trees in order to identify the back edges. To be more precise, if u recursively calls DFS on v, you should set parent [v] = u, and l evel[v] = l evel[u] + 1. Of course, you additionally need to use a visited array. The parent array is to be returned by the multi-DFS function.

Part 5: Construct the graph G_RB

The parent array returned by multi-DFS on G_R identifies a set of edges F_RR ⊆ E_RR defining the DFS forest in G_R . Likewise, we have the edges F_BB ⊆ E_BB of the DFS forest in G_B . Write a function getrbgraph to create and return the graph G_RB = (V, F_RR ∪ F_BB ∪ E_RB ). Pass, as arguments to this function, whatever you need for the construction of G_RB . The edges of G_RB are shown as bold in the figure on the first page. The existence of nonmonochromatic cycles in G is related to G_RB as follows:

CLAIM: G contains a nonmonochromatic cycle if and only if G_RB contains a cycle.

The MAIN() function

• Call readgraph to construct the graph G from user inputs. Call prngraph to print G.

• Call getcolgraph twice with col or = r and col or = b to get G_R and G_B . Print the graphs.

• Invoke the multi-DFS function, once on G_R and once more on G_B , to print the red and the blue cycles detected by the traversals. As by-products, you also get the red and the blue forest edges returned in the parent arrays by the two calls of multi-DFS.

• Construct G_RB using getrbgraph. Print the graph.

• Call multi-DFS on G_RB to detect the existence of nonmonochromatic cycles in G. The returned parent array has no role for this call.

Theoretical Exercise (not for submission): Prove the claim given in Part 5.

Submit a single C/C++ source file. Do not use global/static variables.

Sample I/O

20
b r b b b b r b r b r r r b b b b r b b
0	2	0	10	0	15	0	19	1	5	1	16	2	7	2	9	3	12	4	5	4	10
6	17	6	18	6	19	7	13	9	16	10	15	13	15	13	18	13 19		16	17	18	19
-1

+++ Original graph (G)

2. 0 -> 2, 10, 15, 19

18. 1-> 5,16

2. 2-> 0, 7, 9

2. 3-> 12

2. 4-> 5,10

2. 5-> 1, 4

18. 6 -> 17, 18, 19

2. 7-> 2,13

18. 8 ->

2. 9-> 2,16

18. 10 -> 0, 4, 15

18. 11 ->

18. 12-> 3

2. 13 -> 7, 15, 18, 19

2. 14 ->

2. 15 -> 0, 10, 13

2. 16 -> 1, 9, 17

18. 17 -> 6, 16

2. 18 -> 6, 13, 19

• 2. 19 -> 0, 6, 13, 18

• Red subgraph (GR)

• 18. 1 ->

18. 6-> 17

18. 8 ->

18. 10 ->

18. 11 ->

18. 12 ->

• 18. 17-> 6

• Blue subgraph (GB)

• 2. 0 -> 2, 15, 19

2. 2-> 0, 7, 9

2. 3 ->

2. 4-> 5

2. 5-> 4

2. 7-> 2,13

2. 9-> 2,16

2. 13 -> 7, 15, 18, 19

2. 14 ->

2. 15 -> 0, 13

2. 16-> 9

2. 18 -> 13, 19

• 2. 19 -> 0, 13, 18

• Red cycles

• Blue cycles

(15, 13, 7, 2, 0), Color: (b, b, b, b, b)

(19, 18, 13, 7, 2, 0), Color: (b, b, b, b, b, b)

(19, 18, 13), Color: (b, b, b)

• Nonmonochromatic graph (GRB)

• 2. 0-> 10, 2

18. 1-> 16, 5

2. 2-> 9, 7, 0

2. 3-> 12

2. 4-> 10, 5

2. 5-> 1, 4

18. 6 -> 19, 18, 17

2. 7-> 13, 2

18. 8 ->

2. 9-> 16, 2

18. 10 -> 15, 4, 0

18. 11 ->

18. 12-> 3

2. 13 -> 18, 15, 7

2. 14 ->

2. 15 -> 10, 13

2. 16 -> 17, 1, 9

18. 17 -> 16, 6

2. 18 -> 6, 19, 13

• 2. 19 -> 6, 18

• Multi-color cycles

(19, 6, 18), Color: (b, r, b)

(4, 5, 1, 16, 17, 6, 18, 13, 15, 10), Color: (b, b, r, b, r, r, b, b, b, r)

(7, 2, 9, 16, 17, 6, 18, 13), Color: (b, b, b, b, r, r, b, b)

(2, 9, 16, 17, 6, 18, 13, 15, 10, 0), Color: (b, b, b, r, r, b, b, b, r, b)

— Page 4 of 4 —