StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POBest Graph Drawing Algorithm For Hierarchical Data?
text
Body
copied!<p>I have a collection of directed <em>acyclic</em> graphs that are <em>nearly</em> trees, in the following sense: each graph has a <em>root</em>, and the vertices are organized into <em>levels</em> such that if <em>v</em><sub>1</sub> and <em>v</em><sub>2</sub> are vertices, then if the level of <em>v</em><sub>1</sub> is less than the level of <em>v</em><sub>2</sub>, then there is no edge from <em>v</em><sub>2</sub> to <em>v</em><sub>1</sub> in the graph, although there may be many edges from <em>v</em><sub>1</sub> to vertices at the same or a greater level. For example, an expression tree, a function call graph, or a linear class hierarchy, would be examples of such graphs. Here is an example of such a graph:</p> <pre><code> A1 / \ A1 -> A4, A3 / \ A3 -> A2, A6, A7 A4 A2--A3 A2 -> A6 | \ / \ A6 \_ A7 </code></pre> <p>There are a plethora of graph-drawing algorithms, and I can't determine which is optimal for this situation. Some preliminary research indicates that algorithms for drawing Hasse diagrams might be appropriate, but it seems that the output of such algorithms isn't geared toward the type of data structures that I'm trying to model. There are also several algorithms for modeling hierarchical data, but I'm not sure which would balance ease of implementation with efficiency. One problem with the former approach is that these graphs have a root, as well as a direction. If possible, the algorithm would support <em>cyclic</em> graphs, and minimize the number of numeric computations, but this isn't necessary. For these reasons, I would prefer to avoid force-directed algorithms, and if possible, the GraphViz algorithms such as <em>dot</em>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload