## Table of contents

**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.