merge of bitTree branch

git-svn-id: https://phat.googlecode.com/svn/trunk@27 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d

2 files changed, 185 insertions, 165 deletions

diff --git a/src/phat.cpp b/src/phat.cpp
index a98827c..6fec0c8 100644
--- a/src/phat.cpp
+++ b/src/phat.cpp
@@ -21,15 +21,16 @@
 #include <phat/representations/vector_vector.h>

 #include <phat/representations/vector_set.h>

 #include <phat/representations/sparse_pivot_column.h>

-#include <phat/representations/full_pivot_column.h> 

+#include <phat/representations/full_pivot_column.h>

+#include <phat/representations/bit_tree_pivot_column.h>

 

 #include <phat/algorithms/twist_reduction.h>

-#include <phat/algorithms/standard_reduction.h> 

+#include <phat/algorithms/standard_reduction.h>

 #include <phat/algorithms/row_reduction.h>

 #include <phat/algorithms/chunk_reduction.h>

 

 

-enum Representation_type  {VEC_VEC, VEC_SET, SPARSE_PIVOT, FULL_PIVOT};

+enum Representation_type  {VEC_VEC, VEC_SET, SPARSE_PIVOT, FULL_PIVOT, BIT_TREE_PIVOT};

 enum Algorithm_type  {STANDARD, TWIST, ROW, CHUNK };

 

 void print_help() {

@@ -42,23 +43,23 @@ 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 << "--vec-vec, --vec-set, --full-pivot, --sparse-pivot  --  selects a representation data structure for boundary matrices (default is '--sparse-pivot')" << std::endl;

+    std::cerr << "--vec-vec, --vec-set, --full-pivot, --sparse-pivot, --bit-tree-pivot  --  selects a representation data structure for boundary matrices (default is '--sparse-pivot')" << std::endl;

     std::cerr << "--standard, --twist, --chunk, --row  --  selects a reduction algorithm (default is '--twist')" << std::endl;

 }

 

 void print_help_and_exit() {

     print_help();

     exit( EXIT_FAILURE );

-}   

+}

 

 void parse_command_line( int argc, char** argv, bool& use_binary, Representation_type& rep_type, Algorithm_type& reduction,

                          std::string& input_filename, std::string& output_filename, bool& verbose, bool& dualize ) {

-    

+

     if( argc < 3 ) print_help_and_exit();

 

     input_filename = argv[ argc - 2 ];

     output_filename = argv[ argc - 1 ];

-    

+

     for( int idx = 1; idx < argc - 2; idx++ ) {

         const std::string option = argv[ idx ];

 

@@ -68,6 +69,7 @@ void parse_command_line( int argc, char** argv, bool& use_binary, Representation
         else if( option == "--vec-vec" ) rep_type = VEC_VEC;

         else if( option == "--vec-set" ) rep_type = VEC_SET;

         else if( option == "--full-pivot" )  rep_type = FULL_PIVOT;

+        else if( option == "--bit-tree-pivot" )  rep_type = BIT_TREE_PIVOT;

         else if( option == "--sparse-pivot" ) rep_type = SPARSE_PIVOT;

         else if( option == "--standard" ) reduction = STANDARD;

         else if( option == "--twist" ) reduction = TWIST;

@@ -79,7 +81,7 @@ void parse_command_line( int argc, char** argv, bool& use_binary, Representation
     }

 }

 

-#define LOG(msg) if( verbose ) std::cout << msg << std::endl; 

+#define LOG(msg) if( verbose ) std::cout << msg << std::endl;

 

 template<typename Representation, typename Algorithm>

 void generic_compute_pairing( std::string input_filename,

@@ -111,7 +113,7 @@ void generic_compute_pairing( std::string input_filename,
     LOG( "Computing persistence pairs ..." )

     if( dualize )

         phat::compute_persistence_pairs_dualized< Algorithm > ( pairs, matrix );

-    else 

+    else

         phat::compute_persistence_pairs < Algorithm > ( pairs, matrix );

     LOG( "Computing persistence pairs took " << omp_get_wtime() - pairs_timer <<"s" )

 

@@ -124,12 +126,12 @@ void generic_compute_pairing( std::string input_filename,
         pairs.save_ascii( output_filename );

     }

     LOG( "Writing output file took " << omp_get_wtime() - write_timer <<"s" )

-    

+

 }

 

 #define CALL_GENERIC_CODE(rep,alg) generic_compute_pairing < rep, alg >( input_filename, output_filename, use_binary, verbose, dualize );

 

-int main( int argc, char** argv ) 

+int main( int argc, char** argv )

 {

     bool use_binary = true; // interpret input as binary or ascii file

     Representation_type rep_type = SPARSE_PIVOT; // representation class

@@ -163,6 +165,13 @@ int main( int argc, char** argv )
                         case CHUNK: CALL_GENERIC_CODE(phat::full_pivot_column, phat::chunk_reduction) break;

                         } break;

 

+    case BIT_TREE_PIVOT:  switch( reduction ) {

+                        case STANDARD: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::standard_reduction) break;

+                        case TWIST: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::twist_reduction) break;

+                        case ROW: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::row_reduction) break;

+                        case CHUNK: CALL_GENERIC_CODE(phat::bit_tree_pivot_column, phat::chunk_reduction) break;

+                        } break;

