diff options
author | Arnur Nigmetov <nigmetov@tugraz.at> | 2020-03-06 18:29:25 +0100 |
---|---|---|
committer | Arnur Nigmetov <nigmetov@tugraz.at> | 2020-03-06 18:29:25 +0100 |
commit | 5ebf7142b00554b3f5d151c8b4e81b746962a5b8 (patch) | |
tree | fc5306ab414ef803e6bcbe13817e1c1d990b08b5 | |
parent | 3809e4071827a5959f27e472514eaed08ba6d15e (diff) |
Reorganize matching_dist code, minor fixes.
-rw-r--r-- | matching/CMakeLists.txt | 26 | ||||
-rw-r--r-- | matching/README.md (renamed from matching/README) | 0 | ||||
-rw-r--r-- | matching/example/matching_dist.cpp (renamed from matching/src/main.cpp) | 40 | ||||
-rw-r--r-- | matching/include/matching_distance.h | 2 | ||||
-rw-r--r-- | matching/src/test_generator.cpp | 211 | ||||
-rw-r--r-- | matching/tests/prism_1.bif (renamed from matching/src/tests/prism_1.bif) | 0 | ||||
-rw-r--r-- | matching/tests/prism_2.bif (renamed from matching/src/tests/prism_2.bif) | 0 | ||||
-rw-r--r-- | matching/tests/test_bifiltration.cpp (renamed from matching/src/tests/test_bifiltration.cpp) | 0 | ||||
l--------- | matching/tests/test_bifiltration_1.txt (renamed from matching/src/tests/test_bifiltration_1.txt) | 0 | ||||
l--------- | matching/tests/test_bifiltration_full_triangle_rene.txt (renamed from matching/src/tests/test_bifiltration_full_triangle_rene.txt) | 0 | ||||
-rw-r--r-- | matching/tests/test_common.cpp (renamed from matching/src/tests/test_common.cpp) | 0 | ||||
-rw-r--r-- | matching/tests/test_list.txt (renamed from matching/src/tests/test_list.txt) | 0 | ||||
-rw-r--r-- | matching/tests/test_matching_distance.cpp (renamed from matching/src/tests/test_matching_distance.cpp) | 0 | ||||
-rw-r--r-- | matching/tests/tests_main.cpp (renamed from matching/src/tests/tests_main.cpp) | 0 |
14 files changed, 36 insertions, 243 deletions
diff --git a/matching/CMakeLists.txt b/matching/CMakeLists.txt index 121e25c..3ee0f6b 100644 --- a/matching/CMakeLists.txt +++ b/matching/CMakeLists.txt @@ -22,7 +22,6 @@ set(CMAKE_CXX_STANDARD 14) if (NOT WIN32) set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}") - #set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS} -Wall pedantic -Wextra ") set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS} -Wall -Wextra ") set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -D_GLIBCXX_DEBUG") set(CMAKE_CXX_FLAGS_RELWITHDEBINFO "${CMAKE_CXX_FLAGS_RELEASE} -O2 -g -ggdb") @@ -31,32 +30,23 @@ endif (NOT WIN32) file(GLOB BT_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}/../bottleneck/include/*.h ${CMAKE_CURRENT_SOURCE_DIR}/../bottleneck/include/*.hpp) file(GLOB MD_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}/include/*.h ${CMAKE_CURRENT_SOURCE_DIR}/include/*.hpp) -file(GLOB SRC_FILES ${CMAKE_CURRENT_SOURCE_DIR}/src/*.cpp) - -file(GLOB SRC_TEST_FILES ${CMAKE_CURRENT_SOURCE_DIR}/src/tests/*.cpp) - +file(GLOB SRC_TEST_FILES ${CMAKE_CURRENT_SOURCE_DIR}/tests/*.cpp) + find_package(Threads) set(libraries ${libraries} "stdc++fs" ${CMAKE_THREAD_LIBS_INIT}) find_package(OpenMP) if (OPENMP_FOUND) -set(libraries ${libraries} ${OpenMP_CXX_LIBRARIES}) -set (CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}") -set (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS}") -set (CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${OpenMP_EXE_LINKER_FLAGS}") + set(libraries ${libraries} ${OpenMP_CXX_LIBRARIES}) + set (CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}") + set (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} ${OpenMP_CXX_FLAGS}") + set (CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} ${OpenMP_EXE_LINKER_FLAGS}") endif() -add_executable(matching_distance "src/main.cpp" ${MD_HEADERS} ${BT_HEADERS} ) -target_link_libraries(matching_distance PUBLIC ${libraries}) +add_executable(matching_dist "example/matching_dist.cpp" ${MD_HEADERS} ${BT_HEADERS} ) +target_link_libraries(matching_dist PUBLIC ${libraries}) add_executable(matching_distance_test ${SRC_TEST_FILES} ${BT_HEADERS} ${MD_HEADERS}) target_link_libraries(matching_distance_test PUBLIC ${libraries}) - -add_executable(test_generator "src/test_generator.cpp" - ${MD_HEADERS} - ${BT_HEADERS}) -target_link_libraries(test_generator PUBLIC ${libraries}) - -#add_executable(matching_distance "include/main.cpp" "src/box.cpp" "src/common_util.cpp" "src/line.cpp" "src/persistence_module.hpp" ${BT_HEADERS} ${MD_HEADERS}) diff --git a/matching/README b/matching/README.md index 7dc1874..7dc1874 100644 --- a/matching/README +++ b/matching/README.md diff --git a/matching/src/main.cpp b/matching/example/matching_dist.cpp index 2093457..13e5c6d 100644 --- a/matching/src/main.cpp +++ b/matching/example/matching_dist.cpp @@ -5,7 +5,7 @@ #include <cassert>
#include <experimental/filesystem>
-#ifdef EXPERIMENTAL_TIMING
+#ifdef MD_EXPERIMENTAL_TIMING
#include <chrono>
#endif
@@ -24,12 +24,6 @@ using namespace md; namespace fs = std::experimental::filesystem;
-void force_instantiation()
-{
- DualBox<Real> db;
- std::cout << db;
-}
-
#ifdef PRINT_HEAT_MAP
void print_heat_map(const md::HeatMaps<Real>& hms, std::string fname, const CalculationParams<Real>& params)
{
@@ -149,14 +143,25 @@ int main(int argc, char** argv) using opts::PosOption;
opts::Options ops;
+ CalculationParams<Real> params;
+
bool help = false;
+
+#ifdef MD_EXPERIMENTAL_TIMING
bool no_stop_asap = false;
- CalculationParams<Real> params;
+#endif
+
#ifdef PRINT_HEAT_MAP
bool heatmap_only = false;
#endif
+ // default values are the best for practical use
+ // if compiled with MD_EXPERIMENTAL_TIMING, user can supply
+ // different bounds and traverse strategies
+ // separated by commas, all combinations will be timed.
+ // See corresponding >> operators in matching_distance.h
+ // for possible values.
std::string bounds_list_str = "local_combined";
std::string traverse_list_str = "BFS";
@@ -164,10 +169,12 @@ int main(int argc, char** argv) >> Option('e', "max-error", params.delta, "error threshold")
>> Option('d', "dim", params.dim, "dim")
>> Option('i', "initial-depth", params.initialization_depth, "initialization depth")
+#ifdef MD_EXPERIMENTAL_TIMING
>> Option("no-stop-asap", no_stop_asap,
"don't stop looping over points, if cell cannot be pruned (asap is on by default)")
>> Option("bounds", bounds_list_str, "bounds to use, separated by ,")
- >> Option("traverse", traverse_list_str, "traverse to use, separated by ,")
+ >> Option("traverse", traverse_list_str, "traverse strategy to use, separated by ,")
+#endif
#ifdef PRINT_HEAT_MAP
>> Option("heatmap-only", heatmap_only, "only save heatmap (bruteforce)")
#endif
@@ -177,11 +184,15 @@ int main(int argc, char** argv) std::string fname_b;
if (!ops.parse(argc, argv) || help || !(ops >> PosOption(fname_a) >> PosOption(fname_b))) {
- std::cerr << "Usage: " << argv[0] << "bifiltration-file-1 bifiltration-file-2\n" << ops << std::endl;
+ std::cerr << "Usage: " << argv[0] << " bifiltration-file-1 bifiltration-file-2\n" << ops << std::endl;
return 1;
}
+#ifdef MD_EXPERIMENTAL_TIMING
params.stop_asap = not no_stop_asap;
+#else
+ params.stop_asap = true;
+#endif
auto bounds_list = split_by_delim(bounds_list_str, ',');
auto traverse_list = split_by_delim(traverse_list_str, ',');
@@ -206,7 +217,7 @@ int main(int argc, char** argv) }
-#ifdef EXPERIMENTAL_TIMING
+#ifdef MD_EXPERIMENTAL_TIMING
for(auto bs : bound_strategies) {
for(auto ts : traverse_strategies) {
@@ -215,7 +226,7 @@ int main(int argc, char** argv) }
struct ExperimentResult {
- CalculationParams<Real> params {CalculationParams()};
+ CalculationParams<Real> params {CalculationParams<Real>()};
int n_hera_calls {0};
double total_milliseconds_elapsed {0};
Real distance {0};
@@ -265,12 +276,14 @@ int main(int argc, char** argv) const int n_repetitions = 1;
+#ifdef PRINT_HEAT_MAP
if (heatmap_only) {
bound_strategies.clear();
bound_strategies.push_back(BoundStrategy::bruteforce);
traverse_strategies.clear();
traverse_strategies.push_back(TraverseStrategy::breadth_first);
}
+#endif
std::map<std::tuple<BoundStrategy, TraverseStrategy>, ExperimentResult> results;
for(BoundStrategy bound_strategy : bound_strategies) {
@@ -293,9 +306,11 @@ int main(int argc, char** argv) // remember: params is passed by reference to return real relative error and heat map
int user_max_iters = params.max_depth;
+#ifdef PRINT_HEAT_MAP
if (bound_strategy == BoundStrategy::bruteforce and not heatmap_only) {
params_experiment.max_depth = std::min(7, params.max_depth);
}
+#endif
double total_milliseconds_elapsed = 0;
int total_n_hera_calls = 0;
Real dist;
@@ -377,6 +392,5 @@ int main(int argc, char** argv) Real dist = matching_distance<Real>(bif_a, bif_b, params);
std::cout << dist << std::endl;
#endif
- force_instantiation();
return 0;
}
diff --git a/matching/include/matching_distance.h b/matching/include/matching_distance.h index 5be34c7..276cc3a 100644 --- a/matching/include/matching_distance.h +++ b/matching/include/matching_distance.h @@ -169,7 +169,7 @@ namespace md { bool print_stats { false }; #ifdef MD_PRINT_HEAT_MAP - HeatMaps heat_maps; + HeatMaps<Real> heat_maps; #endif }; diff --git a/matching/src/test_generator.cpp b/matching/src/test_generator.cpp deleted file mode 100644 index a2f0625..0000000 --- a/matching/src/test_generator.cpp +++ /dev/null @@ -1,211 +0,0 @@ -#include <map> -#include <vector> -#include <random> -#include <iostream> -#include <algorithm> - -#include "opts/opts.h" -#include "spdlog/spdlog.h" -#include "spdlog/fmt/ostr.h" - -#include "common_util.h" -#include "bifiltration.h" - -using Real = double; -using Index = md::Index; -using Point = md::Point<Real>; -using Bifiltration = md::Bifiltration<Real>; -using Column = md::Column; -using Simplex = md::Simplex<Real>; - -int g_max_coord = 100; - -using ASimplex = md::AbstractSimplex; - -using ASimplexToBirthMap = std::map<ASimplex, Point>; - -namespace spd = spdlog; - -// random generator is global -std::random_device rd; -std::mt19937_64 gen(rd()); - -//std::mt19937_64 gen(42); - -Point get_random_position(int max_coord) -{ - assert(max_coord > 0); - std::uniform_int_distribution<int> distr(0, max_coord); - return Point(distr(gen), distr(gen)); - -} - -Point get_random_position_less_than(Point ub) -{ - std::uniform_int_distribution<int> distr_x(0, ub.x); - std::uniform_int_distribution<int> distr_y(0, ub.y); - return Point(distr_x(gen), distr_y(gen)); -} - -Point get_random_position_greater_than(Point lb) -{ - std::uniform_int_distribution<int> distr_x(lb.x, g_max_coord); - std::uniform_int_distribution<int> distr_y(lb.y, g_max_coord); - return Point(distr_x(gen), distr_y(gen)); -} - -// non-proper faces (empty and simplex itself) are also faces -bool is_face(const ASimplex& face_candidate, const ASimplex& coface_candidate) -{ - return std::includes(coface_candidate.begin(), coface_candidate.end(), face_candidate.begin(), - face_candidate.end()); -} - -bool is_top_simplex(const ASimplex& candidate_simplex, const std::vector<ASimplex>& current_top_simplices) -{ - return std::none_of(current_top_simplices.begin(), current_top_simplices.end(), - [&candidate_simplex](const ASimplex& ts) { return is_face(candidate_simplex, ts); }); -} - -void add_if_top(const ASimplex& candidate_simplex, std::vector<ASimplex>& current_top_simplices) -{ - // check that candidate simplex is not face of someone in current_top_simplices - if (!is_top_simplex(candidate_simplex, current_top_simplices)) - return; - - spd::debug("candidate_simplex is top, will be added to top_simplices"); - // remove s from currrent_top_simplices, if s is face of candidate_simplex - current_top_simplices.erase(std::remove_if(current_top_simplices.begin(), current_top_simplices.end(), - [candidate_simplex](const ASimplex& s) { return is_face(s, candidate_simplex); }), - current_top_simplices.end()); - - current_top_simplices.push_back(candidate_simplex); -} - -ASimplex get_random_simplex(int n_vertices, int dim) -{ - std::vector<int> all_vertices(n_vertices, 0); - // fill in with 0..n-1 - std::iota(all_vertices.begin(), all_vertices.end(), 0); - std::shuffle(all_vertices.begin(), all_vertices.end(), gen); - return ASimplex(all_vertices.begin(), all_vertices.begin() + dim + 1, true); -} - -void generate_positions(const ASimplex& s, ASimplexToBirthMap& simplex_to_birth, Point upper_bound) -{ - auto pos = get_random_position_less_than(upper_bound); - auto curr_pos_iter = simplex_to_birth.find(s); - if (curr_pos_iter != simplex_to_birth.end()) - pos = md::greatest_lower_bound(pos, curr_pos_iter->second); - simplex_to_birth[s] = pos; - for(const ASimplex& facet : s.facets()) { - generate_positions(facet, simplex_to_birth, pos); - } -} - -Bifiltration get_random_bifiltration(int n_vertices, int max_dim, int n_top_simplices) -{ - ASimplexToBirthMap simplex_to_birth; - - // generate vertices - for(int i = 0; i < n_vertices; ++i) { - Point vertex_birth = get_random_position(g_max_coord / 10); - ASimplex vertex; - vertex.push_back(i); - simplex_to_birth[vertex] = vertex_birth; - } - - std::vector<ASimplex> top_simplices; - // generate top simplices - while((int)top_simplices.size() < n_top_simplices) { - std::uniform_int_distribution<int> dimension_distr(1, max_dim); - int dim = dimension_distr(gen); - auto candidate_simplex = get_random_simplex(n_vertices, dim); - spd::debug("candidate_simplex = {}", candidate_simplex); - add_if_top(candidate_simplex, top_simplices); - } - - Point upper_bound{static_cast<Real>(g_max_coord), static_cast<Real>(g_max_coord)}; - for(const auto& top_simplex : top_simplices) { - generate_positions(top_simplex, simplex_to_birth, upper_bound); - } - - std::vector<std::pair<ASimplex, Point>> simplex_birth_pairs{simplex_to_birth.begin(), simplex_to_birth.end()}; - std::vector<Column> boundaries{simplex_to_birth.size(), Column()}; - -// assign ids and save boundaries - int id = 0; - - for(int dim = 0; dim <= max_dim; ++dim) { - for(int i = 0; i < (int) simplex_birth_pairs.size(); ++i) { - ASimplex& simplex = simplex_birth_pairs[i].first; - if (simplex.dim() == dim) { - simplex.id = id++; - Column bdry; - for(auto& facet : simplex.facets()) { - auto facet_iter = std::find_if(simplex_birth_pairs.begin(), simplex_birth_pairs.end(), - [facet](const std::pair<ASimplex, Point>& sbp) { return facet == sbp.first; }); - assert(facet_iter != simplex_birth_pairs.end()); - assert(facet_iter->first.id >= 0); - bdry.push_back(facet_iter->first.id); - } - std::sort(bdry.begin(), bdry.end()); - boundaries[i] = bdry; - } - } - } - -// create vector of Simplex-es - std::vector<Simplex> simplices; - for(int i = 0; i < (int) simplex_birth_pairs.size(); ++i) { - int id = simplex_birth_pairs[i].first.id; - int dim = simplex_birth_pairs[i].first.dim(); - Point birth = simplex_birth_pairs[i].second; - Column bdry = boundaries[i]; - simplices.emplace_back(id, birth, dim, bdry); - } - -// sort by id - std::sort(simplices.begin(), simplices.end(), - [](const Simplex& s1, const Simplex& s2) { return s1.id() < s2.id(); }); - for(int i = 0; i < (int)simplices.size(); ++i) { - assert(simplices[i].id() == i); - assert(i == 0 || simplices[i].dim() >= simplices[i - 1].dim()); - } - - return Bifiltration(simplices.begin(), simplices.end()); -} - -int main(int argc, char** argv) -{ - spd::set_level(spd::level::info); - int n_vertices; - int max_dim; - int n_top_simplices; - std::string fname; - - using opts::Option; - using opts::PosOption; - opts::Options ops; - - bool help = false; - - ops >> Option('v', "n-vertices", n_vertices, "number of vertices") - >> Option('d', "max-dim", max_dim, "maximal dim") - >> Option('m', "max-coord", g_max_coord, "maximal coordinate") - >> Option('t', "n-top-simplices", n_top_simplices, "number of top simplices") - >> Option('h', "help", help, "show help message"); - - if (!ops.parse(argc, argv) || help || !(ops >> PosOption(fname))) { - std::cerr << "Usage: " << argv[0] << "\n" << ops << std::endl; - return 1; - } - - - auto bif1 = get_random_bifiltration(n_vertices, max_dim, n_top_simplices); - std::cout << "Generated bifiltration." << std::endl; - bif1.save(fname, md::BifiltrationFormat::phat_like); - std::cout << "Saved to file " << fname << std::endl; - return 0; -} - diff --git a/matching/src/tests/prism_1.bif b/matching/tests/prism_1.bif index b37e807..b37e807 100644 --- a/matching/src/tests/prism_1.bif +++ b/matching/tests/prism_1.bif diff --git a/matching/src/tests/prism_2.bif b/matching/tests/prism_2.bif index 49885e6..49885e6 100644 --- a/matching/src/tests/prism_2.bif +++ b/matching/tests/prism_2.bif diff --git a/matching/src/tests/test_bifiltration.cpp b/matching/tests/test_bifiltration.cpp index 742dab8..742dab8 100644 --- a/matching/src/tests/test_bifiltration.cpp +++ b/matching/tests/test_bifiltration.cpp diff --git a/matching/src/tests/test_bifiltration_1.txt b/matching/tests/test_bifiltration_1.txt index ddd23e9..ddd23e9 120000 --- a/matching/src/tests/test_bifiltration_1.txt +++ b/matching/tests/test_bifiltration_1.txt diff --git a/matching/src/tests/test_bifiltration_full_triangle_rene.txt b/matching/tests/test_bifiltration_full_triangle_rene.txt index 47f49fd..47f49fd 120000 --- a/matching/src/tests/test_bifiltration_full_triangle_rene.txt +++ b/matching/tests/test_bifiltration_full_triangle_rene.txt diff --git a/matching/src/tests/test_common.cpp b/matching/tests/test_common.cpp index 9079a56..9079a56 100644 --- a/matching/src/tests/test_common.cpp +++ b/matching/tests/test_common.cpp diff --git a/matching/src/tests/test_list.txt b/matching/tests/test_list.txt index 1984606..1984606 100644 --- a/matching/src/tests/test_list.txt +++ b/matching/tests/test_list.txt diff --git a/matching/src/tests/test_matching_distance.cpp b/matching/tests/test_matching_distance.cpp index 82da530..82da530 100644 --- a/matching/src/tests/test_matching_distance.cpp +++ b/matching/tests/test_matching_distance.cpp diff --git a/matching/src/tests/tests_main.cpp b/matching/tests/tests_main.cpp index 1c77b13..1c77b13 100644 --- a/matching/src/tests/tests_main.cpp +++ b/matching/tests/tests_main.cpp |