Difficulty with multi-source, multi-sink DAG rendering

Help
1

Hello, I have a graph with the following properties,

  • directed
  • acyclic
  • multiple sources
  • multiple sinks
  • disconnected
  • 800+ nodes
  • 2,700+ edges

I know for a fact that the graph does not have an upward planar drawing (or any planar drawing at all).

I’ve been trying to render the graph while making it as “human-friendly” as possible.
However, I haven’t had much luck.

My only hard requirement is that the drawing is “hierarchical” (sources top, sinks bottom).

Here is a link to the graph I am working with (a DOT file),
dag - Pastebin.com (2.7k edges)
strict digraph { 86 -> 10 27 -> 12 12 -> 13 13 -> 14 86 -> 15 - Pastebin.com (1.5k edges)

I tried a bunch of different self-made techniques, and some libraries I found online. I’ve also tried Graphviz and can’t seem to get output I’m happy with.

The Graphviz command I’m using is, dot -Kdot input_file

When outputting a png file, I get an image that is 32767x4213 in dimension!
The graph is also messy:
Imgur: The magic of the Internet (2.7k edges)
Imgur: The magic of the Internet (1.5k edges)

Does anyone here have any advice for me? Or is it just plain impossible?

2
  1. When running your experiments, if you produce an SVG output file, it is easier to zoom in and figure out what you are looking at.
  2. Adding these three lines to your graph will make it “better” (to my eyes) (but not great) :
    splines=polyline // better in some ways, worse in others,
    ranksep=2 // distance between one rank and the next (inches)
    nodesep=1 // distance between nodes in same rank (inches)
  3. The basic problem seems to be that some of the generated ranks (rows) are too “busy” (too many edges). Off-the-top, I don’t know any way to split up ranks with too many edges, hmmm
  4. neato and fdp kind-of finesse the “busy” problem, but they don’t maintain top-to-bottom hierarchy.
3

a late comment: you might also try unflatten (https://graphviz.org/pdf/unflatten.1.pdf) to split the ranks.

4

In this context, neato -Gmode=hier is perhaps underappreciated and insufficiently documented. If you search on the web for Ipsep-COLA you may find a related paper IIRC.

5

Tried this on an ornery graph from elsewhere and it produced a very attractive result. Nice!
However, it seems to ignore len attribute, even if weight is set to 0. Dang.
Maybe I’ll try reading the code sometime to see what is going on.
(How/when len works is pretty murky).
Anyway, thanks for pointing out mode=hier.

6

len is the ideal spring length (but subject to global constraints, i.e. triangle inequality).
weight is as the spring coefficient