+

     case SPARSE_PIVOT:  switch( reduction ) {

                         case STANDARD: CALL_GENERIC_CODE(phat::sparse_pivot_column, phat::standard_reduction) break;

                         case TWIST: CALL_GENERIC_CODE(phat::sparse_pivot_column, phat::twist_reduction) break;

diff --git a/src/self_test.cpp b/src/self_test.cpp
index 4764874..2aabdc4 100644
--- a/src/self_test.cpp
+++ b/src/self_test.cpp
@@ -1,154 +1,165 @@
-/*  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 <http://www.gnu.org/licenses/>. */
-
-#include <phat/compute_persistence_pairs.h>
-
-#include <phat/representations/vector_vector.h>
-#include <phat/representations/vector_set.h>
-#include <phat/representations/sparse_pivot_column.h>
-#include <phat/representations/full_pivot_column.h>
-
-#include <phat/algorithms/twist_reduction.h>
-#include <phat/algorithms/standard_reduction.h>
-#include <phat/algorithms/row_reduction.h>
-#include <phat/algorithms/chunk_reduction.h>
-
-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::full_pivot_column Full;
-    typedef phat::vector_vector Vec_vec;
-    typedef phat::vector_set Vec_set;
-    
-    std::cout << "Reading test data " << test_data << " in binary format ..." << std::endl;
-    phat::boundary_matrix< Full > boundary_matrix;
-    if( !boundary_matrix.load_binary( test_data ) ) {
-        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;
-        phat::persistence_pairs sparse_pairs;
-        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 - 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 - 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_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 );
-        
-        if( sparse_pairs != full_pairs ) {
-            std::cerr << "Error: sparse and full differ!" << std::endl;
-            error = true;
-        }
-        if( full_pairs != vec_vec_pairs ) {
-            std::cerr << "Error: full and vec_vec differ!" << std::endl;
-            error = true;
-        }
-        if( vec_vec_pairs != vec_set_pairs ) {
-            std::cerr << "Error: vec_vec and vec_set differ!" << std::endl;
-            error = true;
-        }
-        if( vec_set_pairs != sparse_pairs ) {
-            std::cerr << "Error: vec_set and sparse differ!" << std::endl;
-            error = true;
-        }
-        
-        if( error ) return EXIT_FAILURE;
-        else std::cout << "All results are identical (as they should be)" << std::endl;
-    }
-    
-    std::cout << "Comparing algorithms using full_pivot_column representation ..." << std::endl;
-    {
-        std::cout << "Running Twist - Full ..." << std::endl;
-        phat::persistence_pairs twist_pairs;
-        phat::boundary_matrix< Full > twist_boundary_matrix = boundary_matrix;
-        phat::compute_persistence_pairs< phat::twist_reduction >( twist_pairs, twist_boundary_matrix );
-        
-        std::cout << "Running Standard - Full ..." << std::endl;
-        phat::persistence_pairs std_pairs;
-        phat::boundary_matrix< Full > std_boundary_matrix = boundary_matrix;
-        phat::compute_persistence_pairs< phat::standard_reduction >( std_pairs, std_boundary_matrix );
-        
-        std::cout << "Running Chunk - Full ..." << std::endl;
-        phat::persistence_pairs chunk_pairs;
-        phat::boundary_matrix< Full > chunk_boundary_matrix = boundary_matrix;
-        phat::compute_persistence_pairs< phat::chunk_reduction >( chunk_pairs, chunk_boundary_matrix );
-        
-        std::cout << "Running Row - Full ..." << std::endl;
-        phat::persistence_pairs row_pairs;
-        phat::boundary_matrix< Full > row_boundary_matrix = boundary_matrix;
-        phat::compute_persistence_pairs< phat::row_reduction >( row_pairs, row_boundary_matrix );
-        
-        if( twist_pairs != std_pairs ) {
-            std::cerr << "Error: twist and standard differ!" << std::endl;
-            error = true;
-        }
-        if( std_pairs != chunk_pairs ) {
-            std::cerr << "Error: standard and chunk differ!" << std::endl;
-            error = true;
-        }
-        if( chunk_pairs != row_pairs ) {
-            std::cerr << "Error: chunk and row differ!" << std::endl;
-            error = true;
-        }
-        if( row_pairs != twist_pairs ) {
-            std::cerr << "Error: row and twist differ!" << std::endl;
-            error = true;
-        }
-        
-        if( error ) return EXIT_FAILURE;
-        else std::cout << "All results are identical (as they should be)" << std::endl;
-    }
-    
-    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::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::compute_persistence_pairs_dualized< phat::chunk_reduction >( dual_pairs, dual_boundary_matrix );
-        
-        if( primal_pairs != dual_pairs ) {
-            std::cerr << "Error: primal and dual differ!" << std::endl;
-            error = true;
-        }
-        
-        if( error ) return EXIT_FAILURE;
-        else std::cout << "All results are identical (as they should be)" << std::endl;
-    }
-    
-    return EXIT_SUCCESS;
-}
+/*  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 <http://www.gnu.org/licenses/>. */

