关于前端:可视化图布局算法浅析

前言

图算法在前端畛域考查的较少，个别除非是要写框架或者打包工具对依赖关系解决（DAG）会用到，前端对图算法的考查个别是比拟少的，而对于可视化畛域而言，图又是必不可少的一种展现形式，其中对于边和节点的展现布局计划联合美学成果会有不同的算法实现，本文旨在介绍一些常见的通用布局算法，其中的每个小的布局计划也会有不同的分支实现

分类

常见算法

Fruchterman-Reingold 布局算法

Fruchterman-Reingold 算法属于力导布局的一种，其本质是将之前 Eades 的布点算法中的基于胡克定律模型进行了改良，应用了库伦斥力并且聚焦在最近相邻节点之间的能量模型，利用模拟退火等优化策略，联合美学规范对整体进行缩小线穿插及整体平均布局，其伪码形容如下图：

对于更加细节的对于 FR 算法的推到，能够参看这篇论文 Graph Drawing by Force-directed Placement；接下来，咱们来看一下前端可视化畛域的一些具体实现，咱们联合 Antv G6 中的源码看一下实现思路：

/**
* Antv 的 layout 是专门公布了一个 npm 包 源码地址：https://github.com/antvis/layout
* FR 算法目录地位 https://github.com/antvis/layout/blob/master/src/layout/fruchterman.ts
*/


import {
  OutNode,
  Edge,
  PointTuple,
  IndexMap,
  Point,
  FruchtermanLayoutOptions
} from "./types";
import {Base} from "./base";
import {isNumber} from "../util";

type NodeMap = {[key: string]: INode;
};

type INode = OutNode & {cluster: string;};

const SPEED_DIVISOR = 800;

/**
 * fruchterman 布局
 */
export class FruchtermanLayout extends Base {
  /** 布局核心 */
  public center: PointTuple;

  /** 进行迭代的最大迭代数 */
  public maxIteration: number = 1000;

  /** 重力大小，影响图的紧凑水平 */
  public gravity: number = 10;

  /** 速度 */
  public speed: number = 1;

  /** 是否产生聚类力 */
  public clustering: boolean = false;

  /** 聚类力大小 */
  public clusterGravity: number = 10;

  public nodes: INode[] = [];

  public edges: Edge[] = [];

  public width: number = 300;

  public height: number = 300;

  public nodeMap: NodeMap = {};

  public nodeIdxMap: IndexMap = {};

  /** 迭代完结的回调函数 */
  public onLayoutEnd: () => void = () => {};

  constructor(options?: FruchtermanLayoutOptions) {super();
    this.updateCfg(options);
  }

  public getDefaultCfg() {
    return {
      maxIteration: 1000,
      gravity: 10,
      speed: 1,
      clustering: false,
      clusterGravity: 10
    };
  }

  /**
   * 执行布局
   */
  public execute() {
    const self = this;
    const nodes = self.nodes;

    if (!nodes || nodes.length === 0) {if (self.onLayoutEnd) self.onLayoutEnd();
      return;
    }

    if (!self.width && typeof window !== "undefined") {self.width = window.innerWidth;}
    if (!self.height && typeof window !== "undefined") {self.height = window.innerHeight;}
    if (!self.center) {self.center = [self.width / 2, self.height / 2];
    }
    const center = self.center;

    if (nodes.length === 1) {nodes[0].x = center[0];
      nodes[0].y = center[1];
      if (self.onLayoutEnd) self.onLayoutEnd();
      return;
    }
    const nodeMap: NodeMap = {};
    const nodeIdxMap: IndexMap = {};
    nodes.forEach((node, i) => {if (!isNumber(node.x)) node.x = Math.random() * this.width;
      if (!isNumber(node.y)) node.y = Math.random() * this.height;
      nodeMap[node.id] = node;
      nodeIdxMap[node.id] = i;
    });
    self.nodeMap = nodeMap;
    self.nodeIdxMap = nodeIdxMap;
    // layout
    return self.run();}

