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

Collaboration diagram for Slic3r::MaxFlowSolver:

Public Member Functions
	MaxFlowSolver (const std::vector< int > &u_nodes, const std::vector< int > &v_nodes, const std::unordered_map< int, std::vector< int > > &uv_link_limits={}, const std::unordered_map< int, std::vector< int > > &uv_unlink_limits={}, const std::vector< int > &u_capacity={}, const std::vector< int > &v_capacity={}, const std::vector< std::pair< std::set< int >, int > > &v_group_capacity={})
std::vector< int >	solve ()

Private Member Functions
void	add_edge (int from, int to, int capacity)

Private Attributes
int	total_nodes
int	source_id
int	sink_id
std::vector< Edge >	edges
std::vector< int >	l_nodes
std::vector< int >	r_nodes
std::vector< std::vector< int > >	adj

Detailed Description

Constructor & Destructor Documentation

◆ MaxFlowSolver()

Slic3r::MaxFlowSolver::MaxFlowSolver	(	const std::vector< int > &	u_nodes,
		const std::vector< int > &	v_nodes,
		const std::unordered_map< int, std::vector< int > > &	uv_link_limits = {},
		const std::unordered_map< int, std::vector< int > > &	uv_unlink_limits = {},
		const std::vector< int > &	u_capacity = {},
		const std::vector< int > &	v_capacity = {},
		const std::vector< std::pair< std::set< int >, int > > &	v_group_capacity = {} )

    {
        assert(u_capacity.empty() || u_capacity.size() == u_nodes.size());
        assert(v_capacity.empty() || v_capacity.size() == v_nodes.size());
        l_nodes = u_nodes;
        r_nodes = v_nodes;
        total_nodes = u_nodes.size() + v_nodes.size() + v_group_capacity.size() + 2;
        source_id = total_nodes - 2;
        sink_id = total_nodes - 1;
 
        adj.resize(total_nodes);
 
        std::vector<int>v_node_to(v_nodes.size(), sink_id);
        for (size_t gid = 0; gid < v_group_capacity.size(); ++gid) {
            for (auto vid : v_group_capacity[gid].first)
                v_node_to[vid] = l_nodes.size() + r_nodes.size() + gid;
        }
 
        // add edge from source to left nodes
        for (int idx = 0; idx < l_nodes.size(); ++idx) {
            int capacity = u_capacity.empty() ? 1 : u_capacity[idx];
            add_edge(source_id, idx, capacity);
        }
        // add edge from right nodes to v_node_to(sink node or temp group node)
        for (int idx = 0; idx < r_nodes.size(); ++idx) {
            int capacity = v_capacity.empty() ? 1 : v_capacity[idx];
            add_edge(l_nodes.size() + idx, v_node_to[idx], capacity);
        }
 
        // add edge from temp group node to sink node
        for (int idx = 0; idx < v_group_capacity.size(); ++idx) {
            int capacity = v_group_capacity[idx].second;
            add_edge(l_nodes.size() + r_nodes.size() + idx, sink_id, capacity);
        }
 
        // add edge from left nodes to right nodes
        for (int i = 0; i < l_nodes.size(); ++i) {
            int from_idx = i;
            // process link limits , i can only link to uv_link_limits
            if (auto iter = uv_link_limits.find(i); iter != uv_link_limits.end()) {
                for (auto r_id : iter->second)
                    add_edge(from_idx, l_nodes.size() + r_id, 1);
                continue;
            }
            // process unlink limits
            std::optional<std::vector<int>> unlink_limits;
            if (auto iter = uv_unlink_limits.find(i); iter != uv_unlink_limits.end())
                unlink_limits = iter->second;
 
            for (int j = 0; j < r_nodes.size(); ++j) {
                // check whether i can link to j
                if (unlink_limits.has_value() && std::find(unlink_limits->begin(), unlink_limits->end(), j) != unlink_limits->end())
                    continue;
                add_edge(from_idx, l_nodes.size() + j, 1);
            }
        }
    }

References add_edge(), adj, l_nodes, r_nodes, sink_id, source_id, and total_nodes.

Here is the call graph for this function:

Member Function Documentation

◆ add_edge()

void Slic3r::MaxFlowSolver::add_edge	(	int	from,
		int	to,
		int	capacity )

private

    {
        adj[from].emplace_back(edges.size());
        edges.emplace_back(from, to, capacity);
        //also add reverse edge ,set capacity to zero
        adj[to].emplace_back(edges.size());
        edges.emplace_back(to, from, 0);
    }

References adj, and edges.

Referenced by MaxFlowSolver().

Here is the caller graph for this function:

◆ solve()

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

                                        {
        std::vector<int> augment;
        std::vector<int> previous(total_nodes, 0);
        while (1) {
            std::vector<int>(total_nodes, 0).swap(augment);
            std::queue<int> travel;
            travel.push(source_id);
            augment[source_id] = MaxFlowGraph::INF;
            while (!travel.empty()) {
                int from = travel.front();
                travel.pop();
 
                // traverse all linked edges
                for (int i = 0; i < adj[from].size(); ++i) {
                    int eid = adj[from][i];
                    Edge& tmp = edges[eid];
                    if (augment[tmp.to] == 0 && tmp.capacity > tmp.flow) {
                        previous[tmp.to] = eid;
                        augment[tmp.to] = std::min(augment[from], tmp.capacity - tmp.flow);
                        travel.push(tmp.to);
                    }
                }
 
                // already find an extend path, stop and do update
                if (augment[sink_id] != 0)
                    break;
            }
            // no longer have extend path
            if (augment[sink_id] == 0)
                break;
 
            for (int i = sink_id; i != source_id; i = edges[previous[i]].from) {
                edges[previous[i]].flow += augment[sink_id];
                edges[previous[i] ^ 1].flow -= augment[sink_id];
            }
        }
 
        std::vector<int> matching(l_nodes.size(), MaxFlowGraph::INVALID_ID);
        // to get the match info, just traverse the left nodes and
        // check the edge with flow > 0 and linked to right nodes
        for (int u = 0; u < l_nodes.size(); ++u) {
            for (int eid : adj[u]) {
                Edge& e = edges[eid];
                if (e.flow > 0 && e.to >= l_nodes.size() && e.to < l_nodes.size() + r_nodes.size())
                    matching[e.from] = r_nodes[e.to - l_nodes.size()];
            }
        }
        return matching;
    }