Lab 14-3: COO Sparse Matrix 相乘 - Introduction to Programming (I)

Lab 14-3: COO Sparse Matrix 相乘 (20%)

輸入：以整數 (符合 long 型態) 的兩矩陣 \(M\) 及 \(N\)
- 矩陣 \(M\) 及 \(N\) 的維度為正整數 \(M_n\)、\(M_m\)、\(N_n\)、\(N_m\)。
- 矩陣的起始位置為 \(M[0][0]\)、\(N[0][0]\)。
- 欲輸入的元素的個數為 \(M_{elements}\)、\(N_{elements}\)。
- 元素紀錄的方式為 (i, j, v)。
- 紀錄格式參考以下的範例。
輸出：顯示使用者輸入的兩 Sparse Matrix 及 \(P = M \times N\) 結果的 Sparse Matrix & 展開的 Matrix。
- 矩陣 \(P\) 的維度 \(P_n\) 與 \(P_m\)。
- 非 0 元素 (i, j, v)。
  - 需以 (0, 0), (0, 1), ... (0, n-1), (1, 0), ... (n-1, m-1) 的順序顯示。
- 展開 matrix 輸出格式參考以下的範例。
檔名：lab14_3_<學號>.cpp (e.g. lab14_3_106062802.cpp)

Notice：

程式需提示輸入 Sparse Matrix \(M\) 及 \(N\)，程式需分析輸入後顯示使用者輸入的矩陣資訊。
計算完 \(P\) 後，顯示矩陣 \(P\)，及展開後的 \(P\)。
程式需檢查輸入的資料是否為合法矩陣，若不相符則顯示錯誤訊息 Invalid matrix. 並結束程式。
- 若矩陣維度為非正整數，則該矩陣為非法矩陣。
- 若欲輸入的元素的個數為負整數，則該矩陣為非法矩陣。
- 如元素的索引值大於矩陣的維度則不算為合法元素。
- 若元素的索引值重複，則以最後一筆紀錄為主。
- 若元素的值為 0 則忽略不紀錄。
程式需檢查矩陣 \(N_m\) 的維度是否與矩陣 \(M_n\) 相同，若不相同則在輸入完矩陣 \(N\) 時顯示錯誤訊息 Invalid matrix. 並結束程式。
程式需使用 function 來處理輸入與輸出、比較、運算。
程式需在 30 秒之內執行完畢，所有測資皆不會超過 30 秒的執行時間。

Format

Input COO matrix M:
<matrix rows>⏎
<matrix columns>⏎
<number of input elements>⏎
<element index> <element index> <element value>⏎
<element index> <element index> <element value>⏎
...⏎
The COO matrix M is:
<matrix rows>
<matrix columns>
<element index> <element index> <element value>
<element index> <element index> <element value>
...
Input COO matrix N:
<matrix rows>⏎
<matrix columns>⏎
<number of input elements>⏎
<element index> <element index> <element value>⏎
<element index> <element index> <element value>⏎
...⏎
The COO matrix N is:
<matrix rows>
<matrix columns>
<element index> <element index> <element value>
<element index> <element index> <element value>
...
The COO matrix P = M * N is:
<matrix rows>
<matrix columns>
<element index> <element index> <element value>
<element index> <element index> <element value>
...
The matrix P is:
<P0_0> <P0_1> ... <P0_n>
<P1_0> <P1_1> ... <P1_n>
...
<Pm_0> <Pm_1> ... <Pm_n>

Example

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
0 3 4⏎
The COO matrix M is:
3
4
0 0 1
0 3 4
1 1 2
2 2 3
Input COO matrix N:
4⏎
3⏎
4⏎
0 1 5⏎
1 2 6⏎
2 2 7⏎
3 2 4⏎
The COO matrix N is:
4
3
0 1 5
1 2 6
2 2 7
3 2 4
The COO matrix P = M * N is:
3
3
0 1 5
0 2 16
1 2 12
2 2 21
The matrix P is:
0 5 16
0 0 12
0 0 21

$ ./a.out⏎
Input COO matrix M:
4⏎
3⏎
4⏎
0 0 1⏎
1 1 0⏎
2 2 3⏎
0 0 4⏎
The COO matrix M is:
4
3
0 0 4
2 2 3
Input COO matrix N:
3⏎
5⏎
4⏎
0 1 5⏎
1 2 6⏎
2 3 7⏎
1 1 4⏎
The COO matrix N is:
3
5
0 1 5
1 1 4
1 2 6
2 3 7
The COO matrix P = M * N is:
4
5
0 1 20
2 3 21
The matrix P is:
0 20 0 0 0
0 0 0 0 0
0 0 0 21 0
0 0 0 0 0

