On Mon, Oct 27, 2008 at 06:00:06PM +0000, Vincent Hennebert wrote:
> Hi,
> 
> 
> [from another post]
> > A really strange thing: is it theoretically possible that the amount 
> > of active nodes is greater than the number of knuth elements? As you 
> > can see in the graph, for short lines there are >14000 active nodes 
> > but only ~7000 knuth elements...
> 
> Line breaking is a bin-packing problem [2], so the potential number of
> active nodes is exponential to the number of words you have in your
> paragraph. So, yes, it???s normal to have more active nodes than elements
> in the sequence.

Each feasible breakpoint can have 4 nodes, one for each line class. If
half of the Knuth elements are legal breakpoints (a simple sequence of
box - glue), then there could be at most 4 * 3500 nodes.

Note that you are using the term active node in the wrong sense,
viz. the set of nodes kept by the program. Active nodes are the subset
of those nodes that participate in the inner loop. Indeed, all nodes
were active at some point.

Regards, Simon

-- 
Simon Pepping
home page: http://www.leverkruid.eu

Reply via email to