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