Introduction to Graphs

Graphs are the perfect data structure for modeling networks, which make them an indispensable piece of your data structure toolkit. They’re composed of nodes, or vertices, which hold data, and edges, which are a connection between two vertices. A single node is a vertex.

Consider a map of the area where you live. As a graph, we could model bus stops as vertices, with bus routes between stops functioning as the edges.

What about the internet? Web pages can be vertices, and the hyperlinks which connect them are edges.

// Edge class
class Edge {
  constructor(start, end, weight = null) {
    this.start = start;
    this.end = end;
    this.weight = weight;
  }
}

// Vertex class
class Vertex {
  constructor(data) {
    this.data = data;
    this.edges = [];
  }

  addEdge(vertex, weight) {
    if (vertex instanceof Vertex) {
      this.edges.push(new Edge(this, vertex, weight));
    } else {
      throw new Error('Edge start and end must both be Vertex');
    }
  }

  removeEdge(vertex) {
    this.edges = this.edges.filter(edge => edge.end !== vertex);
  }

  print() {
    const edgeList = this.edges.map(edge =>
        edge.weight !== null ? `${edge.end.data} (${edge.weight})` : edge.end.data);

    const output = `${this.data} --> ${edgeList.join(', ')}`;
    console.log(output);
  }
}

// Graph class
class Graph {
  constructor(isWeighted = false, isDirected = false) {
    this.vertices = [];
    this.isWeighted = isWeighted;
    this.isDirected = isDirected;
  }

  addVertex(data) {
    const newVertex = new Vertex(data);
    this.vertices.push(newVertex);

    return newVertex;
  }

  removeVertex(vertex) {
    this.vertices = this.vertices.filter(v => v !== vertex);
  }

  addEdge(vertexOne, vertexTwo, weight) {
    const edgeWeight = this.isWeighted ? weight : null;

    if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
      vertexOne.addEdge(vertexTwo, edgeWeight);

      if (!this.isDirected) {
        vertexTwo.addEdge(vertexOne, edgeWeight);
      }
    } else {
      throw new Error('Expected Vertex arguments.');
    }
  }

  removeEdge(vertexOne, vertexTwo) {
    if (vertexOne instanceof Vertex && vertexTwo instanceof Vertex) {
      vertexOne.removeEdge(vertexTwo);

      if (!this.isDirected) {
        vertexTwo.removeEdge(vertexOne);
      }
    } else {
      throw new Error('Expected Vertex arguments.');
    }
  }

  print() {
    this.vertices.forEach(vertex => vertex.print());
  }
}

// Example
const trainNetwork = new Graph(true, true);
const laStation = trainNetwork.addVertex('Los Angeles');
const sfStation = trainNetwork.addVertex('San Francisco');
const nyStation = trainNetwork.addVertex('New York');
const atlStation = trainNetwork.addVertex('Atlanta');
const denStation = trainNetwork.addVertex('Denver');
const calStation = trainNetwork.addVertex('Calgary');

trainNetwork.addEdge(sfStation, laStation, 400);
trainNetwork.addEdge(laStation, sfStation, 400);
trainNetwork.addEdge(nyStation, denStation, 1800);
trainNetwork.addEdge(denStation, nyStation, 1800);
trainNetwork.addEdge(calStation, denStation, 1000);
trainNetwork.addEdge(denStation, calStation, 1000);
trainNetwork.addEdge(atlStation, laStation, 2100);
trainNetwork.addEdge(laStation, atlStation, 2100);

trainNetwork.removeEdge(nyStation, denStation);
trainNetwork.removeEdge(calStation, denStation);
trainNetwork.removeEdge(denStation, calStation);
trainNetwork.removeVertex(calStation);

trainNetwork.print();