Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
MISQUERY ONLINE
WITH RECURSIVE
tblidx AS (
SELECT ROW_NUMBER() OVER() AS id, x, y
FROM tbl),
root AS (
SELECT ROW_NUMBER() OVER() AS id, map.aid AS aid, map.bid AS bid, map.len AS len
FROM (
SELECT a.id AS aid, b.id AS bid,
SQRT(POW(a.x-b.x,2)+POW(a.y-b.y,2)) AS len
FROM tblidx AS a
CROSS JOIN tblidx AS b
ORDER BY len
) AS map
),
kruskalinit(data, n) AS (
VALUES(ARRAY[1], 1)
UNION ALL
SELECT data || n + 1, n + 1
FROM kruskalinit
WHERE n < (
SELECT COUNT(1)
FROM tblidx
)
),
kruskal(ans, tablex, n) AS (
(SELECT 0 :: DOUBLE PRECISION, data, 1
FROM kruskalinit
ORDER BY n DESC
LIMIT 1)
UNION ALL
SELECT
CASE WHEN tablex[root.aid] != tablex[root.bid]
THEN
ans + root.len
ELSE
ans
END,
(SELECT ARRAY_AGG(
CASE WHEN i = tablex[root.bid]::INTEGER
THEN
tablex[root.aid]::INTEGER
ELSE
i
END)
FROM (SELECT UNNEST(tablex) AS i) AS x),
n+1
FROM kruskal, root
WHERE n <= (SELECT COUNT(1) FROM root) AND root.id = n
)
SELECT MAX(ans) AS c FROM kruskal;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.