Graph Vuex Full

GraphDataStructureFull.js

import Vue from 'vue'

import GraphEdge from '../data/graph/GraphEdge'
import GraphVertex from '../data/graph/GraphVertex'

export default {
  namespaced: true,
  state: {
    vertices: {},
    edges: {},
    isDirected: false
  },
  getters: {
    getVertexByKey: (state) => (key) => {
      return state.vertices[key]
    },
    getAllVertices: (state) => {
      return Object.values(state.vertices)
    },
    getEdgeByKey: (state) => (key) => {
      return state.edges[key]
    },
    getAllEdges: (state) => {
      return Object.values(state.edges)
    }
  },
  mutations: {
    addVertex(state, value) {
      let newVertex = value.constructor.name === 'GraphVertex' ? value : new GraphVertex(value);
      if (!state.vertices[newVertex.getKey()]) {
        Vue.set(state.vertices, newVertex.getKey(), newVertex)
      }
    },
    removeVertex(state, vertex) {
      Vue.delete(state.vertices, vertex)
    },
    addEdge(state, edge) {
      Vue.set(state.edges, edge.getKey(), edge)
    },
    addEdgeToVertex(state, {vertex, edge}) {
      vertex.addEdge(edge)
    },
    removeEdge(state, edge) {
      Vue.delete(state.edges, edge)
    },
    removeEdgeFromVertex(state, {vertex, edge}) {
      vertex.deleteEdge(edge)
    }
  },
  actions: {
    addVertex ({ commit }, value) {
      commit('addVertex', value)
    },
    addEdge(context, { startVertex, endVertex, weight }) {
      // Construct new edge
      let newEdge = new GraphEdge(startVertex, endVertex, weight);

      // Try to find start and end start vertices.
      let storedStartVertex = context.getters.getVertexByKey(newEdge.startVertex.getKey())
      let storedEndVertex = context.getters.getVertexByKey(newEdge.endVertex.getKey())

      // Insert start vertex if it wasn't inserted.
      if (!storedStartVertex) {
        context.commit('addVertex', newEdge.startVertex)
        storedStartVertex = context.getters.getVertexByKey(newEdge.startVertex.getKey())
      }

      // Insert end vertex if it wasn't inserted.
      if (!storedEndVertex) {
        context.commit('addVertex', newEdge.endVertex)
        storedEndVertex = context.getters.getVertexByKey(newEdge.endVertex.getKey())
      }

      // Check if edge has been already added.
      // if (this.edges[edge.getKey()]) {
      if (context.getters.getEdgeByKey(newEdge.getKey())) {
        throw new Error('Edge has already been added before');
      } else {
        context.commit('addEdge', newEdge)
      }

      // Add edge to the vertices.
      if (context.state.isDirected) {
        // If graph IS directed then add the edge only to start vertex.
        // storedStartVertex.addEdge(newEdge)
        context.commit('addEdgeToVertex', {vertex: storedStartVertex, edge: newEdge})
      } else {
        // If graph ISN'T directed then add the edge to both vertices.
        context.commit('addEdgeToVertex', {vertex: storedStartVertex, edge: newEdge})
        context.commit('addEdgeToVertex', {vertex: storedEndVertex, edge: newEdge})
      }
    },
    removeEdge(context, edge) {
      if (context.getters.getEdgeByKey(edge.getKey())) {
        context.commit('removeEdge', edge)
      }
    },
    removeVertex(context, vertex) {
      // Get the vertex's edges
      let neighbors = vertex.getNeighbors()

      // iterate over those edges and get adjacent vertexes
      // remove edge references from adjacent vertexes
      neighbors.forEach(neighbor => {
        let edgeToDelete = neighbor.findEdge(vertex)
        context.commit('removeEdgeFromVertex', { vertex: neighbor, edge: edgeToDelete})
      })

      // remove edges from state
      let edgesToDelete = vertex.getEdges()
      edgesToDelete.forEach(edge => {
        context.commit('removeEdge', edge)
      })

      // delete the vertex
      context.commit('removeVertex', vertex)
    }
  }
}

