Slic3r::MaxFlowWithLowerBounds Struct Reference

Collaboration diagram for Slic3r::MaxFlowWithLowerBounds:

Public Member Functions
void	add_edge (int from, int to, int capacity)
bool	bfs ()
int	dfs (int u, int f)
int	solve (std::vector< int > &matching)

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

Detailed Description

Member Function Documentation

add_edge()

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

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

References adj, and edges.

bfs()

bool Slic3r::MaxFlowWithLowerBounds::bfs

(

)

                                     {
        level.assign(total_nodes, -1);
        std::queue<int> q;
        q.push(source_id);
        level[source_id] = 0;
 
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int eid : adj[u]) {
                Edge &e = edges[eid];
                if (e.flow < e.capacity && level[e.to] == -1) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[sink_id] != -1;
    }

References adj, Slic3r::Edge::capacity, edges, Slic3r::Edge::flow, level, sink_id, source_id, Slic3r::Edge::to, and total_nodes.

Referenced by solve().

Here is the caller graph for this function:

dfs()

int Slic3r::MaxFlowWithLowerBounds::dfs	(	int	u,
		int	f )

                                                {
        if (u == sink_id) return f;
        for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
            int eid = adj[u][i];
            Edge &e = edges[eid];
            if (e.flow < e.capacity && level[e.to] == level[u] + 1) {
                int pushed = dfs(e.to, std::min(f, e.capacity - e.flow));
                if (pushed > 0) {
                    e.flow += pushed;
                    edges[eid ^ 1].flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

References adj, Slic3r::Edge::capacity, dfs(), edges, Slic3r::f(), Slic3r::Edge::flow, it, level, sink_id, and Slic3r::Edge::to.

Referenced by dfs(), and solve().

Here is the call graph for this function:

Here is the caller graph for this function:

solve()

int Slic3r::MaxFlowWithLowerBounds::solve

(

std::vector< int > &

matching

)

                                                              {
        int flow = 0;
        while (bfs()) {
            it.assign(total_nodes, 0);
            while (int pushed = dfs(source_id, MaxFlowGraph::INF))
                flow += pushed;
        }
 
        int L = l_nodes.size();
        int R = r_nodes.size();
        // collect l-r matches
        matching.resize(l_nodes.size(), MaxFlowGraph::INVALID_ID);
        for (int u = 0; u < L; ++u) {
            for (int eid : adj[u]) {
                Edge &e = edges[eid];
                if (e.flow > 0 && e.to >= L && e.to < L + R) {
                    matching[e.from] = e.to - L;
                }
            }
        }
        return flow;
    }

References adj, bfs(), dfs(), edges, Slic3r::Edge::flow, Slic3r::Edge::from, Slic3r::MaxFlowGraph::INF, Slic3r::MaxFlowGraph::INVALID_ID, it, L, l_nodes, r_nodes, source_id, Slic3r::Edge::to, and total_nodes.

Here is the call graph for this function:

Member Data Documentation

adj

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

Referenced by add_edge(), bfs(), dfs(), and solve().

edges

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

Referenced by add_edge(), bfs(), dfs(), and solve().

it

std::vector<int> Slic3r::MaxFlowWithLowerBounds::it

Referenced by dfs(), and solve().

l_nodes

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

Referenced by solve().

level

std::vector<int> Slic3r::MaxFlowWithLowerBounds::level

Referenced by bfs(), and dfs().

r_nodes

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

Referenced by solve().

sink_id

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

{ -1 };

Referenced by bfs(), and dfs().

source_id

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

{ -1 };

Referenced by bfs(), and solve().

total_nodes

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

{ -1 };

Referenced by bfs(), and solve().

---

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

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