Example: Boolean Matrix Multiplication in C

// Boolean Matrix Multiplication
#include <stdio.h>

#define SIZE 3 // Assuming square matrices for simplicity in this example

// Function to print a Boolean matrix
void printMatrix(int matrix[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
}

// Function to perform Boolean matrix multiplication
// C[i][j] = OR (A[i][k] AND B[k][j]) for k from 0 to SIZE-1
void booleanMatrixMultiply(int A[SIZE][SIZE], int B[SIZE][SIZE], int result[SIZE][SIZE]) {
    // Step 1: Initialize the result matrix with zeros
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            result[i][j] = 0;
        }
    }

    // Step 2: Perform Boolean multiplication
    for (int i = 0; i < SIZE; i++) { // For each row of A
        for (int j = 0; j < SIZE; j++) { // For each column of B
            for (int k = 0; k < SIZE; k++) { // For each intermediate element
                // C[i][j] = C[i][j] OR (A[i][k] AND B[k][j])
                result[i][j] = result[i][j] || (A[i][k] && B[k][j]);
            }
        }
    }
}

int main() {
    // Step 1: Define two sample Boolean matrices (e.g., adjacency matrices)
    // Represents a graph: 0->1, 1->2
    int matrixA[SIZE][SIZE] = {
        {0, 1, 0},
        {0, 0, 1},
        {0, 0, 0}
    };
    // Represents another relationship or for multiplication with itself
    int matrixB[SIZE][SIZE] = {
        {0, 1, 0},
        {0, 0, 1},
        {0, 0, 0}
    };

    int resultMatrix[SIZE][SIZE];

    printf("Matrix A (Adjacency Matrix):\n");
    printMatrix(matrixA);
    printf("\nMatrix B (same as A for paths of length 2):\n");
    printMatrix(matrixB);

    // Step 2: Perform Boolean matrix multiplication (A * B)
    booleanMatrixMultiply(matrixA, matrixB, resultMatrix);
    printf("\nResult of A * B (Boolean Multiplication - paths of length 2):\n");
    printMatrix(resultMatrix);

    return 0;
}