Graph algorithms for DuckDB — PageRank, shortest path, SCC, MST, and more via petgraph
Maintainer(s):
alitrack
Installing and Loading
INSTALL petgraph_ext FROM community;
LOAD petgraph_ext;
Example
INSTALL petgraph_ext FROM community;
LOAD petgraph_ext;
SELECT * FROM petgraph_shortest_path('[(0,1,2.5),(1,2,1.0),(0,2,5.0)]', 0, 2);
-- → [0,1,2] 3.5
About petgraph_ext
duckdb_petgraph
A DuckDB extension that brings graph algorithms into SQL, powered by the petgraph Rust crate. Run PageRank, betweenness centrality, closeness centrality, eigenvector centrality, SCC, Louvain community detection, topological sort, cycle detection, shortest path, connected components, and MST — no external graph database required.
Features
- 17 table functions: build_graph, list_graphs, drop_graph, edges, neighbors, shortest_path, connected_components, pagerank, betweenness_centrality, closeness_centrality, eigenvector_centrality, scc, mst, louvain, toposort, is_cyclic
- Named graph cache: build once with
petgraph_build_graph('name', ...)and reference with@namefor zero-reparse repeated queries - Multi-batch streaming: all multi-row functions stream results across scan calls — no artificial 2048-row ceiling
- Edge format:
[(src,dst,weight),...]string syntax, usable inline or built from DuckDB tables viastring_agg
Algorithms
| Function | Description |
|---|---|
petgraph_shortest_path |
A* shortest path with path reconstruction |
petgraph_connected_components |
DFS component labeling (undirected) |
petgraph_pagerank |
PageRank with configurable alpha/iterations |
petgraph_betweenness_centrality |
Brandes' algorithm (undirected) |
petgraph_closeness_centrality |
BFS-based closeness (directed) |
petgraph_eigenvector_centrality |
Power-iteration eigenvector |
petgraph_scc |
Tarjan's strongly connected components |
petgraph_louvain |
Louvain community detection |
petgraph_toposort |
Kahn's topological sort |
petgraph_is_cyclic |
Directed cycle detection |
petgraph_mst |
Kruskal's minimum spanning tree |
Limitations
- Graphs must fit in memory (no disk-backed storage)
- Louvain is a simplified greedy pass with 20 iterations — useful for quick community detection but not a full implementation
- Edge weights are f64 only
- Node IDs are i32
Added Functions
| function_name | function_type | description | comment | examples |
|---|---|---|---|---|
| petgraph_betweenness_centrality | table | NULL | NULL | |
| petgraph_build_graph | table | NULL | NULL | |
| petgraph_build_graph_list | table | NULL | NULL | |
| petgraph_closeness_centrality | table | NULL | NULL | |
| petgraph_connected_components | table | NULL | NULL | |
| petgraph_drop_graph | table | NULL | NULL | |
| petgraph_edges | table | NULL | NULL | |
| petgraph_eigenvector_centrality | table | NULL | NULL | |
| petgraph_is_cyclic | table | NULL | NULL | |
| petgraph_list_graphs | table | NULL | NULL | |
| petgraph_louvain | table | NULL | NULL | |
| petgraph_mst | table | NULL | NULL | |
| petgraph_neighbors | table | NULL | NULL | |
| petgraph_pagerank | table | NULL | NULL | |
| petgraph_scc | table | NULL | NULL | |
| petgraph_shortest_path | table | NULL | NULL | |
| petgraph_toposort | table | NULL | NULL |
Overloaded Functions
This extension does not add any function overloads.
Added Types
This extension does not add any types.
Added Settings
This extension does not add any settings.