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 ....
]

Do you want do delete *all* links that create a cycle, or just the links that create a cycle of length 3? In the former case, you can use [Prim's Algorithm](https://en.wikipedia.org/wiki/Prim%27s_algorithm) to find a Minimal Spanning Tree of a graph. — John Bupit, Sep 23 '15 at 20:31

score 2 · Answer 1 · answered Sep 18 '15 at 18:32

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

maioman · Answer 2 · 2015-09-21T12:05:40.153

1

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.

edited Sep 21 '15 at 12:05

answered Sep 21 '15 at 07:42

maioman

18,154
4
36
42

1

Thanks for the answer. The thing with this is my array isn't as simple as the one you've used. Ill add what it looks like to my question :) – thatOneGuy Sep 21 '15 at 08:20
1

yes kind of but my edges array isn't sorted like yours is. Also, your logic gets rid of random links, like the D-C link you have in your data because its source isn't in the previous target .... – thatOneGuy Sep 21 '15 at 09:27
@thisOneGuy what would you want to do with the discarded entries? – maioman Sep 21 '15 at 12:18
at the moment just get rid. But in the end I'm hoping to go back and forth from both sets of data, so adding and taking away links at will – thatOneGuy Sep 21 '15 at 13:07
@thisOneGuy the sorting issue is understandable https://jsfiddle.net/maio/jjvdjqoj/4/ ~vs~ https://jsfiddle.net/jjvdjqoj/6/ – CrandellWS Sep 27 '15 at 02:12

score 1 · Answer 3 · edited May 23 '17 at 12:14

It seems that we had a similar issue that where I had to create a function to get to a specific node. You can see a different version of the same basic function where it was created and used: http://bl.ocks.org/CrandellWS/79be3b8c9e8b74549af5

The original attempts was to use forEach looping but I found it simpler to use a regular for loop. Though I hope this solves your problem, you should read this answer of Why is using “for…in” with array iteration such a bad idea?

  function getObjByValue(myRoot, myType, myType2, myVal, myVal2){
    var d;
    console.log(typeof myRoot)
    if(typeof myRoot == "object"){
      for(d in myRoot){

        //checking for requirements.
        if(myRoot[d][myType] == myVal && myRoot[d][myType2] == myVal2 ){
          console.log(d);

          //accessing the specific one desired...
          d3.select('#specificOne').text(myRoot[d]["other information"]);

          //deleteing it from the copied array
          delete myRoot[d];

          //do something with the rest
          printRemaining(myRoot);

            //done
            return;
        }
      }
    }
  } 

getObjByValue(edges, 'source', 'target', 'A', 'C');

edges = [
    {
        "source": "A",
        "target": "B",
        "other information" : "randomstringAB",
        "other information2" : "randomstringAB"
    },{
        "source": "A",
        "target": "C",
        "other information" : "randomstringAC",
        "other information2" : "randomstringAC"
    },{
        "source": "B",
        "target": "C",
        "other information" : "randomstringBC",
        "other information2" : "randomstringBC"
    },{
        "source": "D",
        "target": "C",
        "other information" : "randomstringDC",
        "other information2" : "randomstringDC"
    },{
        "source": "C",
        "target": "E",
        "other information2" : "randomstringCE",
        "other information" : "randomstringCE"
    }
]

  function getObjByValue(myRoot, myType, myType2, myVal, myVal2){
    var d;
    console.log(typeof myRoot)
    if(typeof myRoot == "object"){
      for(d in myRoot){
        if(myRoot[d][myType] == myVal && myRoot[d][myType2] == myVal2 ){
          console.log(d);
          //accessing the specific one desired...
          d3.select('#specificOne').text(myRoot[d]["other information"]);
          //deleteing it from the copied array
          delete myRoot[d];
          printRemaining(myRoot);
          console.log(d);
          console.log('done');
            //done
            return;
        }
      }
    }
  } 
  
function printRemaining(myArray){
  for(d in myArray){
    d3.select('#edges').append('p').text(myArray[d]["other information"]+'\r\n');
  }

}


getObjByValue(edges, 'source', 'target', 'A', 'C');

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>
<p>First the specific one</p>
<div id="specificOne"></div>
<br /><br /><br /><br /><br />
<p>It's time to eat, Here is the leftovers.</p>
<div id="edges"></div>

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

3 Answers3

fiddle