Make it possible to delete edge from graph.

trekhleb · trekhleb · commit 808a1e713ffe · 2018-05-11T16:58:39.000+03:00
diff --git a/src/data-structures/graph/Graph.js b/src/data-structures/graph/Graph.js
@@ -88,6 +88,25 @@ export default class Graph {
     return this;
   }
 
+  /**
+   * @param {GraphEdge} edge
+   */
+  deleteEdge(edge) {
+    // Delete edge from the list of edges.
+    if (this.edges[edge.getKey()]) {
+      delete this.edges[edge.getKey()];
+    } else {
+      throw new Error('Edge not found in graph');
+    }
+
+    // Try to find and end start vertices and delete edge from them.
+    const startVertex = this.getVertexByKey(edge.startVertex.getKey());
+    const endVertex = this.getVertexByKey(edge.endVertex.getKey());
+
+    startVertex.deleteEdge(edge);
+    endVertex.deleteEdge(edge);
+  }
+
   /**
    * @param {GraphVertex} startVertex
    * @param {GraphVertex} endVertex
diff --git a/src/data-structures/graph/__test__/Graph.test.js b/src/data-structures/graph/__test__/Graph.test.js
@@ -218,4 +218,47 @@ describe('Graph', () => {
 
     expect(graph.getWeight()).toBe(10);
   });
+
+  it('should be possible to delete edges from graph', () => {
+    const graph = new Graph();
+
+    const vertexA = new GraphVertex('A');
+    const vertexB = new GraphVertex('B');
+    const vertexC = new GraphVertex('C');
+
+    const edgeAB = new GraphEdge(vertexA, vertexB);
+    const edgeBC = new GraphEdge(vertexB, vertexC);
+    const edgeAC = new GraphEdge(vertexA, vertexC);
+
+    graph
+      .addEdge(edgeAB)
+      .addEdge(edgeBC)
+      .addEdge(edgeAC);
+
+    expect(graph.getAllEdges().length).toBe(3);
+
+    graph.deleteEdge(edgeAB);
+
+    expect(graph.getAllEdges().length).toBe(2);
+    expect(graph.getAllEdges()[0].getKey()).toBe(edgeBC.getKey());
+    expect(graph.getAllEdges()[1].getKey()).toBe(edgeAC.getKey());
+  });
+
+  it('should should throw an error when trying to delete not existing edge', () => {
+    function deleteNotExistingEdge() {
+      const graph = new Graph();
+
+      const vertexA = new GraphVertex('A');
+      const vertexB = new GraphVertex('B');
+      const vertexC = new GraphVertex('C');
+
+      const edgeAB = new GraphEdge(vertexA, vertexB);
+      const edgeBC = new GraphEdge(vertexB, vertexC);
+
+      graph.addEdge(edgeAB);
+      graph.deleteEdge(edgeBC);
+    }
+
+    expect(deleteNotExistingEdge).toThrowError();
+  });
 });
