Re: Routing Library

[Lars Clausen <lars raeder dk>]

On Mon, 2007-05-14 at 15:28 -0500, David Barnett wrote:
> Hello,
>
> I just joined this list, so pardon me if I'm a little ignorant of how
> things work here. I don't know much about the dia code, either.
>
> I've had the urge many times to create a tree- or graph-oriented 
> application with intelligent autorouting and usually some drag-n-drop
> functionality. Sometimes I just want a quick solution so that I can
> easily see the data structures in a program to debug it. But I've
> searched a lot and it seems like to get that kind of functionality,
> I'd
> either have to hack something very specific like diacanvas or build it
> from scratch on a GTK+ canvas. I'm not sure if graphviz would
> help...I've seen it and some other libraries that looked promising at
> first, but they don't seem to be very versatile or suited for
> drag-n-drop apps. I've also looked for applications with similar
> interfaces, and everything I've found looks like it was built from
> the 
> ground up.

One "quick hack" road would be to combine AutoDia, graphviz and Dia.
AutoDia to extract the graph from source, graphviz to do layout, Dia for
manual fixes and labelling.

> I think it would be quite feasible to make a library designed to
> encapsulate the issues of routing edges, searching for optimal paths,
> and also finding the optimal arrangement of nodes (if desired) into a 
> library with extremely fine-grained control over behavior parameters,
> both globally and for individual nodes and edges.  For instance, the
> style of edges (direct, orthogonal, etc.), shape and size of nodes,
> workspace size and off-limits regions could be specified. 

You can see what Dia has in the area in lib/autoroute.c, it's pretty
basic.  We have no autolayout at all.  Accounting for strange shapes of
nodes and different kinds of edges did end up making it somewhat complex
compared to what it achieves.  I'd love to ship that part off to a
library.

> My plan was to create a library to plan the actual edge paths which
> could be used in any environment, and a GTK+ widget to use that
> library
> and add a ton of interaction behavior. It might also be a good idea
> to 
> include a plugin system for the core library, since the actual routing
> needs to take a ton of factors into account, such as maximizing
> parallel edges or having a labeled "shortcut" when the path is too 
> cluttered; but I'm not sure about that detail, because it seems like
> it
> might be overkill.

A frequently requested feature is some marking of crossing lines, which
may fall under the purvey of plugins.

> I think a lot of free applications in fields like circuit design, UML
> modeling, and tons of others would benefit from this effort, possibly 
> including dia on some level (I saw "better autorouting" on the Google
> SoC wishlist), so I want it to be very flexible and support many
> graphics toolkits and programming languages.
>
> I don't know if I'll be able to take the idea very far, but I
> wondered 
> (a) if I was mistaken thinking no such library already exists or (b)
> if I'm not alone thinking such a project would be useful.

I agree it would be useful, and if it exists already, I'd like to know
so I can use it.  

-Lars