GraphEdge.js

export default class GraphEdge {
  /**
   * @param {GraphVertex} startVertex
   * @param {GraphVertex} endVertex
   * @param {number} [weight=1]
   */
  constructor(startVertex, endVertex, weight = 0) {
    this.startVertex = startVertex;
    this.endVertex = endVertex;
    this.weight = weight;
  }

  /**
   * @return {string}
   */
  getKey() {
    const startVertexKey = this.startVertex.getKey();
    const endVertexKey = this.endVertex.getKey();

    return `${startVertexKey}_${endVertexKey}`;
  }

  /**
   * @return {GraphEdge}
   */
  reverse() {
    const tmp = this.startVertex;
    this.startVertex = this.endVertex;
    this.endVertex = tmp;

    return this;
  }

  /**
   * @return {string}
   */
  toString() {
    return this.getKey();
  }
}

GraphVertex.js

import LinkedList from '../linkedList/LinkedList';

export default class GraphVertex {
  /**
   * @param {*} value
   */
  constructor(value) {
    if (value === undefined) {
      throw new Error('Graph vertex must have a value');
    }

    /**
     * @param {GraphEdge} edgeA
     * @param {GraphEdge} edgeB
     */
    const edgeComparator = (edgeA, edgeB) => {
      if (edgeA.getKey() === edgeB.getKey()) {
        return 0;
      }

      return edgeA.getKey() < edgeB.getKey() ? -1 : 1;
    };

    // Normally you would store string value like vertex name.
    // But generally it may be any object as well
    this.value = value;
    this.edges = new LinkedList(edgeComparator);
  }

  /**
   * @param {GraphEdge} edge
   * @returns {GraphVertex}
   */
  addEdge(edge) {
    this.edges.append(edge);

    return this;
  }

  /**
   * @param {GraphEdge} edge
   */
  deleteEdge(edge) {
    this.edges.delete(edge);
  }

  /**
   * @returns {GraphVertex[]}
   */
  getNeighbors() {
    const edges = this.edges.toArray();

    /** @param {LinkedListNode} node */
    const neighborsConverter = (node) => {
      return node.value.startVertex === this ? node.value.endVertex : node.value.startVertex;
    };

    // Return either start or end vertex.
    // For undirected graphs it is possible that current vertex will be the end one.
    return edges.map(neighborsConverter);
  }

  /**
   * @return {GraphEdge[]}
   */
  getEdges() {
    return this.edges.toArray().map(linkedListNode => linkedListNode.value);
  }

  /**
   * @return {number}
   */
  getDegree() {
    return this.edges.toArray().length;
  }

  /**
   * @param {GraphEdge} requiredEdge
   * @returns {boolean}
   */
  hasEdge(requiredEdge) {
    const edgeNode = this.edges.find({
      callback: edge => edge === requiredEdge,
    });

    return !!edgeNode;
  }

  /**
   * @param {GraphVertex} vertex
   * @returns {boolean}
   */
  hasNeighbor(vertex) {
    const vertexNode = this.edges.find({
      callback: edge => edge.startVertex === vertex || edge.endVertex === vertex,
    });

    return !!vertexNode;
  }

  /**
   * @param {GraphVertex} vertex
   * @returns {(GraphEdge|null)}
   */
  findEdge(vertex) {
    const edgeFinder = (edge) => {
      return edge.startVertex === vertex || edge.endVertex === vertex;
    };

    const edge = this.edges.find({ callback: edgeFinder });

    return edge ? edge.value : null;
  }

  /**
   * @returns {string}
   */
  getKey() {
    return this.value;
  }

  /**
   * @return {GraphVertex}
   */
  deleteAllEdges() {
    this.getEdges().forEach(edge => this.deleteEdge(edge));

    return this;
  }

  /**
   * @param {function} [callback]
   * @returns {string}
   */
  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}