damtypo damtypo - 1 month ago 13
Javascript Question

Removing duplicate edges from an array for a d3 force directed graph

I have an array of edges for a force directed graph, which looks like this but much longer.

var rawLinks = [{ source: 1, target: 2 },
{ source: 2, target: 1 },
{ source: 6, target: 7 },
{ source: 7, target: 6 },
{ source: 8, target: 9 },
{ source: 8, target: 9 },
{ source: 8, target: 86 },
{ source: 8, target: 101 },
{ source: 8, target: 133 },
{ source: 8, target: 134 }]


As these are points on a surface for a line to follow, I want to remove elements that will result in duplicate lines between points.

For example I only want one of the first two elements, as they would result in a line from 1 to 2, and 2 to 1. I only need one line between 1 and 2.

I've tried this, but I get unexpected results.

var links = [];

for (var i=0; i<rawLinks.length; i++) {
for (var j=0; j<rawLinks.length; j++) {
if(rawLinks[i].source != rawLinks[j].target &&
rawLinks[i].target != rawLinks[j].source){

links.push(rawLinks[i])
}
}
}


I'm pretty sure my if statement is the issue. Or is this the completely wrong approach?

As usual I'm sure its obvious to someone with fresh eyes.
What's wrong with my code?

Answer

Since it doesn't matter who is the source and who is the target ("1 to 2" is the same of "2 to 1" in your problem), we'll first reorganize the array:

rawLinks.forEach(function(d){
    var sourceTemp = d.source; targetTemp = d.target;
    if(d.source > d.target){
        d.source = targetTemp;
        d.target = sourceTemp;
    }
});

That creates duplicates, like this:

{ source: 1, target: 2 }
{ source: 1, target: 2 }    

Then, we remove the duplicates:

function removeDups(a){
    a.sort();
    for(var i = 1; i < a.length; ){
        if(a[i-1].source === a[i].source && a[i-1].target === a[i].target){
            a.splice(i, 1);
        } else {
            i++;
        }
    }
    return a;
}

Here is a demo:

var rawLinks = [{ source: 1, target: 2 },
    { source: 2, target: 1 },
    { source: 6, target: 7 },
    { source: 7, target: 6 },
    { source: 8, target: 9 },
    { source: 8, target: 9 },
    { source: 8, target: 86 },
    { source: 8, target: 101 },
    { source: 8, target: 133 },
    { source: 8, target: 134 }];
									
rawLinks.forEach(function(d){
	var sourceTemp = d.source; targetTemp = d.target;
	if(d.source > d.target){
		d.source = targetTemp;
		d.target = sourceTemp;
	}
});

function removeDups(a){
    a.sort();
    for(var i = 1; i < a.length; ){
        if(a[i-1].source === a[i].source && a[i-1].target === a[i].target){
            a.splice(i, 1);
            } else {
            i++;
            }
        }
    return a;
    }  

var links = removeDups(rawLinks);

console.log(links);