Create a gist now

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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment