Эффективные ассоциации многие-ко-многим в 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 не встраивал свой пример, но я позволил себе преобразовать его в класс ES6 с помощью модульных тестов Mocha / Chai.

Как уже упоминали другие, диаграмма направленности должна хранить свои ассоциации (иначе края) в двух отдельных наборах.

Это делает поиск тривиальным.

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