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

Collaboration diagram for Slic3r::GeneralMinCostLowerBoundsSolver:

Classes
struct	LowerBoundEdge

Public Member Functions
	GeneralMinCostLowerBoundsSolver (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 ()
	~GeneralMinCostLowerBoundsSolver ()

Private Member Functions
void	build_feasible_graph (const std::unordered_set< int > &no_lower_groups)
void	build_graph_with_feasible_result ()
void	add_edge_with_lower_bound (int from, int to, int lower, int upper, int cost)
int	get_distance (const int idx_in_left, const int idx_in_right)

Private Attributes
std::unique_ptr< MaxFlowWithLowerBounds >	m_solver_lower_bounds
std::unique_ptr< MinCostMaxFlow >	m_solver_min_cost
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
std::vector< int >	demand
std::vector< LowerBoundEdge >	lower_bound_edges
int	super_source = -1
int	super_sink = -1
int	source_id = -1
int	sink_id = -1
int	max_flow_edges = 0

Detailed Description

Class Documentation

◆ Slic3r::GeneralMinCostLowerBoundsSolver::LowerBoundEdge

struct Slic3r::GeneralMinCostLowerBoundsSolver::LowerBoundEdge

Class Members
int	edge_id
int	lower

Constructor & Destructor Documentation

◆ GeneralMinCostLowerBoundsSolver()

Slic3r::GeneralMinCostLowerBoundsSolver::GeneralMinCostLowerBoundsSolver	(	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_lower_bounds = std::make_unique<MaxFlowWithLowerBounds>();
        m_solver_min_cost = std::make_unique<MinCostMaxFlow>();
    }

References flush_matrix, l_nodes, m_solver_lower_bounds, m_solver_min_cost, m_uv_link_limits, m_uv_unlink_limits, num_groups, r_nodes, and r_nodes_group.

◆ ~GeneralMinCostLowerBoundsSolver()

Slic3r::GeneralMinCostLowerBoundsSolver::~GeneralMinCostLowerBoundsSolver ( )

default

Member Function Documentation

◆ add_edge_with_lower_bound()

void Slic3r::GeneralMinCostLowerBoundsSolver::add_edge_with_lower_bound	(	int	from,
		int	to,
		int	lower,
		int	upper,
		int	cost )

private

    {
        int eid = m_solver_lower_bounds->edges.size();
        m_solver_lower_bounds->add_edge(from, to, upper - lower);
 
        lower_bound_edges.push_back({eid, lower});
        demand[from] -= lower;
        demand[to]   += lower;
    }

References demand, lower_bound_edges, and m_solver_lower_bounds.

Referenced by build_feasible_graph().

Here is the caller graph for this function:

◆ build_feasible_graph()

void Slic3r::GeneralMinCostLowerBoundsSolver::build_feasible_graph ( const std::unordered_set< int > & no_lower_groups )

private

    {
        m_solver_lower_bounds->l_nodes = l_nodes;
        m_solver_lower_bounds->r_nodes = r_nodes;
        m_solver_lower_bounds->total_nodes = l_nodes.size() + r_nodes.size() + num_groups + 2;
 
        m_solver_lower_bounds->source_id = m_solver_lower_bounds->total_nodes - 2;
        m_solver_lower_bounds->sink_id   = m_solver_lower_bounds->total_nodes - 1;
        m_solver_lower_bounds->adj.resize(m_solver_lower_bounds->total_nodes);
        demand.resize(m_solver_lower_bounds->total_nodes, 0);
 
        const int L = m_solver_lower_bounds->l_nodes.size();
        const int R = m_solver_lower_bounds->r_nodes.size();
 
        // source -> l
        for (int i = 0; i < L; ++i)
            m_solver_lower_bounds->add_edge(m_solver_lower_bounds->source_id, i, 1);
 
        // u -> v (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_lower_bounds->add_edge(i, L + j, 1);
                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_lower_bounds->add_edge(i, L + j, 1);
            }
        }
 
        // r -> group
        for (int j = 0; j < R; ++j) {
            int g = r_nodes_group[j];
            m_solver_lower_bounds->add_edge(L + j, L + R + g, 1);
        }
 
        // group -> sink (lower bound = 1)
        for (int g = 0; g < num_groups; ++g) {
            if (no_lower_groups.count(g))
                m_solver_lower_bounds->add_edge(L + R + g, m_solver_lower_bounds->sink_id, R);
            else
                add_edge_with_lower_bound(L + R + g, m_solver_lower_bounds->sink_id, 1, R, 0);
        }
 
        max_flow_edges = m_solver_lower_bounds->edges.size();
 
        // support lower bounds, add super source  super sink
        super_source = m_solver_lower_bounds->total_nodes++;
        super_sink = m_solver_lower_bounds->total_nodes++;
 
        m_solver_lower_bounds->adj.resize(m_solver_lower_bounds->total_nodes);
        demand.resize(m_solver_lower_bounds->total_nodes, 0);
 
        for (int i = 0; i < super_source; ++i) {
            if (demand[i] > 0) {
                m_solver_lower_bounds->add_edge(super_source, i, demand[i]);
            } else if (demand[i] < 0) {
                m_solver_lower_bounds->add_edge(i, super_sink, -demand[i]);
            }
        }
        m_solver_lower_bounds->add_edge(m_solver_lower_bounds->sink_id, m_solver_lower_bounds->source_id, MaxFlowGraph::INF);
        source_id = m_solver_lower_bounds->source_id;
        sink_id = m_solver_lower_bounds->sink_id;
        m_solver_lower_bounds->source_id = super_source;
        m_solver_lower_bounds->sink_id = super_sink;
    }

