Using JavaScript to break a graph into its components

Let's say we have a graph depicted by two objects:

• nodes: an array of objects that, at least, have an id property each
• edges: an array of objects that, at least, have both start_id, end_id properties each

Regardless the properties actual names, it's the meaning what matters.

For simplicity's sake, let's define our edges as an array of arrays like [start_id, end_id] and the result as an array of arrays of node's ids, being each array a component.

What's a graph component?

A maximal connected subgraph within a larger graph.

The code

/**
 * 
 * @param {2D array} edges
 * @returns {2D array} components
 */

const components = edges => {
    const
        tmp = new Set(),
        used = [];
    edges.forEach((a, i) => {
        if (!used.includes(i)) {
            let a_tmp = new Set(a);
            used.push(i);
            edges.forEach((b, j) => {
                const b_tmp = new Set(b);
                if (!used.includes(j) && !a_tmp.isDisjointFrom(b_tmp)) {
                    used.push(j);
                    a_tmp = a_tmp.union(b_tmp);
                }
            });
            tmp.add([...a_tmp].sort((b,a) => b - a));
        }
    });
    const results = [...tmp];
    return (results.length > edges.length) ? components(results) : results;
}

Code breakdown

• We use Set because:
  • It stores only unique values
  • Can be converted from (new Set(array)) and to ([...set]) arrays
  • Allow us to perform set operations
• We use recursion because we need to follow the connected edges. The friend of my friend, is my friend
• We keep track of used ids to avoid processing the same branch of the component twice
• This function is both quite memory efficient and light fast
• .sort((b,a) => b - a) statement is for clarity sake, remove this part to improve performance

The example

const test_case = [
    [0,26],
    [1,26],
    [2,26],
    [3,26],
    [11,160],
    [12,161],
    [13,162],
    [14,163],
    [15,164],
    [16,165],
    [26,167],
    [28,182],
    [33,191],
    [34,191],
    [35,191],
    [36,191],
    [38,193],
    [39,194],
    [45,195],
    [46,197],
    [47,198],
    [139,140],
    [143,216],
    [199,211],
    [211,223],
    [217,261],
    [218,262],
    [219,264],
    [221,266],
    [222,267],
    [223,224],
    [224,225],
    [225,298],
    [225,226],
    [226,229],
    [226,328],
    [227,333],
    [229,242],
    [241,389],
    [242,265],
    [242,328],
    [243,391],
    [244,392],
    [245,393],
    [246,394],
    [247,395],
    [248,396],
    [249,397],
    [250,398],
    [251,399],
    [252,400],
    [256,428],
    [257,429],
    [258,430],
    [259,431],
    [260,432],
    [265,268],
    [268,269],
    [269,282],
    [282,298],
    [298,328],
    [298,328],
    [298,327],
    [305,352],
    [306,353],
    [309,356],
    [310,357],
    [311,359],
    [312,360],
    [313,362],
    [314,363],
    [315,366],
    [322,417],
    [323,418],
    [324,420],
    [325,421],
    [326,422],
    [328,329],
    [328,332],
    [328,390],
    [329,330],
    [330,331],
    [331,332],
    [332,390],
    [332,350],
    [334,335],
    [350,351],
    [351,369],
    [369,370],
    [370,373],
    [373,374],
    [374,390],
    [390,409],
    [409,410]
];

console.log(components(test_case));
// [
//     [0,1,2,3,26,167],
//     [11,160],
//     [12,161],
//     [13,162],
//     [14,163],
//     [15,164],
//     [16,165],
//     [28,182],
//     [33,34,35,36,191],
//     [38,193],
//     [39,194],
//     [45,195],
//     [46,197],
//     [47,198],
//     [139,140],
//     [143,216],
//     [199,211,223,224,225,226,229,242,265,268,269,282,298,327,328,329,330,331,332,350,351,369,370,373,374,390,409,410],
//     [217,261],
//     [218,262],
//     [219,264],
//     [221,266],
//     [222,267],
//     [227,333],
//     [241,389],
//     [243,391],
//     [244,392],
//     [245,393],
//     [246,394],
//     [247,395],
//     [248,396],
//     [249,397],
//     [250,398],
//     [251,399],
//     [252,400],
//     [256,428],
//     [257,429],
//     [258,430],
//     [259,431],
//     [260,432],
//     [305,352],
//     [306,353],
//     [309,356],
//     [310,357],
//     [311,359],
//     [312,360],
//     [313,362],
//     [314,363],
//     [315,366],
//     [322,417],
//     [323,418],
//     [324,420],
//     [325,421],
//     [326,422],
//     [334,335]
// ]