GuillotineModels.Flow.Enumeration

Collection of the methods used for generating the graph representing the flow model.

An edge of the GuillotineModels.Flow Model.

• indx::Any

  Unique identifier of the edge in the model.

• head::Any

  The node from where the flow comes. Source.

• tail::Any

  The node from where the flow ends. Sink.

• back::Any

  The backward edge global index, if it exists, otherwise zero.

A node of the GuillotineModels.Flow model.

• idx::Any

  Unique identifier of the node in the model.

• par::Any

  The size of the plate dimension parallel to the cuts.

• per::Any

  The size of the plate dimension perpendicular to the cuts.

• ori::UInt8

  The cut orientation: one means vertical cuts; two means horizontal cuts.

gen_nodes_and_edges(N, E, d, l, w, L, W) :: ([Node], [Edge], N, E)

!!! Internal use.

Given the integer types used to number nodes and edges, the piece set, and the original plate length, create all nodes and edges except by some dummy ones (that are handled specially and, so, should not even be mixed here).

Notes

• This method is aware the edge identifiers 1 to n+4 are special.
• This method creates the special edges n+2 and n+4, but not any other in the 1:n+4 special identifier interval.

High-level procedure description

• Compute the discretized lengths (widths).
• For each discretized length (width), create a flow with max width (length).
• The backward edges in not-yet-reached flow B may be referred in currently-being-built flow A (a subplate edge from A may enable more flow to a backward edge in B). To solve this problem, a structure is passed around, it is a matrix of three dimensions, which may indexed by the values that are unique for a backward edge (pardim, cutori, per_dim), and stores the identifier for the unique backward edge with such attributes. If some forward edge created need to refer to a backward edge it is receives its identifier at that moment and is always referred by it, the corresponging Edge struct however, is only created at the final of the procedure, when all backward edges are known.
• Backward Edges are similar to waste edges in the fact both of they have the back field as zero (they never enable another backward edge), however only backward edges have tails pointing to the source nodes of flows (and, consequently, the only ones with tails before heads).

gen_closed_flow(...)

!!! Internal use.

Given some "global" structures/counters (last_gnode_idx, last_gedge_idx, lw2pii, ppo2gbedge_idx), the piece set (d, par, per) and the plate dimensions and its allowed cut orientation (ori, PAR, PER), this method builds the graph that represents all allowed cuts over such plate. The only changed parameter is ppo2gbedge_idx.

Arguments

• last_gnode_idx::N: The highest global node identifier already in use.
• last_gedge_idx::E: The highest global edge identifier already in use.
• lw2pii::AbstractArray{D, 2}: A convenient table that translates the dimensions of a piece to the global piece code if there exists a piece that fits the description. It is not changed but a transposition of it is made frequently.
• ppo2gbedge_idx::Array{E, 3}: A table that translates the parallel-perpendicular-orientation triple to the global backward edge index, if it exists. If there is the need to refer to a circulation edge but its global identifier does not yet exists, it is created and saved to the table.
• d::Vector{D}: The demand of the pieces.
• par::Vector{S}: The size of the pieces in the dimension that is parallel to the cuts made in this flow.
• per::Vector{S}: The size of the pieces in the dimension that is perpendicular to the cuts made in this flow.
• ori::UInt8: If it is one, the flow is making vertical cuts, and therefore par is l and per is w. If it is two, the flow is making horizontal cuts and therefore par is w and per is l.
• PAR::S: The size of the flow/plate in the dimension that is parallel to the cuts made.
• PER::S: The size of the flow/plate in the dimension that is perpendicular to the cuts made.

Returns

• A dense list of globalized nodes (all nodes in sequence).
• A sparse list of globalized nodes (if position y has a corresponding node, then v[y] == globalized_node_id, otherwise v[y] == 0).
• A dense list of the globalized edges.
• The index of the last globalized node (after the procedure).
• The index of the last globalized edge (after the procedure).

gen_rr_fow_edges!(::Type{N}, d :: [D], l :: [S], L :: S) :: ([N], [(S, S)])

!!! Internal use.

Arguments

