text: 'use strict';
  /**
   * Graph data structure
   *
   * @module echarts/data/Graph
   * @author Yi Shen(https://www.github.com/pissang)
   */
  
  
      var zrUtil = require('zrender/lib/core/util');
  
      /**
       * @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[id]) {
              return;
          }
  
          var node = new Node(id, dataIndex);
          node.hostGraph = this;
  
          this.nodes.push(node);
  
          nodesMap[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[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 (!(n1 instanceof Node)) {
              n1 = nodesMap[n1];
          }
          if (!(n2 instanceof Node)) {
              n2 = nodesMap[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 (n1 instanceof Node) {
              n1 = n1.id;
          }
          if (n2 instanceof Node) {
              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 (!(startNode instanceof Node)) {
              startNode = this._nodesMap[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(otherNode, 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;
  
      module.exports = Graph;
  