# TeX's algorithms for “breaking paragraph into lines” and “setting the glue”

After scanning through ch.12 of Knuth's TeXbook, I'm guessing that setting the glue must consist in a constrained linear program

• whose variables represent the interword glue, and
• whose constraints correspond to shrinks & stretches allowed for each interword glue.

However, if my intuition is correct, the linear program in question must get prohibitively large pretty quickly as the length of the document increases, at least, for computers back in the day. Does setting the glue use some heuristic instead?

EDIT: Thanks to egreg for his answer. However, I realise I should have included the paragraph-making algorithm in my question.

I'm still not quite clear on the interplay between

• the paragraph-making algorithm (which, I presume, determines where line breaks occur), and
• the text-justification algorithm (which determines the interword glue).

It seems to me that the two problems are not independent. Does the paragraph-making algorithm, in the process of generating line break after line break, not use information about each glue item (natural width, stretch and shrink components), too?

• TeX operates on lists; the glue items are just stored in the lists with their dimensions. Setting the glue is just a simple operation: sum up the stretch or shrink components, look whether the glue has to be stretched or shrinked and how much, then divide the amount proportionally among each item. See tex.stackexchange.com/a/19218/4427 – egreg Apr 20 '13 at 14:09
• Maybe this piece of information will be useful for you: gust.org.pl/bachotex/2010/program (Jan Šustek, Ostrava, Czech Republik Details of the TeX line-breaking algorithm). – Przemysław Scherwentke Apr 20 '13 at 14:45
• The tex paragraph-building algorithm works by dynamic programming and is described in Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102 The fact that it uses dynamic programming limits some of the types of penalties that can be implemented, but allows a much more efficient solution compared to a general linear program. – Lev Bishop Apr 20 '13 at 19:00
• @LevBishop Thanks for the reference, which looks really interesting; I will read it. If you have already read it, would you mind elaborating a bit on your comment and write a full-fledged answer? I might change my mind on which answer is most deserving of my "accepted answer" tick mark :) – jub0bs Apr 20 '13 at 19:16

There's no linear programming involved.

TeX stores items in lists (vertical, horizontal or math lists). Math lists are converted to horizontal lists, so only the first two must be discussed, but they are alike when setting the glue is involved.

Glue is stored as a glue item, represented with its natural width, stretch component and shrink component.

When TeX has to build a box having a certain width from a horizontal list or a certain height from a vertical list (lines in a paragraph or a page, for instance), it sums up all the natural widths, adds the width of the non-glue items and computes how much the glue has to be stretched or shrinked.

If stretching s is required and t total stretch is available, TeX computes the "stretch ratio" r = s/t; and if a glue item has x stretch component, TeX adds rx to the natural width.

The situation is similar for shrinking, with the difference that TeX will never go below the stated shrinking and will output an overfull box if the total shrinking available is not sufficient.

There is a little complication because stretching or shrinking can be expressed in "infinite units". Well, the computation of the total stretching or shrinking available keeps the higher order of infinity resulting from the computation and adds (or removes) from the natural width only to the glue items which match that order of infinity in their specification.

These are very easy and fast operations on any computer.

The paragraph making algorithm takes into account stretchability and shrinkability of the glue items in the horizontal list it has built only in an indirect way.

Glue items mark feasible line break points, provided they are preceded by a non-discardable item (also other items mark feasible breaks). During this phase TeX looks at the natural widths of the items and, to put it simply, chooses a sequence of break points such that no line will exceed the current \hsize.

Actually this choice is based on many parameters, on penalties found in the list (or implicit penalties) and on computed demerits. Possible break points are also discretionary hyphens that may have been automatically inserted during the process.

For each feasible break point, TeX computes the glue ratio for the line that would result, which assigns a badness to the line that will be used in the computation of the total demerits. However glue is not set at this point, but only when TeX has chosen the best sequence of break points (the best according to its rules and the values of the various involved parameters): the lines are put in hboxes of width \hsize, essentially \hbox to \hsize{...} and now the glue is set as explained above.

• The "higher order of infinity" is not actually infinity, but something like 10000 versus 10000^2 IIRC, right? – ShreevatsaR Apr 21 '13 at 3:28
• @ShreevatsaR No, you're thinking of penalties. For infinite glue (fil, fill, filll) TeX simply ignores any stretch/shrink components of less infinite rank, following the rule "infinity plus one equals infinity" (or perhaps, it applies the rule "one over infinity equals zero" in the ratios r). – Ryan Reich Apr 21 '13 at 14:45

The tex paragraph-building algorithm works by dynamic programming and is described in Knuth, Donald E.; Plass, Michael F. (1981), "Breaking paragraphs into lines", Software: Practice and Experience 11 (11): 1119–1184, doi:10.1002/spe.4380111102. The fact that it uses dynamic programming limits some of the types of penalties that can be implemented, but allows a much more efficient solution compared to a general linear program.

Dynamic programming basically means that you set up the problem so that the optimal solution can be built from optimal solutions of its subproblems. This allows discarding suboptimal solutions at each stage and thus no need to ever backtrack. In a simplified version of Knuth/Plass you can think of a directed acyclic graph G=(V,E) with vertices v0,v1,v2...vn representing possible places to insert a linebreak in a paragraph (v0 immediately before the first word of the paragraph and vn immediately after the last word), and edges e0,e1,...,em carrying a weight representing the "badness" of setting a line between a pair of linebreaks. The badness comes from how much the space needs to stretch/shrink and also includes penalties such as for undesirable hyphenations. The problem is to find the minimum weight path on G from v0 to vn, and this is a classic case for the use of dynamic programming, eg Dijkstra's algorithm. The full Knuth/Plass algorithm adds a few refinements (such as quadrupling the set of vertices by adding a looseness label 0..3 to each vertex) without losing the advantage of dynamic programming, and has some tweaks for efficiency (for example not looking for breaks in places where they can't be useful, and only determining hyphenation points if it is not possible to get a good paragraph without hyphenation).