Slic3r::GroupMinCostFlowSolver Class Reference

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

Collaboration diagram for Slic3r::GroupMinCostFlowSolver:

Public Member Functions
	GroupMinCostFlowSolver (const std::vector< FlushMatrix > &matrix_, const std::vector< int > &u_nodes, const std::vector< int > &v_nodes, const std::vector< int > &v_nodes_group, const std::unordered_map< int, std::vector< int > > &uv_link_limits={}, const std::unordered_map< int, std::vector< int > > &uv_unlink_limits={})
std::vector< int >	solve ()
	~GroupMinCostFlowSolver ()

Private Member Functions
void	build_graph ()
int	get_flush_cost (int l_idx, int r_idx)

Private Attributes
std::unique_ptr< MinCostMaxFlow >	m_solver
std::vector< FlushMatrix >	flush_matrix
std::vector< int >	l_nodes
std::vector< int >	r_nodes
std::vector< int >	r_nodes_group
std::unordered_map< int, std::vector< int > >	m_uv_link_limits
std::unordered_map< int, std::vector< int > >	m_uv_unlink_limits
int	num_groups = 0

Detailed Description

Constructor & Destructor Documentation

GroupMinCostFlowSolver()

Slic3r::GroupMinCostFlowSolver::GroupMinCostFlowSolver	(	const std::vector< FlushMatrix > &	matrix_,
		const std::vector< int > &	u_nodes,
		const std::vector< int > &	v_nodes,
		const std::vector< int > &	v_nodes_group,
		const std::unordered_map< int, std::vector< int > > &	uv_link_limits = {},
		const std::unordered_map< int, std::vector< int > > &	uv_unlink_limits = {} )

    {
        flush_matrix       = matrix_;
        l_nodes            = u_nodes;
        r_nodes            = v_nodes;
        r_nodes_group      = v_nodes_group;
        m_uv_link_limits   = uv_link_limits;
        m_uv_unlink_limits = uv_unlink_limits;
        num_groups         = *std::max_element(r_nodes_group.begin(), r_nodes_group.end()) + 1;
 
        m_solver = std::make_unique<MinCostMaxFlow>();
        build_graph();
    }

References build_graph(), flush_matrix, l_nodes, m_solver, m_uv_link_limits, m_uv_unlink_limits, num_groups, r_nodes, and r_nodes_group.

Here is the call graph for this function:

~GroupMinCostFlowSolver()

Slic3r::GroupMinCostFlowSolver::~GroupMinCostFlowSolver ( )

default

Member Function Documentation

build_graph()

void Slic3r::GroupMinCostFlowSolver::build_graph ( )

private

    {
        const int L = (int)l_nodes.size();
        const int R = (int)r_nodes.size();
        const int G = num_groups;
 
        m_solver->l_nodes    = l_nodes;
        m_solver->r_nodes    = r_nodes;
        m_solver->total_nodes = L + R + G + 2;
        m_solver->source_id  = L + R + G;
        m_solver->sink_id    = L + R + G + 1;
        m_solver->adj.resize(m_solver->total_nodes);
 
        int max_flush = 0;
        for (const auto &mat : flush_matrix)
            for (const auto &row : mat)
                for (float v : row)
                    max_flush = std::max(max_flush, (int)v);
        int bonus = max_flush * L + 1;
 
        // source -> l_i
        for (int i = 0; i < L; ++i)
            m_solver->add_edge(m_solver->source_id, i, 1, 0);
 
        // l_i -> r_j (with link/unlink limits)
        for (int i = 0; i < L; ++i) {
            if (auto it = m_uv_link_limits.find(i); it != m_uv_link_limits.end()) {
                for (int j : it->second)
                    m_solver->add_edge(i, L + j, 1, get_flush_cost(i, j));
                continue;
            }
 
            std::optional<std::vector<int>> unlink_limits;
            if (auto it = m_uv_unlink_limits.find(i); it != m_uv_unlink_limits.end())
                unlink_limits = it->second;
 
            for (int j = 0; j < R; ++j) {
                if (unlink_limits.has_value() && std::find(unlink_limits->begin(), unlink_limits->end(), j) != unlink_limits->end())
                    continue;
                m_solver->add_edge(i, L + j, 1, get_flush_cost(i, j));
            }
        }
 
        // r_j -> group_g
        // Compute per-nozzle incoming edge count as capacity upper bound.
        // When unlink_limits restrict multiple filaments to the same nozzle,
        // capacity=1 would block valid assignments. Using the actual in-degree
        // allows the necessary flow while still preserving nozzle-level balance
        // (a nozzle with fewer forced filaments keeps a tighter cap).
        // The first unit carries a small nozzle-bonus to encourage spreading
        // filaments across distinct nozzles within the same group.
        int nozzle_bonus = max_flush + 1;
        std::vector<int> r_in_degree(R, 0);
        for (int i = 0; i < L; ++i) {
            if (auto it = m_uv_link_limits.find(i); it != m_uv_link_limits.end()) {
                for (int j : it->second)
                    r_in_degree[j]++;
                continue;
            }
            std::optional<std::vector<int>> unlink_limits;
            if (auto it = m_uv_unlink_limits.find(i); it != m_uv_unlink_limits.end())
                unlink_limits = it->second;
            for (int j = 0; j < R; ++j) {
                if (unlink_limits.has_value() && std::find(unlink_limits->begin(), unlink_limits->end(), j) != unlink_limits->end())
                    continue;
                r_in_degree[j]++;
            }
        }
 
        for (int j = 0; j < R; ++j) {
            int g = r_nodes_group[j];
            int cap = std::max(r_in_degree[j], 1);
            // First unit gets -nozzle_bonus to prefer using distinct nozzles
            m_solver->add_edge(L + j, L + R + g, 1, -nozzle_bonus);
            if (cap > 1)
                m_solver->add_edge(L + j, L + R + g, cap - 1, 0);
        }
 
        // group_g -> sink (split: first unit gets -bonus, rest gets 0)
        // bonus >> nozzle_bonus, so group coverage always takes priority
        for (int g = 0; g < G; ++g) {
            m_solver->add_edge(L + R + g, m_solver->sink_id, 1, -bonus);
            if (L > 1)
                m_solver->add_edge(L + R + g, m_solver->sink_id, L - 1, 0);
        }
    }

