When I was first learning about the graph data structure and its various algorithms, I came across several graph algorithm visualization websites which helped me improve my understanding of these algorithms. As a fun little personal project, I decided to implement my own web-based graph algorithm visualizer.

The application can be accessed under graphs.amartabakovic.ch. The source code is in the GitHub repository AmarTabakovic/graphs and is licensed under the MIT license.

## Features

### What Can It Do?

The application is currently able to do the following:

- Allow custom graph creation with (un)weighted and (un)directed edges
- Generate randomized graphs
- Compute and visualize the following algorithms from a chosen initial vertex:
- Depth-first search
- Breadth-first search
- Dijkstra’s algorithm

- Adjust the visualization speed dynamically

### What Can It Not Do?

Some of the following features were explicitly not implemented:

- Negative weights (since e.g. Dijkstra’s algorithm would be unable to run properly in that case)
- Responsiveness, especially for small screen sizes

## Implementation Details

### Technologies

For this project, I mainly used plain JavaScript and its built-in Canvas API. The styling is done with SCSS. I picked a boilerplate Webpack project for bundling and minifying. The application is hosted on AWS Amplify.

### Application Structure

The application is split up as following:

```
src
├── fonts
│ └── Inter.ttf
├── images
│ └── favicon.png
├── index.js // Entry point of the application.
├── js
│ ├── algorithms.js // Contains graph algorithms.
│ ├── canvas.js // Contains functions for canvas manipulation and drawing.
│ ├── edge.js // Represents a single edge in a graph.
│ ├── graph.js // Represents a single graph.
│ ├── main.js // Main application file.
│ ├── state.js // Stores the global state of the application.
│ ├── ui.js // Responsible for certain UI elements.
│ └── vertex.js // Represents a single vertex in a graph.
├── styles
│ ├── _form.scss // Form styling.
│ ├── _mobile.scss // Mainly for mobile error message.
│ ├── _scaffolding.scss // Style scaffolding.
│ ├── _variables.scss // SCSS variables.
│ └── index.scss // Main SCSS file.
└── template.html // HTML template.
```

### The Graph Data Structure

#### Graph Class

For the graph data structure, I implemented a class `Graph`

in the file `graph.js`

. This class contains methods
for inserting edges and vertices and for resetting the graph’s state to before an algorithm was run. It also contains a static method
that returns a new graph with randomized vertices and edges. Vertices and edges are saved in the graph’s internal vertex list and edge list.

#### Vertex Class

The class `Vertex`

in the file `vertex.js`

represents a single vertex that a graph can have. A vertex has a $(x,y)$-position
to know where it is positioned on the canvas. A vertex also has an ID, a list of incoming edges and a list of outgoing edges. Lastly,
the vertex has a state, which can be either `unexplored`

or `explored`

. The possible state values are saved in the enumeration `VERTEX_STATES`

.

#### Edge Class

The class `Edge`

in the file `edge.js`

represents a single edge between two vertices. An edge consists of two
vertices `vertex0`

and `vertex1`

and can be directed or undirected. The edge always gets added to the outgoing edge list of `vertex0`

and if the edge is directed, the edge gets added to the incoming edge list of `vertex1`

. If the edge however is undirected,
the edge gets added to the to the outgoing edge list of `vertex1`

as well, since undirected edges are always outgoing from both vertices.
Furthermore, an edge has a weight that must be positive and a state that is
either `unexplored`

, `discoveryEdge`

, `backEdge`

, `crossEdge`

or `relaxed`

. The possible state values are saved in the enumeration `EDGE_STATES`

.

### Drawing the Graph on the Canvas

#### HTML Canvas Elements

There are two separate `<canvas>`

elements, one for the vertices and one for the edges. The edge canvas lies on top of the
vertex canvas and is responsible for catching all mouse press events. The reason for this is that with a single canvas, vertices and edges would be able to draw over each other in an inconsistent manner. For example, if one were to draw two vertices and an edge between them, one could add a third vertex between the two vertices, which would then be drawn on top of the edge.
With the current approach with two canvasses, edges are drawn on top of vertices by default, thereby avoiding inconsistencies when drawing the graph. The canvas layering approach is shown in figure 2.

#### Drawing Logic

The file `canvas.js`

is mainly responsible for the canvas drawing logic and contains methods for drawing vertices and edges.

##### Drawing Vertices

The function `drawVertex(vertex, vertexColor)`

draws a given `Vertex`

instance in a given `vertexColor`

. The vertex is drawn at its \(x\) and \(y\) positions on the vertex canvas with a radius given by the constant `VERTEX_RADIUS`

. The ID of the vertex is drawn as text in the center of the vertex.

##### Drawing Edges

The function `drawEdge(edge, edgeColor)`

draws a given `Edge`

instance in a given `edgeColor`

. The edge is drawn such that there is a line from the border of `vertex0`

to the border of `vertex1`

