---
warning: DO NOT CHANGE THIS MANUALLY, THIS IS GENERATED BY https://github.com/duckdb/community-extensions repository, check README there
title: duckrouting
excerpt: |
DuckDB Community Extensions
Graph routing for DuckDB - shortest paths, flow, spanning trees and more, following pgRouting's semantics and powered by the Boost Graph Library.
extension:
name: duckrouting
description: Graph routing for DuckDB - shortest paths, flow, spanning trees and more, following pgRouting's semantics and powered by the Boost Graph Library.
version: 0.1.6
language: C++
build: cmake
license: MIT
maintainers:
- am2222
repo:
github: am2222/duckrouting
ref: 0bd1bb7cece6623346641e33de65694117ff36c1
docs:
hello_world: |
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');
extended_description: |
`duckrouting` brings graph routing to DuckDB. It follows
[pgRouting](https://pgrouting.org/)'s function semantics - the same column
names, the same conventions, the same edge encoding - and runs on the
[Boost Graph Library](https://www.boost.org/doc/libs/release/libs/graph/).
### 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.
extension_star_count: 5
extension_star_count_pretty: 5
extension_download_count: 17116
extension_download_count_pretty: 17.1k
image: '/images/community_extensions/social_preview/preview_community_extension_duckrouting.png'
layout: community_extension_doc
---
### Compatibility Matrix
This table covers all DuckDB releases that have not reached [end-of-life](https://duckdb.org/release_calendar), including LTS releases, and shows the 2 most recent patch releases of each. Older patch releases are not listed, but the extension may be available for them as well.
| Platform | 1.4.4 | 1.4.5 | 1.5.5 | 1.5.6 | 2.0.0 |
| :--- | :---: | :---: | :---: | :---: | :---: |
| Linux AMD64 | ❌ | ❌ | ✅ | ✅ | ✅ |
| Linux ARM64 | ❌ | ❌ | ✅ | ✅ | ✅ |
| macOS AMD64 | ❌ | ❌ | ✅ | ✅ | ✅ |
| macOS ARM64 | ❌ | ❌ | ✅ | ✅ | ✅ |
| Windows AMD64 | ❌ | ❌ | ✅ | ✅ | ✅ |
| Windows ARM64 | ❌ | ❌ | ❌ | ❌ | ❌ |
| WebAssembly | ❌ | ❌ | ✅ | ✅ | ✅ |
### Installing and Loading
```sql
INSTALL {{ page.extension.name }} FROM community;
LOAD {{ page.extension.name }};
```
{% if page.docs.hello_world %}
### Example
```sql
{{ page.docs.hello_world }}```
{% endif %}
{% if page.docs.extended_description %}
### About {{ page.extension.name }}
{{ page.docs.extended_description }}
{% endif %}
### Added Functions
| function_name | function_type | description | comment | examples |
|-----------------------------------------|---------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|---------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| duckrouting_articulation_points | table | The vertices whose removal would increase the number of connected components -- the single points of failure; returns one node column. | NULL | [SELECT * FROM duckrouting_articulation_points('SELECT id, source, target, cost, reverse_cost FROM edges'); -- nodes 3, 6, 7 and 8] |
| duckrouting_astar | table | Shortest path guided by a heuristic over the x1, y1, x2 and y2 columns the edges query must also expose, giving Dijkstra's answer for less exploration; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_astar('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', 6, 10, heuristic => 3, factor => 3.5);] |
| duckrouting_astar_cost | table | The total cost of each A* shortest path; returns start_vid, end_vid and agg_cost, one row per reachable pair. | NULL | [SELECT * FROM duckrouting_astar_cost('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', 6, [10, 12]);] |
| duckrouting_astar_cost_matrix | table | Routes one list of vertices against itself with A*, giving the cost of every ordered pair; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_astar_cost_matrix('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', [5, 6, 10], false);] |
| duckrouting_bandwidth | table | The largest gap between the indices of two adjacent vertices, which the ordering functions exist to reduce; returns one row of one BIGINT column, bandwidth. | NULL | [SELECT * FROM duckrouting_bandwidth('SELECT id, source, target, cost, reverse_cost FROM edges'); -- 5] |
| duckrouting_bd_astar | table | Bidirectional A*: both frontiers guided by a heuristic over the x1, y1, x2 and y2 columns the edges query must also expose; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_astar('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', 6, 10);] |
| duckrouting_bd_astar_cost | table | The total cost of each bidirectional A* path; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_astar_cost('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', 6, 10);] |
| duckrouting_bd_astar_cost_matrix | table | Routes one list of vertices against itself with bidirectional A*, giving every ordered pair; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_astar_cost_matrix('SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edges', [5, 6, 10], false);] |
| duckrouting_bd_dijkstra | table | Bidirectional Dijkstra: searches forward from the start and backward from the end until the two frontiers meet, giving Dijkstra's answer for less exploration; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_dijkstra('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10);] |
| duckrouting_bd_dijkstra_cost | table | The total cost of each bidirectional Dijkstra path; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_dijkstra_cost('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10);] |
| duckrouting_bd_dijkstra_cost_matrix | table | Routes one list of vertices against itself with bidirectional Dijkstra, giving every ordered pair; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_bd_dijkstra_cost_matrix('SELECT id, source, target, cost, reverse_cost FROM edges', [5, 6, 10], false);] |
| duckrouting_bellman_ford | table | Shortest path via boost::bellman_ford_shortest_paths, slower than Dijkstra but tolerant of negative edge weights; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_bellman_ford('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10, true);] |
| duckrouting_betweenness_centrality | table | How often each vertex lies on a shortest path between two others, normalised to 0-1, so that a high score marks a bottleneck; returns vid and centrality. | NULL | [SELECT * FROM duckrouting_betweenness_centrality('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_biconnected_components | table | Partitions the edges into biconnected components, maximal sets in which no single vertex removal disconnects anything; returns seq, component and edge. | NULL | [SELECT * FROM duckrouting_biconnected_components('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_binary_breadth_first_search | table | Shortest path by 0-1 BFS, a deque-based search for graphs whose edges all cost 0 or 1; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_binary_breadth_first_search('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10);] |
| duckrouting_bipartite | table | Splits the vertices into two sides such that every edge crosses between them, returning no rows when the graph is not bipartite; returns node and color, which is 0 or 1. | NULL | [SELECT * FROM duckrouting_bipartite('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_boyer_myrvold | table | The planar embedding: each vertex's incident edges in rotation order, so every edge appears twice, once from each endpoint; returns seq, source and target, and nothing at all for a non-planar graph. | NULL | [SELECT * FROM duckrouting_boyer_myrvold('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_boykov_kolmogorov | table | The maximum flow from source to sink broken down edge by edge, via boost::boykov_kolmogorov_max_flow; returns seq, edge, start_vid, end_vid, flow and residual_capacity for the edges that carry flow. | NULL | [SELECT * FROM duckrouting_boykov_kolmogorov('SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12);] |
| duckrouting_breadth_first_search | table | Visits every vertex reachable from root, nearest first, so depth never decreases as seq advances; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_breadth_first_search('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 2);] |
| duckrouting_bridges | table | The edges whose removal would disconnect the graph, being the biconnected components that hold a single edge; returns one edge column. | NULL | [SELECT * FROM duckrouting_bridges('SELECT id, source, target, cost, reverse_cost FROM edges'); -- edges 1, 6, 7, 14, 17 and 18] |
| duckrouting_chinese_postman | table | A closed walk traversing every edge at least once, repeating as few of them as possible; returns seq, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_chinese_postman('SELECT id, source, target, cost, reverse_cost FROM edges', false);] |
| duckrouting_chinese_postman_cost | table | The total cost of the closed walk traversing every edge at least once; returns one row of one DOUBLE column, cost. | NULL | [SELECT * FROM duckrouting_chinese_postman_cost('SELECT id, source, target, cost, reverse_cost FROM edges', false);] |
| duckrouting_connected_components | table | Splits the undirected graph into connected components, each labelled by the smallest node id it contains; returns seq, component and node. | NULL | [SELECT * FROM duckrouting_connected_components('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_contraction | table | Simplifies the graph by absorbing dead ends and then collapsing linear chains, repeating the pair for cycles rounds; returns type ('v' or 'e'), id, contracted_vertices, source, target and cost. | NULL | [SELECT * FROM duckrouting_contraction('SELECT id, source, target, cost, reverse_cost FROM edges', false, cycles => 2);] |
| duckrouting_contraction_hierarchies | table | Preprocesses the graph for fast routing, contracting vertices one at a time and adding a shortcut edge wherever that would otherwise lengthen a shortest path; returns type ('v' for a vertex, 'e' for a shortcut), id, contracted_vertices, source, target, cost, metric and vertex_order. | NULL | [SELECT * FROM duckrouting_contraction_hierarchies('SELECT id, source, target, cost FROM edges', false);] |
| duckrouting_cuthill_mckee_ordering | table | A bandwidth-reducing permutation of the vertices via boost::cuthill_mckee_ordering; returns seq and node. | NULL | [SELECT * FROM duckrouting_cuthill_mckee_ordering('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_dag_shortest_path | table | Shortest path over a directed acyclic graph via boost::dag_shortest_paths, linear in the size of the graph and an error if the graph cycles; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_dag_shortest_path('SELECT id, source, target, cost FROM edges', 5, 11);] |
| duckrouting_dead_end_contraction | table | Simplifies the graph by absorbing dead-end vertices into the neighbour that holds them; returns type ('v' or 'e'), id, contracted_vertices, source, target and cost. | NULL | [SELECT * FROM duckrouting_dead_end_contraction('SELECT id, source, target, cost, reverse_cost FROM edges', false);] |
| duckrouting_degree | table | Counts the edges incident on each vertex; returns node and degree. | NULL | [SELECT * FROM duckrouting_degree('SELECT id, source, target FROM edges');] |
| duckrouting_depth_first_search | table | Visits every vertex reachable from root, following each branch to its end before backtracking; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_depth_first_search('SELECT id, source, target, cost, reverse_cost FROM edges', 6);] |
| duckrouting_dijkstra | table | Shortest path for every combination of start and end vertex, one row per node along each path; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_dijkstra('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10); -- six rows, 6 to 10 for agg_cost 5.0] |
| duckrouting_dijkstra_cost | table | The total cost of each shortest path without the per-node detail; returns start_vid, end_vid and agg_cost, one row per reachable pair. | NULL | [SELECT * FROM duckrouting_dijkstra_cost('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10); -- 6, 10, 5.0] |
| duckrouting_dijkstra_cost_matrix | table | Routes one list of vertices against itself, giving the cost of every ordered pair; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_dijkstra_cost_matrix('SELECT id, source, target, cost, reverse_cost FROM edges', [5, 6, 10], false); -- six rows, one per ordered pair] |
| duckrouting_dijkstra_near | table | Of all the combinations of start and end vertex, the cap cheapest as full paths -- which of these is closest, and how do I get there; same columns as duckrouting_dijkstra, and cap defaults to 1. | NULL | [SELECT * FROM duckrouting_dijkstra_near('SELECT id, source, target, cost, reverse_cost FROM edges', 6, [10, 11, 1]); -- vertex 11, the nearest of the three] |
| duckrouting_dijkstra_near_cost | table | The same selection as duckrouting_dijkstra_near without the per-node detail; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_dijkstra_near_cost('SELECT id, source, target, cost, reverse_cost FROM edges', [10, 11, 1], 6, cap => 2); -- the two cheapest pairs] |
| duckrouting_dijkstra_via | table | Routes through a sequence of vertices in order, one leg per consecutive pair; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost and route_agg_cost, with edge -2 marking the end of the route. | NULL | [SELECT * FROM duckrouting_dijkstra_via('SELECT id, source, target, cost, reverse_cost FROM edges', [5, 1, 8]); -- two legs, route_agg_cost 7.0 at the end] |
| duckrouting_dominator_tree | table | For each vertex the immediate dominator relative to root, the last vertex every path from the root must pass through before reaching it; returns vertex_id and idom, which is 0 for the root and for anything unreachable. | NULL | [SELECT * FROM duckrouting_dominator_tree('SELECT id, source, target, cost, reverse_cost FROM edges', 5);] |
| duckrouting_driving_distance | table | Every vertex reachable from start_vid within a total cost of distance -- the service area around a point -- as a shortest-path tree; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_driving_distance('SELECT id, source, target, cost, reverse_cost FROM edges', 11, 2.0); -- nine rows out to cost 2.0] |
| duckrouting_edge_coloring | table | Assigns each edge a colour so that edges meeting at a vertex differ; returns edge and color, counted from 1. | NULL | [SELECT * FROM duckrouting_edge_coloring('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_edge_disjoint_paths | table | As many routes between the endpoints as exist that share no edge, found by giving every usable direction capacity 1 and decomposing the flow back into paths; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_edge_disjoint_paths('SELECT id, source, target, cost, reverse_cost FROM edges', 11, 12); -- two independent routes] |
| duckrouting_edmonds_karp | table | The maximum flow from source to sink broken down edge by edge, via boost::edmonds_karp_max_flow; returns seq, edge, start_vid, end_vid, flow and residual_capacity for the edges that carry flow. | NULL | [SELECT * FROM duckrouting_edmonds_karp('SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12);] |
| duckrouting_edward_moore | table | Shortest path by Edward Moore's algorithm, better known as SPFA: a queue-based refinement of Bellman-Ford; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_edward_moore('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 10, true);] |
| duckrouting_extract_vertices | table | Derives the vertex table implied by an edges query, every vertex appearing exactly once; returns id, in_edges and out_edges. | NULL | [SELECT * FROM duckrouting_extract_vertices('SELECT id, source, target FROM edges');] |
| duckrouting_find_close_edges | table_macro | For each point, the cap nearest edges within tolerance, reported in the shape the withPoints family expects; edges_sql and points_sql name tables of id and geom, and of pid and geom, rather than holding queries. Returns seq, pid, edge_id, fraction, distance, geom and edge. Needs the spatial extension loaded. | NULL | [SELECT * FROM duckrouting_find_close_edges('edges', 'points', 0.5);] |
| duckrouting_floyd_warshall | table | All-pairs shortest path costs via boost::floyd_warshall_all_pairs_shortest_paths, omitting self pairs and unreachable pairs; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_floyd_warshall('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_full_version | table | The versions duckrouting was built from; returns one row of version, boost, compiler and build_type. | NULL | [SELECT * FROM duckrouting_full_version();] |
| duckrouting_hawick_circuits | table | Every circuit -- closed path -- in the directed graph, of which there can be very many; returns seq, path_id, path_seq counting from 0, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_hawick_circuits('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_is_planar | table | Whether the graph can be drawn with no crossing edges; returns one row of one BOOLEAN column, is_planar. | NULL | [SELECT * FROM duckrouting_is_planar('SELECT id, source, target, cost, reverse_cost FROM edges'); -- true] |
| duckrouting_johnson | table | All-pairs shortest path costs via boost::johnson_all_pairs_shortest_paths, which reweights the graph and then runs Dijkstra from every vertex; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_johnson('SELECT source, target, cost FROM edges');] |
| duckrouting_king_ordering | table | A bandwidth-reducing permutation of the vertices via boost::king_ordering; returns seq and node. | NULL | [SELECT * FROM duckrouting_king_ordering('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_kruskal | table | The minimum spanning forest of the undirected graph via boost::kruskal_minimum_spanning_tree, one row per chosen edge; returns edge and cost. | NULL | [SELECT * FROM duckrouting_kruskal('SELECT id, source, target, cost, reverse_cost FROM edges'); -- 14 edges, for 17 vertices in 3 components] |
| duckrouting_kruskal_bfs | table | Walks the Kruskal spanning forest breadth first from each root, stopping at max_depth; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_kruskal_bfs('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 2);] |
| duckrouting_kruskal_dd | table | Walks the Kruskal spanning forest depth first from each root, stopping at an accumulated cost of distance; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_kruskal_dd('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 3.5);] |
| duckrouting_kruskal_dfs | table | Walks the Kruskal spanning forest depth first from each root, stopping at max_depth, so depth rises and falls as the walk backtracks; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_kruskal_dfs('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 2);] |
| duckrouting_ksp | table | Up to k shortest loopless paths for every combination of start and end vertex, cheapest first, by Yen's algorithm; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_ksp('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 17, 2); -- two routes, both costing 4.0] |
| duckrouting_line_graph | table | The line graph: each edge of the input becomes a vertex, and two such vertices are joined when the edges they stand for share an endpoint; returns seq, source, target, cost and reverse_cost. | NULL | [SELECT * FROM duckrouting_line_graph('SELECT id, source, target, cost, reverse_cost FROM edges', false);] |
| duckrouting_line_graph_full | table | The full line graph, which additionally splits each vertex into one node per incident half-edge so that turn costs can be attached; returns seq, source, target, cost and edge. | NULL | [SELECT * FROM duckrouting_line_graph_full('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_linear_contraction | table | Simplifies the graph by collapsing chains of degree-two vertices into a single edge; returns type ('v' or 'e'), id, contracted_vertices, source, target and cost. | NULL | [SELECT * FROM duckrouting_linear_contraction('SELECT id, source, target, cost, reverse_cost FROM edges', false);] |
| duckrouting_make_connected | table | The vertex pairs that would have to be joined to make the graph connected, one fewer than the number of components; returns seq, start_vid and end_vid. | NULL | [SELECT * FROM duckrouting_make_connected('SELECT id, source, target, cost, reverse_cost FROM edges'); -- two pairs, for three components] |
| duckrouting_map_match | table | Snaps GPS trajectories onto the graph with a hidden Markov model (Fast Map Matching, Yang & Gidofalvi 2018). candidates_sql lists the nearby edges of every fix as pid, edge_id, fraction, distance, x, y and an optional traj_id -- what duckrouting_find_close_edges returns, joined back to the fix -- and gps_error is the GPS noise in the units of distance. Returns one row per fix: seq, traj_id, pid, edge, fraction, distance, ep, tp and sp_dist. A trajectory whose fixes cannot be joined produces no rows. | NULL | [SELECT * FROM duckrouting_map_match('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT traj_id, pid, edge_id, fraction, distance, x, y FROM candidates', 0.5);] |
| duckrouting_map_match_path | table | The complete route through the network for each map-matched trajectory, with path_id the trajectory and the first and last fixes as vertices -pid; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. With details => true every fix appears as a vertex. | NULL | [SELECT * FROM duckrouting_map_match_path('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT traj_id, pid, edge_id, fraction, distance, x, y FROM candidates', 0.5);] |
| duckrouting_max_cardinality_match | table | The largest set of edges no two of which share a vertex; returns one edge column. | NULL | [SELECT * FROM duckrouting_max_cardinality_match('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_max_flow | table | The maximum total flow from source to sink, reading capacity and reverse_capacity rather than costs; returns one row of one DOUBLE column, flow. | NULL | [SELECT * FROM duckrouting_max_flow('SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12); -- 230.0] |
| duckrouting_max_flow_min_cost | table | Of all the ways to achieve the maximum flow the cheapest one, from an edges query carrying costs as well as capacities; returns seq, edge, source, target, flow, residual_capacity, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_max_flow_min_cost('SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost FROM edges', 11, 12);] |
| duckrouting_max_flow_min_cost_cost | table | The total cost of the cheapest maximum flow; returns one row of one DOUBLE column, cost. | NULL | [SELECT * FROM duckrouting_max_flow_min_cost_cost('SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost FROM edges', 11, 12); -- 430.0] |
| duckrouting_prim | table | The same minimum spanning forest via boost::prim_minimum_spanning_tree, grown outwards from a root in each component; returns edge and cost. | NULL | [SELECT * FROM duckrouting_prim('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_prim_bfs | table | Walks the Prim spanning forest breadth first from each root, stopping at max_depth; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_prim_bfs('SELECT id, source, target, cost, reverse_cost FROM edges', [6, 13]); -- one walk per root, under its own start_vid] |
| duckrouting_prim_dd | table | Walks the Prim spanning forest depth first from each root, stopping at an accumulated cost of distance; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_prim_dd('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 3.5);] |
| duckrouting_prim_dfs | table | Walks the Prim spanning forest depth first from each root, stopping at max_depth; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_prim_dfs('SELECT id, source, target, cost, reverse_cost FROM edges', 6, 2);] |
| duckrouting_push_relabel | table | The maximum flow from source to sink broken down edge by edge, via boost::push_relabel_max_flow; returns seq, edge, start_vid, end_vid, flow and residual_capacity for the edges that carry flow. | NULL | [SELECT * FROM duckrouting_push_relabel('SELECT id, source, target, capacity, reverse_capacity FROM edges', 11, 12);] |
| duckrouting_separate_crossing | table_macro | Splits every edge at the points where it crosses another edge; edges_sql names a table of id and geom rather than holding a query. Returns seq, id, sub_id and geom. Needs the spatial extension loaded. | NULL | [SELECT * FROM duckrouting_separate_crossing('edges');] |
| duckrouting_separate_touching | table_macro | Splits every edge where another edge's endpoint touches its interior -- a junction that was never noded; edges_sql names a table of id and geom rather than holding a query. Returns seq, id, sub_id and geom. Needs the spatial extension loaded. | NULL | [SELECT * FROM duckrouting_separate_touching('edges');] |
| duckrouting_sequential_vertex_coloring | table | Assigns each vertex a colour so that no edge joins two vertices of the same colour; returns node and color, counted from 1. | NULL | [SELECT * FROM duckrouting_sequential_vertex_coloring('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_sloan_ordering | table | A bandwidth-reducing permutation via boost::sloan_ordering, which starts from a pseudo-peripheral pair and so covers one connected component; returns seq and node. | NULL | [SELECT * FROM duckrouting_sloan_ordering('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_stoer_wagner | table | The cheapest set of edges whose removal disconnects the undirected graph, one row per edge crossing the cut; returns seq, edge, cost and mincut, where mincut is the total and repeats on every row. | NULL | [SELECT * FROM duckrouting_stoer_wagner('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_strong_components | table | Strongly connected components of the directed graph -- sets of vertices that can all reach one another following edge direction; returns seq, component and node. | NULL | [SELECT * FROM duckrouting_strong_components('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_topological_sort | table | Orders a directed acyclic graph so that every edge runs forwards, raising an error on a cyclic graph; returns seq and node. | NULL | [SELECT * FROM duckrouting_topological_sort('SELECT id, source, target, cost FROM edges');] |
| duckrouting_transitive_closure | table | Every vertex reachable from every vertex; returns node and targets, an ascending BIGINT[] of everything reachable from it. | NULL | [SELECT * FROM duckrouting_transitive_closure('SELECT id, source, target, cost, reverse_cost FROM edges');] |
| duckrouting_trsp | table | Shortest path that respects turn restrictions, read from a query exposing path (a BIGINT[] of edge ids) and cost; following that exact sequence costs extra rather than being forbidden, so a large cost is an effective ban. Returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_trsp('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT path, cost FROM restrictions', 6, 10, false);] |
| duckrouting_trsp_via | table | Turn-restricted routing through a sequence of vertices in order, one leg per consecutive pair; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost and route_agg_cost. | NULL | [SELECT * FROM duckrouting_trsp_via('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT path, cost FROM restrictions', [5, 1, 8], false);] |
| duckrouting_trsp_via_with_points | table | Turn-restricted routing through a sequence of vertices and points in order; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost and route_agg_cost. | NULL | [SELECT * FROM duckrouting_trsp_via_with_points('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT path, cost FROM restrictions', 'SELECT pid, edge_id, fraction, side FROM poi', [-1, 6, -3], false);] |
| duckrouting_trsp_with_points | table | Turn-restricted routing between vertices or points sitting partway along an edge; returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_trsp_with_points('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT path, cost FROM restrictions', 'SELECT pid, edge_id, fraction, side FROM poi', -1, -3, false);] |
| duckrouting_tsp | table | An approximate shortest tour visiting every vertex once and returning to the start, from a cost matrix exposing start_vid, end_vid and agg_cost; returns seq, node, cost and agg_cost, where cost is the cost of arriving rather than of leaving. | NULL | [SELECT * FROM duckrouting_tsp('SELECT start_vid, end_vid, agg_cost FROM matrix');] |
| duckrouting_tsp_euclidean | table | The same approximate tour with distances computed from a points query exposing id, x and y rather than from a graph; returns seq, node, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_tsp_euclidean('SELECT * FROM (VALUES (1,0.0,0.0),(2,1.0,0.0),(3,1.0,1.0),(4,0.0,1.0)) t(id,x,y)'); -- the perimeter of the unit square, agg_cost 4.0] |
| duckrouting_version | scalar | Greets `name` and reports the Boost version duckrouting was built against. | NULL | [duckrouting_version('Sam')] |
| duckrouting_with_points | table | Shortest path that may start at, end at or pass through a point sitting partway along an edge, read from a points query exposing pid, edge_id, fraction and an optional side; each point becomes a vertex numbered -pid. Returns seq, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_with_points('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', -1, -3, 'b', details => true);] |
| duckrouting_with_points_cost | table | The total cost of each withPoints shortest path; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_with_points_cost('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', -1, -3, 'b');] |
| duckrouting_with_points_cost_matrix | table | Routes one list of vertices and points against itself, giving the cost of every ordered pair; returns start_vid, end_vid and agg_cost. | NULL | [SELECT * FROM duckrouting_with_points_cost_matrix('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', [-1, -3, 6], 'b');] |
| duckrouting_with_points_dd | table | Driving distance from a vertex or from a point sitting partway along an edge -- a house halfway down a street -- within a total cost of distance; returns seq, depth, start_vid, pred, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_with_points_dd('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', -1, 3.3, 'r', details => true);] |
| duckrouting_with_points_ksp | table | Up to k shortest loopless paths between vertices or points sitting partway along an edge, cheapest first; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost and agg_cost. | NULL | [SELECT * FROM duckrouting_with_points_ksp('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', -1, -3, 2, 'b');] |
| duckrouting_with_points_via | table | Routes through a sequence of vertices and points in order, one leg per consecutive pair; returns seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost and route_agg_cost. | NULL | [SELECT * FROM duckrouting_with_points_via('SELECT id, source, target, cost, reverse_cost FROM edges', 'SELECT pid, edge_id, fraction, side FROM poi', [-1, 6, -3], 'b');] |
### Overloaded Functions
This extension does not add any function overloads.
### Added Types
This extension does not add any types.
### Added Settings
| name | description | input_type | scope | aliases | typed_value |
|----------------|---------------------------------------------------------|------------|--------|---------|-------------|
| temp_directory | Set the directory to which temporary files are written. | VARCHAR | GLOBAL | [] | post.db.tmp |