Как создать ребра между узлами, которые имеют сходство

Question

У меня есть простой класс Graph, и мне нужно создать граф с узлами и ребрами.Между двумя узлами есть ребро, nodeA, nodeB, если массив в nodeA и nodeB имеет некоторые сходства.

Например:

const example = [{
  "node": "A",
  "data": [ 1, 2, 3 ]
}, {
  "node": "B",
  "data": [ 3, 4, 5 ]
}, {
  "node": "C",
  "data": [ 5, 6, 7 ]
}, {
  "node": "D",
  "data": [ 7, 8, 9 ]
}]

Это означаетчто существует грань между:

1. A и B, потому что 3 массива на обоих data массивах.

2. B и C, потому что 5 массивов на обоих data массивах.

3. C и D, потому что 7 рядов на обоих data массивах.

По сути, у нас есть ребро из A -> B -> C -> D

Мне удалось создать график и использовать список смежности для хранения ребер, но проблема в том, что я не знаю, как создавать ребрамежду узлами, которые имеют сходство.Наивным решением было бы посмотреть на example[i - 1] и example[i].Но это неправильно, потому что данные приходят не по порядку.

class Graph {

  constructor(numOfVertex) {

    this.adj = new Map();

  }

  addNodes(node) {

    this.adj.set(node, []);  

  }

  addEdge(nodeA, nodeB) {

    this.adj.get(nodeA).push(nodeB);

    this.adj.get(nodeA).push(nodeB);

  };

}

и для заполнения графика я делаю:

    const graph = new Graph(example.length);

    for (let i = 0; i < example.length; i++) {

      const { node, data } = example[i];

      graph.addVertex(title)

      G.addEdge(...)

    }

Любые идеи о том, как я могу перебрать данныемассив каждого узла, чтобы эффективно видеть сходства?

Ради вопроса я привел небольшой пример данных, на самом деле, я перебираю большой набор данных.

Answer 1

В зависимости от размера data массивов и разреженности результирующего графа, есть несколько способов решения этой проблемы:

• Выполните итерацию по всем парам узлов и вычислите, имеют ли оникрай.Это вычисление может быть выполнено в O(|data[A]| + |data[B]|) для пары узлов (A, B), поэтому сложность этого решения составляет O(N^2 + N * (sum of data[i] over all i)).Это хорошо работает, если ваш график плотный, т. Е. Количество ребер в нем имеет порядок N ² .
• Построить карту (X -> ListOfNodes) так, чтобы каждое числоX отображается на все узлы, которые содержат X в своих данных.Каждая пара узлов, принадлежащих одному и тому же списку, должна быть связана с ребром.Сложность этого решения O((sum of data[i] over all i) + (a hard to estimate quantity that is the number of times each pair of nodes shares a data point)).Для разреженных графиков это должно работать лучше, чем предыдущий подход, но на самом деле это зависит от того, как строятся массивы данных.

Как генерируются ваши данные?