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