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 {&nbsp; constructor() {&nbsp; &nbsp; this.sourceEdges = new Map();&nbsp; &nbsp; this.targetEdges = new Map();&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Clear all associations&nbsp; &nbsp;*/&nbsp; clear() {&nbsp; &nbsp; this.sourceEdges.clear();&nbsp; &nbsp; this.targetEdges.clear();&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Return true if there is a link from source to target&nbsp; &nbsp;*/&nbsp; hasLink(source, target) {&nbsp; &nbsp; let targets = this.sourceEdges.get(source);&nbsp; &nbsp; return targets != undefined && targets.has(target);&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Create a link from source to target, unless one already exists.&nbsp; &nbsp;*/&nbsp; addLink(source, target) {&nbsp; &nbsp; this._add(source, target, this.sourceEdges);&nbsp; &nbsp; this._add(target, source, this.targetEdges);&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Return an iterator over all the targets of source.&nbsp; &nbsp;*/&nbsp; targetsOf(source) {&nbsp; &nbsp; return this._of(source, this.sourceEdges);&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Return an iterator over all the sources of target.&nbsp; &nbsp;*/&nbsp; sourcesOf(target) {&nbsp; &nbsp; return this._of(target, this.targetEdges);&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Return all unique nodes for all associations.&nbsp; &nbsp;*/&nbsp; nodes() {&nbsp; &nbsp; return [...new Set([...this.sourceEdges.keys(), ...this.targetEdges.keys()])];&nbsp; }&nbsp; /**&nbsp; &nbsp;* @brief Return an iterator that generates edges e.g. {source: a, target:b}&nbsp; &nbsp;* for all links in the association.&nbsp; &nbsp;*/&nbsp; edges() {&nbsp; &nbsp; let self = this;&nbsp; &nbsp; return (function*() {&nbsp; &nbsp; &nbsp; for (let [ srcKey, srcVal ] of self.sourceEdges.entries()) {&nbsp; &nbsp; &nbsp; &nbsp; for (let [ tarKey, tarVal ] of srcVal.entries()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield { source: srcKey, target: tarKey };&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; })();&nbsp; }&nbsp; _add(a, b, store) {&nbsp; &nbsp; let set = store.get(a);&nbsp; &nbsp; if (set == undefined) {&nbsp; &nbsp; &nbsp; set = new Set();&nbsp; &nbsp; &nbsp; store.set(a, set);&nbsp; &nbsp; }&nbsp; &nbsp; set.add(b);&nbsp; }&nbsp; _of(a, map) {&nbsp; &nbsp; let b = map.get(a);&nbsp; &nbsp; if (b == undefined) {&nbsp; &nbsp; &nbsp; return new Set();&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; return b.keys();&nbsp; &nbsp; }&nbsp; }}// Construct a graph by adding associationslet 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 arrayconst strSet = (str) => str.trim().length > 0 ? str.split(/,/g) : [];// Run a unit testlet assert = chai.assert,&nbsp; &nbsp; expect = chai.expect,&nbsp; &nbsp; should = chai.should;mocha.setup("bdd");chai.should();describe('hasLink', () => {&nbsp; it('n1 ===> n2', () => graph.hasLink('n1', 'n2').should.equal(true));&nbsp; it('n2 =/=> n4', () => graph.hasLink('n2', 'n4').should.equal(false));&nbsp; it('n3 ===> n4', () => graph.hasLink('n3', 'n4').should.equal(true));});describe('targetsOf', () => {&nbsp; it('n1 : [n2, n3, n4]', () => expect(&nbsp; &nbsp; Array.from(graph.targetsOf('n1'))).to.have.members(strSet('n2,n3,n4')));&nbsp; it('n2 : [n3]', () => expect(&nbsp; &nbsp; Array.from(graph.targetsOf('n2'))).to.have.members(strSet('n3')));&nbsp; it('n3 : [n4]', () => expect(&nbsp; &nbsp; Array.from(graph.targetsOf('n3'))).to.have.members(strSet('n4')));&nbsp; it('n4 : []', () => expect(&nbsp; &nbsp; Array.from(graph.targetsOf('n4'))).to.have.members(strSet('')));});describe('sourcesOf', () => {&nbsp; it('n1 : []', () => expect(&nbsp; &nbsp; Array.from(graph.sourcesOf('n1'))).to.have.members(strSet('')));&nbsp; it('n2 : [n1]', () => expect(&nbsp; &nbsp; Array.from(graph.sourcesOf('n2'))).to.have.members(strSet('n1')));&nbsp; it('n3 : [n1, n2]', () => expect(&nbsp; &nbsp; Array.from(graph.sourcesOf('n3'))).to.have.members(strSet('n1,n2')));&nbsp; it('n4 : [n1, n3]', () => expect(&nbsp; &nbsp; Array.from(graph.sourcesOf('n4'))).to.have.members(strSet('n1,n3')));});describe('nodes', () => {&nbsp; it('graph.nodes()', () => expect( Array.from(graph.nodes())).to.have.members(strSet('n1,n2,n3,n4')));});mocha.run();#mocha-report {&nbsp; font-family: monospace;&nbsp; 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