Last active
December 17, 2020 08:00
-
-
Save printminion/a337eeb63ba232084dfc to your computer and use it in GitHub Desktop.
Javascript Welsh Powell static graph coloring algorithm.
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
| /** | |
| * @desc Welsh Powell static graph coloring algorithm.. | |
| * | |
| * @author Misha M.-Kupriyanov https://google.com/+MishaMKupriyanov | |
| * @link https://gist.github.com/printminion/a337eeb63ba232084dfc | |
| */ | |
| //Source: https://github.com/graphstream/gs-algo/blob/master/src/org/graphstream/algorithm/coloring/WelshPowell.java | |
| function WelshPowell() { | |
| this.chromaticNumber = 0; | |
| this.graph = null; | |
| } | |
| WelshPowell.prototype.init = function (graph) { | |
| this.graph = graph; | |
| }; | |
| WelshPowell.prototype.compute = function () { | |
| }; | |
| WelshPowell.prototype.getChromaticNumber = function () { | |
| return this.chromaticNumber; | |
| }; | |
| WelshPowell.prototype.compute = function () { | |
| // ------- STEP 1 ----------- | |
| // the algorithm requires the use of a sorted list using | |
| // degree values for sorting them. | |
| var heap = []; | |
| var sortedNodes = []; | |
| for (var j in this.graph) { | |
| if (!this.graph.hasOwnProperty(j)) { | |
| continue; | |
| } | |
| heap.push({node: j, neighbors: this.graph[j]}); | |
| } | |
| //console.log('sortedNodes:before', sortedNodes); | |
| sortedNodes = heap.sort(sortVertices); | |
| heap = null; | |
| //console.log('sortedNodes:after', sortedNodes); | |
| // ------ STEP 2 -------- | |
| // color initialization | |
| var nbColors = 0; | |
| var nodeColors = {}; | |
| // ------- STEP 3 -------- | |
| while (sortedNodes.length > 0) { | |
| //Node root = sortedNodes.poll(); | |
| var root = sortedNodes.shift(); | |
| //LinkedList<Node> myGroup = new LinkedList<Node>(); | |
| var myGroup = []; | |
| //myGroup.add(root); | |
| myGroup.push(root); | |
| //root.addAttribute(attributeName, nbColors); | |
| root['color'] = nbColors; | |
| nodeColors[root.node] = {'color': nbColors}; | |
| for (var i = 0; i < sortedNodes.length;) { | |
| var p = sortedNodes[i]; | |
| var conflict = false; | |
| for (j = 0; !conflict && j < myGroup.length; j++) { | |
| conflict = getEdgeBetween(p, myGroup[j].node) != null; | |
| } | |
| if (conflict) { | |
| i++; | |
| } else { | |
| //p.addAttribute(attributeName, nbColors); | |
| p['color'] = nbColors; | |
| nodeColors[p.node] = {'color': nbColors}; | |
| //myGroup.add(p); | |
| myGroup.push(p); | |
| //sortedNodes.remove(i); | |
| sortedNodes.splice(i, 1); | |
| } | |
| } | |
| //console.log('myGroup', myGroup); | |
| myGroup = []; | |
| nbColors++; | |
| } | |
| this.chromaticNumber = nbColors; | |
| return nodeColors; | |
| }; | |
| function getEdgeBetween(node1, nodeId) { | |
| //console.log('getEdgeBetween', node1, nodeId); | |
| var nodeIndex = node1.neighbors.indexOf(parseInt(nodeId)); | |
| var result = (nodeIndex === -1) ? null : nodeId; | |
| //console.log('getEdgeBetween', node1, nodeId, result); | |
| return result; | |
| } | |
| function sortVertices(b, a) { | |
| return a.neighbors.length < b.neighbors.length ? 1 : a.neighbors.length == b.neighbors.length ? 0 : -1; | |
| } | |
| var tests = [ | |
| {chromaticNumber: 6 , graph: [[1, 2, 3, 4, 5], [0, 2, 3, 4, 5], [0, 1, 3, 4, 5], [0, 1, 2, 4, 5], [0, 1, 2, 3, 5], [0, 1, 2, 3, 4]]} | |
| , {chromaticNumber: 3 , graph: [[4, 1], [0, 2], [1, 3], [2, 4], [3, 0]]} | |
| , {chromaticNumber: 2 , graph: [[5, 1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 0]]} | |
| , {chromaticNumber: 2 , graph: [[1,2,3,4,5], [0], [0], [0], [0], [0]]} | |
| , {chromaticNumber: 3 , graph: [[1,2,3,4], [0, 4, 2], [0, 1, 3], [0, 2, 4], [0, 3, 1]]} | |
| , {chromaticNumber: 4 , graph: [[4, 1, 5], [0, 2, 5], [1, 3, 5], [2, 4, 5], [3, 0, 5], [0 ,1 ,2, 3, 4]]} | |
| ]; | |
| for (var i in tests) { | |
| var wp = new WelshPowell("color"); | |
| wp.init(tests[i].graph); | |
| var graphColored = wp.compute(); | |
| if (wp.getChromaticNumber() === tests[i].chromaticNumber) { | |
| console.log('Test[' + i + ']:' + wp.getChromaticNumber() + '==' + tests[i].chromaticNumber, 'passed'); | |
| //console.log('The chromatic number of this graph is : ' + wp.getChromaticNumber()); | |
| for (var n in graphColored) { | |
| console.log("Node " + n + " : color " + graphColored[n]['color']); | |
| } | |
| } else { | |
| console.error('Test[' + i + ']:' + wp.getChromaticNumber() + '!=' + tests[i].chromaticNumber, 'failed'); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks for the code!
You have a reference error on line 126,
graphis not defined