Graph routing for DuckDB - shortest paths, flow, spanning trees and more, following pgRouting's semantics and powered by the Boost Graph Library.
Maintainer(s):
am2222
Installing and Loading
INSTALL duckrouting FROM community;
LOAD duckrouting;
Example
INSTALL duckrouting FROM community;
LOAD duckrouting;
-- Any table with an id, two endpoints and a cost is a graph. No topology
-- tables to build, no geometry required.
CREATE TABLE edges (
id BIGINT, source BIGINT, target BIGINT, cost DOUBLE, reverse_cost DOUBLE
);
INSERT INTO edges VALUES
(1, 5, 6, 1, 1), (2, 6, 10, -1, 1), (3, 10, 15, -1, 1), (4, 6, 7, 1, 1);
-- Shortest path from vertex 5 to vertex 7
SELECT node, edge, agg_cost FROM duckrouting_dijkstra(
'SELECT id, source, target, cost, reverse_cost FROM edges', 5, 7);
-- node | edge | agg_cost
-- 5 | 1 | 0.0
-- 6 | 4 | 1.0
-- 7 | -1 | 2.0
-- Everything within a cost radius: the service area around a point
SELECT node, agg_cost FROM duckrouting_driving_distance(
'SELECT id, source, target, cost, reverse_cost FROM edges', 6, 2.0);
SELECT duckrouting_version('hello');
About duckrouting
duckrouting brings graph routing to DuckDB. It follows
pgRouting's function semantics - the same column
names, the same conventions, the same edge encoding - and runs on the
Boost Graph Library.
The edges query
Every function takes its graph as a string of SQL returning id, source,
target and cost, plus an optional reverse_cost. A negative cost means
the edge does not exist in that direction - that is how one-way streets are
written, and it is pgRouting's convention rather than an error condition.
What is here
| Family | Functions |
|---|---|
| Dijkstra | dijkstra, _cost, _cost_matrix, _via, _near, _near_cost, driving_distance |
| A* | astar, _cost, _cost_matrix (needs x1, y1, x2, y2) |
| Bidirectional | bd_dijkstra, bd_astar and their cost forms |
| K shortest paths | ksp (Yen), with_points_ksp |
| All pairs | floyd_warshall, johnson |
| Components | connected_components, strong_components, biconnected_components, articulation_points, bridges, make_connected |
| Spanning trees | kruskal, prim and their BFS/DFS/DD traversals |
| Traversal | breadth_first_search, depth_first_search, binary_breadth_first_search |
| Flow | max_flow, push_relabel, edmonds_karp, boykov_kolmogorov, max_flow_min_cost, edge_disjoint_paths, max_cardinality_match |
| With points | routing from a point partway along an edge, not just from a vertex |
| Contraction | contraction_hierarchies, dead_end_contraction, linear_contraction |
| Analysis | colouring, planarity, betweenness centrality, min cut, circuits, dominator tree |
| Other | tsp, tsp_euclidean, chinese_postman, line_graph, orderings, transitive_closure |
Verification
Results are checked against pgRouting's own published output - the queries and expected results from its documentation and test suite - rather than against hand-written expectations. Where the two legitimately differ, because a shortest path ties or a spanning tree is not unique, the difference is documented and the tests assert the properties that are determined.
Geometry helpers
duckrouting_find_close_edges, duckrouting_separate_crossing and
duckrouting_separate_touching are SQL macros over DuckDB's spatial
extension. Run INSTALL spatial; LOAD spatial; before calling one; spatial is
not needed for anything else.
Added Functions
| function_name | function_type | description | comment | examples |
|---|---|---|---|---|
| duckrouting_articulation_points | table | NULL | NULL | |
| duckrouting_astar | table | NULL | NULL | |
| duckrouting_astar_cost | table | NULL | NULL | |
| duckrouting_astar_cost_matrix | table | NULL | NULL | |
| duckrouting_bandwidth | table | NULL | NULL | |
| duckrouting_bd_astar | table | NULL | NULL | |
| duckrouting_bd_astar_cost | table | NULL | NULL | |
| duckrouting_bd_astar_cost_matrix | table | NULL | NULL | |
| duckrouting_bd_dijkstra | table | NULL | NULL | |
| duckrouting_bd_dijkstra_cost | table | NULL | NULL | |
| duckrouting_bd_dijkstra_cost_matrix | table | NULL | NULL | |
| duckrouting_bellman_ford | table | NULL | NULL | |
| duckrouting_betweenness_centrality | table | NULL | NULL | |
| duckrouting_biconnected_components | table | NULL | NULL | |
| duckrouting_binary_breadth_first_search | table | NULL | NULL | |
| duckrouting_bipartite | table | NULL | NULL | |
| duckrouting_boyer_myrvold | table | NULL | NULL | |
| duckrouting_boykov_kolmogorov | table | NULL | NULL | |
| duckrouting_breadth_first_search | table | NULL | NULL | |
| duckrouting_bridges | table | NULL | NULL | |
| duckrouting_chinese_postman | table | NULL | NULL | |
| duckrouting_chinese_postman_cost | table | NULL | NULL | |
| duckrouting_connected_components | table | NULL | NULL | |
| duckrouting_contraction | table | NULL | NULL | |
| duckrouting_contraction_hierarchies | table | NULL | NULL | |
| duckrouting_cuthill_mckee_ordering | table | NULL | NULL | |
| duckrouting_dag_shortest_path | table | NULL | NULL | |
| duckrouting_dead_end_contraction | table | NULL | NULL | |
| duckrouting_degree | table | NULL | NULL | |
| duckrouting_depth_first_search | table | NULL | NULL | |
| duckrouting_dijkstra | table | NULL | NULL | |
| duckrouting_dijkstra_cost | table | NULL | NULL | |
| duckrouting_dijkstra_cost_matrix | table | NULL | NULL | |
| duckrouting_dijkstra_near | table | NULL | NULL | |
| duckrouting_dijkstra_near_cost | table | NULL | NULL | |
| duckrouting_dijkstra_via | table | NULL | NULL | |
| duckrouting_dominator_tree | table | NULL | NULL | |
| duckrouting_driving_distance | table | NULL | NULL | |
| duckrouting_edge_coloring | table | NULL | NULL | |
| duckrouting_edge_disjoint_paths | table | NULL | NULL | |
| duckrouting_edmonds_karp | table | NULL | NULL | |
| duckrouting_edward_moore | table | NULL | NULL | |
| duckrouting_extract_vertices | table | NULL | NULL | |
| duckrouting_find_close_edges | table_macro | NULL | NULL | |
| duckrouting_floyd_warshall | table | NULL | NULL | |
| duckrouting_full_version | table | NULL | NULL | |
| duckrouting_hawick_circuits | table | NULL | NULL | |
| duckrouting_is_planar | table | NULL | NULL | |
| duckrouting_johnson | table | NULL | NULL | |
| duckrouting_king_ordering | table | NULL | NULL | |
| duckrouting_kruskal | table | NULL | NULL | |
| duckrouting_kruskal_bfs | table | NULL | NULL | |
| duckrouting_kruskal_dd | table | NULL | NULL | |
| duckrouting_kruskal_dfs | table | NULL | NULL | |
| duckrouting_ksp | table | NULL | NULL | |
| duckrouting_line_graph | table | NULL | NULL | |
| duckrouting_line_graph_full | table | NULL | NULL | |
| duckrouting_linear_contraction | table | NULL | NULL | |
| duckrouting_make_connected | table | NULL | NULL | |
| duckrouting_max_cardinality_match | table | NULL | NULL | |
| duckrouting_max_flow | table | NULL | NULL | |
| duckrouting_max_flow_min_cost | table | NULL | NULL | |
| duckrouting_max_flow_min_cost_cost | table | NULL | NULL | |
| duckrouting_prim | table | NULL | NULL | |
| duckrouting_prim_bfs | table | NULL | NULL | |
| duckrouting_prim_dd | table | NULL | NULL | |
| duckrouting_prim_dfs | table | NULL | NULL | |
| duckrouting_push_relabel | table | NULL | NULL | |
| duckrouting_separate_crossing | table_macro | NULL | NULL | |
| duckrouting_separate_touching | table_macro | NULL | NULL | |
| duckrouting_sequential_vertex_coloring | table | NULL | NULL | |
| duckrouting_sloan_ordering | table | NULL | NULL | |
| duckrouting_stoer_wagner | table | NULL | NULL | |
| duckrouting_strong_components | table | NULL | NULL | |
| duckrouting_topological_sort | table | NULL | NULL | |
| duckrouting_transitive_closure | table | NULL | NULL | |
| duckrouting_trsp | table | NULL | NULL | |
| duckrouting_trsp_via | table | NULL | NULL | |
| duckrouting_trsp_via_with_points | table | NULL | NULL | |
| duckrouting_trsp_with_points | table | NULL | NULL | |
| duckrouting_tsp | table | NULL | NULL | |
| duckrouting_tsp_euclidean | table | NULL | NULL | |
| duckrouting_version | scalar | NULL | NULL | |
| duckrouting_with_points | table | NULL | NULL | |
| duckrouting_with_points_cost | table | NULL | NULL | |
| duckrouting_with_points_cost_matrix | table | NULL | NULL | |
| duckrouting_with_points_dd | table | NULL | NULL | |
| duckrouting_with_points_ksp | table | NULL | NULL | |
| duckrouting_with_points_via | 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.