Last active
March 29, 2020 05:59
-
-
Save elenatorro/6439854e352dfd8d32411fbcc90a4cb1 to your computer and use it in GitHub Desktop.
Welsh-Powell Algorithm for Graph Coloring with CARTO VL
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <title>Welsh-Powell Graph Coloring Algorithm | CARTO</title> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <meta charset="UTF-8"> | |
| <!-- CARTO VL https://carto.com/developers/carto-vl/ --> | |
| <script src="https://libs.cartocdn.com/carto-vl/v1.2.4/carto-vl.min.js"></script> | |
| <!-- Graphology https://graphology.github.io/ --> | |
| <script src="https://gitcdn.xyz/repo/graphology/graphology/cde3c849266b43007e9849b8f7c5ce78319eafe4/build/graphology.min.js"></script> | |
| <!-- Mapbox GL https://docs.mapbox.com/mapbox-gl-js/api/ --> | |
| <script src="https://api.tiles.mapbox.com/mapbox-gl-js/v0.52.0/mapbox-gl.js"></script> | |
| <link href="https://api.tiles.mapbox.com/mapbox-gl-js/v0.52.0/mapbox-gl.css" rel="stylesheet" /> | |
| <style> | |
| html, | |
| body { | |
| margin: 0; | |
| } | |
| #map { | |
| position: absolute; | |
| width: 100%; | |
| height: 100%; | |
| z-index: 1; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div id="map"></div> | |
| <div id="loader"> | |
| <div class="CDB-LoaderIcon CDB-LoaderIcon--big"> | |
| <svg class="CDB-LoaderIcon-spinner" viewBox="0 0 50 50"> | |
| <circle class="CDB-LoaderIcon-path" cx="25" cy="25" r="20" fill="none"></circle> | |
| </svg> | |
| </div> | |
| </div> | |
| <script> | |
| const map = new mapboxgl.Map({ | |
| container: 'map', | |
| style: carto.basemaps.voyager, | |
| center: [-6.38113, 39.483], | |
| zoom: 12.5, | |
| scrollZoom: true, | |
| hash: true | |
| }); | |
| const nav = new mapboxgl.NavigationControl({ | |
| showCompass: false | |
| }); | |
| map.addControl(nav, 'top-left'); | |
| carto.setDefaultAuth({ | |
| username: 'elena-carto', | |
| apiKey: 'default_public' | |
| }); | |
| // Query by Alberto Romeu https://twitter.com/alrocar | |
| // https://carto.com/blog/sql-graph-coloring/ | |
| const source = new carto.source.SQL(` | |
| SELECT DISTINCT a.rdfs_label AS name, | |
| a.cartodb_id, | |
| a.the_geom_webmercator, | |
| CONCAT(array_agg(b.rdfs_label) over (PARTITION BY a.cartodb_id), ',') AS adjacent, | |
| count(b.*) over (PARTITION BY a.cartodb_id) AS valence | |
| FROM barrio a, | |
| barrio b | |
| WHERE ST_INTERSECTS(a.the_geom, b.the_geom) | |
| AND a.cartodb_id != b.cartodb_id | |
| ORDER BY valence DESC, | |
| a.rdfs_label ASC | |
| `); | |
| const viz = new carto.Viz(` | |
| color: transparent | |
| strokeWidth: 0 | |
| @v_features: viewportFeatures($name, $adjacent) | |
| `); | |
| const layer = new carto.Layer('layer', source, viz); | |
| layer.addTo(map); | |
| layer.on('loaded', async () => { | |
| _hideLoader(); | |
| const features = viz.variables.v_features.value; | |
| const countries = getCountries(features); | |
| const graph = await buildGraph(countries); | |
| const names = countries.map(country => country.name); | |
| let coloredCountries = await getColors(graph, names, _getRandomColor()); | |
| while (coloredCountries.length) { | |
| coloredCountries = await getColors(graph, coloredCountries, _getRandomColor()); | |
| } | |
| features.forEach((feature, index) => { | |
| const color = graph.getNodeAttribute(feature.properties.name, 'color'); | |
| if (color) { | |
| feature.color.blendTo(color, 0); | |
| } | |
| }); | |
| }); | |
| async function getColors(graph, countries, color) { | |
| const leftNodes = []; | |
| countries.forEach((country) => { | |
| let colored = false; | |
| if (!graph.getNodeAttribute(country, 'color')) { | |
| graph.forEachNeighbor(country, (neighbor, attributes) => { | |
| if (attributes.color === color) { | |
| colored = true; | |
| } | |
| }); | |
| if (!colored) { | |
| graph.setNodeAttribute(country, 'color', color); | |
| } else { | |
| leftNodes.push(country); | |
| } | |
| } | |
| }); | |
| return leftNodes; | |
| } | |
| function getCountries(features) { | |
| return features.length | |
| ? features.map(getCountry).sort(soryByAdjacent) | |
| : []; | |
| }; | |
| function getCountry(feature) { | |
| const name = feature.properties.name; | |
| const adjacent = getAdjacentCountries(feature); | |
| const valence = adjacent.length; | |
| const color = null; | |
| return { name, adjacent, valence, color }; | |
| } | |
| function soryByAdjacent(prev, feat) { | |
| return prev.adj - feat.adj; | |
| } | |
| function getAdjacentCountries(feature) { | |
| return feature.properties.adjacent | |
| .replace(/\"|{|}/g, '') | |
| .split(',') | |
| .filter(adj => adj !== ""); | |
| } | |
| async function buildGraph(countries) { | |
| const graph = new graphology.Graph(); | |
| countries.forEach(country => { | |
| graph.addNode(country.name); | |
| graph.setNodeAttribute(country.name, 'color', 0); | |
| }); | |
| countries.forEach(country => { | |
| country.adjacent.forEach(adjacent => { | |
| if (graph.hasNode(adjacent)) { | |
| graph.addEdge(country.name, adjacent); | |
| } | |
| }); | |
| }); | |
| return graph; | |
| } | |
| function _getRandomColor() { | |
| const letters = '0123456789ABCDEF'; | |
| let color = '#'; | |
| for (let i = 0; i < 6; i++) { | |
| color += letters[Math.floor(Math.random() * 16)]; | |
| } | |
| return color; | |
| } | |
| function _hideLoader() { | |
| document.getElementById('loader').style.opacity = '0'; | |
| } | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment