确定网络中属于三元组的边

Question

我有网络的边缘：

  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 = {};

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});
});

给出这样的网络：

我想在连接时更改节点和边的不透明度。我有一个函数可以获取所有 links/edges:

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

然后我可以使用这个函数来检查所有连接的边，例如更改所有连接到节点的不透明度：

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.

不过，我想做的是 return 那些属于三元组的边。

因此在上图中，如果 "E" 被悬停，边缘 E-A、E-K、A-K 以及 E-G、E-F 和 F-G 将被 returned。如果将 "H" 悬停在上方，则 H-G、H-B 和 B-G 将被 returned。

我的目的是突出属于每个节点的三元组。重要的是，我不想要不完整的三合会。即，如果 "C" 悬停在上方，则不会 select C-A 和 C-L，因为三元组未用 A-L 闭合。

Answer 1

非常酷的问题。这是解决它的一种方法。

首先，我构建了每个节点的地图以及附加到它的其他节点：

// 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);
  }
});

然后在鼠标悬停时，沿着路径深入 3 层寻找那个 return 到起点：

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
}

工作代码：

<!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>

确定网络中属于三元组的边

Determine edges belonging to triads in networks

javascript

graph-theory

jgrapht

neural-network

d3.js