Where does generating the graph take most of the time?

1

Hi graphviz experts!
I’m wondering where does the iterations of network simplex happen? Is it in the dot.render() or somewhere else? I’m asking because I would like to reduce the amount of time it needs to generate the pdf file. I’ve tried setting nslimit, maxiter, spline and overlap, and the time it spent from adding nodes, edges (which are not part of Graphviz) to finally generating the graph is still very long. Also, is there a suggested # of iterations that I can use as a threshold to set, for example, nslimit? Thanks!

2

I’ll leave it to someone else to answer specifics about simplex, but if you want to share your example I can try profiling it to see what we can optimize. I’ve been doing some of this work lately, but we really need more expensive user examples to guide our investigation.

I am not sure what you mean by dot.render(). Graphviz is mostly C code, so there is nothing like this specific invocation.

3
  • use the -v command line option to get some debugging info (arbitrarily, -v5 is what I use)
  • on Linux, this command will give timestamped debug info (How to timestamp (dot, fdp, neato, twopi, circo) -v output):
    { dot -v5 -T... myfile.gv >myfile.xyz ; } 2>&1 | ts -s >mystuff.log
  • you did not mention nslimit1 Are you using it? (this stuff is poorly documented)
  • I am not an expert, just a groupie, but try this:
    dot -Gnslimit=2 -Gnslimit1=2 -Gmaxiter=5000 -v5 -T...
  • How many nodes and edges in your graph (gc will answer this).
  • Can you share your input?
4

Sorry I should make it clearer. I’m using graphviz library in Python, so I create an graphviz.Diagraph object called dot, and eventually I rendered it to be a pdf file. Currently the difference in time it takes with/without plotting is huge: 3 min without plot, over 1 hour with plot. And since the parameters such as nslimit and maxiter are related to the number of iterations, I’d like to know is it because of from dotfile(xxx.gv)->pdf takes much time or somewhere else.

5

How many nodes and edges?

You can try rendering with layout=sfdp (or circo? or twopi?) for a quick test.

6

I have a dot = graph.Digraph() object, how to get the details of the graph? I tried dot.source and it prints out strings.

7

hi Steveroush,
Thank you for your reply! I tried adding -v to generate from .gv->.pdf, and here are some outputs:
network simplex: 412 nodes 460 edges maxiter=2147483647 balance=1

network simplex: 412 nodes 460 edges 17 iter 0.00 sec

Maxrank = 276, minrank = 0

mincross: pass 0 iter 0 trying 0 cur_cross 161 best_cross 161

mincross: pass 0 iter 1 trying 1 cur_cross 201 best_cross 161

mincross: pass 0 iter 2 trying 0 cur_cross 89 best_cross 89

mincross: pass 0 iter 3 trying 0 cur_cross 79 best_cross 79

mincross: pass 1 iter 0 trying 0 cur_cross 158 best_cross 65

mincross: pass 1 iter 1 trying 1 cur_cross 196 best_cross 65

mincross: pass 1 iter 2 trying 2 cur_cross 114 best_cross 65

mincross: pass 1 iter 3 trying 3 cur_cross 108 best_cross 65

mincross: pass 2 iter 0 trying 0 cur_cross 65 best_cross 65

mincross: pass 2 iter 1 trying 1 cur_cross 111 best_cross 65

mincross: pass 2 iter 2 trying 0 cur_cross 49 best_cross 49

mincross: pass 2 iter 3 trying 0 cur_cross 43 best_cross 43

mincross: pass 2 iter 4 trying 1 cur_cross 43 best_cross 43

mincross: pass 2 iter 5 trying 2 cur_cross 98 best_cross 43

mincross: pass 2 iter 6 trying 3 cur_cross 71 best_cross 43

mincross: pass 2 iter 7 trying 4 cur_cross 59 best_cross 43

mincross: pass 2 iter 8 trying 5 cur_cross 52 best_cross 43

mincross: pass 2 iter 9 trying 6 cur_cross 135 best_cross 43

mincross: pass 2 iter 10 trying 7 cur_cross 82 best_cross 43

mincross: pass 2 iter 11 trying 8 cur_cross 82 best_cross 43

mincross %3: 43 crossings, 0.02 secs.

network simplex: 2816 nodes 3971 edges maxiter=2147483647 balance=2

network simplex: 100 200 300 400 500 600 700 800 900 1000

network simplex: 1100

network simplex: 2816 nodes 3971 edges 1128 iter 0.17 sec

routesplines: 435 edges, 2175 boxes 0.00 sec

Using render: dot:core

Using device: dot:dot:core

gvRenderJobs %3: 0.02 secs.

If my understanding is correct, that doesn’t seem to be a very time-consuming graph-generating process right? So the problem might be in somewhere else.

8

Based on your output, dot has finished node ranking (the first use of network simplex), crossing reduction, and edge routing (the second use of network simplex), and rendering, so dot is done. So, yes, whatever is taking the time is occurring after dot has finished.