For my graph algorithm playground I wrote the method below to generate an n-dimensional hypercube graph. It utilizes a helper function that I wrote up here.
let hypercubeGraph = (D) => { let edges = []; let nodes = []; let numNodes = Math.pow(2, D); const pad = (str, max) => { return str.length < max ? pad("0" + str, max) : str; }; const generateDifferByOne = (input, numBits) => { let inputBits = pad((input).toString(2), numBits).split("").reverse(); let allDiffer = []; // 1 bit difference from input, increasing order, none less than input for(let b = 0; b < numBits; b++){ if(inputBits[b] === "0"){ let newNum = inputBits.slice(); newNum[b] = "1"; allDiffer.push(parseInt(newNum.reverse().join(""), 2)); } } return allDiffer; }; for(let i = 0; i < numNodes; i++){ nodes.push({id: i, label: pad(i.toString(2), D)}); generateDifferByOne(i, D).forEach((j) => { edges.push({from: i, to: j}); }); } return {nodes: nodes, edges: edges, directed: false, weighted: false}; };
Leave a Reply