From d9d3b0518ce5e0a52b9a0bae55fa5d8ca5b3c515 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Tue, 24 Sep 2019 17:53:08 -0400 Subject: made backbone cleaning more efficient by restricting to one-side-broken only, updated the crack finder to this new paradigm --- src/analysis_tools.cpp | 157 ++++++++++++++++--------------------------------- 1 file changed, 52 insertions(+), 105 deletions(-) (limited to 'src/analysis_tools.cpp') diff --git a/src/analysis_tools.cpp b/src/analysis_tools.cpp index 5f180ee..2965915 100644 --- a/src/analysis_tools.cpp +++ b/src/analysis_tools.cpp @@ -1,125 +1,72 @@ #include "analysis_tools.hpp" -template -bool is_shorter(const std::list &l1, const std::list &l2) { - return l1.size() < l2.size(); -} - -/* -bool trivial(boost::detail::edge_desc_impl) { - return true; -} - -std::list, std::list>> find_minimal_crack(const Graph& G, const network& n) { - Graph Gtmp(n.G.vertices.size()); - std::list removed_edges; - - class add_tree_edges : public boost::default_dfs_visitor { - public: - Graph& G; - std::list& E; - - add_tree_edges(Graph& G, std::list& E) : G(G), E(E) {} - - void tree_edge(boost::graph_traits::edge_descriptor e, const Graph& g) { - boost::add_edge(boost::source(e, g), boost::target(e, g), g[e], G); - } - - void back_edge(boost::graph_traits::edge_descriptor e, const Graph& g) { - if (!(boost::edge(boost::source(e, g), boost::target(e, g), G).second)) { - E.push_back(g[e].index); - } - } - }; - - add_tree_edges ate(Gtmp, removed_edges); - boost::depth_first_search(G, visitor(ate)); - - class find_cycle : public boost::default_dfs_visitor { - public: - std::list& E; - unsigned end; - struct done{}; - - find_cycle(std::list& E, unsigned end) : E(E), end(end) {} - - void discover_vertex(boost::graph_traits::vertex_descriptor v, const Graph& g) { - if (v == end) { - throw done{}; - } - } - - void examine_edge(boost::graph_traits::edge_descriptor e, const Graph& g) { - E.push_back(g[e].index); - } - - void finish_edge(boost::graph_traits::edge_descriptor e, const Graph& g) { - E.erase(std::find(E.begin(), E.end(), g[e].index)); - } - }; - - std::list> cycles; +std::pair, std::set> find_minimal_crack(const network& n, unsigned i0) { + std::set removed_edges = n.get_cycle_edges(n.G.dual_edges[i0].v[0]); + + std::vector, std::set>> cycles; + cycles.reserve(removed_edges.size()); + + for (unsigned edge : removed_edges) { + cycles.push_back(n.get_cycle(removed_edges, n.G.dual_edges[edge].v[0], n.G.dual_edges[edge].v[1])); + cycles.back().second.insert(edge); + if (n.G.dual_edges[edge].crossings[0]) + cycles.back().first[0]++; + if (n.G.dual_edges[edge].crossings[1]) + cycles.back().first[1]++; + } - for (auto edge : removed_edges) { - std::list cycle = {edge}; - find_cycle vis(cycle, n.G.dual_edges[edge].v[1]); - std::vector new_color_map(boost::num_vertices(Gtmp)); - try { - boost::depth_first_visit(Gtmp, n.G.dual_edges[edge].v[0], vis, boost::make_iterator_property_map(new_color_map.begin(), boost::get(boost::vertex_index, Gtmp), new_color_map[0])); - } catch(find_cycle::done const&) { - cycles.push_back(cycle); - } + if (cycles.size() == 1) { + return cycles.front(); } - std::list> bool_cycles; - for (auto cycle : cycles) { - std::valarray bool_cycle(n.G.edges.size()); - for (auto v : cycle) { - bool_cycle[v] = 1; + bool all_good = true; + unsigned not_good; + for (unsigned i = 0; i < 2; i++) { + if (!((cycles[i].first[0] % 2 == 0 && cycles[i].first[1] % 2 == 1) || (cycles[i].first[0] % 2 == 1 && cycles[i].first[1] % 2 == 0))) { + all_good = false; + not_good = i; } - bool_cycles.push_back(bool_cycle); } - // generate all possible cycles by taking xor of the edge sets of the known cycles - for (auto it1 = bool_cycles.begin(); it1 != std::prev(bool_cycles.end()); it1++) { - for (auto it2 = std::next(it1); it2 != bool_cycles.end(); it2++) { - std::valarray new_bool_cycle = (*it1) ^ (*it2); - std::list new_cycle; - unsigned pos = 0; - for (uint8_t included : new_bool_cycle) { - if (included) { - new_cycle.push_back(pos); - } - pos++; - } - cycles.push_back(new_cycle); + if (all_good) { + if (cycles[0].second.size() > cycles[1].second.size()) { + return cycles[1]; + } else { + return cycles[0]; } } - std::list, std::list>> output; + const auto& cycle1 = cycles[0]; + const auto& cycle2 = cycles[1]; - // find the cycle representing the crack by counting boundary crossings - for (auto cycle : cycles) { - std::array crossing_count{0,0}; + unsigned sum_sig_0 = cycle1.first[0] + cycle2.first[0]; + unsigned sum_sig_1 = cycle1.first[1] + cycle2.first[1]; - for (auto edge : cycle) { - if (n.G.dual_edges[edge].crossings[0]) { - crossing_count[0]++; - } - if (n.G.dual_edges[edge].crossings[1]) { - crossing_count[1]++; - } - } + std::valarray bool_cycle1(n.G.edges.size()); + std::valarray bool_cycle2(n.G.edges.size()); + for (auto v : cycle1.second) { + bool_cycle1[v] = 1; + } + for (auto v : cycle2.second) { + bool_cycle2[v] = 1; + } - if (crossing_count[0] % 2 == 1 && crossing_count[1] % 2 == 0) { - output.push_back({{1, 0}, cycle}); - } else if (crossing_count[0] % 2 == 0 && crossing_count[1] % 2 == 1) { - output.push_back({{0, 1}, cycle}); + std::valarray new_bool_cycle = bool_cycle1 ^ bool_cycle2; + + std::set new_cycle; + unsigned pos = 0; + for (uint8_t included : new_bool_cycle) { + if (included) { + new_cycle.insert(pos); } + pos++; } - return output; + if (cycles[!not_good].second.size() > new_cycle.size()) { + return {{sum_sig_0, sum_sig_1}, new_cycle}; + } else { + return cycles[!not_good]; + } } -*/ -- cgit v1.2.3-70-g09d2