  public run() {
    const self = this;
    const nodes = self.nodes;
    const edges = self.edges;
    const maxIteration = self.maxIteration;
    const center = self.center;
    const area = self.height * self.width;
    const maxDisplace = Math.sqrt(area) / 10;
    const k2 = area / (nodes.length + 1);
    const k = Math.sqrt(k2);
    const gravity = self.gravity;
    const speed = self.speed;
    const clustering = self.clustering;
    const clusterMap: {[key: string]: {
        name: string | number;
        cx: number;
        cy: number;
        count: number;
      };
    } = {};
    if (clustering) {
      nodes.forEach(n => {if (clusterMap[n.cluster] === undefined) {
          const cluster = {
            name: n.cluster,
            cx: 0,
            cy: 0,
            count: 0
          };
          clusterMap[n.cluster] = cluster;
        }
        const c = clusterMap[n.cluster];
        if (isNumber(n.x)) {c.cx += n.x;}
        if (isNumber(n.y)) {c.cy += n.y;}
        c.count++;
      });
      for (const key in clusterMap) {clusterMap[key].cx /= clusterMap[key].count;
        clusterMap[key].cy /= clusterMap[key].count;
      }
    }
    for (let i = 0; i < maxIteration; i++) {const displacements: Point[] = [];
      nodes.forEach((_, j) => {displacements[j] = {x: 0, y: 0};
      });
      self.applyCalculate(nodes, edges, displacements, k, k2);

      // gravity for clusters
      if (clustering) {
        const clusterGravity = self.clusterGravity || gravity;
        nodes.forEach((n, j) => {if (!isNumber(n.x) || !isNumber(n.y)) return;
          const c = clusterMap[n.cluster];
          const distLength = Math.sqrt((n.x - c.cx) * (n.x - c.cx) + (n.y - c.cy) * (n.y - c.cy)
          );
          const gravityForce = k * clusterGravity;
          displacements[j].x -= (gravityForce * (n.x - c.cx)) / distLength;
          displacements[j].y -= (gravityForce * (n.y - c.cy)) / distLength;
        });

        for (const key in clusterMap) {clusterMap[key].cx = 0;
          clusterMap[key].cy = 0;
          clusterMap[key].count = 0;
        }

        nodes.forEach(n => {const c = clusterMap[n.cluster];
          if (isNumber(n.x)) {c.cx += n.x;}
          if (isNumber(n.y)) {c.cy += n.y;}
          c.count++;
        });
        for (const key in clusterMap) {clusterMap[key].cx /= clusterMap[key].count;
          clusterMap[key].cy /= clusterMap[key].count;
        }
      }

      // gravity
      nodes.forEach((n, j) => {if (!isNumber(n.x) || !isNumber(n.y)) return;
        const gravityForce = 0.01 * k * gravity;
        displacements[j].x -= gravityForce * (n.x - center[0]);
        displacements[j].y -= gravityForce * (n.y - center[1]);
      });

      // move
      nodes.forEach((n, j) => {if (!isNumber(n.x) || !isNumber(n.y)) return;
        const distLength = Math.sqrt(displacements[j].x * displacements[j].x +
            displacements[j].y * displacements[j].y
        );
        if (distLength > 0) {// && !n.isFixed()
          const limitedDist = Math.min(maxDisplace * (speed / SPEED_DIVISOR),
            distLength
          );
          n.x += (displacements[j].x / distLength) * limitedDist;
          n.y += (displacements[j].y / distLength) * limitedDist;
        }
      });
    }

    if (self.onLayoutEnd) self.onLayoutEnd();

    return {
      nodes,
      edges
    };
  }

  private applyCalculate(nodes: INode[],
    edges: Edge[],
    displacements: Point[],
    k: number,
    k2: number
  ) {
    const self = this;
    self.calRepulsive(nodes, displacements, k2);
    self.calAttractive(edges, displacements, k);
  }

  // 计算斥力
  private calRepulsive(nodes: INode[], displacements: Point[], k2: number) {nodes.forEach((v, i) => {displacements[i] = {x: 0, y: 0};
      nodes.forEach((u, j) => {if (i === j) {return;}
        if (!isNumber(v.x) ||
          !isNumber(u.x) ||
          !isNumber(v.y) ||
          !isNumber(u.y)
        )
          return;
        let vecX = v.x - u.x;
        let vecY = v.y - u.y;
        let vecLengthSqr = vecX * vecX + vecY * vecY;
        if (vecLengthSqr === 0) {
          vecLengthSqr = 1;
          const sign = i > j ? 1 : -1;
          vecX = 0.01 * sign;
          vecY = 0.01 * sign;
        }
        // 外围计算项 C 常数值
        const common = k2 / vecLengthSqr;
        displacements[i].x += vecX * common;
        displacements[i].y += vecY * common;
      });
    });
  }

