88

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).

  • 14
    See folks, this is how you ask a question here (and I'm going to overlook the graphviz really sucks blurb because you do a good job of explaining why it "sucks"). – user9 Feb 4 '14 at 21:28
  • 4
    A coworker says that d3.js gets (most of) the positioning done right. Obviously, it has other not-so-nice side effects such as to be browser-based and dynamic (i.e. not everyone gets the same output), so it may be not what you want. – mirabilos Feb 4 '14 at 22:39
  • 3
    @mirabilos Believe me, I already tried a lot of options (since 2011). If the graph had no cycle, it would degenerate to some sort of tree and would be easy to draw. However, my graph actually have many cycles and has circa of 200 nodes. To handle that with graphviz, I had to break the graph in 12 independent subgraphs, repeating the nodes that do appears in more than one graph. Further I needed to add a lot of invisible nodes, edges, and clusters. In my graphs, the clusters have few or no semantic meaning, they are just hacks to try to force graphviz to do its work right. – Victor Stafusa Feb 7 '14 at 17:00
  • 1
    @Oxinabox, yes that is sad. But given the huge number of hacks in the heuristics, tags and structure of graphviz, I think that a restart from zero would be much better than a fork. – Victor Stafusa Feb 13 '14 at 23:52
  • 1
    Computational Science SE has the same question here: scicomp.stackexchange.com/questions/3315/…. Besides GraphViz, there are several options available: Free * JavaScript InfoVis Toolkit * igraph package for the R statistical system * zGrViewer * Large Graph Library Non-free * GraphInsight – Deer Hunter Feb 27 '14 at 11:06
61

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.

  • 14
    I upvoted. Stephen North is a well-recognized expert in graph visualization, and given the OP's bashing of Graphviz it's precious to have his insight as an answer. (I do understand the OP's frustration though, but graphing is a hard problem) – Franck Dernoncourt Mar 14 '14 at 0:45
28

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.

  • 3
    +1. The OP request is impossible (the program gives a graph with the minimum possible number of crossings, for a large graph --> NP-hard so good luck). This answer is expert quality. – Franck Dernoncourt Mar 14 '14 at 0:33
  • I upvoted too. If there was ever a place you want experts to chime in, it is on hard problems, and this is especially nice to hear from experts when it comes to getting software. – Ira Baxter May 5 '14 at 6:47
  • 1
    To convert from GraphViz (.dot) to a format that yEd can read, use dottoxml. – Dave Jarvis Dec 17 '15 at 1:28
  • 1
    As an independent user of yEd (not affiliated to the company) I confirm that yEd is the best free of charge software available out there (and I've tried many) – Alexis Nov 10 '18 at 10:09
16

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.

  • 4
    There can be "reasonably small" number of crossings, not strictly global minimum. – Vi. Mar 18 '15 at 12:28
0

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.

enter image description here

  • 1
    Sorry, but this is not helpful at all. The author explicitly asks for a software that solves the problems better than GraphViz, does. So this obviously rules out GraphViz-based solutions. And UML diagrams are certainly not the typical applications for "large graphs", either. Did you mean to answer a different question? – Sebastian Nov 20 '18 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.