Hacker News new | past | comments | ask | show | jobs | submit login

For everyone interested in algorithms behind Graphviz, here's a paper so start with:

http://www.graphviz.org/Documentation/TSE93.pdf

This work is absolutely amazing. I've tried implementing it a few years ago (as an excervise when preparing for Google interview). So naive. I've found out that I have read each and every sentence extremely carefully to get things right. I got quite far but never finished the implementation. (And I did not get an offer from Google either.)




The clue is in the name - 1993. It is just a pile of incompatible heuristics. I have used it, but I feel its inadequacies like a stiletto to the heart. Draw a quadrilateral with NEATO and see how many times you get a hideous bow tie. Pathetic. Its penumbral effect has been to stifle any real progress in better rival open source libraries, and hence we are all so much more impoverished today.


neato uses distance embedding methods. The paper linked describes Sugiyama-style rank embeddings as implemented in dot. 1) They're incomparable. 2) the theory behind neato was published in 2004 (http://www.graphviz.org/Documentation/GKN04.pdf).

There are research groups (I'm thinking of Tim Dwyer's specifically) that are specifically trying to improve the situation. When you say "it's just a pile of incompatible heuristics", it sounds like you haven't taken the time to try and implement a better solution.

Graph drawing is the kind of thing that seems trivial, right until you try to work on it.

(disclaimer: I'm clearly biased here since I worked with the people who wrote graphviz.)


I'm a little taken aback at your vitriol. Is "Stifled other libraries" a synonym for "Does the job well enough that nothing else was able to compete" ? That's been my sense. A lingua franca for graph visualization, pervasively available.

I hardly think they'd turn away algorithmic contributions, if you've got some.

Do you have an example of your hideous bow ties? I don't usually use graphviz to 'draw' anything, so I don't really have the context to understand your complaint. I've never seen a result I think of as a hideous bow tie.





Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: