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

Collaboration diagram for Slic3r::KMediods:

Public Member Functions
	KMediods (const int k, const int elem_count, const std::shared_ptr< FlushDistanceEvaluator > &evaluator, int default_group_id=0)
void	set_max_cluster_size (const std::vector< int > &group_size)
void	set_cluster_group_size (const std::vector< std::pair< std::set< int >, int > > &cluster_group_size)
void	set_placable_limits (const std::unordered_map< int, std::vector< int > > &placable_limits)
void	set_unplacable_limits (const std::unordered_map< int, std::vector< int > > &unplacable_limits)
void	set_memory_threshold (double threshold)
MemoryedGroupHeap	get_memoryed_groups () const
void	do_clustering (const FilamentGroupContext &context, const ClusteringBudget &budget)
std::vector< int >	get_cluster_labels () const

Protected Types
using	MemoryedGroupHeap = FilamentGroupUtils::MemoryedGroupHeap
using	MemoryedGroup = FilamentGroupUtils::MemoryedGroup

Protected Member Functions
bool	have_enough_size (const std::vector< int > &cluster_size, const std::vector< std::pair< std::set< int >, int > > &cluster_group_size, int elem_count)
int	calc_cost (const std::vector< int > &clusters, const std::vector< int > &cluster_centers, int cluster_id=-1)
std::vector< int >	init_cluster_center (const std::unordered_map< int, std::vector< int > > &placeable_limits, const std::unordered_map< int, std::vector< int > > &unplaceable_limits, const std::vector< int > &cluster_size, const std::vector< std::pair< std::set< int >, int > > &cluster_group_size, int seed)
std::vector< int >	assign_cluster_label (const std::vector< int > &center, const std::unordered_map< int, std::vector< int > > &placeable_limits, const std::unordered_map< int, std::vector< int > > &unplaceable_limits, const std::vector< int > &group_size, const std::vector< std::pair< std::set< int >, int > > &cluster_group_size)

Protected Attributes
MemoryedGroupHeap	memoryed_groups
std::shared_ptr< FlushDistanceEvaluator >	m_evaluator
std::unordered_map< int, std::vector< int > >	m_unplaceable_limits
std::unordered_map< int, std::vector< int > >	m_placeable_limits
std::vector< int >	m_max_cluster_size
std::vector< int >	m_cluster_labels
std::vector< std::pair< std::set< int >, int > >	m_cluster_group_size
std::vector< int >	m_nozzle_to_extruder
int	m_k
int	m_elem_count
int	m_default_group_id { 0 }
double	memory_threshold { 0 }

Detailed Description

Member Typedef Documentation

◆ MemoryedGroup

using Slic3r::KMediods::MemoryedGroup = FilamentGroupUtils::MemoryedGroup

protected

◆ MemoryedGroupHeap

using Slic3r::KMediods::MemoryedGroupHeap = FilamentGroupUtils::MemoryedGroupHeap

protected

Constructor & Destructor Documentation

◆ KMediods()

Slic3r::KMediods::KMediods	(	const int	k,
		const int	elem_count,
		const std::shared_ptr< FlushDistanceEvaluator > &	evaluator,
		int	default_group_id = 0 )

inline

                                                                                                                                      {
            m_k = k;
            m_evaluator = evaluator;
            m_max_cluster_size = std::vector<int>(k, DEFAULT_CLUSTER_SIZE);
            m_elem_count = elem_count;
            m_default_group_id = default_group_id;
        }

References DEFAULT_CLUSTER_SIZE, m_default_group_id, m_elem_count, m_evaluator, m_k, and m_max_cluster_size.

Member Function Documentation

◆ assign_cluster_label()

std::vector< int > Slic3r::KMediods::assign_cluster_label	(	const std::vector< int > &	center,
		const std::unordered_map< int, std::vector< int > > &	placeable_limits,
		const std::unordered_map< int, std::vector< int > > &	unplaceable_limits,
		const std::vector< int > &	group_size,
		const std::vector< std::pair< std::set< int >, int > > &	cluster_group_size )

