19

I have a large directed acyclic graph that I would like to visualize in a bitmap image.

Ideally I'd like to have all the root nodes at the top of the image, and all of the leaf nodes at the bottom, i.e. the graph edges are all pointing in a downwards direction.

Is there a good algorithm for working out the coordinates of all the nodes that meets these constraints and will produce a good visualization?

mikera
  • 105,238
  • 25
  • 256
  • 415

6 Answers6

14

I advise you to use Gephi.

This soft is able to do all the things you want to, especially graph layouts !

Guillaume Lebourgeois
  • 3,796
  • 1
  • 20
  • 23
8

Look at the Graphviz software collection. It contains several programs to render graphs.

The most simple way is to write your graph to disk, in one of Graphviz's text formats. Then execute one of the render programs, and load the resulting image into your application.

Eike
  • 2,205
  • 17
  • 10
3

Bayesian Networks have similar requirements. You might look for algorithms for Bayesian Networks. This paper for example might be helpful.

Jay Askren
  • 10,282
  • 14
  • 53
  • 75
1

If the graph is fairly simply then bitmaps will serve you fairly well. For very dense graphs however you'll want something with vector graphics, such as a SVG file that will support zooming in and out of fine details in a more friendly manner. Better yet is to use an interactive tool dedicated to navigating a graph such as gephi like someone mentioned above or yED

If you're trying to visualize a software dependency graph the best tool I've found for navigating is the DGML tools that are part of Visual Studio. They use a very powerful Sugiyama tree layout that does a fine job of making the flow of the graph directional. They have powerful interactive features with these edge hopping links that are bar none. You can also organize subgraphs and collapse them down, etc.

There's several graph description languages covered in Wikipedia with checking out https://en.wikipedia.org/wiki/Category:Graph_description_languages. If you have a good chunk of RAM the DGML tools can render very pleasantly and make the interaction and exploration of the graph very intuitive.

There's a decent overview of layout techniques to be seen here particularly #2 Layered Graph Drawing from Kozo Sugiyama.

jxramos
  • 7,356
  • 6
  • 57
  • 105
0

You might be interested in layered graph drawing (also known as "hierarchical graph drawing" or "Sugiyama-style graph drawing"). The algorithm is too long to describe here, but Google searches bring up many reliable explanations.

Kevin
  • 14,655
  • 24
  • 74
  • 124
-2

You can try this Go package I wrote: https://github.com/h8liu/e8tools/tree/master/dagvis

An example: http://lonnie.io/gostd/dagvis/

John Weldon
  • 39,849
  • 11
  • 94
  • 127
user3299527
  • 1
  • 1
    Note that [link-only answers](http://meta.stackoverflow.com/tags/link-only-answers/info) are discouraged, SO answers should be the end-point of a search for a solution (vs. yet another stopover of references, which tend to get stale over time). Please consider adding a stand-alone synopsis here, keeping the link as a reference – kleopatra Sep 20 '15 at 08:15
  • you should write at least short description in answer as @kleopatra say. – urfusion Sep 20 '15 at 08:18