  // 计算引力
  private calAttractive(edges: Edge[], displacements: Point[], k: number) {
    edges.forEach(e => {if (!e.source || !e.target) return;
      const uIndex = this.nodeIdxMap[e.source];
      const vIndex = this.nodeIdxMap[e.target];
      if (uIndex === vIndex) {return;}
      const u = this.nodeMap[e.source];
      const v = this.nodeMap[e.target];
      if (!isNumber(v.x) || !isNumber(u.x) || !isNumber(v.y) || !isNumber(u.y))
        return;
      const vecX = v.x - u.x;
      const vecY = v.y - u.y;
      const vecLength = Math.sqrt(vecX * vecX + vecY * vecY);
      const common = (vecLength * vecLength) / k;
      displacements[vIndex].x -= (vecX / vecLength) * common;
      displacements[vIndex].y -= (vecY / vecLength) * common;
      displacements[uIndex].x += (vecX / vecLength) * common;
      displacements[uIndex].y += (vecY / vecLength) * common;
    });
  }

  public getType() {return "fruchterman";}
}

Grid 布局算法

在 dom 中布局，咱们最常想到的就是网格布局，在最早的没有 div 的时代，都是通过 table 进行布局的，这里图的布局也是最容易想到的一种布局形式，尽管简略，但咱们也能够看一下对应的实现思路，咱们看一下在 Cytoscape 中的实现计划：

// grid 布局目录地位 https://github.com/cytoscape/cytoscape.js/blob/unstable/src/extensions/layout/grid.js

function GridLayout(options){this.options = util.extend( {}, defaults, options );
}

