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:


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.


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:


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:


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.

Crazy Last Weeks

Last weeks have been crazy for me. Since the GSoC began, I have been rushing everything related to university and my life to dedicate exclusively to the development. Besides the two classes I was taking, Static Code Analysis and Approximation Algorithms, I had my obligatory teaching internship in Project and Analysis of Algorithms for the postgraduate program, where I was responsible for creating and evaluating assignments for 50+ students and answering general questions.


Besides that, I was in the organization of the Latin & American Algorithms, Graphs and Optimization Symposium during June 2nd to 7th, where I was responsible for a plethora of things before and during the event (Although it was a lot of fun, a lot of researchers from all around the globe and incredible research). And, just as I got back, I had to delve back to tests, assignments, seminars…

One of the problems for brazilians in taking the GSoC is that the beginning of the program does not match exactly with the end of our classes. But now, as everything is (finally!) ending, I can focus entirely in the GSoC and my project. Just before the GSoC (and before even creating my project), I had compiled to KDE Framework 5 and the ROCS software, so most of the development environment was already set.

I am using as my environment the Qt Creator, and I am focusing in the algorithm for creation of specific graph classes inside the generategraphwidget. I have already implemented algorithms for Paths, Complete and Complete Bipartite graphs, besides fixing some details here and there. These modifications are still only in my local machine, as I am having some problems pushing the commits (I must be doing something wrong in my configuration).

I noticed that the calculation of the position of the graphs generated is strange, as it put the graphs almost ouside the view (and we can’t push the view there), so probably the positioning must be corrected. There is a function for calculating the center there, I will compare that function to the point where the view always come back and adjust accordingly. Another detail is the symbols of the view tools, that are not showing correctly.

Hello GSoC and KDE!

My first post! :)


I created this simple blog to write updates related to my Google Summer of Code Project. Soon I will be detailing my experience on the Community Bonding phase!