G6关系图隐藏节点算法探究

作者: 韭菜的故事 | 来源:发表于2020-12-17 21:08 被阅读0次

G6关系图隐藏节点算法探究
Neo4j算法介绍
迪杰斯特拉（Dijkstra）算法
广度优先搜索
算法图解广度优先搜索
A*算法
图数据库Neo4j
Neo4j-属性图和超图和三元组
gojs
【vue2 & G6】快速上手

最近遇到一个需求：在一个关系图上进行特定节点的隐藏，并生成新的关系图。项目里面用的可视化框架是g6，然后我去g6的文档里面搜索了一下“数据过滤”，好家伙，出现了一个左侧目录里面根本不存在的页面，而且并没有任何代码讲解，只是在介绍一个项目，不知道这个项目是曾经存在过还是以后将要上线......最后很无奈，不管数据过滤这个功能是曾经有还是未来会有，反正当前版本是没找着的，只有自力更生了。

关系图基本说明

其实不管是g6还是其他的可视化框架，普通的关系图只需要两组数据（不考虑两个节点之间多条连线），准确的说是两个数组，第一个是点的集合，每一项储存每个节点的id，样式以及其他的信息，至少要有一个唯一id；第二个是节点关系的集合，每一项有一个上游节点id和一个下游节点id，这两个id就能画出两个节点和一条线了。最终无数个节点和节点关系就能组成一个复杂的关系图。
框架会帮我们把节点画到画布上并分配每个节点的坐标，我们要做的就是传入点的集合和关系的集合。
而要实现开头的需求整体上需要两步，第一步是将要隐藏的点从原始的点集合里面去掉，第二步是生成新的节点关系数组。第一步进行数组过滤就能实现，关键就在于第二步。

生成基本的关系图

写了一个demo，整个步骤官网上都有就不赘述了，只将数据放上来，加上了一点样式便于区分，使用的是g6的dagre布局。项目里面一开始没考虑到需要隐藏的节点有两两相邻的情况，所以当时多花了一天才搞定。

    const data = {
      // 点集
      nodes: [
        {
          id: 'node1',
          label: 'n1',
          type: 'normal' // normal-留下的点hide-需要隐藏的点
        },
        {
          id: 'node2',
          label: 'n2',
          type: 'normal'
        },
        {
          id: 'node3',
          label: 'n3',
          type: 'normal'
        },
        {
          id: 'node4',
          label: 'n4',
          type: 'normal'
        },
        {
          id: 'hide1',
          label: 'h1',
          style: {
            fill: 'red'
          },
          type: 'hide'
        },
        {
          id: 'hide2',
          label: 'h2',
          style: {
            fill: 'red'
          },
          type: 'hide'
        }
      ],
      // 边集
      edges: [
        {
          source: 'node1', // 上游节点
          target: 'hide1' // 下游节点
        },
        {
          source: 'node2',
          target: 'hide1'
        },
        {
          source: 'hide1',
          target: 'hide2'
        },
        {
          source: 'hide2',
          target: 'node3'
        },
        {
          source: 'hide2',
          target: 'node4'
        }
      ],
    };

效果图如下

点击切换节点实现红色的点隐藏/显示

现在要求h1和h2隐藏之后n1要连接到n3和n4，n2也要连接到n3和n4。

整体思路

过滤出需要隐藏的点和不需要隐藏的点
从现有的节点关系中过滤出无需改变的节点关系（这个demo比较简单，所有的节点关系都要改变，假如只有h1需要隐藏，那么h2-n3,h2-n4这两个节点关系就过滤出来了）
从现有的节点关系中遍历出需要隐藏的节点的上游节点和下游节点
通过双重遍历上下游节点集合将新的节点关系加入到第一步生成的无需改变的节点关系中
将新的节点关系去重，随后通过不需要隐藏的点和新的节点关系生成新的关系图

上述第三步里面需要判断获取到的上游或下游节点是否也是隐藏节点（递归）

详细过程

首先是准备工作，过滤出需要的数组（以下代码里面使用的'_'都代表lodash中的方法）

      // 需要隐藏的节点的id集合(方便后续计算)
      const hideNodes = data.nodes.filter(v=>v.type==='hide').map(v=>v.id);
      // 剩余正常显示的节点
      const restNodes = data.nodes.filter(v=>v.type!=='hide');
      // 旧的节点关系(因为g6使用data数据生成图之后data里面会多出来很多属性，所以过滤无关属性方便去重)
      const oldEdges = data.edges.map(v => {
          return {
              target: v.target,
              source: v.source
          }
      });
      // 新的节点关系
      let newEdges = [];
      // 无需改变的节点关系
      const noChanges = oldEdges.filter(v=>{
        return !hideNodes.includes(v.target) && !hideNodes.includes(v.source);
      });

