I have developed a tentative first version of a new graph type, which is a tree with cross-edges. I.e., you have a graph which is basically a tree, but where you are allowed to have cross edges. The cross edges are NOT the same as graph edges, and in particular, don't cause additions to the PARENT/CHILD relationships, nor (for this reason) do they cause depths to be incremented. Note that these cross-edges do NOT have to be only one one level of the tree --- they can cross levels. To build such a graph you need to add two more arguments to format-graph-from-roots:
:CROSS-ARC-DRAWER
a function that takes all the arguments accepted by a normal arc-drawer, but also an edge-type keyword argument, which it is free to ignore.
:CROSS-ARC-PRODUCER
a function that takes a graph-node as argument, like inferior-producer, but that returns two values: a list of destination nodes and (optionally) a list of type-designators, that can be passed to the cross-arc-drawer, as the value of the :edge-type keyword argument.
I have posted the source for this to the following URL, hoping that it will attract comments and suggestions:
http://rpgoldman.real-time.com/lisp/tree-with-cross-edges.lisp
I'd love to see this integrated into McCLIM some day!
KNOWN BUGS:
1. Currently only works on :horizontal orientation (I don't have the arc routing for vertical yet).
2. Only draws straight lines for cross edges. It would be nice if the cross edges would swoop around intervening nodes, but I haven't read enough of the CLIM spec to figure out how to do this yet.
3. If you have a depth-bounded tree, probably something very ugly will happen!
I'll try to assemble some screendumps and post them, but for now it's weekend...
Best, R