protected

    {
        std::vector<int> labels(m_elem_count, -1);
        std::vector<int> l_nodes(m_elem_count);
        std::vector<int> r_nodes(m_k);
        std::iota(l_nodes.begin(), l_nodes.end(), 0);
        std::iota(r_nodes.begin(), r_nodes.end(), 0);
 
        std::vector<std::vector<float>> distance_matrix(m_elem_count, std::vector<float>(m_k));
        for (int i = 0; i < m_elem_count; ++i) {
            for (int j = 0; j < m_k; ++j) {
                if (center[j] == -1)
                    distance_matrix[i][j] = static_cast<float>(MaxFlowGraph::MCMF_MAX_EDGE_COST);
                else
                    distance_matrix[i][j] = m_evaluator->get_distance(i, center[j], m_nozzle_to_extruder[j]);
            }
        }
 
        // only consider the size limit if the group can contain all of the filaments
        std::vector<int> r_nodes_capacity = {};
        std::vector<std::pair<std::set<int>, int>> r_nodes_group_capacity = {};
        if (have_enough_size(cluster_size, cluster_group_size, m_elem_count)) {
            r_nodes_capacity = cluster_size;
            r_nodes_group_capacity = cluster_group_size;
        }
        else {
            // TODO: throw exception here?
            // adjust group size to elem count if the group cannot contain all of the filaments
            r_nodes_capacity = std::vector<int>(m_k, m_elem_count);
        }
        std::vector<int> l_nodes_capacity(l_nodes.size(),1);
        //for (size_t idx = 0; idx < center.size(); ++idx)
        //    if (center[idx] != -1)
        //        l_nodes_capacity[center[idx]] = 0;
 
 
        // Each group can receive up to m_elem_count materials at most, so the flow from r_nodes to sink is adjusted to m_elem_count.
        MinFlushFlowSolver M(distance_matrix, l_nodes, r_nodes, placeable_limits, unplaceable_limits, l_nodes_capacity, r_nodes_capacity, r_nodes_group_capacity);
        auto ret = M.solve();
 
        for (size_t idx = 0; idx < ret.size(); ++idx) {
            if (ret[idx] != MaxFlowGraph::INVALID_ID) {
                labels[l_nodes[idx]] = r_nodes[ret[idx]];
            }
        }
 
        for (size_t idx = 0; idx < center.size(); ++idx)
            if (center[idx] != -1)
                assert(labels[center[idx]] == idx);
 
        //for (size_t idx = 0; idx < center.size(); ++idx) {
        //    if (center[idx] != -1) {
        //        labels[center[idx]] = idx;
        //    }
        //}
 
        // If there are materials that have not been grouped in the last step, assign them to a valid group.
        for (size_t idx = 0; idx < labels.size(); ++idx) {
            if (labels[idx] == -1) {
                int fallback = m_default_group_id;
                auto it = unplaceable_limits.find(static_cast<int>(idx));
                if (it != unplaceable_limits.end()) {
                    for (int nid = 0; nid < m_k; ++nid) {
                        if (std::find(it->second.begin(), it->second.end(), nid) == it->second.end()) {
                            fallback = nid;
                            break;
                        }
                    }
                }
                labels[idx] = fallback;
            }
        }
 
        return labels;
    }

References Slic3r::center(), have_enough_size(), Slic3r::MaxFlowGraph::INVALID_ID, m_default_group_id, m_elem_count, m_evaluator, m_k, m_nozzle_to_extruder, Slic3r::MaxFlowGraph::MCMF_MAX_EDGE_COST, and Slic3r::MinFlushFlowSolver::solve().

Referenced by do_clustering().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ calc_cost()

int Slic3r::KMediods::calc_cost	(	const std::vector< int > &	clusters,
		const std::vector< int > &	cluster_centers,
		int	cluster_id = -1 )

protected

    {
        assert(m_evaluator);
        int total_cost = 0;
 
        std::vector<std::pair<int, double>> nozzle_cost(m_k,{0,0.0});
        std::vector<int> nozzle_filaments(m_k, 0);
        for (int i = 0; i < m_elem_count; ++i) {
            if (cluster_id != -1 && cluster_labels[i] != cluster_id)
                continue;
            if (cluster_centers[cluster_labels[i]] == -1)
                continue;
 
            nozzle_filaments[cluster_labels[i]]++;
            for (int j = i + 1; j < m_elem_count; ++j) {
                int nozzle_i = cluster_labels[i];
                int nozzle_j = cluster_labels[j];
                if (nozzle_i == nozzle_j) {
                    nozzle_cost[nozzle_i].first++;
                    nozzle_cost[nozzle_j].second += m_evaluator->get_distance(i, j, m_nozzle_to_extruder[nozzle_i]);
                }
            }
        }
        for (size_t i = 0; i < nozzle_cost.size(); ++i) {
            if (nozzle_filaments[i] > 0 && nozzle_cost[i].second > 0)
                total_cost += nozzle_cost[i].second / nozzle_cost[i].first * (nozzle_filaments[i] - 1);
        }
 
        return total_cost;
    }

References m_elem_count, m_evaluator, m_k, and m_nozzle_to_extruder.

◆ do_clustering()

