mis.js

'use strict';

const VERTEX_COUNT = 7*7*7*7*7;
const VERTEX_DEGREE = 243;

function buildGraph() {
	function* range(lo,hi) {
		var index = 0;
		for (var i = lo ; i < hi ; i++) {
			yield i;
		}
	}

	/**
	 * generates the set of vertices of points in (Z7)^5
	 */
	function* vertices() {
		for (let a of range(0, 7)) 
			for (let b of range(0, 7))
				for (let c of range(0, 7))
					for (let d of range(0, 7))
						for (let e of range(0, 7))
							yield [a, b, c, d, e];
	}

	/**
	 * generates the set of adjacent vertices to the vertices v, 
	 * this set includes v itself.
	 */
	function* neighborhood(v) {
		function mod7(i) {
			var m = i % 7;
			return (m < 0) ? (7 + m) : m;
		}

		for (let a of range(-1,2)) 
			for (let b of range(-1,2))
				for (let c of range(-1,2))
					for (let d of range(-1,2))
						for (let e of range(-1,2))
							yield [ mod7(a + v[0]), mod7(b + v[1]), mod7(c + v[2]), mod7(d + v[3]), mod7(e + v[4])];
	}

	/**
	 * assign a unique integer from [0 .. 7^5) for each vertex.
	 * returns a forward ( Vertex -> Int ) and a backward maps (Int -> Vertex).
	 */
	function assignLabelsToVertices() {
		var i = 0;
		var forwards = {};
		var backwards = {};
		for (let v of vertices()) {
			forwards[v] = i;
			backwards[i] = v;
			i++;
		}
		return [forwards, backwards];	
	} 

	/**
	 * create the graph.
	 *
	 */
	function initializeGraph(numericLables) {
		var graph = new Uint16Array(VERTEX_DEGREE * VERTEX_COUNT);
		for (let v of vertices()) {
			let neighbors = [];
			for (let u of neighborhood(v)) {
				neighbors.push(numericLables[u]);
			}
			neighbors.sort((a, b) => a - b);
			const startingPositionOfV = numericLables[v] * VERTEX_DEGREE;
			for (var j = 0 ; j < neighbors.length ; j++) {
				graph[startingPositionOfV + j] = neighbors[j];		
			}
		}
		return graph;
	}

	const [forwards, backwards] = assignLabelsToVertices();
	const graph = initializeGraph(forwards);
	return { graph : graph, index : backwards}; 
}

var {graph: graph, index: index} = buildGraph();


// 
// actual stuff
// 

function binarySearch(array, value, lo, hi) {
	while (lo < hi) {
		var mid = (lo + hi) >>> 1;
	  	var v = array[mid];
		if (v < value) {
			lo = mid + 1;
		} else {
			hi = mid;
		}
	}
	return hi;
}

class MarkovState {

	constructor() {
		this.elements = new Array(401); // max possible i.s
		for (var i = 0 ; i < this.elements.length ; i++) {
			this.elements[i] = 0;
		}
		this.size = 0;
	}

	add(v) {
		let elements = this.elements;
		const pos = binarySearch(elements, v, 0, this.size);
		elements.splice(pos, 0, v);
		this.size++;
	}

	remove(v) {
		let elements = this.elements;
		const pos = binarySearch(elements, v, 0, this.size);
		elements.splice(pos, 1);
		this.size--;
	}

	len() {
		return this.size;
	}

	independentSet() {
		var result = [];
		for (var i = 0 ; i < this.len() ; i++) {
		 	let v = this.elements[i];
		 	result.push(index[v]);
		}
		return result;
	}

	/* move:
	* 3: v has no nighbhors in the independent set, doAddition.
	* 2: v has exactly one nighbhor in the i.s, doDrag.
	* 1: v has at least two neighbors in the i.s, doNothing.
	* 0: v itself is present in the i.s, doRemove
	*/
	possibleMove(v) {
        // track the move with the assoc move data
        var move = 3;
        var u = 0;
        // i.s
        const a = this.elements;
        const lena = this.len();
        var i = 0;
       	// neighbhrhood 
       	const b = graph;
       	const lenb = 243 * (v + 1);
       	var j = 243 * v;
       	// find the intersection between the neighbrhood of v and the i.s
        while (i < lena && j < lenb) {
            if (a[i] < b[j]) {
                i = binarySearch(a, b[j], i, lena);
            } else if (a[i] > b[j]) {
                j = binarySearch(b, a[i], j, lenb);
            } else {
                u = a[i];
                i += 1;
                j += 1;
                if (u === v) {
                    move = 0;
                    break;
                }
                if (move == 2) {
                    move = 1
                    break;
                }
                move = 2;
            }
        }
        return [move, u];
	}

}

const LAMBDA = 1.0 / (2.0*(242.0) - 3);
const REMOVE = (1.0 - 1.0 / (1.0 + LAMBDA)) * 1e-4;
const ADD = 1.0 - LAMBDA / (1.0 + LAMBDA);
const DRAG = 1.0 - LAMBDA / 4*(1.0 + LAMBDA);


function doRemove(state, u, v) {
	if (Math.random() < REMOVE) {
    	state.remove(v);
    }
}

function doDrag(state, u, v) {
	if (Math.random() < DRAG) {
    	state.remove(u);
    	state.add(v);
    }
}

var lastReport = 0;

function doAdd(state, u, v) {
	if (Math.random() < ADD) {
    	state.add(v);
    	if (state.len() > lastReport) {
    		lastReport = state.len();
    		postMessage(state.independentSet());
    	}
    }
}

function doNothing(state, u , v) {
}

const moves = [doRemove, doNothing, doDrag, doAdd];

var state = new MarkovState();
while (true) {
    const v = Math.floor(Math.random() * VERTEX_COUNT);
    const [move, u] = state.possibleMove(v);
    moves[move](state, u , v);
}