text: /*
  * 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 {__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 == null ? ('' + dataIndex) : ('' + id);
  
      var nodesMap = this._nodesMap;
  
      if (nodesMap[generateNodeKey(id)]) {
          if (__DEV__) {
              console.error('Graph nodes have duplicate name or 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;
  