d3js - Force-Directed Graph: Delete node that only link to itself

Question

I am trying to do the Force-Directed Graph from this example but my data is really big (5000 nodes) so I want to remove some nodes that do not link to any other nodes.

However, in my JSON, every node has at least 1 link (that link to itself). This is an example of my data:

{"directed": false, "graph": {}, 
"nodes": [{"id": 0}, {"id": 1}, {"id": 2}, {"id": 3}, {"id": 4}, {"id": 5}, 
         {"id": 6}, {"id": 7}, {"id": 8}, {"id": 9}, {"id": 10}, {"id": 11}, {"id": 12}], 

"links": [{"source": 0, "target": 0}, {"source": 1, "target": 1}, 
    {"source": 2, "target": 2}, {"source": 3, "target": 3}, 
    {"source": 4, "target": 4}, {"source": 5, "target": 5}, 
    {"source": 6, "target": 6}, {"source": 7, "target": 8}, 
    {"source": 7, "target": 9}, {"source": 7, "target": 10}, 
    {"source": 7, "target": 11}, {"source": 7, "target": 7}, 
    {"source": 8, "target": 8}, {"source": 9, "target": 9}, 
    {"source": 10, "target": 10}, {"source": 11, "target": 11}, 
    {"source": 12, "target": 12}], "multigraph": false}

I.e., node id:0 only has link {"source": 0, "target": 0} so it should get removed but node id:7 has links {"source": 7, "target": 8}, {"source": 7, "target": 7}. It is linked to another node so it should not get removed.

My question is how do I delete nodes that only link to itself?

altocumulus altocumulus · Accepted Answer · 2017-05-22T12:45:37

One way to do this is to first boil down the links to those which are not referring to the same node, i.e. where source !== target. I chose to use Array.prototype.reduce() although other ways of iteration will work just the same. To speed up the elimintation of nodes later on I am also employing a Set to store unique id values, which technically is not necessary for this to work, though.

let uniqueNonSelfReferringLinks = data.links.reduce((set, {source:s, target:t}) =>
  s !== t ? set.add(s).add(t) : set,
  new Set()
);

Filtering the nodes then comes down to iterating the nodes array looking up the set for the value of the nodes' ids:

let filteredNodes = data.nodes.filter(n => uniqueNonSelfReferringLinks.has(n.id));

Consolidating both steps into one this can be written even more concisely:

let filteredNodes = data.nodes.filter(
  function(n) { return this.has(n.id); },  
  data.links.reduce((set, {source:s, target:t}) =>
    s !== t ? set.add(s).add(t) : set,
    new Set()
  )
);

Have a look at the following working demo:

var data = {
  "directed": false,
  "graph": {}, 
  "nodes": [{"id": 0}, {"id": 1}, {"id": 2}, {"id": 3}, {"id": 4}, {"id": 5}, 
         {"id": 6}, {"id": 7}, {"id": 8}, {"id": 9}, {"id": 10}, {"id": 11}, {"id": 12}], 

  "links": [{"source": 0, "target": 0}, {"source": 1, "target": 1}, 
    {"source": 2, "target": 2}, {"source": 3, "target": 3}, 
    {"source": 4, "target": 4}, {"source": 5, "target": 5}, 
    {"source": 6, "target": 6}, {"source": 7, "target": 8}, 
    {"source": 7, "target": 9}, {"source": 7, "target": 10}, 
    {"source": 7, "target": 11}, {"source": 7, "target": 7}, 
    {"source": 8, "target": 8}, {"source": 9, "target": 9}, 
    {"source": 10, "target": 10}, {"source": 11, "target": 11}, 
    {"source": 12, "target": 12}],
  "multigraph": false
};

let filteredNodes = data.nodes.filter(
  function(n) { return this.has(n.id); },  
  data.links.reduce((set, {source:s, target:t}) =>
    s !== t ? set.add(s).add(t) : set,
    new Set()
  )
);

console.log(filteredNodes);

d3js - Force-Directed Graph: Delete node that only link to itself

1 Answers