References flush_matrix, get_flush_cost(), L, l_nodes, m_solver, m_uv_link_limits, m_uv_unlink_limits, num_groups, r_nodes, and r_nodes_group.

Referenced by GroupMinCostFlowSolver().

Here is the call graph for this function:

Here is the caller graph for this function:

get_flush_cost()

int Slic3r::GroupMinCostFlowSolver::get_flush_cost ( int l_idx, int r_idx )

private

    {
        if (r_nodes[r_idx] == -1)
            return 0;
        int group_id = r_nodes_group[r_idx];
        return (int)flush_matrix[group_id][l_nodes[l_idx]][r_nodes[r_idx]];
    }

References flush_matrix, Slic3r::group_id(), l_nodes, r_nodes, and r_nodes_group.

Referenced by build_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

solve()

std::vector< int > Slic3r::GroupMinCostFlowSolver::solve

(

)

    {
        return m_solver->solve();
    }

References m_solver.

Referenced by Slic3r::plan_filament_nozzle_mapping_and_order().

Here is the caller graph for this function:

Member Data Documentation

flush_matrix

std::vector<FlushMatrix> Slic3r::GroupMinCostFlowSolver::flush_matrix

private

Referenced by GroupMinCostFlowSolver(), build_graph(), and get_flush_cost().

l_nodes

std::vector<int> Slic3r::GroupMinCostFlowSolver::l_nodes

private

Referenced by GroupMinCostFlowSolver(), build_graph(), and get_flush_cost().

m_solver

std::unique_ptr<MinCostMaxFlow> Slic3r::GroupMinCostFlowSolver::m_solver

private

Referenced by GroupMinCostFlowSolver(), build_graph(), and solve().

m_uv_link_limits

std::unordered_map<int, std::vector<int> > Slic3r::GroupMinCostFlowSolver::m_uv_link_limits

private

Referenced by GroupMinCostFlowSolver(), and build_graph().

m_uv_unlink_limits

std::unordered_map<int, std::vector<int> > Slic3r::GroupMinCostFlowSolver::m_uv_unlink_limits

private

Referenced by GroupMinCostFlowSolver(), and build_graph().

num_groups

int Slic3r::GroupMinCostFlowSolver::num_groups = 0

private

Referenced by GroupMinCostFlowSolver(), and build_graph().

r_nodes

std::vector<int> Slic3r::GroupMinCostFlowSolver::r_nodes

private

Referenced by GroupMinCostFlowSolver(), build_graph(), and get_flush_cost().

r_nodes_group

std::vector<int> Slic3r::GroupMinCostFlowSolver::r_nodes_group

private

Referenced by GroupMinCostFlowSolver(), build_graph(), and get_flush_cost().

---

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

• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/GCode/ToolOrderUtils.hpp
• /home/runner/work/OrcaSlicer/OrcaSlicer/src/libslic3r/GCode/ToolOrderUtils.cpp