Click to View My

Code

Jump to the following code sections:

Parallel Betweenness Centrality

A graph, or network, is a collection of nodes and edges used to represent relationships in a system. Betweenness Centrality (BC) is a measure of a node's importance in a network. BC computes how many shortest paths in a network pass through a given node. This program implements the Brandes algorithm that uses a propogation "trick" for faster runtime. Custom data structures are implemented for dynamically sized arrays and priority queues. OpenMP is utilized for parallelism.

Download: Zip (224 KB) | Tar (890 KB)

Original picture (right) by Claudio Ricchini shared via Wikipedia under the Creative Commons Attribution-Share Alike 3.0 Unported license. No changes made.

Word Square Solver

A word square is a grid of letters where words can be read both horizontally and vertically, commonly 5 letters by 5 letters. Given a few seed words, this program generates all possible solutions for the common word square. The program utilizes preprocessing, auxiliary data structures, and the Compressed Sparse Column matrix format to achieve magnitudes of speed improvement over a basic approach.

Download: Zip (2.5 MB) | Tar (8.8 MB)

Think-Like-A-Vertex Framework

Think-Like-A-Vertex frameworks are systems that provide a vertex-centric programming model for processing large-scale graph problems. Programs are written from the "perspective of a vertex," which facilitates distribution and fault tolerance. A proof-of-concept prototype is presented to illustrate the model, with implementations of breadth-first search, connected components, and single-source shortest path algorithms.

Download: Zip (35.9 KB) | Tar (110 KB)