Alternative for Graphviz with better automatic node placement for large graphs?

Question

In the past I used Graphviz to create drawing of graphs. It is a nice tools for small graphs.

But unfortunately, for large graphs, Graphviz really sucks:

• It always crossed edges that obviously could be drawn without a cross.
• It superimposes different texts, making them unreadable.
• It has no reusable styling (like CSS), and you need to repeat the same personalizations in nodes and edges over, over, and over again.
• If the user wants to, just say, swap the positions of two nodes. To do so, it is frequently needed to heavily hack the source file, probably screwing unrelated parts of the graph in the process.
• It is very easy that in order to make small changes in one isolated place of the graph, Graphviz forces heavy major changes elsewhere, frequently invalidating hours of working trying to convince it do draw it right.
• It wastes a lot of space in the graph and at the same time overcrowd some places so very tightly.
• Sometimes, some edges makes very tortuous paths to connect the source node with the target node, featuring strange useless curves and a lot of superimposed laterally running edges.
• It features avalanche effects. Trivial modifications somewhere in the graph, might perturb Graphviz heuristics, resulting in a completely different graph.
• A lot of bugs...

I want something that as, a user, I can simply:

• Define what the nodes are, possibly with style to be applied.
• Say what are the edges, possibly with style to be applied.

And then the program gives:

• A graph with the minimum possible number of crossings.
• Pretty aligned nodes are good.

I DO NOT want to:

• Add a lot of hacks on input just because the tool is too stupid to see that it could swap two specific node to remove a crossing.
• Manually need to position edges and nodes.
• Get avalanche effects.

So, what might be a good replacement of Graphviz? I really want it to be a free one.

Note: I don't care much about the format in which the graph should be input'd, as long as I can save and edit a file with the graph description (whatever is the language of such description). So, there is absolutely no need to still be at the dot language or anything similar (in fact, I would be more than happy to throw away my dot files entirely, as there are much more hacks than actual graph-describing there).

Answer 1

Sorry for the disappointment. Graphviz could be better in many ways, but at this point the prospects for that aren't great because AT&T isn't supporting the work as much as it did in the past and some of the authors (like me) have left to seek other work. We are looking for people that want to take it over, so let us know.

We are impressed with yFiles, too.

Also try Tom Sawyer Software; they have a lot of engineering talent and did a lot of work on advanced layout methods and interactive tools. (You may need to spend $$$ as the free trial seems to be discontinued.)

The question did not say what specific layout tool or options were tried or how big a "large" network is, so it's not clear what to suggest.

If "large" means maybe hundreds of nodes, try neato -Goverlap=false (to avoid node text label overlap) and possibly -Gmodel=subset to try for better clustering. (These options are not the default, because in data analysis e.g. in bioinformatics, a straight MDS embedding gives a more accurate rendering of distances in the underlying network.)

If "large" means thousands of nodes, perhaps many thousands, use sfdp instead of neato again with -Goverlap=false. (The subset distance model isn't available in sfdp, because it's not clear how to handle variable edge lengths when merging edges in an hierarchical solver.) You can see a good example of a 1054 node graph here

For "wasted space problems" in the case of disconnected components see also the pack and packmode attributes. The solutions to such problems are not obvious (basically you are trying to optimally pack irregular shapes, with additional constraints, and sometimes at the scale of whatever people consider to be "large" so subquadratic algorithms are needed.) For connected graphs, experiment with -Goverlap options.

Those are the suggestions. As for excuses and explanations...

What someone is calling the "avalanche effect" is also called layout instability with respect to (minor) changes in the input graph. This is a property of almost all batch graph layout programs and constraint solvers. So you should look for interactive tools like D3 spring embedder layout, and Tim Dwyer did a lot of great work on this when he was at Microsoft so maybe someday their Graph Layout toolkit (AGL) will adopt his interactive constraint methods. Just an observation, most researchers and programmers have not attempted to attack scale, interactivity, and aesthetics all at the same time (choose any 2 of the above...)

The styling issue is also a good one, we just didn't have time/energy to tackle it since most graphs are generated automatically, so you could apply styles in some pre-processing tool or script. Also it has to be considered that the graph is not just a static parse tree but after a graph is read, its style sheet or the attributes of objects to which the styles have been applied can be changed, and then the graph must be written out correctly in a way that still preserves the original structure as much as possible. Not insurmountable but these are details that have to be thought through carefully.

Bugs can be reported on www.graphviz.org under Bug and Issue Tracking.

Global edge routing with smooth curves - hard problem. Note that a lot of cool looking layouts by some other tools use curved edges but they just draw over everything else that's in the way. I think we added this feature to graphviz too. Also I think there was a CHI or INFOVIS paper showing such curved edges are actually a little harder to read correctly than straight lines.

Crossings - some local optimization might be possible. Not sure what tool is being used. It is easy to point out specific examples where layouts could be better, but harder to invent an effective solution that where "minimum number of crossings" would not actually make things worse in general.

Note that I'm directly affiliated with Graphviz.

Answer 2

My software recommendation is "yEd" - a free as in beer general purpose graph drawing application that tries very hard to solve the problems you have been running into. To the best of my knowledge this software uses the best freely available implementations of the layout algorithms.

Now to the more detailed answer that would be more suitable for StackOverflow than for "Software Recommendation":

The problem you are trying to solve is a really hard problem (especially in the sense of computationally hard), so it is unlikely that you will find a tool that can solve all of your problems equally well. There are a number of free solutions (GraphViz probably being one of the best) and quite a number of commercial competitors. For the commercial yFiles graph drawing library, there is a free (as in beer) cross-platform application available, that you can try. It can import data from several different formats, apply style mappings to your data and offers a huge collection of different layout algorithms. It's called yEd and can be run without any installation in a web version from here. The desktop version could be launched as a java "webstart" application directly from the browser or after installing one of the standalone programs for Windows, Linux, and Mac.

Some of the layout algorithms should probably not be used with very large graphs (tens of thousands of elements), because they will execute for a very long time or require too much memory, but most of the time there is at least one layout style that should suit your data well. If you need to program against the API, you would need to license the underlying library (available for Java, .net, Javascript), which is against your "free" requirement, but this would give you even more control over the layout.

Disclaimer: I work for the company that creates this (free) product, however on Stack Exchange I do not represent my employer. I have spent most of my academic and professional time on graph drawing software since the late 1990s and I believe I have a very indepth knowledge about the market and the available software (both free and commercial). There may be other tools available and I hope this site can bring up great alternatives - I certainly won't deny them.

Answer 3

To answer very specifically to the question's request, as the other two answers did a great job to expand around:

What you ask is not possible. You want a program that gives a "graph with the minimum possible number of crossings.", and you specifically asked that the program works for large graphs.

However, determining the crossing number of a graph is a NP-hard problem (Garey and Johnson showed it is NP-complete in 1983).

Therefore such a program won't be able to guarantee to find the graph with the minimum possible number of crossings in a reasonable amount of time, making the program useless.

Answer 4

This would certainly be considered a "GraphViz-based solution", but if you're working with GraphViz you may want to check out Gephi. It's far more capable when it comes to processing large graphs.

Answer 5

PlantUML is an open-source tool allowing users to create UML diagrams from a plain text language. The language of PlantUML is an example of an Application Specific Language. It uses Graphviz software to lay out its diagrams. It has been used to allow blind students to work with UML.PlantUML also helps blind software engineers to design and read UML diagrams.