Javascript Union Pairs Union Find

Question

I am working on finding a union. I want to group pairs of numbers based on whether one of the indices has a number with the index of the other pair. So:

I have an array of such pairs:

pairs: [[1,3], [6,8], [3,8], [2,7]]

What is the best way to group them in associations like:

[ [ 1, 3, 8, 6 ], [ 2, 7 ] ]

([1,3] and [3,8] go together because they share 3. This group combines with [6,8] because they share 8. What is the best way to do this in javascript?

Here are some more examples:

pairs: [[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25],[29,12], [22,2], [17,11]]

into [ [ 8, 5, 10, 2, 17, 22, 11 ],[ 4, 18 ],[ 20, 12, 29 ],[ 13, 25 ] ]

Edit The method that I am using now is used here:

findUnions = function(pairs, unions){
   if (!unions){
       unions = [pairs[0]];
       pairs.shift();
   }else{
       if(pairs.length){
           unions.push(pairs[0])
           pairs.shift()
       }
   }

    if (!pairs.length){
        return unions
    }
    unite = true
    while (unite && pairs.length){
        unite = false
        loop1:
        for (i in unions){
            loop2:
            var length = pairs.length;
            for (j=0;j<length;j++){
                if (unions[i].includes(pairs[j][0])){
                    if (!unions[i].includes(pairs[j][1])){
                        unions[i].push(pairs[j][1])
                        pairs.splice(j, 1)
                        j-=1;
                        length-=1
                        unite = true
                    }else{
                        pairs.splice(j, 1)
                        j-=1
                        length-=1
                    }
                }else if (unions[i].includes(pairs[j][1])){
                     unions[i].push(pairs[j][0])
                     pairs.splice(j, 1)
                     unite = true
                    j-=1
                    length-=1
                }
            }
        }
    }
    return findUnions(pairs, unions)
}

Answer 1

Method:

finalArray = [], positions = {};    
for i to Array.length
   for j=i+1 to Array.length
       find match between arr[i] and arr[j]
       if match found
          pos = postion mapped to either i or j in positions
          add elements of arr[i] or arr[j] or both depending on pos.
return finalArray

, finalArray position, finalArray.

function mergeArrays(finalArray, pos, subArray) {
for (var k = 0; k < subArray.length; k++) {
    if (finalArray[pos].indexOf(subArray[k]) < 0)
        finalArray[pos].push(subArray[k]);
}

}

function unionArrays(arr) {
var finalArray = [arr[0]],
    positions = {
        0: 0
    };
for (var i = 0; i < arr.length; i++) {
    for (var j = i + 1; j < arr.length; j++) {
        for (var k = 0; k < arr[i].length; k++) {
            if (arr[j].indexOf(arr[i][k]) >= 0) {
                if (i in positions) {
                    mergeArrays(finalArray, positions[i], arr[j]);
                    positions[j] = positions[i];
                } else if (j in positions) {
                    mergeArrays(finalArray, positions[j], arr[i]);
                    positions[i] = positions[j];
                } else {
                    var pos = finalArray.length;
                    finalArray.push([]);
                    mergeArrays(finalArray, pos, arr[i]);
                    mergeArrays(finalArray, pos, arr[j]);
                    positions[i] = positions[j] = pos;
                }
                break;
            }

        }
    }
    if (!(i in positions)) {
        finalArray.push(arr[i]);
        positions[i] = finalArray.length - 1;
    }
}
return finalArray;
}
console.log(unionArrays([[1,3], [6,8], [3,8], [2,7]]));
console.log(unionArrays([[8,5], [10,8], [4,18], [20,12], [5,2], [17,2], [13,25],[29,12], [22,2], [17,11]]));

Hide result

Answer 2

, , . , , true .

, .

Set .

const arr = [[1,3], [6,8], [3,8], [2,7]];

let res = [];

for (const[key, [a, b]] of Object.entries(arr)) {
  const adjacent = arr.filter((el, index) => index !== +key);

const has = adjacent.filter(el => el.includes(a) || el.includes(b));
  res = [...res, ...has.filter(prop => !res.includes(prop))];
}

let not = new Set(...arr.filter(([a, b]) => !res.some(([c, d]) => 
            a === c || b === d || a === d || b === c)));

let set = new Set();

for (const [a, b] of res) {
  if (!set.has(a)) set.add(a);
  if (!set.has(b)) set.add(b);
}

res = [[...set], [...not]];

console.log(res);

Hide result

Answer 3

. , , dfs. Wikipedia .

dfs - dfs ( ), , . ( "" ) ( "" ). "", .

A ( ), node , . :

[[1,3], [6,8], [3,8], [2,7]]

:

{1: [3], 2: [7], 3: [1, 8], 6: [8], 7: [2], 8: [6, 3]}

( ):

function mapNodes(edges) {
    let nodeMap = {}

    edges.forEach(edge => {
        let node1 = edge[0]
        let node2 = edge[1]

        if (!nodeMap[node1]) nodeMap[node1] = [node2]
        else nodeMap[node1].push(node2)

        if (!nodeMap[node2]) nodeMap[node2] = [node1]
        else nodeMap[node2].push(node1)
    })
    return nodeMap
}

dfs , dfs , . [EDIT: ]:

function dfsForest(nodeMap) {
    let forest = []
    let nodes = Object.keys(nodeMap)

    while (true) {
        let root = +nodes.find(node => !nodeMap[node].visited)
        if (isNaN(root)) break // all nodes visited

        forest.push(dfs(root, nodeMap))
    }
    return forest
}

function dfs(root, nodeMap, tree = []) {
    if (tree.includes(root)) return tree // base case

    tree.push(root)
    nodeMap[root].visited = true

    let connectedNodes = nodeMap[root]
    for (let i = 0; i < connectedNodes.length; i++) {
        let connectedNode = connectedNodes[i]
        dfs(connectedNode, nodeMap, tree)
    }
    return tree
}

JSFiddle .

EDIT:

, , . , visitedNodes n- . , .

350 . dfs 5000 . 50 . . , 1,5 2,5 , , .

In fact, here is a JSFiddle with @Dij answer. You will see, if you double the number of edges, the runtime of the four (yikes). Its algorithm has an interesting feature, since there are no optimal / non-optimal cases; everything takes the same amount of time. However, even in the most non-optimal case, the dfs forest is still slightly faster than this flat rate.