2. Eleftherios Koutsofios and Stephen North. Drawing graphs with dot. Technical Report 910904-59113-08TM, AT&T Bell Laboratories, Murray Hill, New Jersey, September 1991.
It would be very nice to have this to refer to. I’ve found comments like Emden’s recent elaboration on Smyrna invaluable. If nothing else, these kind of multi-generational tech success stories make for fascinating reading.
In the last couple of weeks I gave a 30 min. talk about some of this to computer science groups at a pharm R&D company where I consult. I could fix it up a little. It would be interesting to give this story to other groups. One of the interns was kind of flippant and said this isn’t a current view of how open source works now (I guess meaning numpy, pandas, tensorflow, Apache projects etc.)
Also I’m concerned about making the mistake that telling the story of how you made something is the best way to explain it.
Yes. Thanks. I’m also interested in the “human” aspect of the history. War stories, anecdotes and such. My original question was if this has already been written. Perhaps published in some old computer (paper) magazine or online somewhere. I guess the answer is not. I would be interesting to have one though.
I would love to see your history of Graphviz. It would be a great case study of the innovation that was going on at Bell Labs in the 1980s and 1990s and the role of open source in promoting creativity and sharing the layout algorithms, There are so many new drawing libraries that could learn from these lessons.
Spoiler Alert: The initial kernel for Graphviz was the attempt to draw graphs related to software engineering. Stephen came across a paper addressing this and, being researchers, of course it was decided we could do better. The obvious choice was to minimize the total sum of discrete edge lengths. After working through many, many examples by hand, we discovered that the problem had some amazing properties and an elegant algorithm. Finally turning to the literature, we found that we had “discovered” that the problem was amenable to a network simplex algorithm, which we had largely reinvented for this particular case. This approach to node ranking turned out to be very effective for directed graph layout.
So much for the y coordinates. Handling the assignment of x coordinates proved a much harder problem, with trying to straighten long edges and maintaining the ordering of nodes in rows while avoiding overlap. The initial techniques involved a bunch of heuristics, each handling one set of constraints. It turned out to be the classic case of competing heuristics, where you improve one only to see another one worsen. Then Stephen recognized that you could rotate the problem ninety degrees and reformulate everything as another network simplex minimization. The only snag was the need to handle absolute values in the objective function, but it turned out there is a standard trick for dealing with this. Thus, a bunch of ad hoc computations could be replaced by a single model which could be solved using the same algorithm used in node ranking. I view this as one of the most beautiful ideas in Graphviz.