graphviz

Inside every large graph is a small graph dying to get out.

There's a place for just wanting to see everything, but the beauty of graphs is abstraction. Sometimes if you are asking a specific questions, a small, beautiful graph might be a better way to answer the question, than just rendering a diagram with hundreds or thousands of objects.

Graphviz just provides a basic rendering service; it would be up to higher semantic layers to support such exploration. Also, no doubt, interactivity is essential. It would be good for some enterprise that has the incentives to support the work, to create a new system, or at least to extend Graphviz to support better interactivity. It is not such a big stretch.

We always had trouble with that too. Wasn't there another YC thread in the last couple of days about exactly this problem in typography.

You are drawing large graphs by hand?

ML approaches to graph layout are very exciting, since the constraints people need in real life diagrams are quite intricate, but it's still a research problem.

That DFS is in the network simplex algorithm that solves node coordinates.

Some nice clever person could probably code up that clever algorithm of Brandes and Köpf, https://link.springer.com/chapter/10.1007/3-540-45848-4_3

Some nice clever person could probably replace our 1990s-style network simplex solver with something that takes advantage of multiple CPU cores, too.

Sure it is

Heh heh.

It would probably be helpful to the community if we could add a layout plugin to allow users to specify layouts in some absolute or relative grid format, to avoid all the invisible edge and edge length hackery. We just need appropriate funding.

We have some amazing maintainers who work on gitlab.com/graphviz/graphviz now, but the think is, there are far more bug reporters than bug fixers. The first gen of Graphviz authors are timing out, so we very few people are around now to fix relatively deep semantic or logical bugs, c.f. https://xkcd.com/2347/

Best regards, Graphviz the Project

Do you mean Yu, Schumacher and Crane's repulsive curves, as shown in figure 26 of https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveCurves/Rep... ?

When we started Graphviz, we vaguely sensed the potential for graph databases or environments, like neo4j, but we didn't work much in that area. It would take more resources, or intensity, than what we had. Anyway, gvpr is a modest attempt at a sort of graph query language.

Neo4J is interesting. It does something important, mainly, rationalize the mess of graph representations and algorithms. It's not hard to understand why that is valuable, but Neo4J sell it as being "efficient for linked structures" (relational databases don't have foreign keys and indices) and "intuitive" (have you ever tried to read the code for graph matching in Cymbal? I rest my case.) They have investments of hundreds of millions? Worth billions? They contributed something valuable to the tech economy.

It's surprising the conventional relational database products don't pay much attention to this opportunity, but they have gone vertical, e.g. credit card processing, because in the end it's more profitable to solve big end customer problems.

Most of the work has been on CI/CD, Windows, rationalizing and modernizing the code, and Zheng, Pawar and Goodman contributed a stochastic gradient descent solver, described here, https://arxiv.org/abs/1710.04626 with benefits pointed out by Börsig, Brandes and Pasztor https://arxiv.org/abs/2008.10376 but it's not a default solver, you'd have to ask for it. Great people joined (took over?) the project and have done an amazing job of triage on open bugs, and some were even fixed. We rewrote parts of the network simplex solver to eliminate some of the dumbfounding "trouble in init_rank" errors. We have a long wish list, and are hoping for funding to do some of this work.

Author(s) here. Ask us anything.

Author(s) here

We do voluntarily act on CERT advisories.

But, true.

Oh, that too. Feature interaction is a killer, isn't it.

"Very poor" seems harsh, but, yes, it hurts us, too. (That, and text with slightly-off baselines.)

The relevant code starts around https://gitlab.com/graphviz/graphviz/-/blob/main/lib/common/... If this isn't right, maybe somebody can figure out why. Perhaps the loop stops sometimes on the wrong side of the boundary? Anyway, it's equally possible that when the endpoint coord is handed off to a lower level driver, the arrowhead mitering is wrong. There is no question there was once upon time explicit code to try to cope with this problem, at least in the native PSgen, but I can't find it now. Maybe it wore away as waves of open source development washed over it, along with static tables for a bunch of "standard" PS fonts.

For more background, see for example https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/s...

In the worst case, this has to be debugged for all the drivers in https://gitlab.com/graphviz/graphviz/-/tree/main/plugin

No doubt there are more details if anyone can remember them.

Also, this is a great problem, and we tried to solve it in a more general context. http://dpd.cs.princeton.edu/Papers/DGKN97.pdf

I believe it's an open problem what makes a curve look "natural" or how to do a good job of routing multiple splines around obstacles so they do not intersect each other, though the work of Keean Crane at CMU seems promising: https://www.cs.cmu.edu/~kmcrane/Projects/RepulsiveCurves/ind...

Agree.

nice

Amazing. Cookbooks are still in fashion, too.

It's not often that one can comment on "gratuitous use of 4D".

Someone on the internet is wrong! Or maybe just partially correct.

This is very interesting work. There is some selling going on, not discussing enough about the issues that drove the database community toward relational databases and away from "network" databases in the 1970s.

If you think of visualization systems as a microcosm of more general computing, notice people need more than graphs - they need all kinds of tables, charts, maps, and other things. Same with "graph databases".

