GSoC/2020/StatusReports/DilsonGuimaraes: Difference between revisions
Dilsonguim (talk | contribs) |
Dilsonguim (talk | contribs) |
||
| Line 14: | Line 14: | ||
The graph-layout plugin user interface can be found at Graph Document -> Tools -> Graph Layout. There is a separate tab for each one of the layout algorithms available. In each one of these tabs the parameters of the corresponding layout algorithm can be selected. | The graph-layout plugin user interface can be found at Graph Document -> Tools -> Graph Layout. There is a separate tab for each one of the layout algorithms available. In each one of these tabs the parameters of the corresponding layout algorithm can be selected. | ||
Functional tests were written for each layout algorithm, checking the behavior of the algorithm in some simple cases. Non-functional tests were written to evaluate performance of each algorithm in terms of layout quality. | |||
Documentation is provided both in the source code level and in the application level. In the source code, the public interface of the class that generates the layouts is documented in details. Other parts of the code also include comments describing each function and some implementation decisions. In the application level, a description of how to use each one of the available layout algorithms is provided. | |||
==== Force-Based Layout ==== | ==== Force-Based Layout ==== | ||
| Line 22: | Line 25: | ||
[[File:Force-based-layout-ui-screenshot.png|thumb|left|Graph-layout plugin user interface.]] | [[File:Force-based-layout-ui-screenshot.png|thumb|left|Graph-layout plugin user interface.]] | ||
[[File:2020-06-17-planar.png|thumb|right]] | [[File:2020-06-17-planar.png|thumb|right|Layout generated by the Force-Based Layout Algorithm.]] | ||
Revision as of 22:14, 24 August 2020
Project Overview
Project name: Better Graph Layout for the Graph Theory IDE
The goal of this project is to enable Rocs (https://kde.org/applications/education/rocs) to layout graphs automatically. The project consists of three parts. The first one deals with a layout algorithm that can be applied to any graph. The second part and the third part deal with layout algorithms for trees and directed acyclic graphs, respectively.
The original proposal can be found here.
Work Report
Added features
I created a tool to apply layout algorithms to graphs in Rocs, named graph-layout plugin. It allows the user to select an algorithm and apply it to a graph. Algorithm specific parameters can also be selected. In total, three algorithms were implemented: Force-Based Layout, Radial Tree Layout and Layered DAG Layout.
The graph-layout plugin user interface can be found at Graph Document -> Tools -> Graph Layout. There is a separate tab for each one of the layout algorithms available. In each one of these tabs the parameters of the corresponding layout algorithm can be selected.
Functional tests were written for each layout algorithm, checking the behavior of the algorithm in some simple cases. Non-functional tests were written to evaluate performance of each algorithm in terms of layout quality.
Documentation is provided both in the source code level and in the application level. In the source code, the public interface of the class that generates the layouts is documented in details. Other parts of the code also include comments describing each function and some implementation decisions. In the application level, a description of how to use each one of the available layout algorithms is provided.
Force-Based Layout
The Force-Based Layout algorithm was implemented in the first phase of the project. It is the simplest and the most general algorithm from the ones considered in this project. It can applied to any graph, but no guarantees are given about the resulting layout. In practice, it can generate reasonable results for some graphs.
A screenshot of the corresponding tab in the graph-layout plugin user interface follows, as well as some example layouts generated by the Force-Based Layout.
Implemented layout algorithms
The layout algorithms in this section are already implemented, tested and documented.
- Force based layout: A graph layout algorithm based on the simulation of forces acting on nodes.
- Radial tree layout: A graph layout algorithm specifically designed for trees.
Layout algorithms to be implemented in the future
The layout algorithms in this section will be implemented during the remaining time of the project.
- A layout algorithm for Directed Acyclic Graphs.
Merge requests
All my commits can the found in the following merge requests.
Graph-layout plugin, with force-based layout and radial tree layout.
Blog
My blog can be found here.. The links to posts related to this project are given below:
Experience
I really enjoyed working on this project. Most of my experience writing software is related to research, competitive programming or course projects. This project was a great opportunity for me to work in something different and get more experience working in a code base I did not create, with tools I did not choose. I learned a lot about Qt, which is used a lot in Rocs.
The open source world is something new for me. I already knew and used a lot of open source software, but I never contributed before deciding to apply to GSoC. The efforts of open source communities such as KDE are able to produce great results and it feels nice to become part of something so amazing.
I had to learn about graph layout algorithms to implement this project. I always have fun when I learn new algorithms. This time was not different. Two of the three layout algorithms I implemented are completely heuristic. The only way to get an intuition about the results that they can achieve is by experimentation. Although I love when there is a mathematical proof that the result of an algorithm is good, there are many important situations in which the best thing that can be done is to write a heuristic solution and test it a lot. This is why I value the experience I had working on them.