js Graph using Map class - where to store weight?

Question

I've looked at a dozen examples but can't find any of a weighted graph using the JS Map object (except one with no weight).

Is there a preferred place to put the weight?

Here are the basic class structures:

/**
 * @typedef {any} NodeData The Vertex data and used as a key in lists.
 * @typedef {Map<NodeData, Vertex>} AdjacencyList
 */

class Vertex {
  constructor(data) {
    this.data = data;
    /**
     * @type {AdjacencyList}
     */
    this.edges = new Map();
  }
}

class Graph {
  constructor() {
    /**
     * @type {AdjacencyList}
     */
    this.vertices = new Map();
}

I can't put the weight in my Vertex class I think since the same vertex can be an edge of many others by reference so it needs to be able to have different weights.

My idea is to make an Edge class like so:

class Edge {
  /**
   * @param {Vertex} point
   * @param {number} weight The cost to travel to this point.
   */
  constructor(point, weight) {
    this.point = point;
    this.weight = weight;
  }
}

However, this is a bit annoying for things like listing the nodes in a path, because of mixing data types Vertex and Edge since you start at a Vertex first. To avoid this it starts getting less elegant and I feel like I'm missing something. For example I could put the first Vertex visited into a new Edge instance with a 0 weight so I can have a list of all Edge types returned.

Also, for undirected, this means the same weight value is duplicated to both sides which makes me wonder if that's supposed to be avoided.

Appreciate any insight!

Answer 1

Don't key that edges map by the data of the node it is pointing at. That would make updating the data of a node a real hazzle. Instead, use a Map<Vertex, Weight> for your edges.

An alternative would be to use two maps: neighbors: Map<key, Vertex> and weights: Map<key, Weight>, where you ensure in your methods that the key set is kept in sync. Notice however that a normal AdjacencyList is just a list, it is not keyed at all.