transitive relation in an adjacency matrix

Question

I am trying to identify a transitive relationship between two elements .I am coding in c.

for eg: a->b is represented by a "1" in adjacency matrix in 1st row 2nd column.

so if a->b and b-> c and c->d

i want to identify if a->d. no need to update the adjacency matrix.

approach i have adopted: check all the 1's in the row corresponding to a. lets say there is a 1 in second column ie for b. [(a->b)] , now check if b->d if not proceed to check all the 1's in B's row and continue till 26th row.

I am not really concerned with the complexity. i am just hoping to implement this.

Answer 1

You need to implement a breadth-first search or a depth-first search. Start at a, and stop when you reach d, or when you exhaust all options.

In your case, the depth-first search is somewhat easier to implement, because "plain" C lacks built-in dynamic queues needed for the breadth-first search.

If you do not care about the efficiency and you do not mind updating the matrix, implement the Floyd-Warshall algorithm: it is formulated specifically for adjacency matrices, and takes only five lines to implement:

for (int k = 0 ; k != N ; k++)
    for (int i = 0 ; i != N ; i++)
        for (int j = 0 ; j != N ; j++)
            if (matrix[i][k] && matrix[k][j])
                matrix[i][j] = 1;

After running this algorithm, the resultant matrix contains the transitive closure of the original one.