Group vertices and edges to separate graphs in JavaScript

the problem has an arbitrary array of directed edges, for example, let pairs = [[9, … Read more Group vertices and edges to separate graphs in JavaScript

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

enter image description here

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 = [[20, 3], [24, 29], [12, 30], [16, 9], [4, 10], [28, 23], [6, 15], [30, 18], [2, 5], [14, 27], [8, 20], [10, 17], [1, 18], [25, 15], [31, 0], [3, 23], [15, 9], [17, 27], [29, 5]];

doesn’t work right

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

The first group has 3 as well as sixth as well as other errors.

Source: JavaSript – Stack Overflow



Leave a Reply

Your email address will not be published. Required fields are marked *