/*
|
* 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 zrUtil from 'zrender/src/core/util';
|
import { Dictionary } from 'zrender/src/core/types';
|
import List from './List';
|
import Model from '../model/Model';
|
import Element from 'zrender/src/Element';
|
import { DimensionLoose, ParsedValue } from '../util/types';
|
|
// id may be function name of Object, add a prefix to avoid this problem.
|
function generateNodeKey(id: string): string {
|
return '_EC_' + id;
|
}
|
|
class Graph {
|
type: 'graph' = 'graph';
|
|
readonly nodes: GraphNode[] = [];
|
|
readonly edges: GraphEdge[] = [];
|
|
data: List;
|
|
edgeData: List;
|
|
/**
|
* Whether directed graph.
|
*/
|
private _directed: boolean;
|
|
private _nodesMap: Dictionary<GraphNode> = {};
|
/**
|
* @type {Object.<string, module:echarts/data/Graph.Edge>}
|
* @private
|
*/
|
private _edgesMap: Dictionary<GraphEdge> = {};
|
|
|
constructor(directed?: boolean) {
|
this._directed = directed || false;
|
}
|
|
/**
|
* If is directed graph
|
*/
|
isDirected(): boolean {
|
return this._directed;
|
};
|
|
/**
|
* Add a new node
|
*/
|
addNode(id: string | number, dataIndex?: number): GraphNode {
|
id = id == null ? ('' + dataIndex) : ('' + id);
|
|
const nodesMap = this._nodesMap;
|
|
if (nodesMap[generateNodeKey(id)]) {
|
if (__DEV__) {
|
console.error('Graph nodes have duplicate name or id');
|
}
|
return;
|
}
|
|
const node = new GraphNode(id, dataIndex);
|
node.hostGraph = this;
|
|
this.nodes.push(node);
|
|
nodesMap[generateNodeKey(id)] = node;
|
return node;
|
};
|
|
/**
|
* Get node by data index
|
*/
|
getNodeByIndex(dataIndex: number): GraphNode {
|
const rawIdx = this.data.getRawIndex(dataIndex);
|
return this.nodes[rawIdx];
|
};
|
/**
|
* Get node by id
|
*/
|
getNodeById(id: string): GraphNode {
|
return this._nodesMap[generateNodeKey(id)];
|
};
|
|
/**
|
* Add a new edge
|
*/
|
addEdge(n1: GraphNode | number | string, n2: GraphNode | number | string, dataIndex?: number) {
|
const nodesMap = this._nodesMap;
|
const edgesMap = this._edgesMap;
|
|
// PNEDING
|
if (typeof n1 === 'number') {
|
n1 = this.nodes[n1];
|
}
|
if (typeof n2 === 'number') {
|
n2 = this.nodes[n2];
|
}
|
|
if (!(n1 instanceof GraphNode)) {
|
n1 = nodesMap[generateNodeKey(n1)];
|
}
|
if (!(n2 instanceof GraphNode)) {
|
n2 = nodesMap[generateNodeKey(n2)];
|
}
|
if (!n1 || !n2) {
|
return;
|
}
|
|
const key = n1.id + '-' + n2.id;
|
|
const edge = new GraphEdge(n1, n2, dataIndex);
|
edge.hostGraph = this;
|
|
if (this._directed) {
|
n1.outEdges.push(edge);
|
n2.inEdges.push(edge);
|
}
|
n1.edges.push(edge);
|
if (n1 !== n2) {
|
n2.edges.push(edge);
|
}
|
|
this.edges.push(edge);
|
edgesMap[key] = edge;
|
|
return edge;
|
};
|
|
/**
|
* Get edge by data index
|
*/
|
getEdgeByIndex(dataIndex: number): GraphEdge {
|
const rawIdx = this.edgeData.getRawIndex(dataIndex);
|
return this.edges[rawIdx];
|
};
|
/**
|
* Get edge by two linked nodes
|
*/
|
getEdge(n1: string | GraphNode, n2: string | GraphNode): GraphEdge {
|
if (n1 instanceof GraphNode) {
|
n1 = n1.id;
|
}
|
if (n2 instanceof GraphNode) {
|
n2 = n2.id;
|
}
|
|
const edgesMap = this._edgesMap;
|
|
if (this._directed) {
|
return edgesMap[n1 + '-' + n2];
|
}
|
else {
|
return edgesMap[n1 + '-' + n2]
|
|| edgesMap[n2 + '-' + n1];
|
}
|
};
|
|
/**
|
* Iterate all nodes
|
*/
|
eachNode<Ctx>(
|
cb: (this: Ctx, node: GraphNode, idx: number) => void,
|
context?: Ctx
|
) {
|
const nodes = this.nodes;
|
const len = nodes.length;
|
for (let i = 0; i < len; i++) {
|
if (nodes[i].dataIndex >= 0) {
|
cb.call(context, nodes[i], i);
|
}
|
}
|
};
|
|
/**
|
* Iterate all edges
|
*/
|
eachEdge<Ctx>(
|
cb: (this: Ctx, edge: GraphEdge, idx: number) => void,
|
context?: Ctx
|
) {
|
const edges = this.edges;
|
const len = edges.length;
|
for (let i = 0; i < len; i++) {
|
if (edges[i].dataIndex >= 0
|
&& edges[i].node1.dataIndex >= 0
|
&& edges[i].node2.dataIndex >= 0
|
) {
|
cb.call(context, edges[i], i);
|
}
|
}
|
};
|
|
/**
|
* Breadth first traverse
|
* Return true to stop traversing
|
*/
|
breadthFirstTraverse<Ctx>(
|
cb: (this: Ctx, node: GraphNode, fromNode: GraphNode) => boolean | void,
|
startNode: GraphNode | string,
|
direction: 'none' | 'in' | 'out',
|
context?: Ctx
|
) {
|
if (!(startNode instanceof GraphNode)) {
|
startNode = this._nodesMap[generateNodeKey(startNode)];
|
}
|
if (!startNode) {
|
return;
|
}
|
|
const edgeType: 'inEdges' | 'outEdges' | 'edges' = direction === 'out'
|
? 'outEdges' : (direction === 'in' ? 'inEdges' : 'edges');
|
|
for (let i = 0; i < this.nodes.length; i++) {
|
this.nodes[i].__visited = false;
|
}
|
|
if (cb.call(context, startNode, null)) {
|
return;
|
}
|
|
const queue = [startNode];
|
while (queue.length) {
|
const currentNode = queue.shift();
|
const edges = currentNode[edgeType];
|
|
for (let i = 0; i < edges.length; i++) {
|
const e = edges[i];
|
const otherNode = e.node1 === currentNode
|
? e.node2 : e.node1;
|
if (!otherNode.__visited) {
|
if (cb.call(context, otherNode, currentNode)) {
|
// Stop traversing
|
return;
|
}
|
queue.push(otherNode);
|
otherNode.__visited = true;
|
}
|
}
|
}
|
};
|
|
// TODO
|
// depthFirstTraverse(
|
// cb, startNode, direction, context
|
// ) {
|
|
// };
|
|
// Filter update
|
update() {
|
const data = this.data;
|
const edgeData = this.edgeData;
|
const nodes = this.nodes;
|
const edges = this.edges;
|
|
for (let i = 0, len = nodes.length; i < len; i++) {
|
nodes[i].dataIndex = -1;
|
}
|
for (let i = 0, len = data.count(); i < len; i++) {
|
nodes[data.getRawIndex(i)].dataIndex = i;
|
}
|
|
edgeData.filterSelf(function (idx) {
|
const edge = edges[edgeData.getRawIndex(idx)];
|
return edge.node1.dataIndex >= 0 && edge.node2.dataIndex >= 0;
|
});
|
|
// Update edge
|
for (let i = 0, len = edges.length; i < len; i++) {
|
edges[i].dataIndex = -1;
|
}
|
for (let i = 0, len = edgeData.count(); i < len; i++) {
|
edges[edgeData.getRawIndex(i)].dataIndex = i;
|
}
|
};
|
|
/**
|
* @return {module:echarts/data/Graph}
|
*/
|
clone() {
|
const graph = new Graph(this._directed);
|
const nodes = this.nodes;
|
const edges = this.edges;
|
for (let i = 0; i < nodes.length; i++) {
|
graph.addNode(nodes[i].id, nodes[i].dataIndex);
|
}
|
for (let i = 0; i < edges.length; i++) {
|
const e = edges[i];
|
graph.addEdge(e.node1.id, e.node2.id, e.dataIndex);
|
}
|
return graph;
|
};
|
|
|
}
|
|
|
class GraphNode {
|
|
id: string;
|
|
inEdges: GraphEdge[] = [];
|
|
outEdges: GraphEdge[] = [];
|
|
edges: GraphEdge[] = [];
|
|
hostGraph: Graph;
|
|
dataIndex: number = -1;
|
|
// Used in traverse of Graph
|
__visited: boolean;
|
|
constructor(id?: string, dataIndex?: number) {
|
this.id = id == null ? '' : id;
|
this.dataIndex = dataIndex == null ? -1 : dataIndex;
|
}
|
|
/**
|
* @return {number}
|
*/
|
degree() {
|
return this.edges.length;
|
}
|
|
/**
|
* @return {number}
|
*/
|
inDegree() {
|
return this.inEdges.length;
|
}
|
|
/**
|
* @return {number}
|
*/
|
outDegree() {
|
return this.outEdges.length;
|
}
|
|
// TODO: TYPE Same type with Model#getModel
|
getModel<T = unknown>(): Model<T>
|
getModel<T = unknown, S extends keyof T= keyof T>(path: S): Model<T[S]>
|
getModel<T = unknown>(path?: string): Model {
|
if (this.dataIndex < 0) {
|
return;
|
}
|
const graph = this.hostGraph;
|
const itemModel = graph.data.getItemModel<T>(this.dataIndex);
|
|
return itemModel.getModel(path as any);
|
}
|
|
getAdjacentDataIndices(): {node: number[], edge: number[]} {
|
const dataIndices = {
|
edge: [] as number[],
|
node: [] as number[]
|
};
|
for (let i = 0; i < this.edges.length; i++) {
|
const adjacentEdge = this.edges[i];
|
if (adjacentEdge.dataIndex < 0) {
|
continue;
|
}
|
dataIndices.edge.push(adjacentEdge.dataIndex);
|
dataIndices.node.push(adjacentEdge.node1.dataIndex, adjacentEdge.node2.dataIndex);
|
}
|
return dataIndices;
|
}
|
}
|
|
|
class GraphEdge {
|
/**
|
* The first node. If directed graph, it represents the source node.
|
*/
|
node1: GraphNode;
|
/**
|
* The second node. If directed graph, it represents the target node.
|
*/
|
node2: GraphNode;
|
|
dataIndex: number = -1;
|
|
hostGraph: Graph;
|
|
constructor(n1: GraphNode, n2: GraphNode, dataIndex?: number) {
|
this.node1 = n1;
|
this.node2 = n2;
|
this.dataIndex = dataIndex == null ? -1 : dataIndex;
|
}
|
|
getModel<T = unknown>(): Model<T>
|
getModel<T = unknown, S extends keyof T= keyof T>(path: S): Model<T[S]>
|
getModel<T = unknown>(path?: string): Model {
|
if (this.dataIndex < 0) {
|
return;
|
}
|
const graph = this.hostGraph;
|
const itemModel = graph.edgeData.getItemModel(this.dataIndex);
|
|
return itemModel.getModel(path as any);
|
}
|
|
getAdjacentDataIndices(): {node: number[], edge: number[]} {
|
return {
|
edge: [this.dataIndex],
|
node: [this.node1.dataIndex, this.node2.dataIndex]
|
};
|
}
|
}
|
|
type GetDataName<Host> = Host extends GraphEdge ? 'edgeData' : 'data';
|
|
interface GraphDataProxyMixin {
|
getValue(dimension?: DimensionLoose): ParsedValue;
|
// TODO: TYPE stricter type.
|
setVisual(key: string | Dictionary<any>, value?: any): void;
|
|
getVisual(key: string): any,
|
|
setLayout(layout: any, merge?: boolean): void;
|
|
getLayout(): any
|
|
getGraphicEl(): Element
|
|
getRawIndex(): number
|
}
|
|
function createGraphDataProxyMixin<Host extends GraphEdge | GraphNode>(
|
hostName: 'hostGraph',
|
dataName: GetDataName<Host>
|
): GraphDataProxyMixin {
|
return {
|
/**
|
* @param Default 'value'. can be 'a', 'b', 'c', 'd', 'e'.
|
*/
|
getValue(this: Host, dimension?: DimensionLoose): ParsedValue {
|
const data = this[hostName][dataName];
|
return data.get(data.getDimension(dimension || 'value'), this.dataIndex);
|
},
|
// TODO: TYPE stricter type.
|
setVisual(this: Host, key: string | Dictionary<any>, value?: any) {
|
this.dataIndex >= 0
|
&& this[hostName][dataName].setItemVisual(this.dataIndex, key as any, value);
|
},
|
|
getVisual(this: Host, key: string) {
|
return this[hostName][dataName].getItemVisual(this.dataIndex, key as any);
|
},
|
|
setLayout(this: Host, layout: any, merge?: boolean) {
|
this.dataIndex >= 0
|
&& this[hostName][dataName].setItemLayout(this.dataIndex, layout, merge);
|
},
|
|
getLayout(this: Host) {
|
return this[hostName][dataName].getItemLayout(this.dataIndex);
|
},
|
|
getGraphicEl(this: Host): Element {
|
return this[hostName][dataName].getItemGraphicEl(this.dataIndex);
|
},
|
|
getRawIndex(this: Host) {
|
return this[hostName][dataName].getRawIndex(this.dataIndex);
|
}
|
};
|
};
|
|
|
interface GraphEdge extends GraphDataProxyMixin {};
|
interface GraphNode extends GraphDataProxyMixin {};
|
|
zrUtil.mixin(GraphNode, createGraphDataProxyMixin('hostGraph', 'data'));
|
zrUtil.mixin(GraphEdge, createGraphDataProxyMixin('hostGraph', 'edgeData'));
|
|
export default Graph;
|
|
export {GraphNode, GraphEdge};
|