获取被隐藏节点的下游节点和上游节点，当上游或下游节点也是被隐藏的节点时需要递归继续判断，这里为了思考方便我写了两个方法，最后项目里面写一个方法就行

  // hideItem是hideNodes遍历时的每一项
    function getTarget(oldEdges, hideItem, hideNodes) {
        const result = [];
        oldEdges.forEach(v=>{
          if(v.source === hideItem) {
            if(hideNodes.includes(v.target)){
              const currentItem = v.target;
              const restHideNodes = _.without(hideNodes, v.target); // 当前值从隐藏节点数组中去掉
              const res = getTarget(oldEdges, currentItem, restHideNodes);
              result.push(...res);
            }else{
              result.push(v.target);
            }
          }
        });
        return result;
      }
      function getSource(oldEdges, hideItem, hideNodes) {
        const result = [];
        oldEdges.forEach(v=>{
          if(v.target === hideItem) {
            if(hideNodes.includes(v.source)){
              const currentItem = v.source;
              const restHideNodes = _.without(hideNodes, v.source); // 当前值从隐藏节点数组中去掉
              const res = getSource(oldEdges, currentItem, restHideNodes);
              result.push(...res);
            }else{
              result.push(v.source);
            }
          }
        });
        return result;
      }

最后双重for循环获取新的节点关系

      hideNodes.forEach(hideItem=>{
        // 被隐藏节点的下游节点
        const targetArr = getTarget(oldEdges, hideItem, hideNodes);
        // 被隐藏节点的上游节点
        const sourceArr = getSource(oldEdges, hideItem, hideNodes);
        for (const target of targetArr) {
          for (const source of sourceArr) {
            noChanges.push({ source, target });
          }
        }
        newEdges.push(...noChanges);
        // 去重
        newEdges = _.uniqWith(newEdges, _.isEqual);
      });

至此这个功能就算是完成了，项目里面用起来暂时还没什么问题，不过像这种稍微复杂的过程可能还有进一步优化的空间，以我的实力也就只能做到这种地步了，这个计算过程还是我与小伙伴讨论前后完善了3天才写出来的，这就是吃了不懂算法的亏啊。

最后附上完整代码

<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
  <button id="hide">切换节点</button>
  <div id="mountNode"></div>
  <script src="https://gw.alipayobjects.com/os/lib/antv/g6/4.0.3/dist/g6.min.js"></script>
  <script src="https://cdn.bootcdn.net/ajax/libs/lodash.js/4.17.20/lodash.min.js"></script>
    <script>
    let isShow = true;
    const data = {...}; // 见上文

    const graph = new G6.Graph({
      container: 'mountNode',
      width: 800,
      height: 500,
      layout: {
          type: 'dagre',
          rankdir: 'LR'
      }
    });
    graph.data(data);
    graph.render();
    const hideBtn = document.getElementById('hide');
    hideBtn.onclick = ()=>{
      isShow = !isShow;
      if(isShow) {
        graph.data(data);
        graph.render();
        return;
      }
      // 需要隐藏的节点的id集合
      const hideNodes = data.nodes.filter(v=>v.type==='hide').map(v=>v.id);
      // 剩余正常显示的节点
      const restNodes = data.nodes.filter(v=>v.type!=='hide');
      // 旧的节点关系(过滤无关属性方便去重)
      const oldEdges = data.edges.map(v => {
          return {
              target: v.target,
              source: v.source
          }
      });
      // 新的节点关系
      let newEdges = [];
      // 无需改变的节点关系
      const noChanges = oldEdges.filter(v=>{
        return !hideNodes.includes(v.target) && !hideNodes.includes(v.source);
      });
      hideNodes.forEach(hideItem=>{
        // 被隐藏节点的下游节点
        const targetArr = getTarget(oldEdges, hideItem, hideNodes);
        // 被隐藏节点的上游节点
        const sourceArr = getSource(oldEdges, hideItem, hideNodes);
        for (const target of targetArr) {
          for (const source of sourceArr) {
            noChanges.push({ source, target });
          }
        }
        newEdges.push(...noChanges);
        // 去重
        newEdges = _.uniqWith(newEdges, _.isEqual);
      });
      const newData = {
        nodes: restNodes,
        edges: newEdges
      };
      
      graph.data(newData);
      graph.render();
    }
    function getTarget(oldEdges, hideItem, hideNodes) {
        const result = [];
        oldEdges.forEach(v=>{
          if(v.source === hideItem) {
            if(hideNodes.includes(v.target)){
              const currentItem = v.target;
              const restHideNodes = _.without(hideNodes, v.target); // 当前值从隐藏节点数组中去掉
              const res = getTarget(oldEdges, currentItem, restHideNodes);
              result.push(...res);
            }else{
              result.push(v.target);
            }
          }
        });
        return result;
      }
      function getSource(oldEdges, hideItem, hideNodes) {
        const result = [];
        oldEdges.forEach(v=>{
          if(v.target === hideItem) {
            if(hideNodes.includes(v.source)){
              const currentItem = v.source;
              const restHideNodes = _.without(hideNodes, v.source); // 当前值从隐藏节点数组中去掉
              const res = getSource(oldEdges, currentItem, restHideNodes);
              result.push(...res);
            }else{
              result.push(v.source);
            }
          }
        });
        return result;
      }
    </script>
</body>
</html>