Lab 14: Matrix & Sparse Matrix

Lab 14-1: COO Sparse Matrix 儲存及顯示 (40%)

• 輸入：以整數 (符合 long 型態) 的矩陣 \(M\)
  • 矩陣 \(M\) 的維度為正整數 \(n\) 與 \(m\)。
  • 矩陣的起始位置為 \(M[0][0]\)。
  • 欲輸入的元素的個數為 \(elements\)。
  • 元素紀錄的方式為 (i, j, v)。
  • 紀錄格式參考以下的範例。
• 輸出：顯示使用者輸入的 Sparse Matrix 及展開的 Matrix。
  • 矩陣 \(M\) 的維度 \(n\) 與 \(m\)。
  • 非 0 元素 (i, j, v)。
    • 需以 (0, 0), (0, 1), ... (0, n-1), (1, 0), ... (n-1, m-1) 的順序顯示。
  • 展開 matrix 輸出格式參考以下的範例。
• 檔名：lab14_1_<學號>.cpp (e.g. lab14_1_106062802.cpp)

Notice：

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

Format

<matrix rows>⏎
<matrix columns>⏎
<number of input elements>⏎
<element index> <element index> <element value>⏎
<element index> <element index> <element value>⏎
...⏎
The COO matrix is:
<matrix rows>
<matrix columns>
<element index> <element index> <element value>
<element index> <element index> <element value>
...
The matrix is:
<M0_0> <M0_1> ... <M0_n>
<M1_0> <M1_1> ... <M1_n>
...
<Mm_0> <Mm_1> ... <Mm_n>

Example

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

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

$ ./a.out⏎
0⏎
Invalid matrix.

$ ./a.out⏎
3⏎
0⏎
Invalid matrix.

$ ./a.out⏎
3⏎
4⏎
-1⏎
Invalid matrix.

$ ./a.out⏎
3⏎
4⏎
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 insert_coo_matrix_element(
    coo_sparse_matrix &coo_matrix,
    unsigned long row,
    unsigned long col,
    long val);
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);
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;
    parse_coo_matrix(coo_matrix_M);
    std::cout << "The COO matrix is:" << std::endl;
    print_coo_matrix(coo_matrix_M);
    matrix matrix_M = convert_coo_matrix_to_matrix(coo_matrix_M);
    std::cout << "The matrix is:" << std::endl;
    print_matrix(matrix_M);
    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 insert_coo_matrix_element(
    coo_sparse_matrix &coo_matrix,
    unsigned long row,
    unsigned long col,
    long val);
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);
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;
    parse_coo_matrix(coo_matrix_M);
    sort_coo_matrix(coo_matrix_M);
    std::cout << "The COO matrix is:" << std::endl;
    print_coo_matrix(coo_matrix_M);
    matrix matrix_M = convert_coo_matrix_to_matrix(coo_matrix_M);
    std::cout << "The matrix is:" << std::endl;
    print_matrix(matrix_M);
    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;
    }
}