Lakademy 2019

I’m now writing this post in the last hours of the Lakademy 2019 (and my first one). It was really good to be “formally” introduced to the community and it’s people, and to be in this environment of people wanting to collaborate to something as incredible as KDE. Althought I wanted to contribute more to other projects, I did some changes and fixes in the rocs, wrote my Season of KDE project and got some tasks that can help with the future of rocs.

Together

This event showed me the passion that even the most veteran members have for the software, and how, even after years of collaboration, they are still teaching new members and putting everything they got to create better softwares for everyone. On the other side, seeing the new members collaborating for the first time with such desire to share and learn helped me with the energy to help more.

People

I just have to thanks KDE for everything they provided to me during these months of Google Summer of Code, for the help to come to Salvador to be a part of this community and for the good laughs. It was incredible! To the next Lakademy and (i hope so) Akademy. :)

Special thanks to Tomaz, that introduced me to KDE!


First Day of Lakademy

And Lakademy is finally here! This is not my first direct interaction with a KDE member, but I was sort of nervous to met many members at once, since it has been less than a year that I began contributing to KDE. As I got off the plane I got to know a member of the translation team with a KDE t-shirt and talked to him (he came in the same plane with me), and he introduced me to other members. We got to the hostel and, as we arrived one day earlier, we went out to drink, talk and eat acarajé (which was incredible). It was a nice evening and I got to know better the most veteran and new members.

Arrival

Next day, we got up early to move to the Universidade Federal da Bahia and began the Lakademy. Some members went to buy groceries and some went directly and prepared the room. After a round of presentations, Lakademy was declared online! I spent most of the time reviewing ROCS code and wrote some fixes for redundant code and a problem with the interface that was introduced in one of the last commits. After that, I listed some tasks that could be done this week. We finished the first day of Lakademy sharing what we did and went back to the hostel to prepare to have dinner and some fun in Salvador. :)

Lakademy1

Looking forward for the next days!


Step-by-Step Execution and Examples

Last week I finished writing all the new examples for the ROCS, together with a little description of each commented in the beginning of the code. The following examples were implemented:

  • Breadth First Search;
  • Depth First Search;
  • Topological Sorting Algorithm;
  • Kruskal Algorithm;
  • Prim Algorithm;
  • Dijkstra Algorithm;
  • Bellman-Ford Algorithm;
  • Floyd-Warshall Algorithm;
  • Hopcroft-Karp Bipartite Matching Algorithm.

It is good to note that while Prim algorithm and BFS were already in rocs, they were broken and could not be run. The following image is an example of a simple description of an algorithm:

Description

About the step-by-step execution, I am considering our possibilities. My first idea was to take a look into the debugger for the QScriptEngine class, which is the QScriptEngineDebugger class. An instance of this class can be attached to our script engine, and it provides the programmer with a interface with all the necessary tools.

Although useful, I personally think our rocs don’t need all this tools. (but they can be provided separately) There are 3 ways to stop the code execution using this debugger:

  • By an not treated Exception inside the javascript code;
  • By a call to the debugger instruction, that automatically invokes the debugger interface;
  • By a breakpoint, that can be put in any line of the javascript code.

The first one is not really useful for us, as it halts the code execution. The second and the third can be really useful couple with an Continue command. But the second invokes the full debugger interface, which we don’t really want.

Debugger

So, by using the third one, we can stop the execution in any line of the javascript code and create a step button with the Continue command to continue executing the code. The only problem is how to add the breakpoints, as there is no direct function to add them, and usually the programmer has to use the ConsoleWidget interface or the BreakpointsWidget to do this. The following image shows the Continue button, which is already working:

Continue

But the challenge of adding the breakpoints still remains. One of my ideas is to modify the code editor to accept an click on the line number bar, which triggers an signal to add/remove an breakpoint to that line. This is an clean alternative for me. But for that I have to check if the KTextEditor have this type of signal and create a way to add breakpoints in the code by function.


View and Examples

This week I began learning about QML to try to fix the View that show the graphs and tools for manipulating graphs. More precisely, I wanted to deal with some problems:

  • Vertexes that go near the border of the view cannot be moved;
  • Ctrl-A do not select all the view, just a limited part;
  • The option menu in the Create Node and Create Edge puts the lateral menu over the scroll bar;
  • The scroll bar in the view don’t have much use, as the view is tiny, and the mouse can be used to move in most cases;
  • The Flickable motion from the Qt is stealing most of the clicks from the MouseArea (maybe remove the interactive option while outside the Select/Move?), making really difficult to create new edges;
  • The Icons for the tools are not being showed.

This is the view now:

Old View

This is an probable new view (under implementation), that I will present to my mentors:

New View

I have been studying QML to modify this view and little by little I am building it. Moreover, I modified the two original examples in the code BreadthFirstSearch and PrimSpanningTree to work in the current system (they were with commands not valid for the current version, like interrupt()). I also added one more example for the other search algorithm, DepthFirstSearch and the other implementations are under way:

  • Topological Sorting Algorithm;
  • Kruskal Algorithm;
  • Dijkstra Algorithm;
  • Bellman-Ford Algorithm;
  • Floyd-Warshall Algorithm;
  • Bipartite Matching Algorithm.

I had some other ideas for the interface that can be easily implemented and is a good way to improve the workflow:

Interface

This configuration create more space for the programmer while leaving enough space to visualize the graphs correctly and it works well with a new horizontal toolbar.


The new view is not yet available, as it is only local code. The new algorithm for DAG creation and examples are available in the merge requests here and here, respectively.

(Also, I have been really sick in the last week, but now I think I am better!)


GSoC Update

Last post I said that I was having some problems pushing my modifications to the git repo. I discovered that the official ROCS repository was recently moved to the KDE Gitlab repo, called KDE Invent, where I am working on a fork of the original ROCS repo.

It is a model that I have some knowledge, as I already worked with gitlab in a past internship and did some merge requests because of the Hacktoberfest (I like to win t-shirts). So I had to update my remote of the local repo and I sent my update to my remote fork branch, called improved-graph-ide-classes.

When I was modifying the code, I noticed some problems with the creation of random trees, but I am thinking what is the better way to fix this part. This problem lies in the relation of the algorithm and the edge types available to generate the tree. When using directed edges, the code is sometimes generating directed loops of size 2 in the graph.

Directed Loops

Theorically speaking, the definition of a tree must have undirected edges, otherwise it would be a Directed Acyclical Graph (DAG). There are different algoritms to generate them with different uses. For example, to generate random trees for a given number of nodes, you could choose an algoritm that can generate any tree of the given number of nodes with the same chance [paper] (that means, the algoritm has a uniform distribution of trees when a good seed is guaranteed). As for DAG’s, we can use an ranking algorithm to configure the height and width of the graph, which could be more useful in most cases. While there can exist a algorithm to generate both, I think it would be more useful to separate them.

But then enter the problem: It is not guaranteed that a undirected/directed edge type will exist within the Edge Types of the program, as the user has the freedom to add and modify any edge type. I found two ways to solve it:

  • Always have an undirected and a directed edge in the edge types;
  • Put a check on the interface to check whether the edge is directed or undirected when necessary;

This decision boils down to restrict or not the freedom of the user. Although this not change much on the greater scope of the program, we have to decide if the best way to go is to always force the user to check for the existence of a necessary edge type, or just set two edge types that will always exist and work by restricting the modification of the edges.


Next post I will talk about the identifier part of the ROCS system, as it is a part of ROCS that needs some more polish.