GridLayout.prototype.run = function(){
  let params = this.options;
  let options = params;

  let cy = params.cy;
  let eles = options.eles;
  let nodes = eles.nodes().not( ':parent');

  if(options.sort){nodes = nodes.sort( options.sort);
  }

  let bb = math.makeBoundingBox( options.boundingBox ? options.boundingBox : {x1: 0, y1: 0, w: cy.width(), h: cy.height()} );

  if(bb.h === 0 || bb.w === 0){eles.nodes().layoutPositions(this, options, function( ele){return { x: bb.x1, y: bb.y1};
    } );

  } else {

    // width/height * splits^2 = cells where splits is number of times to split width
    let cells = nodes.size();
    let splits = Math.sqrt(cells * bb.h / bb.w);
    let rows = Math.round(splits);
    let cols = Math.round(bb.w / bb.h * splits);

    let small = function(val){if( val == null){return Math.min( rows, cols);
      } else {let min = Math.min( rows, cols);
        if(min == rows){rows = val;} else {cols = val;}
      }
    };

    let large = function(val){if( val == null){return Math.max( rows, cols);
      } else {let max = Math.max( rows, cols);
        if(max == rows){rows = val;} else {cols = val;}
      }
    };

    let oRows = options.rows;
    let oCols = options.cols != null ? options.cols : options.columns;

    // if rows or columns were set in options, use those values
    if(oRows != null && oCols != null){
      rows = oRows;
      cols = oCols;
    } else if(oRows != null && oCols == null){
      rows = oRows;
      cols = Math.ceil(cells / rows);
    } else if(oRows == null && oCols != null){
      cols = oCols;
      rows = Math.ceil(cells / cols);
    }

    // otherwise use the automatic values and adjust accordingly

    // if rounding was up, see if we can reduce rows or columns
    else if(cols * rows > cells){let sm = small();
      let lg = large();

      // reducing the small side takes away the most cells, so try it first
      if((sm - 1) * lg >= cells ){small( sm - 1);
      } else if((lg - 1) * sm >= cells ){large( lg - 1);
      }
    } else {

      // if rounding was too low, add rows or columns
      while(cols * rows < cells){let sm = small();
        let lg = large();

        // try to add to larger side first (adds less in multiplication)
        if((lg + 1) * sm >= cells ){large( lg + 1);
        } else {small( sm + 1);
        }
      }
    }

    let cellWidth = bb.w / cols;
    let cellHeight = bb.h / rows;

    if(options.condense){
      cellWidth = 0;
      cellHeight = 0;
    }

    if(options.avoidOverlap){for( let i = 0; i < nodes.length; i++){let node = nodes[ i];
        let pos = node._private.position;

        if(pos.x == null || pos.y == null){ // for bb
          pos.x = 0;
          pos.y = 0;
        }

        let nbb = node.layoutDimensions(options);
        let p = options.avoidOverlapPadding;

        let w = nbb.w + p;
        let h = nbb.h + p;

        cellWidth = Math.max(cellWidth, w);
        cellHeight = Math.max(cellHeight, h);
      }
    }

    let cellUsed = {}; // e.g. 'c-0-2' => true

    let used = function(row, col){return cellUsed[ 'c-' + row + '-' + col] ? true : false;
    };

    let use = function(row, col){cellUsed[ 'c-' + row + '-' + col] = true;
    };

    // to keep track of current cell position
    let row = 0;
    let col = 0;
    let moveToNextCell = function(){
      col++;
      if(col >= cols){
        col = 0;
        row++;
      }
    };

    // get a cache of all the manual positions
    let id2manPos = {};
    for(let i = 0; i < nodes.length; i++){let node = nodes[ i];
      let rcPos = options.position(node);

      if(rcPos && (rcPos.row !== undefined || rcPos.col !== undefined) ){ // must have at least row or col def'd
        let pos = {
          row: rcPos.row,
          col: rcPos.col
        };

        if(pos.col === undefined){ // find unused col
          pos.col = 0;

          while(used( pos.row, pos.col) ){pos.col++;}
        } else if(pos.row === undefined){ // find unused row
          pos.row = 0;

          while(used( pos.row, pos.col) ){pos.row++;}
        }

        id2manPos[node.id() ] = pos;
        use(pos.row, pos.col);
      }
    }

    let getPos = function(element, i){
      let x, y;

      if(element.locked() || element.isParent()){return false;}

      // see if we have a manual position set
      let rcPos = id2manPos[element.id() ];
      if(rcPos){
        x = rcPos.col * cellWidth + cellWidth / 2 + bb.x1;
        y = rcPos.row * cellHeight + cellHeight / 2 + bb.y1;

      } else { // otherwise set automatically

        while(used( row, col) ){moveToNextCell();
        }

        x = col * cellWidth + cellWidth / 2 + bb.x1;
        y = row * cellHeight + cellHeight / 2 + bb.y1;
        use(row, col);

        moveToNextCell();}

      return {x: x, y: y};

    };

    nodes.layoutPositions(this, options, getPos);
  }

  return this; // chaining

};

export default GridLayout;

MDS 算法

MDS 是 Multidimensional Scaling 的简称，即为高维数据降维算法，其是一种力导算法高维数据下的稳固下布局的优化，防止数据超载而导致的整体的布局不稳固，上图中方程式通过数学推导化简后（ps：对于具体推导感兴趣的同学能够看这篇文章图布局算法之 Stress Majorization），其伪码形容如下：

接下来，咱们来看一下前端的具体实现，来看一下 Antv G6 中的实现计划：

/**
* Antv 的 layout 是专门公布了一个 npm 包 源码地址：https://github.com/antvis/layout
* MDS 算法目录地位 https://github.com/antvis/layout/blob/master/src/layout/mds.ts
*/

// ml-matrix 是机器学习相干的一些矩阵操作
import {Matrix as MLMatrix, SingularValueDecomposition} from "ml-matrix";
import {PointTuple, OutNode, Edge, Matrix, MDSLayoutOptions} from "./types";
import {floydWarshall, getAdjMatrix, scaleMatrix} from "../util";
import {Base} from "./base";

/**
 * mds 布局
 */
export class MDSLayout extends Base {
  /** 布局核心 */
  public center: PointTuple = [0, 0];

  /** 边长度 */
  public linkDistance: number = 50;

  private scaledDistances: Matrix[];

  public nodes: OutNode[] = [];

  public edges: Edge[] = [];

  /** 迭代完结的回调函数 */
  public onLayoutEnd: () => void = () => {};

  constructor(options?: MDSLayoutOptions) {super();
    this.updateCfg(options);
  }

  public getDefaultCfg() {
    return {center: [0, 0],
      linkDistance: 50
    };
  }

