echarts sankeyLayout 源码
echarts sankeyLayout 代码
文件路径：/src/chart/sankey/sankeyLayout.ts
/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*/
import * as layout from '../../util/layout';
import * as zrUtil from 'zrender/src/core/util';
import {groupData} from '../../util/model';
import ExtensionAPI from '../../core/ExtensionAPI';
import SankeySeriesModel, { SankeySeriesOption, SankeyNodeItemOption } from './SankeySeries';
import { GraphNode, GraphEdge } from '../../data/Graph';
import { LayoutOrient } from '../../util/types';
import GlobalModel from '../../model/Global';
export default function sankeyLayout(ecModel: GlobalModel, api: ExtensionAPI) {
ecModel.eachSeriesByType('sankey', function (seriesModel: SankeySeriesModel) {
const nodeWidth = seriesModel.get('nodeWidth');
const nodeGap = seriesModel.get('nodeGap');
const layoutInfo = getViewRect(seriesModel, api);
seriesModel.layoutInfo = layoutInfo;
const width = layoutInfo.width;
const height = layoutInfo.height;
const graph = seriesModel.getGraph();
const nodes = graph.nodes;
const edges = graph.edges;
computeNodeValues(nodes);
const filteredNodes = zrUtil.filter(nodes, function (node) {
return node.getLayout().value === 0;
});
const iterations = filteredNodes.length !== 0 ? 0 : seriesModel.get('layoutIterations');
const orient = seriesModel.get('orient');
const nodeAlign = seriesModel.get('nodeAlign');
layoutSankey(nodes, edges, nodeWidth, nodeGap, width, height, iterations, orient, nodeAlign);
});
}
/**
* Get the layout position of the whole view
*/
function getViewRect(seriesModel: SankeySeriesModel, api: ExtensionAPI) {
return layout.getLayoutRect(
seriesModel.getBoxLayoutParams(), {
width: api.getWidth(),
height: api.getHeight()
}
);
}
function layoutSankey(
nodes: GraphNode[],
edges: GraphEdge[],
nodeWidth: number,
nodeGap: number,
width: number,
height: number,
iterations: number,
orient: LayoutOrient,
nodeAlign: SankeySeriesOption['nodeAlign']
) {
computeNodeBreadths(nodes, edges, nodeWidth, width, height, orient, nodeAlign);
computeNodeDepths(nodes, edges, height, width, nodeGap, iterations, orient);
computeEdgeDepths(nodes, orient);
}
/**
* Compute the value of each node by summing the associated edge's value
*/
function computeNodeValues(nodes: GraphNode[]) {
zrUtil.each(nodes, function (node) {
const value1 = sum(node.outEdges, getEdgeValue);
const value2 = sum(node.inEdges, getEdgeValue);
const nodeRawValue = node.getValue() as number || 0;
const value = Math.max(value1, value2, nodeRawValue);
node.setLayout({value: value}, true);
});
}
/**
* Compute the x-position for each node.
*
* Here we use Kahn algorithm to detect cycle when we traverse
* the node to computer the initial x position.
*/
function computeNodeBreadths(
nodes: GraphNode[],
edges: GraphEdge[],
nodeWidth: number,
width: number,
height: number,
orient: LayoutOrient,
nodeAlign: SankeySeriesOption['nodeAlign']
) {
// Used to mark whether the edge is deleted. if it is deleted,
// the value is 0, otherwise it is 1.
const remainEdges = [];
// Storage each node's indegree.
const indegreeArr = [];
// Used to storage the node with indegree is equal to 0.
let zeroIndegrees: GraphNode[] = [];
let nextTargetNode: GraphNode[] = [];
let x = 0;
// let kx = 0;
for (let i = 0; i < edges.length; i++) {
remainEdges[i] = 1;
}
for (let i = 0; i < nodes.length; i++) {
indegreeArr[i] = nodes[i].inEdges.length;
if (indegreeArr[i] === 0) {
zeroIndegrees.push(nodes[i]);
}
}
let maxNodeDepth = -1;
// Traversing nodes using topological sorting to calculate the
// horizontal(if orient === 'horizontal') or vertical(if orient === 'vertical')
// position of the nodes.
while (zeroIndegrees.length) {
for (let idx = 0; idx < zeroIndegrees.length; idx++) {
const node = zeroIndegrees[idx];
const item = node.hostGraph.data.getRawDataItem(node.dataIndex) as SankeyNodeItemOption;
const isItemDepth = item.depth != null && item.depth >= 0;
if (isItemDepth && item.depth > maxNodeDepth) {
maxNodeDepth = item.depth;
}
node.setLayout({depth: isItemDepth ? item.depth : x}, true);
orient === 'vertical'
? node.setLayout({dy: nodeWidth}, true)
: node.setLayout({dx: nodeWidth}, true);
for (let edgeIdx = 0; edgeIdx < node.outEdges.length; edgeIdx++) {
const edge = node.outEdges[edgeIdx];
const indexEdge = edges.indexOf(edge);
remainEdges[indexEdge] = 0;
const targetNode = edge.node2;
const nodeIndex = nodes.indexOf(targetNode);
if (--indegreeArr[nodeIndex] === 0 && nextTargetNode.indexOf(targetNode) < 0) {
nextTargetNode.push(targetNode);
}
}
}
++x;
zeroIndegrees = nextTargetNode;
nextTargetNode = [];
}
for (let i = 0; i < remainEdges.length; i++) {
if (remainEdges[i] === 1) {
throw new Error('Sankey is a DAG, the original data has cycle!');
}
}
const maxDepth = maxNodeDepth > x - 1 ? maxNodeDepth : x - 1;
if (nodeAlign && nodeAlign !== 'left') {
adjustNodeWithNodeAlign(nodes, nodeAlign, orient, maxDepth);
}
const kx = orient === 'vertical'
? (height - nodeWidth) / maxDepth
: (width - nodeWidth) / maxDepth;
scaleNodeBreadths(nodes, kx, orient);
}
function isNodeDepth(node: GraphNode) {
const item = node.hostGraph.data.getRawDataItem(node.dataIndex) as SankeyNodeItemOption;
return item.depth != null && item.depth >= 0;
}
function adjustNodeWithNodeAlign(
nodes: GraphNode[],
nodeAlign: SankeySeriesOption['nodeAlign'],
orient: LayoutOrient,
maxDepth: number
) {
if (nodeAlign === 'right') {
let nextSourceNode: GraphNode[] = [];
let remainNodes = nodes;
let nodeHeight = 0;
while (remainNodes.length) {
for (let i = 0; i < remainNodes.length; i++) {
const node = remainNodes[i];
node.setLayout({skNodeHeight: nodeHeight}, true);
for (let j = 0; j < node.inEdges.length; j++) {
const edge = node.inEdges[j];
if (nextSourceNode.indexOf(edge.node1) < 0) {
nextSourceNode.push(edge.node1);
}
}
}
remainNodes = nextSourceNode;
nextSourceNode = [];
++nodeHeight;
}
zrUtil.each(nodes, function (node) {
if (!isNodeDepth(node)) {
node.setLayout({depth: Math.max(0, maxDepth - node.getLayout().skNodeHeight)}, true);
}
});
}
else if (nodeAlign === 'justify') {
moveSinksRight(nodes, maxDepth);
}
}
/**
* All the node without outEgdes are assigned maximum x-position and
* be aligned in the last column.
*
* @param nodes. node of sankey view.
* @param maxDepth. use to assign to node without outEdges as x-position.
*/
function moveSinksRight(nodes: GraphNode[], maxDepth: number) {
zrUtil.each(nodes, function (node) {
if (!isNodeDepth(node) && !node.outEdges.length) {
node.setLayout({depth: maxDepth}, true);
}
});
}
/**
* Scale node x-position to the width
*
* @param nodes node of sankey view
* @param kx multiple used to scale nodes
*/
function scaleNodeBreadths(nodes: GraphNode[], kx: number, orient: LayoutOrient) {
zrUtil.each(nodes, function (node) {
const nodeDepth = node.getLayout().depth * kx;
orient === 'vertical'
? node.setLayout({y: nodeDepth}, true)
: node.setLayout({x: nodeDepth}, true);
});
}
/**
* Using Gauss-Seidel iterations method to compute the node depth(y-position)
*
* @param nodes node of sankey view
* @param edges edge of sankey view
* @param height the whole height of the area to draw the view
* @param nodeGap the vertical distance between two nodes
* in the same column.
* @param iterations the number of iterations for the algorithm
*/
function computeNodeDepths(
nodes: GraphNode[],
edges: GraphEdge[],
height: number,
width: number,
nodeGap: number,
iterations: number,
orient: LayoutOrient
) {
const nodesByBreadth = prepareNodesByBreadth(nodes, orient);
initializeNodeDepth(nodesByBreadth, edges, height, width, nodeGap, orient);
resolveCollisions(nodesByBreadth, nodeGap, height, width, orient);
for (let alpha = 1; iterations > 0; iterations--) {
// 0.99 is a experience parameter, ensure that each iterations of
// changes as small as possible.
alpha *= 0.99;
relaxRightToLeft(nodesByBreadth, alpha, orient);
resolveCollisions(nodesByBreadth, nodeGap, height, width, orient);
relaxLeftToRight(nodesByBreadth, alpha, orient);
resolveCollisions(nodesByBreadth, nodeGap, height, width, orient);
}
}
function prepareNodesByBreadth(nodes: GraphNode[], orient: LayoutOrient) {
const nodesByBreadth: GraphNode[][] = [];
const keyAttr = orient === 'vertical' ? 'y' : 'x';
const groupResult = groupData(nodes, function (node) {
return node.getLayout()[keyAttr] as number;
});
groupResult.keys.sort(function (a, b) {
return a - b;
});
zrUtil.each(groupResult.keys, function (key) {
nodesByBreadth.push(groupResult.buckets.get(key));
});
return nodesByBreadth;
}
/**
* Compute the original y-position for each node
*/
function initializeNodeDepth(
nodesByBreadth: GraphNode[][],
edges: GraphEdge[],
height: number,
width: number,
nodeGap: number,
orient: LayoutOrient
) {
let minKy = Infinity;
zrUtil.each(nodesByBreadth, function (nodes) {
const n = nodes.length;
let sum = 0;
zrUtil.each(nodes, function (node) {
sum += node.getLayout().value;
});
const ky = orient === 'vertical'
? (width - (n - 1) * nodeGap) / sum
: (height - (n - 1) * nodeGap) / sum;
if (ky < minKy) {
minKy = ky;
}
});
zrUtil.each(nodesByBreadth, function (nodes) {
zrUtil.each(nodes, function (node, i) {
const nodeDy = node.getLayout().value * minKy;
if (orient === 'vertical') {
node.setLayout({x: i}, true);
node.setLayout({dx: nodeDy}, true);
}
else {
node.setLayout({y: i}, true);
node.setLayout({dy: nodeDy}, true);
}
});
});
zrUtil.each(edges, function (edge) {
const edgeDy = +edge.getValue() * minKy;
edge.setLayout({dy: edgeDy}, true);
});
}
/**
* Resolve the collision of initialized depth (y-position)
*/
function resolveCollisions(
nodesByBreadth: GraphNode[][],
nodeGap: number,
height: number,
width: number,
orient: LayoutOrient
) {
const keyAttr = orient === 'vertical' ? 'x' : 'y';
zrUtil.each(nodesByBreadth, function (nodes) {
nodes.sort(function (a, b) {
return a.getLayout()[keyAttr] - b.getLayout()[keyAttr];
});
let nodeX;
let node;
let dy;
let y0 = 0;
const n = nodes.length;
const nodeDyAttr = orient === 'vertical' ? 'dx' : 'dy';
for (let i = 0; i < n; i++) {
node = nodes[i];
dy = y0 - node.getLayout()[keyAttr];
if (dy > 0) {
nodeX = node.getLayout()[keyAttr] + dy;
orient === 'vertical'
? node.setLayout({x: nodeX}, true)
: node.setLayout({y: nodeX}, true);
}
y0 = node.getLayout()[keyAttr] + node.getLayout()[nodeDyAttr] + nodeGap;
}
const viewWidth = orient === 'vertical' ? width : height;
// If the bottommost node goes outside the bounds, push it back up
dy = y0 - nodeGap - viewWidth;
if (dy > 0) {
nodeX = node.getLayout()[keyAttr] - dy;
orient === 'vertical'
? node.setLayout({x: nodeX}, true)
: node.setLayout({y: nodeX}, true);
y0 = nodeX;
for (let i = n - 2; i >= 0; --i) {
node = nodes[i];
dy = node.getLayout()[keyAttr] + node.getLayout()[nodeDyAttr] + nodeGap - y0;
if (dy > 0) {
nodeX = node.getLayout()[keyAttr] - dy;
orient === 'vertical'
? node.setLayout({x: nodeX}, true)
: node.setLayout({y: nodeX}, true);
}
y0 = node.getLayout()[keyAttr];
}
}
});
}
/**
* Change the y-position of the nodes, except most the right side nodes
* @param nodesByBreadth
* @param alpha parameter used to adjust the nodes y-position
*/
function relaxRightToLeft(
nodesByBreadth: GraphNode[][],
alpha: number,
orient: LayoutOrient
) {
zrUtil.each(nodesByBreadth.slice().reverse(), function (nodes) {
zrUtil.each(nodes, function (node) {
if (node.outEdges.length) {
let y = sum(node.outEdges, weightedTarget, orient)
/ sum(node.outEdges, getEdgeValue);
if (isNaN(y)) {
const len = node.outEdges.length;
y = len ? sum(node.outEdges, centerTarget, orient) / len : 0;
}
if (orient === 'vertical') {
const nodeX = node.getLayout().x + (y - center(node, orient)) * alpha;
node.setLayout({x: nodeX}, true);
}
else {
const nodeY = node.getLayout().y + (y - center(node, orient)) * alpha;
node.setLayout({y: nodeY}, true);
}
}
});
});
}
function weightedTarget(edge: GraphEdge, orient: LayoutOrient) {
return center(edge.node2, orient) * (edge.getValue() as number);
}
function centerTarget(edge: GraphEdge, orient: LayoutOrient) {
return center(edge.node2, orient);
}
function weightedSource(edge: GraphEdge, orient: LayoutOrient) {
return center(edge.node1, orient) * (edge.getValue() as number);
}
function centerSource(edge: GraphEdge, orient: LayoutOrient) {
return center(edge.node1, orient);
}
function center(node: GraphNode, orient: LayoutOrient) {
return orient === 'vertical'
? node.getLayout().x + node.getLayout().dx / 2
: node.getLayout().y + node.getLayout().dy / 2;
}
function getEdgeValue(edge: GraphEdge) {
return edge.getValue() as number;
}
function sum<T>(array: T[], cb: (item: T, orient?: LayoutOrient) => number, orient?: LayoutOrient) {
let sum = 0;
const len = array.length;
let i = -1;
while (++i < len) {
const value = +cb(array[i], orient);
if (!isNaN(value)) {
sum += value;
}
}
return sum;
}
/**
* Change the y-position of the nodes, except most the left side nodes
*/
function relaxLeftToRight(nodesByBreadth: GraphNode[][], alpha: number, orient: LayoutOrient) {
zrUtil.each(nodesByBreadth, function (nodes) {
zrUtil.each(nodes, function (node) {
if (node.inEdges.length) {
let y = sum(node.inEdges, weightedSource, orient)
/ sum(node.inEdges, getEdgeValue);
if (isNaN(y)) {
const len = node.inEdges.length;
y = len ? sum(node.inEdges, centerSource, orient) / len : 0;
}
if (orient === 'vertical') {
const nodeX = node.getLayout().x + (y - center(node, orient)) * alpha;
node.setLayout({x: nodeX}, true);
}
else {
const nodeY = node.getLayout().y + (y - center(node, orient)) * alpha;
node.setLayout({y: nodeY}, true);
}
}
});
});
}
/**
* Compute the depth(y-position) of each edge
*/
function computeEdgeDepths(nodes: GraphNode[], orient: LayoutOrient) {
const keyAttr = orient === 'vertical' ? 'x' : 'y';
zrUtil.each(nodes, function (node) {
node.outEdges.sort(function (a, b) {
return a.node2.getLayout()[keyAttr] - b.node2.getLayout()[keyAttr];
});
node.inEdges.sort(function (a, b) {
return a.node1.getLayout()[keyAttr] - b.node1.getLayout()[keyAttr];
});
});
zrUtil.each(nodes, function (node) {
let sy = 0;
let ty = 0;
zrUtil.each(node.outEdges, function (edge) {
edge.setLayout({sy: sy}, true);
sy += edge.getLayout().dy;
});
zrUtil.each(node.inEdges, function (edge) {
edge.setLayout({ty: ty}, true);
ty += edge.getLayout().dy;
});
});
}
相关信息
相关文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
6、 golang
-
8、 openharmony