summaryrefslogtreecommitdiff
path: root/src/analysis_tools.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis_tools.cpp')
-rw-r--r--src/analysis_tools.cpp157
1 files changed, 52 insertions, 105 deletions
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 <class T>
-bool is_shorter(const std::list<T> &l1, const std::list<T> &l2) {
- return l1.size() < l2.size();
-}
-
-/*
-bool trivial(boost::detail::edge_desc_impl<boost::undirected_tag,unsigned long>) {
- return true;
-}
-
-std::list<std::pair<std::array<unsigned, 2>, std::list<unsigned>>> find_minimal_crack(const Graph& G, const network& n) {
- Graph Gtmp(n.G.vertices.size());
- std::list<unsigned> removed_edges;
-
- class add_tree_edges : public boost::default_dfs_visitor {
- public:
- Graph& G;
- std::list<unsigned>& E;
-
- add_tree_edges(Graph& G, std::list<unsigned>& E) : G(G), E(E) {}
-
- void tree_edge(boost::graph_traits<Graph>::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<Graph>::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<unsigned>& E;
- unsigned end;
- struct done{};
-
- find_cycle(std::list<unsigned>& E, unsigned end) : E(E), end(end) {}
-
- void discover_vertex(boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g) {
- if (v == end) {
- throw done{};
- }
- }
-
- void examine_edge(boost::graph_traits<Graph>::edge_descriptor e, const Graph& g) {
- E.push_back(g[e].index);
- }
-
- void finish_edge(boost::graph_traits<Graph>::edge_descriptor e, const Graph& g) {
- E.erase(std::find(E.begin(), E.end(), g[e].index));
- }
- };
-
- std::list<std::list<unsigned>> cycles;
+std::pair<std::array<unsigned, 2>, std::set<unsigned>> find_minimal_crack(const network& n, unsigned i0) {
+ std::set<unsigned> removed_edges = n.get_cycle_edges(n.G.dual_edges[i0].v[0]);
+
+ std::vector<std::pair<std::array<unsigned, 2>, std::set<unsigned>>> 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<unsigned> cycle = {edge};
- find_cycle vis(cycle, n.G.dual_edges[edge].v[1]);
- std::vector<boost::default_color_type> 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<std::valarray<uint8_t>> bool_cycles;
- for (auto cycle : cycles) {
- std::valarray<uint8_t> 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<uint8_t> new_bool_cycle = (*it1) ^ (*it2);
- std::list<unsigned> 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::pair<std::array<unsigned, 2>, std::list<unsigned>>> 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<unsigned, 2> 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<uint8_t> bool_cycle1(n.G.edges.size());
+ std::valarray<uint8_t> 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<uint8_t> new_bool_cycle = bool_cycle1 ^ bool_cycle2;
+
+ std::set<unsigned> 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];
+ }
}
-*/