CSR

Defined in csr.hpp

template<class Label = uint32_t, class Ordinal = Label, class LabelStorage = Label*, class OrdinalStorage = Ordinal*, bool weighted = false, class Weight = float, class WeightStorage = Weight*>
class pigo::CSR

Holds compressed sparse row matrices or graphs.

This is a fundamental object in PIGO. It is used to represent sparse matrices and graphs. It can be loaded directly from files that are in adjacency formats, such as CHACO/METIS files.

In many cases, this is the desired format for a graph or matrix in memory. When sparse graphs or matrices are delivered in COO formats, such as matrix market or edge lists, they are frequently converted to CSR. This class can automatically handle such conversions internally.

tparam Label

the label data type. This type needs to be able to support the largest value read inside of the COO. In a graph this is the largest vertex ID.

tparam Ordinal

the ordinal data type. This type needs to support large enough values to hold the number of endpoints or rows in the COO. It defaults to the same type as the label type.

tparam LabelStorage

the storage type of the endpoints of the CSR. This can either be vector (std::vector<Label>), a pointer (Label*), or a shared_ptr (std::shared_ptr<Label>).

tparam OrdinalStorage

the storage type of the offsets of the CSR. This can either be vector (std::vector<Ordinal>), a pointer (Ordinal*), or a shared_ptr (std::shared_ptr<Ordinal>).

tparam weighted

if true, support and use weights

tparam Weight

the weight data type. This type needs to be able to support the largest value read inside of the COO. In a graph this is the largest vertex ID.

tparam WeightStorage

the storage type for the weights. This can be a raw pointer (Weight*), a std::vector (std::vector<Weight>), or a std::shared_ptr<Weight>.

Subclassed by pigo::BaseGraph< uint32_t, uint32_t, uint32_t *, uint32_t *, false, float, float * >, pigo::CSC< uint32_t, uint32_t, uint32_t *, uint32_t *, false, float, float * >

Public Functions

inline CSR()

Initialize an empty CSR.

inline CSR(Label n, Ordinal m, Label nrows, Label ncols)

Allocate a CSR for the given size.

template<class COOLabel, class COOOrdinal, class COOStorage, bool COOsym, bool COOut, bool COOsl, class COOW, class COOWS>
CSR(COO<COOLabel, COOOrdinal, COOStorage, COOsym, COOut, COOsl, weighted, COOW, COOWS> &coo)

Initialize from a COO.

This creates a CSR from an already-loaded COO.

Note that this will densely fill in all labels, so if there are many empty rows there will be unnecessary space used.

Template Parameters

  • COOLabel – the label for the COO format

  • COOOrdinal – the ordinal for the COO format

  • COOStorage – the storage format of the COO

  • COOsym – whether the COO is symmetrized

  • COOut – whether the COO only keeps the upper triangle

  • COOsl – whether the COO removes self loops

  • COOW – the weight type of the COO

  • COOWS – the weight storage type of the COO

Parameters

coo – the COO object to load the CSR from

CSR(std::string fn)

Initialize from a file.

The file type will attempt to be determined automatically.

Parameters

fn – the filename to open

CSR(std::string fn, FileType ft)

Initialize from a file with a specific type.

Parameters

  • fn – the filename to open

  • ft – the FileType to use

CSR(File &f, FileType ft)

Initialize from an open file with a specific type.

Parameters

  • f – the open File

  • ft – the FileType to use

inline LabelStorage &endpoints()

Return the endpoints.

Returns

the endpoints in the LabelStorage format

inline OrdinalStorage &offsets()

Return the offsets.

These contain Ordinals that show the offset for the current label into the endpoints. These are not pointers directly.

Returns

the offsets in the OrdinalStorage format

inline WeightStorage &weights()

Return the weights, if available.

This returns the WeightStorage for the weights, if the CSR is weighted.

Returns

the weights in the WeightStorage format

inline Ordinal m() const

Retrieves the number of endpoints in the CSR.

Returns

the count of endpoints

inline Label n() const

Retrieves the number of labels the CSR contains.

Note that this includes labels with no endpoints.

Returns

the number of labels

inline Label nrows() const

Retrieves the number of rows in the CSR.

Returns

the number of rows

inline Label ncols() const

Retrieves the number of columns in the CSR.

Returns

the number of columns

void sort()

Sort all row adjacencies in the CSR.

template<class nL = Label, class nO = Ordinal, class nLS = LabelStorage, class nOS = OrdinalStorage, bool nw = weighted, class nW = Weight, class nWS = WeightStorage>
CSR<nL, nO, nLS, nOS, nw, nW, nWS> new_csr_without_dups()

Return a new CSR without duplicate entries.

inline void free()

Utility to free consumed memory.

As an IO library, PIGO generally leaves memory cleanup to downstream applications and does not always deallocate in destructors. In some cases it is helpful for PIGO to cleanup directly and then this can be used.

size_t save_size() const

Return the size of the binary save file.

Returns

size_t containing the binary file size

void save(std::string fn)

Save the loaded CSR as a PIGO binary file.

This saves the current CSR to disk

Parameters

fn – the filename to save as

void save(File &w)

Save the loaded CSR as a PIGO binary file.

This saves the current CSR to an open file

Parameters

w – the File to save to

Public Static Attributes

static constexpr const char *csr_file_header = "PIGO-CSR-v2"

The output file header for reading/writing

type pigo::WCSRPtr
template<class Label = uint32_t, class Ordinal = Label, class LabelStorage = Label*, class OrdinalStorage = Ordinal*, bool weighted = false, class Weight = float, class WeightStorage = Weight*>
class CSC : public pigo::CSR<uint32_t, uint32_t, uint32_t*, uint32_t*, false, float, float*>

A compressed sparse column representation.

This is a transposed CSR.

tparam Label

the label data type. This type needs to be able to support the largest value read inside of the CSR. In a graph this is the largest vertex ID.

tparam Ordinal

the ordinal data type. This type needs to support large enough values to hold the number of endpoints or rows in the CSR. It defaults to the same type as the label type.

tparam LabelStorage

the storage type of the endpoints of the CSR. This can either be vector (std::vector<Label>), a pointer (Label*), or a shared_ptr (std::shared_ptr<Label>).

tparam OrdinalStorage

the storage type of the offsets of the CSR. This can either be vector (std::vector<Ordinal>), a pointer (Ordinal*), or a shared_ptr (std::shared_ptr<Ordinal>).

tparam weighted

if true, support and use weights

tparam Weight

the weight data type.

tparam WeightStorage

the storage type for the weights. This can be a raw pointer (Weight*), a std::vector (std::vector<Weight>), or a std::shared_ptr<Weight>.