Drawing tidy graphs with shared parents and children

Question

I'm working on an HTML and Javascript application that will take a git tree and display the commits and merges as a directed graph (like git log --graph). I've read a bit on the Reingold-Tilford tidy algorithm, but it doesn't seem to apply to graphs with nodes that share both parents and children. An example of the desired output (as text, but I'm looking at graphing libraries like d3js and Raphael):

*   - 1 day ago
|
*   - 2 days ago
|\
| * - 3 days ago
|/
*   - 4 days ago
|
*   - 5 days ago

Are there any libraries out there that already handle this? Are there examples (in any language) of rendering graphs like this? As a last resort, I think I'll try to reproduce the graphing from git itself (https://github.com/git/git/blob/master/graph.c), although it is a bit dense.

Thanks for the help.

Answer 1

After a while of implementing my own rather horrible graph, I heard about GitLab and their open source GitHub implementation. They have a similar implementation of the "Network" graph from GitHub, which can be found in their repository.

Some of the files in question:

• lib/gitlab/graph/commit.rb
• lib/gitlab/graph/json_builder.rb
• vender/assets/javascripts/branch-graph.js

With some modification I was able to figure out how they implemented their network graph and am using a version of their code to great success.

Answer 2

First, check out the rubygem Git: http://rubygems.org/gems/git That will save you much work.

Secondly, I've tried to work with d3.js and found it to be very complex and powerful. The graph you are intending to create will work great with that and there is even a d3_rails gem: http://rubygems.org/gems/d3_rails

But remember if you only need to do a simple graphical representation of a few shapes to display minimal complexity (no drilldowns etc.) you might think about using HTML5's canvas. Very easy to use but lacks the power d3.js has.