可视化图布局算法浅析

前言

图算法在前端领域考察的较少，一般除非是要写框架或者打包工具对依赖关系处理（DAG）会用到，前端对图算法的考察一般是比较少的，而对于可视化领域而言，图又是必不可少的一种展示方式，其中对于边和节点的展示布局方案结合美学效果会有不同的算法实现，本文旨在介绍一些常见的通用布局算法，其中的每个小的布局方案也会有不同的分支实现

分类

简写	算法名称	分类	备注
grid	网格布局算法	几何布局
circle	环形布局算法	几何布局
concentric	同心圆布局算法	几何布局
radial	辐射状布局算法	几何布局
avsdf	邻接点最小度优先算法（Adjacent Vertex with Smallest Degree First）	几何布局
dagre	有向无环图树布局算法（Directed Acyclic Graph and Trees）	层级布局
breadthfirst	广度优先布局算法	层级布局
elk	Eclipse布局算法（Eclipse Layout Kernel）	层级布局
klay	K层布局算法（K Lay）	层级布局
fcose	最快复合弹簧内置布局算法（Fast Compound Spring Embedder）	力导布局
cola	约束布局（Constraint-based Layout）	力导布局
cise	环形弹簧内置布局算法（Circular Spring Embedder）	力导布局
elk2	Eclipse布局算法（Eclipse Layout Kernel）	力导布局
euler	欧拉布局算法	力导布局
spread	扩展布局算法	力导布局
fruchterman	Fruchterman-Reingold布局算法	力导布局
combo	混合布局算法	力导布局
mds	高维数据降维布局算法（Multi Dimensional Scaling）	其他布局算法
random	随机布局算法	其他布局

常见算法

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