$ ./a.out⏎
Input COO matrix M:
0⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
0⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
-1⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
3 3 4⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
0 3 4⏎
The COO matrix M is:
3
4
0 0 1
0 3 4
1 1 2
2 2 3
Input COO matrix N:
0⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
0 3 4⏎
The COO matrix M is:
3
4
0 0 1
0 3 4
1 1 2
2 2 3
Input COO matrix N:
3⏎
0⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
0 3 4⏎
The COO matrix M is:
3
4
0 0 1
0 3 4
1 1 2
2 2 3
Input COO matrix N:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
3 3 4⏎
Invalid matrix.

$ ./a.out⏎
Input COO matrix M:
3⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
0 3 4⏎
The COO matrix M is:
3
4
0 0 1
0 3 4
1 1 2
2 2 3
Input COO matrix N:
5⏎
4⏎
4⏎
0 0 1⏎
1 1 2⏎
2 2 3⏎
3 3 4⏎
The COO matrix N is:
5
4
0 0 1
1 1 2
2 2 3
3 3 4
Invalid matrix.

Pseudo Code

#include <iostream>
#include <vector>

typedef struct coo_sparse_matrix_struct
{
    unsigned long rows;
    unsigned long cols;
    std::vector<unsigned long> row_ind;
    std::vector<unsigned long> col_ind;
    std::vector<long> val;
} coo_sparse_matrix;

typedef struct matrix_struct
{
    unsigned long rows;
    unsigned long cols;
    std::vector<std::vector<long> > val;
} matrix;

void sort_col_ind(coo_sparse_matrix &coo_matrix)
{
    for (i = 0; i < coo_matrix.col_ind.size(); i++)
    {
        for (j = i + 1; j < coo_matrix.col_ind.size(); j++)
        {
            if (coo_matrix.col_ind[i] > coo_matrix.col_ind[j])
            {
                swap(coo_matrix.col_ind[i], coo_matrix.col_ind[j]);
                swap(coo_matrix.row_ind[i], coo_matrix.row_ind[j]);
                swap(coo_matrix.val[i], coo_matrix.val[j]);
            }
        }
    }
}
void sort_row_ind(coo_sparse_matrix &coo_matrix)
{
    for (i = 0; i < coo_matrix.row_ind.size(); i++)
    {
        for (j = i + 1; j < coo_matrix.row_ind.size(); j++)
        {
            if (coo_matrix.row_ind[i] > coo_matrix.row_ind[j] ||
                (coo_matrix.row_ind[i] == coo_matrix.row_ind[j] &&
                 coo_matrix.col_ind[i] > coo_matrix.col_ind[j]))
            {
                swap(coo_matrix.row_ind[i], coo_matrix.row_ind[j]);
                swap(coo_matrix.col_ind[i], coo_matrix.col_ind[j]);
                swap(coo_matrix.val[i], coo_matrix.val[j]);
            }
        }
    }
}
void sort_coo_matrix(coo_sparse_matrix &coo_matrix)
{
    sort_col_ind(coo_matrix);
    sort_row_ind(coo_matrix);
}
void parse_coo_matrix(coo_sparse_matrix &coo_matrix);
void print_coo_matrix(const coo_sparse_matrix &coo_matrix);
coo_sparse_matrix mult_coo_matrix(
    const coo_sparse_matrix &coo_matrix_M,
    const coo_sparse_matrix &coo_matrix_N);
matrix convert_coo_matrix_to_matrix(const coo_sparse_matrix &coo_matrix);
void print_matrix(const matrix &matrix);

int main()
{
    coo_sparse_matrix coo_matrix_M, coo_matrix_N, coo_matrix_P;
    std::cout << "Input COO matrix M:" << std::endl;
    parse_coo_matrix(coo_matrix_M);
    std::cout << "The COO matrix M is:" << std::endl;
    print_coo_matrix(coo_matrix_M);
    std::cout << "Input COO matrix N:" << std::endl;
    parse_coo_matrix(coo_matrix_N);
    std::cout << "The COO matrix N is:" << std::endl;
    print_coo_matrix(coo_matrix_N);
    coo_matrix_P = mult_coo_matrix(coo_matrix_M, coo_matrix_N);
    std::cout << "The COO matrix P = M * N is:" << std::endl;
    print_coo_matrix(coo_matrix_P);
    matrix matrix_P = convert_coo_matrix_to_matrix(coo_matrix_P);
    std::cout << "The matrix P is:" << std::endl;
    print_matrix(matrix_P);
    return 0;
}

