如何友好打印含嵌套Set的Graph对象？解决JSON.stringify栈溢出问题

问题背景 #

现有如下图结构代码：

class Node {
  constructor(value) {
    this.value = value;
    this.adjacents = new Set();
  }

  addAdjacent(node) {
    this.adjacents.add(node);
  }
}

class Graph {
  constructor(directed = false) {
    this.nodes = new Map();
    this.directed = directed;
  }

  addVertex(value) {
    const node = this.nodes.has(value);
    if (node) {
      return this.nodes.get(value);
    }

    const vertex = new Node(value);
    this.nodes.set(value, vertex);
    return vertex;
  }

  addEdge(src, dest) {
    let srcNode = this.nodes.get(src);
    if (!srcNode) {
      srcNode = this.addVertex(src);
    }

    let destNode = this.nodes.get(dest);
    if (!destNode) {
      destNode = this.addVertex(dest);
    }

    srcNode.addAdjacent(destNode);
    if (this.directed === false) {
      destNode.addAdjacent(srcNode);
    }
  }
}

const g1 = new Graph();
g1.addVertex("a");
g1.addVertex("b");
g1.addEdge("a", "c");

直接用console.log(g1)时，邻接节点信息无法展开查看：

Graph {
  nodes: Map(3) {
    'a' => Node { value: 'a', adjacents: [Set] },
    'b' => Node { value: 'b', adjacents: Set(0) {} },
    'c' => Node { value: 'c', adjacents: [Set] }
  },
  directed: false
}

尝试用JSON.stringify的replacer转换时，因为节点间循环引用（a和c互相引用），触发栈溢出：

console.log(
  JSON.stringify(
    Object.fromEntries(g1.nodes),
    (_key, value) =>
      value.adjacents instanceof Set ? [...value.adjacents] : value,
    2
  )
);

错误信息：

JSON.stringify(
       ^

RangeError: Maximum call stack size exceeded
    at JSON.stringify (<anonymous>)

解决方案 #

方法1：给Node类添加toJSON方法 #

通过自定义toJSON，让序列化时只输出邻接节点的value，避免循环引用：

class Node {
  constructor(value) {
    this.value = value;
    this.adjacents = new Set();
  }

  addAdjacent(node) {
    this.adjacents.add(node);
  }

  // 自定义序列化逻辑
  toJSON() {
    return {
      value: this.value,
      adjacents: [...this.adjacents].map(node => node.value)
    };
  }
}

之后直接序列化即可得到清晰输出：

console.log(JSON.stringify(Object.fromEntries(g1.nodes), null, 2));

输出结果：

{
  "a": {
    "value": "a",
    "adjacents": [
      "c"
    ]
  },
  "b": {
    "value": "b",
    "adjacents": []
  },
  "c": {
    "value": "c",
    "adjacents": [
      "a"
    ]
  }
}

方法2：改进replacer函数，跟踪已访问节点 #

如果不想修改类定义，可以在replacer里用WeakSet跟踪已处理的节点，避免循环递归：

const visited = new WeakSet();
console.log(
  JSON.stringify(Object.fromEntries(g1.nodes), (key, value) => {
    if (value instanceof Node) {
      if (visited.has(value)) {
        // 已访问过的节点，只返回value避免循环
        return value.value;
      }
      visited.add(value);
      return {
        value: value.value,
        adjacents: [...value.adjacents].map(n => n.value)
      };
    }
    return value;
  }, 2)
);

同样能得到和方法1一致的友好输出。

方法3：手动遍历生成打印对象 #

直接遍历图的节点，构建一个只包含关键信息的普通对象，再打印：

const printObj = {};
for (const [key, node] of g1.nodes) {
  printObj[key] = {
    value: node.value,
    adjacents: [...node.adjacents].map(n => n.value)
  };
}
console.log(printObj);

控制台输出：

{
  a: { value: 'a', adjacents: [ 'c' ] },
  b: { value: 'b', adjacents: [] },
  c: { value: 'c', adjacents: [ 'a' ] }
}

内容的提问来源于stack exchange，提问作者Cody