Graph Algorithms

Gunrock Algorithms

The following is are a wide variety of graph primitives, including traversal-based (Breadth-First Search, Single-Source Shortest Path); node-ranking (Hyperlink-Induced Topic Search, PageRank); and global (Connected Component, Minimum Spanning Tree) implemented within Gunrock.

The "File" column in the table below shows, which within these applications' implementations are (e.g. sssp.hxx). The version number in the "Gunrock" and "Essentials" columns show which API abstraction of gunrock supports the respective application. If you are interested in helping us port an application in the older abstraction ("Gunrock") to a newer, much cleaner abstraction ("Essentials"), please see our How to write a new graph algorithm guide).

Application	Directory	Gunrock	Essentials
A* Search	astar	v0.5.x	❌
Betweenness Centrality	bc	v1.x.x	v0.0.1
Breadth-First Search	bfs	v1.x.x	v0.0.1
Connected Components	cc	v1.x.x	❌🌟
Graph Coloring	color	v1.x.x	v0.0.1
Geolocation	geo	v1.x.x	v0.0.1
RMAT Graph Generator	grmat	v0.5.x	❌
Graph Trend Filtering	gtf	v1.x.x	❌
Hyperlink-Induced Topic Search	hits	v1.x.x	v0.0.1
K-Core Decomposition	kcore	v1.x.x	v0.0.1
K-Nearest Neighbors	knn	v1.x.x	❌
Louvain Modularity	louvain	v1.x.x	❌🌟
Label Propagation	lp	v0.5.x	❌
MaxFlow	mf	v1.x.x	❌
Minimum Spanning Tree	mst	v0.5.x	v0.0.1
PageRank	pr	v1.x.x	v0.0.1
Local Graph Clustering	pr_nibble	v1.x.x	v0.0.1
Graph Projections	proj	v1.x.x	❌
Random Walk	rw	v1.x.x	❌🌟
GraphSAGE	sage	v1.x.x	❌
Stochastic Approach for Link-Structure Analysis	salsa	v0.5.x	❌
Subgraph Matching	sm	v1.x.x	❌🌟
Shared Nearest Neighbors	snn	v1.x.x	❌
Scan Statistics	ss	v1.x.x	❌
Sparse-Matrix Vector Multiplication	spmv	❌	v0.0.1
Single Source Shortest Path	sssp	v1.x.x	v0.0.1
Triangle Counting	tc	v1.x.x	v0.0.1
Top K	topk	v0.5.x	❌
Vertex Nomination	vn	v1.x.x	❌
Who To Follow	wtf	v0.5.x	❌

(🌟 are priority ports, and we're interested in porting them as soon as possible)