javascript d3.js neural-network graph-theory jgrapht

Determine edges belonging to triads in networks

I have edges of a network:

  var links = [
  {source: "A", target: "D", type: "high"},
  {source: "A", target: "K", type: "high"},
  {source: "B", target: "G", type: "high"},
  {source: "H", target: "B", type: "high"},
  {source: "C", target: "A", type: "low"},
  {source: "C", target: "L", type: "low"},
  {source: "E", target: "A", type: "low"},
  {source: "F", target: "B", type: "low"},
  {source: "F", target: "G", type: "low"},
  {source: "K", target: "J", type: "low"},
  {source: "F", target: "I", type: "low"},
  {source: "G", target: "H", type: "low"},
  {source: "E", target: "K", type: "high"},
  {source: "E", target: "G", type: "low"},
  {source: "E", target: "F", type: "high"},
  {source: "E", target: "M", type: "high"},
];

From which I compute the nodes:

var nodes = {};

links.forEach(function(link) {
  link.source = nodes[link.source] || (nodes[link.source] = {name: link.source});
  link.target = nodes[link.target] || (nodes[link.target] = {name: link.target});
});

Giving a network like this:

I want to change opacity of nodes and edges when connected. I have a function to grab all the links/edges:

var linkedByIndex = {};
    links.forEach(function(d) {
        linkedByIndex[d.source.index + "," + d.target.index] = 1;
    });

I can then use this function to check all edges that are connected and e.g. change opacity of all those connected to a node:

function isConnected(a, b) {
    return linkedByIndex[a.index + "," + b.index] || linkedByIndex[b.index + "," + a.index] || a.index == b.index;
}


