How to check if nodes are related? How do I chose only one neighbour if it has two?

Question

I have a force layout in D3.

I have many nodes with links joining them up. My problem is, I want to delete links if nodes meet a certain criteria.

Say I have nodes A,B,C.

Say this tilda character - '~' means connected.

If (A~B && A~C && B~C){

DELETE THE A~C link. //which would leave A~B~C
}

I've tried going through each link :

link.forEach(function{d){ ....

but I can't seem to get my head around how I would do the logic.

I would go through each node 3 times, check if A~B, A~C, B~C, but if i have 100 nodes that's going to be really slow.

Any help would be appreciated :)

Here is how my current edges/links array looks :

edges = [
{
    "source": "A",
    "target": "B",
    "other information" : "randomstring",
    "other information" : "randomstring"
},
{
    "source": "B",
    "target": "C",
    "other information" : "randomstring",
    "other information" : "randomstring"
} // and so on ....
]

Answer 1

This is a graph theory problem where I assume you want to break a cycle, here's what I'd do

Given a graph g of size n and order m

1) build a hash table out of links which maps two nodes with a link (O(m) if the hash is done in constant time), e.g.

// a reference to the link itself (which can be an object or a dom node)
var hash = {}
links.each(function (d) {
  var u = d.source
  var v = d.target
  hash[u] = hash[u] || {}
  // again replace this with the dom node if you want
  hash[u][v] = d
})

2) run dfs finding back edges (more about it in an article I wrote or with a quick google search), whenever you find a back edge you will have info about the source/target node and the length of the cycle O(n + m)

3) erase the link if the length of the cycle is 3 or whatever your criteria is, erasing from links would take O(km) where k is the number of cycles found

Now using d3 you can simply rebind the new data (with some links removed) and rerender the graph

Answer 2

Assuming your logic could be simplified to checking if the current entry.source is equal to the following entry.target, you could use array.reduce:

    edges = [
    {
        "source": "A",
        "target": "B",
        "other information" : "randomstring",
        "other information" : "randomstring"
    },{
        "source": "A",
        "target": "C",
        "other information" : "randomstring",
        "other information" : "randomstring"
    },{
        "source": "B",
        "target": "C",
        "other information" : "randomstring",
        "other information" : "randomstring"
    },{
        "source": "D",
        "target": "C",
        "other information" : "randomstring",
        "other information" : "randomstring"
    },{
        "source": "C",
        "target": "E",
        "other information" : "randomstring",
        "other information" : "randomstring"
    }
]




var res = edges.reduce(function (acc, cur, i, array) {

    if (array[i - 1] == undefined || acc[acc.length - 1].target == cur.source) {
        acc.push(cur)
    }

    return acc

}, [])
console.log(res)

fiddle

This is probably not the most performant solution but, checking 100 objects, you should be fine; furthermore it's quite synthetic and an elegant use of reduce.