Force-Directed Edge Bundling

[BigMadWolf]

IMHO if you want to add new preview properties from external plugins, the supervisor system won't be coherent, so you should simply drop it and put the internal properties elsewhere (let's say in the PreviewModel), especially if there is no performance issue. In addition, the less code you have, the less bugs you get.

[cklee]

Let me try to explain everything in my own words to make sure I have a good grasp of everything.

Create a new PropertyEditor class to handle new object and widget plugins. (I assume that PropertyEditor needs to be developed since I could not find it in the Javadoc.) Each property plugin would be a new element that would change how the preview is drawn. One example of a property plugin if FDEB. Another example would be parallel coordinate alignment when Data Laboratory is completed. Parallel curves, elastic lists, clustering treemaps, scattered maps, etc. are all possible property ideas that will need a Preview plugin. Is this where PropertyEditor comes in?

Idealistically any new plugin developed for Gephi would work seamlessly with the supervisor system and PreviewModel. Unfortunately, this is easier said than done. Dropping a complimentary plugin inside the PreviewModel every single time a developer designs an external plugin might be tedious. PropertyEditor should handle this task within PreviewModel?

And as FDEB is being developed, why can’t we establish a PropertyEditor format, with given wrapper code for developers to easily include the necessary Preview classes for the new plugins they develop? This is important so that in Preview, the image is drawn and exported correctly. In other words, PreviewFDEB, PreviewParallelCures, PreviewElasticLists, etc. could be written and dropped in the PreviewModule within a PropertyEditor framework. It could automatically amend PreviewController and add a new Supervisor for the new plugin. This way, the existing PreviewModule, PreviewController, and supervisors will not need to be changed.

@Mathieu Are these the plugins you had in mind?
http://forum.gephi.org/viewtopic.php?f=5&t=16

[Yestin]

Some ideas about refactoring:

In order to refactor preview module, we must know what defects does current module have.
In my point of view, this module maybe not easy to add new features. Take this GSoC proposal for example, if I want to add FDEB in to this module , I have to rewrite Node.java and Edge.java to support segmentation. Besides that, I also have to modify PreviewPreset.java. Though implement preset is supported in this module, It's not quite simple because it's a little tightly coupled in my view. I think a XML-based configuration and reflection mechanism maybe better for this module.Telling about XML-based configuration + reflection, I have some experience on it: When I want to add some new feature on one of my project, I modify my XML file and add new class only. None of the former code is modified.

I didn't pay much attentation to the preview export api until Mbastian's word about refactoring data structure to support SVG/PDF easily. After looking through those codes in general, I find the PDFExporter is in help with another opensource project of apache to transport svg to pdf. The SVGExporter also use the SVGDOMImplementation of Apache.What we have to do is to modify the data structure of our graph and SVGExporter.java. Our goal is this: after refactoring, SVGExporter.java should not be modified or only be implemented easily when the data structure of graph changed or new features like FDEB are added. To be honest, I don't have a very good idea about this problem.

Telling about the huedles, I think how to find a proper abstract layer about the data structure maybe hard to decide.

[Yestin]

Create a new PropertyEditor class to handle new object and widget plugins. (I assume that PropertyEditor needs to be developed since I could not find it in the Javadoc.) Each property plugin would be a new element that would change how the preview is drawn. One example of a property plugin if FDEB. Another example would be parallel coordinate alignment when Data Laboratory is completed. Parallel curves, elastic lists, clustering treemaps, scattered maps, etc. are all possible property ideas that will need a Preview plugin. Is this where PropertyEditor comes in?

I'm very happy to say that I agree with your opinion about the "PropertyEditor". I think XML configuration + reflection mechanism is also an alternative way to do this thing.

After reading your words, I know you are a researcher on visualization, maybe infovis like me. I also recommended the mentor to use parallel coordinate rather than scatterplot to show multi-dimension data(But I forgot on what module). treemap is a good visualization metaphor for visualize tree structure, I don't think it can visualize graph with complex edges and nodes.
By the way, I haven't heard about elastic lists but it sounds interesting ,can you give me some guide about this metaphor:)?

[mbastian]

I made some comments about the refactoring on your proposals on GSOC website. They answer different questions, nicely complementary. Here they are.

