CSR Matrix¶

Defined in data_structures/csr_matrix.hpp

enum sarma::Order¶

An enum type used to define row ordering of a given matrix. We provide three simple row ordering strategies.

Values:

enumerator ASC¶: Order rows in an ascending way st. |A(i,*)| <= |A(i+1,*)|

enumerator DSC¶: Order rows in an descending way st. |A(i,*)| >= |A(i+1,*)|

enumerator RCM¶: Order rows usin reverse Cuthill-McKee algorithm

enumerator NAT¶: Don’t apply any ordering. Default, natural order

enumerator RND¶: Random ordering

template<class Ordinal, class Value> struct sarma::matrix_base¶

Subclassed by sarma::Matrix< Ordinal, Value >

Public Functions

virtual std::vector<std::vector<Value>> compute_loads(const std::vector<Ordinal> &p, const std::vector<Ordinal> &q) const = 0¶

virtual Value compute_maxload(const std::vector<Ordinal> &p, const std::vector<Ordinal> &q) const = 0¶

virtual Value total_load() const = 0¶

template<class Ordinal, class Value> class sarma::Matrix : public sarma::matrix_base<Ordinal, Value>¶

Public Functions

inline auto data(std::size_t i) const¶: returns data[i] if using data, returns 1 otherwise.

inline const auto &get_data() const¶

inline virtual Value total_load() const¶

const auto &get_sps() const¶

inline void use_data(bool use)¶

if data exists, use=true changes matrix mode to use_data

Parameters

use: specifies whether data should be used

inline bool is_using_data() const¶

inline bool is_pattern() const¶: returns whether the matrix has data stored.

inline Ordinal N() const¶: please note that the vector indptr is csr representation and size of the vector is N_ + 1, here we add a conventional method for getting the number of indptr. However the size of the vector is actually N + 1, so please keep that in mind.

inline Ordinal NNZ() const¶

Matrix() = default¶

inline Matrix(const ns_filesystem::path &path, const bool use_data = false)¶: IO constructor Construct the graph from a file that should be formatted as our csr format.

inline Matrix(const std::vector<std::pair<Ordinal, Ordinal>> &pts, const std::vector<Value> &data, bool _use_data = false)¶

inline Matrix(std::vector<Ordinal> &&indptr, std::vector<Ordinal> &&indices, std::vector<Value> &&data, const Ordinal M, bool use_data_ = false)¶

Constructor to create a graph given all the class members.

Note: uses move semantics.

inline Matrix(const std::vector<Ordinal> &indptr, const std::vector<Ordinal> &indices, const std::vector<Value> &data, const Ordinal M, bool use_data_ = false)¶: Constructor to create a graph given all the class members this one is for mostly external usage, uses copy instead of move.

inline Matrix(const Matrix &other)¶

inline Matrix &operator=(const Matrix &other)¶

inline Matrix(Matrix &&other)¶

inline Matrix &operator=(Matrix &&other)¶

inline Matrix(const std::vector<std::vector<Ordinal>> A)¶: Constructor from dense matrix This will be used for testing purposes.

inline void read_binary(std::istream &in, const bool use_data)¶

inline void read_matrix_market(std::FILE *f, const bool use_data)¶

inline virtual Value compute_maxload(const std::vector<Ordinal> &p, const std::vector<Ordinal> &q) const¶

inline virtual std::vector<std::vector<Value>> compute_loads(const std::vector<Ordinal> &p, const std::vector<Ordinal> &q) const¶

template<typename Real = double> inline void print(std::ostream &out, const std::vector<Ordinal> &p, const std::vector<Ordinal> &q, bool symmetric, Real sp_time, Real ds_time, Real par_time) const¶

inline Matrix transpose() const¶: Get the transpose of the graph.

inline Matrix &sort()¶

inline auto sparsify(const double keep_prob, const int seed = 1) const¶

Return a sparsified matrix.

Parameters

prob: Sparsification factor
seed: Seed for coin tosses

inline bool verify_id_map(const std::vector<Ordinal> &map, Ordinal expected_size, Ordinal min_id = 0) const¶

used for re-ordering, to check whether if map is one-to-one id maping from [0…expected_size-1] to [min_id…min_id+expected_size-1] @parameter map, the id mapping to be verified @parameter expected_size, the expected size of map @parameter min_id, the minimum id of the ids to be mapped to

Return: whether map is valid

inline auto reverse_id_map(const std::vector<Ordinal> &map) const¶

reverse id map @parameter map, the map to be reversed. map is expected to be valid as verified in the verify_id_map

Return: reversed_map

inline Matrix order(Order order = Order::NAT, bool triangular = false, bool reverse = false, int seed = 1) const¶

Generalized order function.

Note

that reverse is by default true for ASC, and false for DSC

Parameters

type: ASC, DSC, RCM or NAT
triangular: Flag to use only upper half of matrix
reverse: decides rcm is reversed

inline Matrix order(const std::vector<Ordinal> &_rows_id_map, const std::vector<Ordinal> &_cols_id_map, bool rows_new_to_org = false, bool cols_new_to_org = false) const¶

ReOrder rows and cols @parameter _rows_id_map, mapping between new row id and old row id @parameter _cols_id_map, mapping between new row id and old row id @parameter rows_new_to_org, true indicating _rows_id_map[new_row_id] = old_row_id; false indicating _rows_id_map[old_row_id] = new_row_id @parameter cols_new_to_org, true indicating _cols_id_map[new_row_id] = old_row_id; false indicating _cols_id_map[old_row_id] = new_row_id.

Return: new matrix, with the new orders of rows and cols.

inline Matrix order_cols(const std::vector<Ordinal> &_map, bool new_to_org = false) const¶

ReOrder cols only.

Return

new matrix, such that the order of cols are shuffled based on map.

Parameters

maplenght: M vector, represents the mapping relationship of org id and new id
new_to_orgif: true, map[i] represents new col i is the origin col map[i] otherwise the other way around

inline Matrix order_rows(const std::vector<Ordinal> &_map, bool new_to_org = false) const¶

ReOrder rows only.

Return

new matrix, such that the order of rows are shuffled based on map.

Parameters

maplenght: N() vector, represents the mapping relationship of org id and new id
new_to_orgif: true, map[i] represents new row i is the origin row map[i] otherwise the other way around

inline void serialize(std::string filename) const¶

serialize the graph into a file

Parameters

filename:

inline void serialize_block(const std::vector<Ordinal> cuts, std::string filename) const¶

take a partition vector and serialize as block csr

Parameters

cuts: partition vector
filename: output file name

Public Members

const std::vector<Ordinal> &indptr = indptr_¶

const std::vector<Ordinal> &indices = indices_¶

const Ordinal &M = M_¶

const bool &sorted = sorted_¶

Friends

inline friend friend std::ostream & operator<< (std::ostream &os, const Matrix &g): simple override of graph ostream