14#include <lagrange/Logger.h>
15#include <lagrange/common.h>
16#include <lagrange/legacy/inline.h>
45template <
typename DerivedE,
typename DerivedO>
46bool chain_edges_into_simple_loops(
47 const Eigen::MatrixBase<DerivedE>& edges,
48 std::vector<std::vector<typename DerivedE::Scalar>>& output,
49 Eigen::PlainObjectBase<DerivedO>& remaining_edges)
51 using Index =
typename DerivedE::Scalar;
52 using IndexArray = Eigen::Matrix<Index, Eigen::Dynamic, 1>;
56 if (edges.rows() == 0) {
61 Index num_vertices = edges.maxCoeff() + 1;
62 Index num_edges = (Index)edges.rows();
65 IndexArray degree_in(num_vertices);
66 IndexArray degree_out(num_vertices);
69 for (Index e = 0; e < num_edges; ++e) {
70 Index v0 = edges(e, 0);
71 Index v1 = edges(e, 1);
75 if (!(degree_in.array() == degree_out.array()).all()) {
76 logger().debug(
"Input digraph has dangling vertices.");
80 std::vector<Index> path_to_first_edge;
83 std::vector<Index> vertex_to_outgoing_edge(num_vertices, invalid<Index>());
86 std::vector<Index> next_edge_along_path(num_edges, invalid<Index>());
89 for (Index e = 0; e < num_edges; ++e) {
90 Index v0 = edges(e, 0);
91 if (degree_out[v0] == 1 && degree_in[v0] == 1) {
94 vertex_to_outgoing_edge[v0] = e;
98 path_to_first_edge.push_back(e);
102 for (Index e = 0; e < num_edges; ++e) {
103 Index v1 = edges(e, 1);
104 next_edge_along_path[e] = vertex_to_outgoing_edge[v1];
108 std::vector<Index> edge_label(num_edges, invalid<Index>());
109 std::vector<Index> path_to_last_edge(path_to_first_edge.size());
110 std::stack<Index> ears;
111 std::vector<std::vector<Index>> paths_in(num_vertices);
112 std::vector<std::vector<Index>> paths_out(num_vertices);
113 std::vector<bool> path_is_pending(path_to_first_edge.size(),
false);
115 auto first_vertex_in_path = [&](Index a) {
return edges(path_to_first_edge[a], 0); };
117 auto last_vertex_in_path = [&](Index a) {
return edges(path_to_last_edge[a], 1); };
123 for (Index a = 0; a < (Index)path_to_first_edge.size(); ++a) {
125 for (Index e = path_to_first_edge[a];
126 e != invalid<Index>() && edge_label[e] == invalid<Index>();
127 e = next_edge_along_path[e]) {
129 path_to_last_edge[a] = e;
132 const Index v_first = first_vertex_in_path(a);
133 const Index v_last = last_vertex_in_path(a);
136 paths_out[v_first].push_back(a);
137 paths_in[v_last].push_back(a);
139 if (v_first == v_last) {
142 path_is_pending[a] =
true;
150 for (Index e = 0; e < num_edges; ++e) {
151 if (edge_label[e] == invalid<Index>()) {
153 const Index a = (Index)path_to_first_edge.size();
154 path_to_first_edge.emplace_back(e);
155 path_to_last_edge.emplace_back(e);
156 path_is_pending.push_back(
false);
160 for (Index ei = next_edge_along_path[e];
161 ei != invalid<Index>() && edge_label[ei] == invalid<Index>();
162 ei = next_edge_along_path[ei]) {
164 path_to_last_edge[a] = ei;
168 next_edge_along_path[path_to_last_edge[a]] = invalid<Index>();
172 path_is_pending[a] =
true;
178 auto remove_from_vector = [](std::vector<Index>& vec,
size_t idx) {
184 Index num_edges_removed = 0;
185 std::vector<bool> edge_is_removed(num_edges,
false);
188 std::vector<bool> path_is_removed(path_to_first_edge.size(),
false);
189 while (!ears.empty()) {
190 const Index a = ears.top();
193 path_is_removed[a] =
true;
198 std::vector<Index> loop;
199 for (Index e = path_to_first_edge[a]; e != invalid<Index>(); e = next_edge_along_path[e]) {
202 edge_is_removed[e] =
true;
205 output.emplace_back(std::move(loop));
208 const Index v = first_vertex_in_path(a);
210 for (
size_t i = 0; i < paths_out[v].size();) {
211 if (paths_out[v][i] == a) {
212 remove_from_vector(paths_out[v], i);
218 for (
size_t i = 0; i < paths_in[v].size();) {
219 if (paths_in[v][i] == a) {
220 remove_from_vector(paths_in[v], i);
228 if (paths_in[v].size() == 1 && paths_out[v].size() == 1) {
229 const Index a_in = paths_in[v].front();
230 const Index a_out = paths_out[v].front();
239 la_debug_assert(next_edge_along_path[path_to_last_edge[a_in]] == invalid<Index>());
241 edges(path_to_last_edge[a_in], 1) == edges(path_to_first_edge[a_out], 0));
244 for (
auto& ai : paths_in[last_vertex_in_path(a_out)]) {
251 next_edge_along_path[path_to_last_edge[a_in]] = path_to_first_edge[a_out];
252 path_to_last_edge[a_in] = path_to_last_edge[a_out];
255 path_to_first_edge[a_out] = invalid<Index>();
256 path_to_last_edge[a_out] = invalid<Index>();
257 path_is_removed[a_out] =
true;
259 paths_out[v].clear();
261 const Index v_first = first_vertex_in_path(a_in);
262 const Index v_last = last_vertex_in_path(a_in);
264 if (v_first == v_last && !path_is_pending[a_in]) {
265 path_is_pending[a_in] =
true;
271 if (num_edges_removed != num_edges) {
273 "Removing ears didn't result in an empty graph, number of edges remaining: {}",
274 num_edges - num_edges_removed);
275 Index true_num_removed = 0;
276 for (
auto b : edge_is_removed) {
282 remaining_edges.resize(num_edges - num_edges_removed, 2);
283 for (Index e = 0, cnt = 0; e < num_edges; ++e) {
284 if (!edge_is_removed[e]) {
286 remaining_edges.row(cnt++) = edges.row(e);
LA_CORE_API spdlog::logger & logger()
Retrieves the current logger.
Definition: Logger.cpp:40
#define la_debug_assert(...)
Debug assertion check.
Definition: assert.h:189
constexpr void swap(function_ref< R(Args...)> &lhs, function_ref< R(Args...)> &rhs) noexcept
Swaps the referred callables of lhs and rhs.
Definition: function_ref.h:114
Main namespace for Lagrange.
Definition: AABBIGL.h:30