GSoC 2020 and KDE

Tomorrow (29/06/2020) begins the first evaluation of the Google Summer of Code 2020. Last GSoC, when I was participating as a student, I wrote in my final report a set of future proposals that could be done in the ROCS graph IDE (Section What’s Next?). This year, some students got interested in these ideas but only one could enter the program (we didn’t have enough mentors for more than one project). Here are the list that I proposed:

• Implementation of a better algorithm to position the nodes and edges on the plane. I can recommend the use of Force-directed graph drawing algorithms, because they are usually fast and are physics-based;
• Create a better interface workflow for the program. I can recommend something like the Possible New Configuration image. This configuration consider that the user will spend most part of the time programming, so it creates a better writing space, while the view has a more square shape, which is (in my opinion), better for visualization;
• Remodelation of how each graph is represented in the javascript code. The type system is good to provide a global configuration, but I think it falls apart when dealing with individual edges and dynamic creation of subgraphs and new edges/nodes (which is needed in some algorithms);
• Rewrite the view to deal with some problems related to the space of the graphs that is really limited, mouse clicks not working correctly and bad navigation;
• Change how the icons are used by the ROCS, as some icons don’t have cross-compatibility between some systems.

From this list, Dilson decided to tackle the first one listed. Here is his proposal. Most of the best algorithms involves some type of heuristic inspired in physical motions in the graph, being really fast and good in most graph classes (although there is specialized algorithms for some graph classes). You can see more of his work here. He is doing a great job by showing a good understanding of the algorithms and methods while giving a great amount of thought in the test process (as it is not trivial to test random algorithms).

For now, he implemented a layout algorithm that is an adaptation of the Fruchtermani-Reingold algorithm that works only on connected graphs in a special plugin that controls each physical forces inside the model. I will be giving some updates on his work sparsely in this blog. Please check his blog for more details if interested. :)