Dot runs forever on a certain example.

Try dot -v to observe its progress.

Note that it's possible to make graphs whose layout or even parsing is quadratic in the input size. For example, in dot,

  • digraph G {
    • a -> b -> c -> .... -> x -> y -> z
      a -> z
      b -> z
      c -> z
      /* and so on... */

      • x -> z


The total edge length (therefore the layout time) of this as a ranked graph is quadratic in the number of nodes. You probably won't encounter the following, but it is also possible to construct graphs whose parsing takes quadratic time in the number of attributes, by appending attributes to nodes and edges after the graph has been loaded. For example:

  • digraph G {
    • /* really big graph goes here...with N+1 nodes */
      n0 -> n1 -> ... -> nN;

      n0 [attr0="whatever",

      • attr1="something else",

      /* and so on with many more attributes */

      • attrM="something again"]


When an attribute first appears, each object is visited with possible cost proportional to the number of previously declared attributes. Thus, the running time for the above would be cN O(M) for some constant c. If there is any concern about this, the graph should specify the attributes first before declaring nodes or edges. In practice, this problem is neglible.

GraphvizWiki: FaqRuntimeDot (last edited 2008-01-17 18:23:36 by H-135-207-131-158)

Recent comments