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