Re: [Groff] [groff] Formatting algorithm

[Ulrich Lauther]

On Fri, May 09, 2014 at 01:12:14PM +0100, Roger Leigh wrote:
> On Fri, May 09, 2014 at 01:07:02PM +0200, Ulrich Lauther wrote:
> > On Fri, May 09, 2014 at 10:48:08AM +0100, Denis M. Wilson wrote:
> > > The method used in TeX is the shortest path in a directed acyclic graph.
> > > This is a well-understood problem. There seems unfortunately to be
> > > nothing useful in the STL. The DAG would need to be a new data type.
> > > 
> > To build and use a DAG we need - in general - a node-object and an 
> > edge-object.
> > The node contains a list of outgoing edges, the edge points to its target 
> > node
> > and contains its length (or cost).
> 
> The Boost Graph Library (BGL) does all this and has algorithms for
> searching, traversal etc.  The nodes and edges are templated and you
> can attach arbitrary data to them.  This might not be a dependency
> you'd want in groff, but just mentioning it in case it's potentially
> useful.
> 
Yes, I know. The same holds for LEDA and the TURBO-library developed by myself 
(unfortunately proprietory).
But the needed data structures are so simple that dragging in another library 
seems overkill.
> 
> Regards,

  ulrich