Number: 1512
Title: Dot runs forever on 1000+ graph (follow-up)
Submitter: Alain Ketterlin
Date: Thu Nov 6 06:12:22 2008
Subsys: Dot
Version: 2.16
System: x86-Linux-2.6.24 (ubuntu 8.04)
Severity: major
More info on my previous bug-report today: I've located the single node that makes dot run forever. The node is named block_0x4d4a4f. All edges to this node are placed at the end of the attached file (there's no incoming edge). Commenting them out lets dot run in a few seconds (I've placed a comment in the dot-file).

There's a total of 60 edges entering the node. I've tried removing various numbers of them to see what happens. Here are the results:

With 20 edges:  1.748s
With 30 edges: 12.043s
With 35 edges: 34.556s
With 40 edges: 7m34.993s
With 45 edges: 9m35.724s
With 48 edges: (stopped after 30 minutes)

Note that I removed "longest edges" first, but in a fairly heuristic manner.

Hope this helps.
Input file:
Comments: Follow-up on bug 1511
Owner: *
Status: *