Slic3r::MinCostMaxFlow Struct Reference

Collaboration diagram for Slic3r::MinCostMaxFlow:

Public Member Functions
std::vector< int >	solve ()
void	add_edge (int from, int to, int capacity, int cost)
bool	spfa (int source, int sink)
int	get_distance (int idx_in_left, int idx_in_right)

Public Attributes
std::vector< std::vector< float > >	matrix
std::vector< int >	l_nodes
std::vector< int >	r_nodes
std::vector< Edge >	edges
std::vector< std::vector< int > >	adj
int	total_nodes { -1 }
int	source_id { -1 }
int	sink_id { -1 }

Detailed Description

Member Function Documentation

add_edge()

void Slic3r::MinCostMaxFlow::add_edge	(	int	from,
		int	to,
		int	capacity,
		int	cost )

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

References adj, and edges.

get_distance()

int Slic3r::MinCostMaxFlow::get_distance	(	int	idx_in_left,
		int	idx_in_right )

    {
        if (l_nodes[idx_in_left] == -1) {
            return 0;
        }
 
        float val = matrix[l_nodes[idx_in_left]][r_nodes[idx_in_right]];
        return std::min(static_cast<int>(val), MaxFlowGraph::MCMF_MAX_EDGE_COST);
    }

References l_nodes, matrix, Slic3r::MaxFlowGraph::MCMF_MAX_EDGE_COST, and r_nodes.

solve()

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

(

)

    {
        while (spfa(source_id, 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 edges 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;
    }

References adj, edges, Slic3r::Edge::flow, Slic3r::Edge::from, Slic3r::MaxFlowGraph::INVALID_ID, l_nodes, r_nodes, sink_id, source_id, spfa(), and Slic3r::Edge::to.

Here is the call graph for this function:

spfa()

bool Slic3r::MinCostMaxFlow::spfa	(	int	source,
		int	sink )

    {
        std::vector<int>dist(total_nodes, MaxFlowGraph::INF);
        std::vector<bool>in_queue(total_nodes, false);
        std::vector<int>flow(total_nodes, MaxFlowGraph::INF);
        std::vector<int>prev(total_nodes, 0);
 
        std::queue<int>q;
        q.push(source);
        in_queue[source] = true;
        dist[source] = 0;
 
        while (!q.empty()) {
            int now_at = q.front();
            q.pop();
            in_queue[now_at] = false;
 
            for (auto eid : adj[now_at]) //traverse all linked edges
            {
                Edge& e = edges[eid];
                if (e.flow<e.capacity && dist[e.to]>dist[now_at] + e.cost) {
                    dist[e.to] = dist[now_at] + e.cost;
                    prev[e.to] = eid;
                    flow[e.to] = std::min(flow[now_at], e.capacity - e.flow);
                    if (!in_queue[e.to]) {
                        q.push(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }
 
        if (dist[sink] == MaxFlowGraph::INF)
            return false;
 
        int now_at = sink;
        while (now_at != source) {
            int prev_edge = prev[now_at];
            edges[prev_edge].flow += flow[sink];
            edges[prev_edge ^ 1].flow -= flow[sink];
            now_at = edges[prev_edge].from;
        }
 
        return true;
    }

References adj, Slic3r::Edge::capacity, Slic3r::Edge::cost, Slic3r::Geometry::dist(), edges, Slic3r::Edge::flow, Slic3r::MaxFlowGraph::INF, Slic3r::Edge::to, and total_nodes.

Referenced by solve().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

adj

std::vector<std::vector<int> > Slic3r::MinCostMaxFlow::adj

Referenced by add_edge(), solve(), and spfa().

edges

std::vector<Edge> Slic3r::MinCostMaxFlow::edges

Referenced by add_edge(), solve(), and spfa().

l_nodes

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

Referenced by get_distance(), and solve().

matrix

std::vector<std::vector<float> > Slic3r::MinCostMaxFlow::matrix

Referenced by get_distance().

r_nodes

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

Referenced by get_distance(), and solve().

sink_id

int Slic3r::MinCostMaxFlow::sink_id { -1 }

{ -1 };

Referenced by solve().

source_id

int Slic3r::MinCostMaxFlow::source_id { -1 }

{ -1 };

Referenced by solve().

total_nodes

int Slic3r::MinCostMaxFlow::total_nodes { -1 }

{ -1 };

Referenced by spfa().

---

The documentation for this struct was generated from the following file:

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