Suggestion: Force-Directed Edge Bundling

[psimm]

A new geom_edge_force that uses force-directed edge bundling would let users create much better "hairball" visualizations that are easier to read. In contrast to geom_conn_bundle it would not require connections, which would make it applicable to many more networks.

Reference:
Holten, Danny, and Jarke J. Van Wijk. "Force‐Directed Edge Bundling for Graph Visualization." Computer Graphics Forum (Blackwell Publishing Ltd) 28, no. 3 (2009): 983-990.

An example in d3: https://github.com/upphiminn/d3.ForceBundle

Unfortunately performance seems to be a major concern.

[thomasp85]

Thanks. I've had my eye on that for a while but implementation is non-trivial. It will have to wait for a time with a lot of free time

[schochastics]

I have been working on this and i think I am pretty close (neglecting potential style guide errors)

This is the stat I wrote:

StatEdgeForceBundle <- ggproto('StatEdgeForceBundle', StatIdentity, setup_data = function(data, params) {
    if (any(names(data) == 'filter')) {
      if (!is.logical(data$filter)) {
        stop('filter must be logical')
      }
      data <- data[data$filter, names(data) != 'filter']
    }
    data <- remove_loop(data)
    force_bundle(data,params)

  },
  required_aes = c('x', 'y'),
  default_aes = aes(filter = TRUE),
  extra_params = c('K','C','P','S','P_rate','I','I_rate','compatibility_threshold','eps')
)

the extra parameter are needed for the force bundling:

force_bundle <- function(data, params) {
  # parameter handling
  K <- params$K#1
  C <- params$C#6
  P <- params$P#1
  S <- params$S#0.04
  P_rate <- params$P_rate#2
  I <- params$I#50
  I_rate <- params$I_rate#2/3
  compatibility_threshold <- params$compatibility_threshold#0.1
  eps <- params$eps#1e-8
  
  #initialize matrix with coordinates
  extraCols <- !names(data) %in% c('x', 'y', 'xend', 'yend', 'group', 'PANEL')
  edges_xy <- cbind(data$x,data$y,data$xend,data$yend)
  m <- nrow(edges_xy)
  
  #initialize edge subdivision list
  elist <- unname(lapply(split(edges_xy, rep(1:nrow(edges_xy), ncol(edges_xy))),
                         function(y) matrix(y,2,2,byrow = TRUE)))
  
  #main force bundling routine
  elist <- force_bundle_iter(edges_xy,elist,K,C,P,P_rate,
                             S,I, I_rate,compatibility_threshold, eps)
  
  # assemble data frame
  segments <- nrow(elist[[1]])
  
  idx <- seq(0, 1, length.out = segments)
  data_bundle <- as.data.frame(cbind(
    rep(1,m*segments), #hard coded, pretty sure that's wrong
    do.call("rbind",elist),
    rep(idx,m),
    rep(1:m,each=segments)))
  names(data_bundle) <- c("PANEL","x","y","index","group")
  cbind(data_bundle,data[rep(1:m, each = segments), extraCols, drop = FALSE])
}

It works, but I get the warning

Warning: Ignoring unknown aesthetics: xend, yend

and other edge aes are not mapped (pretty sure that has to do with the way I build the data frame).
I am unsure where the warning comes from. Any pointers?
Also, is the way I designed the Stat part ok?

I am also wondering if a geom_edge_forcebundle() geom_edge_forcebundle2() make sense since the force bundling always needs intermediate points.

/Edit: fixed the edge aes mapping issue with the lines containing extraCols in the function force_bundle()

[thomasp85]

@schochastics do you want to add this?

[schochastics]

@thomasp85 what is your release schedule? I have a second algorithm that I would also implement. I am going on parental leave tomorrow though, so making a proper PR would take a while. From my side it is no problem to postpone it to the next release.

[thomasp85]

There will be a release soonish to comply with changes in ggplot2, but that may end up as a very small patch release. So, fix on your own accord and enjoy the parental leave. That is way more important than edge bundling🙂

[schochastics]

@thomasp85 I gave this some thought and I am not sure it makes sense to implement it in ggraph. The biggest issue is that, as far as I understand, the bundling cannot be precomputed (as compared to layouts). So if aesthetics need to be changed, the bundling has to be calculated again and that can take a long time and will annoy users. My implementation can probably be made more efficient, but it will remain a bottleneck. The edgebundle package allows to precompute the bundling, although the graph structure is lost.

If you think this is not an issue, or the bottleneck can be avoided somehow, then I can prepare a PR later this year.
Happy to hear your thought about this.

[thomasp85]

one way around it is to use memoisation - I think I at least would like to give it a try

[schochastics]

That is actually a great idea!

[schochastics]

Yup, can confirm that memoise works.