References add_edge_with_lower_bound(), demand, Slic3r::MaxFlowGraph::INF, L, l_nodes, m_solver_lower_bounds, m_uv_link_limits, m_uv_unlink_limits, max_flow_edges, num_groups, r_nodes, r_nodes_group, sink_id, source_id, super_sink, and super_source.

Referenced by solve().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build_graph_with_feasible_result()

void Slic3r::GeneralMinCostLowerBoundsSolver::build_graph_with_feasible_result ( )

private

    {
        for (auto&lb:lower_bound_edges){
            m_solver_lower_bounds->edges[lb.edge_id].flow += lb.lower;
            m_solver_lower_bounds->edges[lb.edge_id ^ 1].flow -= lb.lower;
        }
 
        m_solver_min_cost->l_nodes = m_solver_lower_bounds->l_nodes;
        m_solver_min_cost->r_nodes = m_solver_lower_bounds->r_nodes;
 
        m_solver_min_cost->source_id = source_id;
        m_solver_min_cost->sink_id = sink_id;
        m_solver_min_cost->total_nodes = sink_id + 1;
 
        m_solver_min_cost->edges = m_solver_lower_bounds->edges;
        m_solver_min_cost->edges.erase(m_solver_min_cost->edges.begin() + max_flow_edges, m_solver_min_cost->edges.end());
 
        m_solver_min_cost->adj = m_solver_lower_bounds->adj;
        m_solver_min_cost->adj.resize(m_solver_min_cost->total_nodes);
        for (auto &node_edges : m_solver_min_cost->adj) {
            node_edges.erase(std::remove_if(node_edges.begin(), node_edges.end(), [this](int val) {return val >= this->max_flow_edges;}), node_edges.end());
        }
 
 
        for (auto& e : m_solver_min_cost->edges) {
            int L            = m_solver_min_cost->l_nodes.size();
            int R            = m_solver_min_cost->r_nodes.size();
 
            if (e.from < L && e.to >= L && e.to < L + R) {
                int idx_in_left  = e.from;
                int idx_in_right = e.to - L;
                int group_id = r_nodes_group[idx_in_right];
 
                if (r_nodes[idx_in_right] == -1) continue;
                e.cost = flush_matrix[group_id][l_nodes[idx_in_left]][r_nodes[idx_in_right]];
            }
        }
    }

References flush_matrix, Slic3r::group_id(), L, l_nodes, lower_bound_edges, m_solver_lower_bounds, m_solver_min_cost, max_flow_edges, r_nodes, r_nodes_group, sink_id, and source_id.

Referenced by solve().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_distance()

int Slic3r::GeneralMinCostLowerBoundsSolver::get_distance	(	const int	idx_in_left,
		const int	idx_in_right )

private

◆ solve()

std::vector< int > Slic3r::GeneralMinCostLowerBoundsSolver::solve ( )

    {
        // group nodes that do not need a lower-bound constraint
        std::unordered_set<int> no_lower_group;
        for (int i = 0; i < r_nodes.size(); i++) {
            if (r_nodes[i] >= 0)
                no_lower_group.insert(r_nodes_group[i]);
        }
 
        // 1. build the lower-bound network graph
        build_feasible_graph(no_lower_group);
 
        // 2. compute the max flow
        int need = 0;
        for (int d : demand)
            if (d > 0) need += d;
        std::vector<int> feasible_matching;
        int pushed_flow = m_solver_lower_bounds->solve(feasible_matching);
        assert(need == pushed_flow);
 
        // 3. convert the lower-bound max-flow network into a min-cost-max-flow network
        build_graph_with_feasible_result();
        // 4. compute the min-cost max-flow
        auto min_cost_matching = m_solver_min_cost->solve();
 
        return min_cost_matching;
    }