## 2 MaGraDa Software Tool
### Description of the Visualisation and Computational Tool
#### 2.2.3. Algorithms and View Algorithms  
The third menu, _Algorithms_, implements some well-known algorithms in the context of graphs (see, e.g., [3; 4; 5; 6; 33; 40; 44; 45; 46]). For both weighted and unweighted graphs, this menu offers the Warshall algorithm [33; 45] and the Fleury algorithm [4; 33]. For the Warshall algorithm, MaGraDa displays all iterations needed to obtain the reachability matrix from the adjacency matrix, and highlights the changes from one iteration to the next. At each step of the recursive Warshall algorithm, the user can move forward and backwards through the iterations. The presentation of the Fleury algorithm, in which an Eulerian tour or Eulerian path is built, differs between the text mode and the graphic mode: in the text mode, an Eulerian tour or path is obtained as requested, whereas in the graphic mode, the application requests the user to build the Eulerian tour (or path), so that at each step, when the user selects an edge or arc to add to the tour (or path), the application determines whether it is suitable or not based on the Fleury algorithm. The remainder of the algorithms listed in the third menu are related to weighted graphs. More specifically, MaGraDa implements the critical path algorithm for use with a PERT and the shortest path algorithm for acyclic graphs using Bellman equations [4]; the Dijkstra and Floyd-Warshall algorithms [3; 4] to find the shortest paths from one vertex to the rest or between each pair of vertices, respectively; and the Kruskal and Prim algorithms [5; 6], which obtain a minimum spanning tree from a weighted and undirected graph. All these algorithms are presented in such a way that the user can recognise the steps that have been followed in their execution, thus acquiring important pedagogical value. For example, Figure 9 shows the two first iterations of the Floyd-Warshall algorithm when applied to the graph defined by the weighted adjacency matrix \(\Omega=\Omega^{(1)}\). Note that the interface highlights the changes from one iteration to the next. As an application of the Floyd-Warshall algorithm, users can also obtain a specific shortest path between any two vertices by selecting the specific option included in MaGraDa. The solutions of these algorithms (shortest paths, critical paths and minimum spanning trees) are also displayed graphically on the canvas in the graphic mode. Figure 8. Obtaining the connected components step by step. The option from the _Basic calculations_ menu that permutes the vertices of a graph can be used to teach and learn some characteristics of the Floyd-Warshall algorithm. More specifically, the Floyd-Warshall algorithm can be applied to obtain the shortest path between each pair of vertices with the constraint that each path contains only the intermediate vertices from a restricted set (see e.g., [4]). To solve this problem, a previous permutation of vertices is needed. For example, Figure 10 displays the last two iterations of the Floyd-Warshall algorithm, when the vertices of the graph of Figure 9 are permuted using the permutation \((A,B,C,E,F,D)\). This permuted graph can be obtained with the above-mentioned option (see Figure 10a). Iteration 6 (where \(D\) is the sixth vertex in the permutation) in Figure 10b represents all the shortest paths, with the restriction that vertex \(D\) cannot appear as an intermediate vertex of any path. Obviously, iteration 7 in Figure 10c obtains all the shortest paths with no restrictions. Figure 10: Floyd-Warshall algorithm. Figure 9: First two iterations of the Floyd-Warshall algorithm. Figure 11 illustrates the output of the PERT algorithm when applied to the graph created from the activities table in Figure 7. Figure 11a shows the graph with the critical path (white arcs) and the minimum time required to complete each activity (yellow numbers at each vertex). Figure 11b provides information about the critical activities and the maximum allowable delay to complete a non-critical activity without affecting the project end date.