From e9800d103fcdd19f0417e89781761f7f85d8ec9b Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Fri, 18 May 2018 10:52:51 +0200 Subject: Column types are separated, and the matrix representation is more general in its container type --- include/phat/boundary_matrix.h | 74 ++++++--- include/phat/representations/Container_traits.h | 75 +++++++++ .../phat/representations/Pivot_representation.h | 118 ++++++++++++++ .../phat/representations/Uniform_representation.h | 112 ++++++++++++++ .../Unordered_map_container_traits.h | 120 +++++++++++++++ .../phat/representations/abstract_pivot_column.h | 102 ------------- .../phat/representations/bit_tree_pivot_column.h | 11 +- .../phat/representations/default_representations.h | 47 ++++++ include/phat/representations/full_pivot_column.h | 11 +- include/phat/representations/heap_pivot_column.h | 14 +- include/phat/representations/list_column_rep.h | 97 ++++++++++++ include/phat/representations/set_column_rep.h | 96 ++++++++++++ include/phat/representations/sparse_pivot_column.h | 11 +- include/phat/representations/vector_column_rep.h | 102 +++++++++++++ include/phat/representations/vector_heap.h | 170 --------------------- include/phat/representations/vector_list.h | 101 ------------ include/phat/representations/vector_set.h | 99 ------------ include/phat/representations/vector_vector.h | 107 ------------- src/benchmark.cpp | 10 +- src/convert.cpp | 2 +- src/phat.cpp | 11 +- src/self_test.cpp | 92 ++++++----- src/simple_example.cpp | 2 +- 23 files changed, 906 insertions(+), 678 deletions(-) create mode 100644 include/phat/representations/Container_traits.h create mode 100644 include/phat/representations/Pivot_representation.h create mode 100644 include/phat/representations/Uniform_representation.h create mode 100644 include/phat/representations/Unordered_map_container_traits.h delete mode 100644 include/phat/representations/abstract_pivot_column.h create mode 100644 include/phat/representations/default_representations.h create mode 100644 include/phat/representations/list_column_rep.h create mode 100644 include/phat/representations/set_column_rep.h create mode 100644 include/phat/representations/vector_column_rep.h delete mode 100644 include/phat/representations/vector_heap.h delete mode 100644 include/phat/representations/vector_list.h delete mode 100644 include/phat/representations/vector_set.h delete mode 100644 include/phat/representations/vector_vector.h diff --git a/include/phat/boundary_matrix.h b/include/phat/boundary_matrix.h index f864dee..295cfa5 100644 --- a/include/phat/boundary_matrix.h +++ b/include/phat/boundary_matrix.h @@ -19,12 +19,14 @@ #pragma once #include -#include +#include -// interface class for the main data structure -- implementations of the interface can be found in ./representations namespace phat { - template< class Representation = bit_tree_pivot_column > - class boundary_matrix + +// interface class for the main data structure -- implementations of the interface can be found in ./representations + + template< class Representation = bit_tree_pivot_column > + class boundary_matrix { protected: @@ -45,28 +47,39 @@ namespace phat { void set_dim( index idx, dimension dim ) { rep._set_dim( idx, dim ); } // replaces content of @col with boundary of given index - void get_col( index idx, column& col ) const { col.clear(); rep._get_col( idx, col ); } + void get_col( index idx, column& col ) const { + rep._get_col( idx, col ); + } // set column @idx to the values contained in @col - void set_col( index idx, const column& col ) { rep._set_col( idx, col ); } + void set_col( index idx, const column& col ) { + rep._set_col( idx, col ); } // true iff boundary of given column is empty - bool is_empty( index idx ) const { return rep._is_empty( idx ); } + bool is_empty( index idx ) const { + return rep._is_empty(idx); + } // largest index of given column (new name for lowestOne()) -- NOT thread-safe - index get_max_index( index idx ) const { return rep._get_max_index( idx ); } + index get_max_index( index idx ) const { + return rep._get_max_index(idx); } // removes maximal index from given column - void remove_max( index idx ) { rep._remove_max( idx ); } + void remove_max( index idx ) { + return rep._remove_max( idx ); + } // adds column @source to column @target' - void add_to( index source, index target ) { rep._add_to( source, target ); } + void add_to( index source, index target ) { + rep._add_to( source, target ); } // clears given column - void clear( index idx ) { rep._clear( idx ); } + void clear( index idx ) { + rep._clear(idx); } // finalizes given column - void finalize( index idx ) { rep._finalize( idx ); } + void finalize( index idx ) { + rep._finalize(idx); } // synchronizes all internal data structures -- has to be called before and after any multithreaded access! void sync() { rep._sync(); } @@ -131,6 +144,10 @@ namespace phat { *this = other; } + boundary_matrix( const boundary_matrix& other) { + *this = other; + } + template< typename OtherRepresentation > bool operator==( const boundary_matrix< OtherRepresentation >& other_boundary_matrix ) const { const index number_of_columns = this->get_num_cols(); @@ -154,20 +171,30 @@ namespace phat { return !( *this == other_boundary_matrix ); } + template< typename OtherRepresentation > - boundary_matrix< Representation >& operator=( const boundary_matrix< OtherRepresentation >& other ) + boundary_matrix< Representation >& assign(const boundary_matrix< OtherRepresentation >& other) { + const index nr_of_columns = other.get_num_cols(); + this->set_num_cols( nr_of_columns ); + column temp_col; + for( index cur_col = 0; cur_col < nr_of_columns; cur_col++ ) { + this->set_dim( cur_col, other.get_dim( cur_col ) ); + other.get_col( cur_col, temp_col ); + this->set_col( cur_col, temp_col ); + } + // by convention, always return *this + return *this; + } + + boundary_matrix< Representation >& operator=( const boundary_matrix< Representation >& other ) { - const index nr_of_columns = other.get_num_cols(); - this->set_num_cols( nr_of_columns ); - column temp_col; - for( index cur_col = 0; cur_col < nr_of_columns; cur_col++ ) { - this->set_dim( cur_col, other.get_dim( cur_col ) ); - other.get_col( cur_col, temp_col ); - this->set_col( cur_col, temp_col ); - } + return assign(other); + } - // by convention, always return *this - return *this; + template< typename OtherRepresentation > + boundary_matrix< Representation >& operator=( const boundary_matrix< OtherRepresentation >& other ) + { + return assign(other); } // I/O -- independent of chosen 'Representation' @@ -181,6 +208,7 @@ namespace phat { column temp_col; #pragma omp parallel for private( temp_col ) for( index cur_col = 0; cur_col < nr_of_columns; cur_col++ ) { + //std::cout << "At index " << cur_col << " of " << nr_of_columns << " " << omp_get_thread_num() << std::endl; this->set_dim( cur_col, (dimension)input_dims[ cur_col ] ); index num_rows = input_matrix[ cur_col ].size(); diff --git a/include/phat/representations/Container_traits.h b/include/phat/representations/Container_traits.h new file mode 100644 index 0000000..9ab4b5c --- /dev/null +++ b/include/phat/representations/Container_traits.h @@ -0,0 +1,75 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +namespace phat { + +template + class Column_container_traits { + + public: + + typedef ColumnContainer Column_container; + typedef typename Column_container::value_type Column_type; + + Column_type& col_at(Column_container& data, index idx) const { + return data[ idx ]; + } + + const Column_type& col_at(const Column_container& data, index idx) const { + return data[ idx ]; + } + + index get_size(const Column_container& data) const { + return data.size(); + } + + void resize(Column_container& data, index nr_of_columns) const { + data.resize(nr_of_columns); + } + +}; + +template + class Dimension_container_traits { + + public: + + typedef DimensionContainer Dimension_container; + + index& dim_at(Dimension_container& data, index idx) const { + return data[ idx ]; + } + + const index& dim_at(const Dimension_container& data, index idx) const { + return data[ idx ]; + } + + index get_size(const Dimension_container& data) const { + return data.size(); + } + + void resize(Dimension_container& data, index nr_of_columns) const { + data.resize(nr_of_columns); + } + +}; + + +} // namespace phat diff --git a/include/phat/representations/Pivot_representation.h b/include/phat/representations/Pivot_representation.h new file mode 100644 index 0000000..324c888 --- /dev/null +++ b/include/phat/representations/Pivot_representation.h @@ -0,0 +1,118 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include + +namespace phat{ + +template + class Pivot_representation : public BaseRepresentation { + + public: + + typedef BaseRepresentation Base; + typedef PivotColumn Pivot_column; + + protected: + + // For parallization purposes, it could be more than one full column + mutable thread_local_storage< Pivot_column > pivot_cols; + mutable thread_local_storage< index > idx_of_pivot_cols; + + Pivot_column& get_pivot_col() const { + return pivot_cols(); + } + + bool is_pivot_col( index idx ) const { + return idx_of_pivot_cols() == idx; + } + + void release_pivot_col() { + index idx = idx_of_pivot_cols(); + if( idx != -1 ) { + Base::_clear(idx); + column col; + pivot_cols().get_col_and_clear( col ); + Base::_set_col(idx, col); + } + idx_of_pivot_cols() = -1; + } + + void make_pivot_col( index idx ) { + release_pivot_col(); + idx_of_pivot_cols() = idx; + // Remark: Converting the column to a vector first gives a huge performance + // penalty, due to the fact that data is copied around + //column col; + //Base::_get_col( idx, col ); + + get_pivot_col().add_col( Base::col_traits.col_at(Base::matrix,idx).begin(), + Base::col_traits.col_at(Base::matrix,idx).end()); + + //get_pivot_col().add_col( Base::matrix[idx]); + } + + public: + + void _set_num_cols( index nr_of_cols ) { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) { + pivot_cols[ tid ].init( nr_of_cols ); + idx_of_pivot_cols[ tid ] = -1; + } + Base::_set_num_cols( nr_of_cols ); + } + + void _add_to( index source, index target ) { + if( !is_pivot_col( target ) ) + make_pivot_col( target ); + //column col; + //Base::_get_col(source,col); + + get_pivot_col().add_col( Base::col_traits.col_at(Base::matrix,source).begin(), + Base::col_traits.col_at(Base::matrix,source).end() ); + + //get_pivot_col().add_col(Base::matrix[source]); + } + + void _sync() { + #pragma omp parallel for + for( int tid = 0; tid < omp_get_num_threads(); tid++ ) + release_pivot_col(); + } + + void _get_col( index idx, column& col ) const { is_pivot_col( idx ) ? get_pivot_col().get_col( col ) : Base::_get_col( idx, col ); } + + bool _is_empty( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().is_empty() : Base::_is_empty( idx ); } + + index _get_max_index( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().get_max_index() : Base::_get_max_index( idx ); } + + void _clear( index idx ) { is_pivot_col( idx ) ? get_pivot_col().clear() : Base::_clear( idx ); } + + void _set_col( index idx, const column& col ) { is_pivot_col( idx ) ? get_pivot_col().set_col( col ) : Base::_set_col( idx, col ); } + + void _remove_max( index idx ) { is_pivot_col( idx ) ? get_pivot_col().remove_max() : Base::_remove_max( idx ); } + + void finalize( index idx ) { Base::_finalize( idx ); } + +}; + + +} diff --git a/include/phat/representations/Uniform_representation.h b/include/phat/representations/Uniform_representation.h new file mode 100644 index 0000000..ccbf6a3 --- /dev/null +++ b/include/phat/representations/Uniform_representation.h @@ -0,0 +1,112 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include + +namespace phat { + +template +class Uniform_representation { + + public: + + typedef ColumnContainer Column_container; + typedef DimensionContainer Dimension_container; + + typedef Column_container_traits Column_traits; + typedef Dimension_container_traits Dimension_traits; + + + typedef typename Column_traits::Column_type Column_type; + + protected: + + // We need to label them mutable, since we have no control whether + // the representations are manipulated by the traits class + mutable Dimension_container dims; + mutable Column_container matrix; + + Column_traits col_traits; + Dimension_traits dim_traits; + + thread_local_storage< column > temp_column_buffer; + + public: + + index _get_num_cols() const { + return col_traits.get_size(matrix); + } + + void _set_num_cols(index nr_of_columns) { + col_traits.resize(matrix, nr_of_columns); + for(index idx = 0;idx < nr_of_columns;idx++) { + col_traits.col_at(matrix,idx).offer_thread_local_storage(&temp_column_buffer); + } + dim_traits.resize(dims, nr_of_columns); + } + + dimension _get_dim( index idx ) const { + return dim_traits.dim_at(dims, idx ); + } + + void _set_dim( index idx, dimension dim ) { + dim_traits.dim_at(dims,idx) = dim; + } + + void _get_col( index idx, column& col ) const { + col_traits.col_at(matrix, idx)._get_col( col ); + } + + void _set_col( index idx, const column& col ) { + //col_traits.col_at(matrix, idx)._set_col( col ); + matrix[idx]._set_col(col); + } + + bool _is_empty( index idx ) const { + return col_traits.col_at(matrix, idx)._is_empty(); + } + + index _get_max_index( index idx ) const { + return col_traits.col_at(matrix, idx)._get_max_index(); + } + + void _remove_max( index idx ) { + return col_traits.col_at(matrix, idx)._remove_max(); + } + + void _add_to( index source, index target ) { + Column_type& source_col = col_traits.col_at(matrix, source); + Column_type& target_col = col_traits.col_at(matrix, target); + target_col._add_to( source_col ); + } + + void _clear( index idx ) { + col_traits.col_at(matrix, idx)._clear(); + } + + void _finalize( index idx ) { + col_traits.col_at(matrix, idx)._finalize(); + } + + void _sync() {} + +}; + +} diff --git a/include/phat/representations/Unordered_map_container_traits.h b/include/phat/representations/Unordered_map_container_traits.h new file mode 100644 index 0000000..0e54be6 --- /dev/null +++ b/include/phat/representations/Unordered_map_container_traits.h @@ -0,0 +1,120 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +// This file requires c++11 + +#include + +#include +#include + +namespace phat{ + +template + class Column_container_traits< std::unordered_map > { + + protected: + + index _size; + + mutable std::mutex _mutex; + + public: + + typedef std::unordered_map Column_container; + + typedef ColumnType Column_type; + + Column_type& col_at(Column_container& data, index idx) const { + _mutex.lock(); + typename Column_container::iterator it = data.find(idx); + if(it==data.end()) { + std::pair result + = data.insert(std::make_pair(idx,Column_type())); + it = result.first; + } + _mutex.unlock(); + return it->second; + } + + /* + const Column_type& col_at(const Column_container& data, index idx) const { + if(data.find(idx)==data.end()) { + data.insert(std::make_pair(idx,Column_type())); + } + return data.at(idx); + } + */ + + index get_size(const Column_container& data) const { + return _size; + } + + void resize(Column_container& data, index nr_of_columns) { + _size = nr_of_columns; + } + + }; + +template<> + class Dimension_container_traits< std::unordered_map > { + + protected: + + index _size; + + mutable std::mutex _mutex; + + public: + + typedef std::unordered_map Dimension_container; + + index& dim_at(Dimension_container& data, index idx) const { + _mutex.lock(); + typename Dimension_container::iterator it = data.find(idx); + if(it==data.end()) { + std::pair result + = data.insert(std::make_pair(idx,0)); + it = result.first; + } + _mutex.unlock(); + return it->second; + } + + /* + const index& dim_at(Dimension_container& data, index idx) const { + if(data.find(idx)==data.end()) { + data.insert(std::make_pair(idx,0)); + } + return data.at(idx); + } + */ + + index get_size(const Dimension_container& data) const { + return _size; + } + + void resize(Dimension_container& data, index nr_of_columns) { + _size = nr_of_columns; + } + + }; + +} // of namespace phat diff --git a/include/phat/representations/abstract_pivot_column.h b/include/phat/representations/abstract_pivot_column.h deleted file mode 100644 index e16d7a5..0000000 --- a/include/phat/representations/abstract_pivot_column.h +++ /dev/null @@ -1,102 +0,0 @@ -/* Copyright 2013 IST Austria - Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus - - This file is part of PHAT. - - PHAT is free software: you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - PHAT is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License - along with PHAT. If not, see . */ - -#pragma once - -#include -#include - -namespace phat { - - // Note: We could even make the rep generic in the underlying Const representation - // But I cannot imagine that anything else than vector> would - // make sense - template< typename PivotColumn > - class abstract_pivot_column : public vector_vector { - - protected: - typedef vector_vector Base; - typedef PivotColumn pivot_col; - - // For parallization purposes, it could be more than one full column - mutable thread_local_storage< pivot_col > pivot_cols; - mutable thread_local_storage< index > idx_of_pivot_cols; - - pivot_col& get_pivot_col() const { - return pivot_cols(); - } - - bool is_pivot_col( index idx ) const { - return idx_of_pivot_cols() == idx; - } - - void release_pivot_col() { - index idx = idx_of_pivot_cols(); - if( idx != -1 ) { - this->matrix[ idx ].clear(); - pivot_cols().get_col_and_clear( this->matrix[ idx ] ); - } - idx_of_pivot_cols() = -1; - } - - void make_pivot_col( index idx ) { - release_pivot_col(); - idx_of_pivot_cols() = idx; - get_pivot_col().add_col( matrix[ idx ] ); - } - - public: - - void _set_num_cols( index nr_of_cols ) { - #pragma omp parallel for - for( int tid = 0; tid < omp_get_num_threads(); tid++ ) { - pivot_cols[ tid ].init( nr_of_cols ); - idx_of_pivot_cols[ tid ] = -1; - } - Base::_set_num_cols( nr_of_cols ); - } - - void _add_to( index source, index target ) { - if( !is_pivot_col( target ) ) - make_pivot_col( target ); - get_pivot_col().add_col( matrix[source] ); - } - - void _sync() { - #pragma omp parallel for - for( int tid = 0; tid < omp_get_num_threads(); tid++ ) - release_pivot_col(); - } - - void _get_col( index idx, column& col ) const { is_pivot_col( idx ) ? get_pivot_col().get_col( col ) : Base::_get_col( idx, col ); } - - bool _is_empty( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().is_empty() : Base::_is_empty( idx ); } - - index _get_max_index( index idx ) const { return is_pivot_col( idx ) ? get_pivot_col().get_max_index() : Base::_get_max_index( idx ); } - - void _clear( index idx ) { is_pivot_col( idx ) ? get_pivot_col().clear() : Base::_clear( idx ); } - - void _set_col( index idx, const column& col ) { is_pivot_col( idx ) ? get_pivot_col().set_col( col ) : Base::_set_col( idx, col ); } - - void _remove_max( index idx ) { is_pivot_col( idx ) ? get_pivot_col().remove_max() : Base::_remove_max( idx ); } - - void finalize( index idx ) { Base::_finalize( idx ); } - }; -} - - diff --git a/include/phat/representations/bit_tree_pivot_column.h b/include/phat/representations/bit_tree_pivot_column.h index 4d48e88..4779d70 100644 --- a/include/phat/representations/bit_tree_pivot_column.h +++ b/include/phat/representations/bit_tree_pivot_column.h @@ -19,7 +19,6 @@ #pragma once #include -#include namespace phat { @@ -133,6 +132,15 @@ namespace phat { std::reverse( out.begin(), out.end() ); } + + template + void add_col(InputIterator begin, InputIterator end) { + for(InputIterator it=begin;it!=end;it++) { + add_index(*it); + } + } + + void add_col(const column &col) { for( size_t i = 0; i < col.size(); ++i ) add_index(col[i]); @@ -161,5 +169,4 @@ namespace phat { } }; - typedef abstract_pivot_column bit_tree_pivot_column; } diff --git a/include/phat/representations/default_representations.h b/include/phat/representations/default_representations.h new file mode 100644 index 0000000..a0f618f --- /dev/null +++ b/include/phat/representations/default_representations.h @@ -0,0 +1,47 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + + +namespace phat { + + // typedef Uniform_representation< std::unordered_map, std::unordered_map > hash_vector; + typedef Uniform_representation< std::vector, std::vector > vector_vector; + typedef Uniform_representation< std::vector, std::vector > vector_set; + typedef Uniform_representation< std::vector, std::vector > vector_heap; + typedef Uniform_representation< std::vector, std::vector > vector_list; + typedef Pivot_representation< vector_vector, full_column > full_pivot_column; + typedef Pivot_representation< vector_vector, heap_column > heap_pivot_column; + typedef Pivot_representation< vector_vector, sparse_column > sparse_pivot_column; + typedef Pivot_representation< vector_vector, bit_tree_column > bit_tree_pivot_column; + +} diff --git a/include/phat/representations/full_pivot_column.h b/include/phat/representations/full_pivot_column.h index c2e9e3c..a6a09d1 100644 --- a/include/phat/representations/full_pivot_column.h +++ b/include/phat/representations/full_pivot_column.h @@ -19,7 +19,6 @@ #pragma once #include -#include namespace phat { class full_column { @@ -35,6 +34,15 @@ namespace phat { is_in_history.resize( total_size, false ); } + + template + void add_col(InputIterator begin, InputIterator end) { + for(InputIterator it=begin;it!=end;it++) { + add_index(*it); + } + } + + void add_col( const column& col ) { for( index idx = 0; idx < (index) col.size(); idx++ ) { add_index( col[ idx ] ); @@ -96,5 +104,4 @@ namespace phat { } }; - typedef abstract_pivot_column< full_column > full_pivot_column; } diff --git a/include/phat/representations/heap_pivot_column.h b/include/phat/representations/heap_pivot_column.h index 33cd07b..c5e4313 100644 --- a/include/phat/representations/heap_pivot_column.h +++ b/include/phat/representations/heap_pivot_column.h @@ -19,7 +19,6 @@ #pragma once #include -#include namespace phat { class heap_column { @@ -71,6 +70,18 @@ namespace phat { clear(); } + + template + void add_col(InputIterator begin, InputIterator end) { + for(InputIterator it=begin;it!=end;it++) { + data.push(*it); + inserts_since_last_prune++; + } + if( 2 * inserts_since_last_prune >( index ) data.size( ) ) + prune(); + } + + void add_col( const column& col ) { for( index idx = 0; idx < (index) col.size(); idx++ ) data.push( col[ idx ] ); @@ -122,5 +133,4 @@ namespace phat { } }; - typedef abstract_pivot_column< heap_column > heap_pivot_column; } diff --git a/include/phat/representations/list_column_rep.h b/include/phat/representations/list_column_rep.h new file mode 100644 index 0000000..5de2652 --- /dev/null +++ b/include/phat/representations/list_column_rep.h @@ -0,0 +1,97 @@ +/* Copyright 2013 IST Austria + Contributed by: Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include + +namespace phat { + class list_column_rep { + + protected: + std::list< index > indices; + + public: + + typedef list_column_rep Self; + + std::list::const_iterator begin() const { + return indices.begin(); + } + + std::list::const_iterator end() const { + return indices.end(); + } + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const { + col.clear(); + col.reserve( indices.size() ); + std::copy (indices.begin(), indices.end(), std::back_inserter(col) ); + } + + void _set_col( const column& col ) { + indices.clear(); + indices.resize( col.size() ); + std::copy (col.begin(), col.end(), indices.begin() ); + } + + // true iff boundary of given idx is empty + bool _is_empty() const { + return indices.empty(); + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const { + return indices.empty() ? -1 : *indices.rbegin(); + } + + // removes the maximal index of a column + void _remove_max() { + std::list< index >::iterator it = indices.end(); + it--; + indices.erase( it ); + } + + // clears given column + void _clear() { + indices.clear(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync() {} + + // adds column 'source' to column 'target' + void _add_to( Self& source) { + std::list< index >& source_col = source.indices; + std::list< index >& target_col = this->indices; + std::list< index > temp_col; + target_col.swap( temp_col ); + std::set_symmetric_difference( temp_col.begin(), temp_col.end(), + source_col.begin(), source_col.end(), + std::back_inserter( target_col ) ); + } + + // finalizes given column + void _finalize() { + } + }; +} diff --git a/include/phat/representations/set_column_rep.h b/include/phat/representations/set_column_rep.h new file mode 100644 index 0000000..c43b74e --- /dev/null +++ b/include/phat/representations/set_column_rep.h @@ -0,0 +1,96 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include + +namespace phat { + class set_column_rep { + + protected: + std::set< index > indices; + + public: + + typedef set_column_rep Self; + + std::set::const_iterator begin() const { + return indices.begin(); + } + + std::set::const_iterator end() const { + return indices.end(); + } + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const { + col.clear(); + col.reserve( indices.size() ); + std::copy (indices.begin(), indices.end(), std::back_inserter(col) ); + } + void _set_col( const column& col ) { + indices.clear(); + indices.insert( col.begin(), col.end() ); + } + + // true iff boundary of given idx is empty + bool _is_empty() const { + return indices.empty(); + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const { + return indices.empty() ? -1 : *indices.rbegin(); + } + + // removes the maximal index of a column + void _remove_max() { + std::set< index >::iterator it = indices.end(); + it--; + indices.erase( it ); + } + + // clears given column + void _clear() { + indices.clear(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync() {} + + // adds column 'source' to column 'target' + void _add_to( Self& source) { + + std::set< index >& col = this->indices; + for( std::set< index >::iterator it = source.indices.begin(); it != source.indices.end(); it++ ) { + std::pair< std::set< index >::iterator, bool > result = col.insert( *it ); + if( !result.second ) + col.erase( result.first ); + } + } + + // finalizes given column + void _finalize() { + } + + }; +} diff --git a/include/phat/representations/sparse_pivot_column.h b/include/phat/representations/sparse_pivot_column.h index 390fd91..bbaf98c 100644 --- a/include/phat/representations/sparse_pivot_column.h +++ b/include/phat/representations/sparse_pivot_column.h @@ -19,7 +19,6 @@ #pragma once #include -#include namespace phat { class sparse_column { @@ -37,6 +36,15 @@ namespace phat { void init( const index total_size ) { data.clear(); } + + + template + void add_col(InputIterator begin, InputIterator end) { + for(InputIterator it=begin;it!=end;it++) { + add_index(*it); + } + } + void add_col( const column& col ) { for( index idx = 0; idx < (index) col.size(); idx++ ) @@ -75,5 +83,4 @@ namespace phat { } }; - typedef abstract_pivot_column< sparse_column > sparse_pivot_column; } diff --git a/include/phat/representations/vector_column_rep.h b/include/phat/representations/vector_column_rep.h new file mode 100644 index 0000000..22c37ef --- /dev/null +++ b/include/phat/representations/vector_column_rep.h @@ -0,0 +1,102 @@ +/* Copyright 2013 IST Austria + Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus + + This file is part of PHAT. + + PHAT is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + PHAT is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with PHAT. If not, see . */ + +#pragma once + +#include + +namespace phat { + class vector_column_rep { + + protected: + + std::vector indices; + + thread_local_storage< column >* temp_column_buffer; + + public: + + typedef vector_column_rep Self; + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + temp_column_buffer=tls; + } + + std::vector::const_iterator begin() const { + return indices.begin(); + } + + std::vector::const_iterator end() const { + return indices.end(); + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const { + col.clear(); + col = indices; + } + void _set_col( const column& col ) { + indices = col; + } + + // true iff boundary of given idx is empty + bool _is_empty() const { + return indices.empty(); + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const { + return indices.empty() ? -1 : indices.back(); + } + + // removes the maximal index of a column + void _remove_max() { + indices.pop_back(); + } + + // clears given column + void _clear() { + indices.clear(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync() {} + + // adds column 'source' to column 'target' + void _add_to( const Self& source_col ) { + column& temp_col = (*temp_column_buffer)(); + + size_t new_size = source_col.indices.size() + this->indices.size(); + + if (new_size > temp_col.size()) temp_col.resize(new_size); + + std::vector::iterator col_end = std::set_symmetric_difference( this->indices.begin(), this->indices.end(), + source_col.indices.begin(), source_col.indices.end(), + temp_col.begin() ); + temp_col.erase(col_end, temp_col.end()); + + + this->indices.swap(temp_col); + } + + // finalizes given column + void _finalize() { + column(indices.begin(), indices.end()).swap(indices); + } + }; +} diff --git a/include/phat/representations/vector_heap.h b/include/phat/representations/vector_heap.h deleted file mode 100644 index db0420f..0000000 --- a/include/phat/representations/vector_heap.h +++ /dev/null @@ -1,170 +0,0 @@ -/* Copyright 2013 IST Austria -Contributed by: Jan Reininghaus - -This file is part of PHAT. - -PHAT is free software: you can redistribute it and/or modify -it under the terms of the GNU Lesser General Public License as published by -the Free Software Foundation, either version 3 of the License, or -(at your option) any later version. - -PHAT is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU Lesser General Public License for more details. - -You should have received a copy of the GNU Lesser General Public License -along with PHAT. If not, see . */ - -#pragma once - -#include - -namespace phat { - class vector_heap { - - protected: - std::vector< dimension > dims; - std::vector< column > matrix; - - std::vector< index > inserts_since_last_prune; - - mutable thread_local_storage< column > temp_column_buffer; - - protected: - void _prune( index idx ) - { - column& col = matrix[ idx ]; - column& temp_col = temp_column_buffer(); - temp_col.clear(); - index max_index = _pop_max_index( col ); - while( max_index != -1 ) { - temp_col.push_back( max_index ); - max_index = _pop_max_index( col ); - } - col = temp_col; - std::reverse( col.begin( ), col.end( ) ); - std::make_heap( col.begin( ), col.end( ) ); - inserts_since_last_prune[ idx ] = 0; - } - - index _pop_max_index( index idx ) - { - return _pop_max_index( matrix[ idx ] ); - } - - index _pop_max_index( column& col ) const - { - if( col.empty( ) ) - return -1; - else { - index max_element = col.front( ); - std::pop_heap( col.begin( ), col.end( ) ); - col.pop_back( ); - while( !col.empty( ) && col.front( ) == max_element ) { - std::pop_heap( col.begin( ), col.end( ) ); - col.pop_back( ); - if( col.empty( ) ) - return -1; - else { - max_element = col.front( ); - std::pop_heap( col.begin( ), col.end( ) ); - col.pop_back( ); - } - } - return max_element; - } - } - - public: - // overall number of cells in boundary_matrix - index _get_num_cols( ) const - { - return (index)matrix.size( ); - } - void _set_num_cols( index nr_of_columns ) - { - dims.resize( nr_of_columns ); - matrix.resize( nr_of_columns ); - inserts_since_last_prune.assign( nr_of_columns, 0 ); - } - - // dimension of given index - dimension _get_dim( index idx ) const - { - return dims[ idx ]; - } - void _set_dim( index idx, dimension dim ) - { - dims[ idx ] = dim; - } - - // replaces(!) content of 'col' with boundary of given index - void _get_col( index idx, column& col ) const - { - temp_column_buffer( ) = matrix[ idx ]; - - index max_index = _pop_max_index( temp_column_buffer() ); - while( max_index != -1 ) { - col.push_back( max_index ); - max_index = _pop_max_index( temp_column_buffer( ) ); - } - std::reverse( col.begin( ), col.end( ) ); - } - void _set_col( index idx, const column& col ) - { - matrix[ idx ] = col; - std::make_heap( matrix[ idx ].begin( ), matrix[ idx ].end( ) ); - } - - // true iff boundary of given idx is empty - bool _is_empty( index idx ) const - { - return _get_max_index( idx ) == -1; - } - - // largest row index of given column idx (new name for lowestOne()) - index _get_max_index( index idx ) const - { - column& col = const_cast< column& >( matrix[ idx ] ); - index max_element = _pop_max_index( col ); - col.push_back( max_element ); - std::push_heap( col.begin( ), col.end( ) ); - return max_element; - } - - // removes the maximal index of a column - void _remove_max( index idx ) - { - _pop_max_index( idx ); - } - - // clears given column - void _clear( index idx ) - { - matrix[ idx ].clear( ); - } - - // syncronizes all data structures (essential for openmp stuff) - void _sync( ) {} - - // adds column 'source' to column 'target' - void _add_to( index source, index target ) - { - for( index idx = 0; idx < (index)matrix[ source ].size( ); idx++ ) { - matrix[ target ].push_back( matrix[ source ][ idx ] ); - std::push_heap( matrix[ target ].begin(), matrix[ target ].end() ); - } - inserts_since_last_prune[ target ] += matrix[ source ].size(); - - if( 2 * inserts_since_last_prune[ target ] > ( index )matrix[ target ].size() ) - _prune( target ); - } - - // finalizes given column - void _finalize( index idx ) { - _prune( idx ); - } - - }; -} diff --git a/include/phat/representations/vector_list.h b/include/phat/representations/vector_list.h deleted file mode 100644 index ca0b5b8..0000000 --- a/include/phat/representations/vector_list.h +++ /dev/null @@ -1,101 +0,0 @@ -/* Copyright 2013 IST Austria - Contributed by: Jan Reininghaus - - This file is part of PHAT. - - PHAT is free software: you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - PHAT is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License - along with PHAT. If not, see . */ - -#pragma once - -#include - -namespace phat { - class vector_list { - - protected: - std::vector< dimension > dims; - std::vector< std::list< index > > matrix; - - public: - // overall number of cells in boundary_matrix - index _get_num_cols() const { - return (index)matrix.size(); - } - void _set_num_cols( index nr_of_columns ) { - dims.resize( nr_of_columns ); - matrix.resize( nr_of_columns ); - } - - // dimension of given index - dimension _get_dim( index idx ) const { - return dims[ idx ]; - } - void _set_dim( index idx, dimension dim ) { - dims[ idx ] = dim; - } - - // replaces(!) content of 'col' with boundary of given index - void _get_col( index idx, column& col ) const { - col.clear(); - col.reserve( matrix[idx].size() ); - std::copy (matrix[idx].begin(), matrix[idx].end(), std::back_inserter(col) ); - } - - void _set_col( index idx, const column& col ) { - matrix[ idx ].clear(); - matrix[ idx ].resize( col.size() ); - std::copy (col.begin(), col.end(), matrix[ idx ].begin() ); - } - - // true iff boundary of given idx is empty - bool _is_empty( index idx ) const { - return matrix[ idx ].empty(); - } - - // largest row index of given column idx (new name for lowestOne()) - index _get_max_index( index idx ) const { - return matrix[ idx ].empty() ? -1 : *matrix[ idx ].rbegin(); - } - - // removes the maximal index of a column - void _remove_max( index idx ) { - std::list< index >::iterator it = matrix[ idx ].end(); - it--; - matrix[ idx ].erase( it ); - } - - // clears given column - void _clear( index idx ) { - matrix[ idx ].clear(); - } - - // syncronizes all data structures (essential for openmp stuff) - void _sync() {} - - // adds column 'source' to column 'target' - void _add_to( index source, index target ) { - std::list< index >& source_col = matrix[ source ]; - std::list< index >& target_col = matrix[ target ]; - std::list< index > temp_col; - target_col.swap( temp_col ); - std::set_symmetric_difference( temp_col.begin(), temp_col.end(), - source_col.begin(), source_col.end(), - std::back_inserter( target_col ) ); - } - - // finalizes given column - void _finalize( index idx ) { - } - }; -} diff --git a/include/phat/representations/vector_set.h b/include/phat/representations/vector_set.h deleted file mode 100644 index 6878a27..0000000 --- a/include/phat/representations/vector_set.h +++ /dev/null @@ -1,99 +0,0 @@ -/* Copyright 2013 IST Austria - Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus - - This file is part of PHAT. - - PHAT is free software: you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - PHAT is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License - along with PHAT. If not, see . */ - -#pragma once - -#include - -namespace phat { - class vector_set { - - protected: - std::vector< dimension > dims; - std::vector< std::set< index > > matrix; - - public: - // overall number of cells in boundary_matrix - index _get_num_cols() const { - return (index)matrix.size(); - } - void _set_num_cols( index nr_of_columns ) { - dims.resize( nr_of_columns ); - matrix.resize( nr_of_columns ); - } - - // dimension of given index - dimension _get_dim( index idx ) const { - return dims[ idx ]; - } - void _set_dim( index idx, dimension dim ) { - dims[ idx ] = dim; - } - - // replaces(!) content of 'col' with boundary of given index - void _get_col( index idx, column& col ) const { - col.clear(); - col.reserve( matrix[idx].size() ); - std::copy (matrix[idx].begin(), matrix[idx].end(), std::back_inserter(col) ); - } - void _set_col( index idx, const column& col ) { - matrix[ idx ].clear(); - matrix[ idx ].insert( col.begin(), col.end() ); - } - - // true iff boundary of given idx is empty - bool _is_empty( index idx ) const { - return matrix[ idx ].empty(); - } - - // largest row index of given column idx (new name for lowestOne()) - index _get_max_index( index idx ) const { - return matrix[ idx ].empty() ? -1 : *matrix[ idx ].rbegin(); - } - - // removes the maximal index of a column - void _remove_max( index idx ) { - std::set< index >::iterator it = matrix[ idx ].end(); - it--; - matrix[ idx ].erase( it ); - } - - // clears given column - void _clear( index idx ) { - matrix[ idx ].clear(); - } - - // syncronizes all data structures (essential for openmp stuff) - void _sync() {} - - // adds column 'source' to column 'target' - void _add_to( index source, index target ) { - for( std::set< index >::iterator it = matrix[ source ].begin(); it != matrix[ source ].end(); it++ ) { - std::set< index >& col = matrix[ target ]; - std::pair< std::set< index >::iterator, bool > result = col.insert( *it ); - if( !result.second ) - col.erase( result.first ); - } - } - - // finalizes given column - void _finalize( index idx ) { - } - - }; -} diff --git a/include/phat/representations/vector_vector.h b/include/phat/representations/vector_vector.h deleted file mode 100644 index f111d6b..0000000 --- a/include/phat/representations/vector_vector.h +++ /dev/null @@ -1,107 +0,0 @@ -/* Copyright 2013 IST Austria - Contributed by: Ulrich Bauer, Michael Kerber, Jan Reininghaus - - This file is part of PHAT. - - PHAT is free software: you can redistribute it and/or modify - it under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - PHAT is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License - along with PHAT. If not, see . */ - -#pragma once - -#include - -namespace phat { - class vector_vector { - - protected: - std::vector< dimension > dims; - std::vector< column > matrix; - - thread_local_storage< column > temp_column_buffer; - - public: - // overall number of cells in boundary_matrix - index _get_num_cols() const { - return (index)matrix.size(); - } - void _set_num_cols( index nr_of_columns ) { - dims.resize( nr_of_columns ); - matrix.resize( nr_of_columns ); - } - - // dimension of given index - dimension _get_dim( index idx ) const { - return dims[ idx ]; - } - void _set_dim( index idx, dimension dim ) { - dims[ idx ] = dim; - } - - // replaces(!) content of 'col' with boundary of given index - void _get_col( index idx, column& col ) const { - col = matrix[ idx ]; - } - void _set_col( index idx, const column& col ) { - matrix[ idx ] = col; - } - - // true iff boundary of given idx is empty - bool _is_empty( index idx ) const { - return matrix[ idx ].empty(); - } - - // largest row index of given column idx (new name for lowestOne()) - index _get_max_index( index idx ) const { - return matrix[ idx ].empty() ? -1 : matrix[ idx ].back(); - } - - // removes the maximal index of a column - void _remove_max( index idx ) { - matrix[ idx ].pop_back(); - } - - // clears given column - void _clear( index idx ) { - matrix[ idx ].clear(); - } - - // syncronizes all data structures (essential for openmp stuff) - void _sync() {} - - // adds column 'source' to column 'target' - void _add_to( index source, index target ) { - column& source_col = matrix[ source ]; - column& target_col = matrix[ target ]; - column& temp_col = temp_column_buffer(); - - - size_t new_size = source_col.size() + target_col.size(); - - if (new_size > temp_col.size()) temp_col.resize(new_size); - - std::vector::iterator col_end = std::set_symmetric_difference( target_col.begin(), target_col.end(), - source_col.begin(), source_col.end(), - temp_col.begin() ); - temp_col.erase(col_end, temp_col.end()); - - - target_col.swap(temp_col); - } - - // finalizes given column - void _finalize( index idx ) { - column& col = matrix[ idx ]; - column(col.begin(), col.end()).swap(col); - } - }; -} diff --git a/src/benchmark.cpp b/src/benchmark.cpp index b552d33..7631d57 100644 --- a/src/benchmark.cpp +++ b/src/benchmark.cpp @@ -17,15 +17,7 @@ along with PHAT. If not, see . */ #include - -#include -#include -#include -#include -#include -#include -#include -#include +#include #include #include diff --git a/src/convert.cpp b/src/convert.cpp index 5b4d7a0..d13757f 100644 --- a/src/convert.cpp +++ b/src/convert.cpp @@ -17,7 +17,7 @@ along with PHAT. If not, see . */ -#include +#include #include #include diff --git a/src/phat.cpp b/src/phat.cpp index 3770cf3..46f780c 100644 --- a/src/phat.cpp +++ b/src/phat.cpp @@ -17,15 +17,8 @@ along with PHAT. If not, see . */ #include - -#include -#include -#include -#include -#include -#include -#include -#include +#include +#include #include #include diff --git a/src/self_test.cpp b/src/self_test.cpp index 249b9b2..aef4043 100644 --- a/src/self_test.cpp +++ b/src/self_test.cpp @@ -18,14 +18,7 @@ #include -#include -#include -#include -#include -#include -#include -#include -#include +#include #include #include @@ -52,63 +45,67 @@ int main( int argc, char** argv ) std::cerr << "Error: test data " << test_data << " not found!" << std::endl; return EXIT_FAILURE; } - bool error = false; std::cout << "Comparing representations using Chunk algorithm ..." << std::endl; + + { - std::cout << "Running Chunk - Sparse ..." << std::endl; + std::cout << "Running Chunk - Vec_vec ..." << std::endl; + phat::persistence_pairs vec_vec_pairs; + phat::boundary_matrix< Vec_vec > vec_vec_boundary_matrix(boundary_matrix); + phat::compute_persistence_pairs< phat::chunk_reduction >( vec_vec_pairs, vec_vec_boundary_matrix ); + + std::cout << "Running Chunk - Vec_heap ..." << std::endl; + phat::persistence_pairs vec_heap_pairs; + phat::boundary_matrix< Vec_heap > vec_heap_boundary_matrix(boundary_matrix); + phat::compute_persistence_pairs< phat::chunk_reduction >( vec_heap_pairs, vec_heap_boundary_matrix ); + + std::cout << "Running Chunk - Vec_set ..." << std::endl; + phat::persistence_pairs vec_set_pairs; + phat::boundary_matrix< Vec_set > vec_set_boundary_matrix(boundary_matrix); + phat::compute_persistence_pairs< phat::chunk_reduction >( vec_set_pairs, vec_set_boundary_matrix ); + + std::cout << "Running Chunk - Vec_list ..." << std::endl; + phat::persistence_pairs vec_list_pairs; + phat::boundary_matrix< Vec_list > vec_list_boundary_matrix(boundary_matrix); + phat::compute_persistence_pairs< phat::chunk_reduction >( vec_list_pairs, vec_list_boundary_matrix ); + + + + std::cout << "Running Chunk - Sparse ..." << std::endl; phat::persistence_pairs sparse_pairs; - phat::boundary_matrix< Sparse > sparse_boundary_matrix = boundary_matrix; + phat::boundary_matrix< Sparse > sparse_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::chunk_reduction >( sparse_pairs, sparse_boundary_matrix ); std::cout << "Running Chunk - Heap ..." << std::endl; phat::persistence_pairs heap_pairs; - phat::boundary_matrix< Heap > heap_boundary_matrix = boundary_matrix; + phat::boundary_matrix< Heap > heap_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::chunk_reduction >( heap_pairs, heap_boundary_matrix ); - std::cout << "Running Chunk - Full ..." << std::endl; + std::cout << "Running Chunk - Full ..." << std::endl; phat::persistence_pairs full_pairs; phat::boundary_matrix< Full > full_boundary_matrix = boundary_matrix; phat::compute_persistence_pairs< phat::chunk_reduction >( full_pairs, full_boundary_matrix ); - + std::cout << "Running Chunk - BitTree ..." << std::endl; phat::persistence_pairs bit_tree_pairs; - phat::boundary_matrix< BitTree > bit_tree_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > bit_tree_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::chunk_reduction >( bit_tree_pairs, bit_tree_boundary_matrix ); - std::cout << "Running Chunk - Vec_vec ..." << std::endl; - phat::persistence_pairs vec_vec_pairs; - phat::boundary_matrix< Vec_vec > vec_vec_boundary_matrix = boundary_matrix; - phat::compute_persistence_pairs< phat::chunk_reduction >( vec_vec_pairs, vec_vec_boundary_matrix ); - - std::cout << "Running Chunk - Vec_heap ..." << std::endl; - phat::persistence_pairs vec_heap_pairs; - phat::boundary_matrix< Vec_heap > vec_heap_boundary_matrix = boundary_matrix; - phat::compute_persistence_pairs< phat::chunk_reduction >( vec_heap_pairs, vec_heap_boundary_matrix ); - - std::cout << "Running Chunk - Vec_set ..." << std::endl; - phat::persistence_pairs vec_set_pairs; - phat::boundary_matrix< Vec_set > vec_set_boundary_matrix = boundary_matrix; - phat::compute_persistence_pairs< phat::chunk_reduction >( vec_set_pairs, vec_set_boundary_matrix ); - - std::cout << "Running Chunk - Vec_list ..." << std::endl; - phat::persistence_pairs vec_list_pairs; - phat::boundary_matrix< Vec_list > vec_list_boundary_matrix = boundary_matrix; - phat::compute_persistence_pairs< phat::chunk_reduction >( vec_list_pairs, vec_list_boundary_matrix ); if( sparse_pairs != heap_pairs ) { std::cerr << "Error: sparse and heap differ!" << std::endl; error = true; } - if( heap_pairs != full_pairs ) { + if( heap_pairs != full_pairs ) { std::cerr << "Error: heap and full differ!" << std::endl; error = true; } - if( full_pairs != vec_vec_pairs ) { + if( full_pairs != vec_vec_pairs ) { std::cerr << "Error: full and vec_vec differ!" << std::endl; error = true; } - if( vec_vec_pairs != vec_heap_pairs ) { + if( vec_vec_pairs != vec_heap_pairs ) { std::cerr << "Error: vec_vec and vec_heap differ!" << std::endl; error = true; } @@ -137,27 +134,27 @@ int main( int argc, char** argv ) { std::cout << "Running Twist - BitTree ..." << std::endl; phat::persistence_pairs twist_pairs; - phat::boundary_matrix< BitTree > twist_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > twist_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::twist_reduction >( twist_pairs, twist_boundary_matrix ); std::cout << "Running Standard - BitTree ..." << std::endl; phat::persistence_pairs std_pairs; - phat::boundary_matrix< BitTree > std_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > std_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::standard_reduction >( std_pairs, std_boundary_matrix ); std::cout << "Running Chunk - BitTree ..." << std::endl; phat::persistence_pairs chunk_pairs; - phat::boundary_matrix< BitTree > chunk_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > chunk_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::chunk_reduction >( chunk_pairs, chunk_boundary_matrix ); std::cout << "Running Row - BitTree ..." << std::endl; phat::persistence_pairs row_pairs; - phat::boundary_matrix< BitTree > row_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > row_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::row_reduction >( row_pairs, row_boundary_matrix ); std::cout << "Running Spectral sequence - BitTree ..." << std::endl; phat::persistence_pairs ss_pairs; - phat::boundary_matrix< BitTree > ss_boundary_matrix = boundary_matrix; + phat::boundary_matrix< BitTree > ss_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::spectral_sequence_reduction >( ss_pairs, ss_boundary_matrix ); if( twist_pairs != std_pairs ) { @@ -188,11 +185,11 @@ int main( int argc, char** argv ) std::cout << "Comparing primal and dual approach using Chunk - Full ..." << std::endl; { phat::persistence_pairs primal_pairs; - phat::boundary_matrix< Full > primal_boundary_matrix = boundary_matrix; + phat::boundary_matrix< Full > primal_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs< phat::chunk_reduction >( primal_pairs, primal_boundary_matrix ); phat::persistence_pairs dual_pairs; - phat::boundary_matrix< Full > dual_boundary_matrix = boundary_matrix; + phat::boundary_matrix< Full > dual_boundary_matrix(boundary_matrix); phat::compute_persistence_pairs_dualized< phat::chunk_reduction >( dual_pairs, dual_boundary_matrix ); if( primal_pairs != dual_pairs ) { @@ -208,11 +205,10 @@ int main( int argc, char** argv ) { std::vector< std::vector< int > > vector_vector_matrix; std::vector< int > vector_dims; - boundary_matrix.save_vector_vector( vector_vector_matrix, vector_dims ); - phat::boundary_matrix< BitTree > vector_vector_boundary_matrix; + boundary_matrix.save_vector_vector( vector_vector_matrix, vector_dims ); + phat::boundary_matrix< BitTree > vector_vector_boundary_matrix; vector_vector_boundary_matrix.load_vector_vector( vector_vector_matrix, vector_dims ); - - if( vector_vector_boundary_matrix != boundary_matrix ) { + if( vector_vector_boundary_matrix != boundary_matrix ) { std::cerr << "Error: [load|save]_vector_vector bug" << std::endl; error = true; } diff --git a/src/simple_example.cpp b/src/simple_example.cpp index ba8aafe..e733630 100644 --- a/src/simple_example.cpp +++ b/src/simple_example.cpp @@ -22,7 +22,7 @@ #include // main data structure (choice affects performance) -#include +#include // algorithm (choice affects performance) #include -- cgit v1.2.3