  /**
   * 执行布局
   */
  public execute() {
    const self = this;
    const {nodes, edges = [] } = self;
    const center = self.center;
    if (!nodes || nodes.length === 0) {if (self.onLayoutEnd) self.onLayoutEnd();
      return;
    }
    if (nodes.length === 1) {nodes[0].x = center[0];
      nodes[0].y = center[1];
      if (self.onLayoutEnd) self.onLayoutEnd();
      return;
    }
    const linkDistance = self.linkDistance;
    // the graph-theoretic distance (shortest path distance) matrix
    const adjMatrix = getAdjMatrix({nodes, edges}, false);
    const distances = floydWarshall(adjMatrix);
    self.handleInfinity(distances);

    // scale the ideal edge length acoording to linkDistance
    const scaledD = scaleMatrix(distances, linkDistance);
    self.scaledDistances = scaledD;

    // get positions by MDS
    const positions = self.runMDS();
    self.positions = positions;
    positions.forEach((p: number[], i: number) => {nodes[i].x = p[0] + center[0];
      nodes[i].y = p[1] + center[1];
    });

    if (self.onLayoutEnd) self.onLayoutEnd();

    return {
      nodes,
      edges
    };
  }

  /**
   * mds 算法
   * @return {array} positions 计算后的节点地位数组
   */
  public runMDS(): PointTuple[] {
    const self = this;
    const dimension = 2;
    const distances = self.scaledDistances;

    // square distances
    const M = MLMatrix.mul(MLMatrix.pow(distances, 2), -0.5);

    // double centre the rows/columns
    const rowMeans = M.mean("row");
    const colMeans = M.mean("column");
    const totalMean = M.mean();
    M.add(totalMean)
      .subRowVector(rowMeans)
      .subColumnVector(colMeans);

    // take the SVD of the double centred matrix, and return the
    // points from it
    const ret = new SingularValueDecomposition(M);
    const eigenValues = MLMatrix.sqrt(ret.diagonalMatrix).diagonal();
    return ret.leftSingularVectors.toJSON().map((row: number[]) => {return MLMatrix.mul([row], [eigenValues])
        .toJSON()[0]
        .splice(0, dimension) as PointTuple;
    });
  }

  public handleInfinity(distances: Matrix[]) {
    let maxDistance = -999999;
    distances.forEach(row => {
      row.forEach(value => {if (value === Infinity) {return;}
        if (maxDistance < value) {maxDistance = value;}
      });
    });
    distances.forEach((row, i) => {row.forEach((value, j) => {if (value === Infinity) {distances[i][j] = maxDistance;
        }
      });
    });
  }

  public getType() {return "mds";}
}

总结

可视化图布局是可视化畛域一个比拟精湛的方向，其设计了美学理念、机器学习、数据分析等相干常识，对于智能布局预测，能够联合机器学习等人工智能办法进行解决，业界常见的比方对于 OpenOrd 的一些大规模图布局的边切优化等，具体感兴趣的同学能够参看这篇文章 OpenOrd- 面向大规模图布局的开源算法 - 研读；对于前端智能化与可视化联合的方面，能够将 tensorflow 与可视化图布局进行拓展，具体能够看一下 G6 的图布局预测计划 G6 智能布局预测，其大略实现思路是借助 tensorflow，对于卷积层和池化层的解决以及相干操作。综上，可视化图布局畛域的拓展联合了前端智能化与前端数据可视化两大前端方向，由此可见，前端的七大倒退方向并非是割裂开来的，他们之间相互影响、互相借鉴，对于穿插畛域深入研究或者能有不同的启发！

参考

• Using layouts
• G6- 图布局
• G6 智能布局预测
• antv/vis-predict-engine 源码
• 图可视化之图布局
• OpenOrd- 面向大规模图布局的开源算法 - 研读
• 全栈之计算机根底系列 – 图布局算法与可视化
• 图可视化之图布局
• P 问题、NP 问题、NP 齐全问题和 NP 难问题
• 图布局算法之 Stress Majorization
• 关系网络图 (剖析 & 可视化) 的 13 个 JavaScript 库
• Graph Drawing by Force-directed Placement
• 深度学习 — 模拟退火算法详解（Simulated Annealing，SA）
• TensorFlow 学习（十七）：高级 API 之 tf.layers