A way to specify ranks externally in dot? Or a faster splines alternative in neato?

Hello,
I'm trying to use graphviz to visualize quite large digraphs (hundreds to thousands nodes, 10k-100k edges). The graphs are very wide and shallow (that is, few ranks and many nodes in each rank). This makes the default dot layout unusable - graph of eg. 500pt width and 50000pt height is completely unreadable (I'll don't even mention overlapping edges).

Currently I deal with such graphs by positioning the nodes manually on a grid (with a little effort to make edges going from left to right). I set this layout using pos attrs and run neato with -n and it more or less works. However, the time needed by neato to compute spline edges (even polyline) is completely unacceptable (even over 24hrs of computation). And I need to make sure there are no edges going over nodes.

So the question is: is there any way to tell graphviz to
1) use in dot layout ranks computed externally (and don't bother to much with crossing edges minimization - AFAIR it can explode in large graphs)
or
2) speedup neato spline edge generation algorithm by similar means to those used by dot?

Any suggestions will be appreciated.

Bartosz

As we have noted, spline

As we have noted, spline layout is at least cubic, so it was never meant to be practical for a large number of nodes and edges. Plus you are probably thrashing in memory. You might try using the unflatten filter, or as you are willing to tweak the graph, add varying minlen attributes on your own. (I assume you have just one connected component. If part of the width problem to due to components being place side by side, there are other ways to handle that.)

As for 1), you can recompile dot with -DALLOW_LEVELS after changing line 559 of rank.c from

  if ((N_level = agfindattr(g->proto->n, "level")))

to

  if ((N_level = agattr(g,AGNODE,"level",NULL)))

This will cause dot to read the ranks from each nodes "level" attribute. You can use the mclimit attribute to limit the amount of crossing reduction done.

Thanks for reply.

Thanks for reply. Unfortunately, the unflatten filter does not help significantly.

I've tried to recompile dot with -DALLOW_LEVELS, however the build fails with the following error:


CC rank.lo
rank.c: In function ‘setRanks’:
rank.c:454:21: error: ‘attrsym_t’ has no member named ‘index’
rank.c:457:61: error: ‘node_t’ has no member named ‘name’
rank.c: In function ‘dot2_rank’:
rank.c:1198:16: warning: unused variable ‘N_level’ [-Wunused-variable]
make[3]: *** [rank.lo] Error 1

I've checked last stable as well as the current repository revision with the same results.

My mistake. There was another

My mistake. There was another piece that needed fixing. I have now made the changes and committed them. Basically, in the setRanks function, you want

    for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
        s = agxget (n, lsym);
        v = strtol (s, &ep, 10);
        if (ep == s)
            agerr(AGWARN, "no level attribute for node \"%s\"\n", agnameof(n));
        ND_rank(n) = v;
    }

 

OK, now it compiles and works

OK, now it compiles and works as expected. Thanks!

But... It seems specifying ranks is not enough for me. So I have another question: is there any way I can squeeze the graph (limit distances between adjacent nodes in a given rank) without shrinking nodes? I've tried ratio=compress + size=... , but it only scaled the whole graph down.

To be clear, an example: I'm currently getting images like this: http://bzaborow.org/bart/graphviz/graph.dot_levels.svg and I need something closer to this: http://bzaborow.org/bart/graphviz/graph.neato_mystupid.svg (so all nodes can be displayed on a screen at once without shrinking them too much).

 

Recent comments