Project Name: An Improved Graph Theory IDE
Purpose: As a student, I use graphs in almost everything related to my master’s research. Graph Theory is a great mathematical tool for programmers and mathematicians, as it facilitates some computational problems resolution and modelling. However, is not always easy to understand the underlying theory and algorithms.
List of Added Features
I have added the following features:
- Path Graph Creation Tool;
- Complete Graph Creation Tool;
- Complete Bipartite Graph Creation Tool;
- Random Directed Acyclical Graph Creation Tool;
- Random Tree Creation Tool (Modified to a more well behaved random tree creation tool);
- Script Examples:
- Added Depth-First Search Algorithm;
- Fixed Breadth-First Search Algorithm;
- Added Topological Sorting Algorithm;
- Fixed Prim Algorithm;
- Added Kruskal Algorithm;
- Added Dijkstra Algorithm;
- Added Bellman-Ford Algorithm;
- Added Floyd-Warshall Algorithm;
- Added Bipartite Matching Algorithm.
- Added a interface to access the debugger tools (QScriptEngineDebugger) of our main script engine (QScriptEngine). But this one may be reworked to the new QJsEngine in the future, as the classes we are using today are not present in the default Qt installation (But they can be compiled separately);
- Added a interface to Transform Edges to remove self-edges from the graphs;
- Miscellaneous Changes:
- Removed the "default" edge type and created two new "unidiretional" and "bidiretional" edge types.
- Default values for the some graph classes;
- Variable names fixes;
- Redundant code removal;
- Changed the Mersenne Twister from the booster library to the standard library;
- Fixed the Generator Seeds of the graph generator widget;
- Changed the Topology class to static access only;
- Added correct edge type check on the DAG and Tree creation tools;
- Information about the algorithm and time complexiy of all added script examples.
Graph Creation Tools
All Graph Creation tools planned were implemented in the ROCS software. In this part, the generation of Cycles (called circle graph in ROCS) and random graphs were already implemented, so it was not listed as implemented in the feature list.
A additional modification was made on the Tree generation algorithm, as he was generating invalid tree graphs depending on which edge direction was used in the generator (resulting in cycles). The new algorithm used is presented in this paper, and it is proved that it can generate all possible tree with equal probabilities.
Step-by-Step Execution and Debugging
This feature is provided by the use of the QScriptEngineDebugger class, that already offers a complete debugger interface for the QScriptEngine, as can be seen in the Debugger Interface image.
So, a special button was created to identify when the programmer want to use the debugger or not (showed in the Debugger Button image). When it is clicked, the debugger will be launched with the code being run and the programmer can debug the code properly. Otherwise the code will be run normally.
It is important to note that the support for the Webkit in Qt is deprecated and should be target of revision in the future when Qt version 6 is around. One of the main problems in using the new QJsEngine right now is the missing debugger feature.
An short explanation and the general time complexity is showed in the beginning of each script, as can be seen in the Script Explanation Example image.
I have talked with my mentors and we decided that right now is not a good moment to implement a remote repository for the scripts, as the ROCS is still lacking in other more important features that need to be implemented first (see What's Next for some examples).
It's is possible to check what was merged and what was not in the following links. All my work can be accessed in the following Merge Requests:
- Self Edges Removal on Transform Edges;
- Improved Examples;
- Improved Dag/Tree Algorithm;
- Improved Graph IDE - Classes;
- Debugger option on script menu.
There are still many things that can be improved in the ROCS software that go out of the scope of my project. Here are some examples:
- 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;
- 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.
- Name: Caio Henrique Segawa Tonetti
- Blog: chst.dev
- Mentors: Tomaz Canabrava, Adriaan de Groot
- Email: [email protected]
- KDE Invent ID: https://invent.kde.org/ctonetti
- IRC nickname: ctonetti