void Slic3r::KMediods::do_clustering	(	const FilamentGroupContext &	context,
		const ClusteringBudget &	budget )

    {
        FlushTimeMachine T;
        T.time_machine_start();
 
        const std::vector<unsigned int> used_filaments = collect_sorted_used_filaments(context.model_info.layer_filaments);
 
        auto build_full_map = [&](const std::vector<int>& labels) -> std::vector<int> {
            std::vector<int> full_map(context.group_info.total_filament_num, m_default_group_id);
            for (int i = 0; i < (int)labels.size(); ++i)
                full_map[used_filaments[i]] = labels[i];
            return full_map;
        };
 
        auto evaluate_labels = [&](const std::vector<int>& labels) -> double {
            auto full_map = build_full_map(labels);
            return full_evaluate(used_filaments, full_map, context);
        };
 
        std::vector<int> best_cluster_centers = std::vector<int>(m_k, 0);
        std::vector<int> best_cluster_labels  = std::vector<int>(m_elem_count, m_default_group_id);
        double           best_cluster_cost    = std::numeric_limits<double>::max();
        int              retry_count          = 0;
 
        // Run at least one restart; otherwise every filament would stay in the default group.
        const int retry = std::max(1, budget.max_restarts);
        auto within_budget = [&]() { return budget.timeout_ms <= 0 || T.time_machine_end() < budget.timeout_ms; };
 
        while (retry_count < retry && within_budget()) {
            std::vector<int> curr_cluster_centers = init_cluster_center(m_placeable_limits, m_unplaceable_limits, m_max_cluster_size, m_cluster_group_size, retry_count);
            std::vector<int> curr_cluster_labels = assign_cluster_label(curr_cluster_centers, m_placeable_limits, m_unplaceable_limits, m_max_cluster_size, m_cluster_group_size);
            double           curr_cluster_cost   = evaluate_labels(curr_cluster_labels);
 
            MemoryedGroup g(curr_cluster_labels, curr_cluster_cost, 1);
            update_memoryed_groups(g, memory_threshold, memoryed_groups);
 
            bool mediods_changed = true;
            while (mediods_changed && within_budget()) {
                mediods_changed        = false;
                double best_swap_cost  = curr_cluster_cost;
                int best_swap_cluster  = -1;
                int best_swap_elem     = -1;
 
                for (size_t cluster_id = 0; cluster_id < m_k; ++cluster_id) {
                    if (curr_cluster_centers[cluster_id] == -1) continue;
                    for (int elem = 0; elem < m_elem_count; ++elem) {
                        if (std::find(curr_cluster_centers.begin(), curr_cluster_centers.end(), elem) != curr_cluster_centers.end() ||
                            std::find(m_unplaceable_limits[cluster_id].begin(), m_unplaceable_limits[cluster_id].end(), elem) != m_unplaceable_limits[cluster_id].end())
                            continue;
                        std::vector<int> tmp_centers = curr_cluster_centers;
                        tmp_centers[cluster_id]      = elem;
                        std::vector<int> tmp_labels  = assign_cluster_label(tmp_centers, m_placeable_limits, m_unplaceable_limits, m_max_cluster_size, m_cluster_group_size);
                        double           tmp_cost    = evaluate_labels(tmp_labels);
 
                        if (tmp_cost < best_swap_cost) {
                            best_swap_cost    = tmp_cost;
                            best_swap_cluster = cluster_id;
                            best_swap_elem    = elem;
                            mediods_changed   = true;
                        }
                    }
                }
 
                if (mediods_changed) {
                    curr_cluster_centers[best_swap_cluster] = best_swap_elem;
                    curr_cluster_labels = assign_cluster_label(curr_cluster_centers, m_placeable_limits, m_unplaceable_limits, m_max_cluster_size, m_cluster_group_size);
                    curr_cluster_cost   = evaluate_labels(curr_cluster_labels);
 
                    MemoryedGroup g(curr_cluster_labels, curr_cluster_cost, 1);
                    update_memoryed_groups(g, memory_threshold, memoryed_groups);
                }
            }
 
            if (curr_cluster_cost < best_cluster_cost) {
                best_cluster_centers = curr_cluster_centers;
                best_cluster_cost    = curr_cluster_cost;
                best_cluster_labels  = curr_cluster_labels;
            }
            retry_count += 1;
        }
        m_cluster_labels = best_cluster_labels;
    }

References assign_cluster_label(), Slic3r::collect_sorted_used_filaments(), Slic3r::full_evaluate(), Slic3r::FilamentGroupContext::group_info, init_cluster_center(), Slic3r::FilamentGroupContext::ModelInfo::layer_filaments, m_cluster_group_size, m_cluster_labels, m_default_group_id, m_elem_count, m_k, m_max_cluster_size, m_placeable_limits, m_unplaceable_limits, Slic3r::ClusteringBudget::max_restarts, memory_threshold, memoryed_groups, Slic3r::FilamentGroupContext::model_info, Slic3r::FilamentGroupUtils::FlushTimeMachine::time_machine_start(), Slic3r::ClusteringBudget::timeout_ms, Slic3r::FilamentGroupContext::GroupInfo::total_filament_num, and Slic3r::FilamentGroupUtils::update_memoryed_groups().

