Re: [Groff] [groff] Formatting algorithm

[Roger Leigh]

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.


Regards,
Roger

-- 
  .''`.  Roger Leigh
 : :' :  Debian GNU/Linux    http://people.debian.org/~rleigh/
 `. `'   schroot and sbuild  http://alioth.debian.org/projects/buildd-tools
   `-    GPG Public Key      F33D 281D 470A B443 6756 147C 07B3 C8BC 4083 E800