Force-Directed Edge Bundling

[admin]

This is the thread for asking more details about the Force-Directed Edge Bundling proposal.

[mbastian]

Answers from Yestin questions, interesting to share

The goal of the proposal is adding FDEB to gephi. You said in the description of the proposal that it should be added in the preview module. Have you think about adding FDEB to the layout module? Or you think this is not reasonable? I looked through FDEB paper you supplied in general. In my point of view, FDEB is a graph rendering method or a layout method. Using edge bundling can reduce clutter of large graph. So addding it to the layout module is much properer, isn't it?

I think FDEB fits to the preview module because it's something you want to do for increasing the map readability and design after all and is not suitable for real-time calculation. The thing is that our 3d rendering engine only draws straight lines. Supporting bezier curves is completely killing performances, I made the test. That's why we keep curved lines for the preview module. Without the ability to draw the FDEB results in real-time, I think the proposal don't fit to the layout module.

You also said one of the task of the proposal is to refactor preview module. Should my application on the project contain the detail idea of how to refactor this?

The preview module currently has a quite static architecture. It will need refactoring for adding some algorithms (FDEB) that can integrates the results in the model. The idea of Preview architecture is to be on top of all outputs (Processing, SVG, PDF). In other words Preview API has to be modified to support curves that FDEB will generate.
The refactoring plan will be done with me (your fellow mentor ), so you don't need to include a detailed idea in your application. Just imagine what consequences have the FDEB integration on current Preview features like I did.

I downloaded the source code of this project, and looked through the preview module in general. If we add FDEB in preview module, we may rewrite or implement edge related class first to fit the segmentation of this algorithm. Because of limitation of time, I have a little trouble in covering all the codes and architecture of the project. Do you have any introduction or suggestion?

Right, a new edge type will appear.

In your application, imagine I'm not aware how FDEB works and explain how to code it. That would be neat.

[admin]

Example in Tulip: http://tulip.labri.fr/TulipDrupal/?q=node/231

[Yestin]

hi,
I looked a little about the code. I found the graph model in overview and preview module may be not the same.
I found the graph model in preview module may GraphImpl.java in "Preview Impl". Can you tell me where is the graph model in overview?
and how to transfer this model to the preview module? I am curiousness:)

[BigMadWolf]

GSOC post

Hi there, I'm Jeremy, the student who developed the preview related plugins during the GSOC in summer 2009. First of all, I'd like to say that working on such a Gephi part is really interesting in the way that you make use of both your visualization and software design skills.

Sebastien asked me to introduce the actual preview structure to give you guys a better understanding of the current code, and to help you to polish your proposals. So here I am!

The preview related plugins are the following:

• Preview API is, as mentioned in the overview file, the API for building the graph preview structure;
• Preview Impl is a set of classes implementing the Preview API interfaces;
• Desktop Preview contains the UI classes of the preview, especially the Processing applet redering preview graphs;
• Preview Export contains preview export classes, such as the SVG and the PDF ones.

I'll focus on the preview model implemented in the Preview Impl plugin, because I think this is the thing that might be a bit hard to understand at first sight.

In fact, the preview graph is rendered in the GUI using data from a preview graph structure, which is built from the current workspace graph data. The PreviewController controls this preview graph structure building, which is processed by the PreviewGraphFactory.

The preview settings are stored in objects called supervisors, which are hold in the PreviewModel. In addition, supervisors are implementing a kind of caching system. Indeed, when a preview graph element is created in the PreviewGraphFactory, it is set as a kind of listener to its related supervisor. Then, when a preview setting is changed, the supervisor storing it notifies all the preview graph elements, telling them to update the concerned fields. For instance, when the node color setting is changed in the preview, the new color is set in the NodeSupervisor, and preview nodes listening to it are asked to actually change their own color. Therefore, elements' fields of the preview graph structure are not dynamically computed at each call, but only at the element creation, or when a preview setting is changed.

Note that I'm not very happy with the supervisor system. If needed, feel free to refactor it, or to implement its behavior in another way.

As Mathieu said, the actual Preview API structure is quite static. It is not designed in the way that you can do too much stuff with it from an external plugin. So a related refactoring should be the next challenge for the preview, especially if you want to integrate an algorithm.

I hope this post provided you some help. Good luck & enjoy the GSOC experience!

[cklee]

All right just got caught up with everything discussed here.

Note that I'm not very happy with the supervisor system. If needed, feel free to refactor it, or to implement its behavior in another way.

Question 1 @Jeremy: Can you explain more as to why the supervisor system is not up to par? I'm looking at the code, but it would be very helpful if you could hone in on some problems.

Question 2 @Mentors: I've noticed that the Gephi currently supports PDF and SVG exports. Any plans of doing a Java applet export that is interactive? Or is that out of the scope of this project? (Similar to what Processing is able to do.)

Question 3 @All: From what I understand, this project is to extend the Peview API to handle FDEB curves. The required skillset is Processing, but I feel that the FDEB algorithms should be written out in Java?

[cklee]

Forgot to ask, but would it make sense to make a new Preview API similar to the link below?

http://gephi.org/developers/

I mean it'd be an iteration of what Jeremy wrote, but on a wiki. This would be another big TO DO, but it'd be helpful??

[mbastian]

Yes it would be useful to draft what role could Preview have in the application environment and refactor it in that sense.

It's quite essential actually, as Preview is a requirement for doing Vectorial export, even programatically. Indeed vectorial export is accessible from preview and uses preview data structure and properties to build the SVG or PDF. It should at least be possible to have an easy way to configure options and load preview presets.

The API would have at least following features:
- Configure properties, with name and value
- Load preset
- Build the preview data structure and export SVG/PDF

[BigMadWolf]

Question 1 @Jeremy: Can you explain more as to why the supervisor system is not up to par? I'm looking at the code, but it would be very helpful if you could hone in on some problems.

In retrospect, I have some doubts about implementing a caching system using the observer design pattern, especially when the observers are the thousand edges and nodes of a preview graph which is recreated relatively frequently. This could easily lead to memory leaks if one makes some changes and forgets to unsubscribe the old preview graph elements from their related supervisors. I think there could be better ideas in the literature, or even around the web.

In addition, I had once to do some refactoring in the preview module (I cannot remember what it was about), that lead to a huge change in the supervisors. Therefore, this lets me think the supervisor system would not be flexible enough in its design.

Anyway, the caching system of the preview module is working well for now, so I'm not saying you should rewrite it. But if you feel this part of the code prevents you from doing the amazing stuff you are asked for by Mathieu, you might need to find a better caching design than the one I wrote.

[mbastian]

I'm not sure the caching system is needed, in particular because there is actually no perofrmance problem at this level. Refreshing the preview is not done constantly, erasing the model and redoing it from scratch takes only cuple milliseconds. I tried disabling it and you can almost not see the difference.

Preview must just have a properties list, extensible and a list of objects and methods that can draw these objects using properties. It should have flexibility on:
* Properties, one can add a plugin with new properies, and the associates PropertyEditor class if necessary.
* Objects/Widgets, one can add a plugin that draw new elements on the preview. Renderers for Processing, SVG and PDF must be provided, but factories could help generalize.

I simplify the idea intentionnaly, Jeremy feel free to point the problems encoutered to bring these features.