Referenced by Slic3r::FilamentGroup::calc_group_by_kmedoids().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_cluster_labels()

std::vector< int > Slic3r::KMediods::get_cluster_labels ( ) const

inline

244{ return m_cluster_labels; }

References m_cluster_labels.

Referenced by Slic3r::FilamentGroup::calc_group_by_kmedoids().

Here is the caller graph for this function:

◆ get_memoryed_groups()

MemoryedGroupHeap Slic3r::KMediods::get_memoryed_groups ( ) const

inline

241{ return memoryed_groups; }

References memoryed_groups.

Referenced by Slic3r::FilamentGroup::calc_group_by_kmedoids().

Here is the caller graph for this function:

◆ have_enough_size()

bool Slic3r::KMediods::have_enough_size	(	const std::vector< int > &	cluster_size,
		const std::vector< std::pair< std::set< int >, int > > &	cluster_group_size,
		int	elem_count )

protected

    {
        bool have_enough_size = true;
        std::optional<int>cluster_sum;
        std::optional<int>cluster_group_sum;
 
        if (!cluster_size.empty())
            cluster_sum = std::accumulate(cluster_size.begin(), cluster_size.end(), 0);
        if (!cluster_group_size.empty())
            cluster_group_sum = std::accumulate(cluster_group_size.begin(), cluster_group_size.end(), 0, [](int a, const std::pair<std::set<int>, int>& p) {return a + p.second; });
        if (cluster_sum.has_value())
            have_enough_size &= (cluster_sum >= elem_count);
        if (cluster_group_sum.has_value())
            have_enough_size &= (cluster_group_sum >= elem_count);
        return have_enough_size;
    }

References have_enough_size().

Referenced by assign_cluster_label(), and have_enough_size().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_cluster_center()

std::vector< int > Slic3r::KMediods::init_cluster_center	(	const std::unordered_map< int, std::vector< int > > &	placeable_limits,
		const std::unordered_map< int, std::vector< int > > &	unplaceable_limits,
		const std::vector< int > &	cluster_size,
		const std::vector< std::pair< std::set< int >, int > > &	cluster_group_size,
		int	seed )

protected

    {
        // max flow network
        std::vector<int> l_nodes(m_elem_count); // represent the filament idx, to be shuffled
        std::vector<int> r_nodes(m_k); // represent the group idx
        std::iota(l_nodes.begin(), l_nodes.end(), 0);
        std::iota(r_nodes.begin(), r_nodes.end(), 0);
 
        std::unordered_map<int, std::vector<int>> shuffled_placeable_limits;
        std::unordered_map<int, std::vector<int>> shuffled_unplaceable_limits;
        // shuffle the filaments and transfer placeable,unplaceable limits
        {
            std::mt19937 rng(seed);
            std::shuffle(l_nodes.begin(), l_nodes.end(), rng);
 
            std::unordered_map<int, int>idx_transfer;
            for (size_t idx = 0; idx < l_nodes.size(); ++idx){
                int new_idx = std::find(l_nodes.begin(),l_nodes.end(), idx) - l_nodes.begin();
                idx_transfer[idx] = new_idx;
            }
            for (auto& elem : placeable_limits)
                shuffled_placeable_limits[idx_transfer[elem.first]] = elem.second;
            for (auto& elem : unplaceable_limits)
                shuffled_unplaceable_limits[idx_transfer[elem.first]] = elem.second;
        }
 
 
        MaxFlowSolver M(l_nodes, r_nodes, shuffled_placeable_limits, shuffled_unplaceable_limits);
        auto ret = M.solve();
 
        // A remaining -1 means some filaments cannot be placed under the limit. We ignore the -1 here since we
        // are deciding the cluster center; the -1 can be handled in later steps.
        std::vector<int> cluster_center(m_k, -1);
        for (size_t idx = 0; idx < ret.size(); ++idx) {
            if (ret[idx] != -1) {
                cluster_center[ret[idx]] = l_nodes[idx];
            }
        }
 
        return cluster_center;
    }

References m_elem_count, m_k, and Slic3r::MaxFlowSolver::solve().

Referenced by do_clustering().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_cluster_group_size()

void Slic3r::KMediods::set_cluster_group_size ( const std::vector< std::pair< std::set< int >, int > > & cluster_group_size )

    {
        m_cluster_group_size = cluster_group_size;
        m_nozzle_to_extruder.resize(m_k, 0);
        for (int i = 0; i < m_cluster_group_size.size(); i++) {
            for (auto nozzle_id : m_cluster_group_size[i].first) m_nozzle_to_extruder[nozzle_id] = i;
        }
    }