@antv/algorithm

--- package.json (entry) ---
{
  "name": "@antv/algorithm",
  "version": "0.1.26",
  "description": "graph algorithm",
  "keywords": [
    "graph",
    "algorithm",
    "antv",
    "G6"
  ],
  "files": [
    "package.json",
    "es",
    "lib",
    "dist",
    "LICENSE",
    "README.md"
  ],
  "main": "lib/index.js",
  "module": "es/index.js",
  "types": "lib/index.d.ts",
  "unpkg": "dist/index.min.js",
  "scripts": {
    "build": "npm run clean && father build && npm run build:umd",
    "build:umd": "webpack --config webpack.config.js --mode production",
    "dev:umd": "webpack --config webpack.dev.config.js --mode development",
    "ci": "npm run build && npm run coverage",
    "clean": "rimraf es lib dist",
    "coverage": "jest --coverage",
    "lint": "eslint --ext .js,.jsx,.ts,.tsx --format=pretty \"./\"",
    "lint:src": "eslint --ext .ts --format=pretty \"./src\"",
    "prettier": "prettier -c --write \"**/*\"",
    "test": "npm run build:umd && jest",
    "test-live": "npm run build:umd && DEBUG_MODE=1 jest --watch ./tests/unit/louvain-spec.ts",
    "test-live:async": "npm run build:umd && DEBUG_MODE=1 jest --watch ./tests/unit/louvain-async-spec.ts",
    "lint-staged:js": "eslint --ext .js,.jsx,.ts,.

--- index.js (entry) ---
"use strict";

function _typeof(obj) { "@babel/helpers - typeof"; return _typeof = "function" == typeof Symbol && "symbol" == typeof Symbol.iterator ? function (obj) { return typeof obj; } : function (obj) { return obj && "function" == typeof Symbol && obj.constructor === Symbol && obj !== Symbol.prototype ? "symbol" : typeof obj; }, _typeof(obj); }
Object.defineProperty(exports, "__esModule", {
  value: true
});
Object.defineProperty(exports, "GADDI", {
  enumerable: true,
  get: function get() {
    return _gaddi.default;
  }
});
Object.defineProperty(exports, "Stack", {
  enumerable: true,
  get: function get() {
    return _stack.default;
  }
});
Object.defineProperty(exports, "breadthFirstSearch", {
  enumerable: true,
  get: function get() {
    return _bfs.default;
  }
});
Object.defineProperty(exports, "connectedComponent", {
  enumerable: true,
  get: function get() {
    return _connectedComponent.default;
  }
});
Object.defineProperty(exports, "cosineSimilarity", {
  enumerable: true,
  get: function get() {
    return _cosineSimilarity.default;
  }
});
exports.default = void 0;
Object.defineProperty(exports, "depthFirstSearch", {
  enumerable: true,
  get: function get(

--- bundled output (OSV-MAL flagged — LLM scope expansion) ---

--- lib/adjacent-matrix.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = void 0;
var adjMatrix = function adjMatrix(graphData, directed) {
  var nodes = graphData.nodes,
    edges = graphData.edges;
  var matrix = [];
  // map node with index in data.nodes
  var nodeMap = {};
  if (!nodes) {
    throw new Error("invalid nodes data!");
  }
  if (nodes) {
    nodes.forEach(function (node, i) {
      nodeMap[node.id] = i;
      var row = [];
      matrix.push(row);
    });
  }
  if (edges) {
    edges.forEach(function (edge) {
      var source = edge.source,
        target = edge.target;
      var sIndex = nodeMap[source];
      var tIndex = nodeMap[target];
      if (!sIndex && sIndex !== 0 || !tIndex && tIndex !== 0) return;
      matrix[sIndex][tIndex] = 1;
      if (!directed) {
        matrix[tIndex][sIndex] = 1;
      }
    });
  }
  return matrix;
};
var _default = adjMatrix;
exports.default = _default;

--- lib/connected-component.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = getConnectedComponents;
exports.detectStrongConnectComponents = exports.detectConnectedComponents = void 0;
var _util = require("./util");
/**
 * Generate all connected components for an undirected graph
 * @param graph
 */
var detectConnectedComponents = function detectConnectedComponents(graphData) {
  var _a = graphData.nodes,
    nodes = _a === void 0 ? [] : _a,
    _b = graphData.edges,
    edges = _b === void 0 ? [] : _b;
  var allComponents = [];
  var visited = {};
  var nodeStack = [];
  var getComponent = function getComponent(node) {
    nodeStack.push(node);
    visited[node.id] = true;
    var neighbors = (0, _util.getNeighbors)(node.id, edges);
    var _loop_1 = function _loop_1(i) {
      var neighbor = neighbors[i];
      if (!visited[neighbor]) {
        var targetNode = nodes.filter(function (node) {
          return node.id === neighbor;
        });
        if (targetNode.length > 0) {
          getComponent(targetNode[0]);
        }
      }
    };
    for (var i = 0; i < neighbors.length; ++i) {
      _loop_1(i);
    }
  };
  for (var i = 0; i < nodes.length; i++) {
    var node = nodes[i];
    if (!visited[node.id]) {
      // 对于无向图进行dfs遍历，每一次调用后都得到一个连通分量
      getComponent(node);
      var component = [];
      while (nodeStack.length > 0) {
        component.push(nodeStack.pop());
      }
      allComponents.push(component);
    }
  }
  return allComponents;
};
/**
 * Tarjan's Algorithm 复杂度  O(|V|+|E|)
 * For directed graph only
 * a directed graph is said to be strongly connected if "every vertex is reachable from every other vertex".
 * refer: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 * @param graph
 * @return a list of strongly connected components
 */
exports.detectConnectedComponents = detectConnectedComponents;
var detectStrongConnectComponents = function detectStrongConnectComponents(graphData) {
  var

--- lib/cosine-similarity.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = void 0;
var _vector = _interopRequireDefault(require("./utils/vector"));
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
/**
 * cosine-similarity算法 计算余弦相似度
 * @param item 元素
 * @param targetItem 目标元素
 */
var cosineSimilarity = function cosineSimilarity(item, targetItem) {
  // 目标元素向量
  var targetItemVector = new _vector.default(targetItem);
  // 目标元素向量的模长
  var targetNodeNorm2 = targetItemVector.norm2();
  // 元素向量
  var itemVector = new _vector.default(item);
  // 元素向量的模长
  var itemNorm2 = itemVector.norm2();
  // 计算元素向量和目标元素向量的点积
  var dot = targetItemVector.dot(itemVector);
  var norm2Product = targetNodeNorm2 * itemNorm2;
  // 计算元素向量和目标元素向量的余弦相似度
  var cosineSimilarity = norm2Product ? dot / norm2Product : 0;
  return cosineSimilarity;
};
var _default = cosineSimilarity;
exports.default = _default;

--- lib/i-louvain.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = void 0;
var _louvain = _interopRequireDefault(require("./louvain"));
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
/**
 * 社区发现 i-louvain 算法：模块度 + 惯性模块度（即节点属性相似性）
 * @param graphData 图数据
 * @param directed 是否有向图，默认为 false
 * @param weightPropertyName 权重的属性字段
 * @param threshold 差值阈值
 * @param propertyKey 属性的字段名
 * @param involvedKeys 参与计算的key集合
 * @param uninvolvedKeys 不参与计算的key集合
 * @param inertialWeight 惯性模块度权重
 */
var iLouvain = function iLouvain(graphData, directed, weightPropertyName, threshold, propertyKey, involvedKeys, uninvolvedKeys, inertialWeight) {
  if (directed === void 0) {
    directed = false;
  }
  if (weightPropertyName === void 0) {
    weightPropertyName = 'weight';
  }
  if (threshold === void 0) {
    threshold = 0.0001;
  }
  if (propertyKey === void 0) {
    propertyKey = undefined;
  }
  if (involvedKeys === void 0) {
    involvedKeys = [];
  }
  if (uninvolvedKeys === void 0) {
    uninvolvedKeys = ['id'];
  }
  if (inertialWeight === void 0) {
    inertialWeight = 1;
  }
  return (0, _louvain.default)(graphData, directed, weightPropertyName, threshold, true, propertyKey, involvedKeys, uninvolvedKeys, inertialWeight);
};
var _default = iLouvain;
exports.default = _default;

--- lib/label-propagation.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = void 0;
var _adjacentMatrix = _interopRequireDefault(require("./adjacent-matrix"));
var _util = require("./util");
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
/**
 * 标签传播算法
 * @param graphData 图数据
 * @param directed 是否有向图，默认为 false
 * @param weightPropertyName 权重的属性字段
 * @param maxIteration 最大迭代次数
 */
var labelPropagation = function labelPropagation(graphData, directed, weightPropertyName, maxIteration) {
  if (directed === void 0) {
    directed = false;
  }
  if (weightPropertyName === void 0) {
    weightPropertyName = 'weight';
  }
  if (maxIteration === void 0) {
    maxIteration = 1000;
  }
  // the origin data
  var _a = graphData.nodes,
    nodes = _a === void 0 ? [] : _a,
    _b = graphData.edges,
    edges = _b === void 0 ? [] : _b;
  var clusters = {};
  var nodeMap = {};
  // init the clusters and nodeMap
  nodes.forEach(function (node, i) {
    var cid = (0, _util.uniqueId)();
    node.clusterId = cid;
    clusters[cid] = {
      id: cid,
      nodes: [node]
    };
    nodeMap[node.id] = {
      node: node,
      idx: i
    };
  });
  // the adjacent matrix of calNodes inside clusters
  var adjMatrix = (0, _adjacentMatrix.default)(graphData, directed);
  // the sum of each row in adjacent matrix
  var ks = [];
  /**
   * neighbor nodes (id for key and weight for value) for each node
   * neighbors = {
   *  id(node_id): { id(neighbor_1_id): weight(weight of the edge), id(neighbor_2_id): weight(weight of the edge), ... },
   *  ...
   * }
   */
  var neighbors = {};
  adjMatrix.forEach(function (row, i) {
    var k = 0;
    var iid = nodes[i].id;
    neighbors[iid] = {};
    row.forEach(function (entry, j) {
      if (!entry) return;
      k += entry;
      var jid = nodes[j].id;
      neighbors[iid][jid] = entry;
    });
    ks.push(k);
  });
  var iter = 0;
  var _loop_1 = function _loop_1() {
    var cha

--- lib/nodes-cosine-similarity.js (bundled) ---
"use strict";

Object.defineProperty(exports, "__esModule", {
  value: true
});
exports.default = void 0;
var _util = require("@antv/util");
var _nodeProperties = require("./utils/node-properties");
var _dataPreprocessing = require("./utils/data-preprocessing");
var _cosineSimilarity = _interopRequireDefault(require("./cosine-similarity"));
function _interopRequireDefault(obj) { return obj && obj.__esModule ? obj : { default: obj }; }
/**
 *  nodes-cosine-similarity算法 基于节