+

+#include <phat/compute_persistence_pairs.h>

+

+#include <phat/representations/vector_vector.h>

+#include <phat/representations/vector_set.h>

+#include <phat/representations/sparse_pivot_column.h>

+#include <phat/representations/full_pivot_column.h>

+#include <phat/representations/bit_tree_pivot_column.h>

+

+#include <phat/algorithms/twist_reduction.h>

+#include <phat/algorithms/standard_reduction.h>

+#include <phat/algorithms/row_reduction.h>

+#include <phat/algorithms/chunk_reduction.h>

+

+int main( int argc, char** argv )

+{

+    std::string test_data = argc > 1 ? argv[ 1 ] : "torus.bin";

+

+    typedef phat::sparse_pivot_column Sparse;

+    typedef phat::full_pivot_column Full;

+    typedef phat::bit_tree_pivot_column BitTree;

+    typedef phat::vector_vector Vec_vec;

+    typedef phat::vector_set Vec_set;

+

+    std::cout << "Reading test data " << test_data << " in binary format ..." << std::endl;

+    phat::boundary_matrix< Full > boundary_matrix;

+    if( !boundary_matrix.load_binary( test_data ) ) {

+        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;

+        phat::persistence_pairs sparse_pairs;

+        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 - 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::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_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 );

+

+        if( sparse_pairs != full_pairs ) {

+            std::cerr << "Error: sparse and full differ!" << std::endl;

+            error = true;

+        }

+        if( full_pairs != vec_vec_pairs ) {

+            std::cerr << "Error: full and vec_vec differ!" << std::endl;

+            error = true;

+        }

+        if( vec_vec_pairs != vec_set_pairs ) {

+            std::cerr << "Error: vec_vec and vec_set differ!" << std::endl;

+            error = true;

+        }

+        if( vec_set_pairs != bit_tree_pairs ) {

+            std::cerr << "Error: vec_set and bit_tree differ!" << std::endl;

+            error = true;

+        }

+        if( bit_tree_pairs != sparse_pairs ) {

+            std::cerr << "Error: bit_tree and sparse differ!" << std::endl;

+            error = true;

+        }

+

+        if( error ) return EXIT_FAILURE;

+        else std::cout << "All results are identical (as they should be)" << std::endl;

+    }

+

+    std::cout << "Comparing algorithms using full_pivot_column representation ..." << std::endl;

+    {

+        std::cout << "Running Twist - Full ..." << std::endl;

+        phat::persistence_pairs twist_pairs;

+        phat::boundary_matrix< Full > twist_boundary_matrix = boundary_matrix;

+        phat::compute_persistence_pairs< phat::twist_reduction >( twist_pairs, twist_boundary_matrix );

+

+        std::cout << "Running Standard - Full ..." << std::endl;

+        phat::persistence_pairs std_pairs;

+        phat::boundary_matrix< Full > std_boundary_matrix = boundary_matrix;

+        phat::compute_persistence_pairs< phat::standard_reduction >( std_pairs, std_boundary_matrix );

+

+        std::cout << "Running Chunk - Full ..." << std::endl;

+        phat::persistence_pairs chunk_pairs;

+        phat::boundary_matrix< Full > chunk_boundary_matrix = boundary_matrix;

+        phat::compute_persistence_pairs< phat::chunk_reduction >( chunk_pairs, chunk_boundary_matrix );

+

+        std::cout << "Running Row - Full ..." << std::endl;

+        phat::persistence_pairs row_pairs;

+        phat::boundary_matrix< Full > row_boundary_matrix = boundary_matrix;

+        phat::compute_persistence_pairs< phat::row_reduction >( row_pairs, row_boundary_matrix );

+

+        if( twist_pairs != std_pairs ) {

+            std::cerr << "Error: twist and standard differ!" << std::endl;

+            error = true;

+        }

+        if( std_pairs != chunk_pairs ) {

+            std::cerr << "Error: standard and chunk differ!" << std::endl;

+            error = true;

+        }

+        if( chunk_pairs != row_pairs ) {

+            std::cerr << "Error: chunk and row differ!" << std::endl;

+            error = true;

+        }

+        if( row_pairs != twist_pairs ) {

+            std::cerr << "Error: row and twist differ!" << std::endl;

+            error = true;

+        }

+

+        if( error ) return EXIT_FAILURE;

+        else std::cout << "All results are identical (as they should be)" << std::endl;

+    }

+

+    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::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::compute_persistence_pairs_dualized< phat::chunk_reduction >( dual_pairs, dual_boundary_matrix );

+

+        if( primal_pairs != dual_pairs ) {

+            std::cerr << "Error: primal and dual differ!" << std::endl;

+            error = true;

+        }

+

+        if( error ) return EXIT_FAILURE;

+        else std::cout << "All results are identical (as they should be)" << std::endl;

+    }

+

+    return EXIT_SUCCESS;

+}