Group vertices and edges to separate graphs in JavaScript

Question

the problem has an arbitrary array of directed edges, for example,

let pairs = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];

The array can contain one or more graphs at once. The task is to go through the pairs and break them into groups, in this particular case, the result should be

let output = [

    [0, 3, 5, 6, 9, 12],
    [1, 2, 4, 7, 10],
    [8, 11] 

]; //please 

let pairs = [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]];

let groups = [];

for(let i = 0; i < pairs.length; i++){

        if(groups.length == 0){
    
            groups.push([]);
        groups[0].push(pairs[i][0]);
        groups[0].push(pairs[i][1]);
    
    }
    else{

                let parentGroup = getParentGroup(groups, pairs[i]);
        
        if(parentGroup == null){
        
                groups.push([]);
                groups[groups.length - 1].push(pairs[i][0]);
                groups[groups.length - 1].push(pairs[i][1]);
        
        }
        else{
        
                if(parentHasNode(groups[parentGroup], pairs[i][0])){ if(!parentHasNode(groups[parentGroup], pairs[i][1])) { groups[parentGroup].push(pairs[i][1]); } }
            if(parentHasNode(groups[parentGroup], pairs[i][1])){ if(!parentHasNode(groups[parentGroup], pairs[i][0])) { groups[parentGroup].push(pairs[i][0]); } }
        
        }
                
    
    }


}

console.log(groups);

function parentHasNode(group, left){

        for(let i = 0; i < group.length; i++){
    
            if(group[i] == left) { return true; }
    
    }
    
    return false;

}

function getParentGroup(groups, pair){

        let out = null;
    
    for(let i = 0; i < groups.length; i++){
    
            for(let j = 0; j < groups[i].length; j++){
        
                if(pair[0] == groups[i][j] || pair[1] == groups[i][j]) { out = i; break; }
        
        }
    
    }
    
    return out;

}

ignore sorting

Visually these vertices are arranged into the three graphs illustrated below

By now, I don't need an algorithm to draw these graphs, but to group vertices into separate ones.

I have attached the current code, but it doesn't work correctly every time.

let pairs = [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]];

doesn't work right

let output =     [
    [25, 15], 
    [22, 6, 15, 9, 16], 
    [7, 29], 
    [2, 5], 
    [26, 24, 29, 5], 
    [1, 18], 
    [13, 12], 
    [19, 30, 18, 12], 
    [8, 20], 
    [11, 3, 20], 
    [28, 23, 3, 20], 
    [4, 10], 
    [14, 27], 
    [21, 17, 10, 27], 
    [0, 31]
];

The first group has 3 as well as sixth as well as other errors. It has to be something like that

output =   [

    [25, 15, 22, 6, 9, 16],
    [26, 24, 29, 5, 2, 7],
    [19, 30, 18, 12, 1, 13], 
    [28, 23, 3, 20, 8, 11],
    [21, 17, 10, 27, 4, 14], 
    [0, 31]

  ];

Answer 1

Since the pairs array represents a directed graph, establishing the groups involves traversing the array seeking the chain of matching pairs.

The proposed algorithm below has an outer loop that establishes the current edge pair, seeking matches in the remaining portion of the edge array, and if any matches are found, consolidates these matches into the current edge pair, which of course, is evolving into an edge set. The found matches are then cleared as they have been consolidated with the current edge set, and this continues until the outer loop reaches the end of the edge array.

Finally, the resulting array is a combination of consolidated sets and cleared sets, so the result returns only the non-empty sets.

function groupEdges( edges ) {

  // Turn the edge pairs into Set objects.
  temp = edges.map( po => new Set( po ) );
 
  // Loop through each edge set...
  for ( let i = 0; i < temp.length; i++ ) {
    let currentEdgeSet = temp[ i ];
    if ( currentEdgeSet ) {
      // Loop through each edge...
      let a = Array.from( currentEdgeSet );
      for ( let pi = 0; pi < a.length; pi++ ) {
        // ...and now loop through the remaining edges, seeking a match with
        // the current edge.  Include any found matching edges in with the
        // currentEdgeSet, clear the found matches (as they have been included
        // with the currentEdgeSet), and then re-establish the list of edges
        // being sought from the currentEdgeSet.
        for ( let j = i + 1; j < temp.length; j++ ) {
          if ( temp[ j ] && temp[j].has( a[ pi ] ) ) {
            temp[ j ].forEach( currentEdgeSet.add, currentEdgeSet );
            temp[ j ] = null;
            a = Array.from( currentEdgeSet );
          }
        }
      }
    }
  }
  
  // Finally, only return the non-null edge sets.
  return temp.filter( es => es );
  
}

console.log( groupEdges( [[9, 6], [10, 2], [2, 1], [7, 1], [5, 6], [1, 10], [8, 11], [10, 4], [9, 0], [12, 0], [3, 9], [0, 6]] ).map( s => Array.from( s ) ) );
console.log( groupEdges( [[25, 15], [22, 6], [6, 15], [15, 9], [9, 6], [16, 9], [7, 29], [2, 5], [26, 24], [24, 29], [5, 24], [29, 5], [1, 18], [13, 12], [19, 30], [30, 18], [12, 30], [18, 12], [8, 20], [11, 3], [28, 23], [20, 3], [3, 23], [23, 20], [4, 10], [14, 27], [21, 17], [10, 17], [17, 27], [27, 10], [0, 31]] ).map( s => Array.from( s ) ) );

Note the nuance associated with looping over the values in the currentEdgeSet. JavaScript retains the order of entries added to a Set object, and hence the ability to make use of the index pi into the currentEdgeSet, with the list of ordered edges (ie, ordered by entry into the set) being re-established via a = Array.from( currentEdgeSet ) whenever any new matches are consolidated into currentEdgeSet.