Javascript Union Pairs Union Find

Question

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

I have an array of pairs such as these:

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

whats the best way to group them in unions such as this:

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

([1,3] and [3,8] go together because they share 3. That group unites with [6,8] because they share 8. Whats the best way to do this in javascript?

Here are other 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 Here's the method I'm currently using:

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

In the method we keep storing positions of arrays we are adding to finalArray in positions object and later we can use this object to find a suitable position to add elements of matched arrays in 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]]));

Answer 2

Ah. The algorithm you're looking for is a dfs forest. Wikipedia has some good stuff on trees and forests.

A dfs forest is just a dfs (Depth-First Search) that is run until there are no unvisited nodes. The result is a graph ("forest") of connected and isolated subgraphs ("trees"). These are the "unions" you refer to.

A Depth-First Search is much easier (and faster) when each node is mapped to the nodes to which it's connected. So instead of this data:

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

you want:

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

Transforming your data is fairly trivial (and fast):

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
}

Then the dfs itself is a simple recursive algorithm and the dfs forest just keeps running it until there are no more unvisited nodes. Here's a [EDIT: not so] crude example:

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
}

And here's a JSFiddle with all of that.

EDIT:

Well, I said it was crude. I've edited the code and the fiddle, removing the extra visitedNodes array and the n-squared algorithm it created. It should be just about as blazingly fast as is humanly discovered now.

In my tests it takes about 350 milliseconds to re-format the data AND run the dfs forest on 5000 very non-optimal pairs. In an optimal case, it takes about 50 milliseconds. And it degrades very well. For example, doubling the total edges will increase the execution time from between 1.5 and 2.5 times, depending on how optimal the pairs are.

In fact, here's a JSFiddle with the answer by @Dij. You'll see if you double the number of edges, execution time quadruples (yikes). His algorithm does have an interesting feature, in that there are no optimal/non-optimal cases; everything takes the same amount of time. However, even in the most non-optimal case, a dfs forest is still slightly faster than that flat rate.