. This means that instead of drawing the edge line directly from the \((x,y)\)-positions of both vertices, the edge line needs to be offset from the center of the vertex by the vertex radius, otherwise the edge line would be visible inside of the vertex.
Thus, the line needs to
be drawn from \(\left(\begin{smallmatrix} v_1 + r_{1}\\ v_2 + r_{2} \end{smallmatrix}\right)\) to
\(\left(\begin{smallmatrix} w_1 - r_{1}\\ w_2 - r_{2} \end{smallmatrix}\right)\), with \(\vec{v}=(v_1, v_2)\) corresponding to `vertex0`

, \(\vec{w}= (w_1, w_2)\) corresponding to `vertex1`

and the vertex
radius \(r = \sqrt{r_{1}^2 + r_{2}^2}\) corresponding to `VERTEX_RADIUS`

.

As a first step, the angle \(\theta\) of the edge line is calculated with
\[\notag \theta = \text{atan2}(w_2 - v_2, w_1 - v_1).\]
Afterwards, \(r_1\) and \(r_2\) are calculated using \(\theta\) and \( r \):
\[\notag\begin{align*}
r_1 &= \text{cos}(\theta) \cdot r\\

r_2 &= \text{sin}(\theta) \cdot r.
\end{align*}
\]
Now, the edge line vector \(\vec{e}\) is given by
\[\notag \vec{e} = \begin{pmatrix}(w_1 - r_1) - (v_1 + r_1) \\ (w_2 - r_2) - (v_2 + r_2)\end{pmatrix}.\]
For drawing the edge using the Canvas API, it suffices to know \(\left(\begin{smallmatrix}v_1 + r_1\\v_2+r_2\end{smallmatrix}\right) \) and \(\left(\begin{smallmatrix}w_1 - r_1\\w_2-r_2\end{smallmatrix}\right) \). Figure 3 visualizes the components in play when drawing edges.

For directed edges, the arrow head also needs to be drawn.
The negative \(-\vec{e}\) of the edge line vector \(\vec{e}\) serves as a direction vector from \(\vec{w}\) to \(\vec{v}\).
From \(-\vec{e}\), a normalized vector \(\vec{i}\) is calculated as
\[\notag \vec{i} = \frac{ -\vec{e} }{\lvert \lvert -\vec{e} \rvert \rvert }.\]
Next, the arrow head position vectors \(\vec{a}\) and \(\vec{b}\) are calculated by rotating \(\vec{i}\) by the angle \(\alpha\) in both directions and extending the length by \(l\). The variables \(\alpha\) and \(l\) are defined by the constants `ARROW_HEAD_ANGLE`

and `ARROW_HEAD_LENGTH`

respectively:
\[\notag\begin{align*}
\vec{a} & = \begin{pmatrix} (w_1 - r_1) + (i_1 \cdot \text{cos}(\alpha) - i_2 \cdot \text{sin}(\alpha)) \cdot l \\
(w_2 - r_2) + (i_1 \cdot \text{sin}(\alpha) + i_2 \cdot \text{cos}(\alpha)) \cdot l
\end{pmatrix},\\

\vec{b} & = \begin{pmatrix} (w_1 - r_1) + (i_1 \cdot \text{cos}(\alpha) + i_2 \cdot \text{sin}(\alpha)) \cdot l \\
(w_2 - r_2) + (-i_1 \cdot \text{sin}(\alpha) + i_2 \cdot \text{cos}(\alpha)) \cdot l
\end{pmatrix}.
\end{align*}
\]
Figure 4 shows all components required to draw an arrow head.

#### Getting Input From the Canvas

The edge canvas catches all mouse press events and dispatches them to the function `handleCanvasClick(event, graph)`

. In a first iteration,
it checks whether any of the vertices has been clicked on using the function `checkCoordOnVertex(event, graph)`

, which takes an event object and the graph to check as its arguments. If a vertex has been clicked on, it checks whether another vertex has already been clicked on previously. If the second clicked on vertex is the same vertex or if there is already an edge between the first and the second vertex, the function simply returns, so that no self-loops or double edges get created. Otherwise, it creates an edge between the first and the second clicked on vertex and draws it to the edge canvas using `drawEdge()`

. Afterwards, the function returns.
If no vertex was clicked on, a second iteration over all vertices happens and checks whether the mouse press event occured in the vicinity of a vertex using the function `checkCoordsNearVertex(event, graph)`

, which also takes an event object and the graph to check as its arguments. Here, the vicinity is defined as the rectangle with the \((x,y)\)-coordinates of a vertex as its center and side lengths four times the radius of a vertex, as shown in figure 5. If the mouse press event occured near a vertex, the function simply returns. This is so that vertices are not grouped too close to each other.

Otherwise, if the function did not return at an earlier point, a new vertex is created at the location of the mouse press event, added to the graph and drawn on the vertex canvas with `drawVertex()`

.

### Graph Algorithms

I mainly used the book *Algorithm Design and Applications* by Goodrich and Tamassia [1] as a reference point for the algorithms.

