Представление взвешенного ориентированного графа в JavaScript - PullRequest
Новая
       17

Представление взвешенного ориентированного графа в JavaScript

0 голосов
/ 27 октября 2019

Каков наилучший способ представления взвешенного ориентированного графа в javascript (для базовых операций dfs, bfs и т. Д.)? Я перепробовал несколько подходов и удивляюсь, есть ли еще консенсус.

Мой первый подход заключается в том, чтобы каждая карта ключей соответствовала массиву соединений. Где соединение имеет «другой» ключ и значение, представляющее вес. 

interface Connection {
  key: string;
  value: number;
}

export default class Graph {
  size: number = 0;
  adj: Map<string, Array<Connection>> = new Map();

  constructor(size: number) {
    this.size = size;
  }

В другом подходе хранилище соединений может быть от и до и иметь такой вес. Я думал, что это было бы отчасти избыточно, поскольку ключ - это ключ from: 

interface Connection {
   from: string;
   to: string;
   weight: number;
}

export default class Graph {
      size: number = 0;
      adj: Map<string, Array<Connection>> = new Map();

      constructor(size: number) {
        this.size = size;
      }

Тогда, наконец, я подумал, что я могу настроить что-то подобное с помощью карт: 

interface Metadata {
  weight: number;
  metadata2: string;
  ...
}

export default class Graph {
  size: number = 0;
  adj: Map<string, Map<string, Metadata>> = new Map();
  constructor(size: number) {
    this.size = size;
  }

Моя цель на самом деле просто создать что-то гибкое, чтобы я мог выполнять на нем различные графовые операции и алгоритмы. Есть ли недостаток в использовании двух карт с метаданными вместо использования идеи соединения? Я просто хотел услышать чужой вклад, кроме моего собственного. Я был в состоянии успешно реализовать все, что я пытался, используя идею соединения, но затем недавно подумал об использовании двух уровней карт для узлов и от узлов. Есть ли минусы к этому? У кого-нибудь есть лучший подход? Без метаданных я мог легко представлять края, но с добавлением веса мне было любопытно, как люди представляли это в js.

...