dotty hangs with cpu spin for "apt-cache dotty monodevelop" graph

[Martin Olsson]

This works just fine on Ubuntu karmic:
apt-cache dotty binutils | dotty -

These ones gets stuck inside a CPU spin and never finishes though:
apt-cache dotty gedit | dotty -
apt-cache dotty firefox | dotty -
apt-cache dotty monodevelop | dotty -

The first part (e.g. "apt-cache dotty firefox") finishes just fine so the bug must be in dotty or later on in the chain.

[Nicolás Alvarez (nicolas-alvarez)]

*Never* finishes? How long did you wait?

[周成瑞 (e93b5ae3)]

I think the later three involves many dependencies including conflicts etc. recursively. This should not be a bug. I think this can be closed.

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[John Ellson (ellson)]

I'm an upstream developer for graphviz, but not a Ubuntu user. Could someone please attach the output
of 'apt-cache dotty firefox' ? (Perhaps first verify that 'cat saved_file | dotty -' still exhibits the problem.)

Thanks.

[Martin Olsson (mnemo)]

Here is the output of "apt-cache dotty firefox" from ubuntu 12.04:
http://temp.minimum.se/apt_cache_dotty_firefox.txt

I tried "dotty apt_cache_dotty_firefox.txt" just now and it took 100% CPU for 5mins but no graph so I CTRL-C'ed it.

[John Ellson (ellson)]

I can reproduce with 'dot apt_cache_dotty_firefox.txt'. Thanks.

The graph is probably just too big/complex ... but I can see that some kind of termination should happen in a reasonable time ...

[Martin Olsson (mnemo)]

This also affects more basic packages like gcalctool, acl, linux-image, binutils etc. In fact I can't find a single package where it actually pops up a rendered a graph within reasonable time. Our definitions of reasonable might be different though :-)

btw, I'm seeing this:

$ cat firefox.txt | g '\->' | wc -l
10471
$ cat firefox.txt | g shape | wc -l
2505

...and I wonder, is it realistic for graphviz to handle 2500 nodes with 10k edges?

I was thinking, if graphviz could provide some progress information during layout then dotty could show a UI progress bar with a cancel button. But, in reality the time dotty takes to render these graphs is so long that a progress bar doesn't really help a lot. Indeed, it makes me suspect that maybe we're dealing with a simpler bug that makes graphviz go into an infinite CPU spin loop?

If it's verified that the firefox dep graph (and indeed many other packages) is indeed too heavy for graphviz and this is not a graphviz bug, it would make sense to A) investigate if some other graph layout (other than "dot") can be used within graphviz to make it faster, or B) use some other graph library instead of using graphviz, or C) have apt-cache prune the graph when it gets too complicated (either by not showing all kinds of edges like conflicting/recommended etc) or by simply not showing all dependencies (i.e. maybe just first level or first+second level dependencies).