Slic3r::MinimumSpanningTree Class Reference

Implements Prim's algorithm to compute Minimum Spanning Trees (MST). More...

#include </home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MinimumSpanningTree.hpp>

Collaboration diagram for Slic3r::MinimumSpanningTree:

Classes
struct	Edge
	Represents an edge of the tree. More...

Public Member Functions
	MinimumSpanningTree ()=default
	MinimumSpanningTree (std::vector< Point > vertices)
	Constructs a minimum spanning tree that spans all given vertices.
std::vector< Point >	adjacent_nodes (Point node) const
	Gets the nodes that are adjacent to the specified node.
std::vector< Point >	leaves () const
	Gets the leaves of the tree.
std::vector< Point >	vertices () const
	Gets all vertices of the tree.

Private Types
using	AdjacencyGraph_t = std::unordered_map<Point, std::vector<Edge>, PointHash>

Private Member Functions
AdjacencyGraph_t	prim (std::vector< Point > vertices) const
	Computes the edges of a minimum spanning tree using Prim's algorithm.

Private Attributes
AdjacencyGraph_t	adjacency_graph

Detailed Description

Implements Prim's algorithm to compute Minimum Spanning Trees (MST).

The minimum spanning tree is always computed from a clique of vertices.

---

Class Documentation

Slic3r::MinimumSpanningTree::Edge

struct Slic3r::MinimumSpanningTree::Edge

Represents an edge of the tree.

While edges are meant to be undirected, these do have a start and end point.

Collaboration diagram for Slic3r::MinimumSpanningTree::Edge:

Class Members
const Point	end	The point at which this edge ends.
const Point	start	The point at which this edge starts.

Member Typedef Documentation

AdjacencyGraph_t

using Slic3r::MinimumSpanningTree::AdjacencyGraph_t = std::unordered_map<Point, std::vector<Edge>, PointHash>

private

Constructor & Destructor Documentation

MinimumSpanningTree() [1/2]

Slic3r::MinimumSpanningTree::MinimumSpanningTree ( )

default

References vertices().

Here is the call graph for this function:

MinimumSpanningTree() [2/2]

Slic3r::MinimumSpanningTree::MinimumSpanningTree

(

std::vector< Point >

vertices

)

Constructs a minimum spanning tree that spans all given vertices.

                                                                  : adjacency_graph(prim(vertices))
{
    //Just copy over the fields.
}

References adjacency_graph, prim(), and vertices().

Here is the call graph for this function:

Member Function Documentation

adjacent_nodes()

std::vector< Point > Slic3r::MinimumSpanningTree::adjacent_nodes

(

Point

node

)

const

Gets the nodes that are adjacent to the specified node.

Returns

A list of nodes that are adjacent.

{
    std::vector<Point> result;
    AdjacencyGraph_t::const_iterator adjacency_entry = adjacency_graph.find(node);
    if (adjacency_entry != adjacency_graph.end())
    {
        const auto& edges = adjacency_entry->second;
        std::transform(edges.begin(), edges.end(), std::back_inserter(result),
                       [&node](const Edge& e) { return (e.start == node) ? e.end : e.start; });
    }
    return result;
}

References adjacency_graph.

leaves()

std::vector< Point > Slic3r::MinimumSpanningTree::leaves

(

)

const

Gets the leaves of the tree.

Returns

A list of nodes that are all leaves of the tree.

{
    std::vector<Point> result;
    for (std::pair<Point, std::vector<Edge>> node : adjacency_graph)
    {
        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.
        {
            result.push_back(node.first);
        }
    }
    return result;
}

References adjacency_graph.

prim()

auto Slic3r::MinimumSpanningTree::prim ( std::vector< Point > vertices ) const

private

Computes the edges of a minimum spanning tree using Prim's algorithm.

Parameters

vertices

The vertices to span.

Returns

An adjacency graph with for each point one or more edges.

