Table of contents

• Introduction
• Project Structure
• Algorithms
  • Breadth first search - BFS
  • Bidirectional BFS
  • Depth first search - DFS
  • Dijkstra
• Conclusion

DISCLAIMER It was the first complex client-rendered webapp I built. I disregarded bundle size, so it takes some seconds to load.

Introduction

This project was designed to visualize graph algorithms in an intuitive and interactive way. It implements the main graph algorithms for solving mazes:

• Breadth first search (BFS)
• Biderectional BFS
• Depth first search (DFS)
• Dijkstra

In addition to the ability to generate mazes programmatically through the recursive division algorithm, the webapp has the ability of adding weights to each box in the maze when Dijkstra's algorithm is selected as it can work with weighted graphs.

Project Structure

In terms of project strucutre it was designed to mimic MVC architecture. Nonetheless, shortly after I realised that React isn't quite built to support it, so it is what it is. Even with that the structure is quite readable, being the model focused on the actual algorithms, and the components focused on the different UI elements of the webapp.

src
├── App.tsx
├── MainApp.tsx
├── components
│   ├── colors.js
│   ├── controllers
│   │   ├── AlgorithmMenu.tsx
│   │   ├── ClearButton.tsx
│   │   ├── MazesMenu.tsx
│   │   ├── SolveButton.tsx
│   │   ├── SpeedSlider.tsx
│   │   └── weightedMazeOption.tsx
│   ├── imgs
│   │   ├── crumbs.svg
│   │   ├── dog.svg
│   │   └── steak.svg
│   ├── presentation
│   │   ├── WelcomeGuide.tsx
│   │   └── tutorial
│   │       ├── AlgorithmMazeExplanation.tsx
│   │       ├── CanvasInformation.tsx
│   │       ├── FunctionButtonsExplanation.tsx
│   │       ├── InformationBoxExplanation.tsx
│   │       └── Tutorial.tsx
│   └── viewer
│       ├── Canvas.tsx
│       ├── InformationBox.tsx
│       ├── InformationBoxMaze.tsx
│       ├── Node.tsx
│       └── unweightedAlgorithm.tsx
├── index.js
├── model
│   ├── algorithms
│   │   ├── AlgorithmsEngine.ts
│   │   ├── BFS.ts
│   │   ├── BiderectionalBfs.ts
│   │   ├── DFS.ts
│   │   └── Dijkstra.ts
│   ├── animations
│   │   ├── AnimationsEngine.css
│   │   ├── AnimationsEngine.ts
│   │   ├── gridSelectionAnimation.tsx
│   │   └── toggleWallAnimation.ts
│   ├── grid
│   │   ├── GridEngine.tsx
│   │   └── NodeEngine.ts
│   └── mazes
│       ├── MazesEngine.ts
│       ├── RecursiveDivision.ts
│       ├── elevationAnimations.ts
│       └── random.tsx
├── outils.ts

Algorithms

Breadth first search - BFS

Breadth First Search (BFS) is set to initialise at a vertex and then moves on to traverse all the nodes with the current height before traversing all the others with next depth level. Because in the worst case it traverses the whole graph, its complexity is O(V + E) where V are the vertices and E are the edges of the graph. It works with non-weighted graphs

Bidirectional BFS

Bidirectional BFS works by running two BFS simultaneously, one starting from the dog and another starting from the steak. It has the same limitations and BFS but in practise it's usually quite faster due to reducing the total number of traversed vertices.

Depth first search - DFS

Depth First Search (DFS) works analogously to BFS but traverses in order of the deepest vertex possible at every step, before reaching it and backtracking. Like BFS it works with UN-WEIGHTED graphs, and traverses the whole graph in worst case so its complexity is O(V + E). Contrary to BFS, it doesn't guarantee shortest path

Dijkstra

Dijkstra's picks the unvisited vertex with the lowest distance (closest vertex), calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. It repeats this until it finds the end-node.

Its complexity varies upon the way we store the closest nodes, being the best one O(lgV*V + E) where V are the vertices and E the edges. It works with WEIGHTED graphs

Conclusions

In conclusion, the webapp was a really interesting challenge, both on terms of algorithms and Reactjs. It teached me on the importance of bundle size and dependencies as projects get larger, and a lot about graph algorithms. I learned that with algorithms the value comes from being able to solve real problems, by translating the problem into a set of constraints and then applying the best algorithm to solve it.