Hierarchical edge bundles for general graphs

Does anyone knows if someone have already implemented the method from this paper Hierarchical Edge Bundles for General Graphs by Yuntao Jia 2009 somewhere online?

it allows to create a HEB on a non hierarchical graph

My goal is to use for this project : The Illustrated Manual of Buddhist Terms and Doctrines

It may not be exactly what you’re looking for, but the d3.curve package can get you a long way: A little webby / dleeftink | Observable

That is cool thank you. :wink:

From my little reasearch, it is actually quite a complex process to produce the desired output. You have to “automatically construct a community hierarchy” to controle the inner edge bundles. This uses Betweenness centrality algorithme, Then you have to merge the controle tree branches according to a set of rules. After that you can create the final graph using the Hierarchical edge bundling / D3 | Observable

I have seen that neo4j can be used in Observable. This is quite cool already and I will try to follow that track.

After some research, I have found dblp: Yuntao Jia and this nice paper as well, which is an indebt of the former article.

To be continued! :slight_smile:

My approach would be

  1. Extract minimum spanning tree (MST)
  2. Set halfway points on MST edges as 'attractors'
  3. Apply the d3.curveBundle to non-MST edges in the neighborhood of these attractors

Not true hierarchical edge bundling, but possibly fitting for graphs that aren’t necessary hierarchical.

That is interesting, I will keep that suggesiton and maybe try it out. I can see that some have already do some algo with Minimum Spanning Tree (Minimum Spanning Tree / Mike Bostock | Observable and Minimum Spanning Tree / 3sam3 | Observable)

As the graph is directed, I think I would like to focus on the methode in the paper first. Actually, all the algorithms are there in pseudo code, for example:

Also, I see now that there is quite a bit of module in Node that can help like ngraph.centrality - npm and even Cytoscape.js which seems to have everything I need :wink:

This is a nice example where it is used Dijkstra's algorithm on an RGG / Mark McClure | Observable → my notebook

Sounds great! This is not a simple problem by any means. And remember, a certain model is your coding friend (possibly needs some additional prompting).

1 Like