Textbook: Data Structures with C++ Using STL”, William Ford and William Topp, 20

Question

Textbook: Data Structures with C++ Using STL”, William Ford and William Topp, 2002, Prentice Hall, 0-13-085850-1
CH16
Question 20. page 1012
20. (a) For each pair of verices in a graph, we say that vj is reachable from vi if and only if there is a directed path from vi to vj. This defines the reachability relation R(vi R vj). for each vertex vi, the breadth-first scan identifies the set of all vertices that are reachable from vi. If we use the scan for each vertex of the graph, we get a series of reachability sets that defines the relation R.
       V0: <reachablility set for v0>
       V1: <reachablility set for v1>
           .....
       Vn-1: <reachablility set for vn-1>
The same relation can also be described with an n-by-n reachability matrix that has a 1 in location (i,j) if and only if viRvj. The following define the reachability sets and reachability matrix for the graph.

       Reachability Sets    Reachability Matrix
       A: {A,B,C,D}       A B C D
       B: {B,D} A 1 1 1 1
       C: {B,C,D} B 0 1 0 1
       D: {D} C 0 1 1 1
D 0 0 0 1
Implement the funtion reachMat() that takes a graph as its argument and returns the reachability matrix.
   template <typename T>
   matrix<int> reachMat (graph<T>& g);
Hint: Use an iterator to scan the vertices in the graph. For each vertex, call bfs() to obtain the reachability set. This set determines a row of the reachability
matrix. With a second iterator, scan the vertices in the graph. The set dertemines the elements in the current row. Determine whether the vertex is in the set and, if yes,
insert a 1 in the current column of the current row; otherwise, insert a 0. the rows and columns of the matrix have indices 0,1,...,n-1.
Index 0 corresponds to the first vertex scanned by a graph iterator, index 1 corresponds to the second vertex, and so forth.

(b) Determine the reachability matrix for graph A and Graph B.

/**Note graph in textbook**

Explanation / Answer

#include<stdio.h>

#define V 4

void printSolution(int reach[][V]);

void transitiveClosure(int graph[][V])
{
   
    int reach[V][V], i, j, k;

   
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            reach[i][j] = graph[i][j];

   
    for (k = 0; k < V; k++)
    {
       
        for (i = 0; i < V; i++)
        {
           
            for (j = 0; j < V; j++)
            {
               
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }

    // Print the shortest distance matrix
    printSolution(reach);
}

void printSolution(int reach[][V])
{
    printf ("Following matrix is transitive closure of the given graph ");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
            printf ("%d ", reach[i][j]);
        printf(" ");
    }
}

int main()
{
    /* Let us create the following weighted graph
            10
       (0)------->(3)
        |         /|
      5 |          |
        |          | 1
       |/         |
       (1)------->(2)
            3           */
    int graph[V][V] = { {1, 1, 0, 1},
                        {0, 1, 1, 0},
                        {0, 0, 1, 1},
                        {0, 0, 0, 1}
                      };

  
    transitiveClosure(graph);
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.