To make a hypercube graph it is necessary to connect vertices that have ID’s that differ by 1 bit. I did not readily find any algorithms to do this, so here is my own written in JavaScript.

let pad = (str, max) => {
    return str.length < max ? pad("0" + str, max) : str; 
};

let generateDifferByOne = (input, numBits) => {
    let inputBits = pad((input).toString(2), numBits).split("").reverse();
    let allDiffer = [];

    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;
};

The method above does not generate any values lower than the input, but that can be fixed by adding an “else” inside the loop to switch 1’s to 0’s and push it into allDiffer.

Leave a Reply