GSoC/2019/StatusReports/CaioTonetti: Difference between revisions

Revision as of 17:30, 19 August 2019

Project Overview

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.

Rocs (https://kde.org/applications/education/rocs) is a Graph Theory IDE created in January of 2010, with new updates still being committed almost every month, currently in the KDE repositories, designed for lecturers, students and researchers. It is composed of a visual data structure and a powerful scripting engine in Javascript. Though useful for creating simple graphs, it is still lacking the tools to simplify the creation of bigger graphs, and also of basic graph theory algorithms for beginners. Another improvement it should have is a step by step execution system, in order to fully comprehend the algorithms and facilitate debugging.

List of Added Features

I have added the following features for the first evaluation:

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, as the classes we are using today are not present in the default Qt installation (But they can be compiled separately);
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;
- 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.

TODO

Currently, these features are yet to be implemented.

More tests related to the functionalities implemented;
The repository is yet to be implemented;

Commits

All my work can be accessed in the following Merge Requests:

About Me

Name: Caio Henrique Segawa Tonetti
Blog: chst.dev
Mentors: Tomaz Canabrava, Adriaan de Groot
Email: [email protected]
Github Id: https://github.com/LionsWrath
IRC nickname: ctonetti

Screenshots

Menu of the Path Graph Creation Tool
Menu of the Complete Graph Creation Tool
Menu of the Complete Bipartite Graph Creation Tool
Detail of the default Edge Types changed

@@ Line 7: / Line 7: @@
 == List of Added Features ==
 I have added the following features for the first evaluation:
-* '''Path Graph Creation Tool:''' Tool for creation of Path Graphs;
+* '''Path Graph Creation Tool''';
-* '''Complete Graph Creation Tool:''' Tool for creation of Complete Graphs;
+* '''Complete Graph Creation Tool''';
-* '''Complete Bipartite Graph Creation Tool:''' Tool for creation of Complete Bipartite Graphs;
+* '''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''', as the classes we are using today are not present in the default Qt installation (But they can be compiled separately);
 * '''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.
+**  Redundant code;
+**  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.
 == TODO ==
 Currently, these features are yet to be implemented.
-* More fixes in the graph class creation, as the original algorithm for tree creation is not working properly;
 * More tests related to the functionalities implemented;
 * The repository is yet to be implemented;
-* The step-by-step execution.
 == Commits ==
-My commits are on my branch on the invent.kde.org forked repo: [https://invent.kde.org/ctonetti/rocs/commits/improved-graph-ide-classes  improved-graph-ide-classes].
+All my work can be accessed in the following Merge Requests:
-As the team is not big, one of my mentors advised to not use the phabricator, as it would only complicate our workflow. So,
+* [https://invent.kde.org/kde/rocs/merge_requests/11 Self Edges Removal on Transform Edges];
-our code will be revised in merge requests on the invent.kde.org repo, which there is one as a WIP right now: [https://invent.kde.org/kde/rocs/merge_requests/2 Merge Request].
+* [https://invent.kde.org/kde/rocs/merge_requests/4 Improved Examples];
+* [https://invent.kde.org/kde/rocs/merge_requests/3 Improved Dag/Tree Algorithm];
+* [https://invent.kde.org/kde/rocs/merge_requests/2 Improved Graph IDE - Classes].
 == About Me ==