Every time an algorithm is initiated, the function `beforeAlgorithm(graph)`

is called with the graph to run the algorithm on as its argument.
This function resets the graph’s state, draws it on the canvas and sets a flag signifying that an algorithm is running. After an algorithm finished running, the function `afterAlgorithm()`

is called, which unsets the previously mentioned flag.

Each step in an algorithm is accompanied by a colouring of a vertex or an edge and a delay before the next step.
The usable colors are saved in the enumeration `COLORS`

with possible values `green`

, `yellow`

, `blue`

, `white`

and `canvas`

.
The delay is implemented with the function `sleep()`

that sleeps for a certain amount of milliseconds. The number of milliseconds
is given by the application state variable `visualizationDelay`

. This state variable is mutated by the slider on the sidebar of the application.

```
/**
* Sleep function for visualizations.
*
* @returns promise
*/
const sleep = () => new Promise((resolve) => setTimeout(resolve, state.visualizationDelay))
```

#### Example Using Depth-first Search

This example with depth-first search aims to show the main principle behind visualizing single steps of all implemented algorithms.
The depth-first search algorithm over a connected component from the starting vertex `startingVertex`

is shown below:

```
/**
* Performs a depth first search over the connected component
* from a given starting vertex.
*
* @param {Vertex} startingVertex vertex to start the DFS from
*/
const depthFirstSearch = async (startingVertex) => {
startingVertex.state = VERTEX_STATES.explored
drawVertex(startingVertex, COLORS.blue)
await sleep()
for (const e of startingVertex.outgoingEdges) {
if (e.state === EDGE_STATES.unexplored) {
/** Opposite vertex from the starting vertex. */
let w
if (e.vertex0 == startingVertex) w = e.vertex1
else if (e.vertex1 == startingVertex) w = e.vertex0
if (w.state === VERTEX_STATES.unexplored) {
e.state = EDGE_STATES.discoveryEdge
drawEdge(e, COLORS.green)
await sleep()
await depthFirstSearch(w)
} else {
e.state = EDGE_STATES.backEdge
drawEdge(e, COLORS.yellow)
await sleep()
}
}
}
}
```

The algorithm starts out by setting the state of the starting vertex to `VERTEX_STATES.explored`

and coloring it blue. Next, it iterates through all outgoing edges of the current vertex.
If the current edge `e`

is unexplored, i.e. it has the state `EDGE_STATES.unexplored`

, it first determines the vertex `w`

opposite from the current vertex. Since it is possible that `w`

is either the
`vertex0`

or `vertex1`

property of the edge, it checks which one of them is the current vertex and takes the vertex opposite from that. The algorithm then checks whether the `w`

has not been explored yet, i.e.
whether it has the state `VERTEX_STATES.unexplored`

. If so, it colors `e`

green, sets its state to `EDGE_STATES.discoveryEdge`

and recursively calls `depthFirstSearch(w)`

, which then repeats the previous steps until all vertices and edges have been visited. If the current vertex `w`

however was already explored, `e`

simply gets drawn yellow and its state is set to `EDGE_STATES.backEdge`

.

### Generating Random Graphs

The generation of random graphs is mostly implemented in the static method `createRandomizedGraph()`

in the class `Graph`

, which returns a new
`Graph`

instance with randomized vertices and edges. The method starts out by calculating the number of vertices and edges that need to be created. The number of vertices is a random integer \(V\) with \(5\leq V \leq 15\).
The number of edges is a random integer \(E\) with \( \frac{V}{2} \leq E \leq {V \choose 4} \).
Next, it generates a random boolean \(D\) that determines whether the graph is directed or not. This boolean \(D\) will be set as the value of the property `isDirected`

of every edge that will be created later.
Afterwards, it generates \(V\) vertices with random \((x,y)\)-coordinates, such that the vertices do not collide with each other and that their \((x,y)\)-coordinates lie inside the bounds of the canvas plus some padding. The collision check and bounds check is handled by the function `checkCoordsNearVertex()`

. After the vertices get generated, the \(E\) edges need to get generated.
For this, two random vertices \(v_1\) and \(v_2\) are chosen from the graph’s vertex list, such that there is
no edge between them already. Afterwards, if two such vertices are found, the edge weight is generated as a random integer \(w\) with \(0 \leq W \leq 40\). Finally, the edge gets created with its properties set to \(v_1, v_2, D, W\) and added to the graph.

Some graphs I found to be interesting are shown below in figure 6 :-).

## Outlook

Overall I am pretty happy with the application. There are still certain features that I want to implement in the future, which include:

- More graph algorithms, even though I would have to check for special cases (e.g. negative weight cycles).
Some of the algorithms that I want to implement are:
- Floyd-Warshall algorithm
- Prim-Jarnik algorithm
- Kruskal’s algorithm
- Eulerian path
- Hamiltonian path

- Animated edge drawing with transitions
- Proper responsiveness
- Improved random generation of graphs so that the number of edges and vertices is dependent on the browser window’s dimensions