{"version":3,"file":"circle.js","sourceRoot":"","sources":["../../../src/plots/sankey/circle.ts"],"names":[],"mappings":";;;AAAA,mCAAqC;AAGrC;;GAEG;AACH,SAAgB,QAAQ,CAAC,KAAW,EAAE,WAAmB,EAAE,WAAmB;IAC5E,IAAM,KAAK,GAAG,EAAE,CAAC;IACjB,KAAK,CAAC,OAAO,CAAC,UAAC,CAAC;QACd,IAAM,MAAM,GAAG,CAAC,CAAC,WAAW,CAAW,CAAC;QACxC,IAAM,MAAM,GAAG,CAAC,CAAC,WAAW,CAAW,CAAC;QACxC,IAAI,CAAC,KAAK,CAAC,QAAQ,CAAC,MAAM,CAAC,EAAE;YAC3B,KAAK,CAAC,IAAI,CAAC,MAAM,CAAC,CAAC;SACpB;QACD,IAAI,CAAC,KAAK,CAAC,QAAQ,CAAC,MAAM,CAAC,EAAE;YAC3B,KAAK,CAAC,IAAI,CAAC,MAAM,CAAC,CAAC;SACpB;IACH,CAAC,CAAC,CAAC;IACH,OAAO,KAAK,CAAC;AACf,CAAC;AAbD,4BAaC;AAED;;GAEG;AACH,SAAgB,SAAS,CACvB,KAAW,EACX,KAAe,EACf,WAAmB,EACnB,WAAmB;IAEnB,IAAM,WAAW,GAAG,EAAE,CAAC;IAEvB,KAAK,CAAC,OAAO,CAAC,UAAC,GAAG;QAChB,WAAW,CAAC,GAAG,CAAC,GAAG,EAAE,CAAC;QACtB,KAAK,CAAC,OAAO,CAAC,UAAC,IAAI;YACjB,WAAW,CAAC,GAAG,CAAC,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC;QAC7B,CAAC,CAAC,CAAC;IACL,CAAC,CAAC,CAAC;IAEH,KAAK,CAAC,OAAO,CAAC,UAAC,IAAI;QACjB,WAAW,CAAC,IAAI,CAAC,WAAW,CAAC,CAAC,CAAC,IAAI,CAAC,WAAW,CAAC,CAAC,GAAG,CAAC,CAAC;IACxD,CAAC,CAAC,CAAC;IAEH,OAAO,WAAW,CAAC;AACrB,CAAC;AApBD,8BAoBC;AAED;;;;;GAKG;AACH,SAAgB,YAAY,CAAC,KAAW,EAAE,WAAmB,EAAE,WAAmB;IAChF,IAAI,CAAC,IAAA,cAAO,EAAC,KAAK,CAAC;QAAE,OAAO,EAAE,CAAC;IAE/B,WAAW;IACX,IAAM,WAAW,GAAG,EAAE,CAAC;IAEvB,UAAU;IACV,IAAM,KAAK,GAAG,QAAQ,CAAC,KAAK,EAAE,WAAW,EAAE,WAAW,CAAC,CAAC;IACxD,cAAc;IACd,IAAM,WAAW,GAAG,SAAS,CAAC,KAAK,EAAE,KAAK,EAAE,WAAW,EAAE,WAAW,CAAC,CAAC;IAEtE,wCAAwC;IACxC,IAAM,OAAO,GAAG,EAAE,CAAC;IACnB,aAAa;IACb,KAAK,CAAC,OAAO,CAAC,UAAC,IAAI;QACjB,OAAO,CAAC,IAAI,CAAC,GAAG,CAAC,CAAC;IACpB,CAAC,CAAC,CAAC;IAEH,WAAW;IACX,SAAS,GAAG,CAAC,OAAO;QAClB,aAAa;QACb,OAAO,CAAC,OAAO,CAAC,GAAG,CAAC,CAAC;QACrB,KAAK,CAAC,OAAO,CAAC,UAAC,IAAI;YACjB,IAAI,WAAW,CAAC,OAAO,CAAC,CAAC,IAAI,CAAC,IAAI,CAAC,EAAE;gBACnC,qCAAqC;gBACrC,IAAI,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,EAAE;oBACtB,gBAAgB;oBAChB,WAAW,CAAC,IAAI,CAAC,UAAG,OAAO,cAAI,IAAI,CAAE,CAAC,CAAC;iBACxC;qBAAM,IAAI,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,EAAE;oBAC9B,4BAA4B;oBAC5B,OAAO;iBACR;qBAAM;oBACL,GAAG,CAAC,IAAI,CAAC,CAAC,CAAC,SAAS;iBACrB;aACF;QACH,CAAC,CAAC,CAAC;QACH,uBAAuB;QACvB,OAAO,CAAC,OAAO,CAAC,GAAG,CAAC,CAAC,CAAC;IACxB,CAAC;IAED,iBAAiB;IACjB,KAAK,CAAC,OAAO,CAAC,UAAC,IAAI;QACjB,oBAAoB;QACpB,IAAI,OAAO,CAAC,IAAI,CAAC,IAAI,CAAC,CAAC,EAAE;YACvB,OAAO;SACR;QACD,GAAG,CAAC,IAAI,CAAC,CAAC;IACZ,CAAC,CAAC,CAAC;IAEH,IAAI,WAAW,CAAC,MAAM,KAAK,CAAC,EAAE;QAC5B,OAAO,CAAC,IAAI,CAAC,uCAAgC,WAAW,CAAC,MAAM,sBAAmB,EAAE,WAAW,CAAC,CAAC;KAClG;IAED,eAAe;IACf,OAAO,KAAK,CAAC,MAAM,CAAC,UAAC,IAAI,IAAK,OAAA,WAAW,CAAC,SAAS,CAAC,UAAC,CAAC,IAAK,OAAA,CAAC,KAAK,UAAG,IAAI,CAAC,WAAW,CAAC,cAAI,IAAI,CAAC,WAAW,CAAC,CAAE,EAAjD,CAAiD,CAAC,GAAG,CAAC,EAAnF,CAAmF,CAAC,CAAC;AACrH,CAAC;AAvDD,oCAuDC","sourcesContent":["import { isArray } from '@antv/util';\nimport { Data } from '../../types';\n\n/**\n * 根据 edges 获取对应的 node 结构\n */\nexport function getNodes(edges: Data, sourceField: string, targetField: string): string[] {\n  const nodes = [];\n  edges.forEach((e) => {\n    const source = e[sourceField] as string;\n    const target = e[targetField] as string;\n    if (!nodes.includes(source)) {\n      nodes.push(source);\n    }\n    if (!nodes.includes(target)) {\n      nodes.push(target);\n    }\n  });\n  return nodes;\n}\n\n/**\n * 根据 edges 获取对应的 dfs 邻接矩阵\n */\nexport function getMatrix(\n  edges: Data,\n  nodes: string[],\n  sourceField: string,\n  targetField: string\n): Record<string, Record<string, number>> {\n  const graphMatrix = {};\n\n  nodes.forEach((pre) => {\n    graphMatrix[pre] = {};\n    nodes.forEach((next) => {\n      graphMatrix[pre][next] = 0;\n    });\n  });\n\n  edges.forEach((edge) => {\n    graphMatrix[edge[sourceField]][edge[targetField]] = 1;\n  });\n\n  return graphMatrix;\n}\n\n/**\n * 使用 DFS 思路切断桑基图数据中的环（会丢失数据），保证顺序\n * @param data\n * @param sourceField\n * @param targetField\n */\nexport function cutoffCircle(edges: Data, sourceField: string, targetField: string): Data {\n  if (!isArray(edges)) return [];\n\n  // 待删除的环状结构\n  const removedData = [];\n\n  // 获取所有的节点\n  const nodes = getNodes(edges, sourceField, targetField);\n  // 获取节点与边的邻接矩阵\n  const graphMatrix = getMatrix(edges, nodes, sourceField, targetField);\n\n  // visited：标记节点访问状态, 0：未访问,1：访问中, -1：已访问\n  const visited = {};\n  // 初始化visited\n  nodes.forEach((node) => {\n    visited[node] = 0;\n  });\n\n  // 图的深度遍历函数\n  function DFS(dfsNode) {\n    // 节点状态置为正在访问\n    visited[dfsNode] = 1;\n    nodes.forEach((node) => {\n      if (graphMatrix[dfsNode][node] != 0) {\n        // 当前节点在访问中，再次被访问，证明有环，移动到 removeData\n        if (visited[node] == 1) {\n          // 拼接为字符串，方便最后过滤\n          removedData.push(`${dfsNode}_${node}`);\n        } else if (visited[node] == -1) {\n          // 当前结点及后边的结点都被访问过，直接跳至下一个结点\n          return;\n        } else {\n          DFS(node); // 否则递归访问\n        }\n      }\n    });\n    //遍历过所有相连的结点后，把本节点标记为-1\n    visited[dfsNode] = -1;\n  }\n\n  // 对每个节点执行 dfs 操作\n  nodes.forEach((node) => {\n    //该结点后边的结点都被访问过了，跳过它\n    if (visited[node] == -1) {\n      return;\n    }\n    DFS(node);\n  });\n\n  if (removedData.length !== 0) {\n    console.warn(`sankey data contains circle, ${removedData.length} records removed.`, removedData);\n  }\n\n  // 过滤 remove 路径\n  return edges.filter((edge) => removedData.findIndex((i) => i === `${edge[sourceField]}_${edge[targetField]}`) < 0);\n}\n"]}