[
kde
gsoc
2019
]
12 Aug 2019
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.
[
kde
gsoc
2019
]
21 Jul 2019
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:
This is an probable new view (under implementation), that I will present
to my mentors:
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!)
[
kde
gsoc
2019
]
27 Jun 2019
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.
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.
[
kde
gsoc
2019
]
22 Jun 2019
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.
[
kde
gsoc
2019
]
13 May 2019
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!