diff options
| author | Ulrich Bauer <mail@ulrich-bauer.org> | 2017-06-21 21:18:57 +0200 |
|---|---|---|
| committer | Ulrich Bauer <mail@ulrich-bauer.org> | 2017-06-21 21:18:57 +0200 |
| commit | c551fd32c8f67d62804a1ac925af9ea5e3479a9f (patch) | |
| tree | bb8c8a48f9cbb4c3897c9529bcc7ac76524782df | |
| parent | 3145aa8c43e298bd0b735a5ac155027ccb4deca5 (diff) | |
| parent | d898ef27044bc7f10da478d16581915e95edc2c9 (diff) | |
Merge branch 'dev' into representative-cocycles
* dev: (28 commits)
progress indicator
benchmark using sparsehash
updated benchmark
typo in readme
benchmark results
gudhi benchmark output
benchmark H^1
constructors fixed
code reformatting
code reformatting
reordered initializers
cleanup compressed distance matrix access
fixed move constructor
fix for missing constructor of diameter_entry_t
allow for negative edge filtration values
cleanup binomial coefficients
more code reorganization
code reorganization
moved attribute packed
don’t store diagonal in reduction matrix when not using coefficients
...
# Conflicts:
# Makefile
# ripser.cpp
# ripser.xcodeproj/project.pbxproj
23 files changed, 2224 insertions, 328 deletions
diff --git a/.clang-format b/.clang-format index 598d7c2..1975b19 100644 --- a/.clang-format +++ b/.clang-format @@ -1,7 +1,7 @@ BasedOnStyle: LLVM IndentWidth: 4 TabWidth: 4 -ColumnLimit: 120 +ColumnLimit: 100 AccessModifierOffset: -4 AllowShortIfStatementsOnASingleLine: true AllowShortLoopsOnASingleLine: true @@ -7,6 +7,8 @@ Copyright © 2015–2016 [Ulrich Bauer]. Ripser is a lean C++ code for the computation of Vietoris–Rips persistence barcodes. It can do just this one thing, but does it extremely well. +To see a live demo of Ripser's capabilities, go to [live.ripser.org]. The computation happens inside the browser (using [PNaCl] on Chrome and JavaScript via [Emscripten] on other browsers). + The main features of Ripser: - time- and memory-efficient @@ -14,7 +16,7 @@ The main features of Ripser: - support for coefficients in prime finite fields - no external dependencies (optional support for Google's [sparsehash]) -Currently, Ripser outperforms other codes ([Dionysus], [DIPHA], [GUDHI], [Perseus], [PHAT]) by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency. (Note that [PHAT] does not contain code for generating Vietoris–Rips filtrations). +Currently, Ripser outperforms other codes ([Dionysus], [DIPHA], [GUDHI], [Perseus], [PHAT]) by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency (for the example linked at [live.ripser.org]). (Note that [PHAT] does not contain code for generating Vietoris–Rips filtrations). Input formats currently supported by Ripser: @@ -57,7 +59,7 @@ Ripser supports several compile-time options. They are switched on by defining t - `USE_COEFFICIENTS`: enable support for coefficients in a prime field - `INDICATE_PROGRESS`: indicate the current progress in the console - `PRINT_PERSISTENCE_PAIRS`: output the computed persistence pairs (enabled by default in the code; comment out to disable) - - `USE_GOOGLE_HASHMAP`: enable support for Google's [sparsehash] data structure; may further reducue memory footprint + - `USE_GOOGLE_HASHMAP`: enable support for Google's [sparsehash] data structure; may further reduce memory footprint For example, to build Ripser with support for coefficients: @@ -72,7 +74,7 @@ The input is given either in a file whose name is passed as an argument, or thro - `--format`: use the specified file format for the input. The following formats are supported: - `lower-distance` (default if no format is specified): lower triangular distance matrix; a comma (or whitespace, or other non-numerical character) separated list of the distance matrix entries below the diagonal, sorted lexicographically by row index, then column index - `upper-distance`: upper triangular distance matrix; similar to the previous, but for the entries above the diagonal; suitable for output from the MATLAB functions `pdist` or `seqpdist`, exported to a CSV file - - `distances`: full distance matrix; similar to the above, but for all entries of the distance matrix + - `distance`: full distance matrix; similar to the above, but for all entries of the distance matrix - `dipha`: DIPHA distance matrix as described on the [DIPHA] website - `point-cloud`: point cloud; a comma (or whitespace, or other non-numerical character) separated list of coordinates of the points in some Euclidean space, one point per line - `--dim k`: compute persistent homology up to dimension *k* @@ -89,13 +91,17 @@ The following features are currently planned for future versions: - computation of representative cycles for persistent homology (currenly only *co*cycles are computed) - support for sparse distance matrices +Prototype implementations are already avaliable; please contact the author if one of these features might be relevant for your research. + ### License Ripser is licensed under the [LGPL] 3.0. Please contact the author if you want to use Ripser in your software under a different license. - [Ulrich Bauer]: <http://ulrich-bauer.org> +[live.ripser.org]: <http://live.ripser.org> +[PNaCl]: <https://www.chromium.org/nativeclient/pnacl/> +[Emscripten]: <http://emscripten.org> [latest-release]: <https://github.com/Ripser/ripser/releases/latest> [Dionysus]: <http://www.mrzv.org/software/dionysus/> [DIPHA]: <http://git.io/dipha> diff --git a/benchmarks/benchmarks.txt b/benchmarks/benchmarks.txt index c5fc91f..bb34d08 100644 --- a/benchmarks/benchmarks.txt +++ b/benchmarks/benchmarks.txt @@ -8,3 +8,4 @@ c++ -std=c++11 ripser.cpp -o ripser -Ofast -D NDEBUG -D FILE_FORMAT_DIPHA -D PRINT_PERSISTENCE_PAIRS && /usr/bin/time -l ./ripser --dim 2 ~/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex +/usr/bin/time -l java -Xmx16G -cp Bitbucket/phat-paper/benchmark:Source/javaplex/dist/javaplex-4.2.1.jar RipsFiltration ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2 3
\ No newline at end of file diff --git a/benchmarks/javaplex.txt b/benchmarks/javaplex.txt new file mode 100644 index 0000000..a39e804 --- /dev/null +++ b/benchmarks/javaplex.txt @@ -0,0 +1,19 @@ +geometry74:~ uli$ /usr/bin/time -l java -Xmx16G -cp Bitbucket/phat-paper/benchmark:Source/javaplex/dist/javaplex-4.2.1.jar RipsFiltration ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2 3 +Constructing Rips filtration in 425.57800000000003 s +Computing persistence (default) in 2848.477 s + 3275.48 real 3900.79 user 36.35 sys +12636958720 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 4791446 page reclaims + 2 page faults + 0 swaps + 5 block input operations + 5 block output operations + 0 messages sent + 0 messages received + 5 signals received + 9 voluntary context switches + 9898205 involuntary context switches + diff --git a/benchmarks/sphere_3_192/dionysus.dim_1.out.txt b/benchmarks/sphere_3_192/dionysus.dim_1.out.txt new file mode 100644 index 0000000..0e8cd4d --- /dev/null +++ b/benchmarks/sphere_3_192/dionysus.dim_1.out.txt @@ -0,0 +1,27 @@ +Boundary matrix: +Cocycles: *.ccl +Vertices: +Diagram: +Simplex vector generated, size: 1179808 + +0% 10 20 30 40 50 60 70 80 90 100% +|----|----|----|----|----|----|----|----|----|----| +*************************************************** +Rips timer : Elapsed time [4.19] seconds +Persistence timer : Elapsed time [2.38] seconds +Total timer : Elapsed time [7.45] seconds + 7.54 real 7.46 user 0.06 sys + 142344192 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 34700 page reclaims + 72 page faults + 0 swaps + 5 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 7 voluntary context switches + 212 involuntary context switches diff --git a/benchmarks/sphere_3_192/dionysus.dim_2.out.txt b/benchmarks/sphere_3_192/dionysus.dim_2.out.txt new file mode 100644 index 0000000..3495e23 --- /dev/null +++ b/benchmarks/sphere_3_192/dionysus.dim_2.out.txt @@ -0,0 +1,27 @@ +Boundary matrix: +Cocycles: *.ccl +Vertices: +Diagram: +Simplex vector generated, size: 56050288 + +0% 10 20 30 40 50 60 70 80 90 100% +|----|----|----|----|----|----|----|----|----|----| +*************************************************** +Rips timer : Elapsed time [256.35] seconds +Persistence timer : Elapsed time [205.61] seconds +Total timer : Elapsed time [528.91] seconds + 532.99 real 527.96 user 4.95 sys +3376783360 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 1430837 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 0 voluntary context switches + 17326 involuntary context switches diff --git a/benchmarks/sphere_3_192/dionysus.out.txt b/benchmarks/sphere_3_192/dionysus.out.txt new file mode 100644 index 0000000..3191f98 --- /dev/null +++ b/benchmarks/sphere_3_192/dionysus.out.txt @@ -0,0 +1,27 @@ +Boundary matrix: +Cocycles: *.ccl +Vertices: +Diagram: +Simplex vector generated, size: 1179808 + +0% 10 20 30 40 50 60 70 80 90 100% +|----|----|----|----|----|----|----|----|----|----| +*************************************************** +Rips timer : Elapsed time [4.39] seconds +Persistence timer : Elapsed time [2.55] seconds +Total timer : Elapsed time [7.88] seconds + 7.99 real 7.88 user 0.08 sys + 141664256 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 34606 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 0 voluntary context switches + 2629 involuntary context switches diff --git a/benchmarks/sphere_3_192/dipha.dim_1.out.txt b/benchmarks/sphere_3_192/dipha.dim_1.out.txt new file mode 100644 index 0000000..133977f --- /dev/null +++ b/benchmarks/sphere_3_192/dipha.dim_1.out.txt @@ -0,0 +1,55 @@ + +Input filename: +/Users/uli/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex + +upper_dim: 2 + +Number of processes used: +1 + +Detailed information for rank 0: + time prior mem peak mem bytes recv + 0.0s 3 MB 4 MB 0 MB complex.load_binary( input_filename, upper_dim ); + +Number of cells in input: +1179808 + 0.2s 4 MB 40 MB 0 MB get_filtration_to_cell_map( complex, dualize, filtration_to_cell_map ); + 0.1s 40 MB 127 MB 18 MB get_cell_to_filtration_map( complex.get_num_cells(), filtration_to_cell_map, cell_to_filtration_map ); + 0.0s 154 MB 156 MB 0 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.0s 153 MB 156 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 0.3s 150 MB 165 MB 53 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.1s 136 MB 169 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 0.1s 167 MB 169 MB 1 MB dipha::outputs::save_persistence_diagram( output_filename, complex, filtration_to_cell_map, reduced_columns, dualize, upper_dim ); + +Overall running time in seconds: +0.8 + +Reduction kernel running time in seconds: +0.1 + +Overall peak mem in GB of all ranks: +0.2 + +Individual peak mem in GB of per rank: +0.2 + +Maximal communication traffic (without sorting) in GB between any pair of nodes: +0.1 + +Total communication traffic (without sorting) in GB between all pairs of nodes: +0.1 + 0.90 real 0.71 user 0.15 sys + 177610752 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 78019 page reclaims + 164 page faults + 0 swaps + 10 block input operations + 8 block output operations + 0 messages sent + 0 messages received + 0 signals received + 48 voluntary context switches + 367 involuntary context switches diff --git a/benchmarks/sphere_3_192/dipha.dim_2.out.txt b/benchmarks/sphere_3_192/dipha.dim_2.out.txt new file mode 100644 index 0000000..1a7b30b --- /dev/null +++ b/benchmarks/sphere_3_192/dipha.dim_2.out.txt @@ -0,0 +1,57 @@ + +Input filename: +/Users/uli/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex + +upper_dim: 3 + +Number of processes used: +1 + +Detailed information for rank 0: + time prior mem peak mem bytes recv + 0.0s 3 MB 4 MB 0 MB complex.load_binary( input_filename, upper_dim ); + +Number of cells in input: +56050288 + 12.3s 4 MB 1714 MB 0 MB get_filtration_to_cell_map( complex, dualize, filtration_to_cell_map ); + 5.5s 431 MB 4416 MB 855 MB get_cell_to_filtration_map( complex.get_num_cells(), filtration_to_cell_map, cell_to_filtration_map ); + 0.3s 2278 MB 4416 MB 0 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.0s 2279 MB 4416 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 0.6s 2279 MB 4416 MB 53 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.0s 2240 MB 4416 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 18.7s 2252 MB 5285 MB 3349 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 5.9s 3930 MB 5715 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 6.8s 3716 MB 5715 MB 106 MB dipha::outputs::save_persistence_diagram( output_filename, complex, filtration_to_cell_map, reduced_columns, dualize, upper_dim ); + +Overall running time in seconds: +50.9 + +Reduction kernel running time in seconds: +5.9 + +Overall peak mem in GB of all ranks: +5.6 + +Individual peak mem in GB of per rank: +5.6 + +Maximal communication traffic (without sorting) in GB between any pair of nodes: +4.3 + +Total communication traffic (without sorting) in GB between all pairs of nodes: +4.3 + 50.97 real 42.99 user 7.93 sys +5993607168 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 5448458 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 6 block output operations + 0 messages sent + 0 messages received + 0 signals received + 6 voluntary context switches + 6625 involuntary context switches diff --git a/benchmarks/sphere_3_192/dipha.out.txt b/benchmarks/sphere_3_192/dipha.out.txt new file mode 100644 index 0000000..bae5fc7 --- /dev/null +++ b/benchmarks/sphere_3_192/dipha.out.txt @@ -0,0 +1,55 @@ + +Input filename: +/Users/uli/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex + +upper_dim: 2 + +Number of processes used: +1 + +Detailed information for rank 0: + time prior mem peak mem bytes recv + 0.0s 3 MB 4 MB 0 MB complex.load_binary( input_filename, upper_dim ); + +Number of cells in input: +1179808 + 0.2s 4 MB 40 MB 0 MB get_filtration_to_cell_map( complex, dualize, filtration_to_cell_map ); + 0.1s 40 MB 127 MB 18 MB get_cell_to_filtration_map( complex.get_num_cells(), filtration_to_cell_map, cell_to_filtration_map ); + 0.0s 154 MB 156 MB 0 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.0s 153 MB 156 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 0.3s 151 MB 165 MB 53 MB generate_unreduced_columns( complex, filtration_to_cell_map, cell_to_filtration_map, cur_dim, dualize, unreduced_columns ); + 0.1s 136 MB 169 MB 0 MB reduction_kernel( complex.get_num_cells(), unreduced_columns, reduced_columns ); + 0.1s 167 MB 169 MB 1 MB dipha::outputs::save_persistence_diagram( output_filename, complex, filtration_to_cell_map, reduced_columns, dualize, upper_dim ); + +Overall running time in seconds: +0.9 + +Reduction kernel running time in seconds: +0.1 + +Overall peak mem in GB of all ranks: +0.2 + +Individual peak mem in GB of per rank: +0.2 + +Maximal communication traffic (without sorting) in GB between any pair of nodes: +0.1 + +Total communication traffic (without sorting) in GB between all pairs of nodes: +0.1 + 0.94 real 0.75 user 0.16 sys + 177598464 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 78159 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 5 voluntary context switches + 333 involuntary context switches diff --git a/benchmarks/sphere_3_192/gudhi.dim_1.out.txt b/benchmarks/sphere_3_192/gudhi.dim_1.out.txt new file mode 100644 index 0000000..94e7f6e --- /dev/null +++ b/benchmarks/sphere_3_192/gudhi.dim_1.out.txt @@ -0,0 +1,262 @@ +The complex contains 1179808 simplices + and has dimension 2 +2 0 0 inf +2 1 0.316534 0.682559 +2 1 0.304761 0.647803 +2 0 0 0.332695 +2 0 0 0.323964 +2 0 0 0.319493 +2 0 0 0.316023 +2 1 0.34298 0.65758 +2 0 0 0.304062 +2 0 0 0.297933 +2 0 0 0.297053 +2 0 0 0.293466 +2 1 0.347806 0.638039 +2 0 0 0.289189 +2 0 0 0.288591 +2 0 0 0.287316 +2 0 0 0.285416 +2 0 0 0.283881 +2 0 0 0.283562 +2 0 0 0.282169 +2 0 0 0.280629 +2 0 0 0.277582 +2 0 0 0.277191 +2 0 0 0.276431 +2 0 0 0.274611 +2 0 0 0.270996 +2 0 0 0.268806 +2 0 0 0.266635 +2 0 0 0.266592 +2 0 0 0.264483 +2 0 0 0.264334 +2 0 0 0.257997 +2 0 0 0.25725 +2 0 0 0.253227 +2 0 0 0.253163 +2 0 0 0.249345 +2 0 0 0.249339 +2 0 0 0.248879 +2 0 0 0.247042 +2 0 0 0.246491 +2 0 0 0.24509 +2 0 0 0.24348 +2 0 0 0.240632 +2 0 0 0.23879 +2 0 0 0.237571 +2 0 0 0.234969 +2 0 0 0.234112 +2 0 0 0.231675 +2 0 0 0.231179 +2 1 0.35058 0.580726 +2 0 0 0.228917 +2 0 0 0.2286 +2 0 0 0.227933 +2 0 0 0.227524 +2 0 0 0.223232 +2 0 0 0.218561 +2 0 0 0.218526 +2 0 0 0.215759 +2 0 0 0.214018 +2 1 0.347388 0.559978 +2 0 0 0.210372 +2 0 0 0.208851 +2 0 0 0.208063 +2 0 0 0.207714 +2 0 0 0.207261 +2 0 0 0.207016 +2 0 0 0.205389 +2 0 0 0.204544 +2 0 0 0.204208 +2 0 0 0.203812 +2 0 0 0.202564 +2 0 0 0.201961 +2 0 0 0.199673 +2 0 0 0.197377 +2 0 0 0.195722 +2 0 0 0.193804 +2 0 0 0.193791 +2 0 0 0.192733 +2 0 0 0.192406 +2 0 0 0.192356 +2 0 0 0.191661 +2 0 0 0.190642 +2 1 0.352356 0.541947 +2 0 0 0.189106 +2 0 0 0.184757 +2 0 0 0.18428 +2 0 0 0.179609 +2 1 0.301986 0.478334 +2 0 0 0.176306 +2 0 0 0.175016 +2 0 0 0.17493 +2 0 0 0.174172 +2 0 0 0.173684 +2 0 0 0.173586 +2 0 0 0.173412 +2 0 0 0.168587 +2 0 0 0.167455 +2 0 0 0.165907 +2 0 0 0.165592 +2 0 0 0.165494 +2 0 0 0.165314 +2 0 0 0.165202 +2 0 0 0.164815 +2 0 0 0.164809 +2 0 0 0.162464 +2 1 0.322683 0.482958 +2 0 0 0.159282 +2 0 0 0.158413 +2 0 0 0.157373 +2 0 0 0.157293 +2 0 0 0.157251 +2 0 0 0.1569 +2 0 0 0.15587 +2 0 0 0.154095 +2 0 0 0.15244 +2 0 0 0.151643 +2 0 0 0.150747 +2 0 0 0.149226 +2 0 0 0.149017 +2 0 0 0.148506 +2 0 0 0.147427 +2 0 0 0.147289 +2 0 0 0.147203 +2 0 0 0.145725 +2 0 0 0.145018 +2 0 0 0.143151 +2 0 0 0.143085 +2 0 0 0.142834 +2 0 0 0.142537 +2 0 0 0.142152 +2 0 0 0.141823 +2 0 0 0.138674 +2 1 0.377729 0.514046 +2 0 0 0.135402 +2 0 0 0.134886 +2 0 0 0.133722 +2 0 0 0.133525 +2 0 0 0.133033 +2 0 0 0.131638 +2 0 0 0.131438 +2 0 0 0.129741 +2 0 0 0.127864 +2 0 0 0.127383 +2 0 0 0.126595 +2 0 0 0.124774 +2 1 0.339394 0.463666 +2 0 0 0.123527 +2 0 0 0.122089 +2 0 0 0.121955 +2 0 0 0.119187 +2 1 0.2576 0.373749 +2 0 0 0.115939 +2 1 0.370051 0.483155 +2 0 0 0.111798 +2 0 0 0.111131 +2 0 0 0.109526 +2 0 0 0.108768 +2 1 0.386278 0.4922 +2 1 0.443911 0.54761 +2 1 0.374531 0.477153 +2 1 0.354747 0.454956 +2 0 0 0.0994522 +2 1 0.318032 0.417462 +2 0 0 0.0988752 +2 0 0 0.0970981 +2 0 0 0.0959033 +2 0 0 0.0884133 +2 0 0 0.0870489 +2 0 0 0.0857401 +2 0 0 0.084341 +2 0 0 0.0831521 +2 0 0 0.0831358 +2 0 0 0.0814685 +2 0 0 0.0802451 +2 0 0 0.0800348 +2 0 0 0.0792212 +2 0 0 0.0782455 +2 0 0 0.076909 +2 0 0 0.0753955 +2 1 0.324159 0.399094 +2 0 0 0.0746054 +2 0 0 0.0743236 +2 0 0 0.0741239 +2 1 0.413789 0.487379 +2 0 0 0.0728647 +2 0 0 0.0714516 +2 0 0 0.0702075 +2 0 0 0.0692368 +2 1 0.409968 0.478461 +2 0 0 0.0672609 +2 0 0 0.0651112 +2 0 0 0.0637053 +2 0 0 0.0633425 +2 1 0.298341 0.360737 +2 0 0 0.0623736 +2 1 0.309419 0.37151 +2 1 0.411549 0.471715 +2 0 0 0.0593071 +2 0 0 0.057488 +2 1 0.377019 0.434385 +2 1 0.329066 0.386148 +2 0 0 0.0560443 +2 0 0 0.0559886 +2 0 0 0.0522132 +2 0 0 0.0515157 +2 1 0.412572 0.46308 +2 0 0 0.0496187 +2 0 0 0.048826 +2 0 0 0.0487061 +2 1 0.240869 0.288747 +2 0 0 0.0471186 +2 1 0.531636 0.578093 +2 1 0.530723 0.576869 +2 1 0.33364 0.3797 +2 1 0.431628 0.477277 +2 0 0 0.0433426 +2 1 0.344005 0.387193 +2 1 0.463389 0.505345 +2 1 0.361715 0.403181 +2 1 0.381084 0.421374 +2 1 0.253337 0.292286 +2 0 0 0.0387451 +2 0 0 0.037954 +2 1 0.377147 0.414788 +2 1 0.308779 0.346297 +2 1 0.317521 0.349622 +2 0 0 0.0311057 +2 1 0.331259 0.356381 +2 1 0.279016 0.301331 +2 0 0 0.0217315 +2 1 0.350913 0.369543 +2 1 0.324571 0.343083 +2 0 0 0.0173134 +2 1 0.33392 0.35111 +2 1 0.542696 0.558863 +2 1 0.33836 0.350411 +2 1 0.29997 0.311993 +2 0 0 0.0120098 +2 1 0.189652 0.197515 +2 0 0 0.00391946 +2 0 0 0.0036753 +2 1 0.445398 0.448892 +2 1 0.24546 0.248903 +2 1 0.301045 0.303943 +2 1 0.309336 0.310216 + 0.56 real 0.52 user 0.02 sys + 69439488 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 16943 page reclaims + 29 page faults + 0 swaps + 2 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 10 voluntary context switches + 73 involuntary context switches diff --git a/benchmarks/sphere_3_192/gudhi.dim_2.out.txt b/benchmarks/sphere_3_192/gudhi.dim_2.out.txt new file mode 100644 index 0000000..36740c8 --- /dev/null +++ b/benchmarks/sphere_3_192/gudhi.dim_2.out.txt @@ -0,0 +1,263 @@ +The complex contains 56050288 simplices + and has dimension 3 +2 0 0 inf +2 2 0.720484 1.65562 +2 1 0.316534 0.682559 +2 1 0.304761 0.647803 +2 0 0 0.332695 +2 0 0 0.323964 +2 0 0 0.319493 +2 0 0 0.316023 +2 1 0.34298 0.65758 +2 0 0 0.304062 +2 0 0 0.297933 +2 0 0 0.297053 +2 0 0 0.293466 +2 1 0.347806 0.638039 +2 0 0 0.289189 +2 0 0 0.288591 +2 0 0 0.287316 +2 0 0 0.285416 +2 0 0 0.283881 +2 0 0 0.283562 +2 0 0 0.282169 +2 0 0 0.280629 +2 0 0 0.277582 +2 0 0 0.277191 +2 0 0 0.276431 +2 0 0 0.274611 +2 0 0 0.270996 +2 0 0 0.268806 +2 0 0 0.266635 +2 0 0 0.266592 +2 0 0 0.264483 +2 0 0 0.264334 +2 0 0 0.257997 +2 0 0 0.25725 +2 0 0 0.253227 +2 0 0 0.253163 +2 0 0 0.249345 +2 0 0 0.249339 +2 0 0 0.248879 +2 0 0 0.247042 +2 0 0 0.246491 +2 0 0 0.24509 +2 0 0 0.24348 +2 0 0 0.240632 +2 0 0 0.23879 +2 0 0 0.237571 +2 0 0 0.234969 +2 0 0 0.234112 +2 0 0 0.231675 +2 0 0 0.231179 +2 1 0.35058 0.580726 +2 0 0 0.228917 +2 0 0 0.2286 +2 0 0 0.227933 +2 0 0 0.227524 +2 0 0 0.223232 +2 0 0 0.218561 +2 0 0 0.218526 +2 0 0 0.215759 +2 0 0 0.214018 +2 1 0.347388 0.559978 +2 0 0 0.210372 +2 0 0 0.208851 +2 0 0 0.208063 +2 0 0 0.207714 +2 0 0 0.207261 +2 0 0 0.207016 +2 0 0 0.205389 +2 0 0 0.204544 +2 0 0 0.204208 +2 0 0 0.203812 +2 0 0 0.202564 +2 0 0 0.201961 +2 0 0 0.199673 +2 0 0 0.197377 +2 0 0 0.195722 +2 0 0 0.193804 +2 0 0 0.193791 +2 0 0 0.192733 +2 0 0 0.192406 +2 0 0 0.192356 +2 0 0 0.191661 +2 0 0 0.190642 +2 1 0.352356 0.541947 +2 0 0 0.189106 +2 0 0 0.184757 +2 0 0 0.18428 +2 0 0 0.179609 +2 1 0.301986 0.478334 +2 0 0 0.176306 +2 0 0 0.175016 +2 0 0 0.17493 +2 0 0 0.174172 +2 0 0 0.173684 +2 0 0 0.173586 +2 0 0 0.173412 +2 0 0 0.168587 +2 0 0 0.167455 +2 0 0 0.165907 +2 0 0 0.165592 +2 0 0 0.165494 +2 0 0 0.165314 +2 0 0 0.165202 +2 0 0 0.164815 +2 0 0 0.164809 +2 0 0 0.162464 +2 1 0.322683 0.482958 +2 0 0 0.159282 +2 0 0 0.158413 +2 0 0 0.157373 +2 0 0 0.157293 +2 0 0 0.157251 +2 0 0 0.1569 +2 0 0 0.15587 +2 0 0 0.154095 +2 0 0 0.15244 +2 0 0 0.151643 +2 0 0 0.150747 +2 0 0 0.149226 +2 0 0 0.149017 +2 0 0 0.148506 +2 0 0 0.147427 +2 0 0 0.147289 +2 0 0 0.147203 +2 0 0 0.145725 +2 0 0 0.145018 +2 0 0 0.143151 +2 0 0 0.143085 +2 0 0 0.142834 +2 0 0 0.142537 +2 0 0 0.142152 +2 0 0 0.141823 +2 0 0 0.138674 +2 1 0.377729 0.514046 +2 0 0 0.135402 +2 0 0 0.134886 +2 0 0 0.133722 +2 0 0 0.133525 +2 0 0 0.133033 +2 0 0 0.131638 +2 0 0 0.131438 +2 0 0 0.129741 +2 0 0 0.127864 +2 0 0 0.127383 +2 0 0 0.126595 +2 0 0 0.124774 +2 1 0.339394 0.463666 +2 0 0 0.123527 +2 0 0 0.122089 +2 0 0 0.121955 +2 0 0 0.119187 +2 1 0.2576 0.373749 +2 0 0 0.115939 +2 1 0.370051 0.483155 +2 0 0 0.111798 +2 0 0 0.111131 +2 0 0 0.109526 +2 0 0 0.108768 +2 1 0.386278 0.4922 +2 1 0.443911 0.54761 +2 1 0.374531 0.477153 +2 1 0.354747 0.454956 +2 0 0 0.0994522 +2 1 0.318032 0.417462 +2 0 0 0.0988752 +2 0 0 0.0970981 +2 0 0 0.0959033 +2 0 0 0.0884133 +2 0 0 0.0870489 +2 0 0 0.0857401 +2 0 0 0.084341 +2 0 0 0.0831521 +2 0 0 0.0831358 +2 0 0 0.0814685 +2 0 0 0.0802451 +2 0 0 0.0800348 +2 0 0 0.0792212 +2 0 0 0.0782455 +2 0 0 0.076909 +2 0 0 0.0753955 +2 1 0.324159 0.399094 +2 0 0 0.0746054 +2 0 0 0.0743236 +2 0 0 0.0741239 +2 1 0.413789 0.487379 +2 0 0 0.0728647 +2 0 0 0.0714516 +2 0 0 0.0702075 +2 0 0 0.0692368 +2 1 0.409968 0.478461 +2 0 0 0.0672609 +2 0 0 0.0651112 +2 0 0 0.0637053 +2 0 0 0.0633425 +2 1 0.298341 0.360737 +2 0 0 0.0623736 +2 1 0.309419 0.37151 +2 1 0.411549 0.471715 +2 0 0 0.0593071 +2 0 0 0.057488 +2 1 0.377019 0.434385 +2 1 0.329066 0.386148 +2 0 0 0.0560443 +2 0 0 0.0559886 +2 0 0 0.0522132 +2 0 0 0.0515157 +2 1 0.412572 0.46308 +2 0 0 0.0496187 +2 0 0 0.048826 +2 0 0 0.0487061 +2 1 0.240869 0.288747 +2 0 0 0.0471186 +2 1 0.531636 0.578093 +2 1 0.530723 0.576869 +2 1 0.33364 0.3797 +2 1 0.431628 0.477277 +2 0 0 0.0433426 +2 1 0.344005 0.387193 +2 1 0.463389 0.505345 +2 1 0.361715 0.403181 +2 1 0.381084 0.421374 +2 1 0.253337 0.292286 +2 0 0 0.0387451 +2 0 0 0.037954 +2 1 0.377147 0.414788 +2 1 0.308779 0.346297 +2 1 0.317521 0.349622 +2 0 0 0.0311057 +2 1 0.331259 0.356381 +2 1 0.279016 0.301331 +2 0 0 0.0217315 +2 1 0.350913 0.369543 +2 1 0.324571 0.343083 +2 0 0 0.0173134 +2 1 0.33392 0.35111 +2 1 0.542696 0.558863 +2 1 0.33836 0.350411 +2 1 0.29997 0.311993 +2 0 0 0.0120098 +2 1 0.189652 0.197515 +2 0 0 0.00391946 +2 0 0 0.0036753 +2 1 0.445398 0.448892 +2 1 0.24546 0.248903 +2 1 0.301045 0.303943 +2 1 0.309336 0.310216 + 75.58 real 74.18 user 1.35 sys +2911698944 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 820365 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 11 voluntary context switches + 9107 involuntary context switches diff --git a/benchmarks/sphere_3_192/gudhi.out.txt b/benchmarks/sphere_3_192/gudhi.out.txt new file mode 100644 index 0000000..1a0cddf --- /dev/null +++ b/benchmarks/sphere_3_192/gudhi.out.txt @@ -0,0 +1,262 @@ +The complex contains 1179808 simplices + and has dimension 2 +2 0 0 inf +2 1 0.316534 0.682559 +2 1 0.304761 0.647803 +2 0 0 0.332695 +2 0 0 0.323964 +2 0 0 0.319493 +2 0 0 0.316023 +2 1 0.34298 0.65758 +2 0 0 0.304062 +2 0 0 0.297933 +2 0 0 0.297053 +2 0 0 0.293466 +2 1 0.347806 0.638039 +2 0 0 0.289189 +2 0 0 0.288591 +2 0 0 0.287316 +2 0 0 0.285416 +2 0 0 0.283881 +2 0 0 0.283562 +2 0 0 0.282169 +2 0 0 0.280629 +2 0 0 0.277582 +2 0 0 0.277191 +2 0 0 0.276431 +2 0 0 0.274611 +2 0 0 0.270996 +2 0 0 0.268806 +2 0 0 0.266635 +2 0 0 0.266592 +2 0 0 0.264483 +2 0 0 0.264334 +2 0 0 0.257997 +2 0 0 0.25725 +2 0 0 0.253227 +2 0 0 0.253163 +2 0 0 0.249345 +2 0 0 0.249339 +2 0 0 0.248879 +2 0 0 0.247042 +2 0 0 0.246491 +2 0 0 0.24509 +2 0 0 0.24348 +2 0 0 0.240632 +2 0 0 0.23879 +2 0 0 0.237571 +2 0 0 0.234969 +2 0 0 0.234112 +2 0 0 0.231675 +2 0 0 0.231179 +2 1 0.35058 0.580726 +2 0 0 0.228917 +2 0 0 0.2286 +2 0 0 0.227933 +2 0 0 0.227524 +2 0 0 0.223232 +2 0 0 0.218561 +2 0 0 0.218526 +2 0 0 0.215759 +2 0 0 0.214018 +2 1 0.347388 0.559978 +2 0 0 0.210372 +2 0 0 0.208851 +2 0 0 0.208063 +2 0 0 0.207714 +2 0 0 0.207261 +2 0 0 0.207016 +2 0 0 0.205389 +2 0 0 0.204544 +2 0 0 0.204208 +2 0 0 0.203812 +2 0 0 0.202564 +2 0 0 0.201961 +2 0 0 0.199673 +2 0 0 0.197377 +2 0 0 0.195722 +2 0 0 0.193804 +2 0 0 0.193791 +2 0 0 0.192733 +2 0 0 0.192406 +2 0 0 0.192356 +2 0 0 0.191661 +2 0 0 0.190642 +2 1 0.352356 0.541947 +2 0 0 0.189106 +2 0 0 0.184757 +2 0 0 0.18428 +2 0 0 0.179609 +2 1 0.301986 0.478334 +2 0 0 0.176306 +2 0 0 0.175016 +2 0 0 0.17493 +2 0 0 0.174172 +2 0 0 0.173684 +2 0 0 0.173586 +2 0 0 0.173412 +2 0 0 0.168587 +2 0 0 0.167455 +2 0 0 0.165907 +2 0 0 0.165592 +2 0 0 0.165494 +2 0 0 0.165314 +2 0 0 0.165202 +2 0 0 0.164815 +2 0 0 0.164809 +2 0 0 0.162464 +2 1 0.322683 0.482958 +2 0 0 0.159282 +2 0 0 0.158413 +2 0 0 0.157373 +2 0 0 0.157293 +2 0 0 0.157251 +2 0 0 0.1569 +2 0 0 0.15587 +2 0 0 0.154095 +2 0 0 0.15244 +2 0 0 0.151643 +2 0 0 0.150747 +2 0 0 0.149226 +2 0 0 0.149017 +2 0 0 0.148506 +2 0 0 0.147427 +2 0 0 0.147289 +2 0 0 0.147203 +2 0 0 0.145725 +2 0 0 0.145018 +2 0 0 0.143151 +2 0 0 0.143085 +2 0 0 0.142834 +2 0 0 0.142537 +2 0 0 0.142152 +2 0 0 0.141823 +2 0 0 0.138674 +2 1 0.377729 0.514046 +2 0 0 0.135402 +2 0 0 0.134886 +2 0 0 0.133722 +2 0 0 0.133525 +2 0 0 0.133033 +2 0 0 0.131638 +2 0 0 0.131438 +2 0 0 0.129741 +2 0 0 0.127864 +2 0 0 0.127383 +2 0 0 0.126595 +2 0 0 0.124774 +2 1 0.339394 0.463666 +2 0 0 0.123527 +2 0 0 0.122089 +2 0 0 0.121955 +2 0 0 0.119187 +2 1 0.2576 0.373749 +2 0 0 0.115939 +2 1 0.370051 0.483155 +2 0 0 0.111798 +2 0 0 0.111131 +2 0 0 0.109526 +2 0 0 0.108768 +2 1 0.386278 0.4922 +2 1 0.443911 0.54761 +2 1 0.374531 0.477153 +2 1 0.354747 0.454956 +2 0 0 0.0994522 +2 1 0.318032 0.417462 +2 0 0 0.0988752 +2 0 0 0.0970981 +2 0 0 0.0959033 +2 0 0 0.0884133 +2 0 0 0.0870489 +2 0 0 0.0857401 +2 0 0 0.084341 +2 0 0 0.0831521 +2 0 0 0.0831358 +2 0 0 0.0814685 +2 0 0 0.0802451 +2 0 0 0.0800348 +2 0 0 0.0792212 +2 0 0 0.0782455 +2 0 0 0.076909 +2 0 0 0.0753955 +2 1 0.324159 0.399094 +2 0 0 0.0746054 +2 0 0 0.0743236 +2 0 0 0.0741239 +2 1 0.413789 0.487379 +2 0 0 0.0728647 +2 0 0 0.0714516 +2 0 0 0.0702075 +2 0 0 0.0692368 +2 1 0.409968 0.478461 +2 0 0 0.0672609 +2 0 0 0.0651112 +2 0 0 0.0637053 +2 0 0 0.0633425 +2 1 0.298341 0.360737 +2 0 0 0.0623736 +2 1 0.309419 0.37151 +2 1 0.411549 0.471715 +2 0 0 0.0593071 +2 0 0 0.057488 +2 1 0.377019 0.434385 +2 1 0.329066 0.386148 +2 0 0 0.0560443 +2 0 0 0.0559886 +2 0 0 0.0522132 +2 0 0 0.0515157 +2 1 0.412572 0.46308 +2 0 0 0.0496187 +2 0 0 0.048826 +2 0 0 0.0487061 +2 1 0.240869 0.288747 +2 0 0 0.0471186 +2 1 0.531636 0.578093 +2 1 0.530723 0.576869 +2 1 0.33364 0.3797 +2 1 0.431628 0.477277 +2 0 0 0.0433426 +2 1 0.344005 0.387193 +2 1 0.463389 0.505345 +2 1 0.361715 0.403181 +2 1 0.381084 0.421374 +2 1 0.253337 0.292286 +2 0 0 0.0387451 +2 0 0 0.037954 +2 1 0.377147 0.414788 +2 1 0.308779 0.346297 +2 1 0.317521 0.349622 +2 0 0 0.0311057 +2 1 0.331259 0.356381 +2 1 0.279016 0.301331 +2 0 0 0.0217315 +2 1 0.350913 0.369543 +2 1 0.324571 0.343083 +2 0 0 0.0173134 +2 1 0.33392 0.35111 +2 1 0.542696 0.558863 +2 1 0.33836 0.350411 +2 1 0.29997 0.311993 +2 0 0 0.0120098 +2 1 0.189652 0.197515 +2 0 0 0.00391946 +2 0 0 0.0036753 +2 1 0.445398 0.448892 +2 1 0.24546 0.248903 +2 1 0.301045 0.303943 +2 1 0.309336 0.310216 + 0.59 real 0.56 user 0.02 sys + 69210112 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 16916 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 10 voluntary context switches + 125 involuntary context switches diff --git a/benchmarks/sphere_3_192/ripser.dim_1.out.txt b/benchmarks/sphere_3_192/ripser.dim_1.out.txt new file mode 100644 index 0000000..4ef9cb2 --- /dev/null +++ b/benchmarks/sphere_3_192/ripser.dim_1.out.txt @@ -0,0 +1,264 @@ +distance matrix with 192 points +value range: [0.00367531,2] +persistence intervals in dim 0: + [0,0.00367531) + [0,0.00391946) + [0,0.0120098) + [0,0.0173134) + [0,0.0217315) + [0,0.0311057) + [0,0.037954) + [0,0.0387451) + [0,0.0433426) + [0,0.0471186) + [0,0.0487061) + [0,0.048826) + [0,0.0496187) + [0,0.0515157) + [0,0.0522132) + [0,0.0559886) + [0,0.0560443) + [0,0.057488) + [0,0.0593071) + [0,0.0623736) + [0,0.0633425) + [0,0.0637053) + [0,0.0651112) + [0,0.0672609) + [0,0.0692368) + [0,0.0702075) + [0,0.0714516) + [0,0.0728647) + [0,0.0741239) + [0,0.0743236) + [0,0.0746054) + [0,0.0753955) + [0,0.076909) + [0,0.0782455) + [0,0.0792212) + [0,0.0800348) + [0,0.0802451) + [0,0.0814685) + [0,0.0831358) + [0,0.0831521) + [0,0.084341) + [0,0.0857401) + [0,0.0870489) + [0,0.0884133) + [0,0.0959033) + [0,0.0970981) + [0,0.0988752) + [0,0.0994522) + [0,0.108768) + [0,0.109526) + [0,0.111131) + [0,0.111798) + [0,0.115939) + [0,0.119187) + [0,0.121955) + [0,0.122089) + [0,0.123527) + [0,0.124774) + [0,0.126595) + [0,0.127383) + [0,0.127864) + [0,0.129741) + [0,0.131438) + [0,0.131638) + [0,0.133033) + [0,0.133525) + [0,0.133722) + [0,0.134886) + [0,0.135402) + [0,0.138674) + [0,0.141823) + [0,0.142152) + [0,0.142537) + [0,0.142834) + [0,0.143085) + [0,0.143151) + [0,0.145018) + [0,0.145725) + [0,0.147203) + [0,0.147289) + [0,0.147427) + [0,0.148506) + [0,0.149017) + [0,0.149226) + [0,0.150747) + [0,0.151643) + [0,0.15244) + [0,0.154095) + [0,0.15587) + [0,0.1569) + [0,0.157251) + [0,0.157293) + [0,0.157373) + [0,0.158413) + [0,0.159282) + [0,0.162464) + [0,0.164809) + [0,0.164815) + [0,0.165202) + [0,0.165314) + [0,0.165494) + [0,0.165592) + [0,0.165907) + [0,0.167455) + [0,0.168587) + [0,0.173412) + [0,0.173586) + [0,0.173684) + [0,0.174172) + [0,0.17493) + [0,0.175016) + [0,0.176306) + [0,0.179609) + [0,0.18428) + [0,0.184757) + [0,0.189106) + [0,0.190642) + [0,0.191661) + [0,0.192356) + [0,0.192406) + [0,0.192733) + [0,0.193791) + [0,0.193804) + [0,0.195722) + [0,0.197377) + [0,0.199673) + [0,0.201961) + [0,0.202564) + [0,0.203812) + [0,0.204208) + [0,0.204544) + [0,0.205389) + [0,0.207016) + [0,0.207261) + [0,0.207714) + [0,0.208063) + [0,0.208851) + [0,0.210372) + [0,0.214018) + [0,0.215759) + [0,0.218526) + [0,0.218561) + [0,0.223232) + [0,0.227524) + [0,0.227933) + [0,0.2286) + [0,0.228917) + [0,0.231179) + [0,0.231675) + [0,0.234112) + [0,0.234969) + [0,0.237571) + [0,0.23879) + [0,0.240632) + [0,0.24348) + [0,0.24509) + [0,0.246491) + [0,0.247042) + [0,0.248879) + [0,0.249339) + [0,0.249345) + [0,0.253163) + [0,0.253227) + [0,0.25725) + [0,0.257997) + [0,0.264334) + [0,0.264483) + [0,0.266592) + [0,0.266635) + [0,0.268806) + [0,0.270996) + [0,0.274611) + [0,0.276431) + [0,0.277191) + [0,0.277582) + [0,0.280629) + [0,0.282169) + [0,0.283562) + [0,0.283881) + [0,0.285416) + [0,0.287316) + [0,0.288591) + [0,0.289189) + [0,0.293466) + [0,0.297053) + [0,0.297933) + [0,0.304062) + [0,0.316023) + [0,0.319493) + [0,0.323964) + [0,0.332695) + [0, ) +persistence intervals in dim 1: + [0.542696,0.558863) + [0.531636,0.578093) + [0.530723,0.576869) + [0.463389,0.505345) + [0.445398,0.448892) + [0.443911,0.54761) + [0.431628,0.477277) + [0.413789,0.487379) + [0.412572,0.46308) + [0.411549,0.471715) + [0.409968,0.478461) + [0.386278,0.4922) + [0.381084,0.421374) + [0.377729,0.514046) + [0.377147,0.414788) + [0.377019,0.434385) + [0.374531,0.477153) + [0.370051,0.483155) + [0.361715,0.403181) + [0.354747,0.454956) + [0.352356,0.541947) + [0.350913,0.369543) + [0.35058,0.580726) + [0.347806,0.638039) + [0.347388,0.559978) + [0.344005,0.387193) + [0.34298,0.65758) + [0.339394,0.463666) + [0.33836,0.350411) + [0.33392,0.35111) + [0.33364,0.3797) + [0.331259,0.356381) + [0.329066,0.386148) + [0.324571,0.343083) + [0.324159,0.399094) + [0.322683,0.482958) + [0.318032,0.417462) + [0.317521,0.349622) + [0.316534,0.682559) + [0.309419,0.37151) + [0.309336,0.310216) + [0.308779,0.346297) + [0.304761,0.647803) + [0.301986,0.478334) + [0.301045,0.303943) + [0.29997,0.311993) + [0.298341,0.360737) + [0.279016,0.301331) + [0.2576,0.373749) + [0.253337,0.292286) + [0.24546,0.248903) + [0.240869,0.288747) + [0.189652,0.197515) + 0.02 real 0.02 user 0.00 sys + 2682880 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 674 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 5 voluntary context switches + 4 involuntary context switches diff --git a/benchmarks/sphere_3_192/ripser.dim_2.out.txt b/benchmarks/sphere_3_192/ripser.dim_2.out.txt new file mode 100644 index 0000000..7ba2de6 --- /dev/null +++ b/benchmarks/sphere_3_192/ripser.dim_2.out.txt @@ -0,0 +1,266 @@ +distance matrix with 192 points +value range: [0.00367531,2] +persistence intervals in dim 0: + [0,0.00367531) + [0,0.00391946) + [0,0.0120098) + [0,0.0173134) + [0,0.0217315) + [0,0.0311057) + [0,0.037954) + [0,0.0387451) + [0,0.0433426) + [0,0.0471186) + [0,0.0487061) + [0,0.048826) + [0,0.0496187) + [0,0.0515157) + [0,0.0522132) + [0,0.0559886) + [0,0.0560443) + [0,0.057488) + [0,0.0593071) + [0,0.0623736) + [0,0.0633425) + [0,0.0637053) + [0,0.0651112) + [0,0.0672609) + [0,0.0692368) + [0,0.0702075) + [0,0.0714516) + [0,0.0728647) + [0,0.0741239) + [0,0.0743236) + [0,0.0746054) + [0,0.0753955) + [0,0.076909) + [0,0.0782455) + [0,0.0792212) + [0,0.0800348) + [0,0.0802451) + [0,0.0814685) + [0,0.0831358) + [0,0.0831521) + [0,0.084341) + [0,0.0857401) + [0,0.0870489) + [0,0.0884133) + [0,0.0959033) + [0,0.0970981) + [0,0.0988752) + [0,0.0994522) + [0,0.108768) + [0,0.109526) + [0,0.111131) + [0,0.111798) + [0,0.115939) + [0,0.119187) + [0,0.121955) + [0,0.122089) + [0,0.123527) + [0,0.124774) + [0,0.126595) + [0,0.127383) + [0,0.127864) + [0,0.129741) + [0,0.131438) + [0,0.131638) + [0,0.133033) + [0,0.133525) + [0,0.133722) + [0,0.134886) + [0,0.135402) + [0,0.138674) + [0,0.141823) + [0,0.142152) + [0,0.142537) + [0,0.142834) + [0,0.143085) + [0,0.143151) + [0,0.145018) + [0,0.145725) + [0,0.147203) + [0,0.147289) + [0,0.147427) + [0,0.148506) + [0,0.149017) + [0,0.149226) + [0,0.150747) + [0,0.151643) + [0,0.15244) + [0,0.154095) + [0,0.15587) + [0,0.1569) + [0,0.157251) + [0,0.157293) + [0,0.157373) + [0,0.158413) + [0,0.159282) + [0,0.162464) + [0,0.164809) + [0,0.164815) + [0,0.165202) + [0,0.165314) + [0,0.165494) + [0,0.165592) + [0,0.165907) + [0,0.167455) + [0,0.168587) + [0,0.173412) + [0,0.173586) + [0,0.173684) + [0,0.174172) + [0,0.17493) + [0,0.175016) + [0,0.176306) + [0,0.179609) + [0,0.18428) + [0,0.184757) + [0,0.189106) + [0,0.190642) + [0,0.191661) + [0,0.192356) + [0,0.192406) + [0,0.192733) + [0,0.193791) + [0,0.193804) + [0,0.195722) + [0,0.197377) + [0,0.199673) + [0,0.201961) + [0,0.202564) + [0,0.203812) + [0,0.204208) + [0,0.204544) + [0,0.205389) + [0,0.207016) + [0,0.207261) + [0,0.207714) + [0,0.208063) + [0,0.208851) + [0,0.210372) + [0,0.214018) + [0,0.215759) + [0,0.218526) + [0,0.218561) + [0,0.223232) + [0,0.227524) + [0,0.227933) + [0,0.2286) + [0,0.228917) + [0,0.231179) + [0,0.231675) + [0,0.234112) + [0,0.234969) + [0,0.237571) + [0,0.23879) + [0,0.240632) + [0,0.24348) + [0,0.24509) + [0,0.246491) + [0,0.247042) + [0,0.248879) + [0,0.249339) + [0,0.249345) + [0,0.253163) + [0,0.253227) + [0,0.25725) + [0,0.257997) + [0,0.264334) + [0,0.264483) + [0,0.266592) + [0,0.266635) + [0,0.268806) + [0,0.270996) + [0,0.274611) + [0,0.276431) + [0,0.277191) + [0,0.277582) + [0,0.280629) + [0,0.282169) + [0,0.283562) + [0,0.283881) + [0,0.285416) + [0,0.287316) + [0,0.288591) + [0,0.289189) + [0,0.293466) + [0,0.297053) + [0,0.297933) + [0,0.304062) + [0,0.316023) + [0,0.319493) + [0,0.323964) + [0,0.332695) + [0, ) +persistence intervals in dim 1: + [0.542696,0.558863) + [0.531636,0.578093) + [0.530723,0.576869) + [0.463389,0.505345) + [0.445398,0.448892) + [0.443911,0.54761) + [0.431628,0.477277) + [0.413789,0.487379) + [0.412572,0.46308) + [0.411549,0.471715) + [0.409968,0.478461) + [0.386278,0.4922) + [0.381084,0.421374) + [0.377729,0.514046) + [0.377147,0.414788) + [0.377019,0.434385) + [0.374531,0.477153) + [0.370051,0.483155) + [0.361715,0.403181) + [0.354747,0.454956) + [0.352356,0.541947) + [0.350913,0.369543) + [0.35058,0.580726) + [0.347806,0.638039) + [0.347388,0.559978) + [0.344005,0.387193) + [0.34298,0.65758) + [0.339394,0.463666) + [0.33836,0.350411) + [0.33392,0.35111) + [0.33364,0.3797) + [0.331259,0.356381) + [0.329066,0.386148) + [0.324571,0.343083) + [0.324159,0.399094) + [0.322683,0.482958) + [0.318032,0.417462) + [0.317521,0.349622) + [0.316534,0.682559) + [0.309419,0.37151) + [0.309336,0.310216) + [0.308779,0.346297) + [0.304761,0.647803) + [0.301986,0.478334) + [0.301045,0.303943) + [0.29997,0.311993) + [0.298341,0.360737) + [0.279016,0.301331) + [0.2576,0.373749) + [0.253337,0.292286) + [0.24546,0.248903) + [0.240869,0.288747) + [0.189652,0.197515) +persistence intervals in dim 2: + [0.720484,1.65562) + 1.17 real 1.10 user 0.06 sys + 151293952 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 36957 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 2 voluntary context switches + 49 involuntary context switches diff --git a/benchmarks/sphere_3_192/ripser.out.txt b/benchmarks/sphere_3_192/ripser.out.txt new file mode 100644 index 0000000..bc741ae --- /dev/null +++ b/benchmarks/sphere_3_192/ripser.out.txt @@ -0,0 +1,264 @@ +distance matrix with 192 points +value range: [0.00367531,2] +persistence intervals in dim 0: + [0,0.00367531) + [0,0.00391946) + [0,0.0120098) + [0,0.0173134) + [0,0.0217315) + [0,0.0311057) + [0,0.037954) + [0,0.0387451) + [0,0.0433426) + [0,0.0471186) + [0,0.0487061) + [0,0.048826) + [0,0.0496187) + [0,0.0515157) + [0,0.0522132) + [0,0.0559886) + [0,0.0560443) + [0,0.057488) + [0,0.0593071) + [0,0.0623736) + [0,0.0633425) + [0,0.0637053) + [0,0.0651112) + [0,0.0672609) + [0,0.0692368) + [0,0.0702075) + [0,0.0714516) + [0,0.0728647) + [0,0.0741239) + [0,0.0743236) + [0,0.0746054) + [0,0.0753955) + [0,0.076909) + [0,0.0782455) + [0,0.0792212) + [0,0.0800348) + [0,0.0802451) + [0,0.0814685) + [0,0.0831358) + [0,0.0831521) + [0,0.084341) + [0,0.0857401) + [0,0.0870489) + [0,0.0884133) + [0,0.0959033) + [0,0.0970981) + [0,0.0988752) + [0,0.0994522) + [0,0.108768) + [0,0.109526) + [0,0.111131) + [0,0.111798) + [0,0.115939) + [0,0.119187) + [0,0.121955) + [0,0.122089) + [0,0.123527) + [0,0.124774) + [0,0.126595) + [0,0.127383) + [0,0.127864) + [0,0.129741) + [0,0.131438) + [0,0.131638) + [0,0.133033) + [0,0.133525) + [0,0.133722) + [0,0.134886) + [0,0.135402) + [0,0.138674) + [0,0.141823) + [0,0.142152) + [0,0.142537) + [0,0.142834) + [0,0.143085) + [0,0.143151) + [0,0.145018) + [0,0.145725) + [0,0.147203) + [0,0.147289) + [0,0.147427) + [0,0.148506) + [0,0.149017) + [0,0.149226) + [0,0.150747) + [0,0.151643) + [0,0.15244) + [0,0.154095) + [0,0.15587) + [0,0.1569) + [0,0.157251) + [0,0.157293) + [0,0.157373) + [0,0.158413) + [0,0.159282) + [0,0.162464) + [0,0.164809) + [0,0.164815) + [0,0.165202) + [0,0.165314) + [0,0.165494) + [0,0.165592) + [0,0.165907) + [0,0.167455) + [0,0.168587) + [0,0.173412) + [0,0.173586) + [0,0.173684) + [0,0.174172) + [0,0.17493) + [0,0.175016) + [0,0.176306) + [0,0.179609) + [0,0.18428) + [0,0.184757) + [0,0.189106) + [0,0.190642) + [0,0.191661) + [0,0.192356) + [0,0.192406) + [0,0.192733) + [0,0.193791) + [0,0.193804) + [0,0.195722) + [0,0.197377) + [0,0.199673) + [0,0.201961) + [0,0.202564) + [0,0.203812) + [0,0.204208) + [0,0.204544) + [0,0.205389) + [0,0.207016) + [0,0.207261) + [0,0.207714) + [0,0.208063) + [0,0.208851) + [0,0.210372) + [0,0.214018) + [0,0.215759) + [0,0.218526) + [0,0.218561) + [0,0.223232) + [0,0.227524) + [0,0.227933) + [0,0.2286) + [0,0.228917) + [0,0.231179) + [0,0.231675) + [0,0.234112) + [0,0.234969) + [0,0.237571) + [0,0.23879) + [0,0.240632) + [0,0.24348) + [0,0.24509) + [0,0.246491) + [0,0.247042) + [0,0.248879) + [0,0.249339) + [0,0.249345) + [0,0.253163) + [0,0.253227) + [0,0.25725) + [0,0.257997) + [0,0.264334) + [0,0.264483) + [0,0.266592) + [0,0.266635) + [0,0.268806) + [0,0.270996) + [0,0.274611) + [0,0.276431) + [0,0.277191) + [0,0.277582) + [0,0.280629) + [0,0.282169) + [0,0.283562) + [0,0.283881) + [0,0.285416) + [0,0.287316) + [0,0.288591) + [0,0.289189) + [0,0.293466) + [0,0.297053) + [0,0.297933) + [0,0.304062) + [0,0.316023) + [0,0.319493) + [0,0.323964) + [0,0.332695) + [0, ) +persistence intervals in dim 1: + [0.542696,0.558863) + [0.531636,0.578093) + [0.530723,0.576869) + [0.463389,0.505345) + [0.445398,0.448892) + [0.443911,0.54761) + [0.431628,0.477277) + [0.413789,0.487379) + [0.412572,0.46308) + [0.411549,0.471715) + [0.409968,0.478461) + [0.386278,0.4922) + [0.381084,0.421374) + [0.377729,0.514046) + [0.377147,0.414788) + [0.377019,0.434385) + [0.374531,0.477153) + [0.370051,0.483155) + [0.361715,0.403181) + [0.354747,0.454956) + [0.352356,0.541947) + [0.350913,0.369543) + [0.35058,0.580726) + [0.347806,0.638039) + [0.347388,0.559978) + [0.344005,0.387193) + [0.34298,0.65758) + [0.339394,0.463666) + [0.33836,0.350411) + [0.33392,0.35111) + [0.33364,0.3797) + [0.331259,0.356381) + [0.329066,0.386148) + [0.324571,0.343083) + [0.324159,0.399094) + [0.322683,0.482958) + [0.318032,0.417462) + [0.317521,0.349622) + [0.316534,0.682559) + [0.309419,0.37151) + [0.309336,0.310216) + [0.308779,0.346297) + [0.304761,0.647803) + [0.301986,0.478334) + [0.301045,0.303943) + [0.29997,0.311993) + [0.298341,0.360737) + [0.279016,0.301331) + [0.2576,0.373749) + [0.253337,0.292286) + [0.24546,0.248903) + [0.240869,0.288747) + [0.189652,0.197515) + 0.03 real 0.03 user 0.00 sys + 3276800 maximum resident set size + 0 average shared memory size + 0 average unshared data size + 0 average unshared stack size + 819 page reclaims + 0 page faults + 0 swaps + 0 block input operations + 0 block output operations + 0 messages sent + 0 messages received + 0 signals received + 7 voluntary context switches + 119 involuntary context switches diff --git a/benchmarks/sphere_3_192/run_benchmarks.sh b/benchmarks/sphere_3_192/run_benchmarks.sh new file mode 100644 index 0000000..14cac6c --- /dev/null +++ b/benchmarks/sphere_3_192/run_benchmarks.sh @@ -0,0 +1,4 @@ +. run_dionysus.sh +. run_dipha.sh +. run_gudhi.sh +. run_ripser.sh diff --git a/benchmarks/sphere_3_192/run_dionysus.sh b/benchmarks/sphere_3_192/run_dionysus.sh new file mode 100644 index 0000000..7af804f --- /dev/null +++ b/benchmarks/sphere_3_192/run_dionysus.sh @@ -0,0 +1,3 @@ +/usr/bin/time -l ~/Source/Dionysus/examples/cohomology/rips-pairwise-cohomology -s2 -p2 ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2>&1 | tee dionysus.dim_1.out.txt +/usr/bin/time -l ~/Source/Dionysus/examples/cohomology/rips-pairwise-cohomology -s3 -p2 ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2>&1 | tee dionysus.dim_2.out.txt + diff --git a/benchmarks/sphere_3_192/run_dipha.sh b/benchmarks/sphere_3_192/run_dipha.sh new file mode 100644 index 0000000..b700a1a --- /dev/null +++ b/benchmarks/sphere_3_192/run_dipha.sh @@ -0,0 +1,3 @@ +/usr/bin/time -l ~/Bitbucket/dipha/dipha --benchmark --upper_dim 2 --dual ~/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex /dev/null 2>&1 | tee dipha.dim_1.out.txt +/usr/bin/time -l ~/Bitbucket/dipha/dipha --benchmark --upper_dim 3 --dual ~/Bitbucket/phat-paper/benchmark/dipha/sphere_3_192.complex /dev/null 2>&1 | tee dipha.dim_2.out.txt + diff --git a/benchmarks/sphere_3_192/run_gudhi.sh b/benchmarks/sphere_3_192/run_gudhi.sh new file mode 100644 index 0000000..7e39da9 --- /dev/null +++ b/benchmarks/sphere_3_192/run_gudhi.sh @@ -0,0 +1,3 @@ +/usr/bin/time -l ~/Source/Gudhi_library_1.3.1/example/Persistent_cohomology/rips_persistence -d2 -p2 ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2>&1 | tee gudhi.dim_1.out.txt +/usr/bin/time -l ~/Source/Gudhi_library_1.3.1/example/Persistent_cohomology/rips_persistence -d3 -p2 ~/Bitbucket/phat-paper/benchmark/point\ cloud/sphere_3_192_points.dat 2>&1 | tee gudhi.dim_2.out.txt + diff --git a/benchmarks/sphere_3_192/run_ripser.sh b/benchmarks/sphere_3_192/run_ripser.sh new file mode 100644 index 0000000..4cc1c3d --- /dev/null +++ b/benchmarks/sphere_3_192/run_ripser.sh @@ -0,0 +1,3 @@ +/usr/bin/time -l ~/Bitbucket/ripser/ripser ~/Bitbucket/ripser/examples/sphere_3_192.lower_distance_matrix 2>&1 | tee ripser.dim_1.out.txt +/usr/bin/time -l ~/Bitbucket/ripser/ripser ~/Bitbucket/ripser/examples/sphere_3_192.lower_distance_matrix --dim 2 2>&1 | tee ripser.dim_2.out.txt + @@ -50,35 +50,26 @@ template <class Key, class T> class hash_map : public std::unordered_map<Key, T> #endif typedef float value_t; -// typedef uint16_t value_t; - typedef int64_t index_t; typedef int16_t coefficient_t; class binomial_coeff_table { std::vector<std::vector<index_t>> B; - index_t n_max, k_max; public: - binomial_coeff_table(index_t n, index_t k) { - n_max = n; - k_max = k; - - B.resize(n + 1); + binomial_coeff_table(index_t n, index_t k) : B(n + 1) { for (index_t i = 0; i <= n; i++) { B[i].resize(k + 1); - for (index_t j = 0; j <= std::min(i, k); j++) { + for (index_t j = 0; j <= std::min(i, k); j++) if (j == 0 || j == i) B[i][j] = 1; else B[i][j] = B[i - 1][j - 1] + B[i - 1][j]; - } } } index_t operator()(index_t n, index_t k) const { - assert(n <= n_max); - assert(k <= k_max); + assert(n < B.size() && k < B[n].size()); return B[n][k]; } }; @@ -104,56 +95,23 @@ std::vector<coefficient_t> multiplicative_inverse_vector(const coefficient_t m) return inverse; } -template <typename OutputIterator> -OutputIterator get_simplex_vertices(index_t idx, const index_t dim, index_t n, - const binomial_coeff_table& binomial_coeff, OutputIterator out) { - --n; - - for (index_t k = dim + 1; k > 0; --k) { - if (binomial_coeff(n, k) > idx) { - index_t count = n; - while (count > 0) { - index_t i = n; - index_t step = count >> 1; - i -= step; - if (binomial_coeff(i, k) > idx) { - n = --i; - count -= step + 1; - } else - count = step; - } - } - assert(binomial_coeff(n, k) <= idx); - assert(binomial_coeff(n + 1, k) > idx); - - *out++ = n; - idx -= binomial_coeff(n, k); - } - - return out; -} - -std::vector<index_t> vertices_of_simplex(const index_t simplex_index, const index_t dim, const index_t n, - const binomial_coeff_table& binomial_coeff) { - std::vector<index_t> vertices; - get_simplex_vertices(simplex_index, dim, n, binomial_coeff, std::back_inserter(vertices)); - return vertices; -} - #ifdef USE_COEFFICIENTS -struct entry_t { +struct __attribute__((packed)) entry_t { index_t index : 8 * (sizeof(index_t) - sizeof(coefficient_t)); coefficient_t coefficient; - entry_t(index_t _index, coefficient_t _coefficient) : index(_index), coefficient(_coefficient) {} + entry_t(index_t _index, coefficient_t _coefficient) + : index(_index), coefficient(_coefficient) {} entry_t(index_t _index) : index(_index), coefficient(1) {} entry_t() : index(0), coefficient(1) {} -} __attribute__((packed)); +}; static_assert(sizeof(entry_t) == sizeof(index_t), "size of entry_t is not the same as index_t"); -entry_t make_entry(index_t _index, coefficient_t _coefficient) { return entry_t(_index, _coefficient); } -index_t get_index(entry_t e) { return e.index; } -index_t get_coefficient(entry_t e) { return e.coefficient; } +entry_t make_entry(index_t _index, coefficient_t _coefficient) { + return entry_t(_index, _coefficient); +} +index_t get_index(const entry_t& e) { return e.index; } +index_t get_coefficient(const entry_t& e) { return e.coefficient; } void set_coefficient(entry_t& e, const coefficient_t c) { e.coefficient = c; } bool operator==(const entry_t& e1, const entry_t& e2) { @@ -168,41 +126,45 @@ std::ostream& operator<<(std::ostream& stream, const entry_t& e) { #else typedef index_t entry_t; -const index_t get_index(entry_t i) { return i; } -index_t get_coefficient(entry_t i) { return 1; } +const index_t get_index(const entry_t& i) { return i; } +index_t get_coefficient(const entry_t& i) { return 1; } entry_t make_entry(index_t _index, coefficient_t _value) { return entry_t(_index); } -void set_coefficient(index_t& e, const coefficient_t c) { e = c; } +void set_coefficient(entry_t& e, const coefficient_t c) {} #endif const entry_t& get_entry(const entry_t& e) { return e; } -template <typename Entry> struct smaller_index { - bool operator()(const Entry& a, const Entry& b) { return get_index(a) < get_index(b); } +class diameter_index_t : public std::pair<value_t, index_t> { +public: + diameter_index_t() : std::pair<value_t, index_t>() {} + diameter_index_t(std::pair<value_t, index_t>&& p) : std::pair<value_t, index_t>(std::move(p)) {} }; - -typedef std::pair<value_t, index_t> diameter_index_t; -value_t get_diameter(diameter_index_t i) { return i.first; } -index_t get_index(diameter_index_t i) { return i.second; } +value_t get_diameter(const diameter_index_t& i) { return i.first; } +index_t get_index(const diameter_index_t& i) { return i.second; } class diameter_entry_t : public std::pair<value_t, entry_t> { public: diameter_entry_t(std::pair<value_t, entry_t> p) : std::pair<value_t, entry_t>(p) {} - diameter_entry_t(entry_t e) : std::pair<value_t, entry_t>(0, e) {} - diameter_entry_t() : diameter_entry_t(0) {} + diameter_entry_t(entry_t&& e) : std::pair<value_t, entry_t>(0, std::move(e)) {} + diameter_entry_t() : diameter_entry_t(entry_t()) {} + diameter_entry_t(value_t _diameter, index_t _index, coefficient_t _coefficient) + : std::pair<value_t, entry_t>(_diameter, make_entry(_index, _coefficient)) {} + diameter_entry_t(const diameter_index_t& _diameter_index, coefficient_t _coefficient) + : std::pair<value_t, entry_t>(get_diameter(_diameter_index), + make_entry(get_index(_diameter_index), _coefficient)) {} + diameter_entry_t(const diameter_index_t& _diameter_index) : diameter_entry_t(_diameter_index, 1) {} }; const entry_t& get_entry(const diameter_entry_t& p) { return p.second; } entry_t& get_entry(diameter_entry_t& p) { return p.second; } const index_t get_index(const diameter_entry_t& p) { return get_index(get_entry(p)); } -const coefficient_t get_coefficient(const diameter_entry_t& p) { return get_coefficient(get_entry(p)); } -const value_t& get_diameter(const diameter_entry_t& p) { return p.first; } -void set_coefficient(diameter_entry_t& p, const coefficient_t c) { set_coefficient(get_entry(p), c); } -diameter_entry_t make_diameter_entry(value_t _diameter, index_t _index, coefficient_t _coefficient) { - return std::make_pair(_diameter, make_entry(_index, _coefficient)); +const coefficient_t get_coefficient(const diameter_entry_t& p) { + return get_coefficient(get_entry(p)); } -diameter_entry_t make_diameter_entry(diameter_index_t _diameter_index, coefficient_t _coefficient) { - return std::make_pair(get_diameter(_diameter_index), make_entry(get_index(_diameter_index), _coefficient)); +const value_t& get_diameter(const diameter_entry_t& p) { return p.first; } +void set_coefficient(diameter_entry_t& p, const coefficient_t c) { + set_coefficient(get_entry(p), c); } template <typename Entry> struct greater_diameter_or_smaller_index { @@ -212,70 +174,6 @@ template <typename Entry> struct greater_diameter_or_smaller_index { } }; -template <typename DistanceMatrix> class rips_filtration_comparator { -public: - const DistanceMatrix& dist; - const index_t dim; - -private: - mutable std::vector<index_t> vertices; - const binomial_coeff_table& binomial_coeff; - -public: - rips_filtration_comparator(const DistanceMatrix& _dist, const index_t _dim, - const binomial_coeff_table& _binomial_coeff) - : dist(_dist), dim(_dim), vertices(_dim + 1), binomial_coeff(_binomial_coeff){}; - - value_t diameter(const index_t index) const { - value_t diam = 0; - get_simplex_vertices(index, dim, dist.size(), binomial_coeff, vertices.begin()); - - for (index_t i = 0; i <= dim; ++i) - for (index_t j = 0; j < i; ++j) { diam = std::max(diam, dist(vertices[i], vertices[j])); } - return diam; - } - - bool operator()(const index_t a, const index_t b) const { - assert(a < binomial_coeff(dist.size(), dim + 1)); - assert(b < binomial_coeff(dist.size(), dim + 1)); - - return greater_diameter_or_smaller_index<diameter_index_t>()(diameter_index_t(diameter(a), a), - diameter_index_t(diameter(b), b)); - } - - template <typename Entry> bool operator()(const Entry& a, const Entry& b) const { - return operator()(get_index(a), get_index(b)); - } -}; - -class simplex_coboundary_enumerator { -private: - index_t idx_below, idx_above, v, k; - const binomial_coeff_table& binomial_coeff; - -public: - simplex_coboundary_enumerator(index_t _idx, index_t _dim, index_t _n, const binomial_coeff_table& _binomial_coeff) - : idx_below(_idx), idx_above(0), v(_n - 1), k(_dim + 1), binomial_coeff(_binomial_coeff) {} - - bool has_next() { - while ((v != -1) && (binomial_coeff(v, k) <= idx_below)) { - idx_below -= binomial_coeff(v, k); - idx_above += binomial_coeff(v, k + 1); - - --v; - --k; - assert(k != -1); - } - return v != -1; - } - - std::pair<entry_t, index_t> next() { - auto result = std::make_pair(make_entry(idx_above + binomial_coeff(v, k + 1) + idx_below, k & 1 ? -1 : 1), v); - --v; - return result; - } -}; - enum compressed_matrix_layout { LOWER_TRIANGULAR, UPPER_TRIANGULAR }; template <compressed_matrix_layout Layout> class compressed_distance_matrix { @@ -286,7 +184,7 @@ public: void init_rows(); compressed_distance_matrix(std::vector<value_t>&& _distances) - : distances(_distances), rows((1 + std::sqrt(1 + 8 * distances.size())) / 2) { + : distances(std::move(_distances)), rows((1 + std::sqrt(1 + 8 * distances.size())) / 2) { assert(distances.size() == size() * (size() - 1) / 2); init_rows(); } @@ -321,14 +219,14 @@ template <> void compressed_distance_matrix<UPPER_TRIANGULAR>::init_rows() { } } -template <> value_t compressed_distance_matrix<UPPER_TRIANGULAR>::operator()(index_t i, index_t j) const { - if (i > j) std::swap(i, j); - return i == j ? 0 : rows[i][j]; +template <> +value_t compressed_distance_matrix<UPPER_TRIANGULAR>::operator()(index_t i, index_t j) const { + return i == j ? 0 : i > j ? rows[j][i] : rows[i][j]; } -template <> value_t compressed_distance_matrix<LOWER_TRIANGULAR>::operator()(index_t i, index_t j) const { - if (i > j) std::swap(i, j); - return i == j ? 0 : rows[j][i]; +template <> +value_t compressed_distance_matrix<LOWER_TRIANGULAR>::operator()(index_t i, index_t j) const { + return i == j ? 0 : i < j ? rows[j][i] : rows[i][j]; } typedef compressed_distance_matrix<LOWER_TRIANGULAR> compressed_lower_distance_matrix; @@ -338,12 +236,19 @@ class euclidean_distance_matrix { public: std::vector<std::vector<value_t>> points; - euclidean_distance_matrix(std::vector<std::vector<value_t>>&& _points) : points(_points) {} + euclidean_distance_matrix(std::vector<std::vector<value_t>>&& _points) + : points(std::move(_points)) { + for (auto p: points) { + assert(p.size() == points.front().size()); + } + } value_t operator()(const index_t i, const index_t j) const { - return std::sqrt(std::inner_product(points[i].begin(), points[i].end(), points[j].begin(), value_t(), - std::plus<value_t>(), - [](value_t u, value_t v) { return (u - v) * (u - v); })); + assert(i < points.size()); + assert(j < points.size()); + return std::sqrt(std::inner_product( + points[i].begin(), points[i].end(), points[j].begin(), value_t(), std::plus<value_t>(), + [](value_t u, value_t v) { return (u - v) * (u - v); })); } size_t size() const { return points.size(); } @@ -468,176 +373,270 @@ public: } }; -template <typename Heap> void push_entry(Heap& column, index_t i, coefficient_t c, value_t diameter) { +template <typename Heap> +void push_entry(Heap& column, index_t i, coefficient_t c, value_t diameter) { entry_t e = make_entry(i, c); column.push(std::make_pair(diameter, e)); } -template <typename Comparator> -void assemble_columns_to_reduce(std::vector<diameter_index_t>& columns_to_reduce, - hash_map<index_t, index_t>& pivot_column_index, const Comparator& comp, index_t dim, - index_t n, value_t threshold, const binomial_coeff_table& binomial_coeff) { - index_t num_simplices = binomial_coeff(n, dim + 2); +class ripser { + compressed_lower_distance_matrix dist; + index_t dim_max, n; + value_t threshold; + coefficient_t modulus; + const binomial_coeff_table binomial_coeff; + std::vector<coefficient_t> multiplicative_inverse; + mutable std::vector<index_t> vertices; - columns_to_reduce.clear(); +public: + ripser(compressed_lower_distance_matrix&& _dist, index_t _dim_max, value_t _threshold, + coefficient_t _modulus) + : dist(std::move(_dist)), dim_max(std::min(_dim_max, index_t(dist.size() - 2))), + n(dist.size()), threshold(_threshold), modulus(_modulus), binomial_coeff(n, dim_max + 2), + multiplicative_inverse(multiplicative_inverse_vector(_modulus)) {} + + index_t get_next_vertex(index_t& v, const index_t idx, const index_t k) const { + if (binomial_coeff(v, k) > idx) { + index_t count = v; + while (count > 0) { + index_t i = v; + index_t step = count >> 1; + i -= step; + if (binomial_coeff(i, k) > idx) { + v = --i; + count -= step + 1; + } else + count = step; + } + } + assert(binomial_coeff(v, k) <= idx && binomial_coeff(v + 1, k) > idx); + return v; + } + + template <typename OutputIterator> + OutputIterator get_simplex_vertices(index_t idx, const index_t dim, index_t v, + OutputIterator out) const { + --v; + for (index_t k = dim + 1; k > 0; --k) { + get_next_vertex(v, idx, k); + *out++ = v; + idx -= binomial_coeff(v, k); + } + return out; + } + + value_t compute_diameter(const index_t index, index_t dim) const { + value_t diam = -std::numeric_limits<value_t>::infinity(); + + vertices.clear(); + get_simplex_vertices(index, dim, dist.size(), std::back_inserter(vertices)); + + for (index_t i = 0; i <= dim; ++i) + for (index_t j = 0; j < i; ++j) { + diam = std::max(diam, dist(vertices[i], vertices[j])); + } + return diam; + } + + class simplex_coboundary_enumerator { + private: + index_t idx_below, idx_above, v, k; + std::vector<index_t> vertices; + const diameter_entry_t simplex; + const coefficient_t modulus; + const compressed_lower_distance_matrix& dist; + const binomial_coeff_table& binomial_coeff; + + public: + simplex_coboundary_enumerator(const diameter_entry_t _simplex, index_t _dim, + const ripser& parent) + : idx_below(get_index(_simplex)), idx_above(0), v(parent.n - 1), k(_dim + 1), + vertices(_dim + 1), simplex(_simplex), modulus(parent.modulus), dist(parent.dist), + binomial_coeff(parent.binomial_coeff) { + parent.get_simplex_vertices(get_index(_simplex), _dim, parent.n, vertices.begin()); + } + + bool has_next() { + while ((v != -1) && (binomial_coeff(v, k) <= idx_below)) { + idx_below -= binomial_coeff(v, k); + idx_above += binomial_coeff(v, k + 1); + --v; + --k; + assert(k != -1); + } + return v != -1; + } + + diameter_entry_t next() { + value_t coface_diameter = get_diameter(simplex); + for (index_t w : vertices) coface_diameter = std::max(coface_diameter, dist(v, w)); + index_t coface_index = idx_above + binomial_coeff(v--, k + 1) + idx_below; + coefficient_t coface_coefficient = + (k & 1 ? -1 + modulus : 1) * get_coefficient(simplex) % modulus; + return diameter_entry_t(coface_diameter, coface_index, coface_coefficient); + } + }; + + void compute_barcodes(); + + void assemble_columns_to_reduce(std::vector<diameter_index_t>& columns_to_reduce, + hash_map<index_t, index_t>& pivot_column_index, index_t dim) { + index_t num_simplices = binomial_coeff(n, dim + 1); + + columns_to_reduce.clear(); #ifdef INDICATE_PROGRESS - std::cout << "\033[K" - << "assembling " << num_simplices << " columns" << std::flush << "\r"; + std::cout << "\033[K" + << "assembling " << num_simplices << " columns" << std::flush << "\r"; #endif - for (index_t index = 0; index < num_simplices; ++index) { - if (pivot_column_index.find(index) == pivot_column_index.end()) { - value_t diameter = comp.diameter(index); - if (diameter <= threshold) columns_to_reduce.push_back(std::make_pair(diameter, index)); + for (index_t index = 0; index < num_simplices; ++index) { + if (pivot_column_index.find(index) == pivot_column_index.end()) { + value_t diameter = compute_diameter(index, dim); + if (diameter <= threshold) + columns_to_reduce.push_back(std::make_pair(diameter, index)); +#ifdef INDICATE_PROGRESS + if ((index + 1) % 1000000 == 0) + std::cout << "\033[K" + << "assembled " << columns_to_reduce.size() << " out of " + << (index + 1) << "/" << num_simplices << " columns" << std::flush + << "\r"; +#endif + } } - } #ifdef INDICATE_PROGRESS - std::cout << "\033[K" - << "sorting " << num_simplices << " columns" << std::flush << "\r"; + std::cout << "\033[K" + << "sorting " << num_simplices << " columns" << std::flush << "\r"; #endif - std::sort(columns_to_reduce.begin(), columns_to_reduce.end(), - greater_diameter_or_smaller_index<diameter_index_t>()); + std::sort(columns_to_reduce.begin(), columns_to_reduce.end(), + greater_diameter_or_smaller_index<diameter_index_t>()); #ifdef INDICATE_PROGRESS - std::cout << "\033[K"; + std::cout << "\033[K"; #endif -} + } -template <typename DistanceMatrix, typename ComparatorCofaces, typename Comparator> -void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, hash_map<index_t, index_t>& pivot_column_index, - const DistanceMatrix& dist, const ComparatorCofaces& comp, const Comparator& comp_prev, index_t dim, - index_t n, value_t threshold, coefficient_t modulus, - const std::vector<coefficient_t>& multiplicative_inverse, - const binomial_coeff_table& binomial_coeff) { + void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, + hash_map<index_t, index_t>& pivot_column_index, index_t dim) { #ifdef PRINT_PERSISTENCE_PAIRS - std::cout << "persistence intervals in dim " << dim << ":" << std::endl; + std::cout << "persistence intervals in dim " << dim << ":" << std::endl; #endif #ifdef ASSEMBLE_REDUCTION_MATRIX - compressed_sparse_matrix<diameter_entry_t> reduction_matrix; + compressed_sparse_matrix<diameter_entry_t> reduction_coefficients; #else #ifdef USE_COEFFICIENTS - std::vector<diameter_entry_t> reduction_coefficients; + std::vector<diameter_entry_t> reduction_coefficients; #endif #endif - std::vector<diameter_entry_t> coface_entries; - std::vector<index_t> vertices; + std::vector<diameter_entry_t> coface_entries; - for (index_t i = 0; i < columns_to_reduce.size(); ++i) { - auto column_to_reduce = columns_to_reduce[i]; + for (index_t i = 0; i < columns_to_reduce.size(); ++i) { + auto column_to_reduce = columns_to_reduce[i]; #ifdef ASSEMBLE_REDUCTION_MATRIX - std::priority_queue<diameter_entry_t, std::vector<diameter_entry_t>, smaller_index<diameter_entry_t>> - reduction_column; + std::priority_queue<diameter_entry_t, std::vector<diameter_entry_t>, + greater_diameter_or_smaller_index<diameter_entry_t>> + reduction_column; #endif - std::priority_queue<diameter_entry_t, std::vector<diameter_entry_t>, - greater_diameter_or_smaller_index<diameter_entry_t>> - working_coboundary; + std::priority_queue<diameter_entry_t, std::vector<diameter_entry_t>, + greater_diameter_or_smaller_index<diameter_entry_t>> + working_coboundary; - value_t diameter = get_diameter(column_to_reduce); + value_t diameter = get_diameter(column_to_reduce); #ifdef INDICATE_PROGRESS - if ((i + 1) % 1000 == 0) - std::cout << "\033[K" - << "reducing column " << i + 1 << "/" << columns_to_reduce.size() << " (diameter " << diameter - << ")" << std::flush << "\r"; + if ((i + 1) % 1000000 == 0) + std::cout << "\033[K" + << "reducing column " << i + 1 << "/" << columns_to_reduce.size() + << " (diameter " << diameter << ")" << std::flush << "\r"; #endif - index_t j = i; + index_t j = i; - // start with a dummy pivot entry with coefficient -1 in order to initialize - // working_coboundary with the coboundary of the simplex with index column_to_reduce - diameter_entry_t pivot = make_diameter_entry(0, -1, -1 + modulus); + // start with a dummy pivot entry with coefficient -1 in order to initialize + // working_coboundary with the coboundary of the simplex with index column_to_reduce + diameter_entry_t pivot(0, -1, -1 + modulus); #ifdef ASSEMBLE_REDUCTION_MATRIX - // initialize reduction_matrix as identity matrix - reduction_matrix.append_column(); - reduction_matrix.push_back(make_diameter_entry(column_to_reduce, 1)); -#else -#ifdef USE_COEFFICIENTS - reduction_coefficients.push_back(make_diameter_entry(column_to_reduce, 1)); + // initialize reduction_coefficients as identity matrix + reduction_coefficients.append_column(); #endif +#ifdef USE_COEFFICIENTS + reduction_coefficients.push_back(diameter_entry_t(column_to_reduce, 1)); #endif - bool might_be_apparent_pair = (i == j); + bool might_be_apparent_pair = (i == j); - do { - const coefficient_t factor = modulus - get_coefficient(pivot); + do { + const coefficient_t factor = modulus - get_coefficient(pivot); #ifdef ASSEMBLE_REDUCTION_MATRIX - for (auto it = reduction_matrix.cbegin(j); it != reduction_matrix.cend(j); ++it) +#ifdef USE_COEFFICIENTS + auto coeffs_begin = reduction_coefficients.cbegin(j), + coeffs_end = reduction_coefficients.cend(j); +#else + std::vector<diameter_entry_t> coeffs; + coeffs.push_back(columns_to_reduce[j]); + for (auto it = reduction_coefficients.cbegin(j); + it != reduction_coefficients.cend(j); ++it) + coeffs.push_back(*it); + auto coeffs_begin = coeffs.begin(), coeffs_end = coeffs.end(); #endif - { -#ifdef ASSEMBLE_REDUCTION_MATRIX - const auto& simplex = *it; #else #ifdef USE_COEFFICIENTS - const auto& simplex = reduction_coefficients[j]; + auto coeffs_begin = &reduction_coefficients[j], + coeffs_end = &reduction_coefficients[j] + 1; #else - const auto& simplex = columns_to_reduce[j]; + auto coeffs_begin = &columns_to_reduce[j], coeffs_end = &columns_to_reduce[j] + 1; #endif #endif - coefficient_t simplex_coefficient = get_coefficient(simplex) * factor % modulus; + for (auto it = coeffs_begin; it != coeffs_end; ++it) { + diameter_entry_t simplex = *it; + set_coefficient(simplex, get_coefficient(simplex) * factor % modulus); #ifdef ASSEMBLE_REDUCTION_MATRIX - reduction_column.push( - make_diameter_entry(get_diameter(simplex), get_index(simplex), simplex_coefficient)); -#endif - - vertices.clear(); - get_simplex_vertices(get_index(simplex), dim, n, binomial_coeff, std::back_inserter(vertices)); - - coface_entries.clear(); - simplex_coboundary_enumerator cofaces(get_index(simplex), dim, n, binomial_coeff); - while (cofaces.has_next()) { - auto coface_descriptor = cofaces.next(); - entry_t coface = coface_descriptor.first; - index_t covertex = coface_descriptor.second; - index_t coface_index = get_index(coface); - value_t coface_diameter = get_diameter(simplex); - for (index_t v : vertices) { coface_diameter = std::max(coface_diameter, dist(v, covertex)); } - assert(comp.diameter(coface_index) == coface_diameter); - - if (coface_diameter <= threshold) { - coefficient_t coface_coefficient = - (get_coefficient(coface) + modulus) * simplex_coefficient % modulus; - assert(coface_coefficient >= 0); - - diameter_entry_t coface_entry = - make_diameter_entry(coface_diameter, coface_index, coface_coefficient); - coface_entries.push_back(coface_entry); - - if (might_be_apparent_pair && (get_diameter(simplex) == coface_diameter)) { - if (pivot_column_index.find(coface_index) == pivot_column_index.end()) { - pivot = coface_entry; - goto found_persistence_pair; + reduction_column.push(simplex); +#endif + + coface_entries.clear(); + simplex_coboundary_enumerator cofaces(simplex, dim, *this); + while (cofaces.has_next()) { + diameter_entry_t coface = cofaces.next(); + if (get_diameter(coface) <= threshold) { + coface_entries.push_back(coface); + if (might_be_apparent_pair && + (get_diameter(simplex) == get_diameter(coface))) { + if (pivot_column_index.find(get_index(coface)) == + pivot_column_index.end()) { + pivot = coface; + goto found_persistence_pair; + } + might_be_apparent_pair = false; } - might_be_apparent_pair = false; } } + for (auto coface : coface_entries) working_coboundary.push(coface); } - for (auto e : coface_entries) working_coboundary.push(e); - } - pivot = get_pivot(working_coboundary, modulus); + pivot = get_pivot(working_coboundary, modulus); - if (get_index(pivot) != -1) { - auto pair = pivot_column_index.find(get_index(pivot)); + if (get_index(pivot) != -1) { + auto pair = pivot_column_index.find(get_index(pivot)); - if (pair != pivot_column_index.end()) { - j = pair->second; - continue; - } - } else { + if (pair != pivot_column_index.end()) { + j = pair->second; + continue; + } + } else { #ifdef PRINT_PERSISTENCE_PAIRS #ifdef INDICATE_PROGRESS - std::cout << "\033[K"; + std::cout << "\033[K"; #endif // std::cout << " [" << diameter << ", )" << std::endl << std::flush; std::cout << " [" << diameter << ", ): {"; @@ -650,15 +649,15 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, hash_map<in } std::cout << "}" << std::endl; #endif - break; - } + break; + } - found_persistence_pair: + found_persistence_pair: #ifdef PRINT_PERSISTENCE_PAIRS - value_t death = get_diameter(pivot); - if (diameter != death) { + value_t death = get_diameter(pivot); + if (diameter != death) { #ifdef INDICATE_PROGRESS - std::cout << "\033[K"; + std::cout << "\033[K"; #endif // std::cout << " [" << diameter << "," << death << ")" << std::endl << std::flush; std::cout << " [" << diameter << "," << death << "): {"; @@ -673,44 +672,54 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, hash_map<in } #endif - pivot_column_index.insert(std::make_pair(get_index(pivot), i)); + pivot_column_index.insert(std::make_pair(get_index(pivot), i)); #ifdef USE_COEFFICIENTS - const coefficient_t inverse = multiplicative_inverse[get_coefficient(pivot)]; + const coefficient_t inverse = multiplicative_inverse[get_coefficient(pivot)]; #endif #ifdef ASSEMBLE_REDUCTION_MATRIX - // replace current column of reduction_matrix (with a single diagonal 1 entry) - // by reduction_column (possibly with a different entry on the diagonal) - reduction_matrix.pop_back(); - while (true) { - diameter_entry_t e = pop_pivot(reduction_column, modulus); - index_t index = get_index(e); - if (index == -1) break; +// replace current column of reduction_coefficients (with a single diagonal 1 entry) +// by reduction_column (possibly with a different entry on the diagonal) #ifdef USE_COEFFICIENTS - const coefficient_t coefficient = inverse * get_coefficient(e) % modulus; - assert(coefficient > 0); + reduction_coefficients.pop_back(); #else - const coefficient_t coefficient = 1; + pop_pivot(reduction_column, modulus); #endif - reduction_matrix.push_back(make_diameter_entry(get_diameter(e), index, coefficient)); - } + + while (true) { + diameter_entry_t e = pop_pivot(reduction_column, modulus); + if (get_index(e) == -1) break; +#ifdef USE_COEFFICIENTS + set_coefficient(e, inverse * get_coefficient(e) % modulus); + assert(get_coefficient(e) > 0); +#endif + reduction_coefficients.push_back(e); + } #else #ifdef USE_COEFFICIENTS - reduction_coefficients.pop_back(); - reduction_coefficients.push_back(make_diameter_entry(column_to_reduce, inverse)); + reduction_coefficients.pop_back(); + reduction_coefficients.push_back(diameter_entry_t(column_to_reduce, inverse)); #endif #endif - break; - } while (true); - } + break; + } while (true); + } #ifdef INDICATE_PROGRESS - std::cout << "\033[K"; + std::cout << "\033[K"; #endif -} + } +}; -enum file_format { LOWER_DISTANCE_MATRIX, UPPER_DISTANCE_MATRIX, DISTANCE_MATRIX, POINT_CLOUD, DIPHA }; +enum file_format { + LOWER_DISTANCE_MATRIX, + UPPER_DISTANCE_MATRIX, + DISTANCE_MATRIX, + POINT_CLOUD, + DIPHA, + RIPSER +}; template <typename T> T read(std::istream& s) { T result; @@ -738,7 +747,8 @@ compressed_lower_distance_matrix read_point_cloud(std::istream& input_stream) { index_t n = eucl_dist.size(); - std::cout << "point cloud with " << n << " points in dimension " << eucl_dist.points.front().size() << std::endl; + std::cout << "point cloud with " << n << " points in dimension " + << eucl_dist.points.front().size() << std::endl; std::vector<value_t> distances; @@ -811,6 +821,12 @@ compressed_lower_distance_matrix read_dipha(std::istream& input_stream) { return compressed_lower_distance_matrix(std::move(distances)); } +compressed_lower_distance_matrix read_ripser(std::istream& input_stream) { + std::vector<value_t> distances; + while (!input_stream.eof()) distances.push_back(read<value_t>(input_stream)); + return compressed_lower_distance_matrix(std::move(distances)); +} + compressed_lower_distance_matrix read_file(std::istream& input_stream, file_format format) { switch (format) { case LOWER_DISTANCE_MATRIX: @@ -823,29 +839,36 @@ compressed_lower_distance_matrix read_file(std::istream& input_stream, file_form return read_point_cloud(input_stream); case DIPHA: return read_dipha(input_stream); + case RIPSER: + return read_ripser(input_stream); } } void print_usage_and_exit(int exit_code) { - std::cerr << "Usage: " - << "ripser " - << "[options] [filename]" << std::endl - << std::endl - << "Options:" << std::endl - << std::endl - << " --help print this screen" << std::endl - << " --format use the specified file format for the input. Options are:" << std::endl - << " lower-distance (lower triangular distance matrix; default)" << std::endl - << " upper-distance (upper triangular distance matrix)" << std::endl - << " distance (full distance matrix)" << std::endl - << " point-cloud (point cloud in Euclidean space)" << std::endl - << " dipha (distance matrix in DIPHA file format)" << std::endl - << " --dim <k> compute persistent homology up to dimension <k>" << std::endl - << " --threshold <t> compute Rips complexes up to diameter <t>" << std::endl + std::cerr + << "Usage: " + << "ripser " + << "[options] [filename]" << std::endl + << std::endl + << "Options:" << std::endl + << std::endl + << " --help print this screen" << std::endl + << " --format use the specified file format for the input. Options are:" + << std::endl + << " lower-distance (lower triangular distance matrix; default)" + << std::endl + << " upper-distance (upper triangular distance matrix)" << std::endl + << " distance (full distance matrix)" << std::endl + << " point-cloud (point cloud in Euclidean space)" << std::endl + << " dipha (distance matrix in DIPHA file format)" << std::endl + << " ripser (distance matrix in Ripser binary file format)" + << std::endl + << " --dim <k> compute persistent homology up to dimension <k>" << std::endl + << " --threshold <t> compute Rips complexes up to diameter <t>" << std::endl #ifdef USE_COEFFICIENTS - << " --modulus <p> compute homology with coefficients in the prime field Z/<p>Z" + << " --modulus <p> compute homology with coefficients in the prime field Z/<p>Z" #endif - << std::endl; + << std::endl; exit(exit_code); } @@ -891,6 +914,8 @@ int main(int argc, char** argv) { format = POINT_CLOUD; else if (parameter == "dipha") format = DIPHA; + else if (parameter == "ripser") + format = RIPSER; else print_usage_and_exit(-1); #ifdef USE_COEFFICIENTS @@ -914,29 +939,28 @@ int main(int argc, char** argv) { compressed_lower_distance_matrix dist = read_file(filename ? file_stream : std::cin, format); - index_t n = dist.size(); - - std::cout << "distance matrix with " << n << " points" << std::endl; + std::cout << "distance matrix with " << dist.size() << " points" << std::endl; auto value_range = std::minmax_element(dist.distances.begin(), dist.distances.end()); - std::cout << "value range: [" << *value_range.first << "," << *value_range.second << "]" << std::endl; + std::cout << "value range: [" << *value_range.first << "," << *value_range.second << "]" + << std::endl; - dim_max = std::min(dim_max, n - 2); + ripser(std::move(dist), dim_max, threshold, modulus).compute_barcodes(); +} - binomial_coeff_table binomial_coeff(n, dim_max + 2); - std::vector<coefficient_t> multiplicative_inverse(multiplicative_inverse_vector(modulus)); +void ripser::compute_barcodes() { std::vector<diameter_index_t> columns_to_reduce; { union_find dset(n); std::vector<diameter_index_t> edges; - rips_filtration_comparator<decltype(dist)> comp(dist, 1, binomial_coeff); for (index_t index = binomial_coeff(n, 2); index-- > 0;) { - value_t diameter = comp.diameter(index); - if (diameter <= threshold) edges.push_back(diameter_index_t(diameter, index)); + value_t diameter = compute_diameter(index, 1); + if (diameter <= threshold) edges.push_back(std::make_pair(diameter, index)); } - std::sort(edges.rbegin(), edges.rend(), greater_diameter_or_smaller_index<diameter_index_t>()); + std::sort(edges.rbegin(), edges.rend(), + greater_diameter_or_smaller_index<diameter_index_t>()); #ifdef PRINT_PERSISTENCE_PAIRS std::cout << "persistence intervals in dim 0:" << std::endl; @@ -945,12 +969,13 @@ int main(int argc, char** argv) { std::vector<index_t> vertices_of_edge(2); for (auto e : edges) { vertices_of_edge.clear(); - get_simplex_vertices(get_index(e), 1, n, binomial_coeff, std::back_inserter(vertices_of_edge)); + get_simplex_vertices(get_index(e), 1, n, std::back_inserter(vertices_of_edge)); index_t u = dset.find(vertices_of_edge[0]), v = dset.find(vertices_of_edge[1]); if (u != v) { #ifdef PRINT_PERSISTENCE_PAIRS - std::cout << " [0," << get_diameter(e) << ")" << std::endl; + if (get_diameter(e) != 0) + std::cout << " [0," << get_diameter(e) << ")" << std::endl; #endif dset.link(u, v); } else @@ -965,17 +990,13 @@ int main(int argc, char** argv) { } for (index_t dim = 1; dim <= dim_max; ++dim) { - rips_filtration_comparator<decltype(dist)> comp(dist, dim + 1, binomial_coeff); - rips_filtration_comparator<decltype(dist)> comp_prev(dist, dim, binomial_coeff); - hash_map<index_t, index_t> pivot_column_index; pivot_column_index.reserve(columns_to_reduce.size()); - compute_pairs(columns_to_reduce, pivot_column_index, dist, comp, comp_prev, dim, n, threshold, modulus, - multiplicative_inverse, binomial_coeff); + compute_pairs(columns_to_reduce, pivot_column_index, dim); if (dim < dim_max) { - assemble_columns_to_reduce(columns_to_reduce, pivot_column_index, comp, dim, n, threshold, binomial_coeff); + assemble_columns_to_reduce(columns_to_reduce, pivot_column_index, dim + 1); } } } diff --git a/ripser.xcodeproj/project.pbxproj b/ripser.xcodeproj/project.pbxproj index 8703c59..f663e2c 100644 --- a/ripser.xcodeproj/project.pbxproj +++ b/ripser.xcodeproj/project.pbxproj @@ -88,7 +88,7 @@ 551018401BD63CB300990BFF /* Project object */ = { isa = PBXProject; attributes = { - LastUpgradeCheck = 0700; + LastUpgradeCheck = 0800; ORGANIZATIONNAME = "ulrich-bauer.org"; TargetAttributes = { 551018471BD63CB300990BFF = { @@ -129,7 +129,7 @@ isa = XCBuildConfiguration; buildSettings = { ALWAYS_SEARCH_USER_PATHS = NO; - CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x"; + CLANG_CXX_LANGUAGE_STANDARD = "c++0x"; CLANG_CXX_LIBRARY = "libc++"; CLANG_ENABLE_MODULES = YES; CLANG_ENABLE_OBJC_ARC = YES; @@ -138,15 +138,17 @@ CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR; CLANG_WARN_EMPTY_BODY = YES; CLANG_WARN_ENUM_CONVERSION = YES; + CLANG_WARN_INFINITE_RECURSION = YES; CLANG_WARN_INT_CONVERSION = YES; CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR; + CLANG_WARN_SUSPICIOUS_MOVE = YES; CLANG_WARN_UNREACHABLE_CODE = YES; CLANG_WARN__DUPLICATE_METHOD_MATCH = YES; COPY_PHASE_STRIP = NO; DEBUG_INFORMATION_FORMAT = dwarf; ENABLE_STRICT_OBJC_MSGSEND = YES; ENABLE_TESTABILITY = YES; - GCC_C_LANGUAGE_STANDARD = gnu99; + GCC_C_LANGUAGE_STANDARD = c11; GCC_DYNAMIC_NO_PIC = NO; GCC_NO_COMMON_BLOCKS = YES; GCC_OPTIMIZATION_LEVEL = 0; @@ -172,7 +174,7 @@ isa = XCBuildConfiguration; buildSettings = { ALWAYS_SEARCH_USER_PATHS = NO; - CLANG_CXX_LANGUAGE_STANDARD = "gnu++0x"; + CLANG_CXX_LANGUAGE_STANDARD = "c++0x"; CLANG_CXX_LIBRARY = "libc++"; CLANG_ENABLE_MODULES = YES; CLANG_ENABLE_OBJC_ARC = YES; @@ -181,15 +183,17 @@ CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR; CLANG_WARN_EMPTY_BODY = YES; CLANG_WARN_ENUM_CONVERSION = YES; + CLANG_WARN_INFINITE_RECURSION = YES; CLANG_WARN_INT_CONVERSION = YES; CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR; + CLANG_WARN_SUSPICIOUS_MOVE = YES; CLANG_WARN_UNREACHABLE_CODE = YES; CLANG_WARN__DUPLICATE_METHOD_MATCH = YES; COPY_PHASE_STRIP = NO; DEBUG_INFORMATION_FORMAT = "dwarf-with-dsym"; ENABLE_NS_ASSERTIONS = NO; ENABLE_STRICT_OBJC_MSGSEND = YES; - GCC_C_LANGUAGE_STANDARD = gnu99; + GCC_C_LANGUAGE_STANDARD = c11; GCC_NO_COMMON_BLOCKS = YES; GCC_WARN_64_TO_32_BIT_CONVERSION = YES; GCC_WARN_ABOUT_RETURN_TYPE = YES_ERROR; |