This area does exist because the database community underinvested in computing on graphs and networks, the same as it did with usability for a long time. It is still catching up but there is a lot of great work.

Another problem is helping users to understand the cost of what they are trying to compute. Select and join? I can estimate that. Find betweenness centrality of a large network? Find a tour that visits all the cycles of a network exactly once? All the edges? All nodes? Oops. What about graph object types? Is it OK to mix them?

Sometimes I wonder arguments that "graph databases are [more] efficient for linked structures." After 20 or 30 years of intense R&D, relational databases already seem pretty efficient for computing with relationships.

It's not that it can't be done, it's that the community went in a different direction, and there's a strong cultural bias. Bell Labs internally had a "new make" written by Glenn Fowler, that went full bore into tracking dependencies, probing local and global resources, recording configuration state at build time, that we adopted in Graphviz. It was powerful and concise. It was also a heroic effort for Glenn to maintain and develop, though others were assigned. https://ieeexplore.ieee.org/document/6771042

At one point in our project we had a lot of arguments about build systems and software repositories (there were times when we had to stop talking about it), then at some point John Ellson said, look, everyone else is using autotools, so do you want them to use your software? We realized he was right.

Individuals in the software community are capable of building a lot of amazing tools. The difficulty is persuading the community and teaching non-specialists to use them. They already know how to run make, or ./autogen.sh; ./configure --prefix=$HOME

Despite this Graphviz still has 3 or 4 build systems: autotools, Visual Studio (probably 90% of our audience is on Windows though we try not to think about it), Xcode (needed for an under-maintained MacOS app), and Magnus Jacobsson and Matthew Fernandez have a lot of a Cmake build working, though not yet complete.

Apologies for rambling a little off topic.

(30 years and 1500K lines of code later) yes that's somewhat true

Specifically which new algorithms would you like to see?

A difficulty is that implementation is harder than a typical student project, and we need some decent developer documentation.

It's a good observation that a lot of people want "diagrams", not separate, incompatible graph layouts, scatter plots, maps, histograms, radar charts, and everything else. Grammar based libraries and tools are starting to fill this need, but still feel low level, and sometimes too much DIY integration. Great problem though and exciting to see progress in understanding practical needs.

Better Treemap visualization? e.g. https://www.d3-graph-gallery.com/treemap

These are a feature in Tableau, https://help.tableau.com/current/pro/desktop/en-us/buildexam... and PowerBI https://docs.microsoft.com/en-us/power-bi/visuals/power-bi-v...

Yes, force-directed layout doesn't consider number of crossings. dot is the only graphviz program that reduces crossings, and because of the level assignment constraint, even small graphs like K_4 or K_2,2 have crossings that could be avoided by just routing edges differently.

Yes, you can set NDim, https://graphviz.org/doc/info/attrs.html#d:dim I'm not sure why we said up to 10. It's hard to see even in 8 dimensional space!

In terms of drawing graphs of the U.S. states or data like that, it should be possible to, say, create a point at the centroid of every region, then connect the adjacent regions to form a mesh, then feed the mesh to neato with some options to relax the layout but retain the mesh. This is what the overlap removal algorithm does anyway. See https://www.graphviz.org/Documentation/GH10.pdf, at least the figures.

There's plenty of recent work that improves on some of the graphviz algorithms. It's a pity that without a convenient way to incorporate such inventions in a larger system, it tends to languish and not have as much impact or isn't easily available to people that could use it. Nocaj/Ortmann/Brandes work on untangling hairballs is another example: http://jgaa.info/accepted/recent/NocajOrtmannBrandes.pdf We even have this prototyped in a directory somewhere but it would be more work to merge it into the release.

This is an excellent idea. In general, allowing a human to say they would like to expend more machine cycles to search for better renderings would be useful. This would be an interesting summer intern project, It could probably be layered on top of the existing software.

We're reluctant to be exposed to too much anger about misfeatures in 20 year old code that was basically a prototype that escaped from the lab, but go ahead, ask us anything.

We've gotten a lot of help lately from Magnus Jacobsson, Matthew Fernandez and Mark Hansen on cleaning up the website and the code base, even some persistent bugs we could never find ourselves.

Improvements that would benefit the community the most?

- better default styles that don't look like troff from 1985

- better default layout parameters in neato than statistical multidimensional scaling based on shortest path

- more expressive graph language with classes or templates

- more robust handling of error conditions like out of memory

- better documentation to help people find useful tools or just know what they should be looking for

- find someone to donate a generic orthogonal routing algorithm based on a modern algorithm since people want this

- it would be a big effort, but move the core algorithms to a framework that supports interaction with layout generation

Hope this makes sense.

Can't some reasonable person refresh our website so we would have more useful content like this? :-) also include Sketchviz https://news.ycombinator.com/item?id=21518152 don't include anything from haters though

You can fork it on gitlab, https://gitlab.com/graphviz/graphviz.gitlab.io

Thanks! A lot of the good stuff (e.g. stress majorization and the Jaccard distance model stolen for neato -Gmodel=subset) was done in the 2000s. Probably people criticize because they see B&W graphics, Times-Roman and splines rendered 1pt wide and we didn't use XML or JSON.

What?