Sparse Matrix class
Nov 4, 2017 at 6:38pm UTC
Hi everybody !
I'm implementing a sparseMatrix class using vecor<map<index, type_value>> as container, i've implemented almost everything :
here the interface
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
template <typename element_type>
class SparseMatrix {
public :
template <class T>
friend SparseMatrix<T> operator +(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2 );
template <class T>
friend SparseMatrix<T> operator -(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2 );
public :
// container type ;
using data_type = std::vector<std::map<std::size_t , element_type >> ;
using it_rows = typename std::map<std::size_t , element_type>::iterator ;
SparseMatrix(std::size_t rows , std::size_t cols) : rows{rows} , columns{cols}
{
data.resize(rows);
}
SparseMatrix(std::initializer_list<std::initializer_list<element_type>> l );
SparseMatrix(const std::string );
auto insert(std::size_t i , std::pair<std::size_t, element_type> p )
{
assert( i < rows && p.first < columns); // , "Index out of bound" );
data.at(i).insert(p);
}
auto insert(std::size_t i, std::size_t j, element_type val)
{
assert(i<rows && j <columns);
data.at(i)[j] = val ;
}
auto identity() noexcept ;
auto diag(const element_type& v) noexcept ;
auto print() const noexcept ;
auto dataType() const noexcept ;
auto traspose() noexcept ;
private :
std::size_t rows ;
std::size_t columns ;
data_type data ; // vector containing row element
};
now I want to implement the matrix product ... i have no idea to how I can do it !
and one other thing , how looks like this traspose implementation ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
template <typename T>
auto SparseMatrix<T>::traspose() noexcept
{
//rows = columns ;
std::swap(rows,columns);
data_type newData ;
newData.resize(rows);
for (std::size_t i=0; i < columns ; i++)
{
for (std::size_t j=0 ; j < rows ; j++)
{
if (data.at(i).find(j) != data.at(i).end())
{
newData.at(j)[i] = data.at(i).at(j) ;
}
}
}
std::swap(data,newData);
}
Last edited on Nov 4, 2017 at 6:55pm UTC
Nov 4, 2017 at 7:47pm UTC
> now I want to implement the matrix product ... i have no idea to how I can do it !
Provide an overloaded operator, say
() , to access the element at a particular row and col.
If the element does not exist in the sparse matrix, return a default_constructed / alue_initialised
object (this would be zero for numeric types).
Then implement matrix product as it would be implemented for a normal matrix,
except that instead of
mtx[row][col] we would use
mtx(row,col)
Something along these lines:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
#include <iostream>
#include <map>
#include <cassert>
#include <stdexcept>
#include <iomanip>
template < typename T, T nothing = T{} > struct sparse_matrix
{
std::size_t nrows ;
std::size_t ncols ;
std::map< std::size_t, std::map<std::size_t,T> > data ;
sparse_matrix( std::size_t nrows, std::size_t ncols ) : nrows(nrows), ncols(ncols) {}
T operator () ( std::size_t row, std::size_t col ) const
{
const auto row_iter = data.find(row) ;
if ( row_iter != data.end() )
{
const auto col_iter = row_iter->second.find(col) ;
return col_iter != row_iter->second.end() ? col_iter->second : nothing ;
}
else return nothing ;
}
T& insert_or_update( std::size_t row, std::size_t col, const T& value )
{
assert( row < nrows && col < ncols ) ;
if ( row < nrows && col < ncols ) return data[row][col] = value ;
else throw std::out_of_range( "sparse_matrix: row/col is out of range" ) ;
}
std::ostream& print( std::ostream& stm = std::cout ) const
{
for ( std::size_t row = 0 ; row < nrows ; ++row )
{
for ( std::size_t col = 0 ; col < ncols ; ++col )
stm << std::setw(5) << operator ()(row,col) ;
stm << '\n' ;
}
return stm ;
}
};
int main()
{
sparse_matrix<int > mtx( 15, 10 ) ;
for ( std::size_t row = 1 ; row < mtx.nrows ; row += 3 )
for ( std::size_t col = 0 ; col < mtx.ncols ; col += 2 )
mtx.insert_or_update( row, col, row*10 + col ) ;
mtx.print() ;
}
http://rextester.com/ESU4466
Nov 5, 2017 at 1:15pm UTC
I've prefer use this solution :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
template <class T>
SparseMatrix<T> dot(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2 )
{
if (m1.columns != m2.rows)
{
throw std::runtime_error("Matrix sizes dosent match the dot-product" );
}
SparseMatrix<T> result{m1.rows , m2.columns };
for (std::size_t i=0 ; i < result.rows ; i++)
{
for (std::size_t j=0 ; j < result.columns ; j++ )
{
for (std::size_t k=0; k< m1.columns ; k++)
{
if ( m1.data.at(i).find(k) != m1.data.at(i).end() &&
m2.data.at(k).find(j) != m2.data.at(k).end() )
{
result.data.at(i)[j] += (m1.data.at(i).at(k) * m2.data.at(k).at(j)) ;
}
}
}
}
return result ;
}
Topic archived. No new replies allowed.