1 //Copyright (c) 2017 Ultimaker B.V.
2 //CuraEngine is released under the terms of the AGPLv3 or higher.
3
4 #include "MinimumSpanningTree.h"
5
6 #include <iterator>
7 #include <algorithm>
8
9 namespace cura
10 {
11
MinimumSpanningTree(std::vector<Point> vertices)12 MinimumSpanningTree::MinimumSpanningTree(std::vector<Point> vertices) : adjacency_graph(prim(vertices))
13 {
14 //Just copy over the fields.
15 }
16
prim(std::vector<Point> vertices) const17 auto MinimumSpanningTree::prim(std::vector<Point> vertices) const -> AdjacencyGraph_t
18 {
19 AdjacencyGraph_t result;
20 if (vertices.empty())
21 {
22 return result; //No vertices, so we can't create edges either.
23 }
24 // If there's only one vertex, we can't go creating any edges so just add the point to the adjacency list with no
25 // edges
26 if (vertices.size() == 1)
27 {
28 // unordered_map::operator[]() will construct an empty vector in place for us when we try and access an element
29 // that doesnt exist
30 result[*vertices.begin()];
31 return result;
32 }
33 result.reserve(vertices.size());
34 std::vector<Point> vertices_list(vertices.begin(), vertices.end());
35
36 std::unordered_map<const Point*, coord_t> smallest_distance; //The shortest distance to the current tree.
37 std::unordered_map<const Point*, const Point*> smallest_distance_to; //Which point the shortest distance goes towards.
38 smallest_distance.reserve(vertices_list.size());
39 smallest_distance_to.reserve(vertices_list.size());
40 for (size_t vertex_index = 1; vertex_index < vertices_list.size(); vertex_index++)
41 {
42 const auto& vert = vertices_list[vertex_index];
43 smallest_distance[&vert] = vSize2(vert - vertices_list[0]);
44 smallest_distance_to[&vert] = &vertices_list[0];
45 }
46
47 while (result.size() < vertices_list.size()) //All of the vertices need to be in the tree at the end.
48 {
49 //Choose the closest vertex to connect to that is not yet in the tree.
50 //This search is O(V) right now, which can be made down to O(log(V)). This reduces the overall time complexity from O(V*V) to O(V*log(E)).
51 //However that requires an implementation of a heap that supports the decreaseKey operation, which is not in the std library.
52 //TODO: Implement this?
53 using MapValue = std::pair<const Point*, coord_t>;
54 const auto closest = std::min_element(smallest_distance.begin(), smallest_distance.end(),
55 [](const MapValue& a, const MapValue& b) {
56 return a.second < b.second;
57 });
58
59 //Add this point to the graph and remove it from the candidates.
60 const Point* closest_point = closest->first;
61 const Point other_end = *smallest_distance_to[closest_point];
62 if (result.find(*closest_point) == result.end())
63 {
64 result[*closest_point] = std::vector<Edge>();
65 }
66 result[*closest_point].push_back({*closest_point, other_end});
67 if (result.find(other_end) == result.end())
68 {
69 result[other_end] = std::vector<Edge>();
70 }
71 result[other_end].push_back({other_end, *closest_point});
72 smallest_distance.erase(closest_point); //Remove it so we don't check for these points again.
73 smallest_distance_to.erase(closest_point);
74
75 //Update the distances of all points that are not in the graph.
76 for (std::pair<const Point*, coord_t> point_and_distance : smallest_distance)
77 {
78 const coord_t new_distance = vSize2(*closest_point - *point_and_distance.first);
79 const coord_t old_distance = point_and_distance.second;
80 if (new_distance < old_distance) //New point is closer.
81 {
82 smallest_distance[point_and_distance.first] = new_distance;
83 smallest_distance_to[point_and_distance.first] = closest_point;
84 }
85 }
86 }
87
88 return result;
89 }
90
adjacentNodes(Point node) const91 std::vector<Point> MinimumSpanningTree::adjacentNodes(Point node) const
92 {
93 std::vector<Point> result;
94 AdjacencyGraph_t::const_iterator adjacency_entry = adjacency_graph.find(node);
95 if (adjacency_entry != adjacency_graph.end())
96 {
97 const auto& edges = adjacency_entry->second;
98 std::transform(edges.begin(), edges.end(), std::back_inserter(result),
99 [&node](const Edge& e) { return (e.start == node) ? e.end : e.start; });
100 }
101 return result;
102 }
103
leaves() const104 std::vector<Point> MinimumSpanningTree::leaves() const
105 {
106 std::vector<Point> result;
107 for (std::pair<Point, std::vector<Edge>> node : adjacency_graph)
108 {
109 if (node.second.size() <= 1) //Leaves are nodes that have only one adjacent edge, or just the one node if the tree contains one node.
110 {
111 result.push_back(node.first);
112 }
113 }
114 return result;
115 }
116
vertices() const117 std::vector<Point> MinimumSpanningTree::vertices() const
118 {
119 std::vector<Point> result;
120 using MapValue = std::pair<Point, std::vector<Edge>>;
121 std::transform(adjacency_graph.begin(), adjacency_graph.end(), std::back_inserter(result),
122 [](const MapValue& node) { return node.first; });
123 return result;
124 }
125
126 }
127