82 std::map<vertex_t, bool> used_hits;
84 for (vertex_t
i = 0;
i < numSpacepoints;
i++) {
88 for(
size_t idx=0;
idx < rowIndices.size(); ++
idx) {
89 add_edge(rowIndices[
idx], colIndices[
idx], edgeWeights[
idx],
G);
95 UndirectedGraph ugraph;
97 for (
auto v : boost::make_iterator_range(vertices(newG))) {
99 add_vertex(
name, ugraph);
102 auto [edge_b, edge_e] = boost::edges(newG);
103 for (
auto it = edge_b;
it != edge_e; ++
it) {
109 std::vector<std::vector<vertex_t>> sub_graphs =
getSimplePath(ugraph);
111 for (
const auto&
track : sub_graphs) {
112 for (
auto hit_id :
track) {
113 used_hits[hit_id] =
true;
117 std::vector<Vertex> topo_order;
118 boost::topological_sort(newG, std::back_inserter(topo_order));
121 auto next_node_fn = [&](
const Graph &
G, vertex_t current_hit) {
126 for(
auto it = topo_order.rbegin();
it != topo_order.rend(); ++
it) {
128 int hit_id =
boost::get(boost::vertex_name, newG, node_id);
129 if (used_hits[hit_id])
continue;
132 auto roads =
buildRoads(newG, node_id, next_node_fn, used_hits);
133 used_hits[node_id] =
true;
139 std::vector<int>& longest_road = *std::max_element(roads.begin(), roads.end(),
140 [](
const std::vector<int> &
a,
const std::vector<int> &
b) {
141 return a.size() < b.size();
144 if (longest_road.size() >= 3) {
145 std::vector<vertex_t>
track;
146 for (
int node_id : longest_road) {
147 auto hit_id =
boost::get(boost::vertex_name, newG, node_id);
148 used_hits[hit_id] =
true;
149 track.push_back(hit_id);
151 sub_graphs.push_back(
track);
157 for (
const auto&
track : sub_graphs) {
158 std::vector<uint32_t> this_track{
track.begin(),
track.end()};
159 tracks.push_back(this_track);