Project to add repulsive curve layout to graphviz

Based on some discussion in, uh, Twitter , Keenan Crane at CMU asked about having a student add this curved edge fitting algorithm to graphviz.

See figure 26 in the PDF.

Keenan asked about our developer documentation and if we have efficient spatial/geometric data structures they may be able to re-use. I don’t think we have a good story there but let me know if I’m wrong.

Also if Keenan finds a student to work on this, we would be looking for guidance about how to structure this work, to avoid making an intern-sized pull request, as some would say :slight_smile:


As for spatial toolkits, I’m not sure what he wants but we probably don’t have it. We have an implementation of Fortune’s Voronoi algorithm, and we assume the GTS library has been installed. And some basic computational geometry things.

As for integrating this into Graphviz, it would go with the other edge routing algorithms (spline, line, polyline, orthogonal) in the neato library. (It’s not clear how this would fit into the dot layout.) We would create a new type of edge. The code would switch on that type and do its thing. I can point out exactly where this occurs in the code when the time comes. Based on figure 26, this routing is different from the others in that it seems to also move the nodes as well as computing the edge layouts. That shouldn’t be a problem for non-dot layouts.

The implementer can best determine how to incrementally introduce the code, probably starting with new types, auxiliary functions, etc. From our standpoint, the whole thing should probably be done as a separate library, as we currently handle various parts of neato/sfdp. At the global level, the code would be entirely isolated until the new edge type is introduced into the switch statement.

I hope they can accommodate nodes at fixed locations. What about the SIGGRAPH bunny filled with spaghetti - the bunny is fixed, right?

Would be nice to get some new blood on the Graphviz team :slight_smile:

I don’t know enough about the graph structures (they’ll have to rely on Emden for that), but I can certainly advise on things like the repository structure and memory management within Graphviz.

I agree that a new force would be most welcome.

I’m not familiar enough with the code base to be able to say anything about the data structures, but I’m certainly interested in helping out with anything I can, like Git, the various build systems or testing. I sincerely hope that they can be averted from Windows, but otherwise I can help out with that too although it’s not something I yearn for.

Oh, yes, since a couple of months, I’m a full-fledged C++ expert as well. :rofl: