JavaScript 中高效的多对多关联

Question

在我的客户端 JavaScript 应用程序中，我需要一个多对多关联机制来表示有向图的边：一个源可以有多个目标，一个目标可以有多个源，例如：{source:n1, target:n2}{source:n1, target:n3}{source:n1, target:n4}{source:n2, target:n3}{source:n3, target:n4}我需要执行四个操作：add_link(n1, n2); // add a link (unless present)has_link(n2, n4); // => false (no entry with source:n2 and target:n4)targets_of(n1);   // => [n2, n3, n4]sources_of(n4);   // => [n1, n3]另外两个细节：这种结构会经常被阅读，但只是偶尔修改。如果这样可以简化事情，“节点”可以是字符串键而不是对象。我可以将其实现为两个映射：一个映射包含每个源的条目，其值是一组目标，另一个映射包含每个目标的条目，其值是一组源。问题：这是一个明智的做法吗？JavaScript 领域中是否已经存在一些数据结构可以做到这一点？

Answer 1

不知道为什么 Fearless 没有嵌入他的示例，但我冒昧地将其转换为带有 Mocha/Chai 单元测试的 ES6 类。

正如其他人所提到的，有向图应该将其关联（也称为边）存储在两个单独的集合中。

这使得查找变得微不足道。

class AssociationGraph {

  constructor() {

    this.sourceEdges = new Map();

    this.targetEdges = new Map();

  }

  /**

   * @brief Clear all associations

   */

  clear() {

    this.sourceEdges.clear();

    this.targetEdges.clear();

  }

  /**

   * @brief Return true if there is a link from source to target

   */

  hasLink(source, target) {

    let targets = this.sourceEdges.get(source);

    return targets != undefined && targets.has(target);

  }

  /**

   * @brief Create a link from source to target, unless one already exists.

   */

  addLink(source, target) {

    this._add(source, target, this.sourceEdges);

    this._add(target, source, this.targetEdges);

  }

  /**

   * @brief Return an iterator over all the targets of source.

   */

  targetsOf(source) {

    return this._of(source, this.sourceEdges);

  }

  /**

   * @brief Return an iterator over all the sources of target.

   */

  sourcesOf(target) {

    return this._of(target, this.targetEdges);

  }

  /**

   * @brief Return all unique nodes for all associations.

   */

  nodes() {

    return [...new Set([...this.sourceEdges.keys(), ...this.targetEdges.keys()])];

  }

  /**

   * @brief Return an iterator that generates edges e.g. {source: a, target:b}

   * for all links in the association.

   */

  edges() {

    let self = this;

    return (function*() {

      for (let [ srcKey, srcVal ] of self.sourceEdges.entries()) {

        for (let [ tarKey, tarVal ] of srcVal.entries()) {

          yield { source: srcKey, target: tarKey };

        }

      }

    })();

  }

  _add(a, b, store) {

    let set = store.get(a);

    if (set == undefined) {

      set = new Set();

      store.set(a, set);

    }

    set.add(b);

  }

  _of(a, map) {

    let b = map.get(a);

    if (b == undefined) {

      return new Set();

    } else {

      return b.keys();

    }

  }

}

// Construct a graph by adding associations

let graph = new AssociationGraph();

graph.addLink('n1', 'n2');

graph.addLink('n1', 'n3');

graph.addLink('n1', 'n4');

graph.addLink('n2', 'n3');

graph.addLink('n3', 'n4');

// Print the nodes

//for (let node of graph.nodes()) console.log(node);

// Print the edges

//for (let edge of graph.edges()) console.log(JSON.stringify(edge));

// Convenience function to transform a CSV string into an array

const strSet = (str) => str.trim().length > 0 ? str.split(/,/g) : [];

// Run a unit test

let assert = chai.assert,

    expect = chai.expect,

    should = chai.should;

mocha.setup("bdd");

chai.should();

describe('hasLink', () => {

  it('n1 ===> n2', () => graph.hasLink('n1', 'n2').should.equal(true));

  it('n2 =/=> n4', () => graph.hasLink('n2', 'n4').should.equal(false));

  it('n3 ===> n4', () => graph.hasLink('n3', 'n4').should.equal(true));

});

describe('targetsOf', () => {

  it('n1 : [n2, n3, n4]', () => expect(

    Array.from(graph.targetsOf('n1'))).to.have.members(strSet('n2,n3,n4')));

  it('n2 : [n3]', () => expect(

    Array.from(graph.targetsOf('n2'))).to.have.members(strSet('n3')));

  it('n3 : [n4]', () => expect(

    Array.from(graph.targetsOf('n3'))).to.have.members(strSet('n4')));

  it('n4 : []', () => expect(

    Array.from(graph.targetsOf('n4'))).to.have.members(strSet('')));

});

describe('sourcesOf', () => {

  it('n1 : []', () => expect(

    Array.from(graph.sourcesOf('n1'))).to.have.members(strSet('')));

  it('n2 : [n1]', () => expect(

    Array.from(graph.sourcesOf('n2'))).to.have.members(strSet('n1')));

  it('n3 : [n1, n2]', () => expect(

    Array.from(graph.sourcesOf('n3'))).to.have.members(strSet('n1,n2')));

  it('n4 : [n1, n3]', () => expect(

    Array.from(graph.sourcesOf('n4'))).to.have.members(strSet('n1,n3')));

});

describe('nodes', () => {

  it('graph.nodes()', () => expect( Array.from(graph.nodes())).to.have.members(strSet('n1,n2,n3,n4')));

});

mocha.run();

#mocha-report {

  font-family: monospace;

  font-size: smaller;

}

<script src="https://cdnjs.cloudflare.com/ajax/libs/chai/4.2.0/chai.min.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/mocha/7.1.1/mocha.min.js"></script><div id="mocha"></div>

<link href="https://cdnjs.cloudflare.com/ajax/libs/mocha/7.1.1/mocha.min.css" rel="stylesheet"/>

Answer 2

正如@CertainPerformance 所提到的，两个包含集合的地图似乎可以解决问题。产生的实施可用于：

https://gist.github.com/rdpoor/89ea64cb00107be368b2b69d7a89bb6c