byslib/linalg/csr.hpp

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

Depends on

• byslib/core/int_alias.hpp
• Types (byslib/core/traits.hpp)
• byslib/extension/subrange.hpp
• byslib/linalg/coo.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)

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 <numeric>
#include <utility>
#include <vector>

#include "../core/int_alias.hpp"
#include "../extension/subrange.hpp"
#include "coo.hpp"

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

  private:
    std::vector<i32> _indptr, _indices;
    std::vector<T> _data;

  public:
    CSRMatrix(const COOMatrix<T>& coo)
        : shape(coo.shape), _indptr(coo._col_cnt), _indices(coo._data.size()), _data(coo._data.size()) {
        _indptr.push_back(0);

        std::partial_sum(_indptr.begin(), _indptr.end(), _indptr.begin());
        for (auto&& [i, j, v] : coo._data) {
            i32 index = --_indptr[i];
            _indices[index] = j;
            _data[index] = v;
        }
    }
    CSRMatrix(std::pair<i32, i32> shape, const std::vector<std::vector<std::pair<i32, T>>>& data)
        : shape(shape), _indptr(shape.first + 1) {
        for (i32 i = 0; i < shape.first; ++i) {
            for (auto&& [index, elem] : data[i]) {
                _indices.push_back(index);
                _data.push_back(elem);
            }
            _indptr[i + 1] += _indptr[i] + data[i].size();
        }
    }
    auto operator[](std::size_t i) const { return SubRange(_data.cbegin() + _indptr[i], _data.cbegin() + _indptr[i + 1]); }
    std::size_t size() const { return shape.first; }
    std::ptrdiff_t ssize() const { return shape.first; }
};
}  // namespace bys

#include <numeric>
#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
#include <cstddef>
#include <iterator>

#include <array>
#include <iostream>
#include <type_traits>
/**
 * @file traits.hpp
 * @brief Types
 *
 * type_traits拡張
 */
namespace bys {
template <class, class = void> struct has_rshift_from_istream : std::false_type {};
template <class T>
struct has_rshift_from_istream<T, std::void_t<decltype(std::declval<std::istream&>() >> std::declval<T&>())>> : std::true_type {};
template <class T> constexpr bool has_rshift_from_istream_v = has_rshift_from_istream<T>::value;

template <class, class = void> struct has_lshift_to_ostream : std::false_type {};
template <class T>
struct has_lshift_to_ostream<T, std::void_t<decltype(std::declval<std::ostream&>() << std::declval<T&>())>> : std::true_type {};
template <class T> constexpr bool has_lshft_to_ostream_v = has_lshift_to_ostream<T>::value;

template <class, class = void> struct is_tuple_like : std::false_type {};
template <class T> struct is_tuple_like<T, std::void_t<decltype(std::tuple_size<T>())>> : std::true_type {};
template <class T> constexpr bool is_tuple_like_v = is_tuple_like<T>::value;

template <class, class = void> struct is_iterable : std::false_type {};
template <class T> struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>()))>> : std::true_type {};
template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;

template <class T> struct Indexed {
    static_assert(std::is_integral_v<T>);
    using resolve_to = T;
};
using i32_1 = Indexed<i32>;
using i64_1 = Indexed<i64>;

template <class, class = void> struct is_indexed : std::false_type {};
template <class T> struct is_indexed<Indexed<T>> : std::true_type {};
template <class T> constexpr bool is_indexed_v = is_indexed<T>::value;

template <class T, class = void> struct resolve_type { using type = T; };
template <class T> struct resolve_type<T, std::void_t<typename T::resolve_to>> { using type = typename T::resolve_to; };
template <class T, std::size_t N> struct resolve_type<std::array<T, N>> {
    using type = std::array<typename resolve_type<T>::type, N>;
};
template <class T, class U> struct resolve_type<std::pair<T, U>> {
    using type = std::pair<typename resolve_type<T>::type, typename resolve_type<U>::type>;
};
template <class... Args> struct resolve_type<std::tuple<Args...>> {
    using type = std::tuple<typename resolve_type<Args>::type...>;
};
template <class T> using resolve_type_t = typename resolve_type<T>::type;
}  // namespace bys

namespace bys {
template <class Iterator> class SubRange {
  public:
    using iterator = Iterator;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using value_type = typename iterator::value_type;

    SubRange() = default;
    SubRange(const SubRange& s) : _begin(s._begin), _end(s._end) {}
    SubRange(const iterator& begin, const iterator& end) : _begin(begin), _end(end) {}

    iterator begin() const noexcept { return _begin; }
    iterator end() const noexcept { return _end; }
    reverse_iterator rbegin() const noexcept { return reverse_iterator{_end}; }
    reverse_iterator rend() const { return reverse_iterator{_begin}; }
    auto operator[](std::size_t i) const noexcept { return *(_begin + i); }
    auto size() const noexcept { return _end - _begin; }
    bool empty() const noexcept { return _begin == _end; }

    auto to_vec() const { return std::vector(_begin, _end); }

  private:
    iterator _begin, _end;
};
template <class Iterable> auto reversed(Iterable&& iter) {
    static_assert(is_iterable_v<Iterable>, "iter is not iterable");
    return SubRange(std::rbegin(std::forward<Iterable>(iter)), std::rend(std::forward<Iterable>(iter)));
}
}  // namespace bys
#include <algorithm>
#include <cassert>

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

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

  private:
    std::vector<i32> _indptr, _indices;
    std::vector<T> _data;

  public:
    CSRMatrix(const COOMatrix<T>& coo)
        : shape(coo.shape), _indptr(coo._col_cnt), _indices(coo._data.size()), _data(coo._data.size()) {
        _indptr.push_back(0);

        std::partial_sum(_indptr.begin(), _indptr.end(), _indptr.begin());
        for (auto&& [i, j, v] : coo._data) {
            i32 index = --_indptr[i];
            _indices[index] = j;
            _data[index] = v;
        }
    }
    CSRMatrix(std::pair<i32, i32> shape, const std::vector<std::vector<std::pair<i32, T>>>& data)
        : shape(shape), _indptr(shape.first + 1) {
        for (i32 i = 0; i < shape.first; ++i) {
            for (auto&& [index, elem] : data[i]) {
                _indices.push_back(index);
                _data.push_back(elem);
            }
            _indptr[i + 1] += _indptr[i] + data[i].size();
        }
    }
    auto operator[](std::size_t i) const { return SubRange(_data.cbegin() + _indptr[i], _data.cbegin() + _indptr[i + 1]); }
    std::size_t size() const { return shape.first; }
    std::ptrdiff_t ssize() const { return shape.first; }
};
}  // namespace bys

Back to top page