Reference: Sparse matrix - Wikipedia

TA version:

#include <iostream>
#include <vector>
using namespace std;
typedef struct coo_sparse_matrix_struct
{
    unsigned long rows;
    unsigned long cols;
    std::vector<unsigned long> row_ind;
    std::vector<unsigned long> col_ind;
    std::vector<long> val;
} coo_sparse_matrix;

typedef struct matrix_struct
{
    unsigned long rows;
    unsigned long cols;
    std::vector< std::vector<long> > val;
} matrix;

void sort_col_ind(coo_sparse_matrix &coo_matrix)
{
    for (int i = 0; i < coo_matrix.col_ind.size(); i++)
    {
        for (int j = i + 1; j < coo_matrix.col_ind.size(); j++)
        {
            if (coo_matrix.col_ind[i] > coo_matrix.col_ind[j])
            {
                swap(coo_matrix.col_ind[i], coo_matrix.col_ind[j]);
                swap(coo_matrix.row_ind[i], coo_matrix.row_ind[j]);
                swap(coo_matrix.val[i], coo_matrix.val[j]);
            }
        }
    }
}
void sort_row_ind(coo_sparse_matrix &coo_matrix)
{
    for (int i = 0; i < coo_matrix.row_ind.size(); i++)
    {
        for (int j = i + 1; j < coo_matrix.row_ind.size(); j++)
        {
            if (coo_matrix.row_ind[i] > coo_matrix.row_ind[j] ||
                (coo_matrix.row_ind[i] == coo_matrix.row_ind[j] &&
                 coo_matrix.col_ind[i] > coo_matrix.col_ind[j]))
            {
                swap(coo_matrix.row_ind[i], coo_matrix.row_ind[j]);
                swap(coo_matrix.col_ind[i], coo_matrix.col_ind[j]);
                swap(coo_matrix.val[i], coo_matrix.val[j]);
            }
        }
    }
}
void sort_coo_matrix(coo_sparse_matrix &coo_matrix)
{
    sort_col_ind(coo_matrix);
    sort_row_ind(coo_matrix);
}
void parse_coo_matrix(coo_sparse_matrix &coo_matrix);
void print_coo_matrix(const coo_sparse_matrix &coo_matrix);
coo_sparse_matrix mult_coo_matrix(
    const coo_sparse_matrix &coo_matrix_M,
    const coo_sparse_matrix &coo_matrix_N);
matrix convert_coo_matrix_to_matrix(const coo_sparse_matrix &coo_matrix);
void print_matrix(const matrix &matrix);

int main()
{
    coo_sparse_matrix coo_matrix_M, coo_matrix_N, coo_matrix_P;
    std::cout << "Input COO matrix M:" << std::endl;
    parse_coo_matrix(coo_matrix_M);
    std::cout << "The COO matrix M is:" << std::endl;
    print_coo_matrix(coo_matrix_M);
    std::cout << "Input COO matrix N:" << std::endl;
    parse_coo_matrix(coo_matrix_N);
    std::cout << "The COO matrix N is:" << std::endl;
    print_coo_matrix(coo_matrix_N);
    coo_matrix_P = mult_coo_matrix(coo_matrix_M, coo_matrix_N);
    std::cout << "The COO matrix P = M * N is:" << std::endl;
    print_coo_matrix(coo_matrix_P);
    matrix matrix_P = convert_coo_matrix_to_matrix(coo_matrix_P);
    std::cout << "The matrix P is:" << std::endl;
    print_matrix(matrix_P);
    return 0;
}

void parse_coo_matrix(coo_sparse_matrix &coo_matrix)
{
    int n; // n lines of inputs

    /// Exceptions: rows and col can't be nonpositive, n can't be negative
    for (int i = 0; i < 3; i++)
    {
        int temp;
        cin >> temp;
        if (i == 0 && temp > 0)
        {
            coo_matrix.rows = temp;
            continue;
        }
        if (i == 1 && temp > 0)
        {
            coo_matrix.cols = temp;
            continue;
        }
        if (i == 2 && temp >= 0)
        {
            n = temp;
            continue;
        }
        cout << "Invalid matrix." << endl;
        exit(0);
    }

    // Start of Parsing
    while (n--)
    {
        unsigned long r, c;
        long v;
        cin >> r >> c >> v;

        // Exceptions: Index Out of Range
        if (r < 0 ||
            r >= coo_matrix.rows ||
            c < 0 ||
            c >= coo_matrix.cols)
        {
            cout << "Invalid matrix." << endl;
            exit(0);
        }

        // Store COO
        bool flag = false;
        for (int i = 0; i < coo_matrix.row_ind.size(); i++)
        {
            // Rewrite val if already exist
            if (r == coo_matrix.row_ind[i] && c == coo_matrix.col_ind[i])
            {
                if (v == 0) // Erase if val = 0
                {
                    coo_matrix.row_ind.erase(coo_matrix.row_ind.begin() + i);
                    coo_matrix.col_ind.erase(coo_matrix.col_ind.begin() + i);
                    coo_matrix.val.erase(coo_matrix.val.begin() + i);
                }
                else // Rewrite if val != 0
                    coo_matrix.val[i] = v;

                flag = true;
                break;
            }
        }

        // Push_back if not exists yet
        if (!flag && v != 0)
        {
            coo_matrix.row_ind.push_back(r);
            coo_matrix.col_ind.push_back(c);
            coo_matrix.val.push_back(v);
        }
    }
    // End of Parsing

    // Sorting
    sort_coo_matrix(coo_matrix);
}

