Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CREATE OR REPLACE FUNCTION adjacency_list(table_name regclass, user_name text) RETURNS void AS $$
BEGIN
EXECUTE format('DROP TABLE IF EXISTS %s_adjacency_list;
CREATE TABLE %s_adjacency_list AS
SELECT DISTINCT a.cartodb_id,
array_agg(b.cartodb_id) over (PARTITION BY a.cartodb_id) AS adjacent,
count(b.*) over (PARTITION BY a.cartodb_id) AS valence,
0 AS color
FROM %s a,
%s b
WHERE st_intersects(a.the_geom, b.the_geom)
ORDER BY valence DESC,
a.cartodb_id ASC;
SELECT CDB_CartoDBFyTable(''' || user_name || ''',''' || table_name || '_adjacency_list'');', table_name, table_name, table_name, table_name);
END
$$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION greedy_coloring(table_name regclass, user_name text) RETURNS void AS $$
DECLARE
item RECORD;
current_color int = 1;
cc int;
guard int;
BEGIN
PERFORM adjacency_list(table_name, user_name);
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = 0', table_name) INTO guard;
WHILE guard > 0 LOOP
EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = (SELECT cartodb_id FROM %s_adjacency_list WHERE color = 0 ORDER BY cartodb_id ASC LIMIT 1);', table_name, table_name) USING current_color;
FOR item IN EXECUTE format('SELECT * FROM %s_adjacency_list WHERE color = 0', table_name) LOOP
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = $1 AND $2 = ANY(adjacent)', table_name) INTO cc USING current_color, item.cartodb_id;
IF cc = 0 THEN
EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = $2;', table_name) USING current_color, item.cartodb_id;
END IF;
END loop;
current_color = current_color + 1;
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color = 0', table_name) into guard;
END loop;
END;
$$ LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION kempe(table_name regclass, user_name text) RETURNS void AS $$
DECLARE
item RECORD;
cc int;
count int = 1;
d int;
temp_cartodb_id int;
guard int;
BEGIN
PERFORM adjacency_list(table_name, user_name);
EXECUTE format('DROP TABLE IF EXISTS %s_temp', table_name);
EXECUTE format('CREATE TABLE %s_temp (cartodb_id integer, ord integer);', table_name);
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE valence < 5 AND valence > 0', table_name) INTO guard;
WHILE guard > 0 LOOP
EXECUTE format('SELECT cartodb_id FROM %s_adjacency_list WHERE valence < 5 AND valence > 0 ORDER BY valence DESC LIMIT 1', table_name) into temp_cartodb_id;
EXECUTE format('INSERT INTO %s_temp (cartodb_id, ord) VALUES ($1, $2)', table_name) USING temp_cartodb_id, count;
count = count + 1;
EXECUTE format('UPDATE %s_adjacency_list SET valence = 0 WHERE cartodb_id = $1', table_name) USING temp_cartodb_id;
FOR item IN EXECUTE format('SELECT * FROM %s_adjacency_list WHERE $1 = ANY(adjacent)', table_name) USING temp_cartodb_id LOOP
EXECUTE format('UPDATE %s_adjacency_list SET valence = valence - 1 WHERE cartodb_id = $1', table_name) USING item.cartodb_id;
END LOOP;
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE valence < 5 AND valence > 0', table_name) INTO guard;
END LOOP;
EXECUTE format('UPDATE %s_adjacency_list set valence = array_length(adjacent, 1)', table_name);
EXECUTE format('UPDATE %s_adjacency_list set color = 0', table_name);
FOR item IN EXECUTE format('SELECT * FROM %s_temp ORDER BY ord DESC', table_name) LOOP
EXECUTE format('SELECT COUNT(*) FROM %s_adjacency_list WHERE color != 0 AND $1 = ANY(adjacent)', table_name) INTO cc USING item.cartodb_id;
IF cc = 0 THEN
EXECUTE format('UPDATE %s_adjacency_list SET color = 1 WHERE cartodb_id = $1', table_name) USING item.cartodb_id;
ELSE
EXECUTE format('select (array_agg(elements))[1]
from (
select unnest(array[1, 2, 3, 4, 5])
except
SELECT unnest(ARRAY_AGG(color)) FROM %s_adjacency_list WHERE color != 0 AND $1 = ANY(adjacent)
) t (elements)', table_name) INTO d USING item.cartodb_id;
EXECUTE format('UPDATE %s_adjacency_list SET color = $1 WHERE cartodb_id = $2', table_name) USING d, item.cartodb_id;
END IF;
END LOOP;
EXECUTE format('DROP TABLE IF EXISTS %s_temp', table_name);
END;
$$ LANGUAGE plpgsql;
@seanlindsey

This comment has been minimized.

Copy link

commented Feb 8, 2019

If you're looking to make these function work on tables with 100k+ shapes in a reasonable time I suggest add some indexes. Go through and add the standard index for cartdodb_id and valence for kemp/for greedy I added a (color, cartdodb_id). For kemp you will also want an index on adjacent I had to change the clauses "$1 = ANY(adjacent)" to "ARRAY[$1] <@ adjacent" for it to use the index. For greedy, which is much faster in my case, I made a special index on color and adjacent which may not be necessary. I simply declared a max_id int, and set it to max(cartodb_id) + 1 and then made a column adjacent_color set to adjacent || (color + max_id) then replaced "color = $1 AND $2 = ANY(adjacent)" with "array[$1, $2] <@ adjacent_color" where $1 is now current_color + max_id. Then made sure to update adjacent_color when you update color in the next statement. With the indexes these queries were several hundred times faster in my case.

Happy mapping!

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.