byslib/linalg/coo.hpp

• View this file on GitHub
• Last update: 2022-11-30 18:07:55+09:00
• Include: #include "byslib/linalg/coo.hpp"

Depends on

• byslib/core/int_alias.hpp
• byslib/linalg/sparsefwd.hpp

Required by

• Bellman Ford (byslib/graph/bellman_ford.hpp)
• byslib/graph/bfs.hpp
• byslib/graph/dfs.hpp
• byslib/graph/dijkstra.hpp
• byslib/graph/edge.hpp
• byslib/graph/graph.hpp
• byslib/graph/kruskal.hpp
• Lowest Common Ancestor (byslib/graph/lca.hpp)
• Reader (byslib/graph/reader.hpp)
• byslib/graph/shortest_path_tree.hpp
• Topological Sort (byslib/graph/topological_sort.hpp)
• byslib/graph/tree.hpp
• byslib/graph/util.hpp
• Warshall Floyd (byslib/graph/warshall_floyd.hpp)
• byslib/linalg/csr.hpp

Verified with

• test/AOJ/GRL_1_A.test.cpp
• test/AOJ/GRL_1_B.test.cpp
• test/AOJ/GRL_1_C.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#include "../core/int_alias.hpp"
#include "sparsefwd.hpp"

namespace bys {
template <class T> class COOMatrix {
  public:
    using value_type = T;
    const std::pair<i32, i32> shape;

  private:
    std::vector<std::tuple<i32, i32, T>> _data;
    std::vector<i32> _col_cnt;

  public:
    COOMatrix(i32 n, i32 m = -1) : shape{n, m}, _col_cnt(n) {}

    void set(i32 i, i32 j, const T& v) {
        assert(0 <= i and i < shape.first);
        ++_col_cnt[i];
        _data.emplace_back(i, j, v);
    }
    void push_back(i32 i, T&& v) { set(i, _col_cnt[i], std::forward<T>(v)); }
    template <class... Args> void emplace_back(i32 i, Args&&... args) { set(i, _col_cnt[i], {std::forward<Args>(args)...}); }
    auto begin() const { return _data.begin(); }
    auto end() const { return _data.end(); }

    void sort() {
        std::sort(_data.begin(), _data.end(), [](const std::tuple<i32, i32, T>& a, const std::tuple<i32, i32, T>& b) {
            return std::get<2>(a) < std::get<2>(b);
        });
    }
    std::size_t size() const { return shape.first; }
    std::ptrdiff_t ssize() const { return shape.first; }
    std::size_t nonzero() const { return _data.size(); }

    friend CSRMatrix<T>;
};
}  // namespace bys

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

#include <cstdint>
namespace bys {
using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
using f32 = float;
using f64 = double;
using f128 = long double;

using isize = std::ptrdiff_t;
using usize = std::size_t;

#define DEFINE_NUM_LITERAL(name, type) \
    constexpr auto operator"" name(unsigned long long x) { return static_cast<type>(x); }

DEFINE_NUM_LITERAL(_i8, std::int8_t);
DEFINE_NUM_LITERAL(_i16, std::int16_t);
DEFINE_NUM_LITERAL(_i32, std::int32_t);
DEFINE_NUM_LITERAL(_i64, std::int64_t);
DEFINE_NUM_LITERAL(_i128, __int128_t);
DEFINE_NUM_LITERAL(_u8, std::uint8_t);
DEFINE_NUM_LITERAL(_u16, std::uint16_t);
DEFINE_NUM_LITERAL(_u32, std::uint32_t);
DEFINE_NUM_LITERAL(_u64, std::uint64_t);
DEFINE_NUM_LITERAL(_u128, __uint128_t);
DEFINE_NUM_LITERAL(_z, std::size_t);
#undef DEFINE_NUM_LITERAL
}  // namespace bys
namespace bys {
template <class T> struct CSRMatrix;
}

namespace bys {
template <class T> class COOMatrix {
  public:
    using value_type = T;
    const std::pair<i32, i32> shape;

  private:
    std::vector<std::tuple<i32, i32, T>> _data;
    std::vector<i32> _col_cnt;

  public:
    COOMatrix(i32 n, i32 m = -1) : shape{n, m}, _col_cnt(n) {}

    void set(i32 i, i32 j, const T& v) {
        assert(0 <= i and i < shape.first);
        ++_col_cnt[i];
        _data.emplace_back(i, j, v);
    }
    void push_back(i32 i, T&& v) { set(i, _col_cnt[i], std::forward<T>(v)); }
    template <class... Args> void emplace_back(i32 i, Args&&... args) { set(i, _col_cnt[i], {std::forward<Args>(args)...}); }
    auto begin() const { return _data.begin(); }
    auto end() const { return _data.end(); }

    void sort() {
        std::sort(_data.begin(), _data.end(), [](const std::tuple<i32, i32, T>& a, const std::tuple<i32, i32, T>& b) {
            return std::get<2>(a) < std::get<2>(b);
        });
    }
    std::size_t size() const { return shape.first; }
    std::ptrdiff_t ssize() const { return shape.first; }
    std::size_t nonzero() const { return _data.size(); }

    friend CSRMatrix<T>;
};
}  // namespace bys

Back to top page