From 9e3726c6c7762f6292333f85117546acc01f5568 Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Mon, 23 Sep 2019 17:12:55 -0400
Subject: more work, need to finish implementation of searches and make sure
existing ones correctly exclude the cycle edges
---
lib/src/network.cpp | 55 +++++++++++++++++++++++++++++++++--------------------
1 file changed, 34 insertions(+), 21 deletions(-)
(limited to 'lib')
diff --git a/lib/src/network.cpp b/lib/src/network.cpp
index 6b3873b..2a187c5 100644
--- a/lib/src/network.cpp
+++ b/lib/src/network.cpp
@@ -78,16 +78,18 @@ void network::get_cycle_edges_helper(std::set<unsigned>& cycle_edges,
std::set<unsigned>& seen_vertices, unsigned v_prev,
unsigned v_cur) const {
for (unsigned ei : G.dual_vertices[v_cur].ne) {
- const std::array<unsigned, 2>& e = G.dual_edges[ei].v;
- unsigned vn = e[0] == v_cur ? e[1] : e[0];
-
- if (vn != v_prev) {
- auto it = seen_vertices.find(vn);
- if (it == seen_vertices.end()) {
- // if (seen_vertices.contains()) { // need to wait for better c++20 support...
- cycle_edges.insert(vn);
- } else {
- this->get_cycle_edges_helper(cycle_edges, seen_vertices, v_cur, vn);
+ if (fuses[ei]) {
+ const std::array<unsigned, 2>& e = G.dual_edges[ei].v;
+ unsigned vn = e[0] == v_cur ? e[1] : e[0];
+
+ if (vn != v_prev) {
+ auto it = seen_vertices.find(vn);
+ if (it == seen_vertices.end()) {
+ // if (seen_vertices.contains()) { // need to wait for better c++20 support...
+ cycle_edges.insert(vn);
+ } else {
+ this->get_cycle_edges_helper(cycle_edges, seen_vertices, v_cur, vn);
+ }
}
}
}
@@ -102,20 +104,31 @@ std::set<unsigned> network::get_cycle_edges(unsigned v0) const {
return cycle_edges;
}
-std::array<unsigned, 2> network::find_cycle(const std::set<unsigned>& cycle_edges, unsigned v0, unsigned v1) const {
- for (unsigned ei : G.dual_vertices[v0].ne) {
- const std::array<unsigned, 2>& e = G.dual_edges[ei].v;
- unsigned vn = e[0] == v0 ? e[1] : e[0];
- if (vn == v1) {
- return {ei};
- } else {
- std::list<unsigned> edges = this->get_cycle_edges(vn, v1);
- edges.splice(edges.end(), {ei});
- return edges;
+bool network::find_cycle_helper(std::array<unsigned, 2>& sig, const std::set<unsigned>& cycle_edges, unsigned vPrev, unsigned vCur, unsigned vEnd) const {
+ for (unsigned ei : G.dual_vertices[vCur].ne) {
+ if (fuses[ei]) {
+ const std::array<unsigned, 2>& e = G.dual_edges[ei].v;
+ unsigned vn = e[0] == vCur ? e[1] : e[0];
+ if (vn != vPrev) {
+ if (vn == vEnd) {
+ return true;
+ } else {
+ if (find_cycle_helper(sig, cycle_edges, vCur, vn, vEnd)) {
+ if (G.dual_edges[ei].crossings[0]) sig[0]++;
+ if (G.dual_edges[ei].crossings[1]) sig[1]++;
+ return true;
+ }
+ }
+ }
}
}
- return {};
+ return false;
+}
+
+std::array<unsigned, 2> network::find_cycle(const std::set<unsigned>& cycle_edges, unsigned v0, unsigned v1) const {
+ std::array<unsigned, 2> sig;
+ this->find_cycle_helper(sig, cycle_edges, v0, v0,
}
void network::update_backbone(const std::vector<double>& c) {
--
cgit v1.2.3-70-g09d2