From 6723f7687a27ac4e48a5d46bdac9cd4aa2478830 Mon Sep 17 00:00:00 2001 From: "jan.reininghaus" Date: Tue, 17 Dec 2013 10:17:07 +0000 Subject: new representation type heap_pivot_column git-svn-id: https://phat.googlecode.com/svn/trunk@147 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d --- include/phat/representations/heap_pivot_column.h | 107 +++++++++++++++++++++++ src/benchmark.cpp | 7 +- src/phat.cpp | 7 +- src/self_test.cpp | 15 +++- 4 files changed, 130 insertions(+), 6 deletions(-) create mode 100644 include/phat/representations/heap_pivot_column.h diff --git a/include/phat/representations/heap_pivot_column.h b/include/phat/representations/heap_pivot_column.h new file mode 100644 index 0000000..f2bf845 --- /dev/null +++ b/include/phat/representations/heap_pivot_column.h @@ -0,0 +1,107 @@ +/* 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 { + class heap_column { + + protected: + std::priority_queue< index > data; + + void add_index( const index idx ) { + data.push( idx ); + } + + public: + void init( const index total_size ) { + clear(); + } + + void add_col( const column& col ) { + for( index idx = 0; idx < (index) col.size(); idx++ ) + add_index( col[ idx ] ); + } + + index get_max_index() { + if( data.empty() ) + return -1; + else { + index max_element = data.top(); + data.pop(); + while( !data.empty() && data.top() == max_element ) { + data.pop(); + if( data.empty() ) + return -1; + else { + max_element = data.top(); + data.pop(); + } + } + + data.push( max_element ); + return max_element; + } + } + + void get_col_and_clear( column& col ) { + col.clear(); + while( !data.empty() ) { + index max_element = data.top(); + data.pop(); + if( data.empty() ) + col.push_back( max_element ); + else { + if( data.top() != max_element ) + col.push_back( max_element ); + else + data.pop(); + } + } + std::reverse( col.begin(), col.end() ); + } + + bool is_empty() { + return data.empty(); + } + + void clear() { + while( !data.empty() ) + data.pop(); + } + + void remove_max() { + add_index( get_max_index() ); + } + + void set_col( const column& col ) { + clear(); + add_col( col ); + } + + void get_col( column& col ) { + get_col_and_clear( col ); + add_col( col ); + } + }; + + typedef abstract_pivot_column< heap_column > heap_pivot_column; +} diff --git a/src/benchmark.cpp b/src/benchmark.cpp index ca2497c..6a75bfe 100644 --- a/src/benchmark.cpp +++ b/src/benchmark.cpp @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -37,7 +38,7 @@ #include -enum Representation_type {VECTOR_VECTOR, VECTOR_SET, SPARSE_PIVOT_COLUMN, FULL_PIVOT_COLUMN, BIT_TREE_PIVOT_COLUMN, VECTOR_LIST}; +enum Representation_type {VECTOR_VECTOR, VECTOR_SET, SPARSE_PIVOT_COLUMN, HEAP_PIVOT_COLUMN, FULL_PIVOT_COLUMN, BIT_TREE_PIVOT_COLUMN, VECTOR_LIST}; enum Algorithm_type {STANDARD, TWIST, ROW, CHUNK, CHUNK_SEQUENTIAL, BLOCK_SPECTRAL_SEQUENCE}; enum Ansatz_type {PRIMAL, DUAL}; @@ -51,7 +52,7 @@ void print_help() { std::cerr << "--help -- prints this screen" << std::endl; std::cerr << "--dualize -- use only dualization approach" << std::endl; std::cerr << "--primal -- use only primal approach" << std::endl; - std::cerr << "--vector_vector, --vector_set, --vector_list, --full_pivot_column, --sparse_pivot_column, --bit_tree_pivot_column -- use only a subset of representation data structures for boundary matrices" << std::endl; + std::cerr << "--vector_vector, --vector_set, --vector_list, --full_pivot_column, --sparse_pivot_column, --heap_pivot_column, --bit_tree_pivot_column -- use only a subset of representation data structures for boundary matrices" << std::endl; std::cerr << "--standard, --twist, --chunk, --chunk_sequential, --block_spectral_sequence, --row -- use only a subset of reduction algorithms" << std::endl; } @@ -77,6 +78,7 @@ void parse_command_line( int argc, char** argv, bool& use_binary, std::vector< R else if( argument == "--full_pivot_column" ) representations.push_back( FULL_PIVOT_COLUMN ); else if( argument == "--bit_tree_pivot_column" ) representations.push_back( BIT_TREE_PIVOT_COLUMN ); else if( argument == "--sparse_pivot_column" ) representations.push_back( SPARSE_PIVOT_COLUMN ); + else if( argument == "--heap_pivot_column" ) representations.push_back( HEAP_PIVOT_COLUMN ); else if( argument == "--standard" ) algorithms.push_back( STANDARD ); else if( argument == "--twist" ) algorithms.push_back( TWIST ); else if( argument == "--row" ) algorithms.push_back( ROW ); @@ -191,6 +193,7 @@ int main( int argc, char** argv ) case FULL_PIVOT_COLUMN: COMPUTE(full_pivot_column) break; case BIT_TREE_PIVOT_COLUMN: COMPUTE(bit_tree_pivot_column) break; case SPARSE_PIVOT_COLUMN: COMPUTE(sparse_pivot_column) break; + case HEAP_PIVOT_COLUMN: COMPUTE(heap_pivot_column) break; } } } diff --git a/src/phat.cpp b/src/phat.cpp index 1cc5ebb..7f994db 100644 --- a/src/phat.cpp +++ b/src/phat.cpp @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -33,7 +34,7 @@ #include -enum Representation_type {VECTOR_VECTOR, VECTOR_SET, SPARSE_PIVOT_COLUMN, FULL_PIVOT_COLUMN, BIT_TREE_PIVOT_COLUMN, VECTOR_LIST}; +enum Representation_type {VECTOR_VECTOR, VECTOR_SET, SPARSE_PIVOT_COLUMN, FULL_PIVOT_COLUMN, BIT_TREE_PIVOT_COLUMN, VECTOR_LIST, HEAP_PIVOT_COLUMN}; enum Algorithm_type {STANDARD, TWIST, ROW, CHUNK, CHUNK_SEQUENTIAL, BLOCK_SPECTRAL_SEQUENCE }; void print_help() { @@ -46,7 +47,7 @@ void print_help() { std::cerr << "--help -- prints this screen" << std::endl; std::cerr << "--verbose -- verbose output" << std::endl; std::cerr << "--dualize -- use dualization approach" << std::endl; - std::cerr << "--vector_vector, --vector_set, --vector_list, --full_pivot_column, --sparse_pivot_column, --bit_tree_pivot_column -- selects a representation data structure for boundary matrices (default is '--bit_tree_pivot_column')" << std::endl; + std::cerr << "--vector_vector, --vector_set, --vector_list, --full_pivot_column, --sparse_pivot_column, --heap_pivot_column, --bit_tree_pivot_column -- selects a representation data structure for boundary matrices (default is '--bit_tree_pivot_column')" << std::endl; std::cerr << "--standard, --twist, --chunk, --chunk_sequential, --block_spectral_sequence, --row -- selects a reduction algorithm (default is '--twist')" << std::endl; } @@ -75,6 +76,7 @@ void parse_command_line( int argc, char** argv, bool& use_binary, Representation else if( option == "--full_pivot_column" ) representation = FULL_PIVOT_COLUMN; else if( option == "--bit_tree_pivot_column" ) representation = BIT_TREE_PIVOT_COLUMN; else if( option == "--sparse_pivot_column" ) representation = SPARSE_PIVOT_COLUMN; + else if( option == "--heap_pivot_column" ) representation = HEAP_PIVOT_COLUMN; else if( option == "--standard" ) algorithm = STANDARD; else if( option == "--twist" ) algorithm = TWIST; else if( option == "--row" ) algorithm = ROW; @@ -180,5 +182,6 @@ int main( int argc, char** argv ) case FULL_PIVOT_COLUMN: COMPUTE_PAIRING(full_pivot_column) break; case BIT_TREE_PIVOT_COLUMN: COMPUTE_PAIRING(bit_tree_pivot_column) break; case SPARSE_PIVOT_COLUMN: COMPUTE_PAIRING(sparse_pivot_column) break; + case HEAP_PIVOT_COLUMN: COMPUTE_PAIRING(heap_pivot_column) break; } } diff --git a/src/self_test.cpp b/src/self_test.cpp index cfecd0e..21bb3bc 100644 --- a/src/self_test.cpp +++ b/src/self_test.cpp @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -36,6 +37,7 @@ int main( int argc, char** argv ) std::string test_data = argc > 1 ? argv[ 1 ] : "examples/torus.bin"; typedef phat::sparse_pivot_column Sparse; + typedef phat::heap_pivot_column Heap; typedef phat::full_pivot_column Full; typedef phat::bit_tree_pivot_column BitTree; typedef phat::vector_vector Vec_vec; @@ -57,6 +59,11 @@ int main( int argc, char** argv ) 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::compute_persistence_pairs< phat::chunk_reduction >( heap_pairs, heap_boundary_matrix ); + std::cout << "Running Chunk - Full ..." << std::endl; phat::persistence_pairs full_pairs; phat::boundary_matrix< Full > full_boundary_matrix = boundary_matrix; @@ -82,8 +89,12 @@ int main( int argc, char** argv ) 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 != full_pairs ) { - std::cerr << "Error: sparse and full differ!" << std::endl; + if( sparse_pairs != heap_pairs ) { + std::cerr << "Error: sparse and heap differ!" << std::endl; + error = true; + } + if( heap_pairs != full_pairs ) { + std::cerr << "Error: heap and full differ!" << std::endl; error = true; } if( full_pairs != vec_vec_pairs ) { -- cgit v1.2.3