I would suggest to directly plan Preview API rewriting in your proposal instead of modifying current implementaion. Thanks to his experience by mentoring Jeremy past year, the mentor is well-suited to start this work. The aim is really to simplify the architecture, it will look much more easy and straightforward to add FDEB features. The student job is to help porting the current Preview API. However it is a very good exercice to try to change current Preview API to add FDEB features. That will highlight that it's not easy to do and convince the student that it could be much more easier with a proper modular architecture. Putting the anonymous plugin developer shoes is often needed to understand what are the most important features to include in an API. An API should serve developers in a way most common things are easy to do and more complex remains possible. Making everything possible leads to two much abstraction. While working with us, you'll know more about these concepts and you will be invited to read some references. Please try to imagine a simpler system for Preview, that would fit with the current and future (basic) uses-cases. You could read about API design on this website (http://wiki.apidesign.org/wiki/Main_Page) it's a short version of what you could find in one of the book that inspired current Gephi architecture. It's a must read for Gephi developers.

Due to performance issues, SVG and PDF exporters have to do a lot manually. We tried to use Batik or iText to convert SVG to PDF but that fails for the moment due to performance problems. Therefore we have 3 different types of rendering target: Processing, SVG and PDF. We don't expect to add new target and can live with the fact each of them has to be maintained with its drawbacks. But as you were pointing it, that is a problem for modularity. However we can do much better than what we have currently. There is presently no abstaction on what is an rendered object, everything is done in the render() routine of Processing, SVG and PDF renderers. One can imagine having a Renderer interface that would provide code for rendering an object (let's say a node) in a particular target. In my opinon I would read properties in these renderers. That would replace supervisors system and provide extensibility, by letting plugins create or repace current renderers.

The Preview issue is not something simple to solve, once GSOC started the real work will start and what needs to be redone will be clearly set, together. You already showed good understanding on the problem, please continue in that way! The discussion is very fruitful.

[Yestin]

I posted my proposal about refactoring graph model as he said above. But I didn't describe how to refactor in detail. I quite agree with what he said about the importance of API, but I'm afraid of not having enough time to wirte it detailedly in my application. I will try my best with your instruction in the future:)

[cklee]

Wait Yetsin, what are the performance problems for the SVG and PDF renderers/exporters?

I have an idea as to how Processing and its render() routines could be organized into a rendering engine class that linked in node, edge, and child properties produced from FDEB algorithms with appropriate factories/generators. But I don't see how SVG and PDF exporters could be improved on?

And do you have any idea how these three renderers could be moduled so that the supervisor system provides extensibility?

[Yestin]

hi cklee,
In my opinion, the SVG exporter is too complex for some open-source parsers to export, so lots of this part was done manually. You can see this in SVGExporter.java and reference about SVG. Batik and iText are not able to convert SVG to PDF properly, so the "export to pdf" seems not availiable. This is not a very bad news because if we refactor the data structure, the existing SVG and PDF exporter is useless and must be written. If FDEB is to be implemented, All these two parts must be considered. This is not a easy job, I havn't got a clear idea yet and I'm thinking about it now. But I think besides refactoring of Graph model, something must be done on the abstract layer of data model and export module.

[admin]

A complementary work: hierarchical edge bundles

[megaterik]

Hello,

I have some questions about the algorithm itself, could you help me get started?)
1)

We consider the improvement of the performance and computational complexity of FDEB, which is O(N · M^2 · K), with N = iterations, M = edges, and K = subdivision points per
edge, to be the most important direction for future work.A straightforward way to directly address this is to use asubdivision-based approach such as Barnes-Hut simulation to attain O(N · M log M · K) complexity

Suggested Barnes-Hut optimization applicable only for combined force version from 3.1, where we don't calculate edge compatibility, right?
(We can't compute center of mass, when force depends not only on the distance, but also on the edge compatibility = angle compatibility * scale compatibility * position compatibility * visibility compatibility, can we?)
2)
Render gradients(chapter 4.1) is tricky, we can't use OpenGL and our image is a vector rather than raster, is there an standart solution for accumulating gradient in that case? I can write something like O(E^2) algorithm, which for every combination of edges(i,j) increments such segment of edge i, that distance from any point of segment to edge j is less than some constant k. That should work, however maybe there is no need to reinvent wheel

Thanks!