| /* |
| * 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. |
| */ |
| |
| /** |
| * Graph data structure |
| * |
| * @module echarts/data/Graph |
| * @author Yi Shen(https://www.github.com/pissang) |
| */ |
| import { __DEV__ } from '../config'; |
| import * as zrUtil from 'zrender/src/core/util'; |
| import { enableClassCheck } from '../util/clazz'; // id may be function name of Object, add a prefix to avoid this problem. |
| |
| function generateNodeKey(id) { |
| return '_EC_' + id; |
| } |
| /** |
| * @alias module:echarts/data/Graph |
| * @constructor |
| * @param {boolean} directed |
| */ |
| |
| |
| var Graph = function (directed) { |
| /** |
| * 是否是有向图 |
| * @type {boolean} |
| * @private |
| */ |
| this._directed = directed || false; |
| /** |
| * @type {Array.<module:echarts/data/Graph.Node>} |
| * @readOnly |
| */ |
| |
| this.nodes = []; |
| /** |
| * @type {Array.<module:echarts/data/Graph.Edge>} |
| * @readOnly |
| */ |
| |
| this.edges = []; |
| /** |
| * @type {Object.<string, module:echarts/data/Graph.Node>} |
| * @private |
| */ |
| |
| this._nodesMap = {}; |
| /** |
| * @type {Object.<string, module:echarts/data/Graph.Edge>} |
| * @private |
| */ |
| |
| this._edgesMap = {}; |
| /** |
| * @type {module:echarts/data/List} |
| * @readOnly |
| */ |
| |
| this.data; |
| /** |
| * @type {module:echarts/data/List} |
| * @readOnly |
| */ |
| |
| this.edgeData; |
| }; |
| |
| var graphProto = Graph.prototype; |
| /** |
| * @type {string} |
| */ |
| |
| graphProto.type = 'graph'; |
| /** |
| * If is directed graph |
| * @return {boolean} |
| */ |
| |
| graphProto.isDirected = function () { |
| return this._directed; |
| }; |
| /** |
| * Add a new node |
| * @param {string} id |
| * @param {number} [dataIndex] |
| */ |
| |
| |
| graphProto.addNode = function (id, dataIndex) { |
| id = id || '' + dataIndex; |
| var nodesMap = this._nodesMap; |
| |
| if (nodesMap[generateNodeKey(id)]) { |
| return; |
| } |
| |
| var node = new Node(id, dataIndex); |
| node.hostGraph = this; |
| this.nodes.push(node); |
| nodesMap[generateNodeKey(id)] = node; |
| return node; |
| }; |
| /** |
| * Get node by data index |
| * @param {number} dataIndex |
| * @return {module:echarts/data/Graph~Node} |
| */ |
| |
| |
| graphProto.getNodeByIndex = function (dataIndex) { |
| var rawIdx = this.data.getRawIndex(dataIndex); |
| return this.nodes[rawIdx]; |
| }; |
| /** |
| * Get node by id |
| * @param {string} id |
| * @return {module:echarts/data/Graph.Node} |
| */ |
| |
| |
| graphProto.getNodeById = function (id) { |
| return this._nodesMap[generateNodeKey(id)]; |
| }; |
| /** |
| * Add a new edge |
| * @param {number|string|module:echarts/data/Graph.Node} n1 |
| * @param {number|string|module:echarts/data/Graph.Node} n2 |
| * @param {number} [dataIndex=-1] |
| * @return {module:echarts/data/Graph.Edge} |
| */ |
| |
| |
| graphProto.addEdge = function (n1, n2, dataIndex) { |
| var nodesMap = this._nodesMap; |
| var edgesMap = this._edgesMap; // PNEDING |
| |
| if (typeof n1 === 'number') { |
| n1 = this.nodes[n1]; |
| } |
| |
| if (typeof n2 === 'number') { |
| n2 = this.nodes[n2]; |
| } |
| |
| if (!Node.isInstance(n1)) { |
| n1 = nodesMap[generateNodeKey(n1)]; |
| } |
| |
| if (!Node.isInstance(n2)) { |
| n2 = nodesMap[generateNodeKey(n2)]; |
| } |
| |
| if (!n1 || !n2) { |
| return; |
| } |
| |
| var key = n1.id + '-' + n2.id; // PENDING |
| |
| if (edgesMap[key]) { |
| return; |
| } |
| |
| var edge = new Edge(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 |
| * @param {number} dataIndex |
| * @return {module:echarts/data/Graph~Node} |
| */ |
| |
| |
| graphProto.getEdgeByIndex = function (dataIndex) { |
| var rawIdx = this.edgeData.getRawIndex(dataIndex); |
| return this.edges[rawIdx]; |
| }; |
| /** |
| * Get edge by two linked nodes |
| * @param {module:echarts/data/Graph.Node|string} n1 |
| * @param {module:echarts/data/Graph.Node|string} n2 |
| * @return {module:echarts/data/Graph.Edge} |
| */ |
| |
| |
| graphProto.getEdge = function (n1, n2) { |
| if (Node.isInstance(n1)) { |
| n1 = n1.id; |
| } |
| |
| if (Node.isInstance(n2)) { |
| n2 = n2.id; |
| } |
| |
| var edgesMap = this._edgesMap; |
| |
| if (this._directed) { |
| return edgesMap[n1 + '-' + n2]; |
| } else { |
| return edgesMap[n1 + '-' + n2] || edgesMap[n2 + '-' + n1]; |
| } |
| }; |
| /** |
| * Iterate all nodes |
| * @param {Function} cb |
| * @param {*} [context] |
| */ |
| |
| |
| graphProto.eachNode = function (cb, context) { |
| var nodes = this.nodes; |
| var len = nodes.length; |
| |
| for (var i = 0; i < len; i++) { |
| if (nodes[i].dataIndex >= 0) { |
| cb.call(context, nodes[i], i); |
| } |
| } |
| }; |
| /** |
| * Iterate all edges |
| * @param {Function} cb |
| * @param {*} [context] |
| */ |
| |
| |
| graphProto.eachEdge = function (cb, context) { |
| var edges = this.edges; |
| var len = edges.length; |
| |
| for (var 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 |
| * @param {Function} cb |
| * @param {module:echarts/data/Graph.Node} startNode |
| * @param {string} [direction='none'] 'none'|'in'|'out' |
| * @param {*} [context] |
| */ |
| |
| |
| graphProto.breadthFirstTraverse = function (cb, startNode, direction, context) { |
| if (!Node.isInstance(startNode)) { |
| startNode = this._nodesMap[generateNodeKey(startNode)]; |
| } |
| |
| if (!startNode) { |
| return; |
| } |
| |
| var edgeType = direction === 'out' ? 'outEdges' : direction === 'in' ? 'inEdges' : 'edges'; |
| |
| for (var i = 0; i < this.nodes.length; i++) { |
| this.nodes[i].__visited = false; |
| } |
| |
| if (cb.call(context, startNode, null)) { |
| return; |
| } |
| |
| var queue = [startNode]; |
| |
| while (queue.length) { |
| var currentNode = queue.shift(); |
| var edges = currentNode[edgeType]; |
| |
| for (var i = 0; i < edges.length; i++) { |
| var e = edges[i]; |
| var 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 |
| // graphProto.depthFirstTraverse = function ( |
| // cb, startNode, direction, context |
| // ) { |
| // }; |
| // Filter update |
| |
| |
| graphProto.update = function () { |
| var data = this.data; |
| var edgeData = this.edgeData; |
| var nodes = this.nodes; |
| var edges = this.edges; |
| |
| for (var i = 0, len = nodes.length; i < len; i++) { |
| nodes[i].dataIndex = -1; |
| } |
| |
| for (var i = 0, len = data.count(); i < len; i++) { |
| nodes[data.getRawIndex(i)].dataIndex = i; |
| } |
| |
| edgeData.filterSelf(function (idx) { |
| var edge = edges[edgeData.getRawIndex(idx)]; |
| return edge.node1.dataIndex >= 0 && edge.node2.dataIndex >= 0; |
| }); // Update edge |
| |
| for (var i = 0, len = edges.length; i < len; i++) { |
| edges[i].dataIndex = -1; |
| } |
| |
| for (var i = 0, len = edgeData.count(); i < len; i++) { |
| edges[edgeData.getRawIndex(i)].dataIndex = i; |
| } |
| }; |
| /** |
| * @return {module:echarts/data/Graph} |
| */ |
| |
| |
| graphProto.clone = function () { |
| var graph = new Graph(this._directed); |
| var nodes = this.nodes; |
| var edges = this.edges; |
| |
| for (var i = 0; i < nodes.length; i++) { |
| graph.addNode(nodes[i].id, nodes[i].dataIndex); |
| } |
| |
| for (var i = 0; i < edges.length; i++) { |
| var e = edges[i]; |
| graph.addEdge(e.node1.id, e.node2.id, e.dataIndex); |
| } |
| |
| return graph; |
| }; |
| /** |
| * @alias module:echarts/data/Graph.Node |
| */ |
| |
| |
| function Node(id, dataIndex) { |
| /** |
| * @type {string} |
| */ |
| this.id = id == null ? '' : id; |
| /** |
| * @type {Array.<module:echarts/data/Graph.Edge>} |
| */ |
| |
| this.inEdges = []; |
| /** |
| * @type {Array.<module:echarts/data/Graph.Edge>} |
| */ |
| |
| this.outEdges = []; |
| /** |
| * @type {Array.<module:echarts/data/Graph.Edge>} |
| */ |
| |
| this.edges = []; |
| /** |
| * @type {module:echarts/data/Graph} |
| */ |
| |
| this.hostGraph; |
| /** |
| * @type {number} |
| */ |
| |
| this.dataIndex = dataIndex == null ? -1 : dataIndex; |
| } |
| |
| Node.prototype = { |
| constructor: Node, |
| |
| /** |
| * @return {number} |
| */ |
| degree: function () { |
| return this.edges.length; |
| }, |
| |
| /** |
| * @return {number} |
| */ |
| inDegree: function () { |
| return this.inEdges.length; |
| }, |
| |
| /** |
| * @return {number} |
| */ |
| outDegree: function () { |
| return this.outEdges.length; |
| }, |
| |
| /** |
| * @param {string} [path] |
| * @return {module:echarts/model/Model} |
| */ |
| getModel: function (path) { |
| if (this.dataIndex < 0) { |
| return; |
| } |
| |
| var graph = this.hostGraph; |
| var itemModel = graph.data.getItemModel(this.dataIndex); |
| return itemModel.getModel(path); |
| } |
| }; |
| /** |
| * 图边 |
| * @alias module:echarts/data/Graph.Edge |
| * @param {module:echarts/data/Graph.Node} n1 |
| * @param {module:echarts/data/Graph.Node} n2 |
| * @param {number} [dataIndex=-1] |
| */ |
| |
| function Edge(n1, n2, dataIndex) { |
| /** |
| * 节点1,如果是有向图则为源节点 |
| * @type {module:echarts/data/Graph.Node} |
| */ |
| this.node1 = n1; |
| /** |
| * 节点2,如果是有向图则为目标节点 |
| * @type {module:echarts/data/Graph.Node} |
| */ |
| |
| this.node2 = n2; |
| this.dataIndex = dataIndex == null ? -1 : dataIndex; |
| } |
| /** |
| * @param {string} [path] |
| * @return {module:echarts/model/Model} |
| */ |
| |
| |
| Edge.prototype.getModel = function (path) { |
| if (this.dataIndex < 0) { |
| return; |
| } |
| |
| var graph = this.hostGraph; |
| var itemModel = graph.edgeData.getItemModel(this.dataIndex); |
| return itemModel.getModel(path); |
| }; |
| |
| var createGraphDataProxyMixin = function (hostName, dataName) { |
| return { |
| /** |
| * @param {string=} [dimension='value'] Default 'value'. can be 'a', 'b', 'c', 'd', 'e'. |
| * @return {number} |
| */ |
| getValue: function (dimension) { |
| var data = this[hostName][dataName]; |
| return data.get(data.getDimension(dimension || 'value'), this.dataIndex); |
| }, |
| |
| /** |
| * @param {Object|string} key |
| * @param {*} [value] |
| */ |
| setVisual: function (key, value) { |
| this.dataIndex >= 0 && this[hostName][dataName].setItemVisual(this.dataIndex, key, value); |
| }, |
| |
| /** |
| * @param {string} key |
| * @return {boolean} |
| */ |
| getVisual: function (key, ignoreParent) { |
| return this[hostName][dataName].getItemVisual(this.dataIndex, key, ignoreParent); |
| }, |
| |
| /** |
| * @param {Object} layout |
| * @return {boolean} [merge=false] |
| */ |
| setLayout: function (layout, merge) { |
| this.dataIndex >= 0 && this[hostName][dataName].setItemLayout(this.dataIndex, layout, merge); |
| }, |
| |
| /** |
| * @return {Object} |
| */ |
| getLayout: function () { |
| return this[hostName][dataName].getItemLayout(this.dataIndex); |
| }, |
| |
| /** |
| * @return {module:zrender/Element} |
| */ |
| getGraphicEl: function () { |
| return this[hostName][dataName].getItemGraphicEl(this.dataIndex); |
| }, |
| |
| /** |
| * @return {number} |
| */ |
| getRawIndex: function () { |
| return this[hostName][dataName].getRawIndex(this.dataIndex); |
| } |
| }; |
| }; |
| |
| zrUtil.mixin(Node, createGraphDataProxyMixin('hostGraph', 'data')); |
| zrUtil.mixin(Edge, createGraphDataProxyMixin('hostGraph', 'edgeData')); |
| Graph.Node = Node; |
| Graph.Edge = Edge; |
| enableClassCheck(Node); |
| enableClassCheck(Edge); |
| export default Graph; |