[prev in list] [next in list] [prev in thread] [next in thread] 

List:       graphviz-interest
Subject:    [graphviz-interest] Estimating Graph Time/Optimizing
From:       erg () research ! att ! com (Emden R !  Gansner)
Date:       2006-01-23 14:51:54
Message-ID: 43D533D7.1070107 () research ! att ! com
[Download RAW message or body]

Moe Aboulkheir wrote:
> 
> 2) i know nothing about graph theory, and so am ignorant about what 
> neato is spending it's time on, whether rendering or laying things out 
> in memory or whatever.  so far it's been running for about a day, but 
> hasn't yet written any output.  i'm not surprised - i expect it will 
> take several days (maybe weeks?) to generate this graph, but i'm 
> wondering if there is some way i can obtain an estimate of how long it 
> will take for a given graph, (other than cutting the dot file down to an 
> nth of it's size and multiplying to time it takes to render by n)
> 

The time is all being spent laying out the graph. neato is quadratic in the
number of nodes so a 300K node graph is going to take quite a while. It
continues until a certain tolerance is reached or for so many iterations,
so you can get a rough upper bound by seeing how long one interation takes (run neato -v) and
multiply that by the number of iterations, which is 200 by default.

> 2.5) are there any techniques i can employ to make it generate the 
> output faster, e.g. dividing the graph into subgraphs or something.  
> again, i am ignorant.
> 

The maxiter and epsilon attributes control the number of iterations and the tolerance.
Setting these lower and higher will produce output faster, with a corresponding loss in
layout quality, but for big graphs this often isn't a problem.

For graphs this size, there is really nothing you can do. There has been some good work
recently creating new layout techniques which can layout millions of nodes in a few seconds,
but these typically produce good output only on certain special types of graphs.


     Emden


[prev in list] [next in list] [prev in thread] [next in thread]