function fade(opacity) {
        return function(d) {

            node.style("stroke-opacity", function(o) {
                thisOpacity = isConnected(d, o) ? 1 : opacity;
                this.setAttribute('fill-opacity', thisOpacity);
                return thisOpacity;
            }); 
      ....etc.

This is here as a live example.

What I would like to do however is to return those edges that are part of a triad.

Therefore in the above diagram, if "E" was hovered, the edges E-A, E-K, A-K, as well as E-G, E-F and F-G would be returned. If "H" was hovered over, then H-G, H-B and B-G would be returned.

My aim is to highlight the triads belonging to each node. Importantly, I do not want incomplete triads. i.e. if "C" is hovered over, then it wouldn't select C-A and C-L as the triad is not closed with A-L.

Solution

Very cool question. Here's one way to solve it.

First, I built a map of each node and what other nodes are attached to it:

// build a map of every node
// and which are attached to it
// to it both for source and target
// because you don't care about direction
var linkMap = {};
links.forEach(function(d){
  if (!linkMap[d.source.index]){
    linkMap[d.source.index] = [];
  }
  if (linkMap[d.source.index].indexOf(d.target.index) === -1){
    linkMap[d.source.index].push(d.target.index);
  }
  if (!linkMap[d.target.index]){
    linkMap[d.target.index] = [];
  }
  if (linkMap[d.target.index].indexOf(d.source.index) === -1){
    linkMap[d.target.index].push(d.source.index);
  }
});

Then on mouseover, walk the path 3 levels deep looking for one's that return to the starting point:

function followLink(d){

  // only one link, it can't trace back
  if (linkMap[d].length < 2)
    return [];

  var rv = [];
  // trace every route 3 deep
  linkMap[d].forEach(function(i){
    linkMap[i].forEach(function(j){
      linkMap[j].forEach(function(k){
        var a = [i,j,k]; //<-- array of indexes of nodes in triad
        // if there is no repeats in walking
        // and it starts and ends at the same spot
        if (a.filter(function(item, pos) {
          return a.indexOf(item) == pos;
        }).length === 3 && d === a[2]){
          rv.push(a);
        }
      });
    });
  });
  return rv; //<-- array of arrays of triads indexes
}

Working code:

<!DOCTYPE html>
<meta charset="utf-8">
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="http://marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>

<style>
  .node circle {
    stroke-width: 2px;
  }
  
  .node text {
    font-family: sans-serif;
    text-anchor: middle;
    pointer-events: none;
    user-select: none;
    -webkit-user-select: none;
  }
  
  .link {
    stroke-width: 4px;
  }
  
  text {
    font: 18px sans-serif;
    pointer-events: none;
  }
  
  #end-arrow {
    fill: #88A;
  }
</style>

<body>


  <script>
    function bar() {
      console.log("click");
      force.stop();
      force.start();
    }



    var links = [{
      source: "A",
      target: "D",
      type: "high"
    }, {
      source: "A",
      target: "K",
      type: "high"
    }, {
      source: "B",
      target: "G",
      type: "high"
    }, {
      source: "H",
      target: "B",
      type: "high"
    }, {
      source: "C",
      target: "A",
      type: "low"
    }, {
      source: "C",
      target: "L",
      type: "low"
    }, {
      source: "E",
      target: "A",
      type: "low"
    }, {
      source: "F",
      target: "B",
      type: "low"
    }, {
      source: "F",
      target: "G",
      type: "low"
    }, {
      source: "K",
      target: "J",
      type: "low"
    }, {
      source: "F",
      target: "I",
      type: "low"
    }, {
      source: "G",
      target: "H",
      type: "low"
    }, {
      source: "E",
      target: "K",
      type: "high"
    }, {
      source: "E",
      target: "G",
      type: "low"
    }, {
      source: "E",
      target: "F",
      type: "high"
    }, {
      source: "E",
      target: "M",
      type: "high"
    }, ];

    var nodes = {};

    // Compute the distinct nodes from the links.
    links.forEach(function(link) {
      link.source = nodes[link.source] || (nodes[link.source] = {
        name: link.source
      });
      link.target = nodes[link.target] || (nodes[link.target] = {
        name: link.target
      });
    });

    var width = 960,
      height = 700;

    var force = d3.layout.force()
      .nodes(d3.values(nodes))
      .links(links)
      .size([width, height])
      .linkDistance(105)
      .charge(-775)
      .on("tick", tick)
      .start();



    force.on("start", function() {
      console.log("start");
    });
    force.on("end", function() {
      console.log("end");
    });

    R = 18



    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height);

    // add defs-marker
    // add defs-markers
    svg.append('svg:defs').selectAll("marker")
      .data([{
        id: "end-arrow",
        opacity: 1
      }, {
        id: "end-arrow-fade",
        opacity: 0.075
      }])
      .enter().append('marker')
      .attr('id', function(d) {
        return d.id;
      })
      .attr('viewBox', '0 0 10 10')
      .attr('refX', 2 + R)
      .attr('refY', 5)
      .attr('markerWidth', 4)
      .attr('markerHeight', 4)
      .attr('orient', 'auto')
      .append('svg:path')
      .attr('d', 'M0,0 L0,10 L10,5 z')
      .style("opacity", function(d) {
        return d.opacity;
      });

    //phantom marker
    svg.append('svg:defs')
      .append('svg:marker')
      .attr('id', 'end-arrow-phantom')
      .attr('viewBox', '0 0 10 10')
      .attr('refX', 2 + R)
      .attr('refY', 5)
      .attr('markerWidth', 4)
      .attr('markerHeight', 4)
      .attr('orient', 'auto')
      .attr('fill', '#EEE')
      .append('svg:path')
      .attr('d', 'M0,0 L0,10 L10,5 z');


    var link = svg.selectAll(".link")
      .data(force.links())
      .enter()
      .append("line")
      .attr("class", "link")
      .attr("stroke", "#88A")
      .attr('marker-end', 'url(#end-arrow)');

    var node = svg.selectAll(".node")
      .data(force.nodes())
      .enter().append("g")
      .attr("class", "node")
      .call(force.drag);

    node.append("circle")
      .attr("r", R)
      .attr("stroke", '#777')
      .attr("fill", '#DDD')
      .on("mouseover", function(d) {
        var t = followLink(d.index);
        if (t.length){
          link.style('opacity', '0');
          node.style('opacity','0');
          for (var i = 0; i < t.length; i++){
            var a = t[i];
            for (var j = 0; j < a.length; j++){
              var stop = a[j];
              d3.select(node[0][stop]).style('opacity','1');
              var start;
              if (j === 0) start = d.index;
              else start = start = a[j-1];
              links.forEach(function(l,k){
                if (l.source.index === start &&
                    l.target.index === stop){
                      d3.select(link[0][k]).style('opacity','1');
                    }
              });
            }
          }
          
          
          followLink(d.index).forEach(function(i){
            i.forEach(function(j){
              d3.select(node[0][j]).style('opacity','1');
            });
          });
        }
      })
      .on("mouseout", function(){
        node.style('opacity','1');
        link.style('opacity','1');
      });

    node.append("text")
      .attr("x", 0)
      .attr("dy", ".35em")
      .text(function(d) {
        return d.name;
      });

    function tick() {
      link
        .attr("x1", function(d) {
          return d.source.x;
        })
        .attr("y1", function(d) {
          return d.source.y;
        })
        .attr("x2", function(d) {
          return d.target.x;
        })
        .attr("y2", function(d) {
          return d.target.y;
        });

      node
        .attr("transform", function(d) {
          return "translate(" + d.x + "," + d.y + ")";
        });
    }

    // build a map of every node
    // and which are attached to it
    // to it both for source and target
    // because you don't care about direction
    var linkMap = {};
    links.forEach(function(d){
      if (!linkMap[d.source.index]){
        linkMap[d.source.index] = [];
      }
      if (linkMap[d.source.index].indexOf(d.target.index) === -1){
        linkMap[d.source.index].push(d.target.index);
      }
      if (!linkMap[d.target.index]){
        linkMap[d.target.index] = [];
      }
      if (linkMap[d.target.index].indexOf(d.source.index) === -1){
        linkMap[d.target.index].push(d.source.index);
      }
    });
    
    function followLink(d){

      // only one link, it can't trace back
      if (linkMap[d].length < 2)
        return [];
        
      var rv = [];
      // trace every route 3 deep
      linkMap[d].forEach(function(i){
        linkMap[i].forEach(function(j){
          linkMap[j].forEach(function(k){
            var a = [i,j,k];
            // if there is not repeats
            // and it starts and ends at the same spot
            if (a.filter(function(item, pos) {
              return a.indexOf(item) == pos;
            }).length === 3 && d === a[2]){
              rv.push(a);
            }
          });
        });
      });
      return rv;
    }

  </script>