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]

另外两个细节：

这个结构会经常被阅读，但偶尔会被修改。
"nodes" 可以是字符串键而不是对象，如果这样可以简化事情的话。

我可以将其实现为两个映射：一个映射包含每个源的条目，其值是一组目标，另一个映射包含每个目标的条目，其值是一组源。

问题：

这是明智的做法吗？
在 JavaScript 领域是否已经存在一些数据结构可以做到这一点？

Answer 1

正如@CertainPerformance 所提到的，两个地图（每个地图都包含集合）似乎可以解决问题。结果实现可用：

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

Answer 2

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

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

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

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"/>

JavaScript 中高效的多对多关联

Efficient many-to-many associations in JavaScript

javascript

directed-graph

data-structures

问题：