From 5485d57c5632c54c5c377a17672b88357c6455db Mon Sep 17 00:00:00 2001 From: Bryn Keller Date: Mon, 30 Jan 2017 18:12:18 -0800 Subject: Use default representation for example rather than vector_vector --- python/README.rst | 6 ++++-- python/src/simple_example.py | 6 ++++-- setup.py | 3 ++- 3 files changed, 10 insertions(+), 5 deletions(-) diff --git a/python/README.rst b/python/README.rst index 0c6c391..52bc150 100644 --- a/python/README.rst +++ b/python/README.rst @@ -99,8 +99,10 @@ Now the code:: import phat - # define a boundary matrix with the chosen internal representation - boundary_matrix = phat.boundary_matrix(representation = phat.representations.vector_vector) + boundary_matrix = phat.boundary_matrix() + + # or define a boundary matrix with the chosen internal representation + # boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) # set the respective columns -- (dimension, boundary) pairs boundary_matrix.columns = [ (0, []), diff --git a/python/src/simple_example.py b/python/src/simple_example.py index 955e213..7aa6214 100644 --- a/python/src/simple_example.py +++ b/python/src/simple_example.py @@ -21,8 +21,10 @@ if __name__ == "__main__": import phat - # define a boundary matrix with the chosen internal representation - boundary_matrix = phat.boundary_matrix(representation = phat.representations.vector_vector) + boundary_matrix = phat.boundary_matrix() + + # or define a boundary matrix with the chosen internal representation + # boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) # set the respective columns -- (dimension, boundary) pairs boundary_matrix.columns = [ (0, []), diff --git a/setup.py b/setup.py index 1ce0e51..46dadbb 100644 --- a/setup.py +++ b/setup.py @@ -51,7 +51,7 @@ if sys.version_info < (3,4,0): setup( name='phat', - version='1.5.0', + version='1.5.0.post2', author='Bryn Keller', author_email='bryn.keller@intel.com', url='https://bitbucket.org/phat-code/phat', @@ -60,6 +60,7 @@ setup( keywords='algebraic-topology PHAT distributed topology persistent-homology', long_description=long_description, ext_modules=ext_modules, + requires=requires, install_requires=requires, cmdclass={'build_ext': BuildExt}, package_dir={'':'python'}, -- cgit v1.2.3 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 From 90ed83dcb6f3b9296be358f1b5b8a79b761bdc09 Mon Sep 17 00:00:00 2001 From: Bryn Keller Date: Mon, 16 Jul 2018 17:11:01 -0700 Subject: Support constructing columns when the boundary is not sorted, plus some whitespace cleanup --- python/phat.py | 52 +++++++++++++++++++++++++++------------------------- 1 file changed, 27 insertions(+), 25 deletions(-) diff --git a/python/phat.py b/python/phat.py index 70f5b39..c5ad686 100644 --- a/python/phat.py +++ b/python/phat.py @@ -70,7 +70,7 @@ import enum from _phat import persistence_pairs -#The public API for the module +# The public API for the module __all__ = ['boundary_matrix', 'persistence_pairs', @@ -102,6 +102,7 @@ class reductions(enum.Enum): class column(object): """A view on one column of data in a boundary matrix""" + def __init__(self, matrix, index): """INTERNAL. Columns are created automatically by boundary matrices. There is no need to construct them directly""" @@ -120,7 +121,7 @@ class column(object): @dimension.setter def dimension(self, value): - return self._matrix._matrix.set_dim(self._index, value) + self._matrix._matrix.set_dim(self._index, value) @property def boundary(self): @@ -129,16 +130,17 @@ class column(object): @boundary.setter def boundary(self, values): - return self._matrix._matrix.set_col(self._index, values) + self._matrix._matrix.set_col(self._index, values) def __str__(self): return "(%d, %s)" % (self.dimension, self.boundary) + class boundary_matrix(object): """Boundary matrices that store the shape information of a cell complex. """ - def __init__(self, representation = representations.bit_tree_pivot_column, source = None, columns = None): + def __init__(self, representation=representations.bit_tree_pivot_column, source=None, columns=None): """ The boundary matrix will use the specified implementation for storing its column data. If the `source` parameter is specified, it will be assumed to @@ -178,8 +180,8 @@ class boundary_matrix(object): @columns.setter def columns(self, columns): for col in columns: - if not (isinstance(col, column) or isinstance(col, tuple)): - raise TypeError("All columns must be column objects, or (dimension, values) tuples") + if not (isinstance(col, column) or isinstance(col, tuple)): + raise TypeError("All columns must be column objects, or (dimension, values) tuples") if len(columns) != len(self.dimensions): self._matrix.set_dims([0] * len(columns)) for i, col in enumerate(columns): @@ -189,7 +191,7 @@ class boundary_matrix(object): else: dimension, values = col self._matrix.set_dim(i, dimension) - self._matrix.set_col(i, values) + self._matrix.set_col(i, sorted(values)) @property def dimensions(self): @@ -198,7 +200,7 @@ class boundary_matrix(object): @dimensions.setter def dimensions(self, dimensions): - return self._matrix.set_dims(dimensions) + self._matrix.set_dims(dimensions) def __matrix_for_representation(self, representation): short_name = _short_name(representation.name) @@ -207,27 +209,27 @@ class boundary_matrix(object): def __eq__(self, other): return self._matrix == other._matrix - #Note Python 2.7 needs BOTH __eq__ and __ne__ otherwise you get things that - #are both equal and not equal + # Note Python 2.7 needs BOTH __eq__ and __ne__ otherwise you get things that + # are both equal and not equal def __ne__(self, other): return self._matrix != other._matrix def __len__(self): return self._matrix.get_num_entries() - #Pickle support + # Pickle support def __getstate__(self): (dimensions, columns) = self._matrix.get_vector_vector() return (self._representation, dimensions, columns) - #Pickle support + # Pickle support def __setstate__(self, state): presentation, dimensions, columns = state self._representation = representation self._matrix = self.__matrix_for_representation(representation) self._matrix.set_vector_vector(dimensions, columns) - def load(self, file_name, mode = 'b'): + def load(self, file_name, mode='b'): """Load this boundary matrix from a file Parameters @@ -252,7 +254,7 @@ class boundary_matrix(object): else: raise ValueError("Only 'b' - binary and 't' - text modes are supported") - def save(self, file_name, mode = 'b'): + def save(self, file_name, mode='b'): """Save this boundary matrix to a file Parameters @@ -278,37 +280,40 @@ class boundary_matrix(object): raise ValueError("Only 'b' - binary and 't' - text modes are supported") def compute_persistence_pairs(self, - reduction = reductions.twist_reduction): + reduction=reductions.twist_reduction): """Computes persistence pairs (birth, death) for the given boundary matrix.""" representation_short_name = _short_name(self._representation.name) algo_name = reduction.name algo_short_name = _short_name(algo_name) - #Look up an implementation that matches the requested characteristics - #in the _phat module + # Look up an implementation that matches the requested characteristics + # in the _phat module function = getattr(_phat, "compute_persistence_pairs_" + representation_short_name + "_" + algo_short_name) return function(self._matrix) - def compute_persistence_pairs_dualized(self, - reduction = reductions.twist_reduction): + def compute_persistence_pairs_dualized(self, + reduction=reductions.twist_reduction): """Computes persistence pairs (birth, death) from the dualized form of the given boundary matrix.""" representation_short_name = _short_name(self._representation.name) algo_name = reduction.name algo_short_name = _short_name(algo_name) - #Look up an implementation that matches the requested characteristics - #in the _phat module - function = getattr(_phat, "compute_persistence_pairs_dualized_" + representation_short_name + "_" + algo_short_name) + # Look up an implementation that matches the requested characteristics + # in the _phat module + function = getattr(_phat, + "compute_persistence_pairs_dualized_" + representation_short_name + "_" + algo_short_name) return function(self._matrix) def convert(self, representation): """Copy this matrix to another with a different representation""" return boundary_matrix(representation, self) + def _short_name(name): """An internal API that takes leading characters from words For instance, 'bit_tree_pivot_column' becomes 'btpc' """ return "".join([n[0] for n in name.split("_")]) + def _convert(source, to_representation): """Internal - function to convert from one `boundary_matrix` implementation to another""" class_name = source._representation.name @@ -316,6 +321,3 @@ def _convert(source, to_representation): to_rep_short_name = _short_name(to_representation.name) function = getattr(_phat, "convert_%s_to_%s" % (source_rep_short_name, to_rep_short_name)) return function(source._matrix) - - - -- cgit v1.2.3 From 1e2cce06b3de2503cb2336af892fa5024154f920 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 13:20:16 +0200 Subject: Missing file --- include/phat/representations/heap_column_rep.h | 162 +++++++++++++++++++++++++ 1 file changed, 162 insertions(+) create mode 100644 include/phat/representations/heap_column_rep.h diff --git a/include/phat/representations/heap_column_rep.h b/include/phat/representations/heap_column_rep.h new file mode 100644 index 0000000..42dda3f --- /dev/null +++ b/include/phat/representations/heap_column_rep.h @@ -0,0 +1,162 @@ +/* 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 heap_column_rep { + + protected: + std::vector< index > indices; + + index inserts_since_last_prune; + + mutable thread_local_storage< column >* temp_column_buffer; + + protected: + void _prune() + { + column& col = indices; + 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 = 0; + } + + 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: + + typedef heap_column_rep Self; + + std::vector::const_iterator begin() const { + return indices.begin(); + } + + std::vector::const_iterator end() const { + return indices.end(); + } + + void offer_thread_local_storage(thread_local_storage< column >* tls) { + temp_column_buffer=tls; + } + + // replaces(!) content of 'col' with boundary of given index + void _get_col( column& col ) const + { + col.clear(); + (*temp_column_buffer)() = indices; + 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(const column& col ) + { + indices = col; + std::make_heap( indices.begin( ), indices.end( ) ); + } + + // true iff boundary of given idx is empty + bool _is_empty() const + { + return _get_max_index() == -1; + } + + // largest row index of given column idx (new name for lowestOne()) + index _get_max_index() const + { + column& col = const_cast< column& >( indices ); + 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() + { + _pop_max_index( indices ); + } + + // clears given column + void _clear() + { + indices.clear( ); + } + + index _size() { + _prune(); + return indices.size(); + } + + // syncronizes all data structures (essential for openmp stuff) + void _sync( ) {} + + // adds column 'source' to column 'target' + void _add_to( const Self& source ) + { + for( index idx = 0; idx < (index)source.indices.size( ); idx++ ) { + this->indices.push_back( source.indices[ idx ] ); + std::push_heap( this->indices.begin(), this->indices.end() ); + } + inserts_since_last_prune += source.indices.size(); + + if( 2 * inserts_since_last_prune > ( index )this->indices.size() ) + _prune(); + } + + // finalizes given column + void _finalize() { + _prune(); + } + + }; +} -- cgit v1.2.3 From 4cb490d7fabf2e3920d1e7efb4e10c5f5f1ae102 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 13:58:23 +0200 Subject: Fixed python wrapper with respect to update --- python/_phat.cpp | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) diff --git a/python/_phat.cpp b/python/_phat.cpp index df7449d..f0a1516 100644 --- a/python/_phat.cpp +++ b/python/_phat.cpp @@ -12,15 +12,7 @@ #include "phat/persistence_pairs.h" #include "phat/compute_persistence_pairs.h" #include "phat/boundary_matrix.h" -#include "phat/representations/abstract_pivot_column.h" -#include -#include -#include -#include -#include -#include -#include -#include +#include "phat/representations/default_representations.h" #include #include #include -- cgit v1.2.3 From 843e6870e58decba7d22411e4ba0f6dfc2df78a7 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 13:59:04 +0200 Subject: Removed indentation in example to easier copy-and-paster on command line --- python/README.rst | 57 ++++++++++++++++++++++++++++--------------------------- 1 file changed, 29 insertions(+), 28 deletions(-) diff --git a/python/README.rst b/python/README.rst index 52bc150..d59ef00 100644 --- a/python/README.rst +++ b/python/README.rst @@ -97,41 +97,42 @@ We will build an ordered boundary matrix of this simplicial complex consisting o Now the code:: - import phat +import phat - boundary_matrix = phat.boundary_matrix() +boundary_matrix = phat.boundary_matrix() - # or define a boundary matrix with the chosen internal representation - # boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) +# or define a boundary matrix with the chosen internal representation +# boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) - # set the respective columns -- (dimension, boundary) pairs - boundary_matrix.columns = [ (0, []), - (0, []), - (1, [0,1]), - (0, []), - (1, [1,3]), - (1, [0,3]), - (2, [2,4,5])] +# set the respective columns -- (dimension, boundary) pairs +boundary_matrix.columns = [ (0, []), + (0, []), + (1, [0,1]), + (0, []), + (1, [1,3]), + (1, [0,3]), + (2, [2,4,5])] - # or equivalently, boundary_matrix = phat.boundary_matrix(representation = ..., columns = ...) - # would combine the creation of the matrix and the assignment of the columns +# or equivalently, boundary_matrix = phat.boundary_matrix(representation = ..., columns = ...) +# would combine the creation of the matrix and the assignment of the columns - # print some information of the boundary matrix: - print("\nThe boundary matrix has %d columns:" % len(boundary_matrix.columns)) - for col in boundary_matrix.columns: - s = "Column %d represents a cell of dimension %d." % (col.index, col.dimension) - if (col.boundary): - s = s + " Its boundary consists of the cells " + " ".join([str(c) for c in col.boundary]) - print(s) - print("Overall, the boundary matrix has %d entries." % len(boundary_matrix)) +# print some information of the boundary matrix: +print("\nThe boundary matrix has %d columns:" % len(boundary_matrix.columns)) +for col in boundary_matrix.columns: + s = "Column %d represents a cell of dimension %d." % (col.index, col.dimension) + if (col.boundary): + s = s + " Its boundary consists of the cells " + " ".join([str(c) for c in col.boundary]) + print(s) - pairs = boundary_matrix.compute_persistence_pairs() +print("Overall, the boundary matrix has %d entries." % len(boundary_matrix)) - pairs.sort() +pairs = boundary_matrix.compute_persistence_pairs() - print("\nThere are %d persistence pairs: " % len(pairs)) - for pair in pairs: - print("Birth: %d, Death: %d" % pair) +pairs.sort() + +print("\nThere are %d persistence pairs: " % len(pairs)) +for pair in pairs: + print("Birth: %d, Death: %d" % pair) References: @@ -140,5 +141,5 @@ References: .. [3] C.Chen, M.Kerber: Persistent Homology Computation With a Twist. 27th European Workshop on Computational Geometry, 2011. .. [4] U.Bauer, M.Kerber, J.Reininghaus: Clear and Compress: Computing Persistent Homology in Chunks. arXiv:1303.0477_ .. _arXiv:1303.0477: http://arxiv.org/pdf/1303.0477.pdf -.. _`Persistent Homology Algorithm Toolkit`: https://bitbucket.org/phat/phat-code +.. _`Persistent Homology Algorithm Toolbox`: https://bitbucket.org/phat/phat-code .. _`python.org`:http://docs.python-guide.org/en/latest/starting/install/osx/ -- cgit v1.2.3 From 0fbd1f5197e69aee959d3eab134c2792f56fface Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 14:16:18 +0200 Subject: New method "set_dimension" to control the number of rows in the matrix, if needed --- include/phat/boundary_matrix.h | 8 +++++++- include/phat/representations/Pivot_representation.h | 6 +++--- include/phat/representations/Uniform_representation.h | 3 ++- include/phat/representations/heap_column_rep.h | 4 ++++ include/phat/representations/list_column_rep.h | 4 ++++ include/phat/representations/set_column_rep.h | 4 ++++ include/phat/representations/vector_column_rep.h | 4 ++++ 7 files changed, 28 insertions(+), 5 deletions(-) diff --git a/include/phat/boundary_matrix.h b/include/phat/boundary_matrix.h index 295cfa5..d1d6257 100644 --- a/include/phat/boundary_matrix.h +++ b/include/phat/boundary_matrix.h @@ -37,8 +37,14 @@ namespace phat { // get overall number of columns in boundary_matrix index get_num_cols() const { return rep._get_num_cols(); } + // sets the number of rows (1st parameter) and columns (2nd parameter) + // of the matrix. Most internal types ignore the number of rows + // but some do no + void set_dimensions( index nr_of_rows, index nr_of_columns ) {rep._set_dimensions( nr_of_rows, nr_of_columns );} + // set overall number of columns in boundary_matrix - void set_num_cols( index nr_of_columns ) { rep._set_num_cols( nr_of_columns ); } + // sets the number of rows to nr_of_columns as well! + void set_num_cols( index nr_of_columns ) { rep._set_dimensions( nr_of_columns, nr_of_columns ); } // get dimension of given index dimension get_dim( index idx ) const { return rep._get_dim( idx ); } diff --git a/include/phat/representations/Pivot_representation.h b/include/phat/representations/Pivot_representation.h index 324c888..77f8746 100644 --- a/include/phat/representations/Pivot_representation.h +++ b/include/phat/representations/Pivot_representation.h @@ -71,13 +71,13 @@ template public: - void _set_num_cols( index nr_of_cols ) { + void _set_dimensions( index nr_of_rows, 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 ); + pivot_cols[ tid ].init( nr_of_rows ); idx_of_pivot_cols[ tid ] = -1; } - Base::_set_num_cols( nr_of_cols ); + Base::_set_dimensions( nr_of_rows, nr_of_cols ); } void _add_to( index source, index target ) { diff --git a/include/phat/representations/Uniform_representation.h b/include/phat/representations/Uniform_representation.h index ccbf6a3..b31e275 100644 --- a/include/phat/representations/Uniform_representation.h +++ b/include/phat/representations/Uniform_representation.h @@ -54,9 +54,10 @@ class Uniform_representation { return col_traits.get_size(matrix); } - void _set_num_cols(index nr_of_columns) { + void _set_dimensions(index nr_of_rows, 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)._set_nr_of_rows(nr_of_rows); col_traits.col_at(matrix,idx).offer_thread_local_storage(&temp_column_buffer); } dim_traits.resize(dims, nr_of_columns); diff --git a/include/phat/representations/heap_column_rep.h b/include/phat/representations/heap_column_rep.h index 42dda3f..cc47bb3 100644 --- a/include/phat/representations/heap_column_rep.h +++ b/include/phat/representations/heap_column_rep.h @@ -104,6 +104,10 @@ namespace phat { std::make_heap( indices.begin( ), indices.end( ) ); } + void _set_nr_of_rows( int nr_of_rows ) { + // ignore + } + // true iff boundary of given idx is empty bool _is_empty() const { diff --git a/include/phat/representations/list_column_rep.h b/include/phat/representations/list_column_rep.h index 5de2652..bd1200e 100644 --- a/include/phat/representations/list_column_rep.h +++ b/include/phat/representations/list_column_rep.h @@ -54,6 +54,10 @@ namespace phat { std::copy (col.begin(), col.end(), indices.begin() ); } + void _set_nr_of_rows( int nr_of_rows ) { + // ignore + } + // true iff boundary of given idx is empty bool _is_empty() const { return indices.empty(); diff --git a/include/phat/representations/set_column_rep.h b/include/phat/representations/set_column_rep.h index c43b74e..1acb9fd 100644 --- a/include/phat/representations/set_column_rep.h +++ b/include/phat/representations/set_column_rep.h @@ -52,6 +52,10 @@ namespace phat { indices.insert( col.begin(), col.end() ); } + void _set_nr_of_rows( int nr_of_rows ) { + // ignore + } + // true iff boundary of given idx is empty bool _is_empty() const { return indices.empty(); diff --git a/include/phat/representations/vector_column_rep.h b/include/phat/representations/vector_column_rep.h index 22c37ef..babb0df 100644 --- a/include/phat/representations/vector_column_rep.h +++ b/include/phat/representations/vector_column_rep.h @@ -54,6 +54,10 @@ namespace phat { indices = col; } + void _set_nr_of_rows( int nr_of_rows ) { + // ignore + } + // true iff boundary of given idx is empty bool _is_empty() const { return indices.empty(); -- cgit v1.2.3 From 49082c33e5dd7d32c9876d2866bf4033f548bcea Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 14:20:44 +0200 Subject: Increased version number --- README.md | 2 +- setup.py | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/README.md b/README.md index 361d21c..a70fc55 100644 --- a/README.md +++ b/README.md @@ -1,4 +1,4 @@ -# PHAT (Persistent Homology Algorithm Toolbox), v1.5 # +# PHAT (Persistent Homology Algorithm Toolbox), v1.6 # Copyright 2013–2017 IST Austria ## Project Founders ## diff --git a/setup.py b/setup.py index 46dadbb..d3dfc6d 100644 --- a/setup.py +++ b/setup.py @@ -51,7 +51,7 @@ if sys.version_info < (3,4,0): setup( name='phat', - version='1.5.0.post2', + version='1.6.0.post2', author='Bryn Keller', author_email='bryn.keller@intel.com', url='https://bitbucket.org/phat-code/phat', -- cgit v1.2.3 From 51d8590114c2e0ed1c3451b56aa12dab4a5e9807 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 14:22:09 +0200 Subject: Cosmetics --- README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/README.md b/README.md index a70fc55..71dafc5 100644 --- a/README.md +++ b/README.md @@ -1,5 +1,5 @@ # PHAT (Persistent Homology Algorithm Toolbox), v1.6 # -Copyright 2013–2017 IST Austria +Copyright 2013–2020 IST Austria ## Project Founders ## -- cgit v1.2.3 From 64cabcd1dca78057d1d257dccf0e961ccf8a7803 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Mon, 24 Aug 2020 14:25:34 +0200 Subject: Added download tag for new version --- README.md | 1 + 1 file changed, 1 insertion(+) diff --git a/README.md b/README.md index 71dafc5..5e1f5a5 100644 --- a/README.md +++ b/README.md @@ -10,6 +10,7 @@ Ulrich Bauer, Michael Kerber, Jan Reininghaus Hubert Wagner, Bryn Keller ## Downloads ## +* [PHAT, v1.6](https://bitbucket.org/phat-code/phat/get/v1.6.zip) * [PHAT, v1.5](https://bitbucket.org/phat-code/phat/get/v1.5.zip) * [PHAT, v1.4.1](https://bitbucket.org/phat-code/phat/get/v1.4.1.zip) * [PHAT, v1.3](https://drive.google.com/uc?id=0B7Yz6TPEpiGEMGFNQ3FPX3ltelk&export=download) -- cgit v1.2.3 From 04f3abb6598e9336df64a1ef408323d875c2cee3 Mon Sep 17 00:00:00 2001 From: mkerber Date: Tue, 25 Aug 2020 13:39:01 +0000 Subject: Idented code again (md-Syntax) --- python/README.rst | 74 +++++++++++++++++++++++++++---------------------------- 1 file changed, 37 insertions(+), 37 deletions(-) diff --git a/python/README.rst b/python/README.rst index d59ef00..03abc60 100644 --- a/python/README.rst +++ b/python/README.rst @@ -70,7 +70,7 @@ Other configurations are untested. Please note that this package DOES NOT work with the Python 2.7.10 that ships with the operating system in Mac OS X. These words of wisdom from `python.org`_ are worth heeding: - The version of Python that ships with OS X is great for learning but it’s not good for development. + The version of Python that ships with OS X is great for learning but it’s not good for development. The version shipped with OS X may be out of date from the official current Python release, which is considered the stable production version. @@ -97,42 +97,42 @@ We will build an ordered boundary matrix of this simplicial complex consisting o Now the code:: -import phat - -boundary_matrix = phat.boundary_matrix() - -# or define a boundary matrix with the chosen internal representation -# boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) - -# set the respective columns -- (dimension, boundary) pairs -boundary_matrix.columns = [ (0, []), - (0, []), - (1, [0,1]), - (0, []), - (1, [1,3]), - (1, [0,3]), - (2, [2,4,5])] - -# or equivalently, boundary_matrix = phat.boundary_matrix(representation = ..., columns = ...) -# would combine the creation of the matrix and the assignment of the columns - -# print some information of the boundary matrix: -print("\nThe boundary matrix has %d columns:" % len(boundary_matrix.columns)) -for col in boundary_matrix.columns: - s = "Column %d represents a cell of dimension %d." % (col.index, col.dimension) - if (col.boundary): - s = s + " Its boundary consists of the cells " + " ".join([str(c) for c in col.boundary]) - print(s) - -print("Overall, the boundary matrix has %d entries." % len(boundary_matrix)) - -pairs = boundary_matrix.compute_persistence_pairs() - -pairs.sort() - -print("\nThere are %d persistence pairs: " % len(pairs)) -for pair in pairs: - print("Birth: %d, Death: %d" % pair) + import phat + + boundary_matrix = phat.boundary_matrix() + + # or define a boundary matrix with the chosen internal representation + # boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) + + # set the respective columns -- (dimension, boundary) pairs + boundary_matrix.columns = [ (0, []), + (0, []), + (1, [0,1]), + (0, []), + (1, [1,3]), + (1, [0,3]), + (2, [2,4,5])] + + # or equivalently, boundary_matrix = phat.boundary_matrix(representation = ..., columns = ...) + # would combine the creation of the matrix and the assignment of the columns + + # print some information of the boundary matrix: + print("\nThe boundary matrix has %d columns:" % len(boundary_matrix.columns)) + for col in boundary_matrix.columns: + s = "Column %d represents a cell of dimension %d." % (col.index, col.dimension) + if (col.boundary): + s = s + " Its boundary consists of the cells " + " ".join([str(c) for c in col.boundary]) + print(s) + + print("Overall, the boundary matrix has %d entries." % len(boundary_matrix)) + + pairs = boundary_matrix.compute_persistence_pairs() + + pairs.sort() + + print("\nThere are %d persistence pairs: " % len(pairs)) + for pair in pairs: + print("Birth: %d, Death: %d" % pair) References: -- cgit v1.2.3 From 746517263955660b5a0a0f4defc18f2d2d84f502 Mon Sep 17 00:00:00 2001 From: Michael Kerber Date: Tue, 25 Aug 2020 15:47:41 +0200 Subject: more formatting issues --- python/README.rst | 19 +++++++++---------- 1 file changed, 9 insertions(+), 10 deletions(-) diff --git a/python/README.rst b/python/README.rst index 03abc60..7de641d 100644 --- a/python/README.rst +++ b/python/README.rst @@ -70,7 +70,7 @@ Other configurations are untested. Please note that this package DOES NOT work with the Python 2.7.10 that ships with the operating system in Mac OS X. These words of wisdom from `python.org`_ are worth heeding: - The version of Python that ships with OS X is great for learning but it’s not good for development. + The version of Python that ships with OS X is great for learning but it is not good for development. The version shipped with OS X may be out of date from the official current Python release, which is considered the stable production version. @@ -98,12 +98,12 @@ We will build an ordered boundary matrix of this simplicial complex consisting o Now the code:: import phat - + boundary_matrix = phat.boundary_matrix() - + # or define a boundary matrix with the chosen internal representation # boundary_matrix = phat.boundary_matrix(representation = phat.representations.bit_tree_pivot_column) - + # set the respective columns -- (dimension, boundary) pairs boundary_matrix.columns = [ (0, []), (0, []), @@ -112,10 +112,10 @@ Now the code:: (1, [1,3]), (1, [0,3]), (2, [2,4,5])] - + # or equivalently, boundary_matrix = phat.boundary_matrix(representation = ..., columns = ...) # would combine the creation of the matrix and the assignment of the columns - + # print some information of the boundary matrix: print("\nThe boundary matrix has %d columns:" % len(boundary_matrix.columns)) for col in boundary_matrix.columns: @@ -123,13 +123,12 @@ Now the code:: if (col.boundary): s = s + " Its boundary consists of the cells " + " ".join([str(c) for c in col.boundary]) print(s) - print("Overall, the boundary matrix has %d entries." % len(boundary_matrix)) - + pairs = boundary_matrix.compute_persistence_pairs() - + pairs.sort() - + print("\nThere are %d persistence pairs: " % len(pairs)) for pair in pairs: print("Birth: %d, Death: %d" % pair) -- cgit v1.2.3