You have previously completed several features for Gephi and have good algorithms background (I am sure you do better than me
)I need to get a better understanding of the barnes-hut optimization (which works really good for force atlas 2), but I think they refer to using it for quickly discarding edges based on position compatibility since if it is close to 0, the other compatibility measures would not matter.
Anyway I think we would start to implement basic FDEB, when it works create some visualization and when things are good start to think about optimizations and tuning up the algorithm.
About gradients, that's is something I was worried too. For SVG (and pdf I guess) rendering there seems to be support http://www.w3schools.com/svg/svg_grad_linear.asp but for processing rendering I think it has to be done manually http://wiki.processing.org/w/Vertical_Gradient
Eduardo
Statistics:Posted by eduramiba — 21 Mar 2012 21:24
]]>
I have some questions about the algorithm itself, could you help me get started?)
1)
Suggested Barnes-Hut optimization applicable only for combined force version from 3.1, where we don't calculate edge compatibility, right?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
(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!
Statistics:Posted by megaterik — 21 Mar 2012 18:06
]]>
Statistics:Posted by admin — 22 Apr 2010 19:53
]]>
Statistics:Posted by Yestin — 12 Apr 2010 13:42
]]>
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?
Statistics:Posted by cklee — 09 Apr 2010 14:16
]]>
]]>
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.
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.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.
Statistics:Posted by mbastian — 07 Apr 2010 00:11
]]>
cklee wrote: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:)?
Statistics:Posted by Yestin — 06 Apr 2010 13:40
]]>
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.
Statistics:Posted by Yestin — 06 Apr 2010 13:24
]]>
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
Statistics:Posted by cklee — 06 Apr 2010 12:33
]]>
]]>
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.
Statistics:Posted by mbastian — 05 Apr 2010 18:24
]]>
cklee wrote: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.
Statistics:Posted by BigMadWolf — 04 Apr 2010 22:55
]]>
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
Statistics:Posted by mbastian — 02 Apr 2010 12:19
]]>
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??
Statistics:Posted by cklee — 02 Apr 2010 03:07
]]>
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.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 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?
Statistics:Posted by cklee — 02 Apr 2010 02:59
]]>
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.
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!Statistics:Posted by BigMadWolf — 27 Mar 2010 19:37
]]>
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:)
Statistics:Posted by Yestin — 26 Mar 2010 10:44
]]>
Statistics:Posted by admin — 25 Mar 2010 20:11
]]>
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.Yestin wrote: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?
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.Yestin wrote: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 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.Right, a new edge type will appear.Yestin wrote: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?
In your application, imagine I'm not aware how FDEB works and explain how to code it. That would be neat.
Statistics:Posted by mbastian — 25 Mar 2010 16:14
]]>