matrix convert_coo_matrix_to_matrix(const coo_sparse_matrix &coo_matrix)
{
    matrix mtrx;
    mtrx.rows = coo_matrix.rows;
    mtrx.cols = coo_matrix.cols;

    for (unsigned long i = 0; i < mtrx.rows; i++)
        mtrx.val.push_back(vector<long>(mtrx.cols, 0));

    for (int i = 0; i < coo_matrix.row_ind.size(); i++)
    {
        unsigned long r = coo_matrix.row_ind[i], c = coo_matrix.col_ind[i];
        long v = coo_matrix.val[i];
        mtrx.val[r][c] = v;
    }

    return mtrx;
}

void print_matrix(const matrix &matrix)
{
    for (unsigned long i = 0; i < matrix.rows; i++)
    {
        for (unsigned long j = 0; j < matrix.cols; j++)
        {
            cout << matrix.val[i][j] << ' ';
        }
        cout << endl;
    }
}

void print_coo_matrix(const coo_sparse_matrix &coo_matrix)
{
    cout << coo_matrix.rows << '\n'
         << coo_matrix.cols << endl;
    for (unsigned long i = 0; i < coo_matrix.row_ind.size(); i++)
    {
        cout << coo_matrix.row_ind[i]
             << " "
             << coo_matrix.col_ind[i]
             << " "
             << coo_matrix.val[i]
             << endl;
    }
}

void insert_coo_matrix_element(
    coo_sparse_matrix &coo_matrix,
    unsigned long row,
    unsigned long col,
    long val)
{
    coo_matrix.row_ind.push_back(row);
    coo_matrix.col_ind.push_back(col);
    coo_matrix.val.push_back(val);
}

coo_sparse_matrix mult_coo_matrix(
    const coo_sparse_matrix &coo_matrix_M,
    const coo_sparse_matrix &coo_matrix_N)
{
    // Exception: Matrices are not multipliable
    if (coo_matrix_M.cols != coo_matrix_N.rows)
    {
        cout << "Invalid matrix." << endl;
        exit(0);
    }

    coo_sparse_matrix P;
    P.rows = coo_matrix_M.rows;
    P.cols = coo_matrix_N.cols;

    // Iterate over all COO of M
    int m, n;
    for (m = 0; m < coo_matrix_M.row_ind.size();)
    {
        // Current row of P
        int r = coo_matrix_M.row_ind[m];

        // Iterate over all COO of N
        for (n = 0; n < coo_matrix_N.row_ind.size();)
        {
            // current column of P
            int c = coo_matrix_N.col_ind[n];

            // Computing the (i, j) entry of P
            int i = m, j = n, sum = 0;

            while (i < coo_matrix_M.row_ind.size() &&
                   coo_matrix_M.row_ind[i] == r &&
                   j < coo_matrix_N.row_ind.size() &&
                   coo_matrix_N.col_ind[j] == c)
            {
                if (coo_matrix_M.col_ind[i] < coo_matrix_N.row_ind[j])
                    i++;
                else if (coo_matrix_M.col_ind[i] > coo_matrix_N.row_ind[j])
                    j++;
                else
                    sum += coo_matrix_M.val[i++] * coo_matrix_N.val[j++];
            }

            // Insert COO if sum is nonzero
            if (sum != 0)
                insert_coo_matrix_element(P, r, c, sum);

            // To the next column of P
            while (n < coo_matrix_N.row_ind.size() && coo_matrix_N.col_ind[n] == c)
                n++;
        }
        // To the next row of P
        while (m < coo_matrix_M.row_ind.size() && coo_matrix_M.row_ind[m] == r)
            m++;
    }

    return P;
}