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