浅析有向无环图DAG的Sugiyama层次布局
站长
· 阅读数 386
如何绘制一个美观且便于理解的有向无环图？本文以d3-dag实现为例，浅析Sugiyama层次布局算法
前言
如何绘制一个美观且便于理解的有向无环图（DAG）？对于有一定依赖关系的DAG而言，以下几个要点被广泛用于布局中。
- 布局均衡，节点均匀分布
- 边以直线为主
- 减少长边
- 减少边交叉
Sugiyama布局
基于以上的目标， Kozo Sugiyama 在1981年提出有层级结构关系的图布局算法，因此又被称为Sugiyama方法。
该布局方法主要分为以下三个步骤，每个步骤都可以有多种不同实现方式：
1. 节点分层 - Layering
根据边的方向将每个节点划分到不同层（rank），通过增加伪节点（dummy node）使得每条边仅连接相邻两层，每多一个伪节点意味着多一个可能导致边弯曲的点。
例如节点A在第1层，节点B在第3层同时有边 A->B，那么在第2层额外添加节点C，并修改边为 A->C->B
2. 减少边交叉 - Decorssing
这个步骤又叫做节点重排序，因为唯一影响边交叉的就是节点的次序，所以该步骤通过重新计算节点在当前层级的次序来减少边的交叉，通常是最耗时的一步。
3. 计算坐标 - Coordinate assignment
基于上面计算得到的层级和次序来计算真实节点的横坐标和纵坐标，尽量减少去除伪节点后边弯曲的程度，同时布局尽可能平衡。一般而言，节点的纵坐标可以直接基于层级和层高，因此该步骤的实现侧重于计算横坐标。
d3-dag中的实现
d3-dag是一个用于DAG操作和布局的d3插件库，内置了Sugiyama布局的一些简单实现。d3-dag将Sugiyama布局的三个步骤拆分为三个算子，分别是LayeringOperator，DecrossOperator和CoordOperator。
0. 数据结构
DagLink - 边
DAG中的边
interface DagLink<NodeDatum = unknown, LinkDatum = unknown> {
readonly source: DagNode<NodeDatum, LinkDatum>;
readonly target: DagNode<NodeDatum, LinkDatum>;
readonly data: LinkDatum;
readonly points: { readonly x: number; readonly y: number }[];
}
DagNode - 节点
DAG中的节点
interface DagNode<NodeDatum = unknown, LinkDatum = unknown>
extends Dag<NodeDatum, LinkDatum> {
readonly data: NodeDatum;
value?: number;
x?: number;
y?: number;
children(): DagNode<NodeDatum, LinkDatum>[];
childLinks(): DagLink<NodeDatum, LinkDatum>[];
}
Dag - 图
其中count() height() depth() 都是给每个节点初始化层级value。
- count：每个节点下面的叶子数，叶子节点为1。
- height：每个节点离叶子的最长距离，叶子节点为0。
- depth：每个节点离根节点的最长距离，根节点为0。
export type IterStyle = "depth" | "breadth" | "before" | "after";
interface Dag<NodeDatum = unknown, LinkDatum = unknown>
extends Iterable<DagNode<NodeDatum, LinkDatum>> {
roots(): DagNode<NodeDatum, LinkDatum>[];
/** 后代节点 */
descendants(style?: IterStyle): DagNode<NodeDatum, LinkDatum>[];
/** 所有边 */
links(): DagLink<NodeDatum, LinkDatum>[];
size(): number;
/** 计算节点和 */
sum(
callback: (node: DagNode<NodeDatum, LinkDatum>, index: number) => number
): this;
count(): this;
height(): this;
depth(): this;
/** 从根节点拆分DAG为多个连通的DAG */
split(): Dag<NodeDatum, LinkDatum>[];
/** DAG是否连通 */
connected(): boolean;
以下实现都假设输入已经为有向无环图
1. 节点分层
a. Longest Path - 最小化高度
其中一个简单实现就是节点的层级等于它的深度（到达它的最长路径）。
function longestPathCall(dag: Dag): void {
if (options.topDown) {
// 自上而下，最长路径将从顶部开始，将节点尽可能靠近顶部
dag.depth(); // 为每个节点分配层级，等于其距离根节点的最长距离(深度)。
} else {
// 自下而上
dag.height(); // 为每个节点分配层级，等于其距离叶子点的最长距离(高度)。
// 根节点的最高高度
const maxHeight = Math.max(...map(dag.iroots(), (d) => d.value));
for (const node of dag) {
node.value = maxHeight - node.value;
}
}
}
最长路径算法实现起来比较简单，处理速度非常快。但可能分层的结果会非常宽，节点容易挤到某一边，造成大量留白，效果一般。
自下而上
b. Coffman Graham - 限制宽度
Coffman Graham 算法最早是用于解决多核CPU任务调度（任务和任务的依赖也可以视作DAG），后来也被用于DAG绘制中的节点分层。其核心在于以下两个限制：
- 每层数量/宽度不超过www。
- 当前层节点的所有依赖必须在当前层上面。
该算法保证生成的DAG高度h满足 h≤(2−2w)hminh\leq(2- {2\over{w}})h_{min}h≤(2−w2)hmin， 其中hminh_{min}hmin为指定宽度www下分层的最小高度。
function coffmanGrahamCall(dag: Dag): void {
const maxWidth = options.width || Math.floor(Math.sqrt(dag.size() + 0.5));
// 创建优先队列，下一个节点为最近完成父节点次序最小的（最大化父子节点分配的次序差）
function comp(left: DagNode, right: DagNode): boolean {
const leftBefore = data.get(left).before;
const rightBefore = data.get(right).before;
for (const [i, leftb] of leftBefore.entries()) {
const rightb = rightBefore[i];
// leftb: left的父节点中最近分配的次序
// rightb: right的父节点中最近分配的次序
if (rightb === undefined) {
return false;
} else if (leftb < rightb) {
return true;
} else if (rightb < leftb) {
return false;
}
}
return true;
}
const queue = new FastPriorityQueue(comp);
// 从根节点开始
for (const root of dag.iroots()) {
queue.add(root);
}
let i = 0; // 分配的顺序
let layer = 0; // 当前分配的层级，从0开始，层级高的在下面
let width = 0; // 当前层宽度
let node;
while ((node = queue.poll())) {
if (
width < maxWidth &&
data.get(node).parents.every((p) => p.value < layer)
) {
// 当前层宽度 < 限宽 且 节点的所有父节点层级比当前层级低
// 添加节点到当前层
node.value = layer;
width++;
} else {
// 否则添加到新的下一层
node.value = ++layer;
width = 1;
}
for (const child of node.ichildren()) {
// 对于节点的每个直接子节点（有边），记录已经分配层级的父节点序号
const { before, parents } = data.get(child);
before.push(i);
// 当所有父节点已经分配层级后加入优先队列（拓扑序）
if (before.length === parents.length) {
before.sort((a, b) => b - a); // 从大到小排序，最近分配的在前
queue.add(child);
}
}
i++;
}
}
c. Simplex - 最小化边长
该方法通过最小化伪节点的数量来给节点分层，具体实现上和著名的网络单纯型法（**network simplex algorithm）**类似，因此又被称为Simplex Layering。 因为层级必须是整数，所以也是一个纯整数线性规划问题，最小化总边长fff就相当于最小化伪节点的数量
- rank(u)rank(u)rank(u) 为大于等于1的整数
- rank(u)−rank(v)≥1rank(u) - rank(v) \ge 1rank(u)−rank(v)≥1
- f=∑(u,v)∈E(rank(u)−rank(v)−1)f = \sum_{(u,v) \in E}(rank(u) - rank(v) - 1)f=∑(u,v)∈E(rank(u)−rank(v)−1)
在d3-dag中，作者引入了第三方库jsLPSolver来求解这个纯整数线性规划问题。
import { Constraint, Solve, SolverDict, Variable } from "javascript-lp-solver";
function simplexCall(dag: Dag<OpsNodeDatum<Ops>, OpsLinkDatum<Ops>>): void {
const variables: SolverDict<Variable> = {};
const ints: SolverDict<number> = {};
const constraints: SolverDict<Constraint> = {};
/** 获取节点ID */
function n(node: OpsDagNode<Ops>): string {
// ...
}
/** 获取节点的关联变量 */
function variable(node: OpsDagNode<Ops>): Variable {
// ...
}
/** 强制first节点在second节点之前
*
* @param prefix 确定描述约束的唯一前缀
* @param strict 严格在或可能相等之前
*/
function before(
prefix: string,
first: OpsDagNode<Ops>,
second: OpsDagNode<Ops>,
strict: boolean = true
): void {
const fvar = variable(first);
const svar = variable(second);
const cons = `${prefix}: ${n(first)} -> ${n(second)}`;
constraints[cons] = { min: +strict };
fvar[cons] = -1;
svar[cons] = 1;
}
// 初始化节点变量为子节点数量，且为整数变量
for (const node of dag) {
const nid = n(node);
ints[nid] = 1;
variables[nid] = {
opt: node.children.length
};
}
/** 可以插入自定义的排序或分组，这里省略相关逻辑 */
// 添加边限制
for (const link of dag.ilinks()) {
before("link", link.source, link.target);
++variable(link.source).opt;
--variable(link.target).opt;
}
// 解线性规划
const { feasible, ...assignment } = Solve.call(
{},
{
optimize: "opt",
opType: "max",
constraint,
variables,
ints
}
);
// lp solver 赋值
for (const node of dag) {
node.value = assignment[n(node)] || 0;
}
}
2. 减少边交叉
a. Two Layer - 两两比较
每两层进行排序来最小化交叉边，通常速度比较快，执行多次可以提升效果。
- bigrams：以二元形式遍历，[1, 2, 3,4 ] => [1, 2], [2, 3], [3, 4]
interface TwolayerOperator {(
topLayer: DagNode[],
bottomLayer: DagNode[],
topDown: boolean // 自顶向下，只重排序bottomLayer，topLayer不动，默认 true
): void
options = {}
function twoLayerCall(layers: OpSugiNode<O>[][]): void {
const reversed = layers.slice().reverse();
let changed = true;
for (let i = 0; i < options.passes && changed; ++i) {
changed = false;
// top down，每两层对下层排序
for (const [upper, bottom] of bigrams(layers)) {
const init = new Map(bottom.map((node, i) => [node, i] as const));
options.order(upper, bottom, true);
if (bottom.some((node, i) => init.get(node)) !== i) {
changed = true;
}
}
// bottom up，每两层对上层排序
for (const [lower, topl] of bigrams(reversed)) {
const init = new Map(topl.map((node, i) => [node, i] as const));
options.order(topl, lower, false);
if (topl.some((node, i) => init.get(node)) !== i) {
changed = true;
}
}
}
}
一个常用的order 启发式算子为aggregate，根据目标节点的父节点或子节点次序的值（例如平均数和中位数）来排序。在d3-dag中默认使用中位数排序。
class Median implements Aggregator {
private vals: number[] = [];
add(val: number): void {
this.vals.push(val);
}
val(): number | undefined {
return median(this.vals);
}
}
const medianFactory = (): Aggregator => new Median();
// 以下默认factory为medianFactory
function aggCall(
topLayer: DagNode[],
bottomLayer: DagNode[],
topDown: boolean
): void {
if (topDown) {
const incr = new Map(
bottomLayer.map((node) => [node, factory()] as const)
);
for (const [i, node] of topLayer.entries()) {
for (const child of node.ichildren()) {
// 每个下层节点汇总它所有父节点的当前次序
incr.get(child).add(i);
}
}
// 计算中位数作为当前层的最终次序
const aggs = new Map(
[...incr.entries()].map(([node, agg]) => [node, agg.val()] as const)
);
// 根据位置更新节点的次序
order(bottomLayer, aggs);
} else {
const inds = new Map(bottomLayer.map((node, i) => [node, i] as const));
const aggs = new Map(
topLayer.map((node) => {
// 每个上层节点汇总它所有子节点的当前次序
const agg = aggregate(
factory,
map(node.ichildren(), (child) => inds.get(child))
);
return [node, agg] as const;
})
);
order(topLayer, aggs);
}
3. 计算坐标
a. Center
根据节点大小留出间距后让每层节点居中对齐排列，耗时非常短。
function centerCall<N, L>(
layers: DagNode<N, L>[][],
nodeSize: CoordNodeSizeAccessor<N, L>
): number {
// 计算每层的总宽度
const widths = layers.map((layer) => {
let width = 0;
for (const node of layer) {
const nodeWidth = nodeSize(node);
node.x = width + nodeWidth / 2;
width += nodeWidth;
}
return width;
});
const maxWidth = Math.max(...widths);
if (maxWidth <= 0) {
throw new Error("must assign nonzero width to at least one node");
}
for (const [i, layer] of layers.entries()) {
const width = widths[i];
const offset = (maxWidth - width) / 2;
// 每个节点加上相对最宽层的偏移量
for (const node of layer) {
node.x = node.x + offset;
}
}
return maxWidth;
}
DAG绘制
因为d3-dag仅提供了DAG数据结构和布局的能力，没有限制绘制的方法，以下是用d3.js绘制SVG的简单例子：
import * as d3 from "d3";
import * as d3dag from "d3-dag";
const dag = d3dag.dagStratify()(data);
const layout = d3dag
.sugiyama()
.layering(d3dag.layeringCoffmanGraham())
.decross(d3dag.decrossTwoLayer())
.coord(d3dag.coordCenter())
.nodeSize((node) => [node ? 60 : 10, 60]); // 节点和伪节点的间距
const { width, height } = layout;
// 容器
const svg = d3.select("svg").attr("width", width).attr("height", height);
// 节点
const nodes = svg
.append("g")
.selectAll("g")
.data(dag.descendants())
.enter()
.append("g")
.attr("transform", ({ x, y }) => `translate(${x}, ${y})`);
// 形状
nodes.append("circle").attr("r", 20);
// 文本
nodes.append("text").text(({ data }) => data.id)
.attr("text-anchor", "middle")
.attr("alignment-baseline", "middle")
.attr("fill", "white");
// 边
const drawLine = d3.line().curve(d3.curveBasis).x((d) => d.x).y((d) => d.y);
svg.append("g").selectAll("path").data(dag.links())
.enter().append("path")
.attr("d", ({ points }) => drawLine(points))
.attr("fill", "none")
.attr("stroke", "grey")
.attr("stroke-width", 3)
总结
Sugiyama层次布局方法提供了基础的布局思路和框架。经过多年的发展，针对不同的需求，各个环节都有很多算法可以灵活应用。限于篇幅，本文没有介绍其他算法的实现，有兴趣的可以查看参考资料中AntV G6的文章。
参考资料
转载自:https://juejin.cn/post/7041805439918424101