Rollup 如何封装自己的工具库详解之DAG 有向图判断是否有环

介绍

Rollup 是一个 JavaScript 模块打包器，可以将小块代码编译成大块复杂的代码，例如 library 或应用程序。Rollup 对代码模块使用新的标准化格式，这些标准都包含在 JavaScript 的 ES6 版本中，而不是以前的特殊解决方案，如 CommonJS 和 AMD。ES6 模块可以使你自由、无缝地使用你最喜爱的 library 中那些最有用独立函数，而你的项目不必携带其他未使用的代码。ES6 模块最终还是要由浏览器原生实现，但当前 Rollup 可以使你提前体验。

官网

https://www.rollupjs.com/guide/introduction

首先利用 rollup 提供的 demo 代码仓创建项目

rollup-starter-lib 和 rollup-starter-app 中那些使用 Rollup 的示例类库与应用项目

这里我们采用的是 rollup-starter-lib 类库仓库开发，它仅仅是一个基础的配置，如果我们开发工具库代码有 es6 新特性。还需要安装对应的模块支持 babel 转换。

npm i -D @babel/core @babel/preset-env

npm i -D @babel/plugin-transform-runtime rollup-plugin-babel

• .babelrc 配置

{
  "presets": [
    [
      "@babel/env", {
        "modules": false,
        "targets": {
          "browsers": ["> 1%", "last 2 versions", "not ie <= 8"]
        },
        "useBuiltIns": "usage",
        "corejs": 2
      }
    ]
  ],
  "plugins": [
    [
      "@babel/plugin-transform-runtime",
      {
        "corejs": 2
      }
    ]
  ]
}

• rollup.config.js 配置

import babel from 'rollup-plugin-babel';

export default [
    plugins: [
      babel({
        runtimeHelpers: true,
        exclude: ['node_modules/**']
      })
    ],
  }
];

• 完整配置

import resolve from '@rollup/plugin-node-resolve';
import commonjs from '@rollup/plugin-commonjs';
import babel from 'rollup-plugin-babel';
import pkg from './package.json';

export default [
  // browser-friendly UMD build
  {
    input: 'src/main.js',
    output: {
      name: 'dagUtils',
      file: pkg.browser,
      format: 'umd', // 支持浏览器 script 引入方式的格式输出
    },
    plugins: [
      resolve(), // so Rollup can find `ms`
      commonjs(), // so Rollup can convert `ms` to an ES module
      babel({
        runtimeHelpers: true,
        exclude: ['node_modules/**']
      })
    ],
  },

  // CommonJS (for Node) and ES module (for bundlers) build.
  // (We could have three entries in the configuration array
  // instead of two, but it's quicker to generate multiple
  // builds from a single configuration where possible, using
  // an array for the `output` option, where we can specify
  // `file` and `format` for each target)
  {
    input: 'src/main.js',
    output: [
      { file: pkg.main, format: 'cjs' }, // 支持 require 引入方式的格式输出
      { file: pkg.module, format: 'es' }, // 支持 es6 import 引入方式的格式输出
    ],
  }
];

下面我们来封闭一个 DAG 有向图判断是否有环的工具库

• 工具方法源代码

1、深度优先遍历该图，如果在遍历的过程中，发现某个节点有一条边指向已经访问过的节点，则判断为有环

class DFS {
  constructor() {
    this.isDAG = true;
    this.graph = {};
    this.visited = {};
  }

  // 是否有环
  isLoop(edges) {
    let result = false
    let nodes = [];
    edges.forEach(item => {
      const { source, target } = item;
      nodes.push(source);
      nodes.push(target);
    });
    nodes = [...new Set(nodes)];
    this._init(nodes, edges);

    // 保证每个节点都遍历到，排除有的结点没有边的情况
    for (let i = 0; i < nodes.length; i++) {
      // 该节点被访问过，跳过它
      if (this.visited[nodes[i]] === -1) {
        continue;
      }

      this._DFS(i, nodes);
      if (!this.isDAG) {
        result = true
        break;
      }
    }

    return result
  }

  _init(nodes, edges) {
    for (let i = 0; i < nodes.length; i++) {
      const pre = nodes[i];
      this.graph[pre] = {};
      for (let j = 0; j < nodes.length; j++) {
        const next = nodes[j];
        this.graph[pre][next] = 0;
      }
    }
    for (let k = 0; k < edges.length; k++) {
      const edge = edges[k];
      this.graph[edge.source][edge.target] = -1;
    }

    for (let i = 0; i < nodes.length; i++) {
      this.visited[nodes[i]] = 0; // 初始数据，表示一开始所有顶点都未被访问过
    }
  }

  _DFS(i, nodes) {
    // 设置结点 i 变为访问过的状态
    this.visited[nodes[i]] = 1;
    for (let j = 0, len = nodes.length; j < len; j++) {
      // 如果当前结点有指向的结点
      if (this.graph[nodes[i]][nodes[j]] !== 0) {
        // 并且已经被访问过
        if (this.visited[nodes[j]] === 1) {
          this.isDAG = false; // 有环
          break;
        } else if (this.visited[nodes[j]] === -1) {
          continue; // 当前结点后边的结点都被访问过，直接跳至下一个结点
        } else {
          this._DFS(j, nodes)
        }
      }
    }
    // 遍历过所有相连的结点后，把本节点标记为 -1
    this.visited[nodes[i]] = -1;
  }
}

export default DFS;

2、拓扑排序

class Topology {
  constructor() {
    this.list = [];
    this.queue = [];
    this.indegree = {};
  }

  // 是否有环
  isLoop(edges) {
    const nodeLen = this._init(edges);
    Object.keys(this.indegree).forEach(id => {
      if (this.indegree[id] === 0) {
        this.queue.push(id);
      }
    });
    
    let count = 0;
    while (this.queue.length) {
      ++count;
      const currentNode = this.queue.pop();
      const nodeTargets = this.list[currentNode];
      for (let i = 0; i < nodeTargets.length; i++) {
        const target = nodeTargets[i];
        this.indegree[target] -= 1;
        if (this.indegree[target] === 0) {
          this.queue.push(target);
        }
      }
    }

    return count < nodeLen
  }

  _init(edges) {
    let nodes = [];
    edges.forEach(item => {
      const { source, target } = item;
      nodes.push(source);
      nodes.push(target);
      this._addEdge(source, target);
    });
    nodes = [...new Set(nodes)];
    nodes.forEach(node => {
      if (!this.indegree[node]) this.indegree[node] = 0;
      if (!this.list[node]) this.list[node] = [];
    })

    return nodes.length;
  }

  _addEdge(source, target) {
    if (!this.list[source]) this.list[source] = [];
    if (!this.indegree[target]) this.indegree[target] = 0;
    this.list[source].push(target);
    this.indegree[target] += 1;
  }
}

export default Topology;

github 源码地址