Skip to content

Instantly share code, notes, and snippets.

Avatar
💭
Coding

Kenny Bastani kbastani

💭
Coding
View GitHub Profile
View README.md

Prim’s algorithm generates a minimum spanning tree from a graph with weighted edges. Starting in the bottom-left corner, the algorithm keeps a heap of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in the direction with the lowest weight, as long as doing so does not reconnect with another part of the maze. Here the edges are initialized with random weights.

Unlike Wilson’s algorithm, this does not result in a uniform spanning tree. Sometimes, random traversal is misleadingly referred to as randomized Prim’s algorithm; however, the two algorithms exhibit radically different behavior! The global structure of the maze can be more easily seen by flooding it with color.

View README.md

The tree layout implements the Reingold-Tilford algorithm for efficient, tidy arrangement of layered nodes. The depth of nodes is computed by distance from the root, leading to a ragged appearance. Cartesian orientations are also supported. Implementation based on work by Jeff Heer and Jason Davies using Buchheim et al.'s linear-time variant of the Reingold-Tilford algorithm. Data shows the Flare class hierarchy, also courtesy Jeff Heer.

Compare to this Cartesian layout.

View README.md

Unlike choropleth maps, cartograms encode data using area rather than color, resulting in distorted geographic boundaries. In this example, states are rescaled around their centroid, preserving local shape but not topology. Inspired by Zachary Johnson. Non-continguous cartogram design invented by Judy Olsen. U.S. state and county boundaries from the U.S. Census Bureau, simplified using GDAL and MapShaper.