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

前言

图算法在前端畛域考查的较少，个别除非是要写框架或者打包工具对依赖关系解决（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.jsfunction 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