Graph Algorithms

A set of live-animated, fully tweakable graph algorithm visualizations.
Warning: This site is not robust and the algorithms are prone to crashing. It won't affect your computer in any other way than just causing a browser tab to crash. If it happens, just lower the branching factor and depth sliders to decrease the number of nodes. The sliders are tuned to not crash on my quad-core i7 laptop.
Current features:

Types of graphs

• Trees - n-ary complete trees
• Undirected Simple Graphs - randomly spaced nodes, with random-ish edges (see "Nice graph" below)
• Directed Graphs - Undirected Simple Graphs with directionality on edges
• Edge weighted - Undirected Simple Graphs with randomized edge weights and corresponding line thickness (not implemented currently, just viewable)

Algorithms

• Breadth First/Depth First Search
• Maxflow (Not yet implemented, Ford Fulkerson probably)
• Minimum Spanning Tree (Prim's)

Settings

• Branching Factor / Depth - For trees, these represent the number of children of each node and number of layers in the tree. For other graphs, they are simply multiplied together to get the number of nodes
• Density - For all graph types except trees, controls the approximate number of edges in the graph
• Node Size - Size of nodes in graph
• Speed - Speed of animation (higher on slider is fewer ms between frame)

Future Plans:

• Draw your own graphs by clicking to add points and edges
• Save and Load graphs with a JSON text string
• Save Animation as GIF

Learning Corner

Implementation:

This app is written in front-end only JavaScript. All animations are created live based on the state of the controller settings. This extremely thick client design was chosen for a few reasons:

• I can host static sites with front-end JS for free on github pages
• Easier to implement instead of trying to maintain both a UI and Server codebase
• Makes the app more responsive

The code can be viewed here. In short, the app relies on a central state object that is updated whenever the sliders/radio buttons are changed - much like the pattern used in Redux applications. The graph is represented as an object with an Adjacency Matrix to model the graph structure, and arrays of Node and Edge objects to represent the literal expression of the graph. Each animation is tied to a function which populates Frames, a property of the state, with many Graph objects, each colored (and eventually text-ed) differently to represent each step of the algorithm. When the animation is run, the Frames object is populated completely first, and then each Graph gets drawn with a certain amount of time in between each redraw.

Search:

The first algorithms animations implemented on this site are basic Breadth First Search and Depth First Search. These are the two most common algorithms for graph searching. The algorithms start from an initial position (the root of the tree, or a random node in the simple graph) and searches for the goal node, marked in red. When watching the algorithm run some interesting properties can be observed.

The algorithms behave differently depending on the situation they are searching. For example, if the node is in the first half of the bottom row of the tree, DFS will search significantly fewer nodes (marked in green after being visited) than BFS. Though if you animate the algorithm on the random undirected graph - which includes both cycles and much greater "depth" than the trees, BFS will generally take longer, though the eventual path to the goal node will often be much shorter than that of DFS.

The differences between the behavior (which can be formally expressed in part by analyzing their asymptotic time and space complexity, see the linked articles above) make deciding between the two algorithms a critical choice when they are used in application. Graph traversal is a key part of many algorithms for things like web searching, network analysis, artificial intelligence, etc.

Minimal Spanning Tree: ([beta] if it crashes, sorry!)

A Minimal (or minimum) Spanning Tree is the set of edges within a graph that represents the lowest possible cumulative weight to connect all vertices within the graph without cycles. Here, an edge's weight is the length of the edge, for visual simplicity. In other words, the minimal spanning tree I draw here uses the least amount of ink to connect all the dots while only drawing on the graph's edges. As somewhat of an intuition for proving the minimality of the generated tree, I have included in the text output the weight of the spanning tree and the total weight of the graph's edges. Notice that when running the algorithm repeatedly on the same graph, even when starting from different points, the minimal weight is the same. While not a proof of the minimality, it suggests that there are no cheaper ways to traverse the graph. This in turn shows that for any graph with unique edge weights, there is exactly 1 minimum spanning tree. This is most likely the case for any graph you generate on this site, as the likelihood of two nodes being the exact same distance apart is pretty low.

To find the Minimal Spanning Tree, I use Prim's Algorithm. Prim's is the simplest algorithm for finding minimal spanning trees, though with limitations. For example, if you run the animation with a low graph density, you may notice some nodes are not colored. This results from the graph not being connected. A solution would be to run the algorithm until a minimal spanning tree is created for a given connected component of the graph, selected a new node NOT within the MST, and repeat the process until all nodes are part of an MST, creating a Minimal Spanning Forest. A more elegant solution to the non-connected graph problem is using something like Kruskal's Algorithm.

The Euclidean Minimal Spanning Tree takes the idea of an MST and discards the constraint of following only the existing edges of the graph. Instead, it will draw its own connections, choosing the absolute minimum path connecting all nodes. This is equivalent to constructing an MST on a complete graph where the edge weight is the length - and that is the implementation I used.

The applications of finding the Minimal Spanning Tree on a graph are highly varied. Things like process optimization e.g. figuring out the best routes for delivery truck drivers, or the optimal circuit path when designing an electrical component. As with most graph theory problems, the applications go far beyond what you might expect including ecotoxicology, taxonomy, and financial analysis.

Nice Graphs:

A long standing problem with this site was producing random graphs that are structured such that the intuition for what each algorithm does is clear. I refer to this as the "Nice" Graph Problem. Because there is no definition for niceness, I have implemented an algorithm for generating graphs that at least look somewhat organized. I call the current implementation soft k-nearest neighbor. This implementation connects each node to k* nearby nodes. However, they are not necessarily the closest k nodes. Instead, the k * 1.5 nearest are found and then a random k subset of those nearby nodes are selected. This produces graphs that are generally clustered by proximity but includes some variation for visual interest.

*randomly +/- [0,k/2] so each node does not have the same degree