{
    AdjacencyGraph_t result;
    if (vertices.empty())
    {
        return result; //No vertices, so we can't create edges either.
    }
    // If there's only one vertex, we can't go creating any edges so just add the point to the adjacency list with no
    // edges
    if (vertices.size() == 1)
    {
        // unordered_map::operator[]() will construct an empty vector in place for us when we try and access an element
        // that doesnt exist
        result[*vertices.begin()];
        return result;
    }
    result.reserve(vertices.size());
    std::vector<Point> vertices_list(vertices.begin(), vertices.end());
 
    std::unordered_map<const Point*, coordf_t> smallest_distance;    //The shortest distance to the current tree.
    std::unordered_map<const Point*, const Point*> smallest_distance_to; //Which point the shortest distance goes towards.
    smallest_distance.reserve(vertices_list.size());
    smallest_distance_to.reserve(vertices_list.size());
    for (size_t vertex_index = 1; vertex_index < vertices_list.size(); vertex_index++)
    {
        const auto& vert = vertices_list[vertex_index];
        smallest_distance[&vert] = vsize2_with_unscale(vert - vertices_list[0]);
        smallest_distance_to[&vert] = &vertices_list[0];
    }
 
    while (result.size() < vertices_list.size()) //All of the vertices need to be in the tree at the end.
    {
        //Choose the closest vertex to connect to that is not yet in the tree.
        //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)).
        //However that requires an implementation of a heap that supports the decreaseKey operation, which is not in the std library.
        //TODO: Implement this?
        // Break equal-distance ties on coordinates: the map is keyed by address, so its
        // iteration order (and therefore the first minimum) would otherwise depend on where
        // the vertices were allocated.
        using MapValue = std::pair<const Point*, coordf_t>;
        const auto closest = std::min_element(smallest_distance.begin(), smallest_distance.end(),
                                              [](const MapValue& a, const MapValue& b) {
                                                  if (a.second != b.second)
                                                      return a.second < b.second;
                                                  return *a.first < *b.first;
                                              });
 
        //Add this point to the graph and remove it from the candidates.
        const Point* closest_point = closest->first;
        const Point other_end = *smallest_distance_to[closest_point];
        if (result.find(*closest_point) == result.end())
        {
            result[*closest_point] = std::vector<Edge>();
        }
        result[*closest_point].push_back({*closest_point, other_end});
        if (result.find(other_end) == result.end())
        {
            result[other_end] = std::vector<Edge>();
        }
        result[other_end].push_back({other_end, *closest_point});
        smallest_distance.erase(closest_point); //Remove it so we don't check for these points again.
        smallest_distance_to.erase(closest_point);
 
        //Update the distances of all points that are not in the graph.
        for (std::pair<const Point*, coordf_t> point_and_distance : smallest_distance)
        {
            const coordf_t new_distance = vsize2_with_unscale(*closest_point - *point_and_distance.first);
            const coordf_t old_distance = point_and_distance.second;
            if (new_distance < old_distance) //New point is closer.
            {
                smallest_distance[point_and_distance.first] = new_distance;
                smallest_distance_to[point_and_distance.first] = closest_point;
            }
        }
    }
 
    return result;
}

References vertices(), and Slic3r::vsize2_with_unscale().

Referenced by MinimumSpanningTree().

Here is the call graph for this function:

Here is the caller graph for this function:

vertices()

std::vector< Point > Slic3r::MinimumSpanningTree::vertices

(

)

const

Gets all vertices of the tree.

Returns

A list of vertices of the tree.

{
    std::vector<Point> result;
    using MapValue = std::pair<Point, std::vector<Edge>>;
    std::transform(adjacency_graph.begin(), adjacency_graph.end(), std::back_inserter(result),
                   [](const MapValue& node) { return node.first; });
    return result;
}

References adjacency_graph.

Referenced by MinimumSpanningTree(), MinimumSpanningTree(), and prim().

Here is the caller graph for this function:

Member Data Documentation

adjacency_graph

AdjacencyGraph_t Slic3r::MinimumSpanningTree::adjacency_graph

private

Referenced by MinimumSpanningTree(), adjacent_nodes(), leaves(), and vertices().

---

The documentation for this class was generated from the following files:

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MinimumSpanningTree.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/MinimumSpanningTree.cpp