Force-Directed Edge Bundling (#267)

schochastics commented 10 months ago

This PR adds a new geom: geom_edge_bundle_force(). It is a reimplementation of the D3 Version and the version that is also available in different form in the package edgebundle. The main working horse is implemented in src/forceBundle.cpp.

Details

Edge bundling always needs to create a number of intermediate points on an edge. Thus, in my opinion, the version geom_edge_bundle_force() should suffice (no "0" and "2" version needed).

The force bundling algorithm is computationally expensive and will run for a while. To prevent repeated calculation (e.g. when aesthetics are changed) memoise was used so that the bundling only needs to be calculated once.

The algorithm has many parameters which, IMO, are not that easy to fine tune, but the defaults are reasonable in most circumstances.

Disclaimer: This is the first time I wrote a custom geom. Not sure I followed all best practices. Happy to make any change necessary.

Examples

library(ggraph)
library(igraph)
library(edgebundle)
data(us_flights)

states <- map_data("state")

#simple graph
g <- graph_from_edgelist(
  matrix(c(1, 12, 2, 11, 3, 10, 4, 9, 5, 8, 6, 7), ncol = 2, byrow = T), F
)
xy <- cbind(c(rep(0, 6), rep(1, 6)), c(1:6, 1:6))
E(g)$col <- letters[1:6]

Simple Example: No Bundling

ggraph(g, "manual", x = xy[, 1], y = xy[, 2]) +
  geom_edge_link0(aes(edge_colour = col), edge_width = 2, show.legend = FALSE) +
  geom_node_point(size = 5) +
  theme_graph()

Simple Example: With Bundling

ggraph(g, "manual", x = xy[, 1], y = xy[, 2]) +
  geom_edge_bundle_force(aes(edge_colour = col), edge_width = 2,  compatibility_threshold = 0.1, show.legend = FALSE) +
  geom_node_point(size = 5) +
  theme_graph()

US Flight Network

ggraph(us_flights, "manual", x = V(us_flights)$longitude, y = V(us_flights)$latitude) +
  geom_polygon(
    data = states, aes(long, lat, group = group),
    col = "white", size = 0.1, fill = NA
  ) +
  geom_edge_link0(edge_color = "#9d0191", edge_width = 0.05) +
  geom_edge_link0(edge_color = "white", edge_width = 0.005) +
  geom_node_point(color = "#9d0191", size = 0.25) +
  geom_node_point(color = "white", size = 0.25, alpha = 0.5) +
  labs(title = "No Edge Bundling") +
  theme_graph(background = "black") +
  theme(plot.title = element_text(color = "white"))

ggraph(us_flights, "manual", x = V(us_flights)$longitude, y = V(us_flights)$latitude) +
  geom_polygon(
    data = states, aes(long, lat, group = group),
    col = "white", size = 0.1, fill = NA
  ) +
  geom_edge_bundle_force(edge_color = "#9d0191", edge_width = 0.05) +
  geom_edge_bundle_force(edge_colour = "white", edge_width = 0.005) +
  geom_node_point(color = "#9d0191", size = 0.25) +
  geom_node_point(color = "white", size = 0.25, alpha = 0.5) +
  labs(title = "Force Directed Edge Bundling") +
  ggraph::theme_graph(background = "black") +
  theme(plot.title = element_text(color = "white"))

^{Created on 2024-01-11 with reprex v2.0.2}

thomasp85 commented 10 months ago

Thanks for this!

A couple of inputs:

I don't think you need to add [[Rcpp::export]] to any of the other functions other than force_bundle_iter as these are not called from R (right?)
I do think at least a *2 version should be included (a *0 is debatable). The difference between the standard and *2 is whether aesthetics should be interpolated between terminal nodes and both of these are meaningful here. If a *0 version were to be included it would be a matter of providing one that used GeomPath(). As the overhead is pretty low I think we can just include it for completeness.
I vaguely recall a version of force directed edge bundling that repulses edges going in opposite directions so that the bundles became separated. I don't expect this is implemented here, right?
Should we consider using b-spline for drawing so the result is smooth even if one use a small number of splits?

schochastics commented 10 months ago

I don't think you need to add [[Rcpp::export]] to any of the other functions other than force_bundle_iter as these are not called from R (right?)

True. Removed

I do think at least a *2 version should be included (a *0 is debatable). The difference between the standard and *2 is whether aesthetics should be interpolated between terminal nodes and both of these are meaningful here. If a *0 version were to be included it would be a matter of providing one that used GeomPath(). As the overhead is pretty low I think we can just include it for completeness.

hmm thinking about it, it seems that what is implemented at the moment is actually more like a 0 version. Edges are segmented but without much control for the user since the n parameter is missing. So probably makes sense to implemnt all three after all. However, this is probably where my skills (and time) end. I think the most important part is the already implemented Rcpp part and the remaining geom/stat stuff should be doable for you? Otherwise we need to postpone this for a while.

I vaguely recall a version of force directed edge bundling that repulses edges going in opposite directions so that the bundles became separated. I don't expect this is implemented here, right?

That is a different algorithm: http://vis.stanford.edu/papers/divided-edge-bundling. Never got around to implement it. A matlab implementation is on GitHub.

An algorithm one could think of including is edge-path bundling, which is similar to force bundling but I think a bit faster. I have it implemented in edgebundle but that needs a bit more work to translate to ggraph. I would work on that for a later release, if you don't want to do it yourself.

Should we consider using b-spline for drawing so the result is smooth even if one use a small number of splits?

Thats a good idea but also out of my comfort zone :)

So beyond more cleanup if necessary, I am afraid I cannot contribute more at the moment. Hope it is enough for you to continue. Otherwise we postpone it

thomasp85 commented 10 months ago

This is already great. I think I can take it from here

schochastics commented 10 months ago

Great, thanks!

thomasp85 commented 10 months ago

Looking at your edgebundle package there are a bunch of versions that would be interesting to add to ggraph. How would you rather do it? Move over code from your package or import it (potentially requiring some new interfaces in edgebundle)?

schochastics commented 10 months ago

good question. I think the edge-path bundling would be a good candidate to port to ggraph. Stub bundling is buggy and hammer bundling requires datashader from python, so I think both wouldnt make sense to bring to ggraph. In my opinion edge-path and force directed would be enough.

Are you also interested in the flow maps and metro layout?

thomasp85 commented 10 months ago

yeah, I think especially the flow maps would be interesting to bring in, but see no reason to not bring over the metro layout as well while I have somehow now committed to make a feature release 😅

thomasp85 commented 10 months ago

I'll add the path bundling to this PR as it is akin in spirit

schochastics commented 10 months ago

Yes the edge path bundling shouldn't be too hard to port. The flow maps would indeed be cool to have in ggraph as well. Not sure how complex it is too move over though.

The metro map thing is indeed rather niche and I dont see a point either to make this more widely accessible.

thomasp85 commented 10 months ago

I've added the edge path version as well. If you have the time can you check I haven't done anything obviously wrong and written anything wrong in the docs about it?

thomasp85 commented 10 months ago

Also added an extremely simple bundling technique that kinda just popped into my head. Trace the shortest paths on the minimal spanning tree of the graph weighted by edge lengths. I can't claim it leads to visually better output but it is extremely fast

schochastics commented 10 months ago

I had a look. Everything looks good to me

thomasp85 / ggraph