An integer type capable of representing the nodes N. The pieces demand d, their length (or width) l, and a plate length (or width) L. This method assumes the selected pieces fit the selected plate (on both dimensions, this is, in the one that was given and the one that wasn't).

Return

A tuple of two vectors:

1. a vector v of length L; v[y] == 1 iff there is a linear combination of the pieces (respecting demand) that gives y; otherwise v[y] == 0.
2. a vector containing all ordered pairs of linear combinations in which the difference between the two is exactly the size of a piece.

gen_u_fow_edges(glo_nodes, y2node_idx, last_gedge_idx, ppo2gbedge_idx)

!!! Internal use.

This method generate the unrestricted subplate edges, i.e., the subplate edges representing a cut that creates a subplate in which the size of the dimension that is perpendicular to the cut is not the size of a single piece, but of a linear combination of them. Such edges are necessary to solve the unrestricted case but not to solve restricted case.

Arguments

• glo_nodes::Vector{Node{S, N}}: A list of globalized nodes from a single graph (asserts will fail if nodes are from different graphs).
• y2node_idx::Vector{N}: A vector in which !iszero(y2node_idx[y]) only if y is the per value of some node in glo_nodes and zero otherwise.
• last_gedge_idx::E: The highest global edge identifier already in use.
• ppo2gbedge_idx::Array{E, 3}: A table that translates the parallel-perpendicular-orientation triple to the global backward edge index, if it exists. If there is the need to refer to a circulation edge but its global identifier does not yet exists, it is created and saved to the table.

Procedure

Loop through all pairs i and j (i < j) of node indexes (not counting a possibly dummy sink node, but counting the source node), create a edge between the two nodes if glo_nodes[j].per - glo_nodes[i].per <= glo_nodes[i].per.

Returns

1. The list of new edges, already globalized.
2. The last edge index attributed.

gen_w_fow_edges(glo_nodes, last_gedge_idx) :: ([Edge], E)

!!! Internal use.

Given a set of "globalized" nodes, and the index of the last "globalized" edge, create the set of corresponding waste edges (already "globalized").

For now, it is not very smart and just connect the second node to the third, third to the fourth, and so on. Ideally, it should connect every node (except the first) to the next node that has a backward edge associated (not counting the node in question, clearly, no self-loops allowed).

globalize!(see description and source for parameters and return)

!!! Internal use.

The model may be seen as constituted of many independent graphs, but as there is interaction between them (i.e., subplate edges increase the flow of a backward edge in other graph) their nodes and edges must follow a global numbering and the backward edges must be known by all of graphs (as subplate edges need to refer to them as child plates).

This method takes the "local/raw" lists of node (y2node_idx) and edge (raw_fow_edges) numbering (that is just the normal cut positions); the index of the last globalized node (last_gnode_idx) and edge (last_gedge_idx); a matrix that gives the piece index given the piece dimensions (lw2pii); a tridimensional array that gives the backward edge index given its plate dimensions and allowed cut orientation (ppo2gbedge_idx); the allowed cut orientation of the given graph; and the size of the plate dimension parallel to the allowed cuts (PAR).

The method return the "globalized" list of nodes and edges, as the index of the last globalized node and edge.

The method changes ppo2gbedge_idx: if a subplate (forward) edge is created and the corresponding backward edge was not yet numbered, it is given a "globalized" index (all backward edges are created at another step at the end).

merge_duplicates(d :: [D], per :: [S]) :: ([D], [S])

!!! Internal use.

If per has no repeated values just return the parameters. Otherwise, for each value in per with duplicates, keep just one copy of such value inside per and delete the other copies, and the same positions in d; the position in d corresponding to the kept copy will have the sum of the d values for all copies deleted and the copy kept. Sort per by increasing value and swap positions in d to keep the correspondence.

reduce_dlw(d::[D], l::[S], w::[S], L::S, W::S) :: ([D], [S], [S], D)

!!! Internal use.

Create a copy of d, l, and w with only the pieces that fit the plate L x W (i.e., pieces with both dimensions smaller than the corresponding plate dimension). The last value returned is the number of pieces that pass this criteria (and, consequently, the common size of the returned vectors).